運(yùn)籌學(xué)課后習(xí)題解答-1

WORD格式整理版運(yùn)籌學(xué)部分課后習(xí)題解答P471.1用圖解法求解線性規(guī)劃問(wèn)題minz=2x3x124x6x6a）12s.t.4x2x412x,x012解：由圖1可知，該問(wèn)題的可行域?yàn)橥辜疢AB，且C可N知線段BA上的點(diǎn)都為3最優(yōu)解，即該問(wèn)題有無(wú)窮多最優(yōu)解，這時(shí)的最優(yōu)值為z=23032minP471.3用圖解法和單純形法求解線性規(guī)劃問(wèn)題maxz=10x5x123x4x9）a12s.t.5x2x812x,x012解：由圖1可知，該問(wèn)題的可行域?yàn)橥辜疧ABCO，且可知B點(diǎn)為最優(yōu)值點(diǎn)，x13x4x93T1,12即5x2x83，即最優(yōu)解為12x*x2212335z=1015這時(shí)的最優(yōu)值為22max學(xué)習(xí)指導(dǎo)參考WORD格式整理版單純形法：原問(wèn)題化成標(biāo)準(zhǔn)型為maxz=10x5x123x4xx9123s.t.5x2xx8124x,x,x,x01234cj10500bCXx1x2x3x4BB00x93410001038[5]2105x4CZjj0x21/50[14/5]1-3/5310x8/512/501/51CZj010-2j5x3/2015/14-3/14210x110-1/72/71CZj00-5/14-25/14j學(xué)習(xí)指導(dǎo)參考WORD格式整理版3335,z101522T所以有x*1,2maxP782.4已知線性規(guī)劃問(wèn)題：maxz2x4xxx1234x3xx81242xx612xxx6234xxx9x,x,x,x01231234X*(2,2,4,0)，試根據(jù)對(duì)偶求:(1)寫(xiě)出其對(duì)偶問(wèn)題；（2）已知原問(wèn)題最優(yōu)解為理論，直接求出對(duì)偶問(wèn)題的最優(yōu)解。解：（1）該線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題為：minw8y6y6y9y1234y2yy21243yyyy41234yy134yy113y,y,y,y01234（2）由原問(wèn)題最優(yōu)解為*(2,2,4,0)，根據(jù)互補(bǔ)松弛性得：Xy2yy21243yyyy412yy13434把X*(2,2,4,0)代入原線性規(guī)劃問(wèn)題的約束中得第四個(gè)約束取嚴(yán)格不等號(hào)，22489y04即y2y2123yyy4從而有123y13得y4,y53,y1,y051234學(xué)習(xí)指導(dǎo)參考WORD格式整理版所以對(duì)偶問(wèn)題的最優(yōu)解為y*(4,3,1,0)T，最優(yōu)值為w1655minP79考2.7慮如下線性規(guī)劃問(wèn)題：minz60x40x80x1233x2xx21234xx3x41232x2x2x3123x,x,x0123（1）寫(xiě)出其對(duì)偶問(wèn)題；（2）用對(duì)偶單純形法求解原問(wèn)題；解：（1）該線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題為：maxw2y4y3y3123y4y2y601232yy2y40123y3y2y80123y,y,y0123：x,x,x把該線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型（2）在原問(wèn)題加入三個(gè)松弛變量456maxz60x40x80x1233x2xxx212344xx3xx412352x2x2xx31236x0,j1,,6jcj-60-40-80000bCXx1xx3xx5x6BB24000x-2-3-2-11004x-4[-4]-1-30105x-3-2-2-20016CZj-60-40-80000j學(xué)習(xí)指導(dǎo)參考WORD格式整理版0x10-5/45/41-1/120480x111/43/40-1/4010x-106[-3/2]-1/20-1/21CZj0-25-350-150j0x11/6005/311/3-5/6480x5/6102/30-1/31/61/301/3-2/3140xCZ2/301200-80/30-20/3-50/3jjx*(,,0)T,z6054028005223063633maxP812.12某廠生產(chǎn)A、B、C三種產(chǎn)品，其所需勞動(dòng)力、材料等有關(guān)數(shù)據(jù)見(jiàn)下表。要求：（a）確定獲利最大的產(chǎn)品生產(chǎn)計(jì)劃；（b）產(chǎn)品A的利潤(rùn)在什么范圍內(nèi)變動(dòng)時(shí)，上述最優(yōu)計(jì)劃不變；（c）如果設(shè)計(jì)一種新產(chǎn)品D，單件勞動(dòng)力消耗為8單位，材料消耗為2單位，每件可獲利3元，問(wèn)該種產(chǎn)品是否值得生產(chǎn)？（d）如果勞動(dòng)力數(shù)量不增，材料不足時(shí)可從市場(chǎng)購(gòu)買(mǎi)，每單位0.4元。問(wèn)該廠要不要購(gòu)進(jìn)原材料擴(kuò)大生產(chǎn)，以購(gòu)多少為宜。ABC可用量（單位）消耗產(chǎn)品定額資源勞動(dòng)力材料63454553013產(chǎn)品利潤(rùn)（元/件）34學(xué)習(xí)指導(dǎo)參考WORD格式整理版解：由已知可得，設(shè)x表示第j種產(chǎn)品，從而模型為：jmaxz3xx4x3126x3x5x45123s.t.3x4x5x30123x,x,x0123a)用單純形法求解上述模型為：cj31400bCXx1xx3xx5BB2400x45635104x3034[5]0105CZj3140jjj04x15[3]-101-14x633/54/5101/5CZj3/5-11/50-1/300-4/534x1511/3-1/3x30311-1/52/5CZj0-20-1/5-3/5x(5,0,3)T；最優(yōu)值為z354327得到最優(yōu)解為*maxb）設(shè)產(chǎn)品A的利潤(rùn)為3，則上述模型中目標(biāo)函數(shù)x的系數(shù)用3替代并求1解得：3cj1400CXbxxx3xx5BB1243x511-1/301/3-1/3學(xué)習(xí)指導(dǎo)參考WORD格式整理版4x33011-1/52/5CZj-20-1/5-3/5jCZ-2+/30-1/5-/3-3/5+/30jj要最優(yōu)計(jì)劃不變，要求有如下的不等式方程組成立20310解得：935355305333,39242,4從而產(chǎn)品A的利潤(rùn)變化范圍為：55,即55C）設(shè)產(chǎn)品D用x表示，從已知可得6ccB1P1/5B666112833P'B1P412255665把x加入上述模型中求解得：6cj314003bCXx1x2x3x4x5x6BB34x53100-1/301/3-1/3[2]111-1/52/5-4/5x3CZj-20-1/5-3/51/51/6-1/61j3x65/21/2-1/60學(xué)習(xí)指導(dǎo)參考WORD格式整理版4x352/513/151-1/154/150CZj-1/10-59/300-7/30-17/300jx(0,0,5,0,0,5/2)T；最優(yōu)值為z453527.527從而得最優(yōu)解*2max所以產(chǎn)品D值得生產(chǎn)。d）學(xué)習(xí)指導(dǎo)參考WORD格式整理版學(xué)習(xí)指導(dǎo)參考WORD格式整理版P101已3.1知運(yùn)輸問(wèn)題的產(chǎn)銷(xiāo)量與單位運(yùn)價(jià)如下表所示，用表上作業(yè)法求各題的最優(yōu)解及最小運(yùn)費(fèi)。表3-35銷(xiāo)地BBBB4產(chǎn)量產(chǎn)地123A101227201115920251A2A214161853銷(xiāo)量5151510解：由已知和最小元素法可得初始方案為銷(xiāo)地B1B2150B3B4產(chǎn)量產(chǎn)地A115A2A3150102555銷(xiāo)量5151510檢驗(yàn)：學(xué)習(xí)指導(dǎo)參考WORD格式整理版由于有兩個(gè)檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整一：產(chǎn)地銷(xiāo)地B1B2B3B4產(chǎn)量A11501515102505A2A35銷(xiāo)量5151510檢驗(yàn)：由于還有檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整二：銷(xiāo)地B1B25B3B410產(chǎn)量1525產(chǎn)地A1A2A31015505學(xué)習(xí)指導(dǎo)參考WORD格式整理版銷(xiāo)量5151510檢驗(yàn)：從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案z25257109151110180335min最小運(yùn)費(fèi)為：表3-36銷(xiāo)地BBBB產(chǎn)量產(chǎn)地1234A841A69144277252A53326153銷(xiāo)量10102034a58b55，即產(chǎn)大于銷(xiāo)，所以需添加一個(gè)假想的銷(xiāo)地，銷(xiāo)解：因?yàn)閕ji1j1量為3，構(gòu)成產(chǎn)銷(xiāo)平衡問(wèn)題，其對(duì)應(yīng)各銷(xiāo)地的單位運(yùn)費(fèi)都為0。銷(xiāo)地B1B2B3B4B5產(chǎn)量7產(chǎn)地841207A16593443A2A3025026銷(xiāo)量101020153由上表和最小元素法可得初始方案為學(xué)習(xí)指導(dǎo)參考WORD格式整理版銷(xiāo)地B1B2B37B4B5產(chǎn)量7產(chǎn)地A1A2913325A31101526銷(xiāo)量101020153檢驗(yàn)：從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案z69513101741331503193min最小運(yùn)費(fèi)為：表3-37銷(xiāo)地產(chǎn)地B18B26B33B47B5產(chǎn)量A1A2A35205M847303063968銷(xiāo)量252520102035a80b100，即銷(xiāo)大于產(chǎn)，所以需添加一個(gè)假想的產(chǎn)地，產(chǎn)解：因?yàn)閕ji1j1學(xué)習(xí)指導(dǎo)參考WORD格式整理版量為20，構(gòu)成產(chǎn)銷(xiāo)平衡問(wèn)題，其對(duì)應(yīng)各銷(xiāo)地的單位運(yùn)費(fèi)都為0。銷(xiāo)地B18B26B33B47B55產(chǎn)量20303020產(chǎn)地A1A2A3A4銷(xiāo)量5M84763968000002525201020由上表和最小元素法可得初始方案為銷(xiāo)地B15B2B320B410B5產(chǎn)量20303020產(chǎn)地A1A2A3A415525200銷(xiāo)量2525201020檢驗(yàn)：由于有兩個(gè)檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整一：學(xué)習(xí)指導(dǎo)參考WORD格式整理版銷(xiāo)地B1B2B3B420B5產(chǎn)量20產(chǎn)地A1A2201030530A325A4501520銷(xiāo)量2525201020檢驗(yàn)：由于還有檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整二：銷(xiāo)地B1B2B3B4B5產(chǎn)量產(chǎn)地A120201030030A220A3525A402020銷(xiāo)量2525201020檢驗(yàn)：學(xué)習(xí)指導(dǎo)參考WORD格式整理版從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案z320520410653258002000305min最小運(yùn)費(fèi)為：P127用4.8割平面法求解整數(shù)規(guī)劃問(wèn)題。maxz7x9x12x3x6a）127xx3512x,x0,且為整數(shù)12解：該問(wèn)題的松弛問(wèn)題為：maxz7x9x12x3x6127xx3512x,x012則單純形法求解該松弛問(wèn)題得最后一單純形表為：cj7900bCXx1xx3x4BB29x7/2017/221/2227x9/210-1/223/221CZ00-28/1-15/11jj(31/2)x(07/22)x(01/22)x割平面1為：234學(xué)習(xí)指導(dǎo)參考WORD格式整理版12227x221xx30227x221xx12342345從而有c79000jbCXxxx2x4x5BB139x7/2017/221/22027x9/210-1/223/22010x-1/200-7/22-1/2215CZ00-28/1-15/110010017x32/71001/7-1/7jj9x3210x11/70011/7-22/73CZ000-1-8jj(44/7)x(01/7)x(16/7)x5割平面2為：14xxxx4071xxx44166777774515456c790003jbCXx1x2x3x4x5x6BB9x301001027x32/71001/7-1/7011/7-22/700-1/7-6/7110x11/70030x-4/7006CZ000-1-80jj9x30100102學(xué)習(xí)指導(dǎo)參考WORD格式整理版7x410x100100016-7CZ0000-2-7000-1110-4130x44jj由上表可知該問(wèn)題已經(jīng)達(dá)到整數(shù)解了，所以該整數(shù)解就是原問(wèn)題的最優(yōu)解，即x*4,3T，最優(yōu)值為z749355maxP144用5.3圖解分析法求目標(biāo)規(guī)劃模型minZ=Pd-+Pd++P（2d-+1d4-）1122x+x+d--d+=4033c）1211x+x+d--d+=40+10=501222+d--d+=2433x+d--d+=30s.t.x1244x、x、d、d、d、d、d、d、d、d-≥0+1-1+2-2+3-3+4124解:由下圖可知，滿足目標(biāo)函數(shù)的滿意解為圖中的A點(diǎn)。P170求6.4下圖中的最小樹(shù)學(xué)習(xí)指導(dǎo)參考WORD格式整理版解：避圈法為：得到最小樹(shù)為：P171用6.7標(biāo)號(hào)法求下圖中點(diǎn)v1到各點(diǎn)的最短路。學(xué)習(xí)指導(dǎo)參考WORD格式整理版解：如下圖所示：vvP1736.14用Ford-Fulkerson的標(biāo)號(hào)算法求下圖中所示各容量網(wǎng)絡(luò)中從s到t的最大流，并標(biāo)出其最小割集。圖中各弧旁數(shù)字為容量c，括弧中為流量f.ijijB)解：對(duì)上有向圖進(jìn)行2F標(biāo)號(hào)得到學(xué)習(xí)指導(dǎo)參考WORD