指派问题——匈牙利法

1、指派问题匈牙利法 指派问题的求解方法指派问题的求解方法 匈牙利法匈牙利法 指派问题的求解方法指派问题的求解方法 指派问题匈牙利法2 指派问题及求解方法指派问题及求解方法 1 、指派问题的提出、指派问题的提出 有有 n 项不同的任务，恰好分派给项不同的任务，恰好分派给n 个人分别承担，个人分别承担， 由于每人完成各项任务的效率情况不同。现假设必由于每人完成各项任务的效率情况不同。现假设必 须指派每个人去完成一项任务，需考虑怎样把须指派每个人去完成一项任务，需考虑怎样把 n 项项 任务指派给任务指派给 n 个人，使得完成个人，使得完成 n 项任务的总的效率项任务的总的效率 最高，这就是指派问题。最

2、高，这就是指派问题。 例有例有4个工人，要分别指派他们完成个工人，要分别指派他们完成4项不同的工作，项不同的工作， 每人做各项工作所消耗的时间如下表所示，问应如每人做各项工作所消耗的时间如下表所示，问应如 何指派工作，才能使总的消耗时间为最少。何指派工作，才能使总的消耗时间为最少。 指派问题匈牙利法3 解：解：令令 xij = 1(第第 i人完成第人完成第j项工作项工作)或或0（第（第 i人不进行人不进行 第第j项工作项工作)于是得到一个于是得到一个0-1整数规划问题：整数规划问题： Min z=15x11+18x12+21x13+24x14+19x21+23x22 +22x23+18x24+

3、26x31+17x32+16x33+19x34 +19x41 +21x42+23x43+17x44 s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作乙只能干一项工作) x31+ x32+ x33+ x34= 1 (丙只能干一项工作丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作丁只能干一项工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干工作只能一人干)

4、 x13+ x23+ x33+ x43= 1 ( C工作只能一人干工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干工作只能一人干) xij 为为0-1变量变量，i,j = 1,2,3,4 指派问题匈牙利法 2、指派问题的一般形式指派问题的一般形式 设有设有 n 个资源（人或机器等）个资源（人或机器等）A1, A2, , An，分配做，分配做 n 件事件事B1, B2, Bn， 要求每件事必须使用要求每件事必须使用1个资源，且不同个资源，且不同 事件由不同资源完成。已知事件由不同资源完成。已知 Ai 做做 Bj的效的效 率（如劳动工时、成本、创造价值等）率（如劳

