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

指派问题（assignment problem）问题一：今分派个工人去从事项工作. 工人从事工作的工作效率为. 试求一个分派方案，使每个工人都从事一项工作，每项工作都由一个工人承担，且总工作效率最大.建模：令则可建立如下数学规划模型：算例1 利用LINGO软件求解如下指派问题：，.模型求解：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注：程序中并没限制是0-1变量，但由其余约束条件足以保证返回的结果中变量的值为0、1.结果：Global optimal solution found.Objective value: 34.00000Extended solver steps: 0Total solver iterations: 0 Variable Value Reduced Cost C( W1, J1) 4.000000 0.000000 C( W5, J5) 6.000000 0.000000 X( W1, J1) 0.000000 4.000000 X( W1, J2) 0.000000 8.000000 X( W1, J3) 1.000000 7.000000 X( W1, J4) 0.000000 15.00000 X( W1, J5) 0.000000 12.00000 X( W2, J1) 0.000000 7.000000 X( W2, J2) 1.000000 9.000000 X( W2, J3) 0.000000 17.00000 X( W2, J4) 0.000000 14.00000 X( W2, J5) 0.000000 10.00000 X( W3, J1) 1.000000 6.000000 X( W3, J2) 0.000000 9.000000 X( W3, J3) 0.000000 12.00000 X( W3, J4) 0.000000 8.000000 X( W3, J5) 0.000000 7.000000 X( W4, J1) 0.000000 6.000000 X( W4, J2) 0.000000 7.000000 X( W4, J3) 0.000000 14.00000 X( W4, J4) 1.000000 6.000000 X( W4, J5) 0.000000 10.00000 X( W5, J1) 0.000000 6.000000 X( W5, J2) 0.000000 9.000000 X( W5, J3) 0.000000 12.00000 X( W5, J4) 0.000000 10.00000 X( W5, J5) 1.000000 6.000000算例2今分派5个工人去从事5项工作. 工人从事工作的时间见下表：8610912912711974358958118467511试求一个分派方案，使每个工人都从事一项工作，每项工作都由一个工人承担，且总工作时间最少.建模：令，则可建立如下0-1规划模型：模型求解：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结果： Global optimal solution found. Objective value: 30.00000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost C( W1, J1) 8.000000 0.000000 C( W5, J5) 11.00000 0.000000 X( W1, J1) 1.000000 8.000000 X( W1, J2) 0.000000 6.000000 X( W1, J3) 0.000000 10.00000 X( W1, J4) 0.000000 9.000000 X( W1, J5) 0.000000 12.00000 X( W2, J1) 0.000000 9.000000 X( W2, J2) 0.000000 12.00000 X( W2, J3) 0.000000 7.000000 X( W2, J4) 0.000000 11.00000 X( W2, J5) 1.000000 9.000000 X( W3, J1) 0.000000 7.000000 X( W3, J2) 0.000000 4.000000 X( W3, J3) 1.000000 3.000000 X( W3, J4) 0.000000 5.000000 X( W3, J5) 0.000000 8.000000 X( W4, J1) 0.000000 9.000000 X( W4, J2) 1.000000 5.000000 X( W4, J3) 0.000000 8.000000 X( W4, J4) 0.000000 11.00000 X( W4, J5) 0.000000 8.000000 X( W5, J1) 0.000000 4.000000 X( W5, J2) 0.000000 6.000000 X( W5, J3) 0.000000 7.000000 X( W5, J4) 1.000000 5.000000 X( W5, J5) 0.000000 11.00000 Row Slack or Surplus Dual Price 1 30.00000 -1.000000 11 0.000000 0.000000由上述结果知，问题的最优解为，其余.模型说明：（1）另解：化为六个顶点的完全二分图上的最优匹配问题，利用匈牙利算法（1955，Kuhn）来解.（2）因MatLab要求决策变量须为单一下标，故不便于利用MatLab来解.（3）Lindo主要用来解线性规划问题，故建议使用Lingo来解数学规划.问题二：某公司拟将8个职员平均分配到4个办公室.根据直观评估，有些职员在一起时合作得很好，有些则不然.下表给出了8个职员两两之间的相容程度（由于对称性，只给出了一半数据），数字越小代表相容得越好：9342156173521442921552876234问：应如何分配这些职员，才能是他们相容得最好？建模：令则可建立如下数学规划模型：由所给相容程度数据的对称性，上述模型只针对表中对角线右上方的数据关系而建立；约束条件“”保证了任一职员仅被分配一次.模型求解：Lingo程序：model:sets:ren/1.8/;links(ren,ren)| &2 # GT # &1:c,x;endsetsdata:c=9 3 4 2 1 5 6 1 7 3 5 2 1 4 4 2 9 2 1 5 5 2 8 7 6 2 3 4;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结果：Global optimal solution found. Objective value: 6.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost C( 1, 2) 9.000000 0.000000 C( 7, 8) 4.000000 0.000000 X( 1, 2) 0.000000 9.000000 X( 1, 3) 0.000000 3.000000 X( 1, 4) 0.000000 4.000000 X( 1, 5) 0.000000 2.000000 X( 1, 6) 1.000000 1.000000 X( 1, 7) 0.000000 5.000000 X( 1, 8) 0.000000 6.000000 X( 2, 3) 0.000000 1.000000 X( 2, 4) 0.000000 7.000000 X( 2, 5) 0.000000 3.000000 X( 2, 6) 0.000000 5.000000 X( 2, 7) 1.000000 2.000000 X( 2, 8) 0.000000 1.000000 X( 3, 4) 0.000000 4.000000 X( 3, 5) 0.000000 4.000000 X( 3, 6) 0.000000 2.000000 X( 3, 7) 0.000000 9.000000 X( 3, 8) 1.000000 2.000000 X( 4, 5) 1.000000 1.000000 X( 4, 6) 0.000000 5.000000 X( 4, 7) 0.000000 5.000000 X( 4, 8) 0.000000 2.000000 X( 5, 6) 0.000000 8.000000 X( 5, 7) 0.000000 7.000000 X( 5, 8) 0.000000 6.000000 X( 6, 7) 0.000000 2.000000 X( 6, 8) 0.000000 3.000000 X( 7, 8) 0.000000 4.000000 Row Slack or Surplus Dual Price 1 6.000000 -1.000000 9 0.000000 0.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);bin(x24);bin(x25);bin(x26);bin(x27);bin(x28);bin(x34);bin(x35);bin(x36);bin(x37);bin(x38);bin(x45);bin(x46);bin(x47);bin(x48);bin(x56);bin(x57);bin(x58);bin(x67);bin(x68);bin(x78);end结果：Global optimal solution found.Objective value: 6.000000Objective bound: 6.000000Infeasibilities: 0.000000Extended solver steps: 0Total solver iterations: 0 Variable Value Reduced Cost X12 0.000000 9.000000 X13 0.000000 3.000000 X14 0.000000 4.000000 X15 0.000000 2.000000 X16 1.000000 1.000000 X17 0.000000 5.000000 X18 0.000000 6.000000 X23 0.000000 1.000000 X24 0.000000 7.000000 X25 0.000000 3.000000 X26 0.000000 5.000000 X27 1.000000 2.000000 X28 0.000000 1.000000 X34 0.000000 4.000000 X35 0.000000 4.000000 X36 0.000000 2.000000 X37 0.000000 9.000000 X38 1.000000 2.000000 X45 1.000000 1.000000 X46 0.000000 5.000000 X47 0.000000 5.000000 X48 0.000000 2.000000 X56 0.000000 8.000000 X57 0.000000 7.000000 X58 0.000000 6.000000 X67 0.000000 2.000000 X68 0.000000 3.000000 X78 0.000000 4.000000 Row Slack or Surplus Dual Price 1 6.000000 -1.000000 9 0.000000 0.000000问题三： （婚姻问题）某财主想把自己的三个女儿嫁出去。现恰有三位求婚者，他们为娶到愿意支付的财礼数由下面的矩阵给出：问：财主应该如何嫁女儿，才能获得最多的财礼？模型假设：一夫一妻制.模型建立：，则可建立如下模型：模型求解：Lingo程序model:sets:Chaser/Ch1.Ch3/;Women/W1.W3/;links(Chaser, Women):c,x;endsetsdata:c=3,5,26, 27,10,28, 1,4,7;enddatamax=sum(links:c*x);for(Chaser(i):sum(Women(j):x(i,j)=1);for(Women(j):sum(Chaser(i):x(i,j)=1);for(links:bin(x);end结果：Global optimal solution found.Objective value: 57.00000Objective bound: 57.00000Infeasibilities: 0.000000Extended solver steps: 0Total solver iterations: 0 Variable Value Reduced Cost C( CH1, P1) 3.000000 0.000000 C( CH1, P2) 5.000000 0.000000 C( CH1, P3) 26.00000 0.000000 C( CH2, P1) 27.00000 0.000000 C( CH2, P2) 10.00000 0.000000 C( CH2, P3) 28.00000 0.000000 C( CH3, P1) 1.000000 0.000000 C( CH3, P2) 4.000000 0.000000 C( CH3, P3) 7.000000 0.000000 X( CH1, P1) 0.000000 -3.000000 X( CH1, P2) 0.000000 -5.000000 X( CH1, P3) 1.000000 -26.00000 X( CH2, P1) 1.000000 -27.00000 X( CH2, P2) 0.000000 -10.00000 X( CH2, P3) 0.000000 -28.00000 X( CH3, P1) 0.000000 -1.000000 X( CH3, P2) 1.000000 -4.000000 X( CH3, P3) 0.000000 -7.000000 Row Slack or Surplus Dual Price 1 57.00000 1.000000 7 0.000000 0.000000或LINGO程序：model:max=3*x11+5*x12+26*x13+27*x21+10*x22+28*x23+x31+4*x32+7*x33;x11+x12+x13=1;x21+x22+x23=1;x31+x32+x33=1;x11+x21+x31=1;x12+x22+x32=1;x13+x23+x33=1;bin(x11);bin(x12);bin(x13);bin(x21);bin(x22);bin(x23);bin(x31);bin(x32);bin(x33);end结果：Global optimal solution found.Objective value: 57.00000Objective bound: 57.00000Infeasibilities: 0.000000Extended solver steps: 0Total solver iterations: 0 Variable Value Reduced Cost X11 0.000000 -3.000000 X12 0.000000 -5.000000 X13 1.000000 -26.00000 X21 1.000000 -27.00000 X22 0.000000 -10.00000 X23 0.000000 -28.00000 X31 0.000000 -1.000000 X32 1.000000 -4.000000 X33 0.000000 -7.000000 Row Slack or Surplus Dual Price 1 57.00000 1.000000 7 0.000000 0.000000或MatLab程序：c=-3;-5;-26;-27;-10;-28;-1;-4;-7;Aeq=1,1,1,0,0,0,0,0,0;0,0,0,1,1,1,0,0,0;0,0,0,0,0,0,1,1,1;1,0,0,1,0,0,1,0,0;0,1,0,0,1,0,0,1,0;0,0,1,0,0,1,0,0,1;beq=1;1;1;1;1;1;lb=0,0,0,0,0,0,0,0,0;x,fval=bintprog(c,Aeq,beq,lb,)结果： c=-3;-5;-26;-27;-10;-28;-1;-4;-7; Aeq=1,1,1,0,0,0,0,0,0;0,0,0,1,1,1,0,0,0;0,0,0,0,0,0,1,1,1;1,0,0,1,0,0,1,0,0;0,1,0,0,1,0,0,1,0;0,0,1,0,0,1,0,0,1; beq=1;1;1;1;1;1; lb=0,0,0,0,0,0,0,0,0; /好像没有然后把下面的lb去掉也行 x,fval=bintprog(c,Aeq,beq,lb,)Warning: The given starting point x0 is not binary integer feasible; it will be ignored. In bintprog at 271Optimization terminated.x = 0 0 1 1 0 0 0 1 0fval = -57注：求解线性规划问题的MATLAB程序为（1）是一般变量（linear integer）：x,fval=linprog(c,A,b,Aeq,beq,lb,ub)；（2）是0-1变量（Boolean integer）：x,fval=bintprog(c,A,b,Aeq,beq,lb,ub).问题四：人员调度问题某项工作一周七天中的每一天都需要有人值班，每天所需值班人员的最小数目分别为20、16、13、16、19、14、12；每一值班人员在一周中需连续值班5天.问：一周中应如何安排人员值班，才能合乎工作要求，且值班人员数目最少？模型建立：令一周中第天的值班人数为，则可建立如下模型min z=x1+x2+x3+x4+x5+x6+x7s.t.x4+x5+x6+x7+x1=20x5+x6+x7+x1+x2=16x6+x7+x1+x2+x3=13x7+x1+x2+x3+x4=16x1+x2+x3+x4+x5=19x2+x3+x4+x5+x6=14x3+x4+x5+x6+x7=12x1,x7=0,整数;Lingo程序：min=x1+x2+x3+x4+x5+x6+x7;x4+x5+x6+x7+x1=20;x5+x6+x7+x1+x2=16;x6+x7+x1+x2+x3=13;x7+x1+x2+x3+x4=16;x1+x2+x3+x4+x5=19;x2+x3+x4+x5+x6=14;x3+