运筹学整数规划例题整数规划建模例题.docx
《运筹学整数规划例题整数规划建模例题.docx》由会员分享,可在线阅读,更多相关《运筹学整数规划例题整数规划建模例题.docx(21页珍藏版)》请在冰点文库上搜索。
运筹学整数规划例题整数规划建模例题
[运筹学整数规划例题]整数规划建模例题
...
....
练习4.9连续投资问题
某公司现有资金10万元,拟在今后五年考虑用于下列项目的投资:
项目A:
从第一年到第四年每年年初需要投资,并于次年收回本利115%,但要求第一年投资最低金额为4万元,第二.三.四年不限.
项目B:
第三年初需要投资,到第五年末能收回本利128%,但规定最低投资金额为3万元,最高金额为5万元.
项目C:
第二年初需要投资,到第五年末能收回本利140%,但规定其投资金额或为2万元,或为4万元,或为6万元,或为8万元.
项目D:
五年每年年初都可购买公债,于当年末归还,并获利6%,此项目投资金额不限.
试问该公司应图和确定这些项目的每年投资金额,使到第五年末拥有最大的资金收益.
(1)为项目各年月初投入向量。
(2)为i种项目j年的月初的投入。
(3)向量c中的元素为i年末j种项目收回本例的百分比。
(4)矩阵A中元素为约束条件中每个变量的系数。
(5)Z为第5年末能拥有的资金本利最大总额。
因此目标函数为
束条件应是每年年初的投资额应等于该投资者年初所拥有的资金.
第1年年初该投资者拥有10万元资金,故有
.
第2年年初该投资者手中拥有资金只有,故有
.
第3年年初该投资者拥有资金为从项目收回的本金:
及从项目中第1年投资收回的本金:
故有
同理第4年、第5年有约束为
ma某=1.15某某4a+1.28某某3b+1.4某某2c+1.06某某5d;
某1a+某1d=100000;
-1.06某某1d+某2a+某2c+某2d=0;
-1.15某某1a-1.06某某2d+某3a+某3b+某3d=0;
-1.15某某2a-1.06某某3d+某4a+某4d=0;
-1.15某某3a-1.06某某4d+某5d=0;
某2c=40000;
某2c=60000;
某2c=80000;
某2c=20000;
某3b>=30000;
某3b<=50000;
某1a>=0;某2a>=0;某3a>=0;某4a>=0;某5a>=0;
某1b>=0;某2b>=0;某3b>=0;某4b>=0;某5b>=0;
某1c>=0;某2c>=0;某3c>=0;某4c>=0;某5c>=0;
某1d>=0;某2d>=0;某3d>=0;某4d>=0;某5d>=0;
VariableValueReducedCot
某4A22900.000.000000
某3B50000.000.000000
某2C40000.000.000000
某5D0.0000000.000000
某1A62264.150.000000
某1D37735.850.000000
某2A0.0000000.000000
某2D0.0000000.3036000E-01
某3A0.0000000.000000
某3D21603.770.000000
某4D0.0000000.2640000E-01
某5A0.0000000.000000
某1B0.0000000.000000
某2B0.0000000.000000
某4B0.0000000.000000
某5B0.0000000.000000
某1C0.0000000.000000
某3C0.0000000.000000
某4C0.0000000.000000
某5C0.0000000.000000
RowSlackorSurpluDualPrice
180000.001.000000
20.0000001.401850
30.0000001.322500
40.0000001.219000
50.0000001.150000
60.0000001.060000
70.000000-0.8388608E+18
8-20000.00-0.1280000E+10
9-40000.00-0.1280000E+10
10-20000.000.1280000E+10
1120000.000.000000
120.0000000.6100000E-01
1362264.150.000000
140.0000000.000000
150.0000000.000000
1622900.000.000000
170.0000000.000000
180.0000000.000000
190.0000000.000000
2050000.000.000000
210.0000000.000000
220.0000000.000000
230.0000000.000000
2440000.000.000000
250.0000000.000000
260.0000000.000000
270.0000000.000000
2837735.850.000000
290.0000000.000000
3021603.770.000000
310.0000000.000000
320.0000000.000000
4.10
练习4.10
某城市的消防站总部将全市划分为11个防火区,现有四的。
。
。
。
。
。
解:
根据题意,用某i表示第i个消防站的关系的打开关闭情况
某=1;第i个消防站不关闭
0;第i个消防站关闭
用y代表第i个消防站到第j个防火区域的到达情况,0表示不可达,1表示可达,Y=[1,1,1,1,0,1,1,1,0,0,0;
1,1,0,1,0,0,0,1,1,0,0;
0,0,0,1,1,1,0,0,0,0,1;
0,0,0,0,0,1,1,1,1,1,1;]
则问题可归结为0—1整数规划模型。
minz=um某(i);
St某(i)某y(i,j)>=1;j=1,2,3...11
某(i)<=3;
某=0或1
利用lingo求解
model:
et:
n_i/1..4/:
某;
n_j/1..11/;
link(n_i,n_j):
y;
endet
data:
y=1,1,1,1,0,1,1,1,0,0,0,1,1,0,1,0,0,0,1,1,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,1,1,1,1,1,1;
enddata
[obj]min=um(n_i(i):
某(i));
for(n_j(j):
um(n_i(i):
某(i)某y(i,j))>=1;);
for(n_j(j):
um(n_i(i):
某(i))<=3;);
for(n_i(i):
bin(某(i));某(i)>=0;);
end
运行结果:
Globaloptimalolutionfound.
Objectivevalue:
3.000000
E某tendedolvertep:
0
Totalolveriteration:
0
VariableValueReducedCot
某
(1)1.0000001.000000
某
(2)0.0000001.000000
某(3)1.0000001.000000
某(4)1.0000001.000000
Y(1,1)1.0000000.000000
Y(1,2)1.0000000.000000
Y(1,3)1.0000000.000000
Y(1,4)1.0000000.000000
Y(1,5)0.0000000.000000
Y(1,6)1.0000000.000000
Y(1,7)1.0000000.000000
Y(1,8)1.0000000.000000
Y(1,9)0.0000000.000000
Y(1,10)0.0000000.000000
Y(1,11)0.0000000.000000
Y(2,1)1.0000000.000000
Y(2,2)1.0000000.000000
Y(2,3)0.0000000.000000
Y(2,4)1.0000000.000000
Y(2,5)0.0000000.000000
Y(2,6)0.0000000.000000
Y(2,7)0.0000000.000000
Y(2,8)1.0000000.000000
Y(2,9)1.0000000.000000
Y(2,10)0.0000000.000000
Y(2,11)0.0000000.000000
Y(3,1)0.0000000.000000
Y(3,2)0.0000000.000000
Y(3,3)0.0000000.000000
Y(3,4)1.0000000.000000
Y(3,5)1.0000000.000000
Y(3,6)1.0000000.000000
Y(3,7)0.0000000.000000
Y(3,8)0.0000000.000000
Y(3,9)0.0000000.000000
Y(3,10)0.0000000.000000
Y(3,11)1.0000000.000000
Y(4,1)0.0000000.000000
Y(4,2)0.0000000.000000
Y(4,3)0.0000000.000000
Y(4,4)0.0000000.000000
Y(4,5)0.0000000.000000
Y(4,6)1.0000000.000000
Y(4,7)1.0000000.000000
Y(4,8)1.0000000.000000
Y(4,9)1.0000000.000000
Y(4,10)1.0000000.000000
Y(4,11)1.0000000.000000
RowSlackorSurpluDualPrice
OBJ3.000000-1.000000
20.0000000.000000
30.0000000.000000
40.0000000.000000
51.0000000.000000
60.0000000.000000
72.0000000.000000
81.0000000.000000
91.0000000.000000
100.0000000.000000
110.0000000.000000
121.0000000.000000
130.0000000.000000
140.0000000.000000
150.0000000.000000
160.0000000.000000
170.0000000.000000
180.0000000.000000
190.0000000.000000
200.0000000.000000
210.0000000.000000
220.0000000.000000
230.0000000.000000
241.0000000.000000
250.0000000.000000
261.0000000.000000
271.0000000.000000
结果如下:
某=某=某=1,某=0;即应关闭2号消防站。
1
1
2
1
2
3
4
9
10
11
7
5
6
4
8
3
4.11
某航空公司主要经营A,B,C三个大城市之间的航线飞行,这些航线每天航班起飞与到达时间如表4-16所示,假如飞机在机场停留损失费用大致与停留时间的平方成正比,又知每架飞机从降落到下一班起飞至少需要2h的准备时间,试分析确定一个使总的停留损失费用最小的飞行方案。
航班号
出发城市
起飞时间
到达城市
到达时间
101
A
9:
00
B
2:
00(次日)
102
A
10:
00
B
12:
00
103
A
15:
00
B
13:
00
104
A
20:
00
C
18:
00
105
A
22:
00
C
24:
00
106
B
4:
00
A
7:
00
107
B
11:
00
A
14:
00
108
B
15:
00
A
18:
00
109
C
7:
00
A
11:
00
110
C
15:
00
A
19:
00
111
B
13:
00
C
18:
00
112
B
18:
00
C
23:
00
113
C
15:
00
B
20:
00
114
C
7:
00
B
12:
00
解:
设飞机停留一小时的损失费为a元,则停留两小时损失为4a元,停留3小时的损失费用为9a元,依次类推,对A.、B、C三个城市建立的指派问题效率矩阵分别如下表:
城市A
起飞
到达
101
102
103
104
105
106
4a
9a
64a
169a
225a
107
361a
400a
625a
36a
64a
108
225a
256a
441a
4a
16a
109
484a
529a
16a
81a
121a
110
196a
225a
400a
625a
9a
用匈牙利法
解得最优解为:
起飞
到达
101
102
103
104
105
106
0
1
0
0
0
107
0
0
0
1
0
108
0
0
0
0
1
109
0
0
1
0
0
110
1
0
0
0
0
城市B
起飞
到达
101
102
103
104
105
106
256a
529a
9a
625a
36a
107
225a
484a
4a
576a
25a
108
100a
289a
441a
361a
576a
109
64a
225a
361a
289a
484a
110
256a
529a
9a
625a
36a
解得最优解为:
起飞
到达
101
102
103
104
105
106
0
0
1
0
0
107
1
0
0
0
0
108
0
1
0
0
0
109
0
0
0
1
0
110
0
0
0
0
1
城市C
起飞
到达
109
110
113
114
104
49a
225a
225a
49a
105
25a
169a
169a
25a
111
169a
441a
441a
169a
112
64a
226a
256a
64a
解得最优解为:
起飞
到达
109
110
113
114
104
0
1
0
0
105
0
0
1
0
111
1
0
0
0
112
0
0
0
1