运筹学整数规划例题

1、练习4.9 连续投资问题某公司现有资金10万元,拟在今后五年内考虑用于下列项目的投资:项目a:从第一年到第四年每年年初需要投资,并于次年收回本利115%,但要求第一年投资最低金额为4万元,第二.三.四年不限.项目b:第三年初需要投资,到第五年末能收回本利128%,但规定最低投资金额为3万元,最高金额为5万元.项目c:第二年初需要投资,到第五年末能收回本利140%,但规定其投资金额或为2万元,或为4万元,或为6万元,或为8万元.项目d:五年内每年年初都可购买公债,于当年末归还,并获利6%,此项目投资金额不限.试问该公司应图和确定这些项目的每年投资金额,使到第五年末拥有最大的资金收益.(1) 为项

2、目各年月初投入向量。(2) 为 i 种项目j年的月初的投入。(3) 向量c中的元素为i年末j种项目收回本例的百分比。(4) 矩阵a中元素为约束条件中每个变量的系数。(5) z为第5年末能拥有的资金本利最大总额。因此目标函数为束条件应是每年年初的投资额应等于该投资者年初所拥有的资金.第1年年初该投资者拥有10万元资金,故有.第2年年初该投资者手中拥有资金只有,故有.第3年年初该投资者拥有资金为从项目收回的本金: ,及从项目中第1年投资收回的本金: ,故有同理第4年、第5年有约束为,max=1.15*x4a+1.28*x3b+1.4*x2c+1.06*x5d; x1a+x1d=100000;-1.

3、06*x1d+x2a+x2c+x2d=0;-1.15*x1a-1.06*x2d+x3a+x3b+x3d=0;-1.15*x2a-1.06*x3d+x4a+x4d=0;-1.15*x3a-1.06*x4d+x5d=0;x2c=40000 ;x2c=60000;x2c=80000;x2c=20000; x3b=30000;x3b=0;x2a=0;x3a=0;x4a=0;x5a=0;x1b=0;x2b=0;x3b=0;x4b=0;x5b=0;x1c=0;x2c=0;x3c=0;x4c=0;x5c=0;x1d=0;x2d=0;x3d=0;x4d=0;x5d=0; variable value redu

4、ced cost x4a 22900.00 0.000000 x3b 50000.00 0.000000 x2c 40000.00 0.000000 x5d 0.000000 0.000000 x1a 62264.15 0.000000 x1d 37735.85 0.000000 x2a 0.000000 0.000000 x2d 0.000000 0.3036000e-01 x3a 0.000000 0.000000 x3d 21603.77 0.000000 x4d 0.000000 0.2640000e-01 x5a 0.000000 0.000000 x1b 0.000000 0.00

5、0000 x2b 0.000000 0.000000 x4b 0.000000 0.000000 x5b 0.000000 0.000000 x1c 0.000000 0.000000 x3c 0.000000 0.000000 x4c 0.000000 0.000000 x5c 0.000000 0.000000 row slack or surplus dual price 1 80000.00 1.000000 2 0.000000 1.401850 3 0.000000 1.322500 4 0.000000 1.219000 5 0.000000 1.150000 6 0.00000

6、0 1.060000 7 0.000000 -0.8388608e+18 8 -20000.00 -0.1280000e+10 9 -40000.00 -0.1280000e+10 10 -20000.00 0.1280000e+10 11 20000.00 0.000000 12 0.000000 0.6100000e-01 13 62264.15 0.000000 14 0.000000 0.000000 15 0.000000 0.000000 16 22900.00 0.000000 17 0.000000 0.000000 18 0.000000 0.000000 19 0.0000

7、00 0.000000 20 50000.00 0.000000 21 0.000000 0.000000 22 0.000000 0.000000 23 0.000000 0.000000 24 40000.00 0.000000 25 0.000000 0.000000 26 0.000000 0.000000 27 0.000000 0.000000 28 37735.85 0.000000 29 0.000000 0.000000 30 21603.77 0.000000 31 0.000000 0.000000 32 0.000000 0.0000004.10某城市的消防总站将全市划

8、分为11个防火区，现有4个消防站，图4-11给出的是该城市各防火区域和防火站的示意图，其中1,2,3,4，表示消防站1，2，11表示防火区域，根据历史资料证实，各消防站可在事先规定允许的时间内对所负责的区域内的火灾予以扑灭，图中没有虚线连接的就表示不负责，现在总部提出：能否减少消防站的数目，仍能保证负责各地区的防火任务？如果可以的话，应该关闭哪个？练习4.10某城市的消防站总部将全市划分为11个防火区，现有四的。解：根据题意，用xi表示第i个消防站的关系的打开关闭情况x=1； 第i个消防站不关闭 0； 第i个消防站关闭用y代表第i个消防站到第j个防火区域的到达情况，0表示不可达，1表示可达，y

