运筹学[胡运权]第五版课后运筹作业

1、47 页 1.1bX22x1+x2=2用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解47 页 1.1d无界解1.2 (b)约束方程的系数矩阵 A= 1 22 1 1 2P1 P2 P3(4基基解X1 X2 X3 X4是含RJ行解目标函数值P1 P2-411/200否P1 P32/5011/50是43/5P1 P4-1/30011/6否P2 P301/2 20是5P2 P40 -1/2 02否P3 P40011是5最优解 A=(01/2 20)T和(0011)T49页13题设Xij为第i月租j个月的面积minz=2800x11+2800x21+2800x31+2800x41+450

2、0x12+4500x22+4500x32+6000x13 +6000x23+7300x14s.t.x11+x12+x13+x14 >15x12+x13+x14+x21+x22+x23 >10，13+x14+x22+x23+x31+x32 > 20x14+x23+x32+x41>12Xij>0用excel求解为：用LINDO求解：LP OPTIMUM FOUND AT STEP 3OBJECTIVE FUNCTION VALUE1)118400.0VARIABLE VALUEREDUCED COSTZ 0.0000001.000000X113.0000000.000

3、000X210.0000002800.000000X318.0000000.000000X410.0000001100.000000X120.0000001700.000000X220.0000001700.000000X320.0000000.000000X130.000000400.000000X230.0000001500.000000X1412.0000000.000000ROW SLACK OR SURPLUS DUAL PRICES2)0.000000-2800.0000003)2.0000000.0000004)0.000000-2800.0000005)0.000000-170

4、0.000000NO. ITERATIONS= 3答 若使所费租借费用最小，需第一个月租一个月租期300平方米，租四个月租期1200平方米，第三个月租一个月租期 800平方米，50页14题设al, a2, a3, a4, a5 分别为在A1, A2, B1, B2, B3 加工的I产品数量，bl, b2, b3分别为在A1, A2, B1 加工的II产品数量，cl为在A2, B2上加工的田产 品数量。则目标函数为maxz= (1.25-0.25)( a1+a2+a3)+( 2-0.35) b3+( 2.8-0.5)c1 -0.05 (a1+b1)-0.03 (a2+b2+c1)- 0.06 (

5、a3+b3)-0.11(a4+c1)-0.05a5=0. 95a1+0. 97a2+0. 94a3+1.5b3+2.1c1-0.05b1-0.11a4-0.05a5s.t.石a1+10b1 <60007a2+b2+12c1 <100006a3+8a3 < 4000I 4a4+11c1 <70007a5 <4000a1+a2-a3-a4-a5=0b1+b2-b3=0Ia1 , a2, a3, a4, a5, b1 , b2, b3, c1 >0用lindo求解得：LP OPTIMUM FOUND AT STEP 6OBJECTIVE FUNCTION VALU

6、E1) 16342.29REDUCED COST0.0000009.6400000.0000000.00000015.9000000.2300000.0000000.0000000.000000VARIABLE VALUE A11200.000000A20.000000A3285.714294B3 10000.000000 C10.000000B10.000000A4342.857147A5571.428589B2 10000.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.0000000.1680003) 0.0000001.5000004) 0.000

7、0000.0750005) 5628.5712890.0000006) 0.0000000.0085717) 0.0000000.1100008) 0.000000-1.500000NO. ITERATIONS= 6 计算lindo截屏一皿 广如刈 也的产Np3二.制“一1制西»即，wi am 的王昱iaIP (FTIXIV mi,5? < STEFCBJEC7BE FLNCTlUX -ALLE16J42.29) E 1 7 3 3 1 J TJ2 1 U-A4-A&CBAAK&VALLE1200.000000 比 OTOOTO285.7142941小.OOOO

