2014年929管理運籌學1答案

1、西南交通大學2014年全日制碩士研究生入學試題解析試題名稱：管理運籌學一一、判斷題（20分，共5小題）（答在試卷上的內容無效）（對錯誤的選項應改錯或說明原因）1對一個有n個變量m個約束條件的標準型線性規(guī)劃模型，其可行域的頂點恰好為 TOC o 1-5 h z 呼個。（x）解析：可以舉個例子，假設是2兩個變量2個約束條件，那么可行域的頂點并不恰好為1個。2、 指派問題系數矩陣的某一行（列）各元素分別減去該行（列）的最小元素，得到的新矩陣求得的最優(yōu)解和原系數矩陣求得的最優(yōu)解相同。（V）3、 整數規(guī)劃模型的最優(yōu)目標函數值一定不大于其對應的線性規(guī)劃模型的最優(yōu)目標函數值。（V）4、 對于一個動態(tài)規(guī)劃問題

2、，應用順序解法或逆序解法可能會得到不同的結果。（X）解析：順序法和逆序法是解決動態(tài)規(guī)劃問題的兩種方法，對于同一個動態(tài)規(guī)劃問題，無論使用的是哪種方法，最后得出的結果是一定的，相同的。改錯：對于一個動態(tài)規(guī)劃問題，應用順序解法或逆序解法得到相同的結果。5、 存儲策略就是決定補充存儲數量的策略。（X）解析：存儲 策略不止是決定補充存儲數量，而且還決定補充時間，這里題目說的不全面。改錯：決定何時補充，補充多少數量的辦法稱之為存儲策略。二、簡答題（20分，共2小題）（答在試卷上的內容無效）1、（ 10分）如下所示的網絡，每條弧旁邊的數字是（q、）， （ Cj、幣）分別表示該弧的容量和流量。試判斷該網絡流是

