指派问题含非标准指派问题

1、.第五章整数规划§ 1 整数规划的数学模型及特点要求一部分或全部决策变量必须取整数值得规划问题称为整数规划。其模型为：nMax( 或 min)z=c jx jj1naijxij(, )bii1,2,mj 1s.tx j0j1,2,nx1 , x2 ,xn中部分或全部取整数若要求决策变量只能取值0 或 1 的整数规划称为0-1 型整数线性规划。§ 5 指派问题一 指派问题的标准形式及数学模型在现实生活中， 有各种性质的指派问题。 例如，有若干项工作需要分配给若干人（或部门）来完成； 有若干项合同需要选择若干个投标者来承包；有若干班级需要安排在各教室上课等等。 诸如此类的问题，

2、它们的基本要求是在满足特定的指派要求条件下，使指派方案的总体效果最佳。由于指派问题的多样性，有必要定义指派问题的标准形式。指派问题的标准形式（以人和事为例）是：有 n 个人和n 件事，已知第i 个人作第j件事的费用为cij (i , j1,2,n) ，要求确定人和事之间的一一对应的指派方案，是完成这n件事的总费用最少。为了建立标准指派问题的数学模型，引入n 2 个 0-1 变量：0 若不指派第 i 人作第 j 事xiji 人作第 j件事i ， j=1,2, n1 若指派第这样，问题的数学模型可写成nnmin zcij xij（5.1 ）i 1j 1n（ 5.2）xij 1j 1,2,ni 1

3、ns.txij 1i1,2,n（5.3）j 1xij0,1i , j1,2,n（ 5.4）其中，（ 5.1）表示每件事必优且只有一个人去做，（ 5.2）表示每个人必做且只做一件事。注：1指派问题是产量（ai ）、销量（ b j ）相等，且ai =b j =1，i ， j=1,2,n 的运输;.问题。 有时也称 cij 为第 i个人完成第 j 件工作所需的资源数，称之为 效率系数 （或价值系2数）。并称矩阵c11c12c1nC=(cij ) n n =c21c22c2n（5.5 ）cn1cn 2cnn为效率矩阵（或价值系数矩阵）。并称决策变量 xij 排成的 n×n 矩阵x11x12x

4、1 nX= (xij ) nn =x21x22x2 n（ 5.6）xn1xn 2xnn为决策变量矩阵 。(5.6) 的特征是它有n 个 1，其它都是 0。这 n 个 1 位于不同行、不同列。每一种情况为指派问题的一个可行解。共n!个解。其总的费用 z =C X这里的 表示两矩阵对应元素的积，然后相加。问题是： 把这 n 个 1 放到 X 的 n2 个位置的什么地方可使耗费的总资源最少？（解最优）例 1已知效率矩阵50202300C=56704800则01000100X（1）= 0 00 1 ，X（2）=00101000100000100001都是指派问题的最优解例 12/P-149 ：某商业公

5、司计划开办五家新商店。为了尽早建成营业，商业公司决定由5 家建筑公司分别承建。已知建筑公司Ai （ i=1 ， 2， 5）对新商店Bj （ 1，2， 5）的建造费用的报价（万元）为cij （ i ， j=1,2,5） , 见表 5-9 。商业公司应当对5 家建筑公司怎样分派建筑任务，才能使总的建筑费用最少？表 5-9;.cijB 1B2B 3B4B5A 14871512A 279171410A 3691287A 46714610A 56912106解：这是一标准的指派问题。若设1当 A i 承建 Bj 时xij =当 A i 不承建 B j 时00-1 变量i,j=1,2,5则问题的数学模型为

6、Min z=4 x11 +8 x12 +10 x54 +6 x555xij1j1,2,5i 15s.txij1i1,2,5j1xij0,1i , j1,2,5若看成运输问题，且xij 如上所述，则表5-9 为商 B 1B2B3B4B 5任务店公司A 1（ 4）（8） （7）（ 15） （ 12）1x11x12x13x14x15A 2（ 7）(9)(17)(14)(10)1x21x22x23x24x25A 3(6)(9)(12)(8)(7)1x31x32x33x34x35A 4(6)(7)(14)(6)(10)1x41x42x43x44x45A 5(6)(9)(12)(10)(6)1x51x52

