lingo指派问题.docx
- 文档编号:15297286
- 上传时间:2023-07-03
- 格式:DOCX
- 页数:19
- 大小:39.74KB
lingo指派问题.docx
《lingo指派问题.docx》由会员分享,可在线阅读,更多相关《lingo指派问题.docx(19页珍藏版)》请在冰点文库上搜索。
lingo指派问题
Lingo作业题
1、指派问题
设有n个人,计划作n项工作,其中
表示第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项工作的指派最优问题,从而使题目中的
收益等达到所需要的目的。
在题目中曾提到:
每个人完成一项工作。
其意思就是每人只能做一项工作且每项工作只能做一人做。
二、符号说明
此题属于最优指派问题,引入如下变量:
题目中说:
表示第i个人做第j项工作的收益。
例如
则表示第5个人做第6项工作。
即
s.t.:
,j=1,2,3,···,6
,i=1,2,3,···,6
,i,j=1,2,3,···,6
此题需要求出最大值最优(最大值),即需要使用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输出(结果)框:
Globaloptimalsolutionfound.
Objectivevalue:
142.0000
Extendedsolversteps:
0
Totalsolveriterations:
0
VariableValueReducedCost
C111.000000-20.00000
C120.000000-15.00000
C130.000000-16.00000
C140.000000-5.000000
C150.000000-4.000000
C160.000000-7.000000
C210.000000-17.00000
C220.000000-15.00000
C231.000000-33.00000
C240.000000-12.00000
C250.000000-8.000000
C260.000000-6.000000
C310.000000-9.000000
C320.000000-12.00000
C330.000000-18.00000
C340.000000-16.00000
C351.000000-30.00000
C360.000000-13.00000
C410.000000-12.00000
C420.000000-8.000000
C430.000000-11.00000
C441.000000-27.00000
C450.000000-19.00000
C460.000000-14.00000
C510.0000000.000000
C520.000000-7.000000
C530.000000-10.00000
C540.000000-21.00000
C550.000000-10.00000
C561.000000-32.00000
C610.0000000.000000
C621.0000000.000000
C630.0000000.000000
C640.000000-6.000000
C650.000000-11.00000
C660.000000-13.00000
RowSlackorSurplusDualPrice
1142.00001.000000
20.0000000.000000
30.0000000.000000
40.0000000.000000
50.0000000.000000
60.0000000.000000
70.0000000.000000
80.0000000.000000
90.0000000.000000
100.0000000.000000
110.0000000.000000
120.0000000.000000
130.0000000.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=201516547,
1715331286,
91218163013,
12811271914,
0710211032,
00061113;
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输出(结果)框
Globaloptimalsolutionfound.
Objectivevalue:
142.0000
Extendedsolversteps:
0
Totalsolveriterations:
0
VariableValueReducedCost
A(A1)1.0000000.000000
A(A2)1.0000000.000000
A(A3)1.0000000.000000
A(A4)1.0000000.000000
A(A5)1.0000000.000000
A(A6)1.0000000.000000
B(B1)1.0000000.000000
B(B2)1.0000000.000000
B(B3)1.0000000.000000
B(B4)1.0000000.000000
B(B5)1.0000000.000000
B(B6)1.0000000.000000
XY(A1,B1)20.000000.000000
XY(A1,B2)15.000000.000000
XY(A1,B3)16.000000.000000
XY(A1,B4)5.0000000.000000
XY(A1,B5)4.0000000.000000
XY(A1,B6)7.0000000.000000
XY(A2,B1)17.000000.000000
XY(A2,B2)15.000000.000000
XY(A2,B3)33.000000.000000
XY(A2,B4)12.000000.000000
XY(A2,B5)8.0000000.000000
XY(A2,B6)6.0000000.000000
XY(A3,B1)9.0000000.000000
XY(A3,B2)12.000000.000000
XY(A3,B3)18.000000.000000
XY(A3,B4)16.000000.000000
XY(A3,B5)30.000000.000000
XY(A3,B6)13.000000.000000
XY(A4,B1)12.000000.000000
XY(A4,B2)8.0000000.000000
XY(A4,B3)11.000000.000000
XY(A4,B4)27.000000.000000
XY(A4,B5)19.000000.000000
XY(A4,B6)14.000000.000000
XY(A5,B1)0.0000000.000000
XY(A5,B2)7.0000000.000000
XY(A5,B3)10.000000.000000
XY(A5,B4)21.000000.000000
XY(A5,B5)10.000000.000000
XY(A5,B6)32.000000.000000
XY(A6,B1)0.0000000.000000
XY(A6,B2)0.0000000.000000
XY(A6,B3)0.0000000.000000
XY(A6,B4)6.0000000.000000
XY(A6,B5)11.000000.000000
XY(A6,B6)13.000000.000000
X(A1,B1)1.000000-20.00000
X(A1,B2)0.000000-15.00000
X(A1,B3)0.000000-16.00000
X(A1,B4)0.000000-5.000000
X(A1,B5)0.000000-4.000000
X(A1,B6)0.000000-7.000000
X(A2,B1)0.000000-17.00000
X(A2,B2)0.000000-15.00000
X(A2,B3)1.000000-33.00000
X(A2,B4)0.000000-12.00000
X(A2,B5)0.000000-8.000000
X(A2,B6)0.000000-6.000000
X(A3,B1)0.000000-9.000000
X(A3,B2)0.000000-12.00000
X(A3,B3)0.000000-18.00000
X(A3,B4)0.000000-16.00000
X(A3,B5)1.000000-30.00000
X(A3,B6)0.000000-13.00000
X(A4,B1)0.000000-12.00000
X(A4,B2)0.000000-8.000000
X(A4,B3)0.000000-11.00000
X(A4,B4)1.000000-27.00000
X(A4,B5)0.000000-19.00000
X(A4,B6)0.000000-14.00000
X(A5,B1)0.0000000.000000
X(A5,B2)0.000000-7.000000
X(A5,B3)0.000000-10.00000
X(A5,B4)0.000000-21.00000
X(A5,B5)0.000000-10.00000
X(A5,B6)1.000000-32.00000
X(A6,B1)0.0000000.000000
X(A6,B2)1.0000000.000000
X(A6,B3)0.0000000.000000
X(A6,B4)0.000000-6.000000
X(A6,B5)0.000000-11.00000
X(A6,B6)0.000000-13.00000
RowSlackorSurplusDualPrice
1142.00001.000000
20.0000000.000000
30.0000000.000000
40.0000000.000000
50.0000000.000000
60.0000000.000000
70.0000000.000000
80.0000000.000000
90.0000000.000000
100.0000000.000000
110.0000000.000000
120.0000000.000000
130.0000000.000000
五、模型结果
通过以上的应用Lingo模型求解,得出结论:
第1项工作由第1个人来完成。
第2项工作由第3个人来完成。
第3项工作由第5个人来完成。
第4项工作由第4个人来完成。
第5项工作由第6个人来完成。
第6项工作由第2个人来完成。
2、钢管下料问题
某钢管零售商从钢管厂进货,将钢管按照顾客的要求切割后售出,从钢管厂进货时得到的钢管都是19m.
(1)现有一客户需要50根4m、20根6m和15根8m的钢管,应如何下料最节省?
(2)零售商如果采用的不同切割模式太多,将会导致生产过程的复杂化,从而增加生产和管理成本,所以该零售商规定采用的不同切割模式不能超过3种。
此外该客户需要
(1)中的三种钢管外,还需要10根5m的钢管,应如何下料最省?
解:
(1)
一、问题分析
根据第二题第一问的题意我们可以知道,此题的最终目标是让我们建立一种数学模型来解决这个实际生活中的问题。
本题中,因为客户需要4m、6m、8m的钢管,故将19m分为如下:
只切一种钢管:
1)切4m钢管4根,余料为3m
2)切6m钢管3根,余料为1m
3)切8m钢管2根,余料为3m
同时切多种钢管:
4)同时分别切4m和6m钢管3根和1根,此时余料为1m
5)同时分别切4m和8m钢管2根和1根,此时余料为3m
6)同时分别切4m、6m和8m钢管各1根,此时余料为1m
7)同时分别切4m和6m钢管1根和2根,此时余料为3m
题目中所问:
应如何下料最节省,应有两种讨论方法:
一,切下来的钢管根数最少,二,切下来的钢管余料最少。
下面分别用
和
来讨论之。
此题属于下料最省问题,与常见的线性问题极为类似。
因此,使用Lingo软件。
二、符号说明
表示上述七种情况中第i种情况切钢管的根数
三、建立模型
:
切下来的钢管根数最少
Minz=
s.t.:
:
切下来的钢管余料最少
Minz=
s.t.:
四、模型求解
:
切下来的钢管根数最少
Lingo输入框:
min=x1+x2+x3+x4+x5+x6+x7;
4*x1+3*x4+2*x5+x6+x7>=50;
3*x2+x4+x6+2*x7>=20;
2*x3+x5+x6>=15;
Lingo输出(结果)框:
Globaloptimalsolutionfound.
Objectivevalue:
25.00000
Totalsolveriterations:
4
VariableValueReducedCost
X10.0000000.000000
X20.0000000.2500000
X35.0000000.000000
X415.000000.000000
X50.0000000.000000
X65.0000000.000000
X70.0000000.2500000
RowSlackorSurplusDualPrice
125.00000-1.000000
20.000000-0.2500000
30.000000-0.2500000
40.000000-0.5000000
:
切下来的钢管余料最少
Lingo输入框:
min=3*x1+x2+3*x3+x4+3*x5+x6+3*x7;
4*x1+3*x4+2*x5+x6+x7>=50;
3*x2+x4+x6+2*x7>=20;
2*x3+x5+x6>=15;
@gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(x6);@gin(x7);
Lingo输出(结果)框:
Globaloptimalsolutionfound.
Objectivevalue:
27.00000
Extendedsolversteps:
0
Totalsolveriterations:
5
VariableValueReducedCost
X10.0000003.000000
X20.0000001.000000
X30.0000003.000000
X412.000001.000000
X50.0000003.000000
X615.000001.000000
X70.0000003.000000
RowSlackorSurplusDualPrice
127.00000-1.000000
21.0000000.000000
37.0000000.000000
40.0000000.000000
五、模型结果
:
切下来的钢管根数最少
根据lingo输出语句转化成简单语句得:
根据情况3取5根钢管,根据情况4取15根钢管,根据情况6取5根钢管。
总计取25根钢管。
余料为35m。
:
切下来的钢管余料最少
根据lingo输出语句转化成简单语句得:
根据情况4取12根钢管,根据情况6取15根钢管。
总计取27根钢管。
余料为27m。
经过二者比较,选择“
:
切下来的钢管根数最少”。
(2)
一、问题分析
根据第二题第二问的题意我们可以知道,此题的最终目标是让我们建立一种数学模型来解决这个实际生活中的问题。
通过第一问我们了解到,切钢管的余料不能大于4m,即1m、2m、3m都可以。
故每根钢管的长度不能大于19m(题目要求,同时也不能少于16m(前面提到)。
而其目中提到:
采用的不同切割模式不能超过3种,故选择与第一问不同的变量。
此题属于下料最省问题,与常见的线性问题极为类似。
因此,使用Lingo软件。
由于题中所叙述的“需要
(1)中的三种钢管外,还需要10根5m的钢管”故此客户得到的钢管数不得少于26根(
25.789
26,此处取整,钢管数不能为分数),同时(做最简单的考虑),假设此客户只要50根4m的钢管,且每一根钢管能切4根4m的,则12.5次能切完,取整,为13根;同理。
其他情况也一样,只生产5m、6m的钢管,需要10根;只生产8m的管需要8根8m的钢管。
根据以上叙述,应满足一个最基本的条件即:
。
2、符号说明
表示第i种情况切钢管的根数,与第一问不同的是i的取值范围为1,2,3。
由于列举法较烦,我们采用如下方法:
设切割4m,5m,6m,8m的钢管数为
。
3、建立模型
Minz=
S.t.:
4、模型求解
Lingo输入框:
min=x1+x2+x3;
r11*x1+r12*x2+r13*x3>=50;
r21*x1+r22*x2+r23*x3>=10;
r31*x1+r32*x2+r33*x3>=20;
r41*x1+r42*x2+r43*x3>=15;
4*r11+5*r21+6*r31+8*r41<=19;
4*r11+5*r21+6*r31+8*r41>=16;
4*r12+5*r22+6*r32+8*r42<=19;
4*r12+5*r22+6*r32+8*r42>=16;
4*r13+5*r23+6*r33+8*r43<=19;
4*r13+5*r23+6*r33+8*r43>=16;
@gin(x1);@gin(x2);@gin(x3);
@gin(r11);@gin(r12);@gin(r13);
@gin(r21);@gin(r22);@gin(r23);
@gin(r31);@gin(r32);@gin(r33);
@gin(r41);@gin(r42);@gin(r43);
x1+x2+x3>=26;
x1+x2+x3<=31;
Lingo输出(结果)框:
Localoptimalsolutionfound.
Object
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- lingo 指派 问题