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

1第五章整数规划§1整数规划的数学模型及特点要求一部分或全部决策变量必须取整数值得规划问题称为整数规划。其模型为：Max(或min)z=njjjxc1s.tnjnjiijijxxxnjxmibxa,,,2,10,2,1),(211若要求决策变量只能取值0或1的整数规划称为0-1型整数线性规划。§5指派问题一．指派问题的标准形式及数学模型在现实生活中，有各种性质的指派问题。例如，有若干项工作需要分配给若干人（或部门）来完成；有若干项合同需要选择若干个投标者来承包；有若干班级需要安排在各教室上课等等。诸如此类的问题，它们的基本要求是在满足特定的指派要求条件下，使指派方案的总体效果最佳。由于指派问题的多样性，有必要定义指派问题的标准形式。指派问题的标准形式（以人和事为例）是：有n个人和n件事，已知第i个人作第j件事的费用为),2,1,(njicij，要求确定人和事之间的一一对应的指派方案，是完成这n件事的总费用最少。为了建立标准指派问题的数学模型，引入2n个0-1变量：10ijx这样，问题的数学模型可写成ninjijijxcz11min（5.1）s.tnjixnixnjxijnjijniij,2,1,1,0,2,11,2,1111（5.3）其中，（5.1）表示每件事必优且只有一个人去做，（5.2）表示每个人必做且只做一件事。注：○1指派问题是产量（ia）、销量（jb）相等，且ia=jb=1，i，j=1,2,…n的运输中部分或全部取整数若指派第i人作第j件事若不指派第i人作第j事i，j=1,2,…n（5.2）（5.4）2问题。○2有时也称ijc为第i个人完成第j件工作所需的资源数，称之为效率系数（或价值系数）。并称矩阵C=nnijc)(=nnnnnnccccccccc212222111211（5.5）为效率矩阵（或价值系数矩阵）。并称决策变量ijx排成的n×n矩阵X=nnijx)(=nnnnnnxxxxxxxxx212222111211（5.6）为决策变量矩阵。(5.6)的特征是它有n个1，其它都是0。这n个1位于不同行、不同列。每一种情况为指派问题的一个可行解。共n!个解。其总的费用z=C⊙X这里的⊙表示两矩阵对应元素的积，然后相加。问题是：把这n个1放到X的2n个位置的什么地方可使耗费的总资源最少？（解最优）例1已知效率矩阵C=0084765000320205则X（1）=0100000110000010，X（2）=1000000101000010都是指派问题的最优解例12/P-149：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司Ai（i=1，2，…5）对新商店Bj（1，2，…5）的建造费用的报价（万元）为ijc（i，j=1,2,…5）,见表5-9。商业公司应当对5家建筑公司怎样分派建筑任务，才能使总的建筑费用最少？表5-93ijcB1B2B3B4B5A14871512A279171410A3691287A46714610A56912106解：这是一标准的指派问题。若设0-1变量ijx=01则问题的数学模型为Minz=411x+812x+…+1054x+655xs.t5,2,1,1,05,2,115,2,115151jixixjxijjijiij若看成运输问题，且ijx如上所述，则表5-9为商店公司B1B2B3B4B5任务A1（4）11x（8）12x（7）13x（15）14x（12）15x1A2（7）21x(9)22x(17)23x(14)24x(10)25x1A3(6)31x(9)32x(12)33x(8)34x(7)35x1A4(6)41x(7)42x(14)43x(6)44x(10)45x1A5(6)51x(9)52x(12)53x(10)54x(6)55x1当Ai承建Bj时当Ai不承建Bj时i,j=1,2,…54所选的公司数111115当然，第一行的1应放在（1，1）位置，此位置同时是第一列的费用最小。但一般情况下没有这么好。需找一适合一般的方法。二．匈牙利解法原理：虽然指派问题是一类特殊的整数规划问题，又是特殊的0-1规划问题和特殊的运输问题，因此，它可以用多种相应的解法来求解。但是，这些解法都没有充分利用指派问题的特殊性质，有效地减少计算量。1955年，库恩（W.W.Kuhn）提出了匈牙利法。定理1：设指派问题的效率矩阵为C=nnijc)(，若将该矩阵的某一行（或某一列）的各个元素都减去统一常数t（t可正可负），得到新的效率矩阵nnijcC)(，则以C为效率矩阵的新的指派问题与原指派问题的最优解相同。但其最优解比原最优解之减少t.证明：设式（5.1）～（5.4）为原指派问题。现在C矩阵的第k行个元素东减去同一常数t,记新的指派问题的目标函数为Z.则有Z=ni1njijijxc1=nkii1njijijxc1+njijijxc1=nkii1njijijxc1+njkjkjxtc1)(=nkii1njijijxc1+njkjkjxc1-tnjkjx1=ni1njijijxc1-t·1=Z-t因此有MinZ=min(Z-t)=minZ-t而新问题的约束方程同原指派问题。因此其最优解比相同，而最优解差一个常数。推论：若将指派问题的效率矩阵每一行即每一列分别减去各行及各列的最小元素，则得到新指派问题与原指派问题有相同的最优解。证明：结论是显然的。只要反复运用定理1便可得证。当将效率矩阵的每一行都减去各行的最小元素，将所得的矩阵的每一列在减去当前列中最小元素，则最后得到新效率矩阵C中必然出现一些零元素。设ijc=0，从第i行来看，它表示第i个人去干第j项工作效率（相对）最好。而从第j列来看，这个0表示第j项工作以第i人来干效率(相对)最高。定义：在效率矩阵C中，有一组在不同行不同列的零元素，称为独立零元素组，此时每个元素称为独立零元素。例2:已知C=0084765000320205则｛12c=0，24c=0，31c=0，43c=0｝是一个独立零元素组，12c=0，24c=0，31c=0，43c=0分别称为独立零元素。｛12c=0，23c=0，31c=0，44c=0｝也是一个独立零元素组，而5｛14c=0，23c=0，31c=0，44c=0｝就不是一个独立零元素组，因为14c=0与44c=0这两个零元素位于同一列中。根据以上对效率矩阵中零元素的分析，对效率矩阵C中出现的的独立零元素组中零元素所处的位置，在决策变量矩阵中令相应的ijx=1，其余的ijx=0。就可找到指派问题的一个最优解。就上例中X（1）=0100000110000010，就是一个最优解。同理X（2）=1000000101000010也是一个最优解。但是在有的问题中发现效率矩阵C中独立零元素的个数不够n个，这样就无法求出最优指派方案，需作进一步的分析。首先给出下述定理。定理2效率矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。我们不证它，说一下意思：例3：已知矩阵C1=0084765000320205，C2=5636040084275500003220205，C3=341404008653300003420207分别用最少直线去覆盖各自矩阵中的零元素：C1=0084765000320205，C2=5636040084275500003220205，C3=341404008653300003420207可见，C1最少需要4条线，C2最少需要4条线，C3最少需要5条线，方能划掉矩阵中所有的零。即它们独立零元素组中零元素最多分别为4，4，5。三．匈牙利法求解步骤：6我们以例题来说明指派问题如何求解：例4给定效率矩阵C=9118713161491514410413152求解该指派问题。解：ⅰ）变换效率矩阵，将各行各列都减去当前各行、各列中最小元素。C=91187131614915144104131522410475011100621113000102350960607130=C这样得到的新矩阵C中，每行每列都必然出现零元素。ⅱ）用圈0法求出新矩阵C中独立零元素。（1）进行行检验对C进行逐行检验，对每行只有一个未标记的零元素时，用○记号将该零元素圈起。然后将被圈起的零元素所在的列的其它未标记的零元素用记号×划去。如C中第2行、第3行都只有一个未标记的零元素，用○分别将它们圈起。然后用×划去第1列其它未被标记的零元素（第2列没有），见CC00102350960607130=C在第i行只有一个零元素ijc=0时，表示第i人干第j件工作效率最好。因此优先指派第i人干第j项工作，而划去第j列其它未标记的零元素，表示第j项工作不再指派其它人去干（即使其它人干该项工作也相对有最好的效率）。重复行检验，直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素时为止。本题C中第1行此时也只有1个未被标记的零元素。因此圈起C中第1行第4列的零元素14c，然后用×划去第4列中未被标记的零元素。这是第4行也只有一个未被标记的零元素43c，再用○圈起，见C行变换2497min列变换Min00427C00102350960607130=C（2）进行列检验与进行行检验相似，对进行了行检验的矩阵逐列进行检验，对每列只有一个未被标记的零元素，用记号○将该元素圈起，然后技改元素所在行的其他未被标记的零元素打×。重复上述列检验，直到每一列都没有未被标记的零元素或有两个未被标记的零元素为止。这时可能出现以下三种情况：○1每一行均有圈0出现，圈0的个数m恰好等于n,即m=n.○2存在未标记的零元素，但他们所在的行和列中，为标记过的零元素均至少有两个。○3不存在未被标记过的零元素，当圈0的个数mn.ⅲ)进行试指派若情况○1出现，则可进行试指派：令圈0为止的决策变量取值为1，其他决策变量取值均为零，得到一个最优指派方案，停止计算。上例中得到C后，出现了情况○1，可令14x=1，22x=1，31x=1，43x=1，其余ijx=0。即为最优指派。若情况○2出现，则在对每行、每列的其它未被标记的零元素任选一个，加上标记○，即圈上该零元素。然后给同行、同列的其它未被标记的零元素加标记×。然后再进行行、列检验，可能出现情况○1或○3，出现情况○1则由上述得到一最优指派，停止计算。若情况○3出现，则要转入下一步。ⅳ）：做最少直线覆盖当前所有零元素。我们还以例12来说明过程：已知例12指派问题的系数矩阵为：61012961081476781296101417971215784C先对各行元素分别减去本行的最小元素，然后对各列也如此，即C04630408101263037102081134004320405001232037710811030=C此时，C中各行各列都已出现零元素。为了确定C中的独立零元素，对C加圈，即行变换列变换8C=