7、x53x54x55;.所选的公司数111115当然，第一行的 1 应放在（ 1， 1）位置，此位置同时是第一列的费用最小。但一般情况下没有这么好。需找一适合一般的方法。二 匈牙利解法原理：虽然指派问题是一类特殊的整数规划问题，又是特殊的 0-1 规划问题和特殊的运输问题，因此， 它可以用多种相应的解法来求解。 但是，这些解法都没有充分利用指派问题的特殊性质，有效地减少计算量。 1955 年，库恩（ W.W.Kuhn ）提出了匈牙利法。定理 1：设指派问题的效率矩阵为C= (cij ) n n ，若将该矩阵的某一行 （或某一列）的各个元素都减去统一常数t（ t 可正可负），得到新的效率矩阵C(c

8、ij ) n n ，则以 C 为效率矩阵的新的指派问题与原指派问题的最优解相同。但其最优解比原最优解之减少t.证明： 设式（ 5.1 ）（ 5.4 ）为原指派问题。现在C矩阵的第 k 行个元素东减去同一常数 t, 记新的指派问题的目标函数为Z .则有nnnnnnnnZ =cij xij=cijxij +cij xij =cij xij+(ckjt) xkji 1j 1i 1j 1j 1i 1j 1j 1i ki knnnnnn=cij xij+ckjxkj -txkj=cij xij-t · 1=Z-ti 1j 1j 1j 1i 1j 1i k因此有MinZ =min(Z-t)=mi

9、nZ-t而新问题的约束方程同原指派问题。因此其最优解比相同，而最优解差一个常数。推论：若将指派问题的效率矩阵每一行即每一列分别减去各行及各列的最小元素，则得到新指派问题与原指派问题有相同的最优解。证明： 结论是显然的。只要反复运用定理1 便可得证。当将效率矩阵的每一行都减去各行的最小元素，将所得的矩阵的每一列在减去当前列中最小元素，则最后得到新效率矩阵C中必然出现一些零元素。设c ij，从第i行来看，它=0表示第 i 个人去干第 j项工作效率（相对）最好。而从第j列来看， 这个 0表示第 j项工作以第 i 人来干效率 ( 相对 ) 最高。定义 ：在效率矩阵C 中，有一组在不同行不同列的零元素，

10、称为独立零元素组，此时每个元素称为独立零元素。例2: 已知50202300C=56704800则 c12 =0， c24=0， c31=0， c43 =0是一个独立零元素组，c12 =0， c24 =0， c31 =0 ，c43 =0 分别称为独立零元素。 c12 =0， c23 =0， c31 =0， c44 =0也是一个独立零元素组，而;. c14 =0， c23 =0 ， c31 =0， c44 =0就不是一个独立零元素组，因为c14 =0 与 c44 =0 这两个零元素位于同一列中。根据以上对效率矩阵中零元素的分析，对效率矩阵C 中出现的的独立零元素组中零元素所处的位置，在决策变量矩阵

11、中令相应的xij =1，其余的 xij =0。就可找到指派问题的一个最优解。就上例中0100X （1）= 0001，10000010就是一个最优解。同理0100X=0010（2）10000001也是一个最优解。但是在有的问题中发现效率矩阵 C 中独立零元素的个数不够 n 个，这样就无法求出最优指派方案，需作进一步的分析。首先给出下述定理。定理 2 效率矩阵 C 中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。我们不证它，说一下意思：例 3：已知矩阵502502027020203000430002302072， C3=0335C1=56，C2=0550780046800448040636

12、5041430分别用最少直线去覆盖各自矩阵中的零元素：50205020270202230004300023000 5 572，C3=0335C1 =56， C2=07480046800448000636504143可见， C1 最少需要4 条线， C2最少需要4 条线， C3最少需要 5 条线，方能划掉矩阵中所有的零。即它们独立零元素组中零元素最多分别为4， 4，5。三 匈牙利法求解步骤：;.我们以例题来说明指派问题如何求解：例 4 给定效率矩阵2151341041415C=914161378119求解该指派问题。解： ）变换效率矩阵，将各行各列都减去当前各行、各列中最小元素。min21513

13、41041415C=9141613781192013112013704行变换列变换60101160690574053= C92701420100Min0042这样得到的新矩阵C 中，每行每列都必然出现零元素。）用圈 0 法求出新矩阵C 中独立零元素。（ 1）进行行检验对 C 进行逐行检验，对每行只有一个未标记的零元素时，用记号将该零元素圈起。然后将被圈起的零元素所在的列的其它未标记的零元素用记号×划去。如C 中第 2 行、第3 行都只有一个未标记的零元素，用分别将它们圈起。然后用×划去第1 列其它未被标记的零元素（第2 列没有），见 C013706069C= C053201

