第五讲分配问题指派问题与匈牙利法

1、1第第5 5讲讲 分配问题（指派问题）与匈牙利法分配问题（指派问题）与匈牙利法2分配问题的提出3分配问题的提出分配问题的提出若干项若干项工作或任务工作或任务需要若需要若干个人干个人去完成。由于每人的知识、去完成。由于每人的知识、能力、经验的不同，故各人完成不同任务所需要的时间不同能力、经验的不同，故各人完成不同任务所需要的时间不同（或其他资源）。（或其他资源）。问：问： 应指派哪个人完成何项工作，可使完成所有工作所应指派哪个人完成何项工作，可使完成所有工作所消消耗的总资源最少耗的总资源最少？4分配问题的提出分配问题的提出设某公司准备派设某公司准备派 n n 个工人个工人x x1 1，x x2

2、2，x xn n ，去作去作 n n 件工作件工作 y y1 1，y y2 2，y yn n。已知工人已知工人x xi i完成工作完成工作 y yj j 所需所需时间为时间为c cij ij ( (i i, ,j j=1,2,=1,2,n n) )。现问：如何确定一个分派工人去工作的方案，使现问：如何确定一个分派工人去工作的方案，使得工人们完成工作的得工人们完成工作的总时间为最少。总时间为最少。台台机机床床加加工工项项任任务务；条条航航线线有有艘艘船船去去航航行行等等。n n n n 还比如：还比如：5整体解题思路总结整体解题思路总结例题：例题：工作者工作者1工作者工作者2工作者工作者3工作者

3、工作者4工作者工作者5工作工作14871512工作工作279171410工作工作3691287工作工作46714610工作工作56912106单位：小时单位：小时6标准形式的分配问题7标准形式的分配问题标准形式的分配问题分派方案满足下述两个条件：分派方案满足下述两个条件： 任一个工人都不能去做两件或两件以上的工作任一个工人都不能去做两件或两件以上的工作1.1.任一件工作都不能同时接受两个及以上的工人去做任一件工作都不能同时接受两个及以上的工人去做设某公司准备派设某公司准备派 n n 个工人个工人x x1 1，x x2 2，x xn n ，去作去作 n n 件工作件工作 y y1 1，y y2

4、2，y yn n。已知工人已知工人x xi i完成工作完成工作 y yj j 所需时间为所需时间为c cij ij ( (i i, ,j j=1,2,=1,2,n n) )。现问：如何确定一个分派工人去工作的方案，使得工人们现问：如何确定一个分派工人去工作的方案，使得工人们完成工作的完成工作的总时间为最少。总时间为最少。8标准形式的分配问题标准形式的分配问题nn事事人人9数学模型数学模型nncij：第第i人做第人做第j事的费用事的费用xij1 若指派第若指派第i人做第人做第j事事0 若指派第若指派第i人不做第人不做第j事事总费用总费用：11nnijijijc xi，j1, ., nj1,.,n

5、i1,.,nniijx11njijx11事事人人时间、原料、时间、原料、金钱等资源金钱等资源10数学模型数学模型ninjijijxcz11minniijx11njijx11j1,.,ni1,.,n,.,n,i,jxij21 10 或s.t.线性规划问题线性规划问题运输问题运输问题0-1型整数规划问题型整数规划问题11匈牙利匈牙利法法 1955 1955年由美国数学家年由美国数学家W.W.kuhn(W.W.kuhn(库恩库恩) )提出，利用了提出，利用了匈牙利数学家匈牙利数学家D.Konig(D.Konig(康尼格康尼格) )证明的证明的2 2个定理。个定理。nnnnnncccccccccC.1

6、12222111211nnnnnnxxxxxxxxxX.112222111211系数矩阵系数矩阵(效率矩阵效率矩阵)解矩阵解矩阵(决策变量矩决策变量矩阵阵)nn12定义定义：在系数矩阵在系数矩阵C中，中，处在不同行不同列处在不同行不同列的一的一组零元素，称为组零元素，称为独立零元素组独立零元素组，其中每个元素，其中每个元素称为称为独立零元素独立零元素。0084765000320205C4431321243312412,cccccccc44313241,cccc0100000110000010Xninjijijxcz11min最优解最优解13014丙丙085乙乙210甲甲CBA时时 工作工作 间

