运筹学胡运权第五版课后答案,运筹作业

1、47 页 1.1bX2用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解47 页 1.1d无界解精选1.2 (b)约束方程的系数矩阵A= 122 1P1 P2341 2P3 P4基基解是否可行解目标函数值X1X2X3X4P1P2-411/200否P1P32/5011/50是43/5P1P4-1/30011/6否P2P301/220是5P2P40-1/202否P3P40011是5最优解 A=(01/220)T 和(0011)T49页13题设Xij为第i月租j个月的面积minz=2800x11+2800x21+2800x31+2800x41+4500x12+4500x22+4500x32

2、+6000x13+6000x23+7300x14s.t.厂 x11+x12+x13+x145x12+x13+x14+x21+x22+x230气 x13+x14+x22+x23+x31+x32 割x14+x23+x32+x41羽2匚 Xij 0用excel求解为：0000000ooooooeHX000000L0000000z丄 soo a3ona3d3nnw3iaVldVA000 旳 14(13D1V A NOI丄ONnd m/l丄93raoedm丄s 丄 vaNnod i/ini/iiido di:搦來oaNn宙X210.0000002800.000000X318.0000000.000000

3、X410.0000001100.000000X120.0000001700.000000X220.0000001700.000000X320.0000000.000000X130.000000400.000000X230.0000001500.000000X1412.0000000.0000002)0.000000-2800.0000003)2.0000000.0000004)0.000000-2800.0000005)0.000000-1700.000000ROW SLACK OR SURPLUSDUAL PRICESNO. ITERATIONS=3答 若使所费租借费用最小，需第一个月租一个

4、月租期300平方米，租四个月租期1200平方米，第三个月租一个月租期 800平方米，50页14题设al, a2, a3, a4, a5分别为在A1, A2, B1, B2, B3加工的I产品数量，bl, b2, b3分别为在A1, A2, B1加工的U产品数量，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 (a3+b3)-0.11(a4+c1)-0.05a5=0. 95a1+0. 97a2+0. 94a3

5、+1.5b3+2.1c1-0.05b1-0.11a4-0.05a5s.t.5a1+10b1 60007a2+b2+12c1w 100006a3+8a3 4000I 4a4+11c1 7000j 7a50用lindo求解得：LP OPTIMUM FOUND AT STEP6DUAL PRICESOBJECTIVE FUNCTION V ALUE1)16342.29VARIABLEVALUEREDUCED COSTA11200.0000000.000000A20.0000009.640000A3285.7142940.000000B310000.0000000.000000C10.00000015

6、.900000B10.0000000.230000A4342.8571470.000000A5571.4285890.000000B2 10000.0000000.0000002)0.0000000.1680003)0.0000001.5000004)0.0000000.0750005)5628.5712890.0000006)0.0000000.0085717)0.0000000.1100008)0.000000-1.500000ROW SLACK OR SURPLUSNO. ITERATIONS=计算lindo截屏Hi EdHl Ik吹 舄邮51精选VALLERENTED l0.00000

7、0(l.OCOOOOft IV+OOOO285.714294O.0QCKJWlOOg OOOQOO0.0000000.000000IB. 9000000. WOQQOO. JOOW342.857147O. 0QOTOO671.420&S&O. 000000IOKM).OAO(XX0.000000*LP QPTI1O AT STEP 6OBJECTbE FtNCTIOX iALlE現 29) E 1 n. 3 3 1 -4 JJ - J nx1 U-A4-A&CBAABAR:ADltf ald I *1F r P 01 L用匸 zmjz 0. 95aHi, 97c2-0. 94zS- , 5b3

8、-2. I c: -C-. D5zl-O. aJD. 05ajIs. t.5e)+J0bl =60007a2+b2+l 2c 10000钿;J+U3W40OO4a441 id =7000倔i=4M0hL城角护Qend.M SLACK OR SLRPLLS DTM FUICE2) 0.0000000.160003) 0.0000001.5000004) 0. OOOOOQO Q7oOOO5J o6JS.5?L2S&0.OQOTOOe)o.oeooooo.(wsftl7)0.0000000.1100009)0. W0WX-L, 300000辄 ITESATKAS-2.1a:对偶问题为：maxz=2

