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

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

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

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

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

5、變量xj的系數(shù)列向量由Pj變成基變量的值為，目標(biāo)函數(shù)的值為，檢驗(yàn)數(shù)公式）。解：（1）圖解如下： 所有基本可行解：O（0,0），Q1（6,0），Q2（4,2），Q3（2,3），Q4（0,3）共五個(gè)基可行解。從上圖知：最優(yōu)解為點(diǎn)Q2（4,2），目標(biāo)函數(shù)值為Z20。（2）模型標(biāo)準(zhǔn)化為：?jiǎn)渭冃畏ū淼^(guò)程如下表示：cj3 4 0 0 0CBXBx1 x2 x3 x4 x5b000x3x4x51 1 1 0 0 1 2 0 1 00 1 0 0 16836 出基8-Z3 4 0 0 00300x1x4x51 1 1 0 0 0 1 -1 1 00 1 0 0 1 626233Z0 1 -3 0 0183

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

7、：五、有一個(gè)Max型的線性規(guī)劃問(wèn)題具有四個(gè)非負(fù)變量，三個(gè)“”型的條件，其最優(yōu)表格如下表，請(qǐng)寫(xiě)出其對(duì)偶問(wèn)題的最優(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 解：該問(wèn)題的松馳變量為x5,x6,x7，由對(duì)偶規(guī)劃的性質(zhì)知三個(gè)對(duì)偶變量的值分別為x5,x6,x7檢驗(yàn)數(shù)的負(fù)值，目標(biāo)函數(shù)值與原問(wèn)題相等。故， W34/3。六、求下列運(yùn)輸問(wèn)題的解：銷 地產(chǎn) 地B1B2B3供應(yīng)量A16424A2857

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

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

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

11、、某廠從國(guó)外引進(jìn)一臺(tái)設(shè)備，由工廠A至G港口有多條通路可供選擇，其路線及費(fèi)用如圖1所示?，F(xiàn)要確定一條從A到G的使總運(yùn)費(fèi)最小的路線，請(qǐng)將該問(wèn)題描述成一個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題，然后求其最優(yōu)解。070C1B1D1130602040GC240A1030D2130 050C3B2第四階段第三階段第二階段第一階段 圖1解：把問(wèn)題分為4個(gè)階段，如圖1示。設(shè)Sk為每一階段的起點(diǎn)，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時(shí)，從Sk到終點(diǎn)G的最短距離值。指標(biāo)函數(shù)遞推方程：，k=3,2,1邊界方程

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

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

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

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

16、：， 下面利用表格進(jìn)行計(jì)算，從最后一個(gè)階段開(kāi)始：n=3時(shí)： 此時(shí) 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時(shí)： 此時(shí) 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.111.

17、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時(shí)： 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，此時(shí)X1*=3； S2 = S1+X1*3=033=0，此時(shí)X2*=7； S3 = S2+X2*4=074=3，此時(shí)

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

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

20、：解：用破圈法求得的最小部分樹(shù)為：v1v2v3v4v6v7v8v54233315最小部分樹(shù)的權(quán)為：13+33+24+521。三、求圖2中從點(diǎn)v1到其余各點(diǎn)的最短路：43v1v3v5v73251382736圖2v4v28052解：用T、P標(biāo)號(hào)算法：1.給v1點(diǎn)標(biāo)P標(biāo)號(hào)，其他點(diǎn)標(biāo)T標(biāo)號(hào)，為。2.從v1點(diǎn)出發(fā)，修改v2、v3點(diǎn)的T標(biāo)號(hào)，并把其中最小者改為P標(biāo)號(hào)。T(v2)=3，T(v3)=2P（v3）。3.從剛剛獲得P標(biāo)號(hào)的點(diǎn)v3出發(fā)，可達(dá)v2,v4,v5,修改T標(biāo)號(hào)，并把最小者改為P標(biāo)號(hào)。4.依此類推，各點(diǎn)的P標(biāo)號(hà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,僅有起點(diǎn)v1可標(biāo)號(hào)，最小割為，最大流流量為17。五、計(jì)算題：1.設(shè)需要某物品12件/天，不允許缺貨，存貯費(fèi)率