7、间 人员人员004丙丙075乙乙200甲甲CBA时时 工作工作 间间 人员人员458丙丙4129乙乙987甲甲CBA时时 工作工作 间间 人员人员定理：定理：若若将分配问题系数矩阵的将分配问题系数矩阵的每一行每一行及及每一列每一列分别分别减去减去各行及各列的各行及各列的最小元素最小元素，则则新分配问题与原分配新分配问题与原分配问题有问题有相同的最优解相同的最优解，只有最优值差一常数。，只有最优值差一常数。相关定理相关定理使每行每列使每行每列都出现零元素都出现零元素步骤步骤1：变换系数矩阵，使其每行每列都出现变换系数矩阵，使其每行每列都出现0元素元素 把各把各行行元素分别减去本行元素的最小值，然

8、后元素分别减去本行元素的最小值，然后在此基础上在此基础上再把每再把每列列元素减去本列中的最小值。元素减去本列中的最小值。6 10 12 9 610 6 14 7 67 8 12 9 610 14 17 9 712 15 7 8 40 4 3 2 04 0 5 0 01 2 3 2 03 7 7 1 08 11 0 3 00 4 6 3 04 0 8 1 01 2 6 3 03 7 01 2 08 11 3 4 066674min00310min此时每行及每列中肯定都有此时每行及每列中肯定都有0元素元素步骤步骤2：进行试分配，判断是否存在进行试分配，判断是否存在n个独立零元素个独立零元素 尝试对

9、所有零元素做尝试对所有零元素做标记标记，确定确定独立零元素独立零元素。（1）逐）逐行行检验检验对对只有一个只有一个的零元素的的零元素的行行，用，用记号记号O将该零元素圈起，然后将该零元素圈起，然后将将被圈起的零元素所在列被圈起的零元素所在列的其他的其他未标记的零元素未标记的零元素用用记号记号/划去。划去。01370606905320100重复行检验，直到重复行检验，直到每一行都没有未被标记每一行都没有未被标记的零元素的零元素或或至少有两个未至少有两个未被标记被标记的零元素为止。的零元素为止。表示此人只能做该事表示此人只能做该事（此事只能由该人做）（此事只能由该人做）表示此事已不能由表示此事已不

10、能由其他人来做其他人来做（此人已不能做其他事）（此人已不能做其他事）1604320405001232037710811030圈圈0即独立零元素即独立零元素步骤步骤2：进行试分配，判断是否存在进行试分配，判断是否存在n个独立零元素个独立零元素 尝试对所有零元素做尝试对所有零元素做标记标记，确定确定独立零元素独立零元素。（2）逐）逐行行检验检验17步骤步骤2：进行试分配，判断是否存在进行试分配，判断是否存在n个独立零元素个独立零元素 尝试对所有零元素做尝试对所有零元素做标记标记，确定确定独立零元素独立零元素。（2）逐）逐列列检验检验与行检验类似：与行检验类似：对只有一个未标记的零元素的对只有一个未

11、标记的零元素的列列，用记号，用记号O将该将该零元素圈起，然后将被圈起的零元素所在零元素圈起，然后将被圈起的零元素所在行行的其他未标记的零元的其他未标记的零元素用记号素用记号/划去。划去。重复重复列列检验，直到检验，直到没有未被标记没有未被标记的零元素的零元素或或至少有两个未被标记至少有两个未被标记的零元素为止。的零元素为止。013706069053201001804320405001232037710811030圈圈0即独立零元素即独立零元素步骤步骤2：进行试分配，判断是否存在进行试分配，判断是否存在n个独立零元素个独立零元素 尝试对所有零元素做尝试对所有零元素做标记标记，确定确定独立零元素独

