第四版運(yùn)籌學(xué)部分課后習(xí)題解答模板

1、運(yùn)籌學(xué)部分課后習(xí)題解答P471.1用圖解法求解線性規(guī)劃問題minz=2x+3x1 2a)4x+6x>612s.t<4x+2x>412x,x>0v12解：由圖1可知，該問題的可行域?yàn)橥辜疢ABCN,且可知線段BA上的點(diǎn)都為3最優(yōu)解，即該問題有無窮多最優(yōu)解，這時的最優(yōu)值為z=2x+3x0=3min2P471.3用圖解法和單純形法求解線性規(guī)劃問題maxz=10x+5x12、3x+4x<9a)12s.t<5x+2x<812x,x>0v123x+4x=9x=1113<12二<3，即最優(yōu)解為x*=l,315x+2x=8x=L2丿11222解：由圖

2、1可知，該問題的可行域?yàn)橥辜疧ABCO，且可知B點(diǎn)為最優(yōu)值點(diǎn),T即3 35這時的最優(yōu)值為Zmax=10X1+5X=兀圖1單純形法:原問題化成標(biāo)準(zhǔn)型為maxz=10x+5x123x+4x+x=9123s.t<5x+2x+x=8124x,x,x,x>01234cTj10500CBXBbx1x2x3x40x3934100x485201C-Zjj105000x321/5014/51-3/510x18/512/501/5C-Zjj010-25x23/2015/14-3/1410x1110-1/72/7C-Zjj00-5/14-25/14所以有x*=T,z=10x1+5x-=-5max22P7

3、82.4已知線性規(guī)劃問題:maxz=2x+4x+x+x1234x+3x+x<81242 x+x<612x+x+x<62 34x+x+x<9123x,x,x,x>01234求：寫出其對偶問題；(2)已知原問題最優(yōu)解為X*二(2,2,4,0)，試根據(jù)對偶理論，直接求出對偶問題的最優(yōu)解。解：(1)該線性規(guī)劃問題的對偶問題為:minw=8y+6y+6y+9y1234'y+2y+y>21243 y+y+y+y>41234y+y>13 4y+y>113y,y,y,y>01234(2)由原問題最優(yōu)解為X*=(2,2,4,0)，根據(jù)互補(bǔ)松弛性

4、得:y+2y+y=2124<3y+y+y+y=41234y+y=1J34把X*=(2,2,4,0)代入原線性規(guī)劃問題的約束中得第四個約束取嚴(yán)格不等號,即2+2+4二8<9ny二04y+2y=212從而有<3y+y+y=4123y=1J3z43得y=,y=,y=1,y=01525344 3所以對偶問題的最優(yōu)解為y*=(-,-,1,0)t，最優(yōu)值為w=165 5minP792.7考慮如下線性規(guī)劃問題：minz=60x+40x+80x1233x+2x+x>21234x+x+3x>4V1232x+2x+2x>3123x,x,x>0J123（1）寫出其對偶問題；

5、（2）用對偶單純形法求解原問題;解：(1)該線性規(guī)劃問題的對偶問題為:maxw=2y+4y+3y123”3y+4y+2y<601232y+y+2y<40V123y+3y+2y<80123y,y,y>0J123(2)在原問題加入三個松弛變量x,x,x把該線性規(guī)劃問題化為標(biāo)準(zhǔn)型:4 56maxz=-60x-40x-80x1233x-2xx+x=212344x-x3x+x=412352x-2x2x+x=31236x>0,j=1,6jCTj-60-40-80-000CBXBbx1x2x3x4x5x60x4-2-3-2-11000x5-4-4-1-30100x6-3-2-2

6、-2001CZjj-60-40-800000x410-5/45/41-1/12080x1111/43/40-1/400x6-10-3/2-1/20-1/21C-Zjj0-25-350-1500x411/6005/311/3-5/680x15/6102/30-1/31/640x22/3011/301/3-2/3C-Zjj00-80/30-20/3-50/3x*=(5,2,O)T,Z=60X5+40X-+80X0=23063max633P812.12某廠生產(chǎn)A、B、C三種產(chǎn)品，其所需勞動力、材料等有關(guān)數(shù)據(jù)見下表。要求：（a）確定獲利最大的產(chǎn)品生產(chǎn)計(jì)劃；（b）產(chǎn)品A的利潤在什么范圍內(nèi)變動時，上述最優(yōu)