9、y1+3y2+5y3s.t.y1+2y2+y3 w23y3+y2+4y3w 24y1+3y2+3y3=4y1 0, y 2w 0,y3 无约束因为原问题的对偶问题的对偶问题仍是原问题，因此本问题的对偶问题的对偶问题为：minz=2x1+2x2+4x3s.t. x1+3x2+4x3 22x1+x2+3x3w 3*x1+4x2+3x3=5、x1,x2 0,x3 无约束81 页 2.12a)设x1,x2,x3分别为A, B, C产品数量maxz=3x1+x2+4x3s.t.6x1+3x2+5x3 w 453x1+4x2+5x3w 30x1,x2,x3 0用lomdo求解为LP OPTIMUM FOU

10、ND AT STEP2OBJECTIVE FUNCTION V ALUEROW SLACK OR SURPLUSDUAL PRICES1)27.00000VARIABLEVALUEREDUCED COSTX15.0000000.000000X20.0000002.000000X33.0000000.000000X1,X2,X30.0000000.0000002) 0.0000000.2000003) 0.0000000.6000004) 0.0000000.000000NO. ITERATIONS=2|FE| Reporr. WindowLP OPTIWUVFOUND AT STEP2陀 un

11、titledOBJECTIVE FUNCTION VALUEmax 3xBx24x31)27. 000006xl+3x2+5x3=453xl4x2+5x30 end|XI5. 0000000.000000X20. 0000002.000000X33. 000000CL 000000Xh X2t X30. 0000000.000000ROWSLACK OR SURPLUSDUAL BRICES2)0. 0000000. 2000003)0 0000000; 6000004)0. 0000000.000000NO. TTERATTOXS=2最大生产计划为 A 生产 5 个单位， C 生产 3 个单

12、位b)LP OPTIMUM FOUND AT STEP2OBJECTIVE FUNCTION V ALUE1) 27.00000VARIABLEVALUEREDUCED COSTX15.0000000.000000X20.0000002.000000X33.0000000.000000X1,X2,X30.0000000.000000ROWSLACK OR SURPLUSDUAL PRICES2)0.0000000.2000003)0.0000000.6000004)0.0000000.000000NO. ITERATIONS= 2RANGES IN WHICH THE BASIS IS UNC

13、HANGED:VARIABLEOBJ COEFFICIENT RANGESCURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX13.0000001.8000000.600000X21.0000002.000000INFINITYX34.0000001.0000001.500000X1,X2,X30.0000000.000000INFINITYROWRIGHTHAND SIDE RANGESCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE245.00000015.00000015.000000330.00000015

14、.0000007.50000040.0000000.000000INFINITYEP :PTT旳H FCiUKD AT STEPrF.iErrrvE HU-row vt.tt1)VAT. I ABLE27 COCOOVALUEE 000000 c. cooooo 9.000000 r nooonnREDUCED0 OODDOD2.000 303O.OOODODn onriDQiu untitled max 3x1+x2+4x3 s. t 6xl3x2+5x3=453xl+4x2+5x3=0 endl2310 0000000 000000000000DUiil PRICES0,20000)00.

15、600000O.DODDaONO ITEKiTZCNS=ROGEE IN UHICE THEBA5J5 IS VWCHftUGED可知A产品的利润变化范围【6. 8,2.4】，上述计划不变OBJ mEFFTCTENT FiNGESVARIABLEIICUBREffTCOEF3. ooaooo1 LOLUOU4 0000001：.匚(JCIOCIOaLLQVABLE7NCREAF：71 SOOOOt)2 00O0D01 _oonQflL ODOOUODEC?EASz2 SO JOJC1 SDQQOnIHFIillTyCLRFEN7RTGKTHNTi SIDE 抚HGES aLLOVABLKBBS

16、THCREASE：DECREASS15 IOLOOO亠5 .OOUOtlJ DODODU3C COCOOQIE 0000D07 30KOQ匚Qacon 00000TtrFIzJJTYC)设x4为产品D的数量maxz=3x1+x2+4x3+3x4 s.t.6x1+3x2+5x3+8x4w 451 3x1+4x2+5x3+2x4 0用lomdo求解为LP OPTIMUM FOUND AT STEP0OBJECTIVE FUNCTION V ALUE1)27.50000ROW SLACK OR SURPLUSDUAL PRICESVARIABLEVALUEREDUCED COSTX10.000000

