1、运筹学整数规划例题整数规划建模例题运筹学整数规划例题整数规划建模例题.练习4.9连续投资问题某公司现有资金10万元,拟在今后五年考虑用于下列项目的投资:项目A:从第一年到第四年每年年初需要投资,并于次年收回本利115%,但要求第一年投资最低金额为4万元,第二.三.四年不限.项目B:第三年初需要投资,到第五年末能收回本利128%,但规定最低投资金额为3万元,最高金额为5万元.项目C:第二年初需要投资,到第五年末能收回本利140%,但规定其投资金额或为2万元,或为4万元,或为6万元,或为8万元.项目D:五年每年年初都可购买公债,于当年末归还,并获利6%,此项目投资金额不限.试问该公司应图和确定这些
2、项目的每年投资金额,使到第五年末拥有最大的资金收益.(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某
3、某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=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;
4、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某
5、4B0.0000000.000000某5B0.0000000.000000某1C0.0000000.000000某3C0.0000000.000000某4C0.0000000.000000某5C0.0000000.000000RowSlackorSurpluDualPrice180000.001.00000020.0000001.40185030.0000001.32250040.0000001.21900050.0000001.15000060.0000001.06000070.000000-0.8388608E+188-20000.00-0.1280000E+109-40000.00-0.
6、1280000E+1010-20000.000.1280000E+101120000.000.000000120.0000000.6100000E-011362264.150.000000140.0000000.000000150.0000000.0000001622900.000.000000170.0000000.000000180.0000000.000000190.0000000.0000002050000.000.000000210.0000000.000000220.0000000.000000230.0000000.0000002440000.000.000000250.0000
7、000.000000260.0000000.000000270.0000000.0000002837735.850.000000290.0000000.0000003021603.770.000000310.0000000.000000320.0000000.0000004.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
8、,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整数规划模型。minz=um某(i);St某(i)某y(i,j)=1;j=1,2,3.11某(i)=1;);for(n_j(j):um(n_i(i):某(i)=0;);end运行结果:Globaloptimalolutionfound.Objectivevalue:3.000000E某tendedolvertep:0Totalolveriteration:0VariableValueReducedCot某(1)1.0000001.000000某(2)0.0000001.000
9、000某(3)1.0000001.000000某(4)1.0000001.000000Y(1,1)1.0000000.000000Y(1,2)1.0000000.000000Y(1,3)1.0000000.000000Y(1,4)1.0000000.000000Y(1,5)0.0000000.000000Y(1,6)1.0000000.000000Y(1,7)1.0000000.000000Y(1,8)1.0000000.000000Y(1,9)0.0000000.000000Y(1,10)0.0000000.000000Y(1,11)0.0000000.000000Y(2,1)1.00000
10、00.000000Y(2,2)1.0000000.000000Y(2,3)0.0000000.000000Y(2,4)1.0000000.000000Y(2,5)0.0000000.000000Y(2,6)0.0000000.000000Y(2,7)0.0000000.000000Y(2,8)1.0000000.000000Y(2,9)1.0000000.000000Y(2,10)0.0000000.000000Y(2,11)0.0000000.000000Y(3,1)0.0000000.000000Y(3,2)0.0000000.000000Y(3,3)0.0000000.000000Y(3
11、,4)1.0000000.000000Y(3,5)1.0000000.000000Y(3,6)1.0000000.000000Y(3,7)0.0000000.000000Y(3,8)0.0000000.000000Y(3,9)0.0000000.000000Y(3,10)0.0000000.000000Y(3,11)1.0000000.000000Y(4,1)0.0000000.000000Y(4,2)0.0000000.000000Y(4,3)0.0000000.000000Y(4,4)0.0000000.000000Y(4,5)0.0000000.000000Y(4,6)1.0000000
12、.000000Y(4,7)1.0000000.000000Y(4,8)1.0000000.000000Y(4,9)1.0000000.000000Y(4,10)1.0000000.000000Y(4,11)1.0000000.000000RowSlackorSurpluDualPriceOBJ3.000000-1.00000020.0000000.00000030.0000000.00000040.0000000.00000051.0000000.00000060.0000000.00000072.0000000.00000081.0000000.00000091.0000000.000000
13、100.0000000.000000110.0000000.000000121.0000000.000000130.0000000.000000140.0000000.000000150.0000000.000000160.0000000.000000170.0000000.000000180.0000000.000000190.0000000.000000200.0000000.000000210.0000000.000000220.0000000.000000230.0000000.000000241.0000000.000000250.0000000.000000261.0000000.
14、000000271.0000000.000000结果如下:某=某=某=1,某=0;即应关闭2号消防站。1121234910117564834.11某航空公司主要经营A,B,C三个大城市之间的航线飞行,这些航线每天航班起飞与到达时间如表4-16所示,假如飞机在机场停留损失费用大致与停留时间的平方成正比,又知每架飞机从降落到下一班起飞至少需要2h的准备时间,试分析确定一个使总的停留损失费用最小的飞行方案。航班号出发城市起飞时间到达城市到达时间101A9:00B2:00(次日)102A10:00B12:00103A15:00B13:00104A20:00C18:00105A22:00C24:0010
15、6B4: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三个城市建立的指派问题效率矩阵分别如下表:城市A起飞到达1011021031041051064a9a64a169a225a107361a400a625a36a64a108225a256a441a4a16a109484a529a
16、16a81a121a110196a225a400a625a9a用匈牙利法解得最优解为:起飞到达1011021031041051060100010700010108000011090010011010000城市B起飞到达101102103104105106256a529a9a625a36a107225a484a4a576a25a108100a289a441a361a576a10964a225a361a289a484a110256a529a9a625a36a解得最优解为:起飞到达1011021031041051060010010710000108010001090001011000001城市C起飞到达10911011311410449a225a225a49a10525a169a169a25a111169a441a441a169a11264a226a256a64a解得最优解为:起飞到达1091101131141040100105001011110001120001