视频字幕
今天我们来学习用匈牙利法求解指派问题。指派问题是运筹学中的经典问题，目标是在满足约束条件下，找到使总成本或总时间最少的分配方案。在这个例子中，我们有四个人甲乙丙丁，需要完成四项任务A、B、C、D。表格显示了每个人完成各项任务所需的时间。我们的目标是找到一种分配方案，使得总的完成时间最少。
匈牙利法是解决指派问题的经典算法。它的核心思想是通过行变换和列变换，在成本矩阵中产生尽可能多的零元素，然后寻找独立零元素来构成最优解。算法分为三个主要步骤：第一步是行变换，每行减去该行的最小值；第二步是列变换，每列减去该列的最小值；第三步是寻找独立零元素。独立零元素的特点是每行每列只能选择一个零元素，这样就能保证每个人只分配一个任务，每个任务只分配给一个人。
现在开始第一步行变换。行变换的规则是每行减去该行的最小值。首先我们找出每行的最小值：甲这一行最小值是7，乙这一行最小值是7，丙这一行最小值是8，丁这一行最小值是7。然后每行的所有元素都减去对应的最小值。经过行变换后，我们可以看到每行都至少有一个零元素，这为后续寻找独立零元素奠定了基础。
接下来进行第二步列变换。列变换的规则是每列减去该列的最小值。我们检查行变换后的矩阵，找出每列的最小值：任务A列最小值是0，任务B列最小值是0，任务C列最小值是4，任务D列最小值是0。然后每列的所有元素都减去对应的最小值。经过列变换后，矩阵中出现了更多的零元素，这为寻找独立零元素创造了更好的条件。
现在开始寻找独立零元素。独立零元素的选择规则是每行每列只能选择一个零元素。我们按照以下步骤进行：首先找到只有一个零的行或列，选择该零元素，然后划掉同行同列的其他零元素。通过这个过程，我们找到了四个独立零元素：甲选择任务D，乙选择任务B，丙选择任务A，丁选择任务C。这就是我们的最优分配方案。