《指派问题(含非标准指派问题)》由会员分享，可在线阅读，更多相关《指派问题(含非标准指派问题)（18页珍藏版）》请在金锄头文库上搜索。
1、第五章 整数规划1整数规划的数学模型及特点规定一部分或所有决策变量必须取整数值得规划问题称为整数规划。其模型为: Ma(或mi)z=中部分或所有取整数 s.t若规定决策变量只能取值0或的整数规划称为0-1型整数线性规划。 5 指派 问 题一 指派问题的原则形式及数学模型在现实生活中,有多种性质的指派问题。例如，有若干项工作需要分派给若干人（或部门）来完毕；有若干项合同需要选择若干个投标者来承包;有若干班级需要安排在各教室上课等等。诸如此类的问题，它们的基本规定是在满足特定的指派规定条件下，使指派方案的总体效果最佳。由于指派问题的多样性,有必要定义指派问题的原则形式。指派问题的原则形式(以人和事
2、为例)是：有个人和n件事,已知第个人作第j件事的费用为，规定拟定人和事之间的一一相应的指派方案，是完毕这n件事的总费用至少。为了建立原则指派问题的数学模型，引入个0-1变量:若指派第i人作第j件事若不指派第i人作第j事i，j=1,2,n 这样,问题的数学模型可写成 （5.1)（5.4）（5.2） t (5）其中，（5）表达每件事必优且只有一种人去做，(5.2）表达每个人必做且只做一件事。注: 指派问题是产量(）、销量（)相等，且=1，i，j=1,2，的运送问题。 有时也称为第i个人完毕第件工作所需的资源数,称之为效率系数(或价值系数)。并称矩阵 C = （55）为效率矩阵(或价值系数矩阵)。并
3、称决策变量排成的nn矩阵= （5.6）为决策变量矩阵。(56)的特性是它有n个1,其他都是0。这n个1位于不同行、不同列。每一种状况为指派问题的一种可行解。共!个解。其总的费用 z CX 这里的表达两矩阵相应元素的积,然后相加。问题是:把这n个1放到的个位置的什么地方可使耗费的总资源至少?(解最优)例已知效率矩阵 C 则 X(1）= , X(2）= 都是指派问题的最优解例2-14:某商业公司筹划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司Ai(=1，2,5）对新商店Bj（1,5)的建造费用的报价(万元)为（i，j=1,2，5）,见表5-9。商业公司应当对5
4、家建筑公司如何分派建筑任务,才干使总的建筑费用至少？表-9BB2B3BA14871512A2791714A391287A46105691206解：这是一原则的指派问题。若设0变量i,j=1,2,5当Ai不承建Bj时当Ai承建Bj时则问题的数学模型为 M =+0+6 s.t若当作运送问题，且如上所述,则表5-9为商店公司1B2B3B4B任务A(4)()（7）(15)（2)1A(7）（)(17)(14)(1)1A3()(9）()(8)(7）1A4（6)(7)（14)（)(1)1A(6)(9）(2)(1）(6）1所选的公司数1111固然,第一行的1应放在(1，1)位置,此位置同步是第一列的费用最小。
5、但一般状况下没有这样好。需找一适合一般的措施。二 匈牙利解法原理：虽然指派问题是一类特殊的整数规划问题，又是特殊的0-1规划问题和特殊的运送问题，因此，它可以用多种相应的解法来求解。但是,这些解法都没有充足运用指派问题的特殊性质,有效地减少计算量。9年,库恩（WKun)提出了匈牙利法。定理1:设指派问题的效率矩阵为C= ，若将该矩阵的某一行（或某一列）的各个元素都减去统一常数t(可正可负），得到新的效率矩阵,则觉得效率矩阵的新的指派问题与原指派问题的最优解相似。但其最优解比原最优解之减少t证明:设式（5.1）(.4)为原指派问题。目前C矩阵的第k行个元素东减去同一常数t，记新的指派问题的目的函
6、数为.则有=+= =+-t=-=Z-t因此有 Min=min（Z-t)mnZ-t而新问题的约束方程同原指派问题。因此其最优解比相似,而最优解差一种常数。推论：若将指派问题的效率矩阵每一行即每一列分别减去各行及各列的最小元素,则得到新指派问题与原指派问题有相似的最优解。证明：结论是显然的。只要反复运用定理便可得证。当将效率矩阵的每一行都减去各行的最小元素,将所得的矩阵的每一列在减去目前列中最小元素,则最后得到新效率矩阵中必然浮现某些零元素。设=0,从第i行来看,它表达第个人去干第项工作效率(相对)最佳。而从第j列来看，这个表达第项工作以第人来干效率（相对)最高。定义：在效率矩阵C中，有一组在不同
7、行不同列的零元素，称为独立零元素组，此时每个元素称为独立零元素。例2: 已知 C 则=0，=0，0,0是一种独立零元素组,=0，0，=,=0分别称为独立零元素。=,=0,=0,0也是一种独立零元素组,而，=0，=0,=0就不是一种独立零元素组，由于=0与0这两个零元素位于同一列中。根据以上对效率矩阵中零元素的分析,对效率矩阵中浮现的的独立零元素组中零元素所处的位置，在决策变量矩阵中令相应的=，其他的=。就可找到指派问题的一种最优解。就上例中 (1）= ，就是一种最优解。同理 X（2)= 也是一种最优解。但是在有的问题中发现效率矩阵C中独立零元素的个数不够n个,这样就无法求出最优指派方案，需作进
8、一步的分析。一方面给出下述定理。定理2效率矩阵中独立零元素的最多种数等于能覆盖所有零元素的至少直线数。我们不证它,说一下意思:例3：已知矩阵C1= ,C2= ,3=分别用至少直线去覆盖各自矩阵中的零元素:C1= ，C= ，C3=可见,C1至少需要4条线，C2至少需要4条线，C3至少需要条线，方能划掉矩阵中所有的零。即它们独立零元素组中零元素最多分别为,5。三 匈牙利法求解环节:我们以例题来阐明指派问题如何求解：例4给定效率矩阵 C=求解该指派问题。解：）变换效率矩阵,将各行各列都减去目前各行、各列中最小元素。min 列变换行变换7942C Min 0 0 4 2这样得到的新矩阵中,每行每列都必
9、然浮现零元素。)用圈0法求出新矩阵中独立零元素。（)进行行检查对进行逐行检查，对每行只有一种未标记的零元素时,用记号将该零元素圈起。然后将被圈起的零元素所在的列的其他未标记的零元素用记号划去。如中第2行、第行都只有一种未标记的零元素,用分别将它们圈起。然后用划去第1列其他未被标记的零元素(第2列没有）,见 在第行只有一种零元素=0时，表达第人干第件工作效率最佳。因此优先指派第人干第j项工作,而划去第j列其他未标记的零元素,表达第j项工作不再指派其别人去干(虽然其别人干该项工作也相对有最佳的效率）。反复行检查,直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素时为止。本题中第1行此时也
10、只有个未被标记的零元素。因此圈起中第1行第4列的零元素，然后用划去第4列中未被标记的零元素。这是第4行也只有一种未被标记的零元素,再用圈起，见 （2）进行列检查 与进行行检查相似，对进行了行检查的矩阵逐列进行检查，对每列只有一种未被标记的零元素，用记号将该元素圈起，然后技改元素所在行的其她未被标记的零元素打。反复上述列检查，直到每一列都没有未被标记的零元素或有两个未被标记的零元素为止。这时也许浮现如下三种状况:每一行均有圈浮现,圈0的个数m正好等于n,即m.存在未标记的零元素，但她们所在的行和列中，为标记过的零元素均至少有两个。不存在未被标记过的零元素，当圈0的个数m .） 进行试指派若状况浮
11、现，则可进行试指派：令圈0为止的决策变量取值为1,其她决策变量取值均为零,得到一种最优指派方案，停止计算。上例中得到后，浮现了状况,可令=1，=,=，=1,其他=0。即为最优指派。若状况浮现，则在对每行、每列的其他未被标记的零元素任选一种,加上标记，即圈上该零元素。然后给同行、同列的其他未被标记的零元素加标记。然后再进行行、列检查，也许浮现状况或，浮现状况则由上述得到一最优指派,停止计算。若状况浮现,则要转入下一步。):做至少直线覆盖目前所有零元素。我们还以例1来阐明过程：已知例12指派问题的系数矩阵为： 先对各行元素分别减去本行的最小元素,然后对各列也如此,即列变换行变换 =此时,中各行各列
12、都已浮现零元素。 为了拟定中的独立零元素,对加圈，即由于只有4个独立零元素,少于系数矩阵阶数n=5,不能进行指派,为了增长独立零元素的个数，需要对矩阵作进一步的变换,变换环节如下：()对中所有不含圈0元素的行打,如第3行。（2)对打的行中,所有零元素所在的列打，如第列。(3）对所有打列中圈0元素所在行打,如第2行。(4）反复上述（2）,(3)步，直到不能进一步打为止。（5)对未打的每一行划始终线,如第1,3，5行。对已打的每一列划一纵线,如第1列,既得到覆盖目前0元素的至少直线数。见。= =):对矩阵作进一步变换,以增长0元素。在未被直线覆盖过的元素中找最小元素，将打行的各元素减去这个最小元素，将打裂的各元素加上这个最小元素(以避免打行中浮现负元素)，这样就增长了零元素的个数。如中未被直线覆盖过的元素中,最小元素为=1，对打的第2,3行各元素都减去2,对打的第列各元素都加上,得到矩阵。 ）：回到环节),对已增长了零元素的矩阵,再用圈法找出独立零元素组。中已有5个独立零元素，故可拟定指派问题的最优方案。本例的最优解为承建X*也就是说,最优指派方案是：让A1 B3 A2 2 A B1
