中南大學(xué)現(xiàn)代遠(yuǎn)程教育平臺-運(yùn)籌學(xué)課程作業(yè)答案

1、運(yùn)籌學(xué)作業(yè)答案作業(yè)一一、是非題：1.圖解法與單純形法雖然求解的形式不同，但從幾何上理解，兩者是一致的。（）2.線性規(guī)劃問題的每一個基解對應(yīng)可行解域的一個頂點。（）3.如果線性規(guī)劃問題存在最優(yōu)解，則最優(yōu)解一定可以在可行解域的頂點上獲得。（）4.用單純形法求解Max型的線性規(guī)劃問題時，檢驗數(shù)Rj0對應(yīng)的變量都可以被選作入基變量。（）5.單純形法計算中，如果不按最小比值規(guī)劃選出基變量，則在下一個解中至少有一個基變量的值為負(fù)。（）6.線性規(guī)劃問題的可行解如為最優(yōu)解，則該可行解一定是基可行解。（）7.若線性規(guī)劃問題具有可行解，且可行解域有界，則該線性規(guī)劃問題最多具有有限個數(shù)的最優(yōu)解。（）8.對一個有n個

2、變量，m個約束的標(biāo)準(zhǔn)型線性規(guī)劃問題，其可行域的頂點數(shù)恰好為個。（）9.一旦一個人工變量在迭代中變?yōu)榉腔兞亢螅撟兞考跋鄳?yīng)列的數(shù)字可以從單純形表中刪除，而不影響計算結(jié)果。（）10.求Max型的單純形法的迭代過程是從一個可行解轉(zhuǎn)換到目標(biāo)函數(shù)值更大的另一個可行解。（）二、線性規(guī)劃建模題：1.某公司一營業(yè)部每天需從A、B兩倉庫提貨用于銷售，需提取的商品有：甲商品不少于240件，乙商品不少于80臺，丙商品不少于120噸。已知：從A倉庫每部汽車每天能運(yùn)回營業(yè)部甲商品4件，乙商品2臺，丙商品6噸，運(yùn)費(fèi)200元/每部；從B倉庫每部汽車每天能運(yùn)回營業(yè)部甲商品7件，乙商品2臺，丙商品2噸，運(yùn)費(fèi)160元/每部。問

3、：為滿足銷售量需要，營業(yè)部每天應(yīng)發(fā)往A、B兩倉庫各多少部汽車，并使總運(yùn)費(fèi)最少？解：設(shè)營業(yè)部每天應(yīng)發(fā)往A、B兩倉庫各x1，x2部汽車,則有：2.現(xiàn)有一家公司準(zhǔn)備制定一個廣告宣傳計劃來宣傳開發(fā)的新產(chǎn)品，以使盡可能多的未來顧客特別是女顧客得知?，F(xiàn)可利用的廣告渠道有電視、廣播和報紙，根據(jù)市場調(diào)查整理得到下面的數(shù)據(jù)：項目電 視廣播報紙一般時間黃金時間每個廣告單元的費(fèi)用(元)每個廣告單元所接觸的顧客數(shù)(萬人)每個廣告單元所接觸的女顧客數(shù)(萬人)40004030700090403000502015002010該企業(yè)計劃用于此項廣告宣傳的經(jīng)費(fèi)預(yù)算是80萬元，此外要求：至少有200萬人次婦女接觸廣告宣傳；電視廣

4、告費(fèi)用不得超過50萬元,電視廣告至少占用三個單元一般時間和兩個單元黃金時間,廣播和報紙廣告單元均不少于5個單元而不超過10個單元。解：設(shè)電視一般時間、黃金時間、廣播和報紙各投放廣告單元數(shù)為x1，x2，x3，x4，有：三、計算題：對于線性規(guī)劃模型1.用圖解法求出其所有基本解，并指出其中的基本可行解和最優(yōu)解。2.三個方程中分別添加松馳變量x3,x4,x5后把模型化成標(biāo)準(zhǔn)型，用單純形法尋求最優(yōu)解。并與1題中圖解法中對照，單純形表中的基可行解分別對應(yīng)哪些頂點。3.若直接取最優(yōu)基，請用單純形表的理論公式進(jìn)行計算對應(yīng)基B的單純形表，并與第2題最優(yōu)單純形表的計算結(jié)果比較是否一致。（附單純形表的理論公式：非基

5、變量xj的系數(shù)列向量由Pj變成基變量的值為，目標(biāo)函數(shù)的值為，檢驗數(shù)公式）。解：（1）圖解如下： 所有基本可行解：O（0,0），Q1（6,0），Q2（4,2），Q3（2,3），Q4（0,3）共五個基可行解。從上圖知：最優(yōu)解為點Q2（4,2），目標(biāo)函數(shù)值為Z20。（2）模型標(biāo)準(zhǔn)化為：單純形法表迭代過程如下表示：cj3 4 0 0 0CBXBx1 x2 x3 x4 x5b000 x3x4x51 1 1 0 0 1 2 0 1 00 1 0 0 16836 出基8-Z3 4 0 0 00300 x1x4x51 1 1 0 0 0 1 -1 1 00 1 0 0 1 626233Z0 1 -3 0 01

