運(yùn)籌學(xué)部分課后習(xí)題解答_1

1、運(yùn)籌學(xué)部分課后習(xí)題解答P47 1.1 用圖解法求解線性規(guī)劃問(wèn)題 a） 解：由圖1可知，該問(wèn)題的可行域?yàn)橥辜疢ABCN，且可知線段BA上的點(diǎn)都為最優(yōu)解，即該問(wèn)題有無(wú)窮多最優(yōu)解，這時(shí)的最優(yōu)值為P47 1.3 用圖解法和單純形法求解線性規(guī)劃問(wèn)題 a） 解：由圖1可知，該問(wèn)題的可行域?yàn)橥辜疧ABCO，且可知B點(diǎn)為最優(yōu)值點(diǎn)，即，即最優(yōu)解為這時(shí)的最優(yōu)值為單純形法：原問(wèn)題化成標(biāo)準(zhǔn)型為10500b09341008520110500021/5014/51-3/5108/512/501/5010-253/2015/14-3/1410110-1/72/700-5/14-25/14所以有P78 2.4 已知線性規(guī)劃問(wèn)

2、題：求: (1) 寫(xiě)出其對(duì)偶問(wèn)題；（2）已知原問(wèn)題最優(yōu)解為，試根據(jù)對(duì)偶理論，直接求出對(duì)偶問(wèn)題的最優(yōu)解。解：（1）該線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題為：（2）由原問(wèn)題最優(yōu)解為，根據(jù)互補(bǔ)松弛性得：把代入原線性規(guī)劃問(wèn)題的約束中得第四個(gè)約束取嚴(yán)格不等號(hào)，即 從而有 得所以對(duì)偶問(wèn)題的最優(yōu)解為，最優(yōu)值為P79 2.7 考慮如下線性規(guī)劃問(wèn)題：（1） 寫(xiě)出其對(duì)偶問(wèn)題；（2）用對(duì)偶單純形法求解原問(wèn)題；解：（1）該線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題為：（2）在原問(wèn)題加入三個(gè)松弛變量把該線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型：-60-40-80000b0-2-3-2-11000-4-4-1-30100-3-2-2-2001-60-40-80000010

3、-5/45/41-1/12080111/43/40-1/400-10-3/2-1/20-1/210-25-350-150011/6005/311/3-5/6805/6102/30-1/31/6402/3011/301/3-2/300-80/30-20/3-50/3 P81 2.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í)可從市

4、場(chǎng)購(gòu)買，每單位0.4 元。問(wèn)該廠要不要購(gòu)進(jìn)原材料擴(kuò)大生產(chǎn)，以購(gòu)多少為宜。消耗定額產(chǎn)品資源AB C可用量（單位）勞動(dòng)力材料6 3 53 4 54530產(chǎn)品利潤(rùn)（元/件）3 1 4解：由已知可得，設(shè)表示第種產(chǎn)品，從而模型為：a) 用單純形法求解上述模型為：31400b0456351003034501314000153-101-1463/54/5101/53/5-11/500-4/5351-1/301/3-1/343011-1/52/50-20-1/5-3/5得到最優(yōu)解為；最優(yōu)值為 b）設(shè)產(chǎn)品A的利潤(rùn)為，則上述模型中目標(biāo)函數(shù)的系數(shù)用替代并求解得：1400b351-1/301/3-1/343011-1

5、/52/5-20-1/5-3/50-2+/30-1/5-/3-3/5+/3要最優(yōu)計(jì)劃不變，要求有如下的不等式方程組成立解得：從而產(chǎn)品A的利潤(rùn)變化范圍為：,即C）設(shè)產(chǎn)品D用表示，從已知可得把加入上述模型中求解得：314003b351-1/301/3-1/3243011-1/52/5-4/50-20-1/5-3/51/535/21/2-1/601/6-1/61452/513/151-1/154/150-1/10-59/300-7/30-17/300從而得最優(yōu)解；最優(yōu)值為所以產(chǎn)品D值得生產(chǎn)。d）P101 3.1已知運(yùn)輸問(wèn)題的產(chǎn)銷量與單位運(yùn)價(jià)如下表所示，用表上作業(yè)法求各題的最優(yōu)解及最小運(yùn)費(fèi)。表3-35