3、否為最人流，并找出其最小截集占解析：這是一道考查網絡的流中最大流的基礎題，判斷網絡流是否為最大流，首先知道該如何判斷，就是看網絡圖中還是否存在增流鏈，是對課本中求網絡最大流方法步驟的考查，判斷找出了最大流，根據被標號的點和未被標號的點就找出了最小截集，這里給出兩種解法。(由于是簡答題，解法一可以簡略一些回答)解法一：1、標記過程(1 )先給源Vs標號(0,:)(2)對Vs進行檢查，從Vs出發(fā)的邊(* , V)上，fsi Cs,，故V的標記為(+ Vs , I (V2),其中，l(vj=min 訃(Vs),(Csi- fs) = min =7,邊叫)，f,2= C?，故 V?得不到標記。Vs成為

4、已檢查過的點。(3 )取己標記而未檢查的點V，檢查V，在邊(VJ上，以E3Z/luT0-/us 1 4 2 3 t， I :修改后如下圖(2,2)V%修改后該鏈為飽和鏈，繼續(xù)標號查視Vs標記Vs一標號+ OO已不存在由Vs到、的增流鏈。故可以判斷該網絡流不是最大流，已標記的頂點集合為y -，未標記的頂點集合V v乂乂，V ,v/?故有K （V,V） = i （V,V） , （V,V）是該網絡的最小截集。I = iVi 2 3 4 ，i，is is2。久 匚I lij _t|x/J 舊un。2、（ 10分）若如上所示的網絡圖，已知各弧的單位流量費用為bj，現要在已知最大流的基礎上求最小費用流，試

5、簡述其方法。（不用計算結果）解析：這道簡答題考查的是最小費用流的算法過程，題目比較簡單，在課本中給出了詳細步驟。解：（1）針對已知最大流為7的網絡圖G,構建伴隨網絡流f的增流網絡Gf（2）針對增流網絡G”查看是否存在基于W的負回路；若不存在，說明當前網絡流已經 TOC o 1-5 h z 是最小費用流，算法終止，否則轉到（3）。（3） 針對存在的負回路C，令=min?c （e） ,e為Gf中負回路的邊（4）針對負回路C對應的運輸網絡G中的圈，判斷該圈是否為增流圈；若不是，轉到（2）繼續(xù)尋找負回路，否則轉（5）。（5）針對運輸網絡G中的增流圈，把增流圈中方向與負回路方向一致的所有不飽和邊的流量加

6、上；把增流圈中方向與負回路方向相反的所有正邊的流量減去。（6） 繼續(xù)尋找負回路，若有負回路，繼續(xù)調整，否則轉（1）。三、證明題（10分，共1小題）（答在試卷上的內容無效）試用對偶理論證明下列線性規(guī)劃模型為無界解。maxZ = 3 為 4x2 x3-X| 2x2 3x3 三 6st+x2 4x3 蘭 7KM 0解析：對偶問題的基本性質中弱對偶性是?？嫉淖C明題，這里考查的是弱對偶性里的推論3:若原問題可行，而對偶問題不可行，則原問題的目標函數值無界。解：令 =x2 =x3 =0，滿足約束條件，可知原問題可行。該問題的對偶問題為min w =6% 7y2% 3 y?二 32% +y2 3 4st3*

7、-4y2 二 1V, yA0由約束條件i可知對偶問題不可行，由對偶問題弱對偶性的推論可知，原問題的為無界解。四、建模題（15分，共1小題）（答在試卷上的內容無效）某企業(yè)有5個擬選擇的投資項目，其所需投資額與期望收益如下表所示。由于各項目之間有一定的聯 系，A、C、E之間必須選擇一項，且僅需選擇一項；B和D之間需選擇，也僅需選擇一項；又由于C和D兩項目密切相關，C的實施必須以D的實施為前提條件。該企業(yè)共籌集資金 1500萬元。試構建相應的模型以確定應該選擇哪些項目投資，使期望收益最大。（不用求解）項目所需投資額（萬兒）期望收益（萬元）A60100B4080C2070D4060E5090解析：這道

8、題很明顯是一道考查0-1規(guī)劃的投資問題建模題，一般的思路是，針對第j個項目，只有投資和不投資兩種狀態(tài)，所以可以用0-1變量X來描述這兩種狀態(tài)：*=1表示投資第j個項目，*=0表示不投資。但在現實的投資問題中會有許多特殊要求，像排斥問題、優(yōu)先級問題、不可缺問題等，而這些需要通過約束條件方程來表述。0-1規(guī)劃問題模型的解1第i個項目被投資0第i個項目不被投法采用隱枚舉法。P167解：引入 0-1 變量 x (i =A,B,C,D,E)，設 Xj =max z = 100 xa 80 冷 70Xc60XD 90 xe 60 xa +40 xb +20 xc +40 xd +50 xe 蘭 1500

9、XA +XC +XE =1 stXB+XD 蘭 1Xc 蘭 XDx =0 或 1五、計算題（85分，共5小題）（答在試卷上的內容無效）1、（ 15分）用兩階段法求下列線性規(guī)劃模型的最優(yōu)解。min z =2x 3x2fl 1/XAx220% 十 X2 = 10Xi，X2-0解析：題目中已經明確給出了用兩階段法來求解線性規(guī)劃模型，所以這道題就只能用此方法來解答， 考查的就是基礎的兩階段法，往年沒有考過，考生往往也就疏忽了對基礎知識的復習，做起來就比較生 疏，而且中間不小心算錯了，后面的都白算，因此應該重視基礎知識的復習以及加強計算能力。解：將模型化為如下形式，其中X3為松弛變量，X4為多余變量，X

10、5, x6為人工變量1x. x=44 2 3stXj3x? X4+X5= 20 為 +x2 +x6 =10 Xj-0(j =123,4,5,6)CB第一階段的初始單純性表如下:CjT000011CBXBb0X31X51X6ZjCj z0X341/21/410001X520130-1101X10110001Zj240-111CjZj-2-40100表中檢驗數表明未達到最優(yōu)解，把X2作為換入變量，CjT00CBX BbXiX2X5作為換出變量，得到如下單純形表：001XXX只3451X60X37/35/12011/12-1/1200X220/31/310-1/31/301X10/32/3001/3

11、-1/31Zj2/3001/3-1/31Cj-Zj表中檢驗數表明還未達到最優(yōu)解，表-2/3把X00-1/31作為換入變量，X6作為換出變量，4/3得到如下單純形0：CjT000011cBXBbX1X2X3X4X5X60X31/4001-1/81/8-5/80X25010-1/21/2-1/20X151001/2-1/23/2Zj0000o0Cj-Zj000011由上表可知，非基變量檢驗數全部0,已達到最優(yōu)解，且基變量中不含有人工變量，所以轉入第二階段：恢復原來的目標函數，繼續(xù)用單純形法求解。改變后如下表：CjT2300CBXBbXIX2X3X40X31/4001-1/83X25010-1/22

12、*51001/2Zj000-1/2Cj _召0001/2由檢驗數可知，上表已達到最優(yōu)解，求出的最優(yōu)解為1（為*飛3飛4飛5羌）=（5,5, 一，0,0,0），目標函數值為z=2 5 3 5 = 25。42、（ 25分）考慮如下線性規(guī)劃問題max z = -5*5X213X3+x2+3x3 蘭 20stt?12x4x2+10 x3 蘭 90*02,3）分別對兩個約束條件引入松弛變量X4,x5,用單純形法得到如下最優(yōu)單純形表。Cj-551300CBXBbXIX2X3X4x5X2X52010:03-40CT00-2-50不用重新求解，分別分析如下問題。(1)約束條件的右邊常數變?yōu)? Ib2 20 1

13、 (2)使最優(yōu)解不變的C 2的變化范圍；Xg r-21對應的系數變?yōu)閍, = 0，模型的解會有什么變化？J21-.5-(4)增加一個新的約束條件2xX25X3- 50,模型的解會有什么變化？解析：這是一道綜合計算題，既考查了對偶單純形法的應用又考查了靈敏度分析的計算，這是每年必考的計算題之一，雖然變化的類型不算多，但靈活性比較高，需要自己總結歸納，解：(1) Bd101101;，代入單純形表 1 04 14 1 一2熟練掌握。Cj-551300CBXBbX1X2X3X4X55X210-113100X5-20160-2-41aj00-2-5025x5為換出變量，V，-2-4故X3為換入變量，得新

