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

中南大學現(xiàn)代遠程教育平臺—運籌學課程作業(yè)答案中南大學現(xiàn)代遠程教育平臺—運籌學課程作業(yè)答案中南大學現(xiàn)代遠程教育平臺—運籌學課程作業(yè)答案中南大學現(xiàn)代遠程教育平臺—運籌學課程作業(yè)答案編制僅供參考審核批準生效日期地址：電話：傳真:郵編:《運籌學》作業(yè)答案作業(yè)一一、是非題：1.圖解法與單純形法雖然求解的形式不同，但從幾何上理解，兩者是一致的。（√）2.線性規(guī)劃問題的每一個基解對應(yīng)可行解域的一個頂點。（╳）3.如果線性規(guī)劃問題存在最優(yōu)解，則最優(yōu)解一定可以在可行解域的頂點上獲得。（√）4.用單純形法求解Max型的線性規(guī)劃問題時，檢驗數(shù)Rj＞0對應(yīng)的變量都可以被選作入基變量。（√）5.（√）6.線性規(guī)劃問題的可行解如為最優(yōu)解，則該可行解一定是基可行解。（╳）7.若線性規(guī)劃問題具有可行解，且可行解域有界，則該線性規(guī)劃問題最多具有有限個數(shù)的最優(yōu)解。（╳）8.對一個有n個變量，m個約束的標準型線性規(guī)劃問題，其可行域的頂點數(shù)恰好為個。（╳）9.一旦一個人工變量在迭代中變?yōu)榉腔兞亢?，該變量及相?yīng)列的數(shù)字可以從單純形表中刪除，而不影響計算結(jié)果。（√）10.求Max型的單純形法的迭代過程是從一個可行解轉(zhuǎn)換到目標函數(shù)值更大的另一個可行解。（√）二、線性規(guī)劃建模題：1.某公司一營業(yè)部每天需從A、B兩倉庫提貨用于銷售，需提取的商品有：甲商品不少于240件，乙商品不少于80臺，丙商品不少于120噸。已知：從A倉庫每部汽車每天能運回營業(yè)部甲商品4件，乙商品2臺，丙商品6噸，運費200元/每部；從B倉庫每部汽車每天能運回營業(yè)部甲商品7件，乙商品2臺，丙商品2噸，運費160元/每部。問：為滿足銷售量需要，營業(yè)部每天應(yīng)發(fā)往A、B兩倉庫各多少部汽車，并使總運費最少？