17、0.100000X20.0000001.966667X35.0000000.000000X42.5000000.0000002) 0.0000000.2333333) 0.0000000.566667NO. ITERATIONS=0LP 0PI1.ULSJ FOUND Al STEP 2V-OBJECTIVE FLyCTIOX YIUE) E 1 2 3 4L u X X s XAB27.50000阿SLACK OR SURPLUSDL.U PRICES2)0. oooooo0. 2335 333)0. OOOOOO0. 56CC67U0. OOOOOO0. oooooo5)0. OOOOOO

18、0. ooooooG)5 OOOOOOD- OOOOOO7)2. 5000000. ooooooVALUE0. 0000DO0. OOOODO5.OOOOOO2. 500000REDLCEC COSTD. 100000 1.96666,0. OOOOOO0. 0000 0050. ITERATION沪2u titled nmax 3xl+x2+4x3+3x4 s. t.6x1-3k2+5x3+8x4=453xl-4x2+5x3+2x40x3X0x4-0end安排生产D有利，新最有生产计划为x1=x2=0,x3=5,x4=2.5，利润为 27.5d)maxz=3x1+x2+4x3-0.4ys.t

19、.6x1+3x2+5x345y 3x1+4x2+5x3-y 0用lomdo求解为LP OPTIMUM FOUND AT STEP0OBJECTIVE FUNCTION VALUEVARIABLEVALUEREDUCED COSTX10.0000000.600000X20.0000001.800000X39.0000000.0000001)Y15.0000000.00000030.00000ROW SLACK OR SURPLUSDUAL PRICES2) 0.0000000.4000003) 0.0000000.400000NO. ITERATIONS=0FS Recorti 隘 iLinti

20、tledlLF QPTIM1 M FOl NDAT ST5Pmax 3xl+x2+4x3-0. 4yOBJECTIVEHACTIOX VAI IT6xl3x25x3=451)30.000003x1+4x2+5x3-v-0VARIABLEVALUEREDUCED COSTx20XIa 0000000.6000007t3=0y=01llX2Q. 0000001, 800000X39.0000000.00000015.0000000.000000EOW SF ACK CR SUKPLUSDUAL ?RTCES2)o. oooooo0, 4000003)0.0000000. 4000004)0.000

21、000a oooooo5)0.0000000, 0000006)9.0000000. 0000007)15.0000000. 000000X0. ITERATIONS二0可知购进原材料15个单位为宜4.1a)设 yi=1第i组条件起作用- 5+(1-y2)M y1+y2=1 y1,y2=0 或 1b）设yi=1 第i组条件起作用第i组条件不起作用x=0y1c)x=3y2x=5y2x=7y4y1+y2+y3+y4=1y1,y2,y3,y4=0 或 1设yi= 1为假定取值50L-0为假定取值x=0x=0y1x 50-(1-y2)My1+y2=1y1,y2=0 或 1d）设yi= _ 1第i组条件

22、起作用J 0 第i组条件不起作用i=1,2 则厂 x1 1-(1-y1)M 彳 x2W 4+(1-y2)M y1+y2=1j y1,y2=0 或 1e)设yi= 1第i组条件起作用 / 0第i组条件不起作用x1+x25-(1-y1)M x1 2+(1-y3)M x3+x4 6+(1-y4)M y1+y2+y3+y4 2i y1,y2,y3,y4=1 或 0i=1,2 则4.2f 10* minz=- is.t.x1+x8=1x7+x8=1x3+x5 1x4+x5 1 x5+x6+x7+x8xj=AEC)EF臣亦33.329. 2S8.63. 926. 429. &30.42B. S33.631