6、8340 x1x2x51 0 2 -1 00 1 -1 1 00 0 1 -1 1421Z0 0 -2 -1 0-20從上表知：表一中的基可行解（0,0,6,8,3）對應(yīng)坐標(biāo)原點O，表二中的基可行解為（6,0,0,2,3）對應(yīng)圖中的Q1點，表三中的基可行解為（4,2,0,0,1）對應(yīng)圖中的Q2點，得到最優(yōu)解。（3）若取基，基變量為x1,x2,x5，剛好是最優(yōu)表中的對應(yīng)基變量，可算出（從第三個單純形表也可找到B1），由單純形表計算公式計算非基變量的系數(shù)列向量、檢驗數(shù)及基解等。，。，與迭代的第三個單純形表計算結(jié)果一致。四、寫出下列線性規(guī)劃問題的對偶問題。解：設(shè)三個方程的對偶變量分別為y1,y2,y

7、3，有：五、有一個Max型的線性規(guī)劃問題具有四個非負(fù)變量，三個“”型的條件，其最優(yōu)表格如下表，請寫出其對偶問題的最優(yōu)解及目標(biāo)函數(shù)值。XBx1 x2 x3 x4 x5 x6 x7bx4x6x10 1 2/3 1 2/3 0 -1/30 2 -1 0 0 1 01 1 1/3 0 1/3 0 1/3 14/3410/3-Z0 -2 -4/3 0 -4/3 0 -1/3-34/3 解：該問題的松馳變量為x5,x6,x7，由對偶規(guī)劃的性質(zhì)知三個對偶變量的值分別為x5,x6,x7檢驗數(shù)的負(fù)值，目標(biāo)函數(shù)值與原問題相等。故， W34/3。六、求下列運(yùn)輸問題的解：銷 地產(chǎn) 地B1B2B3供應(yīng)量A16424A2

8、8575需求量333用表上作業(yè)法求解此問題的最優(yōu)解。（要求用行列差值法給初始解，用位勢法求檢驗數(shù)。）解：（1）這是一個產(chǎn)銷平衡的運(yùn)輸問題，用行列差值法給初始解：銷 地產(chǎn) 地B1B2B3行差值供應(yīng)量A16（1）4（）2（3）2,24A28（2）5（3）7（）2,35列差值2,21,15需求量333（2）用位勢法求檢驗數(shù)：對基變量有：,并令u1=0，求出行列位勢，如下表。銷 地產(chǎn) 地B1B2B3行位勢vi供應(yīng)量A16（1）4（）2（3）u1=04A28（2）5（3）7（）u2=25列位勢vjv1=6v2=3v3=2需求量333各非基變量的檢驗數(shù)分別為：R12=4(3+0)=1，R23=7(3+2)

9、=2，即基變量的檢驗數(shù)都大于0，當(dāng)前方案為最優(yōu)調(diào)運(yùn)方案。作業(yè)二一、用隱枚舉法求解下面01型整數(shù)規(guī)劃問題：解：問題為求極大型，需所有的變量前的價值系數(shù)變?yōu)樨?fù)號，故令，模型變?yōu)椋?，用目?biāo)函數(shù)值探索法求最大值：x1x2x3是否滿足約束方程Z(1)(2)(3)（4）0100010032從表中可以看出，當(dāng)時具最大目標(biāo)函數(shù)值，即，Zmax2。二、某服裝廠有五項工作需要分給五個技工去完成，組成分派問題，各技工完成各項工作的能力評分如下表所示。請問應(yīng)如何分派，才能使總得分最大？ 工作 評分人員B1平車B2考克B3卷邊B4繃縫B5打眼A11.30.8001.0A201.21.31.30A31.0001.20A4

10、01.0500.21.4A51.00.90.601.1解：（1）效率矩陣為：，問題是求極大，轉(zhuǎn)化為求極小問題，設(shè)，構(gòu)造以bij為系數(shù)的矩陣，（2）對bij矩陣進(jìn)行系數(shù)變換，使每行每列出現(xiàn)0元素，（3）進(jìn)行試分配：，（4）作最少的直線覆蓋所有的0元素：（5）在沒有被覆蓋的部分中找出最小數(shù)0.1，則第四、五行減去這個最小數(shù)0.1，同時第五列加上這個最小數(shù)，其他元素不變，目的是增加0元素的個數(shù)。（6）試分配：，此時，所有的0都已打括號或劃掉，且打括號的0元素（獨(dú)立的0元素）個數(shù)剛好為5個，得到了問題的最優(yōu)解，問題的解矩陣為：，即A1做平車，A2做卷邊，A3做繃縫，A4做打眼，A5做考克，總得分為6.

