指派问题 - 平衡型

1. 声音
   观察依据

   主讲人提到了“行数”和“四行”。

2. 图示
   观察依据

   该矩阵有四行，标记为 A、B、C、D。

rows

成本矩阵中的水平线，代表人员或代理。

矩阵中水平线的集合。

1. 声音
   观察依据

   主讲人提到了“列数”和“四列”。

2. 图示
   观察依据

   该矩阵有四列，标记为1、2、3、4。

columns

成本矩阵中的垂直线，代表工作或任务。

矩阵中垂直线的集合。

1. 声音
   观察依据

   主讲人说：“减去每一行的最小元素”。

2. 公式
   观察依据

   进行形如$10 - 10 = 0$、$12 - 10 = 2$的计算。

minimum entry

在成本矩阵某一行中找到的最小数值。

矩阵中出现的实数。

1. 图示
   观察依据

   手写矩阵使用行标签 A、B、C 和 D。

A, B, C, D

成本矩阵的行标签，代表指派问题中的人或任务。

四个行索引组成的集合。

1. 图示
   观察依据

   手写矩阵使用列标签1、2、3和4。

1, 2, 3, 4

成本矩阵的列标签，代表指派问题中的任务或人。

四个列索引组成的集合。

1. 图示
   观察依据

   第1步矩阵写作一个$4\times 4$数组，其行分别为：$A=(0,2,9,1)$，$B=(0,5,2,3)$，$C=(1,3,2,0)$，$D=(0,4,3,1)$。

Step 1 matrix

行约简后得到的矩阵，作为列约简的输入。

$4\times 4$非负整数矩阵。

1. 图示
   观察依据

   第2步矩阵逐步填入数值，最终形成如下各行：$A=(0,0,7,1)$，$B=(0,3,0,3)$，$C=(1,1,0,0)$，$D=(0,2,1,1)$。

Step 2 matrix

对第1步矩阵进行列约简后得到的矩阵。

$4\times 4$非负整数矩阵。

1. 图示
   观察依据

   两个矩阵的行均标记为 A、B、C、D。

2. 声音
   观察依据

   主讲人将它们称为人员 A、B、C 和 D。

A, B, C, D

指分配问题中的人员（即各行）。

由4名人员组成的集合。

1. 图示
   观察依据

   两个矩阵的列均标记为1、2、3、4。

2. 声音
   观察依据

   主讲人将它们称为工作1、2、3和4。

1, 2, 3, 4

指分配问题中的工作（即各列）。

由4项工作组成的集合。

1. 图示
   观察依据

   页面顶部展示了一个$4\times 4$矩阵，其元素为10、12、19、11等形式。

Cost Matrix

原始矩阵，其中每个元素表示将对应人员分配至对应工作的成本。

一个$4\times 4$的非负整数矩阵。

1. 图示
   观察依据

   一个 4x4 矩阵，位于“步骤 2：列约简”下，其中仅包含零和正整数。

Reduced Matrix

匈牙利法中经过行约简与列约简后的矩阵。

$4\times 4$的非负整数矩阵。

1. 图示
   观察依据

   顶部矩阵在“人员”标题下列出行为 A、B、C、D。

A, B, C, D

指派成本矩阵中的人员标签（行）。

成本矩阵的行索引。

1. 声音
   观察依据

   主讲人根据行数与列数是否相等，定义了平衡型与非平衡型指派问题。

2. 图示
   观察依据

   标题“平衡型指派问题”书写在顶部。

当行数（人员数）等于列数（任务数）时，该指派问题称为平衡型；若二者不相等，则称为非平衡型指派问题。

1. 平衡型问题中，行数等于列数。

1. 声音
   观察依据

   主讲人指出：“我们必须采用匈牙利法来求解该问题。”

匈牙利法是一种用于最优求解指派问题的算法。

1. 适用于平衡型指派问题。

1. 平衡型 vs 非平衡型指派问题

1. 声音
   观察依据

   主讲人讲解：“首先需进行行约减，即对每一行，用该行各元素中的最小值分别减去该行所有元素。”

2. 图示
   观察依据

   在原矩阵下方绘制一个新的空矩阵，用于记录约减后的数值。

匈牙利法的第一步是：在成本矩阵的每一行中找出最小元素，并将该最小值从该行所有元素中减去。

1. 需要原始成本矩阵。

1. 匈牙利法

1. 图示
   观察依据

   页面标题显示：“解：这是一个平衡的指派问题。”

2. 声音
   观察依据

   讲解者讨论将每项工作指派给一个人，这符合指派问题的标准设定。

本视频将给定的$4\times 4$成本表视为一个平衡的指派问题，即行数等于列数，从而可以寻求一一对应的指派。

1. 该成本矩阵是方阵（行数与列数相等）。

2. 每项工作必须且仅能指派给一个人。