9、=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;则问题可归结为01整数规划模型。min z=sum x（i）;st x（i）*y（i，j）=1；j=1,2,3.11 x（i）=1;);for(n_j(j):sum(n_i(i):x(i)=0;);end运行结果：global optimal solution found. objective value: 3.000000 extended solver steps: 0 total solver iteration

10、s: 0 variable value reduced cost x( 1) 1.000000 1.000000 x( 2) 0.000000 1.000000 x( 3) 1.000000 1.000000 x( 4) 1.000000 1.000000 y( 1, 1) 1.000000 0.000000 y( 1, 2) 1.000000 0.000000 y( 1, 3) 1.000000 0.000000 y( 1, 4) 1.000000 0.000000 y( 1, 5) 0.000000 0.000000 y( 1, 6) 1.000000 0.000000 y( 1, 7)

11、1.000000 0.000000 y( 1, 8) 1.000000 0.000000 y( 1, 9) 0.000000 0.000000 y( 1, 10) 0.000000 0.000000 y( 1, 11) 0.000000 0.000000 y( 2, 1) 1.000000 0.000000 y( 2, 2) 1.000000 0.000000 y( 2, 3) 0.000000 0.000000 y( 2, 4) 1.000000 0.000000 y( 2, 5) 0.000000 0.000000 y( 2, 6) 0.000000 0.000000 y( 2, 7) 0

12、.000000 0.000000 y( 2, 8) 1.000000 0.000000 y( 2, 9) 1.000000 0.000000 y( 2, 10) 0.000000 0.000000 y( 2, 11) 0.000000 0.000000 y( 3, 1) 0.000000 0.000000 y( 3, 2) 0.000000 0.000000 y( 3, 3) 0.000000 0.000000 y( 3, 4) 1.000000 0.000000 y( 3, 5) 1.000000 0.000000 y( 3, 6) 1.000000 0.000000 y( 3, 7) 0.

13、000000 0.000000 y( 3, 8) 0.000000 0.000000 y( 3, 9) 0.000000 0.000000 y( 3, 10) 0.000000 0.000000 y( 3, 11) 1.000000 0.000000 y( 4, 1) 0.000000 0.000000 y( 4, 2) 0.000000 0.000000 y( 4, 3) 0.000000 0.000000 y( 4, 4) 0.000000 0.000000 y( 4, 5) 0.000000 0.000000 y( 4, 6) 1.000000 0.000000 y( 4, 7) 1.0

14、00000 0.000000 y( 4, 8) 1.000000 0.000000 y( 4, 9) 1.000000 0.000000 y( 4, 10) 1.000000 0.000000 y( 4, 11) 1.000000 0.000000 row slack or surplus dual price obj 3.000000 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 1.000000 0.000000 6 0.000000 0.000000 7 2.000000 0.000000

15、8 1.000000 0.000000 9 1.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000 12 1.000000 0.000000 13 0.000000 0.000000 14 0.000000 0.000000 15 0.000000 0.000000 16 0.000000 0.000000 17 0.000000 0.000000 18 0.000000 0.000000 19 0.000000 0.000000 20 0.000000 0.000000 21 0.000000 0.000000 22 0.000

16、000 0.000000 23 0.000000 0.000000 24 1.000000 0.000000 25 0.000000 0.000000 26 1.000000 0.000000 27 1.000000 0.000000结果如下： x= x=x=1，x=0；即应关闭2号消防站。121234910117564834.11某航空公司主要经营a，b，c三个大城市之间的航线飞行，这些航线每天航班起飞与到达时间如表4-16所示，假如飞机在机场停留损失费用大致与停留时间的平方成正比，又知每架飞机从降落到下一班起飞至少需要2h的准备时间，试分析确定一个使总的停留损失费用最小的飞行方案。航班号出

17、发城市起飞时间到达城市到达时间101a9：00b2:00（次日）102a10：00b12:00103a15：00b13:00104a20：00c18:00105a22：00c24:00106b4：00a7:00107b11：00a14:00108b15：00a18:00109c7：00a11:00110c15：00a19:00111b13：00c18:00112b18：00c23:00113c15：00b20:00114c7：00b12:00解：设飞机停留一小时的损失费为a元，则停留两小时损失为4a元，停留3小时的损失费用为9a元，依次类推，对a.、b、c三个城市建立的指派问题效率矩阵分别如下

18、表： 城市a起飞到达 101 102103104105 106 4a 9a 64a169a225a 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 102103104105 106 0 1 000 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 102103104105 106 256a 529a 9a625a36a 107 225a 484a 4a 576a 25a 108 100a 289a 441a 361a 576a 109 64a 225a 361a 289a 484a 110 256a 529a