7、計(jì)劃不變；（c）如果設(shè)計(jì)一種新產(chǎn)品D,單件勞動力消耗為8單位，材料消耗為2單位，每件可獲利3元，問該種產(chǎn)品是否值得生產(chǎn)？（d）如果勞動力數(shù)量不增，材料不足時可從市場購買，每單位0.4元。問該廠要不要購進(jìn)原材料擴(kuò)大生產(chǎn)，以購多少為宜。消產(chǎn)品定額、資源ABC可用量（單位）勞動力63545材料34530產(chǎn)品利潤（元/件）314解：由已知可得，設(shè)x表示第j種產(chǎn)品，從而模型為:jmaxz=3x+x+4x1236x+3x+5x<45123s.t3x+4x+5x<30123x,x,x>0v123a)用單純形法求解上述模型為:cTj31400CBXBbx1x2x3x4x50x44563510

8、0x53034501C-Zjj314000x4153-101-14x363/54/5101/5C-Zjj3/5-11/500-4/53x151-1/301/3-1/34x33011-1/52/5C-Zjj0-20-1/5-3/5得到最優(yōu)解為x*二(5,0,3)T；最優(yōu)值為z二3X5+4X3二27maxb)設(shè)產(chǎn)品A的利潤為3+九，則上述模型中目標(biāo)函數(shù)x的系數(shù)用3+九替代并求1解得:cTj3+九1400CBXBbx1x2x3x4x53xi51-1/301/3-1/34x33011-1/52/5C-Zjj九-20-1/5-3/5（C-Z）jj0-2+九/30-1/5-九/3-3/5+九/3要最優(yōu)計(jì)劃

9、不變，要求有如下的不等式方程組成立2+-<03<0解得:533+d05 339124從而產(chǎn)品A的利潤變化范圍為：3-,3+9，即2-,4-C）設(shè)產(chǎn)品D用x表示，從已知可得6b=ccB-1P=1/566B6把x加入上述模型中求解得:6cTj314003CBXBbx1x2x3x4x5x63x151-1/301/3-1/324x33011-1/52/5-4/5CZjj0-20-1/5-3/51/53x65/21/2-1/601/6-1/614x352/513/151-1/154/150CZjj-1/10-59/300-7/30-17/300從而得最優(yōu)解x*二(0,0,5,0,0,5/2)

10、t；最優(yōu)值為z=4x5+3x-=27.5>27max2所以產(chǎn)品D值得生產(chǎn)。d）由晚諭才勺他檢旬3T'聊“盧甩十門0.9入伙;氓策入謝川哄梆性）X”M/X,杓TL31(0'匕Z>PT-入w庁>2-命處耒池增杯十詞當(dāng)入兀于-扌入9切P1013.1已知運(yùn)輸問題的產(chǎn)銷量與單位運(yùn)價如下表所示，用表上作業(yè)法求各題的最優(yōu)解及最小運(yùn)費(fèi)。表335檢驗(yàn):檢驗(yàn):解：因?yàn)楣二工b，即產(chǎn)銷平衡所以由已知和最小元素法可得初始方案為ElB2B3B4行位勢A1訓(xùn)釣2151A2015出1016A3呂5四辺禺0調(diào)Q)13列位勢-111314由于有兩個檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整一:逬BlB2

11、B3B4行位勢A11A2調(diào)I02115紉106A3勺5訓(xùn)04列位勢-21314由于還有檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整二:檢驗(yàn):逬BlE2B3B4行位勢A15竺Ulio1A210152他6A3©觀08列位勢-61L310從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案最小運(yùn)費(fèi)為：z二2X5+2X5+7X10+9x15+11x10+18x0二335min解：因?yàn)楣二58工b二55，即產(chǎn)大于銷，所以需添加一個假想的銷地，銷i=1j=1量為3,構(gòu)成產(chǎn)銷平衡問題，其對應(yīng)各銷地的單位運(yùn)費(fèi)都為0。A1841207A26947025A35343026銷量101020153產(chǎn)量B1B2B3B4B5產(chǎn)

12、地地由上表和最小元素法可得初始方案為檢驗(yàn):BlB2B3B4B5行位勢A17©包1A269引哲130T34A3|J1101315%3列位勢2000-4從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案最小運(yùn)費(fèi)為：z二6X9+5X1+3X10+lx7+4x13+3x15+0x3二193min解：因?yàn)楣二80工b二100，即銷大于產(chǎn)，所以需添加一個假想的產(chǎn)地，產(chǎn)iji=1j=1量為20,構(gòu)成產(chǎn)銷平衡問題，其對應(yīng)各銷地的單位運(yùn)費(fèi)都為0。:地銷地B1B2B3B4B5產(chǎn)量A18637520A25M84730A36396830A40000020銷量2525201020由上表和最小元素法可得初始方案