1. 声音
   观察依据

   接下来我们要进入下一步，即列约减。

2. 声音
   观察依据

   现在我们考虑第一列，需将该列中的最小元素从本列其余各元素中减去。

3. 图示
   观察依据

   主讲人写下一个新的 4x4 矩阵，置于“步骤 2：列约简”下方，方法是从步骤 1 的矩阵中减去各列的最小值。

在行约减之后，下一步是列约减：对当前矩阵的每一列，找出其中最小的元素，并将该最小值从该列所有元素中减去。这一操作生成一个新矩阵，同时保持各列内部元素间的相对差值不变。

1. 将此步骤应用于行约减后所得的矩阵。

2. 对每一列分别减去该列的最小值。

1. 平衡的指派问题

1. 声音
   观察依据

   '现在我们需要转到step three。'

2. 声音
   观察依据

   '我们需要从本步骤所得矩阵的第一行开始，逐行检查每行包含多少个零。'

3. 声音
   观察依据

   '因此我们现在需要验证每行和每列是否都恰好有一个零。'

4. 图示
   观察依据

   笔尖在步骤2矩阵的各行之间移动，同时说话者逐行计数零的个数。

列约简之后的下一步是逐行检查约简后的矩阵，并统计每行所含零的个数。说话者指出，目标是在进行分配之前确保每行和每列都恰好有一个零。

1. 使用列约简后得到的矩阵。

2. 按顺序逐行检查，并统计每行中零的个数。

1. 匈牙利法中的列约减步骤

1. 图示
   观察依据

   矩阵上方可见文字“第2步：列约简”。

2. 声音
   观察依据

   讲解者说明如何选择零元素，并划去同一列中其余的零元素。

在匈牙利法的列约简步骤中，需选取零元素，使得每行与每列均恰好有一个被选中的零。当某行的一个零被选中后，该零所在列的其他零即被划去，以避免同一项工作被多次分配。

1. 该矩阵必须是方阵或已平衡。

2. 为获得最优指派，每行与每列都必须恰好有一个被选中的零。

1. 声音
   观察依据

   讲解者称“所有人员均已分配工作”，并逐一列出各项指派。

2. 图示
   观察依据

   带圆圈的零出现在位置(A,2)、(B,3)、(C,4)和(D,1)。

一旦找到一组覆盖全部行与列的独立零元素，其对应的位置即构成最优指派。每个带圆圈的零表示将该零所在行所代表的人员，指派给该零所在列所代表的工作。

1. 一个 $n \times n$ 矩阵中必须恰好有 n 个独立零。

1. 匈牙利法中的列约简步骤

1. 图示
   观察依据

   纸上写着文字“这是一个平衡的指派问题”。

当人员（或源点）数量等于工作（或目的地）数量时，该指派问题即为平衡的。本视频中，有4名人员和4项工作，因此构成一个平衡问题。

1. 人员数 = 工作数

1. 图示
   观察依据

   第二张矩阵上方写着文字“步骤1：行约减”。

2. 图示
   观察依据

   画面可见已完成的行约简矩阵；对照原始表格，各行最小值为10、5、11、8。

匈牙利法求解指派问题的第一步：找出成本矩阵每一行的最小元素，并将该最小值从该行所有元素中减去。

1. 应用于初始成本矩阵。

1. 平衡的指派问题

1. 图示
   观察依据

   第三张矩阵上方写着文字‘步骤2：列约简’。

匈牙利法的第二步：对已完成行约简的矩阵，找出每一列的最小元素，并将该最小值从该列所有元素中减去。

1. 应用于已行约简的矩阵。

1. 行约简步骤

1. 图示
   观察依据

   在列约简后的矩阵中，对零元素进行圈出或划去操作，以确保每行每列恰好选中一个零；所选指派结果列于表格中：人员A分配至工作2，B分配至工作3，C分配至工作4，D分配至工作1。

完成行约简与列约简后，矩阵中的零元素代表潜在的最优指派；目标是选出一组零，使得每行和每列均恰好包含一个被选中的零。具体操作为：圈出一个零，同时划去其所在行与列中的其余零，重复此过程直至所有行与列均被覆盖。

1. 该矩阵必须已通过行约简与列约简步骤完成约简。

1. 列约简步骤

1. 声音
   观察依据

   '现在这个问题的核心在于：每项工作必须分配给一个人。'

在当前求解的指派问题中，每项工作必须且只能分配给一个人。

1. 该问题是一个平衡的指派问题。

每项工作恰好分配给一个人。

1. 声音
   观察依据

   因此，现在我们需要检查每一行和每一列是否都恰好有一个零。

1. 主讲人将此作为检验条件提出，但在本片段中并未充分说明为何此时该条件已足够。

在进入指派选择步骤之前，应先检验约减后的矩阵，确保其每一行和每一列都恰好有一个零。