14、00在第 i 行只有一个零元素cij =0 时，表示第i 人干第 j 件工作效率最好。因此优先指派第 i 人干第 j 项工作， 而划去第 j 列其它未标记的零元素， 表示第 j 项工作不再指派其它人去干（即使其它人干该项工作也相对有最好的效率）。重复行检验， 直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素时为止。本题 C 中第 1 行此时也只有1 个未被标记的零元素。因此圈起C 中第 1 行第 4 列的零元素 c14 ，然后用×划去第4 列中未被标记的零元素。这是第4 行也只有一个未被标记的零元素 c43 ，再用圈起，见C;.013706069C= C05320100（

15、2）进行列检验与进行行检验相似，对进行了行检验的矩阵逐列进行检验，对每列只有一个未被标记的零元素， 用记号将该元素圈起， 然后技改元素所在行的其他未被标记的零元素打×。 重复上述列检验，直到每一列都没有未被标记的零元素或有两个未被标记的零元素为止。这时可能出现以下三种情况： 每一行均有圈0 出现，圈 0 的个数 m恰好等于 n, 即 m=n.1 存在未标记的零元素，但他们所在的行和列中，为标记过的零元素均至少有两个。2 不存在未被标记过的零元素，当圈0 的个数 m< n.3) 进行试指派0 为止的决策变量取值为1，其他决策变量取值若情况 出现，则可进行试指派：令圈1均为零，得到

16、一个最优指派方案，停止计算。上例中得到 C后，出现了情况 1 ，可令 x14 =1， x22 =1， x31=1 ， x43 =1，其余 xij =0。即为最优指派。若情况2 出现，则在对每行、每列的其它未被标记的零元素任选一个，加上标记，即圈上该零元素。然后给同行、同列的其它未被标记的零元素加标记×。然后再进行行、列检验，可能出现情况1 或3 ，出现情况1 则由上述得到一最优指派，停止计算。若情况3 出现，则要转入下一步。 ）：做最少直线覆盖当前所有零元素。我们还以例12 来说明过程：已知例 12 指派问题的系数矩阵为：487151279171410C691287671481069

17、12106先对各行元素分别减去本行的最小元素，然后对各列也如此，即043118030118行变换021073列变换01773C= C0 3 6210232101804005040364002340此时， C 中各行各列都已出现零元素。为了确定 C 中的独立零元素，对C 加圈，即;.03011801773C = 023210050402340由于只有4 个独立零元素，少于系数矩阵阶数n=5, 不能进行指派，为了增加独立零元素的个数，需要对矩阵作进一步的变换，变换步骤如下：（ 1）对 C 中所有不含圈0 元素的行打 ，如第 3 行。（ 2）对打 的行中，所有零元素所在的列打，如第1 列。（ 3）对

18、所有打列中圈0 元素所在行打，如第2 行。（ 4）重复上述（ 2），（ 3）步，直到不能进一步打为止。（ 5）对未打的每一行划一直线，如第1，3， 5 行。对已打的每一列划一纵线，如第 1 列，既得到覆盖当前0 元素的最少直线数。见C。0301180301180177301773C=0232102321=C00504005040234002340）：对矩阵 C作进一步变换，以增加0 元素。在未被直线覆盖过的元素中找最小元素，将打行的各元素减去这个最小元素，将打裂的各元素加上这个最小元素（以避免打行中出现负元素） ，这样就增加了零元素的个数。如 C中未被直线覆盖过的元素中，最小元素为 c21 =

19、c35 =1，对打的第2，3 行各元素都减去2，对打的第1 列各元素都加上1，得到矩阵 C。03011 81301181066200662C1121001 210=C00504105040234012340）：回到步骤） ，对已增加了零元素的矩阵，再用圈0 法找出独立零元素组 = 012101050412340C中已有 5 个独立零元素，故可确定指派问题的最优方案。本例的最优解为;.0010001000X*= 100000001000001也就是说，最优指派方案是：让A 1承建B 3A 2B2A 3B1A 4B4A 5B5这样按排能使总的建造费最少，为z=79 6 6

20、6=34（万元）四 一般的指派问题在实际应用中，常会遇到非标准形式，解决的思路是：先化成标准形式，然后再用匈牙利法求解。1 最大化的指派问题其一般形式为nnmax zcij xiji 1j 1nxij1j1,2,ni1s.tnxij1i1,2,nj1xij0,1i, j1,2,n处理办法：设最大化的指派问题的系数矩阵为C= (cij )n n ， m=max c11 , c12 , cnn , 令B=(Bij )n n =(m cij ) n n ，则以 B 为系数矩阵的最小化指派问题和以C 为系数矩阵的原最大化指派问题有相同的最优解。例 5：某工厂有 4 名工人 A 1， A 2，A 3，