解：設(shè)營業(yè)部每天應(yīng)發(fā)往A、B兩倉庫各x1，x2部汽車,則有：2.現(xiàn)有一家公司準備制定一個廣告宣傳計劃來宣傳開發(fā)的新產(chǎn)品，以使盡可能多的未來顧客特別是女顧客得知?，F(xiàn)可利用的廣告渠道有電視、廣播和報紙，根據(jù)市場調(diào)查整理得到下面的數(shù)據(jù)：項目電視廣播報紙一般時間黃金時間每個廣告單元的費用(元)每個廣告單元所接觸的顧客數(shù)(萬人)每個廣告單元所接觸的女顧客數(shù)(萬人)40004030700090403000502015002010該企業(yè)計劃用于此項廣告宣傳的經(jīng)費預(yù)算是80萬元，此外要求：①至少有200萬人次婦女接觸廣告宣傳；②電視廣告費用不得超過50萬元,③電視廣告至少占用三個單元一般時間和兩個單元黃金時間,④廣播和報紙廣告單元均不少于5個單元而不超過10個單元。解：設(shè)電視一般時間、黃金時間、廣播和報紙各投放廣告單元數(shù)為x1，x2，x3，x4，有：三、計算題：對于線性規(guī)劃模型1.用圖解法求出其所有基本解，并指出其中的基本可行解和最優(yōu)解。2.三個方程中分別添加松馳變量x3,x4,x5后把模型化成標準型，用單純形法尋求最優(yōu)解。并與1題中圖解法中對照，單純形表中的基可行解分別對應(yīng)哪些頂點。3.若直接取最優(yōu)基，請用單純形表的理論公式進行計算對應(yīng)基B的單純形表，并與第2題最優(yōu)單純形表的計算結(jié)果比較是否一致。（附單純形表的理論公式：非基變量xj的系數(shù)列向量由Pj變成基變量的值為，目標函數(shù)的值為，檢驗數(shù)公式）。解：（1）圖解如下：所有基本可行解：O（0,0），Q1（6,0），Q2（4,2），Q3（2,3），Q4（0,3）共五個基可行解。從上圖知：最優(yōu)解為點Q2（4,2），目標函數(shù)值為Z＝20。（2）模型標準化為：單純形法表迭代過程如下表示：cj34000CBXBx1x2x3x4x5bθ000x3x4x5[1]110012010010016836出基8-－Z340000300x1x4x5111000[1]-11001001626233－Z01-300－18340x1x2x5102-1001-110001-11421－Z00-2-10-20從上表知：表一中的基可行解（0,0,6,8,3）對應(yīng)坐標原點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)基變量，可算出（從第三個單純形表也可找到B－1），由單純形表計算公式計算非基變量的系數(shù)列向量、檢驗數(shù)及基解等。，，。，與迭代的第三個單純形表計算結(jié)果一致。四、寫出下列線性規(guī)劃問題的對偶問題。解：設(shè)三個方程的對偶變量分別為y1,y2,y3，有：五、有一個Max型的線性規(guī)劃問題具有四個非負變量，三個“≤”型的條件，其最優(yōu)表格如下表，請寫出其對偶問題的最優(yōu)解及目標函數(shù)值。XBx1x2x3x4x5x6x7bx4x6x1012/312/30-1/302-10010111/301/301/314/3410/3-Z0-2-4/30-4/30-1/3-34/3解：該問題的松馳變量為x5,x6,x7，由對偶規(guī)劃的性質(zhì)知三個對偶變量的值分別為x5,x6,x7檢驗數(shù)的負值，目標函數(shù)值與原問題相等。故，W＝34/3。六、求下列運輸問題的解：銷地產(chǎn)地B1B2B3供應(yīng)量A16424A28575需求量333用表上作業(yè)法求解此問題的最優(yōu)解。（要求用行列差值法給初始解，用位勢法求檢驗數(shù)。）解：（1）這是一個產(chǎ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)=2，即基變量的檢驗數(shù)都大于0，當前方案為最優(yōu)調(diào)運方案。作業(yè)二一、用隱枚舉法求解下面0－1型整數(shù)規(guī)劃問題：解：問題為求極大型，需所有的變量前的價值系數(shù)變?yōu)樨撎枺柿?，模型變?yōu)椋?，用目標函?shù)值探索法求最大值：x1’x2’x3是否滿足約束方程Z(1)(2)(3)（4）01000100╳√√√√32從表中可以看出，當時具最大目標函數(shù)值，即，Zmax＝2。二、某服裝廠有五項工作需要分給五個技工去完成，組成分派問題，各技工完成各項工作的能力評分如下表所示。請問應(yīng)如何分派，才能使總得分最大？