1. 该矩阵已完成行约减与列约减。

针对约减后矩阵的每一行和每一列。

1. 声音
   观察依据

   讲解者计算$10-10=0$，$12-10=2$，$19-10=9$，$11-10=1$。

2. 图示
   观察依据

   数值0、2、9、1被写入新矩阵的第一行。

1. 公式

   $$10 - 10 = 0$$
   解释

   从A行的第一个元素中减去该行的最小元素（10）。

   步骤依据

   行约简规则。

   视频直接表达
2. 公式

   $$12 - 10 = 2$$
   解释

   从A行的第二个元素中减去该行的最小元素（10）。

   步骤依据

   行约简规则。

   视频直接表达
3. 公式

   $$19 - 10 = 9$$
   解释

   从A行的第三个元素中减去该行的最小元素（10）。

   步骤依据

   行约简规则。

   视频直接表达
4. 公式

   $$11 - 10 = 1$$
   解释

   从A行的第四个元素中减去该行的最小元素（10）。

   步骤依据

   行约简规则。

   视频直接表达

约简后的第一行为[0, 2, 9, 1]。

1. 声音
   观察依据

   讲解者计算5减5等于0，10减5等于5，7减5等于2，8减5等于3。

2. 图示
   观察依据

   数值0、5、2、3被写入新矩阵的第二行。

1. 公式

   $$5 - 5 = 0$$
   解释

   从B行的第一个元素中减去最小元素（5）。

   步骤依据

   行约简规则。

   视频直接表达
2. 公式

   $$10 - 5 = 5$$
   解释

   从B行的第二个元素中减去最小元素（5）。

   步骤依据

   行约简规则。

   视频直接表达
3. 公式

   $$7 - 5 = 2$$
   解释

   从B行的第三个元素中减去最小元素（5）。

   步骤依据

   行约简规则。

   视频直接表达
4. 公式

   $$8 - 5 = 3$$
   解释

   从B行的第四个元素中减去最小元素（5）。

   步骤依据

   行约简规则。

   视频直接表达

约简后的第二行为[0, 5, 2, 3]。

1. 声音
   观察依据

   讲解者计算12减11等于1，14减11等于3，13减11等于2，11减11等于0。

2. 图示
   观察依据

   数值1、3、2、0写入新矩阵的第三行。

1. 公式

   $$12 - 11 = 1$$
   解释

   从C行的第一个元素中减去最小元素（11）。

   步骤依据

   行约简规则。

   视频直接表达
2. 公式

   $$14 - 11 = 3$$
   解释

   从C行的第二个元素中减去最小元素（11）。

   步骤依据

   行约简规则。

   视频直接表达
3. 公式

   $$13 - 11 = 2$$
   解释

   从C行的第三个元素中减去最小元素（11）。

   步骤依据

   行约简规则。

   视频直接表达
4. 公式

   $$11 - 11 = 0$$
   解释

   从C行的第四个元素中减去最小元素（11）。

   步骤依据

   行约简规则。

   视频直接表达

约简后的第三行为[1, 3, 2, 0]。

1. 声音
   观察依据

   讲解者开始计算8减8等于0，12减8等于4。

2. 图示
   观察依据

   数值0、4在视频结束前被写入新矩阵的第四行。

1. 第D行最后两个元素的计算因视频结束而被截断。

1. 公式

   $$8 - 8 = 0$$
   解释

   用第D行的第一个元素减去最小元素（8）。

   步骤依据

   行约简规则。

   视频直接表达
2. 公式

   $$12 - 8 = 4$$
   解释

   用第D行的第二个元素减去最小元素（8）。

   步骤依据

   行约简规则。

   视频直接表达

约简后的第四行以[0, 4, …]开头。

1. 声音
   观察依据

   主讲人解释了如何从该列所有元素中减去该列的最小元素。

2. 图示
   观察依据

   步骤2的矩阵按列由步骤1的矩阵填充而成。

1. 公式

   $$\begin{bmatrix}0&2&9&1\\0&5&2&3\\1&3&2&0\\0&4&3&1\end{bmatrix}$$
   解释

   从页面上所示的步骤1矩阵开始。

   步骤依据

   直接从手写的矩阵中观察得出。

   视频直接表达
2. 公式

   $$\min(0,0,1,0)=0$$
   解释

   对于第1列，最小元素是0，因此减去0后该列保持不变。

   步骤依据

   说话者陈述的列最小值规则。

   视频直接表达
3. 公式

   $$\min(2,5,3,4)=2$$
   解释

   对于第2列，最小元素是2。

   步骤依据

   说话者陈述的列最小值规则。

   视频直接表达
4. 公式

   $$(2-2,5-2,3-2,4-2)=(0,3,1,2)$$
   解释

   从第 2 列的每个元素中减去 2，以得到新的第 2 列元素。

   步骤依据

   对已识别出的列最小值进行算术减法运算。

   视频直接表达