8、OO 0.000000 0. OCOQQO342.8571475Tl.d2SS91帆帆健眦2REXCED l<JST 0.000000 ft IV+OOOO O.CKXMJW 0. oooooo 瓜 900000 0. JOOW 0. OQOOQO O.OQOOQO 0.000000顼-grW 0. gSslW，QlaS+l, ib3+2- ! cl-0P05b-l_0, La4-0P05a5 Ie. t.501+10>1 =&OTO7a2+b2+12cK-10OT0期3+6心仁4飙4a4+llCl- =70007a5(=4fl00卜卜心-«3-的f

9、5=0bl+bZ-b 灯 0end|R时SLACK OR SLRPLC5XAL PSICEo2)0.0000400.160003)o.ocoooo1.5000004)见OOOQOOO OTifflWj)-20. 0QOTO06)o.oeoooo0.0086717)0.040(XX>ft. 110000B)D. 000000"-1. 50(X100K0. ITERADOW-62.1a:对偶问题为：maxz=2y1+3y2+5y3s.t.,1+2y2+y3 <2,3y3+y2+4y3 <24y1+3y2+3y3=4y y1 >0, y 2 00,y3 无约束因此本

10、问题的对偶问题的对偶问因为原问题的对偶问题的对偶问题仍是原问题, 题为：minz=2x1+2x2+4x3s.t.xx1+3x2+4x3 >22x1+x2+3x3< 3x1+4x2+3x3=5:x1,x2 >0,x3 无约束81 页 2.12a)设x1,x2,x3分别为A, B, C产品数量maxz=3x1+x2+4x3s.t.6x1+3x2+5x30 453x1+4x2+5x30 30x1,x2,x3 >0用lomdo求解为LP OPTIMUM FOUND AT STEP 2OBJECTIVE FUNCTION VALUE1)27.00000VARIABLEX1X2X3

11、X1,X2,X3VALUE5.0000000.0000003.0000000.000000REDUCED COST0.0000002.0000000.0000000.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.0000000.2000003) 0.0000000.6000004) 0.0000000.000000NO. ITERATIONS= 2限untitled下max 3xl+x2+4x3I s. t.6xl+3x2+5x3<=45 3xl+4x2+5x3<=30 xl, x2, x3)l0 end|LP OPTTfUXf FOUND

12、AT STEP 2OBJECTIVE FUNCTION VALUE1) 27.00000VARIABLE VALUEREDUCED COSTXI5.0000000.000000X20.0000002.000000X33,0000000.000000Xh X2t X30.0000000. 000000DIAL PRICES 0.200000 0.600000 0.000000ROW SLACKOR SURPLUS2) 0.0000003) 0.0000004) 0.000000NO. TTERATTOXS= 2最大生产计划为A生产5个单位，C生产3个单位b)LP OPTIMUM FOUND AT

13、 STEP 2OBJECTIVE FUNCTION VALUE1)27.00000VARIABLEX1X2X3X1,X2,X3VALUE 5.000000 0.000000 3.0000000.000000REDUCED COST0.0000002.0000000.0000000.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.0000000.2000003) 0.0000000.6000004) 0.0000000.000000NO. ITERATIONS= 2RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEF

14、FICIENT RANGESVARIABLE CURRENT ALLOWABLE ALLOWABLECOEF INCREASE DECREASE0.600000 INFINITY 1.500000INFINITYX13.0000001.800000X21.0000002.000000X34.0000001.000000X1,X2,X30.0000000.000000RIGHTHAND SIDE RANGESROW CURRENT ALLOWABLE ALLOWABLERHS245.000000330.00000040.000000INCREASE15.00000015.000000 0.000

15、000DECREASE15.0000007.500000INFINITY暧 Reports WindupLP OPTIMUMFOUWD AT 5TEP2RTErTEE TTHr"TOU TALITE1)27 COCOOHABLEVALUEREDUCED 8STKIE 0000000 000003X20.0000002.000DQD曲3 OQOUOUU.OOtJDQ JSI. 12,5«30 OQOQOQ.OQDDa 口w untitled >max 3xl+x2+4x3 s. t.6xl-3x2+5x3<=453xl+4x2+5x3<=30 xL x2,

16、x3>=0 endlOBJECTIVE FUNCTION VALUE231SL4CK CR SUEF1US DUiil PRICESD. 0000000,2000000 0000000.600DOD 000000(LOW口口口ND ITEK4TZCNS=RiWGES IN UHICE THE BA5J5 IS UNCHITGEDOBJ COEFFrriENT P iff GESVARIABLECL EhENTaLLQVABIXALLEABLECOEF7NCREAF：7DECREASFII3.000000i SOOOOt)O.feODO JOX-1 LOLUOU2 uUOUDOIMFd I