11、1。三、某廠從國外引進(jìn)一臺設(shè)備，由工廠A至G港口有多條通路可供選擇，其路線及費(fèi)用如圖1所示。現(xiàn)要確定一條從A到G的使總運(yùn)費(fèi)最小的路線，請將該問題描述成一個動態(tài)規(guī)劃問題，然后求其最優(yōu)解。070C1B1D1130602040GC240A1030D2130 050C3B2第四階段第三階段第二階段第一階段 圖1解：把問題分為4個階段，如圖1示。設(shè)Sk為每一階段的起點，xk為第k階段的決策變量，狀態(tài)轉(zhuǎn)移方程為：SK+1xk(Sk)。k=1,2,3,4。階段指標(biāo)函數(shù)為Sk到xk(Sk)的距離值，最優(yōu)指標(biāo)函數(shù)fk(Sk)為第k階段狀態(tài)為Sk時，從Sk到終點G的最短距離值。指標(biāo)函數(shù)遞推方程：，k=3,2,1邊

12、界方程為：。下面列表計算如下：x4S4x4 GD13030GD24040Gk=4時：k=3時：x3S3x4 D1D2C10+3030D1C24030304070D1或D2C304040D2k=2時：x2S2x4 C1C2C3B170+3060+70100C1B21070504080C2k=1時：x1S1x4B1B2A20+1003080110B2最優(yōu)路線有兩條：AB2C2D1G或AB2C2D2G，最短距離值為110。四、某公司打算在三個不同的地區(qū)設(shè)置4個銷售點，根據(jù)市場預(yù)測部門估計，在不同的地區(qū)設(shè)置不同數(shù)量的銷售店，每月可得到的利潤如表1所示。試問在各個地區(qū)應(yīng)如何設(shè)置銷售點，才能使每月獲得的總

13、利潤最大？其值是多少?表1銷售店利潤地區(qū)01234101625303220121721223010141617解：設(shè)給每一個地區(qū)設(shè)置一個銷售點為一個階段，共三個階段。xk為給第k個地區(qū)設(shè)置的銷售點數(shù)；Sk 為第k階段還剩余的銷售點數(shù)，S14狀態(tài)轉(zhuǎn)移方程為：Sk+1=Skxk dk(xk)為在第k個地區(qū)設(shè)置xk個銷售點增加利潤最優(yōu)指標(biāo)函數(shù)fk(Sk)為第k階段把Sk個銷售點時分給第k、k+1,3個銷售點獲取的最大收益。指標(biāo)函數(shù)遞推方程：，k=2,1邊界方程為：。逆推計算如下：k=3時：S3=x3x3S3x3012340000110101214142316163417174k=2時：S3= S2x

14、2x3S3x2012340000101012+012120+1412+1017+022130+1612+1417+1021+027240+1712+1617+1421+1022+0312或3k=1時：S2= S1x1x1S1x2012344031162725223012320472最優(yōu)決策方案為：第一個地區(qū)設(shè)置2個銷售點，第二個地區(qū)設(shè)置1個銷售點，第三個地區(qū)設(shè)置1個銷售點，每月可獲總利潤為47。五、某廠生產(chǎn)一種產(chǎn)品，該產(chǎn)品在未來三個月中的需要量分別為3，4，3萬件，若生產(chǎn)準(zhǔn)備費(fèi)為3萬元/次，每件成本為1元，每件每月存儲費(fèi)為0.7元，假定1月初和4月初存貨為0，并每月產(chǎn)量不限。試求該廠未來三個月

15、內(nèi)的最優(yōu)生產(chǎn)計劃？要求用解：這是個動態(tài)決策問題，下面用動態(tài)規(guī)劃求解。解：這是個動態(tài)決策問題，下面用動態(tài)規(guī)劃求解，建立如下動態(tài)規(guī)劃數(shù)學(xué)模型。需求量： D1=3 D2=4 D3=31月3月4月2月階段(月份)n： 1 2 3 4狀態(tài)變量Sn：每月初庫存，有 S1=0，S2=0,1,2,3, 4,5,6,7，S3=0,1，2,3， S4=0。決策變量Xn：每月的生產(chǎn)量 X1：據(jù)題意有決策變量的允許范圍：3x110, 0 x27, 0 x33 。狀態(tài)轉(zhuǎn)移方程： Sn+1 = Sn +XnD n 階段指標(biāo)函數(shù)(成本)：成本=生產(chǎn)費(fèi)用存儲費(fèi)用rn(Xn)=31Xn ， Xn00 ， Xn00.7Sn指標(biāo)函

