指派问题(0-1规划---程序)

指派问题（assignmentproblem）问题一：今分派n个工人n去从事n项工作nJJJ,,,21.工人iW从事工作jJ的工作效率为njicij,,2,1,,.试求一个分派方案，使每个工人都从事一项工作，每项工作都由一个工人承担，且总工作效率最大.建模：令否则，件事，个人做第指派第,0,1jixijnji,,2,1,则可建立如下数学规划模型：njixnjxnixtsxczijniijnjijninjijij,,2,1,,1,0,,2,1,1,,2,1,1..min1111算例1利用LINGO软件求解如下指派问题：5n，61012961061476781296101417971215784C.模型求解：Lingo程序：model:sets:Worker/W1..W5/;Job/J1..J5/;links(Worker,Job):c,x;endsetsdata:c=4,8,7,15,12,7,9,17,14,10,6,9,12,8,7,6,7,14,6,10,6,9,12,10,6;enddatamin=@sum(links:c*x);@for(Worker(i):@sum(Job(j):x(i,j))=1);@for(Job(j):@sum(Worker(i):x(i,j))=1);@for(links:@bin(x));end注：程序中并没限制ijx是0-1变量，但由其余约束条件足以保证返回的结果中变量的值为0、1.结果：Globaloptimalsolutionfound.Objectivevalue:34.00000Extendedsolversteps:0Totalsolveriterations:0VariableValueReducedCostC(W1,J1)4.0000000.000000……C(W5,J5)6.0000000.000000X(W1,J1)0.0000004.000000X(W1,J2)0.0000008.000000X(W1,J3)1.0000007.000000X(W1,J4)0.00000015.00000X(W1,J5)0.00000012.00000X(W2,J1)0.0000007.000000X(W2,J2)1.0000009.000000X(W2,J3)0.00000017.00000X(W2,J4)0.00000014.00000X(W2,J5)0.00000010.00000X(W3,J1)1.0000006.000000X(W3,J2)0.0000009.000000X(W3,J3)0.00000012.00000X(W3,J4)0.0000008.000000X(W3,J5)0.0000007.000000X(W4,J1)0.0000006.000000X(W4,J2)0.0000007.000000X(W4,J3)0.00000014.00000X(W4,J4)1.0000006.000000X(W4,J5)0.00000010.00000X(W5,J1)0.0000006.000000X(W5,J2)0.0000009.000000X(W5,J3)0.00000012.00000X(W5,J4)0.00000010.00000X(W5,J5)1.0000006.000000算例2今分派5个工人521,,,去从事5项工作521,,,JJJ.工人iW从事工作jJ的时间)5,,2,1,(jicij见下表：1J2J3J4J5J1W86109122W91271193W743584W9581185W467511试求一个分派方案，使每个工人都从事一项工作，每项工作都由一个工人承担，且总工作时间最少.建模：令5,,1,,,,0,,1jiJWxjiij否则从事工作分派工人，则可建立如下0-1规划模型：5,,1,,1,05,,1,15,,1,1..max51515151jixjxixtsxczijiijjijijijij模型求解：Lingo程序如下：model:sets:Worker/W1..W5/;Job/J1..J5/;links(Worker,Job):c,x;endsetsdata:c=8,6,10,9,12,9,12,7,11,9,7,4,3,5,8,9,5,8,11,8,4,6,7,5,11;enddatamin=@sum(links:c*x);@for(Worker(i):@sum(Job(j):x(i,j))=1);@for(Job(j):@sum(Worker(i):x(i,j))=1);@for(links:@bin(x));end结果：Globaloptimalsolutionfound.Objectivevalue:30.00000Extendedsolversteps:0Totalsolveriterations:0VariableValueReducedCostC(W1,J1)8.0000000.000000……C(W5,J5)11.000000.000000X(W1,J1)1.0000008.000000X(W1,J2)0.0000006.000000X(W1,J3)0.00000010.00000X(W1,J4)0.0000009.000000X(W1,J5)0.00000012.00000X(W2,J1)0.0000009.000000X(W2,J2)0.00000012.00000X(W2,J3)0.0000007.000000X(W2,J4)0.00000011.00000X(W2,J5)1.0000009.000000X(W3,J1)0.0000007.000000X(W3,J2)0.0000004.000000X(W3,J3)1.0000003.000000X(W3,J4)0.0000005.000000X(W3,J5)0.0000008.000000X(W4,J1)0.0000009.000000X(W4,J2)1.0000005.000000X(W4,J3)0.0000008.000000X(W4,J4)0.00000011.00000X(W4,J5)0.0000008.000000X(W5,J1)0.0000004.000000X(W5,J2)0.0000006.000000X(W5,J3)0.0000007.000000X(W5,J4)1.0000005.000000X(W5,J5)0.00000011.00000RowSlackorSurplusDualPrice130.00000-1.000000……110.0000000.000000由上述结果知，问题的最优解为15442332511xxxxx，其余0ijx.模型说明：（1）另解：化为六个顶点的完全二分图6,6K上的最优匹配问题，利用匈牙利算法（1955，Kuhn）来解.（2）因MatLab要求决策变量须为单一下标，故不便于利用MatLab来解.（3）Lindo主要用来解线性规划问题，故建议使用Lingo来解数学规划.问题二：某公司拟将8个职员平均分配到4个办公室.根据直观评估，有些职员在一起时合作得很好，有些则不然.下表给出了8个职员两两之间的相容程度ijc（由于对称性，只给出了一半数据），数字越小代表相容得越好：1s2s3s4s5s6s7s8s1s－93421562s－1735213s－442924s－15525s－8766s－237s－48s－问：应如何分配这些职员，才能是他们相容得最好？建模：令否则，到同一个办公室，和分配职员,0,1jixij8,,1,ji则可建立如下数学规划模型：81,1,08,,1,1..minjixixtsxczijikijjkjiijij或由所给相容程度数据ijc的对称性，上述模型只针对表中对角线右上方的数据关系而建立；约束条件“8,,1,1ixikijjk或”保证了任一职员i仅被分配一次.模型求解：Lingo程序：model:sets:ren/1..8/;links(ren,ren)|&2#GT#&1:c,x;endsetsdata:c=9342156173521442921552876234;enddatamin=@sum(links:c*x);@for(ren(i):@sum(links(j,k)|j#EQ#i#or#k#EQ#i:x(j,k))=1);@for(links:@bin(x));end结果：Globaloptimalsolutionfound.Objectivevalue:6.000000Extendedsolversteps:0Totalsolveriterations:0VariableValueReducedCostC(1,2)9.0000000.000000……C(7,8)4.0000000.000000X(1,2)0.0000009.000000X(1,3)0.0000003.000000X(1,4)0.0000004.000000X(1,5)0.0000002.000000X(1,6)1.0000001.000000X(1,7)0.0000005.000000X(1,8)0.0000006.000000X(2,3)0.0000001.000000X(2,4)0.0000007.000000X(2,5)0.0000003.000000X(2,6)0.0000005.000000X(2,7)1.0000002.000000X(2,8)0.0000001.000000X(3,4)0.0000004.000000X(3,5)0.0000004.000000X(3,6)0.0000002.000000X(3,7)0.0000009.000000X(3,8)1.0000002.000000X(4,5)1.0000001.000000X(4,6)0.0000005.000000X(4,7)0.0000005.000000X(4,8)0.0000002.000000X(5,6)0.0000008.000000X(5,7)0.0000007.000000X(5,8)0.0000006.000000X(6,7)0.0000002.000000X(6,8)0.0000003.000000X(7,8)0.0000004.000000RowSlackorSurplusDualPrice16.000000-1.000000……90.0000000.000000或Lingo程序：model:min=9*x12+3*x13+4*x14+2*x15+x16+5*x17+6*x18+x23+7*x24+3*x25+5*x26+2*x27+x28+4*x34+4*x35+2*x36+9*x37+2*x38+x45+5*x46+5*x47+2*x48+8*x56+7*x57+6*x58+2*x67+3*x68+4*x78;x12+x13+x14+x15+x16+x17+x18=1;x12+x23+x24+x25+x26+x27+x28=1;x13+x23+x34+x35+x36+x37+x38=1;x14+x24+x34+x45+x46+x47+x48=1;x15+x25+x35+x45+x56+x57+x58=1;x16+x26+x36+x46+x56+x67+x68=1;x17+x27+x37+x47+x57+x67+x78=1;x18+x28+x38+x48+x58+x68+x78=1;@bin(x12);@bin(x13);@bin(x14);@bin(x15);@bin(x16);@bin(x17);@bin(x18);@bin(x23);@bi