17、 TV734 000000i -oonan1 =minMC.COaODDL ODOOQOIHFIMITyRTGKTHiNTi SIDE 熊MESCLRFEN7aLLOVABLK心 LLWABLEBBSTHCRE各更/包胎三15 L OLOOO-E .00U00-E jnjo ju3C COOOOOIE OODOOO7 30 30 JOr coaciDn -nd口口口TUFIjITTY可知A产品的利润变化范围6. 8,2.4，上述计划不变c)设X4为产品D的数量maxz=3x1+x2+4x3+3x4s.t.'6x1+3x2+5x3+8x40 453 3x1+4x2+5x3+2x40 30

18、1x1,x2,x3 ,x4 >0用lomdo求解为LP OPTIMUM FOUND AT STEP 01)27.50000REDUCED COST0.1000001.9666670.0000000.000000OBJECTIVE FLyCTIOX ',r；±UE27,50000VALUE0. OOOODO0. OOOODO5.OOOOOO2. 500000REDLCEC COST D. 100000 1.96666, 0. 000000 0. 000000R阴 SLCK OR SURPLUS2) 0.0000003) 0.000000410.000000>0. O

19、OCOOO6) 5.0000007) 2.500。50. IIER.mOS=2DIAL PRICES 0.2333330. 5666670. 0000000. 000000Q. 0000 g0. 000000国.urrmied hmax 3xl+x2+4x3+3x4s. t.6x1-3k2+5x3+8x4<=45 3xl-4x2+5x3+2x4<-30| xl>=0x2> 二 0x3X0x4>-0 endVARIABLE VALUEX10.000000X20.000000X35.000000X42.500000ROW SLACK OR SURPLUS DUAL P

20、RICES2) 0.0000000.2333333) 0.0000000.566667NO. ITERATIONS= 0安排生产D有利，新最有生产计划为x1=x2=0,x3=5,x4=2.5 ,利润为27.5d)maxz=3x1+x2+4x3-0.4y s.t.Bx1+3x2+5x3 <45J 3x1+4x2+5x3-y <30 x1,x2,x3,y>0用lomdo求解为LP OPTIMUM FOUND AT STEP 0REDUCED COST0.6000001.8000000.0000000.000000陶 Reports WindowLP OPTTMLAI FOLAD

21、AT STEP 。OBJECTIVE FUMTTOX VALIT1)30.00000VARIABLE XI X2 X3YVALUE0.000000O.0000009.00000015,000000REDUCED COST 0.600000 L 800000 0. 000000 0. 000000唯 <Lintitlf*dimax 3xl*x2+4x3 0. -lyS. T.6xl3x25x3<-453xl+4x2+5x3-y<=30 xl>=0x2>0x3>=0y>0enil|4.1EOW sr KK OR SUKPLUS2) 0.00000。3) 0

22、.0000004) 0.0000005) 0.0000006) 0.0000007) 15.000000XO. ITEmi0XS= 0可知购进原材料15个单位为宜a) 设yi= 1 第i组条件起作用I 0 第i组条件不起作用(x1+x2<2-(1-y1)MM2x1+3x215+(1-y2)M y1+y2=1y1,y2=0 或 1DUAL PRICES 0.400000 0. 100000 0.000000 0.000000 0.000000 0.000000一充分大正数VARIABLE VALUEX10.000000X20.000000X39.000000Y15.000000ROW SL

23、ACK OR SURPLUS DUAL PRICES2) 0.0000000.4000003) 0.0000000.400000NO. ITERATIONS= 0b)设 yi= 1第i组条件起作用第i组条件不起作用x月y1 x=3y2 x=5y2 彳7y4 y1+y2+y3+y4=1 yy2,y3,y4=0C) 设yi二1为假定取伯> 50i1r 0为假定取值x=01 x=0y1J x> 50-(1-y2)M|y1+y2=1y1,y2=0 或 1d)设yi= 1 第i组条件起作用i=1,2 则i=1,2 则J 0 第i组条件不起作用L x1<2+(1-y1)M x2>1

