指派问题――匈牙利法

指派问题的求解方法匈牙利法•指派问题的求解方法2指派问题及求解方法1、指派问题的提出•有n项不同的任务，恰好分派给n个人分别承担，由于每人完成各项任务的效率情况不同。现假设必须指派每个人去完成一项任务，需考虑怎样把n项任务指派给n个人，使得完成n项任务的总的效率最高，这就是指派问题。例．有4个工人，要分别指派他们完成4项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。工作工人ABCD甲15182124乙19232218丙26171619丁192123173解：令xij=1(第i人完成第j项工作)或0（第i人不进行第j项工作)．于是得到一个0--1整数规划问题：Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.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工作只能一人干)x13+x23+x33+x43=1(C工作只能一人干)x14+x24+x34+x44=1(D工作只能一人干)xij为0--1变量，i,j=1,2,3,42、指派问题的一般形式设有n个资源（人或机器等）A1,A2,…,An，分配做n件事B1,B2,…Bn，要求每件事必须使用1个资源，且不同事件由不同资源完成。已知Ai做Bj的效率（如劳动工时、成本、创造价值等）为cij。问如何进行指派可使总工作效率最佳？指派问题的一般形式定义变量：设指派问题变量为xij,，则共有n2个变量，且变量取值为：xij=1或0(xij=1表示Ai做Bj，否则取值为0)由cij(0)组成的方阵称为效率矩阵，模型为：10),,2,1(1),,2,1(1..1111orxnjxnixtsxczMinijniijnjijninjijij3、指派问题的匈牙利解法•1955年，库恩（W.W.Kuhn）利用匈牙利数学家康尼格（D.König）关于矩阵中独立零元素定理，提出了一种指派问题算法，被称为匈牙利解法。•指派问题的任何可行解由n2个满足约束条件的数xij组成。这些xij中，有n个为1，其余均为0，且此n个1必位于损益表中不同行不同列中，由此n个xij=1确定了n个相应的cij也位于效率矩阵中的不同行不同列上，相应的可行解的目标函数值由此n个cij之和确定。指派问题的匈牙利解法定理6.1：设C=(cij)是一个效率矩阵，若可行解x*=(xij)的n个1所对应的n个C=(cij)均为0，则x*是最优解。定理6.2：设给定了以C=(cij)为效率矩阵的指派问题G，现将C的元素cij改变为：c’ij=cij-i-j，其中：i,j为常数。则以C’=(c’ij)为效率矩阵的指派问题G’与G有相同的最优解。•约化矩阵：效率矩阵通过行或列同时加上（减去）一个常数得到的矩阵。指派问题的性质定理的证明定理6.2：对于指派问题，效率矩阵的任一行(或列)减去(或加上)一个相同的数得到的新指派问题与原问题同解。s)(s)(xcxcxs)(xcxcs)x(cxc=zn1jkjkjnki1in1jijijn1jkjn1jkjkjnki1in1jijijn1jkjkjnki1in1jijijz指派问题的匈牙利解法•根据此定理，可以对做如下改变，目的是找出C中的n个不同行不同列的0元素：•将C的每一行减去该行中的最小元素，得到C’矩阵，则C’的每行中均至少出现一个0元素，且所有cij0。同样，对C的列亦进行如此计算，由此，我们完全可以从原效率矩阵出发，得到一个新的效率矩阵，使C的每行每列中均至少存在一个0元素，而不改变问题的最优解。指派问题的匈牙利解法约化矩阵性质应用347100320460315310),2(),5(),2(),2(43219322875982537532列减，再对第得到行分别加，，，第例：C约化矩阵性质应用（续）•注：不同行不同列的0元素，称为独立0元素,当矩阵中含有n个独立0元素时即得解。142822141)0(0)0(2043)0(31231)0(52342311fxxxx相应最小费用是一组最优解，显然，得到6072395006024310指派问题的匈牙利解法定理6.3设矩阵C中含有0元素，那么划去C中所有0元素所需的最少直线数等于C中独立0元素的个数。例下列矩阵中，最少3条直线覆盖了所有0元素，因此可判定矩阵有3个独立0元素。13指派问题的匈牙利解法——步骤Step1.每行减去该行的最小数,每列减去该列的最小数，使矩阵每行每列均有0元素；Step2.寻找独立0元素•从单个0元素的行(列)开始，给0加圈，记作◎，然后划去所在列(行)的其它0元素，记为；重复进行，直到处理完所有列(行)的单个0元素；•若还存在没有画圈的0元素(同行或同列中的0元素多于1个)，则从剩余的0元素最少的行(列)开始，选0元素画圈，然后划掉同行同列的其它0元素，反复进行，直到所有0元素均被圈出或划掉为止；若◎元素的数目m=n，则该指派问题的最优解已经得到，否则转入Step3；指派问题的匈牙利解法——步骤（续）Step3.设有mn个◎,找最少覆盖所有0的直线1)对没有◎的行打√2)对已打√行中含所在列打√3)对已打√列中含◎所在行打√4)重复2)~3),直至没有要打√的行和列为止5)对没有打√的行划横线,对打√的列划竖线得到最少覆盖所有0的直线数l。•若ln，则转Step4；若l=n，则转Step2重新派；14指派问题的匈牙利解法——步骤（续）Step4设未被这些直线覆盖的元素中的最小值为。对未划线的行减去，划线的列加上。转Step2。指派问题的匈牙利解法—例•分别减去各行最小数7、6、7、6、49107104106614159141217766698979712指派问题的匈牙利解法—例•各行、列均有0元素56360400892751000003220205指派问题的匈牙利解法—例•试派并划线2445636040)0(8927510)0(0)0(032202)0(5lm指派问题的匈牙利解法—例•得到新的矩阵，再次试派，得解324696713414)0(4)0(0811)0(538000)0(34202)0(7**51*44*35*23*12fxxxxx指派问题——匈牙利法•练习例题：甲乙丙丁四个人，A、B、C、D四项任务，不同的人做不同的工作效率不同，表中数据为时耗，如何指派不同的人去做不同的工作使效率最高？任务人时间ABCD甲乙丙丁41075276333444663数模：minZ=ΣΣcijxijΣxij=1i=1,…,nΣxij=1j=1,…,nXij=0或1指派问题解法—匈牙利法解：类似运输问题的最小元素法第一步造0——各行各列减其最小元素41075-40631621Cij=2763-2054105313344-300110014663-31330132-1第二步圈0——寻找不同行不同列的0元素，圈之。所在行和列其它0元素划掉第三步打——无的行打，打行上0列打，打列上行打，打行上0列打…第四步划线——无行、打列划线第五步造0——直线未覆盖的元素，减去其最小值，交叉点上加最小元素，产生新的0元素，Goto20621-1510040Cij=0531-1042031000011012021320232221+1最优解：x13=1,x21=1,x32=1,x44=1Z=15独立练习•P161第6.4题6.5.4非标准形式的指派问题•非标准型指派问题求解的总原则是化非标准形式为标准形式，然后用匈牙利解法求解。(1)最大化指派问题设效率矩阵为，其中最大元素为m，令矩阵，则以B为效率矩阵的最小化指派问题和以C为效率矩阵的原最大化指派问题有相同的最优解；nnijcC)(ijijnnijcmbbB,)(非标准形式的指派问题(2)资源数量(人数等)与事件数不等的指派•若资源少，事件多，则增加一些虚拟的资源点，这些虚拟的资源做事件的效率系数为0，可理解为这些费用(成本)实际上不会发生；•若资源多，事件少，则增加一些虚拟事件，这些虚拟事件被资源实现的费用(成本、效率)取值为0；非标准形式的指派问题(3)一个资源可以做多件事的指派问题若某资源可以用来做几件事件，则可将该资源化作相同的几个资源来接受指派，这几个“资源”做同一事件的费用（效率）系数取相同值；(4)某一事件不允许由某一资源做的情况处理取相应的矩阵系数为M(M0充分大)非标准形式的指派问题—例任务与人员数不等的情况分配甲、乙、丙、丁4人去完成5项任务，每人完成各项任务的时间如下表。由于任务多，规定其中有一人可兼完成两项任务，试确定总花费时间最少的分派方案。非标准形式的指派问题—例各人完成不同任务的效率情况任务人ABCDE甲59112217乙242311518丙14782012丁42216325非标准形式的指派问题—例解：增加一人，其完成各项任务时间为该任务完成的最少时间：任务人ABCDE甲59112217乙242311518丙14782012丁42216325戊4丁7丙8丙3丁12丙非标准形式的指派问题—例人多任务少，允许某人空闲从甲、乙、丙、丁、戊5人中选4人去完成4项任务，每人完成各项任务的时间如下表。规定每人只能完成一项任务。由于某种原因，甲必须被分配一项任务，丁不承担第4项任务，试确定总花费时间最少的分派方案。非标准形式的指派问题—例各人完成不同任务的效率情况人工作甲乙丙丁戊1102315925101524315514715420151368非标准形式的指派问题—例解：增加虚设任务5，完成该任务时间为0，某人不完成某任务时，取时间M人工作甲乙丙丁戊11023159251015243155147154201513M85M0000