13、為檢驗(yàn):O-由于有兩個檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整一:B4©©5創(chuàng)邑6-O-'lfp=lIII52由于還有檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整二:沁B1B2B3B4B5產(chǎn)量A12020A2201030A3525030A402020銷量2525201020檢驗(yàn):ElB2B3B4B5行位勢A1A2A3A48j(+7)(+8)201(+7)(+2)1065創(chuàng)259)(+j)創(chuàng)00(+|)2i(+5)2o型包型204891列位勢-3-6-1-4-1從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案最小運(yùn)費(fèi)為：z二3X20+5X20+4X10+6x5+3x25+8x0+0x20+0

14、x0二305minP1274.8用割平面法求解整數(shù)規(guī)劃問題。maxz=7x+9x12a)解：該問題的松弛問題為:-x+3x<612<7x+x<3512x,x>0,且為整數(shù)J12maxz=7x+9x12-x+3x<612<7x+x<3512x,x>0v12則單純形法求解該松弛問題得最后一單純形表為:cTj7900CBXBbx1x2x3x49x27/2017/221/227x19/210-1/223/22CZjj00-28/11-15/11割平面1為：(3+1/2)二x+(0+7/22)x+(0+1/22)x2341 71cc711xxx3W0x+x

15、x2 223224222322452從而有cTj79000CBXBbx1x2x3x4x59x27/2017/221/2207x19/210-1/223/2200x5-1/200-7/22-1/221CZjj00-28/11-15/1109x23010017x132/71001/7-1/70x311/70011/7-22/7CZjj000-1-8割平面2為：(4+4/7)x+(0+1/7)x+(-1+6/7)x1454 16164一一一x一xx一x一4<0x+x一x7747515747567CTj790003cBXBbX1X2X3X4X5X69X230100107X132/71001/7-

16、1/700X311/70011/7-22/700X6-4/7000-1/7-6/71C-Zjj000-1-809X230100107X141000-110X310010-410X4400016-7C-Zjj0000-2-7由上表可知該問題已經(jīng)達(dá)到整數(shù)解了，所以該整數(shù)解就是原問題的最優(yōu)解，即X*=(4,3»，最優(yōu)值為z二7X4+9X3二55maxP1445.3用圖解分析法求目標(biāo)規(guī)劃模型c）minZ=Pd+Pd+P（2d-+1d-）rx+i+di也+=40%“丿x1+x2+d2-df=40+10=50st*X+df-d3+=24x2+d-d4+=30244Xi、X2、q+、di"

17、;、df、d2>4+、d3、d4+、d4-$0解：由下圖可知，滿足mind1-的滿意解為區(qū)域X2CDX1；滿足mindg+的滿意解為閉區(qū)域bcdeb；滿足min2q-的滿意解為圖中的A點(diǎn)，滿足minq-的滿意解為圖中的A點(diǎn)，所以該問題的滿意解為圖中的點(diǎn)A(24,26)x2xl用圖解分析法求目標(biāo)規(guī)劃模型minz=Pd+Pd+Pd+112332x+2x+d一一d+=41211x2x+dd+=4<1222x+2x+dd+=81233x,x>0;d、d+>0i=1,2,3'12ii的滿意解。解：由下圖可知，滿足mind+的滿意解為區(qū)域CDOA；1滿足mind+的滿意解為

18、閉區(qū)域MCDOM；3滿足mind+的滿意解為圖中的陰影部分，即為圖中的凸多邊形OABCDO。2P1706.4求下圖中的最小樹12L/><A/7-.></*6F解：避圈法為：(1) %=僅巴=3,匚9耳尺&丹(2) %=仇呂代=©門眉屮口丹=(A,B,Gy2=(C,D,E,F,H(4)=A,B,G,C)y2=D,E,F,HQ)V=AEU6DS=E,玖咼(6)=A,B,G,C,D,Ey2=F,H=(A,B,G,C,D,E,Hy2=F%=F,H九=$得到最小樹為：解：如下圖所示:10113714比、0117卩48P1736.14用Ford-Fulkerson

19、的標(biāo)號算法求下圖中所示各容量網(wǎng)絡(luò)中從Vs到"t的最大流，并標(biāo)出其最小割集。圖中各弧旁數(shù)字為容量c，括弧中為流量f.B)解：對上有向圖進(jìn)行2F標(biāo)號得到(0,co5(5)(3)51)為)5)Vif1)2i2C2)5141川4(4由于所有點(diǎn)都被標(biāo)號了，即可以找到增廣鏈，所以流量還可以調(diào)整，調(diào)整量為1,所以已經(jīng)是最大流了，最大流量等于最小割的容量，最小由圖可知，標(biāo)號中斷，割為與直線KK相交的弧的集合，即為(v,v),(v,v),(v,v),(v,v),(v,v),(v,vs3s4s51t2t23所以從v到v的最大流為：f*二1+2+5+3+2+1二14ststC)5t5)8(6)4(4)2(0)2(0)2C2)6(6)6解：對上有向圖進(jìn)行2