5、动工时、成本、创造价值等） 为为cij 。问如何进行指派可使总工作效率。问如何进行指派可使总工作效率 最佳？最佳？ 指派问题匈牙利法 指派问题的一般形式指派问题的一般形式 定义变量：设指派问题变量为定义变量：设指派问题变量为 xij, ，则共有，则共有n2 个变量，且变量取值为：个变量，且变量取值为： xij=1或或0 ( xij =1 表示表示 Ai 做做 Bj，否则取值为，否则取值为 0 ) 由由cij ( 0)组成的方阵组成的方阵 称为效率矩阵，模型为：称为效率矩阵，模型为： 10 ),2,1(1 ),2,1(1. 1 1 11 orx njx nixts xczMin ij n i i

6、j n j ij n i n j ijij 指派问题匈牙利法 3、指派指派问题的匈牙利解法问题的匈牙利解法 1955年，库恩（年，库恩（W.W.Kuhn）利用匈牙利数学）利用匈牙利数学 家康尼格（家康尼格（D.Knig）关于矩阵中独立零元素）关于矩阵中独立零元素 定理，提出了一种指派问题算法，被称为匈定理，提出了一种指派问题算法，被称为匈 牙利解法。牙利解法。 指派问题的任何可行解由指派问题的任何可行解由 n2个满足约束条件个满足约束条件 的数的数 xij 组成组成。这些这些 xij中，有中，有 n个为个为1，其余，其余 均为均为0，且此，且此 n个个1必位于损益表中不同行不必位于损益表中不同

7、行不 同列中，由此同列中，由此 n个个xij=1 确定了确定了n 个相应的个相应的cij 也位于效率矩阵中的不同行不同列上，相应也位于效率矩阵中的不同行不同列上，相应 的可行解的可行解 的目标函数值由此的目标函数值由此 n个个cij 之和确定。之和确定。 指派问题匈牙利法 指派问题的匈牙利解法指派问题的匈牙利解法 定理定理6.1：设：设 C=(cij)是一个效率矩阵，若可行是一个效率矩阵，若可行 解解x*=(xij)的的 n个个1所对应的所对应的 n个个 C=(cij)均为均为0， 则则x* 是最优解。是最优解。 定理定理6.2：设给定了以：设给定了以 C=(cij)为效率矩阵的指为效率矩阵的

8、指 派问题派问题 G，现将，现将 C的元素的元素cij 改变为：改变为： cij=cij- i- j，其中：其中： i, j 为常数。为常数。 则以则以C=(cij) 为效率矩阵的指派问题为效率矩阵的指派问题G 与与 G有相同的最优解。有相同的最优解。 约化矩阵约化矩阵：效率矩阵通过行或列同时加上：效率矩阵通过行或列同时加上 （减去）一个常数得到的矩阵。（减去）一个常数得到的矩阵。 指派问题匈牙利法 指派问题的性质定理的证明指派问题的性质定理的证明 定理定理6.2：对于指派问题，效率矩阵的任一行：对于指派问题，效率矩阵的任一行 (或列或列)减去减去(或加上或加上)一个相同的数得到的新指一个相同

9、的数得到的新指 派问题与原问题同解。派问题与原问题同解。 s)( s)(xcxc xs)(xcxc s)x(cxc=z n 1j kjkj n ki 1i n 1j ijij n 1j kj n 1j kjkj n ki 1i n 1j ijij n 1j kjkj n ki 1i n 1j ijij z 指派问题匈牙利法 指派问题的匈牙利解法指派问题的匈牙利解法 根据此定理，可以对根据此定理，可以对 做如下改变，目的是做如下改变，目的是 找出找出C 中的中的 n个不同行不同列的个不同行不同列的0元素元素： 将将 C的每一行减去该行中的最小元素，得的每一行减去该行中的最小元素，得 到到C矩阵矩

10、阵 ，则，则C 的每行中均至少出现一个的每行中均至少出现一个 0元素，且所有元素，且所有cij 0 。同样，对。同样，对C 的列亦进的列亦进 行如此计算，由此，我们完全可以从原效行如此计算，由此，我们完全可以从原效 率矩阵率矩阵 出发，得到一个新的效率矩阵出发，得到一个新的效率矩阵 ，使，使 C的每行每列中均至少存在一个的每行每列中均至少存在一个0元素，而元素，而 不改变问题的最优解。不改变问题的最优解。 指派问题匈牙利法 指派问题的匈牙利解法指派问题的匈牙利解法 约化矩阵性质应用约化矩阵性质应用 34 7100 3204 6031 5310 ),2(),5(),2(),2(4321 9322

11、 8759 8253 7532 列减列减，再对第，再对第得到得到 行分别加行分别加，第第 例：例： C 指派问题匈牙利法 约化矩阵性质应用（续）约化矩阵性质应用（续） 注：不同行不同列的注：不同行不同列的0 0元素，称为独立元素，称为独立0 0元素元素, , 当矩阵中含有当矩阵中含有n个独立个独立0 0元素时即得解。元素时即得解。 142822 1 41)0(0 )0(204 3)0(31 231)0( 52342311 f xxxx 相应最小费用相应最小费用 是一组最优解，是一组最优解，显然，显然， 得到得到 指派问题匈牙利法 6072 3950 0602 4310 指派问题的匈牙利解法指派

12、问题的匈牙利解法 定理定理6.3 6.3 设矩阵设矩阵C C中含有中含有0 0元素，那么划去元素，那么划去C C中中 所有所有0 0元素所需的最少直线数等于元素所需的最少直线数等于C C中独立中独立0 0 元素的个数。元素的个数。 例例 下列矩阵中，最少下列矩阵中，最少3 3条直线覆盖了所有条直线覆盖了所有0 0元元 素，因此可判定矩阵有素，因此可判定矩阵有3 3个独立个独立0 0元素。元素。 指派问题匈牙利法13 指派问题的匈牙利解法指派问题的匈牙利解法步骤步骤 Step 1. 每行减去该行的最小数每行减去该行的最小数, 每列减去该每列减去该 列的最小数，使矩阵每行每列均有列的最小数，使矩阵

13、每行每列均有0元素；元素； Step 2. 寻找独立寻找独立0元素元素 从从单单个个0元素的行元素的行(列列)开始，给开始，给0加圈，记作加圈，记作， 然后划去所在列然后划去所在列(行行)的其它的其它0元素，记为元素，记为；重复；重复 进行，直到处理完所有列进行，直到处理完所有列(行行)的的单个单个0元素；元素； 若若还还存在没有画圈的存在没有画圈的0元素元素(同行或同列中的同行或同列中的0元素元素 多于多于1个个)，则从剩余的，则从剩余的0元素最少的行元素最少的行(列列)开始，开始， 选选0元素画圈，然后划掉同行同列的其它元素画圈，然后划掉同行同列的其它0元素，元素， 反复进行，直到所有反复

14、进行，直到所有0元素均被圈出或划掉为止；元素均被圈出或划掉为止； 若若元素的数目元素的数目m=n，则该指派问题的最优，则该指派问题的最优 解已经得到，否则转入解已经得到，否则转入Step 3； 指派问题匈牙利法14 指派问题的匈牙利解法指派问题的匈牙利解法步骤（续）步骤（续） Step 3. 设有设有 mn 个个, 找最少覆盖所有找最少覆盖所有0的直线的直线 1) 对没有的行打对没有的行打 2) 对已打对已打行中含行中含所在列打所在列打 3) 对已打对已打列中含所在行打列中含所在行打 4) 重复重复2)3), 直至没有要打直至没有要打的行和列为止的行和列为止 5) 对没有打对没有打的行划横线的