12、立零元素。（2）逐）逐列列检验检验可能出现三种情况可能出现三种情况1.每一行均有圈每一行均有圈0出现，圈出现，圈0的个数恰好等于的个数恰好等于n2.存在未标记过的零元素，但它们所在的行和列中，未被标存在未标记过的零元素，但它们所在的行和列中，未被标记过的零元素的个数均至少有两个。记过的零元素的个数均至少有两个。3.不存在未被标记过的零元素，但圈不存在未被标记过的零元素，但圈0的个数的个数n可进行分配：令可进行分配：令圈圈0位置的决策变量取值位置的决策变量取值为为1，其他为，其他为0（3）判断）判断独立零元素独立零元素的个数的个数013706069053201000001010010000010

13、20可能出现三种情况可能出现三种情况2.存在未标记过的零元素，但它们所在的行和列中，未被标存在未标记过的零元素，但它们所在的行和列中，未被标记过的零元素的个数均至少有两个。记过的零元素的个数均至少有两个。3.不存在未被标记过的零元素，但圈不存在未被标记过的零元素，但圈0的个数的个数n从某从某行行（列列）的）的两个两个未被标记过的零元素中未被标记过的零元素中任选一个任选一个加上加上圈圈，然后给然后给同同列列、同、同行行的其他未被标记的零元素都加的其他未被标记的零元素都加/，然后再，然后再进行行、列检验，可能出现情况进行行、列检验，可能出现情况1或或3。（3）判断）判断独立零元素独立零元素的个数的

14、个数502092300801057598004063600100000100100000001000001圈圈0个数个数等于等于n=5多重最优解多重最优解21可能出现三种情况可能出现三种情况3.不存在未被标记过的零元素，但圈不存在未被标记过的零元素，但圈0的个数的个数n（3）判断）判断独立零元素独立零元素的个数的个数圈圈0个数个数4 n=5作作最少直线覆盖当前所有零元素最少直线覆盖当前所有零元素，便，便于下步增加独立零元素的个数。于下步增加独立零元素的个数。0432040500123203771081103022定理：定理：系数矩阵系数矩阵C中中独立零元素的最多个数独立零元素的最多个数等于等于

15、能覆能覆盖所有零元素的盖所有零元素的最少线数最少线数。由匈牙利数学家由匈牙利数学家D.Konig(康尼格康尼格)所证明所证明502023000567480050202230000105729800406365例例：分别求下列矩阵中的独立零元素的最多个数。：分别求下列矩阵中的独立零元素的最多个数。44独立零元素独立零元素的个数最多：的个数最多：23 对对不含圈不含圈0的行打的行打； 在打在打的行中，对所有零元素所在的行中，对所有零元素所在列列打打； 在所有打在所有打的列中，对圈的列中，对圈0所在所在行行打打； 重复重复2,3步，直到不能步，直到不能打打为止。为止。 对对未打未打的每一行的每一行画

16、一横线，对画一横线，对已打已打的每一列的每一列画画一纵线，即得到覆盖当前一纵线，即得到覆盖当前0元素的元素的最少直线最少直线集。集。0432040500123203771081103024找未被直线覆盖的最小数字找未被直线覆盖的最小数字k k；对矩阵的每行：当该行对矩阵的每行：当该行有直线覆盖时有直线覆盖时，令，令u ui i=0=0； 当该行当该行无直线覆盖无直线覆盖时时，令，令u ui i=k=k。04320405001232037710811030uiui0 01 11 10 00 0对矩阵的每列：当该对矩阵的每列：当该列列有直线覆盖时有直线覆盖时，令，令v vj j=-k=-k； 当该

17、当该列列无直线覆盖无直线覆盖时时，令，令v vj j=0=0。vjvj-1-10 00 00 00 02504320405001232037710811030uiui0 01 11 10 00 0vjvj-1-10 00 00 00 0 04320405000121026600811030从原矩阵的每个元素从原矩阵的每个元素aij 中分别减去中分别减去ui和和vj，得到新元，得到新元素素26再次寻找独立零元素再次寻找独立零元素 04320405000121026600811030逐逐列列检验检验 10000010000000100010001006 10 12 9 610 6 14 7 67