14、的單純形表Cj-551300cBXBbX1X2X3X4X55X2-202310-53/213X310-8012-1/2aj-160X2為換出變量，X4為換入變量，得新的單純形法如下：0-1-1一 20 得：Cj-551300CBXBbX2X3X4X5:X4X34-23/56/5-1/52/500-3/101/10a-103/5-1/500-13/10此時，所有的非基變量檢驗數均小于0,達到最優(yōu)解，最優(yōu)解為(為必氏必風)=(0,0,2,4,0)，目標函數最優(yōu)值為z = 26(2)X2為基變量，故maXX-2/3),(-5/1)A .：即-2/3心乞0cA minb/(1*那么c2值得允許變化范圍

15、就是13/3,5】。(3)|-01-4PT*5:; i - ci CB P| = -200 5所以最優(yōu)解不會發(fā)生變化。(4)增加一個新的約束條件2X1 X2 5XA 50，引入松弛變量X6化為2X1 X2 5X3 XA = 50 ,其中X6 -0，把X6作為基變量，然后把這個方程的系數補加到題目中給出單純形表的最后一行中，得下表Cj-5513000CBXBbX1X2X3X4X5X65X220-1131000X510160-2-4100X650215001進行初等變換，使基變量的系數矩陣變?yōu)閱挝痪仃?，如下?Cj-5513000CBXBbX1X2X3X4X5X65X220-1131000X510

16、160-2-4100X630302-10100-2-500表滿足最優(yōu)檢驗，基變量也可行，得到最優(yōu)解G卷，X2,X3,X4,X5,X6）=（0,20,0,0,10,30），模型的解不變。3、（ 10分）六個城市G （仁i乞6）間航空票價q （表示g與C.間票價，單位：100元）見F表（：表示無直接航線），現在要設計出任何兩城市間票價最廉的路線方案。請建立模型,并以C i與其他城市間方案為例作具體說明。0 500040251001520oQ250102000(Cij)6 601025055解析：從題目給出的矩陣可以聯想到圖與網絡中介紹的無向圖，所以這個問題考查的是圖與網絡的最短路問題，轉化成無向圖