15、行划横线, 对打对打的列划竖线的列划竖线 得到最少覆盖所有得到最少覆盖所有0的直线数的直线数l。 若若l0充分大充分大) 指派问题匈牙利法 非标准形式的指派问题非标准形式的指派问题例例 任务与人员数不等的情况任务与人员数不等的情况 分配甲、乙、丙、丁分配甲、乙、丙、丁 4 人去完成人去完成 5 项任务，每人完成各项任务的时间项任务，每人完成各项任务的时间 如下表。由于任务多，规定其中有如下表。由于任务多，规定其中有 一人可兼完成两项任务，试确定总一人可兼完成两项任务，试确定总 花费时间最少的分派方案。花费时间最少的分派方案。 指派问题匈牙利法 非标准形式的指派问题非标准形式的指派问题例例 各人

16、完成不同任务的效率情况各人完成不同任务的效率情况 任务任务 人人 A B C D E 甲甲59112217 乙乙242311518 丙丙14782012 丁丁42216325 指派问题匈牙利法 非标准形式的指派问题非标准形式的指派问题例例 解：增加一人，其完成各项任务时间为该任解：增加一人，其完成各项任务时间为该任 务完成的最少时间：务完成的最少时间： 任务任务 人人 A B C D E 甲甲59112217 乙乙242311518 丙丙14782012 丁丁42216325 戊戊4丁 丁 7丙 丙 8丙 丙 3丁 丁 12丙 丙 指派问题匈牙利法 非标准形式的指派问题非标准形式的指派问题例例 人多任务少，允许某人空闲人多任务少，允许某人空闲 从甲、乙、丙、丁、戊从甲、乙、丙、丁、戊5人中选人中选 4 人去完成人去完成 4 项任务，每人完成各项任务，每人完成各 项任