5. 公式

   $$\min(9,2,2,3)=2$$
   解释

   对于第3列，最小元素是2。

   步骤依据

   说话者陈述的列最小值规则。

   视频直接表达
6. 公式

   $$(9-2,2-2,2-2,3-2)=(7,0,0,1)$$
   解释

   从第 2 列的每个元素中减去 3，以得到新的第 3 元素。

   步骤依据

   对已识别出的列最小值进行算术减法运算。

   视频直接表达
7. 公式

   $$\min(1,3,0,1)=0$$
   解释

   对于第4列，最小元素是0，因此该列保持不变。

   步骤依据

   主讲人陈述的列最小值规则。

   视频直接表达
8. 公式

   $$\begin{bmatrix}0&0&7&1\\0&3&0&3\\1&1&0&0\\0&2&1&1\end{bmatrix}$$
   解释

   将变换后的各列组合起来，构成第2步矩阵。

   步骤依据

   按列汇总计算结果。

   视频直接表达

列约简后的矩阵为[[0,0,7,1],[0,3,0,3],[1,1,0,0],[0,2,1,1]]。

1. 声音
   观察依据

   主讲人依次检查第一、第二、第三和最后一行，并指出每行均含有两个零。

2. 图示
   观察依据

   笔尖指向第2步矩阵的各行，同时计数零的个数。

1. 公式

   $$A:(0,0,7,1)$$
   解释

   检查第2步矩阵的A行。

   步骤依据

   直接从屏幕上显示的矩阵读取信息。

   视频直接表达
2. 公式

   $$\#\text{zeros in row A}=2$$
   解释

   A行包含两个零，因此主讲人表示暂不选择其中任一零。

   步骤依据

   统计该行中零元素的个数。

   视频直接表达
3. 公式

   $$B:(0,3,0,3)$$
   解释

   检查第2步矩阵的B行。

   步骤依据

   直接从显示的矩阵中读取。

   视频直接表达
4. 公式

   $$\#\text{zeros in row B}=2$$
   解释

   B 行也包含两个零。

   步骤依据

   统计该行中零元素的个数。

   视频直接表达
5. 公式

   $$C:(1,1,0,0)$$
   解释

   检查步骤2矩阵中的 C 行。

   步骤依据

   直接从显示的矩阵中读取。

   视频直接表达
6. 公式

   $$\#\text{zeros in row C}=2$$
   解释

   C 行也包含两个零。

   步骤依据

   统计该行中零元素的个数。

   视频直接表达
7. 公式

   $$D:(0,2,1,1)$$
   解释

   检查步骤2矩阵中的 D 行。

   步骤依据

   直接从显示的矩阵中读取。

   视频直接表达
8. 公式

   $$\#\text{zeros in row D}=1$$
   解释

   口述解释指出接下来检查最后一行；从视觉上看，显示的 D 行有一个零。

   步骤依据

   统计该行中零元素的个数。

   视频直接表达

前三行每行均包含两个零，因此说话人在本片段中暂缓从这些行中选择指派。

1. 声音
   观察依据

   讲解者逐行叙述选择零元并划去其他零元的过程。

2. 图示
   观察依据

   矩阵单元格上圆圈与叉号的视觉递进变化。

1. 公式

   $$$$
   解释

   在 D 行识别列 1 处的唯一零元，将其圈出，并划去列 1 中的其他零元（位于 A,1 和 B,1）。

   步骤依据

   D 行仅剩一个可用零元，因此必须指派 $D\to 1$。

   视频直接表达
2. 公式

   $$$$
   解释

   在 A 行识别列 2 处剩余的可用零元，并将其圈出。

   步骤依据

   A,1 处的零元已被划去，故 A 行唯一可选的是 A,2。

   视频直接表达
3. 公式

   $$$$
   解释

   在 B 行识别列 3 处的唯一零元，并将其圈出。

   步骤依据

   此前多次划去后，B 行仅剩一个零元。

   视频直接表达
4. 公式

   $$$$
   解释

   在 C 行识别列 4 处剩余的可用零元，将其圈出，并划去 C,3 处的零元。

   步骤依据

   列 3 已存在指派（$B\to 3$），因此 C 必须取列 4。

   视频直接表达

最优指派方案为：$A\to 2$，$B\to 3$，$C\to 4$，$D\to 1$。

1. 声音
   观察依据

   主讲人说：“总最小成本需要将所有这些加起来才能求得。因此，当我们把所有这些加起来时，得到总最优成本为38卢比。”

2. 图示
   观察依据

   表格列出了所选分配方案的原始成本：$A\to 2$为12，$B\to 3$为7，$C\to 4$为11，$D\to 1$为8。总和写作“总最优成本 = 38卢比”

