本节概要
所谓指派问题是指这样一类问题：有 n 项任务，恰好有 n 个人可以分别去完成其中任何一项，由于任务的性质和每个人的技术专长各不相同，因此，各人去完成不同任务的效率也不一样。于是提出如下问题：应当指派哪个人去完成哪项任务，才能使总的效率最高?类似的指派问题还有：n 台机床加工 n 项任务；n 条航线安排 n 艘船或 n 架客机去航行等。
例子
某公司有 B1，B2，B3，B4 四项不同的任务，恰有 A1，A2，A3，A4 四个人去完成各项不同的任务。由于任务性质及每个人的技术水平不同，他们完成各项任务所需的时间如表所示。
工作时间表
问题
怎样指派任务才能使这项工程花费的总时数最少?
解
第一步
从效益矩阵的每行减去各行中的最小元素，再从每列中减去各列的最小元素，得
效益矩阵
这里值称为初始缩减矩阵。各行各列所减去的数之总和称为缩减量。本题的缩减量为
S=2+4 ＋ 9 ＋ 7 ＋ 4 ＋ 2=28。
注意：如果某行（或列）有 0 元素，就不必再减。
第二步
找出一个指派方案，以寻求最优解。
经过第一步变换后，初始缩减矩阵中每行每列都已有了 0 元素，还需要找出 n 个独立的 0 元素，即找出 n 个位于不同行不同列的 0 元素来。若能找出，则以这些 0 元素对应的元素位置为 1，其余为 0，便得到一个解矩阵，从而得到最优解。
寻找 n 个独立 0 元素的方法如下。
- 从第 1 行开始检查。若某一行只有一个 0 元素，就对这个 0 元素打上 △ 号，然后划去 △ 所在列的其他 0 元素，记作 γ。
- 从第 1 列开始检查，若某列只有 1 个 0 元素，就对这个 0 元素打上 △ 号，(不考虑已划去的 0 元素)。然后再划去 △ 所在行的其他 0 元素，记作 γ。
- 重复(1)(2)两步，直到所有 0 元素打上 △ 号或被划去。
最优解
这表示 A，去完成任务 B4，A2 去完成任务 B2，A3 去完成任务 B1，A4 去完成任务 B3 所需总时间最少，这时：
注意：
- 如果在矩阵中能得到位于不同行不同列的 n(n=4)个 △，那么就完成了求最优解的过程；
- 如果矩阵中的所有 0 元素打上 △ 号，或被划去 γ，而不是每一行都有打 △ 号的 0 元素，那么解题过程还没有完成。
第三步
求最优解
- 对没有 △ 的行打 √ 号；
- 在已打 √ 号的行上，对有 0 元素的列打 √ 号；
- 再对打 √ 号的列上有 △ 的行打 √ 号；
- 重复步骤（2）(3）直到得不出新的打 √ 的行、列为止。
- 对没有打 √ 的行画横线，对所有打 √ 的列画纵线，这就得到覆盖所有 0 元素的最少直线数。
第三步
第四步
修改缩减矩阵，使每行每列都至少有 1 个 △ 元素，具体方法如下。
- 在第三步得到的矩阵中，对没有被直线覆盖的部分找出最小元素；
- 在打 √ 号行的各元素中都减去这个最小元素；
- 在打 √ 号列的各元素中都加上这个最小元素。
从而得到一个新的缩减矩阵。如果它已有 n 个不同行不同列的 0 元素，则求解过程已完成，如果还没有得到 n 个 0 元素，则返回第三步重新进行。
第四步
最优解
网友评论