24、-(1-y1)M< x2<4+(1-y2)M y1+y2=1、y1,y2=0 或 1e)设yi=1 第i组条件起作用10 第i组条件不起作用x1+x2 <15-(1-y1)M x1<2-(1-y2)M x3>2+(1-y3)Mx3+x4>6+(1-y4)M y1+y2+y3+y4>2l y1,y2,y3,y4=1 或 04.2$ 10minz二乙-1cjxj弓 , 1xj=5x1+x8=1x7+x8=1s.t. x3+x5< 144+x5< 1x5+x6+x7+x8<2xj= 1选择钻探第sj井位0- 否4.5设xij为第i种泳姿用第

25、名运动员minza也.户Js.t.x x11+x12+x13+x14+x15=1x21+x22+x23+x24+x25=1x31+x32+x33+x34+x35=1x41+x42+x43+x44+x45=1-x11+x21+x22+x23=1x12+x22+x32+x42=1x13+x23+x33+x43=1x14+x24+x34+x44=1I x15+x25+x35+x45=1 xij=1 或 0(i=1,2,3,4 j=1,2,3,4,5)由excel计算得出；张游仰泳，王游蛙泳，赵游自由泳，预期总成绩为 126.2s.V丘耽/长餐AEC口EF, MS)里沃33.32S,638,930.4

26、33.6军干：力M0j中十傅曲俎ha茂同D2ft. 226.429. 62B. 531. 1可雪中格印：liiiniiFiis* L悔斗幺起找扶王直口泳 illxl2113xl.4xlSu= jz-t：； ifFlZil昆泳 121122123Q4x26(GSlECIlS inilEtlllBE 泳 11132加X34X35. 1驻通吕由泳 X打亶裴x43乂屿里设张王.史求和口泳100001苜1泳01000= 1中泳001001胃13由泳000101 = 1格和】1110<=jT=<= <= <=1111137.7000C01G000口翻”0000029.6037.7A

27、3L】蕊.928.30ini 1138. 2r=T'一一1唠次33 32fi. S 36, g30, 433. 6自由泳Z9. 226,429.628.531.可用于蝌用工如泳总盘赵 xll 需】钱张112x13122摩王周114X15X24x 市ME.主域需到一斛，比内是所与的为诺度事优粉品.报诒SJ二印修吉一一锣细嵯的鬻富疆依夏力卬厘忌泳x32烹33X34万跖定 r取前除“F亲iL-翘曲瓜自由泳x41i42x-13i44愁找张王H求和001001=I0001Q1-10100Q=1自由读1。000111 10< << <11 11 0Q33. S0000034

28、.70028.5000?9 20000总计29 2126.：28. 533. 83-1.70nicu匚因为使mindl-,故在x1+x2=40的右侧，若使mind4+,则在x1+x2=50的左侧，即 阴影区域，因为在阴影部分无法使 2d2-+d3-最小，故比较E (20, 30) ,F (24, 26) ,E 点:d2-=4,d3-=0 min2d2-+d3-=8, F点:d2-=0,d3-=4, min2d2-+d3-=4,故选F点程序法七先级别约束x124约束蛭30止偏差的14负偏差d-约束 04C关察 一4000C24二240C30三30001Q50=30:indl-0.淑1于魏培星3

29、报京一I一性1=克感I'k 番k-1,6.36优先飙乱约束Hl约束Vd2426d3d4aiTidl-ai ntU* ：J12d2-t正惘差日+负偏差d-1约束1000-100 关系40 =24 -30 =5。=6.4a破圈法40243050避圈法最小部分树166.4b10121012最小部分树32172 页 v1|o I1. 8v21.72. 8v33.71.4v4v02.9红色曲线为使用一年卖出蓝色曲线为使用两年卖出绿色曲线为使用三年卖出紫色曲线为使用四年卖出最短路程为 3.7万元，路径为 v0-v1-v4 或v0-v2-v4 或v0-v1-v

30、2-v4三种方案分别为：第一年年初买新车，年末卖掉再买新车，一直用到第四年年末卖掉；第一年出买新车，用两年后于第二年末卖掉再买新车，用两年于第四年末卖掉；第一年出买新车，年末卖掉后再买新车，第二年末卖掉再买新车，再用两年于第四年年末卖掉。由图可知，若摩托车最多使用三年，答案仍然不变6.14bv5 (v4,1)根据题意，先给发点vs标号，由弧（vs,v2 ）得对v2进行标号（vs,1 ）;弧（v2,v1 ）对v1标号（v2,1 ）; 弧（vs,v3 ）得对 v3 进行标号（vs,1 ）;弧（v3,v4 ）对 v4 标号（v3,1 ）;弧（v3,v4 ） 对 v4 标号（v3,1 ）;弧（v4,v

31、5）对 v5 标号（v4,1 ）;弧（v5,vt ）对 vt 标号（v5,1 ）; 反向追踪找出增广链最大流为 14,最小割集为 （v1,v3） （v2,v3） （v2,vt ） （v1,vt ） 6.14c最大流13,无最小割集193 页-7.2 表 7-9194 页 7.3b假定最初事件在时刻零出现，则有t ES(1,2)= t ES(1,3)= t ES (1,4)=0t EF (1,2)= t ES (1,2)+t(1,2)=2t EF (1,3)=4t EF (1,4)=8t ES (2,5)=2t EF (2,5)=5t ES (5,8)=8t EF (5,8)=15t es (8

32、,9)=15t EF (8,9)=20t es (5,7)=5t ef (5,7)=7t ES (4,7)=8t EF (4,7)=11t ES (4,6)=8t EF (4,6)=10t ES (3,6)=4t EF (3,6)=12t ES (6,7)=12t EF (6,7)=13t ES (7,9)=13t EF (7,9)=15t ES(6,9)=12t EF (6,9)=19最短周期为 20t LF(6,9)= t LF(8,9)= t LF (7,9)=20t LS(8,9)=15t LS(7,9)=16t LS(6,9)=13t LF(5,8)=15t LS(5,8)=8t L

33、F(5,7)=16t LS(5,7)=14t LS(4,7)=10t LF(4,7)=13t ls(6,7)=15 t lf(6,7)=16 t ls(4,6)=10 t lf(4,6)=13 t ls(3,6)=5t lf(3,6)=13 t ls(1,3)=1t lf(1,3)=5 t ls(1,4)=0t lf(1,4)=8 t lf(2,5)=8t ls(2,5)=5 t lf(1,2)=5t ls(1,2)=3作业(ij )t (i,j)t ES(i,j)t EF(i,j)t LS(i,j)t LF(i,j)Ri,j)F(i,j)12345678(1，2)2023530(1， 3)4