工作評分人員B1平車B2考克B3卷邊B4繃縫B5打眼A100A200A3000A400A50解：（1）效率矩陣為：，問題是求極大，轉(zhuǎn)化為求極小問題，設(shè)，構(gòu)造以bij為系數(shù)的矩陣，（2）對bij矩陣進行系數(shù)變換，使每行每列出現(xiàn)0元素，（3）進行試分配：，（4）作最少的直線覆蓋所有的0元素：（5）在沒有被覆蓋的部分中找出最小數(shù)，則第四、五行減去這個最小數(shù)，同時第五列加上這個最小數(shù)，其他元素不變，目的是增加0元素的個數(shù)。（6）試分配：，此時，所有的0都已打括號或劃掉，且打括號的0元素（獨立的0元素）個數(shù)剛好為5個，得到了問題的最優(yōu)解，問題的解矩陣為：，即A1做平車，A2做卷邊，A3做繃縫，A4做打眼，A5做考克，總得分為。三、某廠從國外引進一臺設(shè)備，由工廠A至G港口有多條通路可供選擇，其路線及費用如圖1所示。現(xiàn)要確定一條從A到G的使總運費最小的路線，請將該問題描述成一個動態(tài)規(guī)劃問題，然后求其最優(yōu)解。070C1070C1B1D11D1130602030602040G40GC240AC240A1030D21301030D21300050C3B50C3B2第四階段第三階段第第四階段第三階段第二階段第一階段圖1圖1解：把問題分為4個階段，如圖1示。設(shè)Sk為每一階段的起點，xk為第k階段的決策變量，狀態(tài)轉(zhuǎn)移方程為：SK+1＝xk(Sk)。k=1,2,3,4。階段指標函數(shù)為Sk到xk(Sk)的距離值，最優(yōu)指標函數(shù)fk(Sk)為第k階段狀態(tài)為Sk時，從Sk到終點G的最短距離值。指標函數(shù)遞推方程：，k=3,2,1邊界方程為：。下面列表計算如下：x4S4x4GD13030GD24040Gk=4時：k=3時：x3S3x4D1D2C10+30－30D1C240＋3030＋4070D1或D2C3－0＋4040D2k=2時：x2S2x4C1C2C3B170+3060+70－100C1B210＋7050＋4080C2k=1時：x1S1x4B1B2A20+10030＋80110B2最優(yōu)路線有兩條：A→B2→C2→D1→G或A→B2→C2→D2→G，最短距離值為110。四、某公司打算在三個不同的地區(qū)設(shè)置4個銷售點，根據(jù)市場預(yù)測部門估計，在不同的地區(qū)設(shè)置不同數(shù)量的銷售店，每月可得到的利潤如表1所示。試問在各個地區(qū)應(yīng)如何設(shè)置銷售點，才能使每月獲得的總利潤最大其值是多少表1銷售店利潤地區(qū)01234101625303220121721223010141617解：設(shè)給每一個地區(qū)設(shè)置一個銷售點為一個階段，共三個階段。xk為給第k個地區(qū)設(shè)置的銷售點數(shù)；Sk為第k階段還剩余的銷售點數(shù)，S1＝4狀態(tài)轉(zhuǎn)移方程為：Sk+1=Sk－xkdk(xk)為在第k個地區(qū)設(shè)置xk個銷售點增加利潤最優(yōu)指標函數(shù)fk(Sk)為第k階段把Sk個銷售點時分給第k、k+1,…3個銷售點獲取的最大收益。指標函數(shù)遞推方程：，k=2,1邊界方程為：。逆推計算如下：k=3時：S3=x3x3S3x3012340000110101214142316163417174k=2時：S3=S2－x2x3S3x201234000010＋1012+012120+1412+1017+022130+1612+1417+1021+027240+1712+1617+1421+1022+0312或3k=1時：S2=S1－x1x1S1x20123440＋3116＋2725＋2230＋1232＋0472最優(yōu)決策方案為：第一個地區(qū)設(shè)置2個銷售點，第二個地區(qū)設(shè)置1個銷售點，第三個地區(qū)設(shè)置1個銷售點，每月可獲總利潤為47。五、某廠生產(chǎn)一種產(chǎn)品，該產(chǎn)品在未來三個月中的需要量分別為3，4，3萬件，若生產(chǎn)準備費為3萬元/次，每件成本為1元，每件每月存儲費為元，假定1月初和4月初存貨為0，并每月產(chǎn)量不限。試求該廠未來三個月內(nèi)的最優(yōu)生產(chǎn)計劃？要求用動態(tài)規(guī)劃求解。

