发布时间 : 星期二 文章lingo 指派问题更新完毕开始阅读ecfe8221a5e9856a561260cd
Lingo作业题
1、指派问题
设有n个人, 计划作n项工作, 其中cij表示第i个人做第j项工作的收益,求一种指派方式，使得每个人完成一项工作，使总收益最大.现6个人做6项工作的最优指派问题，其收益矩阵如表所示，请给出合理安排. 人 工作1 工作2 工作3 工作4 工作5 工作6 1 20 15 16 5 4 7 2 17 15 33 12 8 6 3 9 12 18 16 30 13 4 12 8 11 27 19 14 5 0 7 10 21 10 32 6 0 0 0 6 11 13 解： 一、问题分析
根据第一题的题意我们可以知道，此题的最终目标是让我们建立一种数学模型来解决这个实际生活中的问题，此题意简而言之就是为了解决6个人做6项工作的指派最优问题，从而使题目中的Cij收益等达到所需要的目的。在题目中曾提到：每个人完成一项工作。其意思就是每人只能做一项工作且每项工作只能做一人做。
二、符号说明
此题属于最优指派问题，引入如下变量：
题目中说：Cij表示第i个人做第j项工作的收益。例如C56则表示第5个人做第6项工作。
即maxz???xyijcij
i?1j?166s.t.：
?Ci?16ij···，6 ?1 ，j=1,2,3，
?Cj?16ij···，6 ?1 ，i=1,2,3，
···，6 Cij?0或1 ，i,j=1,2,3，
此题需要求出最大值最优（最大值），即需要使用max，表示最大。
在编程过程中“@bin（x）”是“限制x为0或1”。 三、建立模型
此题属于最优指派问题，与常见的线性问题极为类似。因此，使用Lingo
软件。
由于“每人只能做一项工作且每项工作只能做一人做”故采用0-1规划求得优。
四、模型求解
（一）常规程序求解 Lingo输入框：
max=20*c11+15*c12+16*c13+5*c14+4*c15+7*c16+ 17*c21+15*c22+33*c23+12*c24+8*c25+6*c26+ 9*c31+12*c32+18*c33+16*c34+30*c35+13*c36+ 12*c41+8*c42+11*c43+27*c44+19*c45+14*c46+ 0*c51+7*c52+10*c53+21*c54+10*c55+32*c56+ 0*c61+0*c62+0*c63+6*c64+11*c65+13*c66; c11+c12+c13+c14+c15+c16=1; c21+c22+c23+c24+c25+c26=1; c31+c32+c33+c34+c35+c36=1; c41+c42+c43+c44+c45+c46=1; c51+c52+c53+c54+c55+c56=1; c61+c62+c63+c64+c65+c66=1; c11+c21+c31+c41+c51+c61=1; c12+c22+c32+c42+c52+c62=1; c13+c23+c33+c43+c53+c63=1; c14+c24+c34+c44+c54+c64=1; c15+c25+c35+c45+c55+c65=1; c16+c26+c36+c46+c56+c66=1;
@bin(c11);@bin(c12);@bin(c13);@bin(c14);@bin(c15);@bin(c16); @bin(c21);@bin(c22);@bin(c23);@bin(c24);@bin(c25);@bin(c26); @bin(c31);@bin(c32);@bin(c33);@bin(c34);@bin(c35);@bin(c36); @bin(c41);@bin(c42);@bin(c43);@bin(c44);@bin(c45);@bin(c46); @bin(c51);@bin(c52);@bin(c53);@bin(c54);@bin(c55);@bin(c56); @bin(c61);@bin(c62);@bin(c63);@bin(c64);@bin(c65);@bin(c66);
Lingo输出（结果）框：
Global optimal solution found.
Objective value: 142.0000 Extended solver steps: 0 Total solver iterations: 0
Variable Value Reduced Cost C11 1.000000 -20.00000 C12 0.000000 -15.00000 C13 0.000000 -16.00000 C14 0.000000 -5.000000 C15 0.000000 -4.000000
C16 0.000000 -7.000000 C21 0.000000 -17.00000 C22 0.000000 -15.00000 C23 1.000000 -33.00000 C24 0.000000 -12.00000 C25 0.000000 -8.000000 C26 0.000000 -6.000000 C31 0.000000 -9.000000 C32 0.000000 -12.00000 C33 0.000000 -18.00000 C34 0.000000 -16.00000 C35 1.000000 -30.00000 C36 0.000000 -13.00000 C41 0.000000 -12.00000 C42 0.000000 -8.000000 C43 0.000000 -11.00000 C44 1.000000 -27.00000 C45 0.000000 -19.00000 C46 0.000000 -14.00000 C51 0.000000 0.000000 C52 0.000000 -7.000000 C53 0.000000 -10.00000 C54 0.000000 -21.00000 C55 0.000000 -10.00000 C56 1.000000 -32.00000 C61 0.000000 0.000000 C62 1.000000 0.000000 C63 0.000000 0.000000 C64 0.000000 -6.000000 C65 0.000000 -11.00000 C66 0.000000 -13.00000
Row Slack or Surplus Dual Price 1 142.0000 1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 0.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000
12 0.000000 0.000000 13 0.000000 0.000000
（二）循环语句求解 Lingo输入框： model: sets:
gz/A1..A6/:a; ry/B1..B6/:b; yw(gz,ry):xy,x; endsets data:
a=1,1,1,1,1,1; b=1,1,1,1,1,1; xy=20 15 16 5 4 7, 17 15 33 12 8 6, 9 12 18 16 30 13, 12 8 11 27 19 14, 0 7 10 21 10 32, 0 0 0 6 11 13; enddata
max=@sum(yw:xy*x);
@for(gz(i):@sum(ry(j):x(i,j))=1); @for(ry(j):@sum(gz(i):x(i,j))=1); @for(yw(i,j):@bin(x(i,j))); End
Lingo输出（结果）框
Global optimal solution found.
Objective value: 142.0000 Extended solver steps: 0 Total solver iterations: 0
Variable Value Reduced Cost A( A1) 1.000000 0.000000 A( A2) 1.000000 0.000000 A( A3) 1.000000 0.000000 A( A4) 1.000000 0.000000 A( A5) 1.000000 0.000000 A( A6) 1.000000 0.000000 B( B1) 1.000000 0.000000 B( B2) 1.000000 0.000000