4.5 车辆调度中的匈牙利方法• 在物流活动中，经常会遇到这样的问题，有 n项运输任务，恰好有n辆车可承担这些运输 任务，由于车型、载重以及司机对道路熟悉 程度等方面的不同，效率也不一样，于是产 生了应指派哪辆车去完成哪项运输任务，使 总效率最高（或总费用最小，或时间最短） 的问题，这类问题称为指派问题类似的问 题有，n项配送任务，怎样指派到n个超市上 分别完成的问题；n条航线，怎样指定n艘船 去航行的问题等• 1、事件数与人数（车数）相等时指派问题的标准形式可以表述为：有n辆汽车和 n人，已知第 i个人做第 j项任务的费用为，，如何确定任务和人的一一对应的指派方案，使得完成n件事情的总费用最少？ 补充• 0-1规划注：如问题是求最大值的话，则需要将目标函数转换成求最 小值，再用匈牙利方法求解系数（效率）矩阵• 指派问题的最优解有这样性质，对任意 一个求最小值的效率矩阵（cij） ，若从 系数矩阵（cij）的一行（列）各元素中 分别减去或加上同一个常数k，得到新的 矩阵（bij），那么以（bij）为系数矩阵 求得的最优解和用原系数矩阵求得的最 优解相同而他们的目标函数仅相差一 个常数k.匈牙利方法的基本原理：• 利用这一性质，可使原系数矩阵变换为含 有很多0元素的新系数矩阵，而最优解保持 不变，在系数矩阵（bij）中，我们关心位 于不同行不同列的0元素，以下简称独立0 元素。
若能在系数矩阵（bij）中找到n个独 立的0元素，则令解矩阵（xij）中对应这个 n个独立的0元素取值为1，其他元素取值 为0这就是以（bij）为系数矩阵的指派问 题的最优解，也就得到了原问题的最优解 4.3.1指派问题的解法———匈牙利解法• 这种方法是匈牙利数学家考尼格(Konig) 提出的，因此得名匈牙利解法 • 匈牙利法是针对指派问题的标准型进行 求解匈牙利法的计算步骤如下：step1 按照一定的方法不断变化效率矩阵，设 法在原有效率矩阵基础上经变换，使新矩阵 的每行每列至少有一个零元素 (1)行变换：找出每行最小元素，再从该行各 元素中减去这个最小元素； (2)列变换：找出每列最小元素，再从该列各 元素中减去这个最小的元素； 经变换后的效率矩阵中，其每行、每列至少 有一个零元素• Step2 进行试指派，以寻求最优解 • (1)从只有一个0元素的行(列)开始，给这个0元素加圈 ，记作◎，然后划去所在列(行)的其他0元素，记作φ ； • (2)给只有一个0元素的列(行)的0元素加圈，记作◎ ， 然后划去所在行(列)的其他0元素，记作φ ； • (3)反复进行(1)、(2)两步，直到所有的0元素都被圈出 和划掉为止； • (4)若仍没有画圈的0元素，且同行(列)的0元素至少有 两个．则从剩下0元素最少的行(列)开始，比较这行各 0元素所在列的0元素的数目，选择0元素少的那列(行) 的这个0元素加圈，然后划掉同行同列的其他0元素； 可反复进行，直到所有0元素都已圈出和划掉为止； • (5)若元素◎的数目m等于矩阵的阶数n，那么这指派 问题的最优解已得到；若m＜n，则转入step3；• step3 作最少的直线覆盖所有0元素，以确定该系 数矩阵中能找到最多的独立0元素数；• (1)对没有◎的行打√号； • (2)对已打√号的行中，所有含φ元素的列打√号 • (3)再对打有√号的列中含0元素的行打√号 • (4)重复(2)、(3)直到得不出新的打√号的行、列为 止； • (5)对没有打√号的行画一横线，有√号的列画一纵 线，这就得到覆盖所有0元素的最少直线数．令这 直线数为m，若m＜n，说明必须再变换当前的系 数矩阵，才能找到n个独立的0元素，为此转step4 ； • step4 在没有被直线覆盖的部分中找出最 小元素，然后在打√号的行各元素中都减 去这最小元素，而在打√号的列的各元素 都加上这是小元素，以保证原来的0元素 不变．这样得到新的系数矩阵，若得到n 个独立的0元素，则已得到最优解，否则 回到step3重复进行。
例5• 某物流公司现有4项运输任务A、B、C、D， 现有甲、乙、丙、丁4辆车，他们完成任务所 需时间如表4-12所示问应指派何人去完成 何任务，使所需总时间最少？解： step1 对原有效率矩阵进行行变换和列变换，即找出每行最小元素，再从该行各元素中减去这个最小元素；找出每列最小元素，再从该列各元素中减去这个最小的元素，则有： 经变换后的效率矩阵 B 中，其每行、每列至少有一个零元素对矩阵 B 零元素按 step2进行得： 对新矩阵进行试分配，得到独立0 元素个数为m＝4，等于其阶数n＝4，从而得到了最优解矩阵，如下所示 由解矩阵得最优指派方案为甲—D，乙—B，丙—A，丁—C 总的消耗时间为min z＝C31+c22+c43+c14=28(小时) • 实例（m
对矩阵 B 零元素按 step2进行得： 显然矩阵B独立0元素个数为m＝3，小于 矩阵B的阶数4所以按step3对矩阵B作 能覆盖所有0元素的最少直线数，如下所 示√√√需要变换系数矩阵 B，即在矩阵B 中，从没有被直线覆盖的元素中找出最小元素 1，第二行、第四行的都减 1，第四列的元素加 1，得到新的矩阵 新矩阵独立0 元素个数为m＝ 3，小于其阶数4，所以按step3继续对新矩阵作能覆盖所有 0 元素的最小直线数， 如下所示√√√√√． 从没有被直线覆盖的元素中找出最小元素2，第一行、第二行、第四行的元素减去 2 ，第一列、第四列的元素加上2 ，得到新的矩阵• 或者对新矩阵(6)进行试分配，得到独立0 元素个数为m＝4，等于其阶数n＝4，从而得到了最优解矩阵，如下所示 由解矩阵得最优指派方案为甲—A，乙—D，丙—C，丁—B 另外，还可以得到另一个最优指派方案为：甲—B，乙—A，丙—C，丁—D 总的消耗时间为min z＝70 小时 想一想1、怎样求解目标函数最大值的分配方案呢 ？ 2、若人数大于事件数呢？反之呢？实例1• 例如：甲、乙、丙3人做四项工作，系 数矩阵可调整为人数小于事件数实例2• 例如：甲、乙、丙3人做四项工作，系 数矩阵为人数小于事件数• 如：甲、乙、丙3人做四项工作，要求甲做两 项，系数矩阵可调整为若甲、乙、丙、都最多可作2项工作• 系数矩阵可调整为练一练• 某物流公司安排甲、 乙、丙、丁四个人去 完成四项任务，每人 完成各项任务的时间 如表4-16所示。
• 请根据已知条件求解 一个总花费时间最少 的指派方案ABCD甲25293142乙39382620丙34272840丁24423623。