1. 公式

   $$12 + 7 + 11 + 8$$
   解释

   将约简矩阵中确定的最优分配所对应的原始成本相加。

   步骤依据

   一个分配方案的总成本，等于各个人—岗位对的个体成本之和。

   视频直接表达
2. 公式

   $$38$$
   解释

   相加的结果是38。

   步骤依据

   算术运算。

   视频直接表达

给定指派问题的总最优成本为38卢比。

1. 图示
   观察依据

   给出一个$4\times 4$的成本矩阵，人员为A、B、C、D，工作为1、2、3、4。

2. 声音
   观察依据

   主讲人逐步演示该特定矩阵的行化简过程。

使用匈牙利法求解给定的$4\times 4$指派问题。

1. 费用矩阵：A行[10, 12, 19, 11]，B行[5, 10, 7, 8]，C行[12, 14, 13, 11]，D行[8, 12, 11, 9]

对费用矩阵进行行化简。

1. 公式

   $$Identify minimums: min(A)=10, min(B)=5, min(C)=11, min(D)=8$$
   解释

   找出每行中的最小数。

   步骤依据

   最小元素的定义。

   视频直接表达
2. 公式Subtract minimums from respective rows
   解释

   应用行化简规则，生成一个新的矩阵。

   步骤依据

   匈牙利法中的行化简步骤。

   视频直接表达

部分化简后的矩阵中，A行为[0, 2, 9, 1]，B行为[0, 5, 2, 3]，C行为[1, 3, 2, 0]，D行以[0, 4, …]开头。

目视核对新矩阵中手写数字与计算所得减法结果是否一致。

1. 图示
   观察依据

   完整的演算示例手写在纸上，从第1步矩阵变换到第2步矩阵。

2. 声音
   观察依据

   讲解者逐列说明各列的最小值及相应的减法运算。

给定行最简形矩阵[[0,2,9,1],[0,5,2,3],[1,3,2,0],[0,4,3,1]]，执行列约简。

1. 第1步矩阵：$A=(0,2,9,1)$，$B=(0,5,2,3)$，$C=(1,3,2,0)$，$D=(0,4,3,1)$。

2. 行标记为A、B、C、D，列标记为1、2、3、4。

通过从该列每个元素中减去该列的最小元素，得到第2步矩阵。

1. 公式

   $$\text{Column 1 minimum}=0$$
   解释

   第1列的最小元素是0，因此第1列保持不变。

   步骤依据

   列约简规则。

   视频直接表达
2. 公式

   $$\text{Column 2 minimum}=2$$
   解释

   第2列的最小元素是2。

   步骤依据

   列约简规则。

   视频直接表达
3. 公式

   $$(2,5,3,4)-(2,2,2,2)=(0,3,1,2)$$
   解释

   减去 2 列中每个元素的值2。

   步骤依据

   算术减法。

   视频直接表达
4. 公式

   $$\text{Column 3 minimum}=2$$
   解释

   第3列中的最小元素是2。

   步骤依据

   列约简规则。

   视频直接表达
5. 公式

   $$(9,2,2,3)-(2,2,2,2)=(7,0,0,1)$$
   解释

   减去 2 列中每个元素的值3。

   步骤依据

   算术减法。

   视频直接表达
6. 公式

   $$\text{Column 4 minimum}=0$$
   解释

   第4列中的最小元素是0，因此第4列保持不变。

   步骤依据

   列约简规则。

   视频直接表达
7. 公式

   $$\begin{bmatrix}0&0&7&1\\0&3&0&3\\1&1&0&0\\0&2&1&1\end{bmatrix}$$
   解释

   将变换后的各列组合成第2步矩阵。

   步骤依据

   合并按列得到的结果。

   视频直接表达

对应的式子为：[[0,0,7,1],[0,3,0,3],[1,1,0,0],[0,2,1,1]]

结果矩阵的每一列都至少包含一个零，这与列约简所声明的目标一致。

1. 声音
   观察依据

   说话人逐行检查，并对每行中零的个数作出说明。

2. 图示
   观察依据

   笔尖指向步骤2矩阵的A、B和C行。

列约简完成后，观察矩阵中每行包含多少个零，再进行指派。

1. 步骤2矩阵：$A=(0,0,7,1)$，$B=(0,3,0,3)$，$C=(1,1,0,0)$，$D=(0,2,1,1)$。

根据每行零的个数，判断是否存在可立即指派的行。

1. 公式

   $$\text{Row A has two zeros}$$
   解释

   A行是(0,0,7,1)，因此它在第1列和第2列含有零。

   步骤依据

   直接从矩阵中计数。

   视频直接表达
2. 公式

   $$\text{Do not select a zero in row A yet}$$
   解释

   由于存在两个零，说话者暂缓选择。

   步骤依据

   音频中已说明。

   视频直接表达
