运筹学实验报告五最优化问题.docx
2018-2019学年第一学期运筹学实验报告（五）班级：交通运输171 学号：1000000000 姓名： * 日期： 2018. 12.6Y(1,1)0.0000005.000000Y(lz2)0.0000005.000000Y(1/3)0.0000005.000000Y(1,4)0.0000005.000000Y(1/5)0.0000005.000000Y(2,1)1.0000003.000000Y(2,2)0.0000003.000000Y(2,3)0.0000003.000000Y(2,4)0.0000003.000000Y(2,5)0.0000003.000000Y(3,1)1.0000004.000000Y(3,2)0.0000004.000000Y(3,3)0.0000004.000000Y(3,4)0.0000004.000000Y(3,5)0.0000004.000000Y(4,1)0.0000002.000000Y(4,2)0.0000002.000000Y(4,3)0.0000002.000000Y(4,4)0.0000002.000000Y(4,5)0.0000002.000000z(1/1)0.0000005.000000Z(lz2)0.0000005.000000Z(1,3)0.0000005.000000Z(1,4)0.0000005.000000Z(lz5)0.0000005.000000Z(2,1)0.0000004.000000Z(2,2)0.0000004.000000Z(2,3)1.0000004.000000Z(2,4)0.0000004.000000z(2,5)0.0000004.000000Z(3,1)0.0000001.000000Z(3,2)0.0000001.000000Z(3,3)0.0000001.000000Z(3,4)0.0000001.000000Z(3,5)0.0000001.000000Z(4,1)0.0000009.000000Z(4,2)0.0000009.000000Z(4,3)0.0000009.000000Z(4,4)0.0000009.000000Z(4,5)0.0000009.000000Row12Dual Price-1.0000000.000000Slack or Surplus75.50000150.0000350.000000.0000004200.00000.0000005100.00000.00000060.0000000.00000070.0000000.00000080.0000000.00000090.0000000.000000100.0000000.000000110.0000000.000000120.0000000.000000130.0000000.000000140.0000000.000000150.0000000.000000161.0000000.000000170.0000000.000000180.0000000.000000190.0000000.000000200.0000000.000000210.0000000.000000220.0000000.000000230.0000000.000000240.0000000.000000250.0000000.000000260.0000000.000000270.0000000.000000280.0000000.000000290.0000000.000000300.0000000.000000310.0000000.000000320.0000000.000000330.0000000.000000340.0000000.000000350.0000000.000000360.0000000.000000370.0000000.000000380.0000000.000000390.0000000.000000400.0000000.000000410.0000000.000000420.0000000.000000实验三：一、问题重述某班准备从5名游泳队员中选择4个人组成接力队，参加学校的4*100m混合泳接力比 赛。5名队员4种泳姿的百米平均成绩如下表所示(单位：秒)，问应如何选拔队员组成 接力队？甲乙丙T戊蝶泳66.857.2787067.4仰泳75.66667.874.271蛙泳8766.484.669.683.8自由泳58.65359.457.262.4进一步考虑：如果最近队员丁的蛙泳成绩有较大退步，只有75. 2秒；而队员戊经过艰 苦训练自由泳成绩有所进步，达到57. 5秒，组成接力队的方案是否应该调整？二、模型假设及符号说明以i=l, 2, 3, 4, 5分别表示5名队员，j=l, 2, 3, 4分别表示4种泳姿，以c”表示 第i名队员第j种泳姿的最好成绩；设第i名队员是否使用第i种泳姿参与比赛为Xij,若 第i名队员使用第j种泳姿参与比赛，则xu=l,对应地，若xu=O,则表示第i名队员不使 用第j种泳姿参与比赛。其中，每位成员最多可上场一次，且四种游泳方式都必须有队员使 用。三、数学模型5 4min z =工=内i=l ；=l，a=1(/T,2,3,4)s. t. , £x屋 l(i = 1,2,3,4,5)勺二0或1四、模型求解及结果分析模型一结果分析：当为2=83=134=匕|=1时，即甲选手以自由泳，乙选手以蝶泳，丙选手以仰泳，丁选手以蛙泳参加比赛，所得成绩时间少，即z=253.2秒；模型二结果分析：当芭2=/3=马4=匕5=1时，即乙选手以蝶泳，丙选手以仰泳，丁 选手以蛙泳,戊选手以自由泳参加比赛，所得成绩时间最短，即z=257.7秒。五、附录(程序)模型一：sets :yong/1.4/;xuan/1.5/;link(yong,xuan):c,x;endsetsdata:c=66.8 57.2 78 70 67.475.6 66 67.8 74.2 7187 66.4 84.6 69.6 83.858.6 53 59.4 57.2 62.4;enddatamin=sum (link, (i, j ) : c (iz j ) *x (i, j );for(xuan (j) :sum(yong(i) :x(i,j)<=1);©for(yong(i):sum(xuan(j):x(i,j)=1);for(link (i,j) :bin (x (i,j);模型一运算结果：Global optimal solution found.Objective value:Objective bound:Infeasibilities:Extended solver steps:Total solver iterations:Variablec(lz1)C(1/2)C(1,3)C(1/4)C(lz5)c(2,1)c(2,2)c(2,3)C(2,4)C(2,5)C(3,1)C(3,2)c(3,3)c(3,4)c(3,5)c(4,1)c(4,2)C(4,3)253.2000253.20000.00000000ValueReduced Cost66.800000.00000057.200000.00000078.000000.00000070.000000.00000067.400000.00000075.600000.00000066.000000.00000067.800000.00000074.200000.00000071.000000.00000087.000000.00000066.400000.00000084.600000.00000069.600000.00000083.800000.00000058.600000.00000053.000000.00000059.400000.000000C( 4, 4)57.200000.000000C( 4Z 5)62.400000.000000X( 1, 1)0.00000066.80000X( 1, 2)1.00000057.20000X( 1, 3)0.00000078.00000X( 1, 4)0.00000070.00000X( 1, 5)0.00000067.40000X( 2Z 1)0.00000075.60000X( 2Z 2)0.00000066.00000X( 2, 3)1.00000067.80000X( 2Z 4)0.00000074.20000X( 2Z 5)0.00000071.00000X( 3, 1)0.00000087.00000X( 3, 2)0.00000066.40000X( 3, 3)0.00000084.60000X( 3, 4)1.00000069.60000X( 3, 5)0.00000083.80000X( 4Z 1)1.00000058.60000X( 4, 2)0.00000053.00000X( 4, 3)0.00000059.40000X( 4Z 4)0.00000057.20000X( 4, 5)0.00000062.40000RowSlack or SurplusDual Price1253.2000-1.00000020.0000000.00000030.0000000.00000040.0000000.00000050.0000000.00000061.0000000.00000070.0000000.00000080.0000000.00000090.0000000.000000100.0000000.000000模型二：sets:yong/1.4/;xuan/1.5/;link(yong,xuan):c,x;endsetsdata:c=66.8 57.2 78 70 67.475.6 66 67.8 74.2 7187 66.4 84.6 75.2 83.858.6 53 59.4 57.2 57.5;enddatamin=sum(link(i,j):c(i,j)*x (i,j);for(xuan (j) :sum(yong(i) :x(i,j)<=1);for(yong(i):sum(xuan(j):x(i,j)=1);for(link(iz j) :bin (x (i,j);模型二运算结果：Global optimal solution found.Objective value:Objective bound: Infeasibilities:257.7000257.70000.000000Extended solver steps:0Total solver iterations:0VariableValueReduced CostC(lz1)66.800000.000000C(1,2)57.200000.000000C(1,3)78.000000.000000C(lz4)70.000000.000000C(1/5)67.400000.000000C(2,1)75.600000.000000c(2,2)66.000000.000000C(2,3)67.800000.000000C(2,4)74.200000.000000C(2,5)71.000000.000000C(3,1)87.000000.000000C(3,2)66.400000.000000C(3,3)84.600000.000000C(3,4)75.200000.000000C(3,5)83.800000.000000c(4,1)58.600000.000000C(4,2)53.000000.000000C(4,3)59.400000.000000C(4,4)57.200000.000000C(4,5)57.500000.000000X(1/1)0.00000066.80000X(1,2)1.00000057.20000X(1/3)0.00000078.00000x(lz4)0.00000070.00000x(1/5)0.00000067.40000X(2,1)0.00000075.60000X(2,2)0.00000066.00000X(2,3)1.00000067.80000X(2,4)0.00000074.20000X(2,5)0.00000071.00000X(3, 1)0.00000087.00000x(3, 2)0.00000066.40000X(3, 3)0.00000084.60000X(3, 4)1.00000075.20000X(3, 5)0.00000083.80000x(4, 1)0.00000058.60000X(4, 2)0.00000053.00000X(4, 3)0.00000059.40000x(4, 4)0.00000057.20000X(4, 5)1.00000057.50000RowSlack or SurplusDual Price1257.7000-1.00000021.0000000.00000030.0000000.00000040.0000000.00000050.0000000.00000060.0000000.00000070.0000000.00000080.0000000.00000090.0000000.000000100.0000000.000000实验一：一、问题重述某昼夜服务的公共交通系统每天各时间段(每4个小时为一个时段)所需的值班人数如 卜.表所示。这些值班人员在某一时段开始上班后要连续工作8个小时(包括轮流用膳时间)。 问该公交系统至少需要多少名工作人员才能满足值班的需要？班次时间段所需人数16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030二、模型假设及符号说明设该第i班次开始上班的工作人员的人数为Xi人，则第i班次上班的工作人员将在第 (i+l)班次下班。(i= 1,2,3,4,5,6)三、数学模型min z = xl+x2+x3+x4+x5+x6r x6 4- 1 > 60xi+x2> 7()x2 + x3 > 60sJ. <+ x4 > 50x4+xs> 20x5 + x6 > 30y之0,且一均为整数，i = 1,2,.6四、模型求解及结果分析Global optimal solution found.Objective value:150.0000Objective bound:150.0000Infeasibilities:0.000000Extended solver steps:0Total solver iterations:4ValueReduced60.0000010.00000VariableCostXI1.000000X21.000000X350.000001.000000X40.0000001.000000X530.000001.000000X60.0000001.000000RowSlack, or SurplusDualPrice1150.0000-1.00000020.0000000.00000030.0000000.00000040.0000000.00000050.0000000.000000610.000000.00000070.0000000.000000根据Ling。程序运行结果分析可知：当第i班次开始上班的工作人员排布如下时，所需 人力最少，为150人。班次123456人数6010500300五、附录(程序)min=xl+x2+x3+x4+x5+x6;xl+x6>=60;xl+x2>=70;x2+x3>=60;x3+x4>=50;x4+x5>=20;x5+x6>=30;gin(xl);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6); end实验二：一、问题重述某公司正在考虑在某城市开发一些销仕:代理业务。经过测试，该公司已经确定了该城市 未来5年的业务量，分别为400, 500, 600, 700和800。该公司已经初步物色了4家销售公司作为 其代理候选企业，下表给出了该公司与每个候选企业建立代理关系的一次性费用，以及每个 候选企业每年所能承揽的最大业务量和年运行费用。问改公司应该与哪些候选企业建立代理 关系？候选代理1候选代理2候选代理3候选代理4年最大业务量350250300200一次性费用（万元）100809070年运行费用（万元）7.54.06.53.0在此基础上继续讨论：如果该公司目前已经与上述4个代理建立了代理关系并处于运行 状态，但每年年初可以决定临时中断或重新恢复代理关系，每次临时中断或重新恢复代理关 系的费用如下表所示。问该公司应如何对这些代理进行业务调整？代理1代理2代理3代理4临时中断费用（万元）5342重新恢复费用（万元）5419二、模型假设及符号说明模型一：设第j年与候选代理i是否开始建立代理关系为Xij,若在第j年与该候选代理i开始建 立代理关系，则xij=l,表示关系不中断，对应需要付清一次性费用，以及共（6-j）年的年 运行费用；对应地，若Xij=O,则表示该代理公司在第j年尚未建立代理关系或在此之前已经 建立了代理关系。即：七=J 1，第/年与第，家代理开始建立代理关系.0, else5且有：= 1模型二：模型假设：公司已经与四家都有代理关系符号说明：%=1 一一第j年与第i个公司有代理关系马=0笫j年与第i个公司没有代理关系为=1 一一第j年与第i个公司中断代理关系z/7 = I -第j年与第i个公司恢复代理关系三、数学模型模型一：z1)= 0 一一第j年与第i个公司不恢复代理关系5555min z = 10。2xj + 8°Z-v2/- + 90Zx3J + 70x4,7-1川j-ij-i+ 7.5g (6 -J)A-ly+4(6-j)x2；+ 6.5g(6一 /)刍/ + 3g (6 力匕, j=i，=i;=i，=i'350xn + 250% + 300x3i + 200x41 > 4002222350,j + 2502占4 +300213, + 200Xx4；2 500y=ij=iJ=i六i3503 j + 250火 +300力 为 + 200 x4. > 600y=i;=i>ij=i4 4443502% + 25。2% +30()Z% + 20()WX 2 700 j=i;=ij=ij=i5 555350Z xm + 250Z 工2, + 30。2 x3j + 200Z X4J - 800 j=i，=ij=i六i、%=0或1, i = 123,4, J = 1,2,345模型二：5555min Z = 7.5 X1, + 4.0 x2j + 6.5 x3j + 3.02 x4y7-i六 j-i7-i+ 52 )3 + 32 y2j + 4 之 y3j+y4 .7=1；=I7=1 j=l5555+4 , +Z2j + Z z3；+ 9Z z管八 ij=i八 i350x11 + 250x2I+ 300x3I+ 200x41 > 400350M 2 + 250x22 + 300x32 4- 200x42 > 500 35(1% + 250.& + 3000 + 200% > 600s工 350% + 250% + 300处 + 200% > 700350不 + 250x25+ 3000 + 200x45> 800 为一毛(加)工)力+中，=123,4, j =0,1,2,3,4 XgfjW z«m),i = 1,2,3,4, j = 1,2,3,4四、模型求解及结果分析模型一结果分析：当“=/1=匕4=1时，即公司在第一年初开始与代理1、代理2建 立代理关系，在第四年开始与代理4建立关系，此时为最少费用，即z=313.5万元。模型二结果分析：当)% =%i=l，Z23=l时，即公司在与所有代理保持代理关系的前提 下，在第一年与代理2、代理3中断代理，在第3年与代理2恢复代理关系，此时为最少费 用，即z=75. 5万元。五、附录(程序)模型一运算代码：sets :buss/1.4/;year/1.5/;link(buss,year) :c, x;endsetsdata:c=350 100 7.5 5 5250 80 4.0 3 4300 90 6.5 4 1200 70 3.0 2 9;enddatamin=sum(link(i,j) :c(i,2)*x (i,j) + sum (buss (i) :c(i,3)* (5*x(i,l)+4*x(i,2)+3*x(i,3)+2*x(i,4)+x(i,5)/for(buss(i):sum(year(j):x(i,j)<=1);sum(buss(i):c(izl)*x(i,l)>=400;sum(buss(i):c(i,l)*(x(i,l)+x(i,2)>=500;sum (buss (i) :c(izl)*(x(izl)+x(iz2)+x(i,3) ) ) >=600;sum (buss (i) :c(i,l)*(x(i,l)+x(i,2)+x(i,3)+x(i,4) ) ) >=700;sum(buss(i):c(i,l)*(x(i,l)+x(i,2)+x(i,3)+x(i,4)+x(i,5)>=800;for(link(i,j) :bin (x (i,j);模型一运算结果：Global optimal solution found.Objective value:313.5000Objective bound:313.5000Infeasibilities:0.000000Extended solver steps:0Total solver iterations:35VariableValueReduced CostC(1,1)350.00000.000000c(lz2)100.00000.000000c(1/3)7.5000000.000000c(1,4)5.0000000.000000C(1/5)5.0000000.000000C(2,1)250.00000.000000C(2,2)80.000000.000000C(2,3)4.0000000.000000c(2,4)3.0000000.000000C(2,5)4.0000000.000000c(3,1)300.00000.000000C(3,2)90.000000.000000C(3,3)6.5000000.000000C(3,4)4.0000000.000000C(3,5)1.0000000.000000c(4,1)200.00000.000000C(4,2)70.000000.000000c(4,3)3.0000000.000000C(4,4)2.0000000.000000C(4,5)9.0000000.000000X(1/1)1.000000137.5000x(lz2)0.000000130.0000x(1,3)0.000000122.5000X(1,4)0.000000115.0000x(lz5)0.000000107.5000X(2,1)1.000000100.0000X(2,2)0.00000096.00000X(2,3)0.00000092.00000x(2,4)0.00000088.00000X(2,5)0.00000084.00000X(3,1)0.000000122.5000x(3,2)0.000000116.0000X(3,3)0.000000109.5000X(3,4)0.000000103.0000X(3,5)0.00000096.50000X(4,1)0.00000085.00000X(4,2)0.00000082.00000x(4,3)0.00000079.00000x(4,4)1.00000076.00000X(4,5)0.00000073.00000Row12Dual Price-1.0000000.000000Slack or Surplus313.50000.00000030.0000000.00000041.0000000.00000050.0000000.0000006200.00000.0000007100.00000.00000080.0000000.0000009100.00000.000000100.0000000.000000模型二：sets :buss/1.4/;year/1.5/:b;link(buss,year):c,x,y,z;endsetsdata:c=350 100 7.5 5 5250804.034300906.541200703.029;b=400 500 600700 800;enddatamin=sum(link(i,j):c(i,3)*x (i,j) +sum(link(i,j):c(i,4)*y(i,j)+sum(link(i,j):c(i,5)*z (i,j);for(year(j) :sum(buss(i) :c(i,l)*x(i,j)>=b (j);for(buss(i):1-x(i,1)<=y (i,1);for(buss (i) :for(year(j) |j#LE#4:x(iz j)-x(i,j + 1)<=y(iz j +1);for(buss(i):for(year(j)|j#LE#4:x(i,j+1)-x(i,j)<=z(i,j+1);for(link(i,j) :bin (x (i,j);for(link (i,j) :bin(y(i,j);for(link(i,j):bin (z(i,j);模型二运算结果：Global optimal solution found.Objective value:75.50000Objective bound:75.50000Infeasibilities:0.000000Extended solver steps:0Total solver iterations:141VariableB( 1)Value400.0000Reduced Cost0.000000B(2)500.00000.000000B(3)600.00000.000000B(4)700.00000.000000B(5)800.00000.000000C(1/1)350.00000.000000C(lz2)100.00000.000000C(1,3)7.5000000.000000C(lz4)5.0000000.000000c(1/5)5.0000000.000000C(2,1)250.00000.000000c(2,2)80.000000.000000C(2,3)4.0000000.000000C(2,4)3.0000000.000000C(2,5)4.0000000.000000C(3,1)300.00000.000000c(3,2)90.000000.000000C(3,3)6.5000000.000000c(3,4)4.0000000.000000C(3,5)1.0000000.000000C(4,1)200.00000.000000C(4,2)70.000000.000000C(4,3)3.0000000.000000c(4,4)2.0000000.000000C(4,5)9.0000000.000000x(lz1)1.0000007.500000X(1/2)1.0000007.500000X(1,3)1.0000007.500000X(1/4)1.0000007.500000x(lz5)1.0000007.500000X(2,1)0.000000