16、數(shù)遞推方程：， 下面利用表格進(jìn)行計算，從最后一個階段開始：n=3時： 此時 S3+X3DD3=0，即X3=3S3X3S3r3(X3)f3(S3)X3*012306+0=66315+0.7=5.75.7224+1.4=5.45.4130+2.1=2.12.10n=2時： 此時 S2+X2D2=4，即X24S2；S3 = S2 +X2D2，即S3 = S2 +X24X2S2r2(X2)+ f3 (S3)f2 (S2)X20123456707+68+5.79+5.410+2.112.1716.7+67.7+5.78.7+5.49.7+2.111.8626.4+67.4+5.78.4+5.49.4+2

17、.111.6536.1+67.1+5.78.1+5.49.1+2.111.2442.8+66.8+5.77.8+5.48.8+2.18.8053.5+5.77.5+5.48.5+2.19.2064.2+5.48.2+2.19.6074.9+2.170n=1時： X13S1；S2 = S1 +X1D1，即S2 = S1 +X13X1S1r1(X1)+ f2 (S2)f1 (S1)X1*0123456706+12.17+11.88+11.69+11.210+8.818.13由此可知：S1=0，此時X1*=3； S2 = S1+X1*3=033=0，此時X2*=7； S3 = S2+X2*4=074

18、=3，此時X3*=0。最優(yōu)策略為：X*=x1*，x2*，x3*=3，7，0 Z*=f1*(S1)=18.1即第一個月生產(chǎn)3萬件，第二個月生產(chǎn)7萬件，第三個月生產(chǎn)0萬件，可使總成本最低為18.1萬元。作業(yè)三（圖與網(wǎng)絡(luò)分析、存貯論部分）判斷題：1.圖論中的圖不僅反映了研究對象之間的關(guān)系，而且是真實圖形的寫照，因而對圖中點與點的相對位置、點與點連線的長短曲直等都要嚴(yán)格注意。（）2.在任一圖G中，當(dāng)點集V確定后，樹圖是G中邊數(shù)最少的連通圖。（）3.如圖中某點vi有若干個相鄰點，與其距離最遠(yuǎn)的相鄰點為vj，則邊vi,vj必不包含在最小支撐樹內(nèi)。（）4.在任一連通圖G中，點數(shù)為N，則保證這N點相互連通且任

19、意兩點間僅有一條鏈相通的圖一定含有N1條邊。（）5.求網(wǎng)絡(luò)最大流問題可歸結(jié)為求解一個線性規(guī)劃問題。（）6.訂購費(fèi)為每訂一次貨所發(fā)生的費(fèi)用，它同每次訂貨的數(shù)量無關(guān)。（）7.在同一存貯模型中，可能既發(fā)生存貯費(fèi)用，又發(fā)生短缺費(fèi)用。（）8.在允許缺貨發(fā)生短缺的存貯模型中，訂貨批量的確定應(yīng)使由于存貯量的減少帶來的節(jié)約能抵消缺貨時造成的損失。（）9.當(dāng)訂貨數(shù)量超過一定的值允許打折扣的情況下，打折扣條件下的訂貨批量要大于不打折扣時的訂貨批量。（）10.在其他費(fèi)用不變的情況下，隨著單位存貯費(fèi)用的增加，最優(yōu)訂貨批量也相應(yīng)增大。（）二、求圖1中的最小樹5v1v2v3v4v6v7v8v565456278333441

20、圖1：解：用破圈法求得的最小部分樹為：v1v2v3v4v6v7v8v54233315最小部分樹的權(quán)為：13+33+24+521。三、求圖2中從點v1到其余各點的最短路：43v1v3v5v73251382736圖2v4v28052解：用T、P標(biāo)號算法：1.給v1點標(biāo)P標(biāo)號，其他點標(biāo)T標(biāo)號，為。2.從v1點出發(fā)，修改v2、v3點的T標(biāo)號，并把其中最小者改為P標(biāo)號。T(v2)=3，T(v3)=2P（v3）。3.從剛剛獲得P標(biāo)號的點v3出發(fā)，可達(dá)v2,v4,v5,修改T標(biāo)號，并把最小者改為P標(biāo)號。4.依此類推，各點的P標(biāo)號如圖2所示。從v1到v7的最短路為：v1 v3v5v7，距離為8。四、求圖3中網(wǎng)絡(luò)的最大流、最大流的流量和最小割。v2v5v7v1v3v6v458434428898圖36v2v5v7v1v3v6v45,58,84,43,34,44,42,28,38,89,98,86,2解：最大流如圖示：0,僅有起點v1可標(biāo)號，最小割為，最大流流量為17。五、計算題：1.設(shè)需要某物品12件/天，不允許缺貨，存貯費(fèi)率