21、A 4，分别操作 4 台车床 B1， B 2， B3， B 4。每小时单产量如下表，求产值最大的分配方案。车床B 1B2B3B4工人A 110987A 23456A 32112A 44356;.10987解： C= (cij ) n n =3456， m=max 10,9,8,7,5,6 =10,21124356012301230013B=(Bij )n n =(10cij ) n n =76543210310089980110000=0675423102200= BB 中的数 =n=4,所以10000001（5。 7）X=10000010即为最优解。从而产值最大的分配方案也为（5.7 ），最

22、大产值为Z=10 6 1 5=222 人数和事数不等的指派问题。1 若人数 < 事数，添一些虚拟的 “人”，此时这些虚拟的 “人” 做各件事的费用系数取为 0，理解为这些费用实际上不会发生。2 若人数 > 事数，添一些虚拟的“事” ，此时这些虚拟的“事”被各个人做的费用系数同样也取为 0。例 6：现有 4 个人， 5 件工作。每人做每件工作所耗时间如下表：工作B1B2B3B4B5工人A10114281A7111014122A56912143A1315111074问指派那个人去完成哪项工作，可是总消耗最小？解：添加虚拟人A5，构造标准耗时阵：;.1011428892067111014

23、12行变换04375C= 569121401479= C13 1511107684300000000000所圈 0 数 =4< 5=n,下找最少覆盖0 的直线。8920604375C = 014796843000000从未划去的元素中找最小者： 4，3，7， 5， 1，4，7， 9 =1。未划去的行减去此最小者 1，划去的列加上次最小者 1，得 C 。9920603264C = 003687843010000个数 =n,从而的一最优指派：0001010000X=010000000100100从而最少耗时为z=2 7 67=223. 一个人可做几件事的指派问题。若某人可作几件事，则可将该人

24、化作相同的几个“人”来接受指派。这几个“人”做同一件事的费用系数当然一样。例 6：对例 12 的指派问题，为了保证工程质量，经研究决定，舍弃建筑公司 A 4 和 A 5，让技术力量较强的建筑公司 A 1、A 2、A 3 来承建。根据实际情况，可以允许每家建筑公司承建一家或两家商店。求使总费用最少的指派方案。解：反映投标费用的系数矩阵为：B1B2B3B4B54871512A179171410A2691287A3由于每家建筑公司最多可承建两家新商店，因此，把每家建筑公司化作相同的两家建筑公司（ Ai 和 Ai ， i=1 ， 2，3）。这样，系数矩阵变为：B1B2B3B4B5;.487151248

25、71512791714107917141069121276912127上面的系数矩阵有 6 行 5 列，为了使“人”和“事”的数目相同，引入一件虚拟事，使之成为标准的指派问题，其系数矩阵为：BB2B3BB5B1464871512048715120C=79171410079171410069128706912870000750000750列变换3110630= CC3110630215000215000C 的数 =5< 6=n, 下找 0 元素的最少直线覆盖。000750000750C=3110630-13110630 -1215000215000000751000751209520= C

26、209520215001215001从而得一最优指派：001000承建100000公司商店010000A1B 1X =00001B 30000010A2B 2000100B 6= B 4A3B 5;.总费用为z=7 4 9 7 8=35( 万元 )4某事不能由某人去做的指派问题某事不能由某人去做，可将此人做此时的费用取作足够大的M 。例 7：分配甲、乙、丙、丁四个人去完成 A 、 B、 C、 D、 E 五项任务，每人完成各项任务的时间如下表。由于任务重，人数少，考虑：a). 任务 E 必须完成，其它4 项任务可选3 项完成。但甲不能做A 项工作。b) 其中有一人完成两项，其他人每人完成一项。试

27、分别确定最优分配方案，使完成任务的总时间最少。任务ABCDE人甲2529314237乙3938262033丙3427284032丁2442362345解：这是一人数与工作不等的指派问题，若用匈牙利法求解，需作一下处理。a) 由于任务数大于人数，所以需要有一个虚拟的人，设为戊。因为工作E 必须完成，故设戊完成 E 的时间为 M （ M 为非常大的数） ，即戊不能做工作E，其余的假想时间为 0，建立的效率矩阵表如下：任ABCDE务人甲M29314237乙3938262033丙3427284032丁2442362345戊0000M用匈牙利法求解过程如下：M29314237M021383938262033 行变换19186013 列变换C=34272840327011352442362345119130220000M0000MM021331918608701130119130170000M由于数 =4<5=阶数，下找最少覆盖0 的直线;.M021331918608C =