23、.1王宦111zl213xl.4xlS珑x21xE6IE渝13t132xASx94xS52由凡x41142x43x4E現张王周10 00001 00000 140吕由龙00 0I0E和1 110=1= =1i=L=137.7& 0000必10000oas. 90000 029.6a谢S7.7431 1型金2a.scimJE1JB 4F13-E -二翻ntis-maB* 1号干： 鼻士聞 可匿虫亓稱国”(BflB 1FUB 2选择钻探第sj井位否4.5设xij为第i种泳姿用第名运动员min z=E：= 2；=剧何s.t.厂 x11+x12+x13+x14+x15=1x21+x22+x23+x24

24、+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=1j x15+x25+x35+x45=1xij=1 或 0 (i=1,2,3,4 j=1,2,3,4,5)由excel计算得出；张游仰泳，王游蛙泳，赵游自由泳，预期总成绩为126.2s.赵XllX21L .(1 icu2S. 536.日30. $33G26.429. 628.531. 1钱张112X13122溷王周114X15XZ4酒x32戈33x34耳35i42x

25、-13i44*45観张王周Q10 00 01 01 00 00 00 01 11 0 1 1 03XSQ00 034.7028.500 00 00 028. &33. S3-1.701因为使mind1-，故在x1+x2=40的右侧，若使 mind4+,则在x1+x2=50的左侧，即 阴影区域，因为在阴影部分无法使 2d2-+d3-最小，故比较E (20, 30) ,F (24,26)丘点:d2-=4,d3-=0 min2d2-+d3-=8, F 点:d2-=0,d3-=4, min2d2-+d3-=4,故选 F 占八、程序法tindl-cind4约束P2030正幅差10000040040243

26、0夭系40243050弋先级别约束石124约束屹30正偏埜d14负侑老已-约束C4C关系n:4000C24=240C3C二30001C昶=o0lindl-0ABCDEF,H1化先缭别约束xl约束疋亡任3-長嗚善日-约束2dl242610o40 =403肚0024 -244d30430 =305d40050 =500理划rt第删 常，可币壬h fi的中吧P优就花 抿青腮aiTidl-ai ntU*i : J12d2ta.9L6_.36.4a破圈法倔存方走u .加（EjQ三蓿珂二豆耶罕XU空用if,；37217336424避圈法6精选最小部分树166.4b1072510 1210 12最小部分树3

27、2精选172 页 6.11红色曲线为使用一年卖出蓝色曲线为使用两年卖出绿色曲线为使用三年卖出紫色曲线为使用四年卖出最短路程为 3.7万元，路径为 vO-v1-v4或v0-v2-v4或v0-v1-v2-v4三种方案分别为：第一年年初买新车，年末卖掉再买新车，一直用到第四年年末卖掉；第一年出买新车，用两年后于第二年末卖掉再买新车，用两年于第四年末卖掉；第一年出买新车，年末卖掉后再买新车，第二年末卖掉再买新车，再用两年于第四年年末卖掉。由图可知，若摩托车最多使用三年，答案仍然不变6.14b根据题意，先给发点vs标号，由弧(vs,v2)得对v2进行标号(vs,1);弧(v2,v1 )对v1标号(v2,

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

29、,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,9)=15t ef (8,9)=20t es (5,7)=5t ef (5,7)=7t LF (7,9)=20t ES (4,7)=8 t EF (4,7)=11 t ES (4,6)=8 t EF (4,6)=10 t ES (3,6)=4 t EF (3,6)=12 t ES (6,7)=12 t EF (6,7)=13 t ES (7,9)=13 t EF (7,9)=15 t ES(6,9)=12 t EF (6,9

30、)=19 最短周期为 20 t LF(6,9)= t LF(8,9)= t LS(8,9)=15 t LS(7,9)=16 t LS(6,9)=13 t LF(5,8)=15 t LS(5,8)=8 t LF(5,7)=16 t LS(5,7)=14 t LS(4,7)=10 t LF(4,7)=13t ls(6,7)=15t lf(6,7)=16t ls(4,6)=10t lf(4,6)=13t ls(3,6)=5t lf(3,6)=13t ls(1,3)=1t lf(1,3)=5t ls(1,4)=0t lf(1,4)=8t lf(2,5)=8t ls(2,5)=5t 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)4041510(1 , 4)8080800(,5)3255830(3, 6)841251310(4, 5)0888800(4, 6)2810101332(4, 7)3811101322(5, 7)757141696(5, 8)781581500(6,