18、8 12 9 610 14 17 9 712 15 7 8 4原题：原题：分配方案分配方案A=7+9+6+6+6=3427再次寻找独立零元素再次寻找独立零元素 04320405000121026600811030逐逐列列检验检验 00001010001000000010001006 10 12 9 610 6 14 7 67 8 12 9 610 14 17 9 712 15 7 8 4分配方案分配方案B=7+9+7+6+6=3528 对对不含圈不含圈0的行打的行打； 在打在打的行中，对所有零元素所在的行中，对所有零元素所在列列打打； 在所有打在所有打的列中，对圈的列中，对圈0所在所在行行打打

19、； 重复重复2,3步，直到不能步，直到不能打打为止。为止。 对对未打未打的每一行的每一行画一横线，对画一横线，对已打已打的每一列的每一列画画一纵线，即得到覆盖当前一纵线，即得到覆盖当前0元素的元素的最少直线最少直线集。集。5020223000010572980040636550202230000105729800406365圈圈0个数个数4 n=529找未被直线覆盖的最小数字找未被直线覆盖的最小数字k k；对矩阵的每行：当该行对矩阵的每行：当该行有直线覆盖时有直线覆盖时，令，令u ui i=0=0； 当该行当该行无直线覆盖无直线覆盖时时，令，令u ui i=k=k。uiui0 00 02 20

20、 02 2对矩阵的每列：当该对矩阵的每列：当该列列有直线覆盖时有直线覆盖时，令，令v vj j=-k=-k； 当该当该列列无直线覆盖无直线覆盖时时，令，令v vj j=0=0。vjvj-2-20 00 00 00 05020223000010572980040636530 3414040089053800003220205从原矩阵的每个元素从原矩阵的每个元素aij 中分别减去中分别减去ui和和vj，得到新元，得到新元素素uiui0 00 02 20 02 2vjvj-2-20 00 00 00 05020223000010572980040636531 34140400890538000032

21、20205再次寻找独立零元素再次寻找独立零元素分配方案分配方案B 000010010010000010000001032 3414040089053800003220205再次寻找独立零元素再次寻找独立零元素分配方案分配方案B 000010100010000001000001033整体解题思路总结整体解题思路总结34整体解题思路总结整体解题思路总结例题：例题：人人1人人2人人3人人4人人5工作工作14871512工作工作279171410工作工作3691287工作工作46714610工作工作56912106单位：小时单位：小时35整体解题思路总结整体解题思路总结6 10 12 9 610 6

22、14 7 67 8 12 9 610 14 17 9 712 15 7 8 4例题：例题：36步骤步骤1：变换系数矩阵，使其每行每列都出现变换系数矩阵，使其每行每列都出现0元素元素 把各把各行行元素分别减去本行元素的最小值，然后元素分别减去本行元素的最小值，然后在此基础上在此基础上再把每再把每列列元素减去本列中的最小值。元素减去本列中的最小值。6 10 12 9 610 6 14 7 67 8 12 9 610 14 17 9 712 15 7 8 40 4 3 2 04 0 5 0 01 2 3 2 03 7 7 1 08 11 0 3 00 4 6 3 04 0 8 1 01 2 6 3

23、03 7 01 2 08 11 3 4 066674min00310min此时每行及每列中肯定都有此时每行及每列中肯定都有0元素元素3704320405001232037710811030圈圈0即独立零元素即独立零元素步骤步骤2：进行试分配，判断是否存在进行试分配，判断是否存在n个独立零元素个独立零元素 尝试对所有零元素做尝试对所有零元素做标记标记，确定确定独立零元素独立零元素。（2）逐）逐行行检验检验38可能出现三种情况可能出现三种情况3.不存在未被标记过的零元素，但圈不存在未被标记过的零元素，但圈0的个数的个数n（3）判断）判断独立零元素独立零元素的个数的个数圈圈0个数个数4 n=5作作最少直线覆盖当前所有零元素最少直线覆盖当前所有零元素，便，便于下步增加独立零元素的个数。于下步增加独立零元素的个数。0432040500123203771081103039 对对不含圈不含圈0的行打的行打； 在打在打的行中，对所有零元素所在的行中，对所有零元素所在列列打打； 在所有打在所有打的列中，对圈的列中，对圈0所在所在行行打打； 重复重复2,3步，直到不能步，直到不能打打为止。为止。 对对未打未打的每一行的每一行画一横线，对画一横线，对已打已打的每一列的每一列画画