3. 公式

   $$\text{Row B has two zeros}$$
   解释

   B行是(0,3,0,3)，因此它在第1列和第3列含有零。

   步骤依据

   直接从矩阵中计数。

   视频直接表达
4. 公式

   $$\text{Row C has two zeros}$$
   解释

   C行是(1,1,0,0)，因此它在第3列和第4列含有零。

   步骤依据

   直接从矩阵中计数。

   视频直接表达
5. 公式

   $$\text{Move on to the last row}$$
   解释

   由于前三行每行都有两个零，说话者转而检查第 D 行。

   步骤依据

   音频中已说明。

   视频直接表达

A、B、C 三行每行均包含两个零，因此在本片段中未从这些行中选择任何指派。

该结论直接由屏幕上显示的2步矩阵得出。

1. 图示
   观察依据

   完整的问题设定与求解步骤已写在纸上。

2. 声音
   观察依据

   讲解者说明了解题步骤，并口述了最终的指派方案及对应的成本值。

1. 最终总最小成本的计算未在本片段内完成。

给定成本矩阵，为4个人（A、B、C、D）和4项工作（1、2、3、4）求最优指派方案及最小成本。

1. 成本矩阵：$A=[10, 12, 19, 11]$，$B=[5, 10, 7, 8]$，$C=[12, 14, 13, 11]$，$D=[8, 12, 11, 9]$。

2. 已给出经行约简与列约简后的约简矩阵。

确定最优的人—工作指派方案，并计算总最小成本。

1. 公式

   $$$$
   解释

   应用列约简逻辑：在约简矩阵中选取独立零元素。

   步骤依据

   匈牙利法要求找到 n 个独立零元素。

   视频直接表达
2. 公式

   $$$$
   解释

   所得指派方案为：A→工作2，B→工作3，C→工作4，D→工作1。

   步骤依据

   源自约简矩阵中被圆圈标记的零元素。

   依据视频推导
3. 公式

   $$$$
   解释

   查原成本矩阵中这些指派对应的成本：Cost(A,2)=12，Cost(B,3)=7，Cost(C,4)=11，Cost(D,1)=8。

   步骤依据

   总成本必须根据原始成本矩阵计算，而非约简后的矩阵。

   视频直接表达

最优指派：A分配工作2、B分配工作3、C分配工作4、D分配工作1。视频末尾的板书从原始费用相加，得到$12+7+11+8=38$卢比。

验证每个人员与每项工作均恰好被使用一次，且各项成本与原始矩阵一致。

1. 图示
   观察依据

   整段视频演示了一个特定的$4\times 4$指派问题的求解过程。

在给定如下成本矩阵的前提下，为4个人（A、B、C、D）分配4项工作（1、2、3、4），使得总成本最小： A：[10, 12, 19, 11] B：[5, 10, 7, 8] C：[12, 14, 13, 11] D：[8, 12, 11, 9]

1. 一个$4\times 4$的成本矩阵，表示每个人被分配到每个岗位所需的成本。

确定人员与岗位之间的最优指派方案，以及对应的总最小成本。

1. 公式

   $$Row Minima: A=10, B=5, C=11, D=8$$
   解释

   找出初始成本矩阵中每行的最小值。

   步骤依据

   行约减步骤的定义。

   依据视频推导
2. 公式Row Reduced Matrix: A: [0, 2, 9, 1] B: [0, 5, 2, 3] C: [1, 3, 2, 0] D: [0, 4, 3, 1]
   解释

   从该行每个元素中减去其所在行的最小值。

   步骤依据

   行约减公式的应用。

   视频直接表达
3. 公式

   $$Column Minima of Row Reduced Matrix: 1=0, 2=2, 3=2, 4=0$$
   解释

   找出行约减后矩阵中每列的最小值。

   步骤依据

   列约减步骤的定义。

   依据视频推导
4. 公式Column Reduced Matrix: A: [0, 0, 7, 1] B: [0, 3, 0, 3] C: [1, 1, 0, 0] D: [0, 2, 1, 1]
   解释

   从该列每个元素中减去其所在列的最小值。

   步骤依据

   列约减公式的应用。

   视频直接表达
5. 公式

   $$Optimal Assignments: A->2, B->3, C->4, D->1$$
   解释

   从列约减后的矩阵中选取零元素，使得每行每列恰好选一个。视频中演示：圈出 A2，划去 A 行和 2 列中的其余零；圈出 B3，划去其余零；圈出 C4；圈出 D1。

   步骤依据

   从约减后的矩阵中求得最优指派的方法。

   视频直接表达
6. 公式

   $$Total Cost = 12 + 7 + 11 + 8 = 38$$
   解释

   将所选指派在原始成本矩阵中对应的成本相加（$A\to 2$ 的成本为 12，$B\to 3$ 的成本为 7，$C\to 4$ 的成本为 11，$D\to 1$ 的成本为 8）。

   步骤依据

   最终目标函数值的计算。

   视频直接表达

