![第四版運(yùn)籌學(xué)部分課后習(xí)題解答_第1頁](http://file2.renrendoc.com/fileroot_temp3/2021-11/5/6887932d-bead-47a8-9f1c-2cf2c122a814/6887932d-bead-47a8-9f1c-2cf2c122a8141.gif)
![第四版運(yùn)籌學(xué)部分課后習(xí)題解答_第2頁](http://file2.renrendoc.com/fileroot_temp3/2021-11/5/6887932d-bead-47a8-9f1c-2cf2c122a814/6887932d-bead-47a8-9f1c-2cf2c122a8142.gif)
![第四版運(yùn)籌學(xué)部分課后習(xí)題解答_第3頁](http://file2.renrendoc.com/fileroot_temp3/2021-11/5/6887932d-bead-47a8-9f1c-2cf2c122a814/6887932d-bead-47a8-9f1c-2cf2c122a8143.gif)
![第四版運(yùn)籌學(xué)部分課后習(xí)題解答_第4頁](http://file2.renrendoc.com/fileroot_temp3/2021-11/5/6887932d-bead-47a8-9f1c-2cf2c122a814/6887932d-bead-47a8-9f1c-2cf2c122a8144.gif)
![第四版運(yùn)籌學(xué)部分課后習(xí)題解答_第5頁](http://file2.renrendoc.com/fileroot_temp3/2021-11/5/6887932d-bead-47a8-9f1c-2cf2c122a814/6887932d-bead-47a8-9f1c-2cf2c122a8145.gif)
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、運(yùn)籌學(xué)部分課后習(xí)題解答P47用圖解法求解線性規(guī)劃問題min z=2x 3x2、4為 6x26a )st 4為 2x24x1,x20解:由圖1可知,該問題的可行域?yàn)橥辜?MABC,且可知線段BA上的點(diǎn)都為3最優(yōu)解,即該問題有無窮多最優(yōu)解,這時(shí)的最優(yōu)值為Zmin =2 -30322P47用圖解法和單純形法求解線性規(guī)劃問題max z=10x.| 5x2、3為 4x2 9a )s.t 5為 2x28x1, x? 0T1,32解:由圖1可知,該問題的可行域?yàn)橥辜?OABCO且可知B點(diǎn)為最優(yōu)值點(diǎn),即3x1 4x2 91 3,即最優(yōu)解為x*5x1 2x2 8x2這時(shí)的最優(yōu)值為Zmax = 1。1 5| 35
2、Tv1圖1單純形法:原問題化成標(biāo)準(zhǔn)型為max z=10x1 5x23 4x2 x39s.t 5 2x2 x4 8Cj10500CbXbbX1X2X3X40X3934100x485201Cj Zj105000X321/5014/51-3/510Xi8/512/501/5Cj Zj010-25X23/2015/14-3/1410Xi110-1/72/7Cj Zj00-5/14-25/14Xi,X2,X3,X40maxz2為4x2X3X4X13x2X482咅x26x2x3x46xx2x39xz,X3, X40所以有x*13101 5 i35"2P78已知線性規(guī)劃問題:求:(1)寫出其對(duì)偶問
3、題;(2)已知原問題最優(yōu)解為X* (2,2,4,0),試根據(jù)對(duì)偶理論,直接求出對(duì)偶問題的最優(yōu)解。解:(1)該線性規(guī)劃問題的對(duì)偶問題為:(2)minw8y16y26y39y4y12 y2y423y1y2y3y44y3y41y1y31y1, y2,y3,y40由原問題最優(yōu)解為*X(2,2,42),根據(jù)互補(bǔ)松弛性得y12 y2y423y1 y2y3y44y3y41把X*(2,2,4,0)代入原線性規(guī)劃問題的約束中得第四個(gè)約束取嚴(yán)格不等號(hào),即2 2 489目40y12 y22從而有3y1y2y34y3 1得y4得Y15,Y235山1,V40所以對(duì)偶冋題的最優(yōu)解為y( ,3,1,0)T,最優(yōu)值為Wmin
4、165 5P79考慮如下線性規(guī)劃問題:min z 60xi 40x2 80x33xi 2x2 X324xi X2 3x342xi 2x2 2x3 3xi,x?,x30(1)寫出其對(duì)偶問題;(2)用對(duì)偶單純形法求解原問題;解:(1)該線性規(guī)劃問題的對(duì)偶問題為:max w 2% 4y2 3y33% 4y2 2y3602yi y2 2y340,yi 3y2 2y380%也30(2)在原問題加入三個(gè)松弛變量X4,X5,X6把該線性規(guī)劃問題化為標(biāo)準(zhǔn)型max z60x1 40x2 80x33x12x2X3X424x-iX23x3X542為2x22x3X63Xj0,j1L ,6Cj-60-40-80000C
5、bXbbX1X2X3X4X5X60X4-2-3-2-11000X5-4-4-1-30100X6-3-2-2-2001Cj Zj-60-40-800000X410-5/45/41-1/12080X1111/43/40-1/400X6-10-3/2-1/20-1/21CjZj0-25-350-1500X411/6005/311/3-5/680X15/6102/30-1/31/640X22/3011/301/3-2/3CjZj00-80/30-20/3-50/3x* (5,-,0)T,Zmax 60 5 40 ? 80 0 空6 3633P81某廠生產(chǎn)A B C三種產(chǎn)品,其所需勞動(dòng)力、材料等有關(guān)數(shù)據(jù)
6、見下表。 要求:(a)確定獲利最大的產(chǎn)品生產(chǎn)計(jì)劃;(b)產(chǎn)品A的利潤在什么范圍內(nèi)變動(dòng) 時(shí),上述最優(yōu)計(jì)劃不變;(c)如果設(shè)計(jì)一種新產(chǎn)品D,單件勞動(dòng)力消耗為8單位, 材料消耗為2單位,每件可獲利3元,問該種產(chǎn)品是否值得生產(chǎn)?(d)如果勞動(dòng)力數(shù)量不增,材料不足時(shí)可從市場(chǎng)購買,每單位元。問該廠要不要購進(jìn)原材料擴(kuò)大生產(chǎn),以購多少為宜。消耗產(chǎn)品ABC可用量(單位)定 額勞動(dòng)力63545材料34530產(chǎn)品利潤(元/件)314解:由已知可得,設(shè)Xj表示第j種產(chǎn)品,從而模型為:max z 3為 x2 4x36Xj 3x2 5x345st 3 4x2 5x330為KX 0a)用單純形法求解上述模型為:Cj3140
7、0CbXbbXiX2X3X4X50X445635100X53034501Cj Zj314000X4153-101-14X363/54/5101/5Cj Zj3/5-11/500-4/53Xi51-1/301/3-1/34X33011-1/52/5Cj Zj0-20-1/5-3/5得到最優(yōu)解為x*(5,0,3)T ;最優(yōu)值為Zmax3 5 4 327b )設(shè)產(chǎn)品A的利潤為3,則上述模型中目標(biāo)函數(shù)xi的系數(shù)用3替代并求解得:Cj31400CbXbbX1X2X3X4X53X51-1/301/3-1/34X33011-1/52/5Cj Zj-20-1/5-3/5CjZj0-2+/30-1/5-/3-3
8、/5+/3要最優(yōu)計(jì)劃不變,要求有如下的不等式方程組成立01-0解得:395355305323從而產(chǎn)品A的利潤變化范圍為:3 3,3 9 ,即22,445555C)設(shè)產(chǎn)品D用X6表示,從已知可得16 C6 CB B P61/5P' B 1P6把X6加入上述模型中求解得:Cj314003CbXbbX1X2X3X4X5X63X151-1/301/3-1/324X33011-1/52/5-4/5Cj Zj0-20-1/5-3/51/53X65/21/2-1/601/6-1/614X352/513/151-1/154/150Cj Zj-1/10-59/300-7/30-17/300c從而得最優(yōu)解
9、 x*(0,0,5,0,0,5 /2)t ;最優(yōu)值為 zmax4 5 327.5272所以產(chǎn)品D值得生產(chǎn)。由必存冷許令粘才込弭力眩為 k * 聲、(才t入為嗾訥處1切上卜撈乙f寸I一L、入少3十亍入=0f F 'l 卩I/匕門L vlxk 6 -A ?門» 2氐 r百壯入f “ -f入#25和期認(rèn)歲冋5 2宀F 風(fēng)惋冰茂嗆也吟抽4% A瀾1沖星訃"P101已知運(yùn)輸問題的產(chǎn)銷量與單位運(yùn)價(jià)如下表所示,用表上作業(yè)法求各題的最 優(yōu)解及最小運(yùn)費(fèi)。表 3-3534解:因?yàn)閍ibj ,即產(chǎn)銷平衡所以由已知和最小元素法可得初始方案為檢驗(yàn):B1B2B3M行位勢(shì)A1A2A3創(chuàng)釣2115
10、 20勺5珂迪訶0訶O16列位勢(shì)-1113/由于有兩個(gè)檢驗(yàn)數(shù)小于零,所以需調(diào)整,調(diào)整一:產(chǎn)地銷地B1B2B3B4產(chǎn)量A11515A20151025A3505銷量5151510檢驗(yàn):進(jìn)BlB!B3刑行位幫A1A215 更 珂®勺0 1 百5訶刨15 出 10 訶0164列位勢(shì)-2 1314由于還有檢驗(yàn)數(shù)小于零,所以需調(diào)整,調(diào)整二:檢驗(yàn):B1B2EjA1辿11A2156A32列位勢(shì)-61310從上表可以看出所有的檢驗(yàn)數(shù)都大于零,即為最優(yōu)方案最小運(yùn)費(fèi)為:Zmin 2 5 2 5 7 10 9 15 11 10 18 0335表 3-36A84127A694725A534326銷量10102
11、015B2584bj產(chǎn)地銷地B4產(chǎn)量3解:因?yàn)閍ii 155,即產(chǎn)大于銷,所以需添加一個(gè)假想的銷地,銷j 1量為3,構(gòu)成產(chǎn)銷平衡問題,其對(duì)應(yīng)各銷地的單位運(yùn)費(fèi)都為0銷地 r地xTB1B2B3B4B5產(chǎn)量A1841207A26947025A35343026銷量 101020153由上表和最小元素法可得初始方案為檢驗(yàn):B1E2B3別BE行便勢(shì)A1)修17211413Q1 34A35 110315%3列位勢(shì)2000-4從上表可以看出所有的檢驗(yàn)數(shù)都大于零,即為最優(yōu)方案最小運(yùn)費(fèi)為:zmin 6 9 5 1 3 10 1 7 4 13 3 15 0 3 193解:因?yàn)閍i 80bj 100,即銷大于產(chǎn),所以
12、需添加一個(gè)假想的產(chǎn)地,產(chǎn)i 1j 1銷地 產(chǎn)地范B1B2B3B4B5產(chǎn)量A18637520A25M84730A36396830A40000020銷量2525201020量為20,構(gòu)成產(chǎn)銷平衡問題,其對(duì)應(yīng)各銷地的單位運(yùn)費(fèi)都為0o由上表和最小元素法可得初始方案為檢驗(yàn):進(jìn)BlB2B5行位勢(shì)A1創(chuàng)戛320Il g)1U2邑5臨甩3A36|259呃£ 54A4o2O 21 (+|),00咆翌-2列位勢(shì)2 -1214由于有兩個(gè)檢驗(yàn)數(shù)小于零,所以需調(diào)整,調(diào)整一:銷地 產(chǎn)地WB1B2B3B4B5-r、曰. 產(chǎn)量A12020A2201030A325530A401520銷量2525201020檢驗(yàn):逬E
13、1B2 I5B4B5行位勢(shì)A1201A252(363%護(hù)25 g6A4210型15- 2列位勢(shì)2-3212由于還有檢驗(yàn)數(shù)小于零,所以需調(diào)整,調(diào)整二:銷地B1B2B3B4B5產(chǎn)量A12020A2201030A3525030A402020銷量2525201020檢驗(yàn):31E2I!3B4B5行位勢(shì)A1 血A4導(dǎo)p3 5j20M|85 25 220 U(+7)3包) 10 刃(g)(g) 6|Q) s 0 0 204891列位勢(shì)- 3-6-1-4-1從上表可以看出所有的檢驗(yàn)數(shù)都大于零,即為最優(yōu)方案最小運(yùn)費(fèi)為:zmin 3 20 5 20 4 10 6 5 3 25 8 0 0 20 0 0305P12
14、7用割平面法求解整數(shù)規(guī)劃問題max z 7x1 9x2x. 3x26a)°27% x2 35Xi,X20,且為整數(shù)解:該問題的松弛問題為:max z 7x. 9x2Xi 3x267xi X2 35x.,x20則單純形法求解該松弛問題得最后一單純形表為:Cj7900CbXbbX1X2X3X49X27/2017/221/227X19/210-1/223/22Cj Zj00-28/11-15/11割平面 1 為:(3 1/2) X2 (0 7/22)X3 (0 1/22)x41 71c c 711X3X4 X2 3 0X3X4 X52 22 22 22 22 2從而有7X4X1X54016
15、4嚴(yán) 7X5 X6 -Cj79000CbXbbXX2X3X4X59X27/2017/221/2207X19/210-1/223/2200X5-1/200-7/22-1/221Cj Zj00-28/11-15/1109X23010017X132/71001/7-1/70X311/70011/7-22/7Cj Zj000-1-8割平面 2 為:(4 4/7) x,(0 1/7)x4( 16/7)x5Cj790003CbX BbXiX2X3X4X5X69X230i00i07xi32/7i00i/7-i/700X3ii/700ii/7-22/700X6-4/7000-i/7-6/7iCjZj000-i
16、-809X230i00i07Xi4i000-ii0X3i00i0-4i0X44000i6-7Cj乙0000-2-7由上表可知該問題已經(jīng)達(dá)到整數(shù)解了,所以該整數(shù)解就是原問題的最優(yōu)解,即*tx 4,3 ,最優(yōu)值為 Zmax 7 4 9 3 55P144用圖解分析法求目標(biāo)規(guī)劃模型min Z =Pi di +P2_d2 + P3 ( 2d3+1d4)廠 xi+ x 2 +di- di = 40xi + x 2 + d2- - d2+= 40+i0=50<xi+ d3- - d3+= 24x 2 +- d4+= 30Xi、X2、di、di、d2、d2、d3、d3、d4、d40解:由下圖可知,滿足m
17、indi的滿意解為區(qū)域X2CDXi滿足mi nd?+的滿意解為閉區(qū)域BCDEB滿足min2d3-的滿意解為圖中的A點(diǎn),滿足mind的滿意解為圖中的A點(diǎn),所以該問題的滿意解為圖中的點(diǎn) A(24,26)x2用圖解分析法求目標(biāo)規(guī)劃模型min zP1d1P2d3P3d2X12x2didi4Xi2x2d2d24Xi2X2d3d38Xi,X20;di、di0i 1,2,3的滿意解。解:由下圖可知,滿足mindi的滿意解為區(qū)域CDOA滿足min d3的滿意解為閉區(qū)域MCDQM滿足min d2的滿意解為圖中的陰影部分,即為圖中的凸多邊形OABCDOP170求下圖中的最小樹/h>7解:避圈法為:% = 3
18、衛(wèi)®必=2月衛(wèi)衛(wèi)陽 広匸SEGC必二DE FtH%二且EGG”込二血武H)巧二AEGQ. D.閲耳=耳旳眄=SEGCDE月)耳二卩fGCQ耳F,均厲F得到最小樹為:解:如下圖所示:P 173用Ford-Fulkerson的標(biāo)號(hào)算法求下圖中所示各容量網(wǎng)絡(luò)中從Vs到Vt的最大流,并標(biāo)出其最小割集。圖中各弧旁數(shù)字為容量Cj,括弧中為流量B)解:對(duì)上有向圖進(jìn)行2F標(biāo)號(hào)得到由于所有點(diǎn)都被標(biāo)號(hào)了,即可以找到增廣鏈,所以流量還可以調(diào)整,調(diào)整量為1, 得由圖可知,標(biāo)號(hào)中斷,所以已經(jīng)是最大流了,最大流量等于最小割的容量,最小 割為與直線KK相交的弧的集合,即為(Vs,V3),(Vs,V4),(Vs,V5),(V!,Vt),(V2,Vt),(V2,V3)所以從Vs到Vt的最大流為:fs;12 5 3 2 1 14C)解:對(duì)上有向圖進(jìn)行 2F標(biāo)號(hào)得到由于所有點(diǎn)都被標(biāo)號(hào)了,即可以找到增廣鏈,所以流量還可以調(diào)整,調(diào)整量為1,得由圖可知,標(biāo)號(hào)中斷,所以已經(jīng)是最大流了,最大流量等于最小割的容量, 最小割為與直線KK相交的弧的集合,即為(Vs,Vi),( Vs,V3),(V2,V5),所以從Vs到vt的最大流為:fst 5 3 5 13P193根據(jù)下表給定的條
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 生態(tài)修復(fù)資源共享合同(2篇)
- 甲乙方協(xié)議書(2篇)
- 2025年硫酸黏菌素類產(chǎn)品合作協(xié)議書
- 五年級(jí)數(shù)學(xué)下冊(cè)口算題
- 中考人教版地理一輪復(fù)習(xí):七年級(jí)上下冊(cè)1-10章聽課評(píng)課記錄
- 人教版地理八年級(jí)下冊(cè)第七章第四節(jié)《祖國的神圣領(lǐng)土臺(tái)灣省》聽課評(píng)課記錄1
- 重慶城區(qū)商品房買賣合同范本
- 立體車庫出租協(xié)議書范本
- 全科醫(yī)師轉(zhuǎn)崗培訓(xùn)單位合作協(xié)議書范本
- 二零二五年度區(qū)塊鏈技術(shù)應(yīng)用合作開發(fā)標(biāo)準(zhǔn)合同
- 醫(yī)生給病人免責(zé)協(xié)議書(2篇)
- 外購?fù)鈪f(xié)管理制度
- 人教版(2024年新教材)七年級(jí)上冊(cè)英語Unit 7 Happy Birthday 單元整體教學(xué)設(shè)計(jì)(5課時(shí))
- 2024變電站無人機(jī)巡檢系統(tǒng)規(guī)范第1部分:技術(shù)規(guī)范
- 機(jī)動(dòng)車商業(yè)保險(xiǎn)條款(2020版)
- 《大小比較》(說課課件)二年級(jí)下冊(cè)數(shù)學(xué)西師大版
- 張五常子女和婚姻合約中的產(chǎn)權(quán)執(zhí)行問題
- 口腔粘膜常見疾病
- 餐廳值班管理培訓(xùn)
- XXXX無線維護(hù)崗位認(rèn)證教材故障處理思路及案例分析
- 酒店春節(jié)營銷方案
評(píng)論
0/150
提交評(píng)論