運籌學 本復習資料

《運籌學》課程復習資料一、判斷題：1.圖解法與單純形法即使求解形式不一樣，但從幾何上了解，二者是一致。[]2.線性規(guī)劃問題每一個基本解對應可行解域一個頂點。[]3.任何線性規(guī)劃問題存在并具備惟一對偶問題。[]4.已知yi*為線性規(guī)劃對偶問題最優(yōu)解，若yi*＞0，說明在最優(yōu)生產計劃中第i種資源已完全耗盡。[]5.運輸問題是一個特殊線性規(guī)劃問題，因而其求解結果也可能出現(xiàn)以下四種情況之一：有惟一最優(yōu)解，有沒有窮多最優(yōu)解，無界解，無可行解。[]6.動態(tài)規(guī)劃最優(yōu)性原理確保了從某一狀態(tài)開始未來決議獨立于先前已做出決議。[]7.假如線性規(guī)劃問題存在最優(yōu)解，則最優(yōu)解一定能夠在可行解域頂點上取得。[]8.用單純形法求解Max型線性規(guī)劃問題時，檢驗數(shù)Rj＞0對應變量都能夠被選作入基變量。[]9.對于原問題是求Min，若第i個約束是“＝”，則第i個對偶變量yi≤0。[]10.[]11.[]12.在允許缺貨發(fā)生短缺存貯模型中，訂貨批量確實定應使因為存貯量降低帶來節(jié)約能抵消缺貨時造成損失。[]13.依照對偶問題性質，當原問題為無界解時，其對偶問題無可行解，反之，當對偶問題無可行解時，其原問題具備無界解。[]14.在線性規(guī)劃最優(yōu)解中，若某一變量xj為非基變量，則在原來問題中，改變其價值系數(shù)cj，反應到最終單純形表中，除xj檢驗數(shù)有改變外，對其它各數(shù)字無影響。[]15.單純形迭代中添加人工變量目標是為了得到問題一個基本可行解。[]16.訂購費為每訂一次貨所發(fā)生費用，它同每次訂貨數(shù)量無關。[]17.[]18.在物資價格有折扣存貯模型中，計算費用時必須考慮物資本身費用。[]19.若線性規(guī)劃問題具備可行解,且可行解域有界,則該線性規(guī)劃問題最多具備有限個數(shù)最優(yōu)解。[]20.對一個有n個變量，m個約束標準型線性規(guī)劃問題，其可行域頂點數(shù)恰好為個。[]21.檢驗數(shù)Rj表示非基變量xj增加一個單位時目標函數(shù)改變量。[]22.在求網絡最大流問題中，最大流流量是惟一，但最大流不一定惟一。[]23.[]24.狀態(tài)轉移方程為狀態(tài)變量和決議變量函數(shù)關系。[]25.任何線性規(guī)劃問題一定有最優(yōu)解。[]26.一旦一個人工變量在迭代中變?yōu)榉腔兞亢?，該變量及對應列?shù)字若從單純形表中刪除，將會影響后面計算結果。[]27.影子價格是企業(yè)生產過程中資源一個隱含潛在價值，表明單位資源貢獻，與市場價格是不一樣兩個概念。[]28.指派問題效率矩陣每一行（或每一列）元素分別減去一個常數(shù)，將不影響最優(yōu)指派方案。[]29.任意可行流流量不超出任意割集割量。[]30.當訂貨數(shù)量超出一定值允許打折扣情況下，打折扣條件下訂貨批量要大于不打折扣時訂貨批量。[]31.Dijkstra算法(T、P標號算法)要求邊長度非負。[]32[]33.在其余費用不變情況下，伴隨單位存貯費用增加，最優(yōu)訂貨批量也對應增大。[]34.運輸問題用閉回路法和用位勢法求得檢驗數(shù)不相同。[]35.容量網絡中可行流是最大流充要條件是不存在發(fā)點到收點增廣鏈。[]36.在其余費用不變情況下，伴隨單位缺貨費用增加，最優(yōu)訂貨批量也對應減小。[]37.在任一圖G中，當點集V確定后，樹圖是G中邊數(shù)最少連通圖。[]38.對偶問題對偶是原問題。[]39.求網絡最大流問題可歸結為求解一個線性規(guī)劃模型。[]40.互為對偶問題，或者同時都有最優(yōu)解，或者同時都無最優(yōu)解。[]二、建模題：1.某煉油企業(yè)為提升煉油能力和增加企業(yè)經濟效益，經研究有五種技術改造投資方案可供選擇，它們所需投資費用年收益如表1所表示。其中：方案1和方案2只能選擇其中一個，不能兼而實現(xiàn)，而且，如選擇方案2，則方案3必須同時選擇，或者都不選擇?，F(xiàn)該企業(yè)可供支配資金總額為：第一年有650萬元，第二年僅有460萬元。技術推行結果要求最少應增加出油能力500桶/天，但又不得超出1100桶/天。為了確定該企業(yè)總經濟效益最大投資方案，試建立該問題線性規(guī)劃模型。表1投資方案表方案序號技改方案內容決策變量投資（萬元）年收益（萬元）第一年第二年1更新舊裝置，提升煉油能力500桶/天X12002001002建造新裝置，提升煉油能力1000桶/天X23001502003往新廠建輸油管，提升煉油能力100桶/天X315050504往老廠建輸油管，提升煉油能力50桶/天X410070305增加槽車運輸能力，能提升出油20桶/天X55040202.某鋼廠軋制薄銅板知卷寬度為100CM，現(xiàn)在要在寬度上進行切割以完成以下訂貨任務：24cm寬75卷，40cm50卷和32cm寬110卷，長度都是一樣。試求處理切割方案線性規(guī)劃模型，使切割剩下邊料最少。3.寫出下面線性規(guī)劃問題對偶問題。4.寫出下面線性規(guī)劃問題對偶問題：三、填空題：1.某企業(yè)利用三種原料生產五種產品，其關于數(shù)據(jù)如表2，企業(yè)決議是這五種產品各生產多少使企業(yè)贏利最大。表2產品原料萬件產品所用原料數(shù)（千克）資源量（千克）ABCDE甲乙丙0.510.500.50.50－0.51.510.5111151210.5萬件產品利潤（萬元）41051010.5已知該問題建立線性規(guī)劃模型最優(yōu)單純形表如表3所表示，依照提供信息完成填空。表3cj41051010.5000CBXBx1x2x3x4x5x6x7x8b10.5010x5x7x4121012000.25-0.5-1.50011-1.5-0.5-1010-201101.250.5－Z-1.5-1-5.500-10-101)該問題最優(yōu)解。2)目標函數(shù)值。3)設y1,y2,y3為對應對偶變量，則y1,y2,y3含義可表述為：。4)對偶問題最優(yōu)解是。5)企業(yè)關鍵資源是。2.已知某求極大值（Max型）線性規(guī)劃問題初始單純形表及最終單純形表以下，依照表中提供信息及單純形表迭代規(guī)律完成填空。Cj41500CBXBx1x2x3x4x5bθ0x43141080000x5214013000－Z415000……0x40-1/2-21-3/235004x11a201/2b－Zc-1d0e-60001)該規(guī)劃問題初始基本可行解為。2)初始單純形表中，若選變量x3入基，則出基變量為，目標函數(shù)增加值為。3)單純形表迭代時，圍繞主元，經過線性變換需把入基列變成。4)最終單純形表中，基變量為。5)最終單純形表中，系數(shù)a＝。6)最終單純形表中，x1值b=。7)最終單純形表中，檢驗數(shù)c=,d=,e=。3.已知某線性規(guī)劃問題用單純形法計算時得到初始單純形表及最終單純形表見下表，依照單純形表迭代規(guī)律完成填空。cj2－11000CBXBx1x2x3x4x5x6b000x4x5x63111－1112－1100010001601020－Z2－110000……0x40a11－1－2b2x1c00.501/21/2dex201－1.50－1/21/2f－Z0gh0－3/2－1/2i1)最終單純形表中基變量為。2)最終單純形表第一行，a=，b=。3)最終單純形表第二行，c=，d=。4)最終單純形表第三行，e=，f=。5)目標函數(shù)行，g=，h=，i=。4.下面為一線性規(guī)劃模型（Max型）迭代過程中某一單純形表，表中CB列表示對應基變量價值系數(shù)。Cj行表示各變量價值系數(shù)。（）（）（）（）（）4（）102-1206（）01-1130-Z0-30-2-2-260要求：1)把單純形表中空格補充完整。2)基本可行解為：X*＝（）T。3)目標函數(shù)值為：Z＝（）。4)當前基本可行解是否是最優(yōu)解。（）[注：填是或不是]四、計算題：1.對于線性規(guī)劃模型，請先把模型化成標準型，然后用單純形表迭代求其最優(yōu)解。2.某廠從國外引進一臺設備，由工廠A至G港口有多條通路可供選擇，其路線及費用如圖1所表示。現(xiàn)要確定一條從A到G使總運費最小路線，請將該問題描述成一個動態(tài)規(guī)劃問題，然后求其最優(yōu)解。AAB1C2G2030圖1B2C1C3D11D217060504000304030103.已知某運輸問題供輸關系及單位運價表以下表示：產地銷地B1B2B3產量A14258A23537A31324需求量485①列出產銷平衡表，并用行列差值法給出該運輸問題初始基可行解。②用位勢法求初始可行解對應各非基變量檢驗數(shù)。③求出該運輸問題最優(yōu)解。4.把以下線性規(guī)劃問題化成標準型，然后用單純形法求最優(yōu)解及目標函數(shù)值。5.求下面網絡節(jié)點1到節(jié)點7最短路徑。vv2v3v4v6v7v14655567v5418126.某商店擬購進一個應時商品出售。經估算，在未來旺季中每出售一箱可凈得利潤5000元，如旺季過后則只能削價出售，每箱要賠本元。這種商品需求情況經統(tǒng)計分析，具備以下分布規(guī)律：需求量（箱）012345概率P（R）0.050.10.250.350.150.1現(xiàn)商店經理需作出訂購該商品多少箱決議，其最優(yōu)決議是訂購多少箱？贏利期望值為多大？最小損失期望值又是多大？7.求圖中最小樹及最小樹權。55v1v2v3v4v6v7v8v5654562783334418.某企業(yè)打算在三個不一樣地域設置4個銷售點，依照市場預測部門估量，在不一樣地域設置不一樣數(shù)量銷售店，每個月可得到利潤如表1所表示。試問在各個地域應怎樣設置銷售點，才能使每個月取得總利潤最大？其值是多少?表1銷售店利潤地域012341016253032201217212230101416179.某企業(yè)每年需電感5000個，每次訂購費50元，存貯費為1元/個·年，不允許缺貨。若采購少許電感每個單價3元，若一次采購1500個以上則每個單價1.8元，問該企業(yè)每次應采購多少個？10.某地電力企業(yè)有三個發(fā)電站，它們負責5個城市供電任務，其輸電網絡如圖4所表示。由圖可知，城市8因為經濟發(fā)展，要求供給電力65MW，三個發(fā)電站在滿足城市4、5、6、7用電需要量后，它們還分別剩下15MW、10MW、40MW，輸電網絡剩下輸電能力見圖4節(jié)點上是數(shù)字。三個發(fā)電站在滿足城市4、5、6、7用電需要量后，剩下發(fā)電能力共有65MW，與城市8用電量剛好相等。問：（1）輸電網絡輸電能力是否滿足輸電65MW電力；（2）如不滿足，需要增建或改建那些輸電線路?4545101520203015401540MW15MW1010MW21346578圖411.加工制作羽絨服工廠預測下年度銷售量為15000件。準備在整年300個工作日內均衡組織生產。假如為加工制作一件羽絨服所需各種原材料成本為48元，又制作一件羽絨服所需原料年存貯費為其成本22％。提出一次訂貨所需費用為250元，訂貨提前期為零，不允許缺貨，試求經濟訂貨批量及訂購周期。12.設某工廠自國外進口一部精密機器，由機器制造廠至出口港有三個港口可選擇，而進口港又有三個可選擇，進口后可經由兩個城市抵達目標地，其間運輸費用如圖所表示（單位：百元），試把該問題描述成一個多階段決議問題，并用動態(tài)規(guī)劃方法求解。202040307040203010405603030303040401050AB1B2B3C1C2C3D1D2E13.試用表上作業(yè)法求解下面運輸問題最優(yōu)解。（要求用行列差值法給初始解，用位勢法求檢驗數(shù)。）銷地產地B1B2B3供給量A16424A28575需求量33314.某建筑工地每個月需求水泥量為1200噸，每噸定價為1500元，不允許缺貨。設每噸每個月存放費為價格2％，每次訂貨費為1800元，需要提前7天訂貨。試求經濟訂購批量、每個月總費用和再訂貨點?！哆\籌學》課程復習資料參考答案一、判斷題：1.√2.×3.√4.√5.×6.√7.√8.√9.×10.√11.╳12.√13.×14.√15.√16.√17.√18.√19.×20.×21.√22.√23.√24.√25.╳26.×27.√28.√29.√30.√31.√32.×33.×34.×35.√36.×37..√38.√39.√40.√二、建模題：1.見教材1.2節(jié)線性規(guī)劃問題建模。2.解：設在100cm寬薄銅板上能切割40㎝寬薄銅板U個，32㎝寬薄銅板V個，24㎝寬薄銅板W個，則有以下切割方式：UVW余料<24①20020②1114③10212④0304⑤02112⑥01220⑦0044設xj為上述第j種切割方式切割100㎝銅板數(shù)，有：3.其對偶問題為：或4.對偶問題為：三、填空題：1.X＝(0,0,0,0.5,10,0,1.25)T。Z＝110。y1,y2,y3分別為甲、乙、丙三種資源出售帶來價值增值（或利潤）。。甲、丙資源。提醒：若原問題是Max型，則對偶變量值為對應松弛變量檢驗數(shù)負值。2.1）（0,0,0,8000,3000）T2）x537503）單位列向量4）x4，x15）-1/26）15007）0-3-2提醒：求該題時注意：（1）單純形表中基變量系數(shù)列向量為單位列向量，檢驗數(shù)為0。（2）依照單純形表計算公式求出各變量xj檢驗數(shù)，由計算目標函數(shù)值或某個基變量值。（3）在最優(yōu)單純形表中，松馳變量x4,x5兩列系數(shù)向量為當前基逆矩陣B-1，由（向量b為初始單純形表中方程右邊常數(shù)向量），也可求出基變量值。如此題：3.1）x4,x1,x22)0103）1154)-155）0-1.5-254.（4）（2）（6）（0）（0）4（x1）102-1206(x3)01-1130-Z0-30-2-2-2601)單純形表填空如上表示。2)基本可行解為：X*＝（20,0,30,0,0）T3)目標函數(shù)值為：Z＝（260）。4)是四、計算題：1.見教材1.4.5單純形表。2.解：把問題分為4個階段，A→B（可選B1,B2）,B→C（可選C1,C2）,C→D（可選D1,D2）,D→G各為一個階段。設Sk為每一階段起點，xk為第k階段決議變量，狀態(tài)轉移方程為：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邊界方程為：。下面列表計算以下：k=4時：x4S4x4GD13030GD24040Gk=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。3.①產大于銷，增添假想銷地B4，列出產銷平衡表，用行列差值法給初始解以下表示：銷地產地B1B2B3B4產量行差值A14（×）2（8）5（×）0（×）82,2,3A23（×）5（0）3（5）0（2）73,0,2A31（4）3（×）2（0）0（×）41,1,-需求量4852列差值2,2,-1,1,31,1,22,-②用位勢法求初始可行解對應各非基變量檢驗數(shù)：對基變量有：Rij=cij－(ui+vj)=0，求出行、列位勢，如表示：銷地產地B1B2B3B4產量行位勢A14（×）2（8）5（×）0（×）8u1=0A23（×）5（0）3（5）0（2）7u2=3A31（4）3（×）2（0）0（×）4u3=2需求量4852列位勢v1=－1v2=2v3=0v4=－3利用Rij=cij－(ui+vj)求出非基變量檢驗數(shù)：R11=5，R13=5，R14=3，R21=1，R32=－1，R34=1。③選x32為入基變量，作閉回路調整，調整量為0，如表示：銷地產地B1B2B3B4行位勢A14（×）2（8）5（×）0（×）u1=0A23（×）5（×）3（5）0（2）u2=2A31（4）3（0）2（0）0（×）u3=1列位勢v1=0v2=2v3=1v4=－2再次利用Rij=cij－(ui+vj)求出非基變量檢驗數(shù)：R11=4，R13=4，R14=2，R21=1，R22=1，R34=1。當前調運方案為最優(yōu)方案，如上表示，最小運費Z＝2×8＋3×5＋1×4＝35。4.見教材1.4.5單純形表。5.用T、P標號算法：①給v1點標P標號，其余點標T標號，為＋∞。②從v1點出發(fā)，修改v2、v3、v4點T標號，并把其中最小者改為P標號。T(v2)=4=P(v2)，T(v3)=6，T(v4)=5=P(v4)。③從剛才取得P標號點v2出發(fā)，可達v3,v5（與其相鄰且還未取得P標號點）,修改其T標號，并把最小T標號v3,v5改為P標號。T(v3)=min{6，p(v2)+d23}=min{6,4+1}=5=P(v3)，T(v5)=11。④依這類推，各點P標號如圖所表示。從v1到v7最短路為：v1→v2→v3→v5→v7或v1→v2→v3→v6→v5→v7，距離為16。44v2v2v3v4v6v7v14655567v541812105516016099556.解：由題意有：α＝5000元，β＝元由表中累計概率可知：最優(yōu)決議是訂購3箱。贏利期望值：E[C(Q)]＝－×3×0.05＋（5000－×2）×0.1＋（5000×2－×1）×0.25＋5000×3×0.6＝10800元。同理可計算出最小損失期望值為2950元。7.解：用破圈法求得最小部分樹為：vv1v2v3v4v6v7v8v54233315最小部分樹權為：1＋3+3＋3+2＋4+5＝21。8.解：設給每一個地域設置一個銷售點為一個階段，共三個階段。xk為給第k個地域設置銷售點數(shù)。Sk為第k階段還剩下銷售點數(shù)，S1＝4狀態(tài)轉移方程為：Sk+1=Sk－xkdk(xk)為在第k個地域設置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)決議方案為：第一個地域設置2個銷售點，第二個地域設置1個銷售點，第三個地域設置1個銷售點，每個月可獲總利潤為47。9.R=5000(個/年)，co=50(元/次),ch=1(元/個·年)首先計算出經濟訂購批量：（個）分情況討論：①設Q*=715，則每年訂購7次，年費用為：F1=5000×3+50×7+（1×715）/2=15707.5元②設Q*=1500，則每年訂購4次，年費用為：F1=5000×1.8+50×4+（1×1500）/2=9950元③設Q*=5000，則每年訂購1次，年費用為：F1=5000×1.8+50+（1×5000）/2=11550元故應考慮折扣，該企業(yè)每次采購1500個以上，5000個以下。詳細采購數(shù)量可視企業(yè)流動資金等詳細情況而定。10.解：(1)虛構發(fā)點vs，如圖示。(2)求出網絡最大流如圖示，最大流量為55，不滿足輸電65MW電力。(3)在飽和弧v5－v8上增建輸送10MW新線路，使其容量增加到20MW，而把非飽和弧vs→v1→v4→v6及vs→v3→v6弧上各增加5MW流量，v6→v5弧上增加10MW流量，即可滿足輸電65MW電力需求量。vvs45,4510,1015,1520,1020,2030,1515,1040,10