最优指派方案为：人员 A 指派至工作2，人员 B 指派至工作3，人员 C 指派至工作4，人员 D 指派至工作1。总最优成本为 Rs 38。

所选原始成本之和（$12+7+11+8$）正确等于所陈述的总最优成本38。

1. 图示
   观察依据

   一只手在原矩阵下方绘制一个新的$4\times 4$方格，并逐行填入计算所得的数值。

1. 原始成本矩阵

2. 新的空白网格

3. 笔

4. 计算得出的数字

1. 新网格被绘制出来

2. 数字按从左上到右下的顺序依次填入网格

1. 原始成本矩阵保持不变，位于顶部

该视觉过程演示了行简化步骤的实际应用，展示了如何基于原始数据构建新矩阵。

1. 图示
   观察依据

   镜头展示一张手写解题纸：顶部为原始的$4\times 4$表格，随后是“1步：行约减”，再下面是“2步：列约减”。

1. 原始的$4\times 4$成本表

2. 标题：“解：这是一个平衡的指派问题”

3. 1步矩阵

4. 2步矩阵

5. 笔与手

1. 视角向下移动，主讲人写下步骤2矩阵。

2. 步骤2矩阵按列依次填入。

3. 随后，笔尖横向指向已完成的步骤2矩阵的各行。

1. 行标签保持为 A、B、C、D。

2. 列标签保持为1、2、3、4。

3. 步骤1矩阵始终显示在步骤2矩阵上方。

视觉结构展示了匈牙利法的顺序工作流程：从原始问题出发，依次进行行约减、列约减、零元素检验。

1. 动画
   观察依据

   手写将步骤2矩阵的元素逐列填入。

1. 空白的步骤2网格

2. 步骤1矩阵

3. 笔

1. 第1列被复制为0、0、1、0。

2. 第2列被写作0、3、1、2。

3. 第3列被写作7、0、0、1。

4. 第4列被写作1、3、0、1。

1. 矩阵尺寸保持为$4\times 4$。

2. 行标签与列标签均不发生变化。

动画明确展示了：对第1步矩阵的每一列，独立执行列约简操作。

1. 动画
   观察依据

   笔尖依次指向已完成的第2步矩阵的各行，同时讲解者逐个计数零元素。

1. 已完成的第2步矩阵

2. 笔尖

1. 注意力从第A行移至第B行，再移至第C行，最后移向最后一行。

1. 矩阵中的元素本身在本次检查过程中不会发生变化。

这一可视化序列对应下一个算法步骤：检查每行在分配选择前出现多少个零。

1. 动画
   观察依据

   手用笔在下方矩阵中对特定零元素画圆圈，并对其他零元素画叉。

1. 约简矩阵

2. 笔

3. 圆圈

4. 叉

1. 零元素按顺序被画上圆圈，以表示被选中。

2. 同一列中的其他零被划掉，表示排除。

1. 矩阵中的数值保持不变。

2. 网格结构保持恒定。

视觉标记展示了算法步骤：为每一行和每一列分别确定唯一的指派。

1. 动画
   观察依据

   摄像机或纸张向上移动，显露出页面的顶部区域。

1. 纸张

2. 原始成本矩阵

1. 视图从解题区域切换至问题陈述区域。

1. 纸张上的内容静止不动。

此操作是必要的，以便在最终计算步骤中参考原始成本。

1. 动画
   观察依据

   一只手执笔，在上方成本矩阵的每一行中指向并下划线标出最小值。

1. 上方成本矩阵

2. 笔

3. 手

1. 笔逐行移动，依次指向每行中的最小数字，并将其下划线标出。

1. 矩阵中的数字在此过程中保持不变。

这一可视化操作演示了在每一行中寻找最小元素的过程，即行约简步骤的第一部分。

1. 动画
   观察依据

   视频展示了已预先写好的矩阵，分别标注为“步骤1：行约简”和“步骤2：列约简”。

1. 实际的减法运算过程未予展示；结果已直接写出。

1. 行约简矩阵

2. 列约简矩阵

1. 视图沿页面向下移动，以显示求解过程中后续出现的各矩阵。

1. 维持$4\times 4$网格的结构。

这些图示呈现了匈牙利法中应用行约简与列约简规则后，成本矩阵所处的各个中间状态。

1. 动画
   观察依据

   在‘列约简矩阵’中，对某些特定的零元素画上圆圈，并将同一行或同一列中的其余零元素划掉。

1. 列约简矩阵

2. 圆圈

3. 叉号

1. 特定的零元素用圆圈标记以表示被选中，而冲突的零则用叉号标记。

1. 矩阵中的数值保持不变。