動態(tài)規(guī)劃求解，建立如下動態(tài)規(guī)劃數(shù)學模型。1月1月3月4月2月①階段(月份)n：1234②狀態(tài)變量Sn：每月初庫存，有S1={0}，S2={0,1,2,3,4,5,6,7}，S3={0,1，2,3}，S4={0}。③決策變量Xn：每月的生產(chǎn)量據(jù)題意有決策變量的允許范圍：3≤x1≤10,0≤x2≤7,0≤x3≤3。④狀態(tài)轉(zhuǎn)移方程：Sn+1=Sn+Xn－Dn⑤階段指標函數(shù)(成本)：成本=生產(chǎn)費用＋存儲費用rrn(Xn)=3＋1·Xn，Xn＞00，Xn＝0＋＋⑥遞推方程：，下面利用表格進行計算，從最后一個階段開始：n=3時：此時S3+X3－D3=0，即X3=3－S3X3S3r3(X3)f3(S3)X3*012306+0=66315+=224+=130+=0n=2時：此時S2+X2≥2=4，即X2≥4－S2；S3=S2+X2－D2，即S3=S2+X2－4X2S2r2(X2)+f3(S3)f2(S2)X20123456707+68+9+10+71+6+++62+6+++53+6+++44+6+++05+++06++07+70n=1時：X1≥3－S1；S2=S1+X1－D1，即S2=S1+X1－3X1S1r1(X1)+f2(S2)f1(S1)X1*0123456706+7+8+9+10+3由此可知：S1=0，此時X1*=3；S2=S1+X1*－3=0＋3－3=0，此時X2*=7；S3=S2+X2*－4=0＋7－4=3，此時X3*=0。最優(yōu)策略為：X*={x1*，x2*，x3*}={3，7，0}Z*=f1*(S1)=即第一個月生產(chǎn)3萬件，第二個月生產(chǎn)7萬件，第三個月生產(chǎn)0萬件，可使總成本最低為萬元。作業(yè)三（圖與網(wǎng)絡(luò)分析、存貯論部分）判斷題：1.圖論中的圖不僅反映了研究對象之間的關(guān)系，而且是真實圖形的寫照，因而對圖中點與點的相對位置、點與點連線的長短曲直等都要嚴格注意。（╳）2.在任一圖G中，當點集V確定后，樹圖是G中邊數(shù)最少的連通圖。（√）3.如圖中某點vi有若干個相鄰點，與其距離最遠的相鄰點為vj，則邊[vi,vj]必不包含在最小支撐樹內(nèi)。（╳）4.在任一連通圖G中，點數(shù)為N，則保證這N點相互連通且任意兩點間僅有一條鏈相通的圖一定含有N－1條邊。（√）5.求網(wǎng)絡(luò)最大流問題可歸結(jié)為求解一個線性規(guī)劃問題。（√）6.訂購費為每訂一次貨所發(fā)生的費用，它同每次訂貨的數(shù)量無關(guān)。（√）7.在同一存貯模型中，可能既發(fā)生存貯費用，又發(fā)生短缺費用。（√）8.在允許缺貨發(fā)生短缺的存貯模型中，訂貨批量的確定應(yīng)使由于存貯量的減少帶來的節(jié)約能抵消缺貨時造成的損失。（√）9.當訂貨數(shù)量超過一定的值允許打折扣的情況下，打折扣條件下的訂貨批量要大于不打折扣時的訂貨批量。（√）10.在其他費用不變的情況下，隨著單位存貯費用的增加，最優(yōu)訂貨批量也相應(yīng)增大。（╳）二、求圖1中的最小樹5v5v1v2v3v4v6v7v8v565456278333441圖1解：用破圈法求得的最小部分樹為：vv1v2v3v4v6v7v8v54233315最小部分樹的權(quán)為：1＋3+3＋3+2＋4+5＝21。三、求圖2中從點v1到其余各點的最短路：43v1v43v1v3v5v73251382736圖2v4v288005252解：用T、P標號算法：1.給v1點標P標號，其他點標T標號，為＋∞。2.從v1點出發(fā)，修改v2、v3點的T標號，并把其中最小者改為P標號。T(v2)=3，T(v3)=2＝P（v3）。3.從剛剛獲得P標號的點v3出發(fā)，可達v2,v4,v5,修改T標號，并把最小者改為P標號。4.依此類推，各點的P標號如圖2所示。從v1到v7的最短路為：v1→v3→v5→v7，距離為8。四、求圖3中網(wǎng)絡(luò)的最大流、最大流的流量和最小割。vv2v5v7v1v3v6v458434428898圖36v2v2v5v7v1v3v6v45,58,84,43,34,44,42,