運籌學[胡運權]第五版課后運籌作業(yè)

1、47 頁 1.1bX22x1+x2=2用圖解法找不到滿足所有約束條件的公共范圍，所以該問題無可行解47 頁 1.1d無界解1.2 (b)約束方程的系數(shù)矩陣 A= 1 22 1 1 2P1 P2 P3(4基基解X1 X2 X3 X4是含RJ行解目標函數(shù)值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最優(yōu)解 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產(chǎn)品數(shù)量，bl, b2, b3分別為在A1, A2, B1 加工的II產(chǎn)品數(shù)量，cl為在A2, B2上加工的田產(chǎn) 品數(shù)量。則目標函數(shù)為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截屏一皿 廣如刈 也的產(chǎn)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產(chǎn)品數(shù)量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最大生產(chǎn)計劃為A生產(chǎn)5個單位，C生產(chǎn)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產(chǎn)品的利潤變化范圍6. 8,2.4，上述計劃不變c)設X4為產(chǎn)品D的數(shù)量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安排生產(chǎn)D有利，新最有生產(chǎn)計劃為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一充分大正數(shù)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計算得出；張游仰泳，王游蛙泳，趙游自由泳，預期總成績?yōu)?126.2s.V丘耽/長餐AEC口EF, MS)里沃33.32S,638,930.4

26、33.6軍干：力M0j中十傅曲俎ha茂同D2ft. 226.429. 62B. 531. 1可雪中格?。簂iiiniiFiis* 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.主域需到一斛，比內(nèi)是所與的為諾度事優(yōu)粉品.報詒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的左側，即 陰影區(qū)域，因為在陰影部分無法使 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優(yōu)先飆亂約束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)根據(jù)題意，先給發(fā)點vs標號，由?。╲s,v2 ）得對v2進行標號（vs,1 ）;?。╲2,v1 ）對v1標號（v2,1 ）; 弧（vs,v3 ）得對 v3 進行標號（vs,1 ）;?。╲3,v4 ）對 v4 標號（v3,1 ）;?。╲3,v4 ） 對 v4 標號（v3,1 ）;?。╲4,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假定最初事件在時刻零出現(xiàn)，則有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作業(yè)(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)課堂作業(yè)1.柴油機生產(chǎn)計劃設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