6、產(chǎn)地銷地B1B2B3B4產(chǎn)量A1A2A31012227142091611201815255銷量5151510解：由已知和最小元素法可得初始方案為產(chǎn)地銷地B1B2B3B4產(chǎn)量A1A2A351501501015255銷量5151510檢驗(yàn)：由于有兩個(gè)檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整一： 產(chǎn)地銷地B1B2B3B4產(chǎn)量A1A2A351501510015255銷量5151510 檢驗(yàn)：由于還有檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整二：產(chǎn)地銷地B1B2B3B4產(chǎn)量A1A2A355101510015255銷量5151510檢驗(yàn)：從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案最小運(yùn)費(fèi)為：表3-36產(chǎn)地銷地B1B2B3

7、B4產(chǎn)量A1A2A386549314427372526銷量10102015解：因?yàn)?，即產(chǎn)大于銷，所以需添加一個(gè)假想的銷地，銷量為3，構(gòu)成產(chǎn)銷平衡問(wèn)題，其對(duì)應(yīng)各銷地的單位運(yùn)費(fèi)都為0。產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A1A2A386549314427300072526銷量101020153由上表和最小元素法可得初始方案為產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A1A2A3911071315372526銷量101020153檢驗(yàn)： 從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案最小運(yùn)費(fèi)為：表3-37 產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A1A2A38566M3389746578203030銷量25252010

8、20解：因?yàn)?，即銷大于產(chǎn)，所以需添加一個(gè)假想的產(chǎn)地，產(chǎn)量為20，構(gòu)成產(chǎn)銷平衡問(wèn)題，其對(duì)應(yīng)各銷地的單位運(yùn)費(fèi)都為0。產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A1A2A3A485606M3038907460578020303020銷量2525201020由上表和最小元素法可得初始方案為產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A1A2A3A4520252001015520303020銷量2525201020檢驗(yàn)： 由于有兩個(gè)檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整一：產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A1A2A3A4205252001051520303020銷量2525201020 檢驗(yàn)：由于還有檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整二

9、：產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A1A2A3A4205252001002020303020銷量2525201020檢驗(yàn)：從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案最小運(yùn)費(fèi)為：P127 4.8 用割平面法求解整數(shù)規(guī)劃問(wèn)題。a） 解：該問(wèn)題的松弛問(wèn)題為：則單純形法求解該松弛問(wèn)題得最后一單純形表為：7900b97/2017/221/2279/210-1/223/2200-28/11-15/11割平面1為：從而有79000b97/2017/221/22079/210-1/223/2200-1/200-7/22-1/22100-28/11-15/1109301001732/71001/7-1/7

10、011/70011/7-22/7000-1-8割平面2為：790003b93010010732/71001/7-1/70011/70011/7-22/700-4/7000-1/7-6/71000-1-8093010010741000-11010010-410400016-70000-2-7由上表可知該問(wèn)題已經(jīng)達(dá)到整數(shù)解了，所以該整數(shù)解就是原問(wèn)題的最優(yōu)解，即，最優(yōu)值為P144 5.3 用圖解分析法求目標(biāo)規(guī)劃模型x1 + x2 + d1- - d1+= 40 x1 + x2 + d2- - d2+= 40+10=50x1 + d3- - d3+= 24 x2 + d4- - d4+= 30min

11、Z = P1 d1-+ P2 d2+ P3（2d3- +1d4-）s.t.x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 、d4+、d4- 0 c） 解:由下圖可知，滿足目標(biāo)函數(shù)的滿意解為圖中的A 點(diǎn)。 P170 6.4 求下圖中的最小樹(shù)解：避圈法為：得到最小樹(shù)為：P171 6.7 用標(biāo)號(hào)法求下圖中點(diǎn)到各點(diǎn)的最短路。解：如下圖所示：P 173 6.14 用Ford-Fulkerson的標(biāo)號(hào)算法求下圖中所示各容量網(wǎng)絡(luò)中從到的最大流，并標(biāo)出其最小割集。圖中各弧旁數(shù)字為容量，括弧中為流量.B) 解：對(duì)上有向圖進(jìn)行2F標(biāo)號(hào)得到由于所有點(diǎn)都被標(biāo)號(hào)了，即可以找到增廣鏈，所以流量還可以調(diào)整

12、，調(diào)整量為1，得由圖可知，標(biāo)號(hào)中斷，所以已經(jīng)是最大流了，最大流量等于最小割的容量，最小割為與直線KK相交的弧的集合，即為所以從到的最大流為： C) 解：對(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相交的弧的集合，即為，所以從到的最大流為： P193 7.1 根據(jù)下表給定的條件，繪制PERT網(wǎng)絡(luò)圖。表7-8作業(yè)代號(hào) a1 a2 a3 b1 b2 b3 c1 c2 c3緊前作業(yè)無(wú) a1 a2 無(wú) b1 b2 a1，b1 a2，b2，c1 a3，b3，c2解：繪制