这一可视化过程展示了如何从约简后的矩阵中选出一组线性无关的零元素，这些零元素对应人员与工作的最优指派。

1. 声音
   观察依据

   ‘那么，如果我们在这一行中看到有两个零，我们就不要选择其中任何一个零。’

人们可能认为，约简后的矩阵中任意一个零都可以立即被选为分配对象。

讲话者明确推迟了当某行含有两个零时的选择操作，这表明应等待零的分布模式变得更加受限后再进行分配。

1. 声音
   观察依据

   说话人明确指出：“我们必须从原始给定的矩阵中查看成本值。”

学生可能错误地将约简矩阵中的数值（其中大部分为零）相加，以求得总成本。

总最小成本必须始终通过对原始成本矩阵中对应位置的元素求和来计算。

1. 声音
   观察依据

   说话者表示，在确认这是一个平衡问题后，将采用匈牙利法。

确认问题是否平衡，是应用标准匈牙利法之前必不可少的预备步骤。

1. 声音
   观察依据

   说话者介绍行简化是采用匈牙利法时首先要进行的操作。

行约简是匈牙利法这一更广泛求解流程中所包含的一个具体步骤。

1. 图示
   观察依据

   该页将问题标记为平衡型，然后依次执行步骤1和步骤2。

2. 声音
   观察依据

   讲话者从平衡型问题的设定转入列约简。

之所以采用列约简法，是因为该问题已被识别为平衡型指派问题，且已完成行约简。

1. 声音
   观察依据

   ‘现在我们必须转到step three’，这句话紧接在完成步骤2的矩阵之后。

2. 图示
   观察依据

   零检查是在步骤2的矩阵上进行的。

统计零个数的步骤以列约简所得矩阵作为输入。

1. 声音
   观察依据

   主讲人将零检验与以下要求联系起来：每项工作必须分配给一个人，且每行和每列都恰好有一个零。

行列零检验被呈现为一种强制实现一一对应分配要求的方法。

1. 图示
   观察依据

   整个片段展示了该方法中典型的标有“步骤1”和“步骤2”的步骤。

列约简及找出独立零元，是提取最优指派前的必要步骤。

1. 图示
   观察依据

   解法按顺序呈现为“步骤1：行约简”，随后是“步骤2：列约简”。

列约简步骤应用于已完成行约简的矩阵。

1. 图示
   观察依据

   最优指派从‘列约简’矩阵中存在的零元素中选出。

最优指派的选择依据是前述约简步骤所生成的零元素分布模式。

1. 声音
   观察依据

   主讲人定义了平衡问题与非平衡问题。

1. 平衡型 vs 非平衡型指派问题

1. 声音
   观察依据

   主讲人讲解并演示了行约简。

1. 匈牙利法
2. 行约减步骤

1. 声音
   观察依据

   主讲人定义并演示了列约减。

2. 图示
   观察依据

   第2步矩阵由第1步矩阵构造而成。

1. 匈牙利法中的列约减步骤
2. 对所展示的$4\times 4$矩阵实施了列约减。
3. 对屏幕上显示的$4\times 4$矩阵执行列约简运算。

1. 图示
   观察依据

   页面上显示“第1步：行约减”，后接“第2步：列约减”。

2. 声音
   观察依据

   我们需要考虑在 step one 中所得到的矩阵

1. 匈牙利法中的列约减步骤
2. 对所展示的$4\times 4$矩阵实施了列约减。

1. 声音
   观察依据

   ‘这里有两处零，因此我们暂不选择其中任意一个零。’

1. 分配选择前的零计数步骤
2. 不得立即从含多个零的行中进行分配。
3. 逐行检查简化后矩阵中的零元素。

1. 图示
   观察依据

   标题：‘这是一个平衡的指派问题。’

2. 声音
   观察依据

   ‘每项工作都必须分配给一个人。’

1. 平衡的指派问题
2. 一一对应分配要求

1. 声音
   观察依据

   现在我们要进入step three……检查它有多少个零。

1. 分配选择前的零计数步骤
2. 逐行检查第2步矩阵中的零元素。
3. 逐行检查简化后矩阵中的零元素。

1. 声音
   观察依据

   讲解者说明如何逐行选择零元。

1. 匈牙利法中的列约简步骤

1. 声音
   观察依据

   讲解者提到需查看原始矩阵中的成本值。

1. 最优指派的提取

1. 图示
   观察依据

   该视频展示了求解指派问题的完整流程。

1. 平衡的指派问题
2. 行约简步骤
3. 列约简步骤
4. 最优指派选取

1. 图示
   观察依据

   标有‘步骤1：行约简’的部分解释了这一概念。

1. 行约简步骤

1. 声音
   观察依据

   讲解者通过将所选指派对应的原始成本相加，来说明如何计算总最小成本。

1. 总最优成本的计算