17、即建立了最短路的模型。P226解：（1）用圖表示出來題目中矩陣即建立了任何兩城市間票價路線方案模型，如下圖也可以建立如下的網絡模型圖:由上表可知Ci到C2的最短徑路是：Gr J C?費用3500Ci到 C3的最短徑路是：GrC6rC4rC 或 G r C5 r C4Q3 或 G C5 r C費用4500。Ci到C4的最短徑路是：G r C5 r C4或G r CA - C4費用3500。q到C5的最短徑路是：G rC5費用2500元q到C6的最短徑路是：G rC6費用1000元4、（20分）有某物資從A|5A25Aj處運往BB2E3三個地方，各處供應量、需求量（單位：t）及單位運價（單位：10

18、元/t）見下表。、銷地產地BiB2B3產量a59215A31711a62820銷量181216判斷以下給出的方案可否作為初始可行解（說明判斷依據）？并求物資最優(yōu)調運方案及其最小總費用。銷地產地B1B2B3a312A211a1514解析：這道題考查的是運輸問題的基本定理和表上作業(yè)法求產銷平衡運輸問題的最優(yōu)值算法，難度不大，還可以考查產銷不平衡或產銷量不確定等條件的運輸問題來增加難度，運輸問題是每年必考的計算題之一，應予以重視。解：（1）題目給出的方案不可以作為初始可行解，雖然產銷平衡，但是根據定理：m+n-1個變量構成基本可行解的充要條件是它不含閉回路。而給出的方案中基變量個數為6個，而且Xn，

19、Xi3，X33, X31可以構成一個閉回路，故不可作為初始可行解。（2）構造綜合表，在綜合表的最右邊補一列，在最下面補一行，然后分別計算差值并填入表中，如下 表：、銷地 產地BiB2B3產量差值AiXiix2x13153A2x21x22x23112A3X31X32X33204銷量181216送=46差值215在上表中，最大差值5來自第二歹U,在第二歹U中沒有被標識的變量所對應的最小運價是C13 = 2,在這里選擇變量X!3作為基變量。X3=15,并將取值畫上圈，處理后的綜合表如下:肖地產地B1B2XXA2x21x22A3x31x32銷量1812差值21B3產量差值2153x23112x3320

20、416Z=465對上表重新計算差值，按照上述方法找出基變量，處理后的綜合表如下:、銷地 產地BiB2B3產量差值AXX2150A2x21Xx23112A3X312X33204銷量181216送=46差值311重復上述步驟，處理后的綜合表如下:、銷地產地BiB2AiXXA23XA 3x312銷量1812差值30B3產量差值2150X114x3320216Z=461重復上述步驟，處理后的綜合表如下:、銷地 產地BiB2B3產量差值AiXX2150A23XX110A3628200銷量181216送=46差值000在上表中，X13 , X2” X31 , X32氐3為基變量，因此有如下方程式組:U1

21、V3 = Ci3 = 2U2 V|_ c/ 3U3V1 - C31 =6U3 V2 - C32= 23 v3 = C33 = 8令比二0,按照位勢法寫入表中，得下表:、銷地產地-4B2產量、。、1XX153A23XX116A320銷量181216送=46計算出所有非基變量的檢驗數，并將求出的檢驗數填到綜合表中對應的非基變量xij的位置,如下表：、銷地產地、0Bi-4B22B3產量0A1559132*15153A23*1272116A36*21*28*20銷量181216送=46表中沒有負檢驗數，說明已經是最優(yōu)解，即（心必廠乂彳廠乂彳？，X33）=（15,11,7,12,1）調運方案為從A1運到B3 15噸，從A2運到B11噸，從A3運到B1 7噸，從A3運到B? 12噸，從A3運到 B31 噸。則目標函數值z=（2