34、041510(1，4)8080800(,5)3255830(3, 6)841251310(4, 5)0888800(4, 6)2810101332(4, 7)3811101322(5, 7)757141696(5, 8)781581500(6, 7)11213151630(6,9)71219132011(7,9)41315162055(8,9)51520152000关键路线为(1 , 4) , (4, 5), (5 , 8) , (8 , 9)课堂作业1.柴油机生产计划设x1,x2,x3,x4分别为一二三四季度计划 minz= 11.4x1+11.55x2+11.3x3+11.45x4s.t.

35、zx1<25x2<35Jx3<30x4<10<x1+x2+x3+x4=70LP OPTIMUM FOUND AT STEP 3OBJECTIVE FUNCTION VALUE1) 796.2500REDUCED COST0.0000000.0000000.0000000.000000VARIABLE VALUEX125.000000X25.000000X330.000000X410.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.0000000.1500003) 30.0000000.0000004) 0.0000000.25

36、00005) 0.0000000.1000006) 0.000000-11.550000NO. ITERATIONS= 3.日. ：，1，间则密闻 品制 目但! 由&j 1MI Iiia-p nc*> p KBiaarsywOBJECTIVE -I-XCTTDX VALUEI)796.2500VARIABLEVALUEXI25.000000X25.000000X330.000000对10.ooooooKEDVCED COST s oooooo c. oooooo 0. 000000 o.oooooobin IL 4x111, S. L k1<=27' x2<=35 k3<-30 x4<=10xl+x2x3