2014年929管理運(yùn)籌學(xué)1答案

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

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

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

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

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

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

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

8、題很明顯是一道考查0-1規(guī)劃的投資問(wèn)題建模題，一般的思路是，針對(duì)第j個(gè)項(xiàng)目，只有投資和不投資兩種狀態(tài)，所以可以用0-1變量X來(lái)描述這兩種狀態(tài)：*=1表示投資第j個(gè)項(xiàng)目，*=0表示不投資。但在現(xiàn)實(shí)的投資問(wèn)題中會(huì)有許多特殊要求，像排斥問(wèn)題、優(yōu)先級(jí)問(wèn)題、不可缺問(wèn)題等，而這些需要通過(guò)約束條件方程來(lái)表述。0-1規(guī)劃問(wèn)題模型的解1第i個(gè)項(xiàng)目被投資0第i個(gè)項(xiàng)目不被投法采用隱枚舉法。P167解：引入 0-1 變量 x (i =A,B,C,D,E)，設(shè) 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五、計(jì)算題（85分，共5小題）（答在試卷上的內(nèi)容無(wú)效）1、（ 15分）用兩階段法求下列線性規(guī)劃模型的最優(yōu)解。min z =2x 3x2fl 1/XAx220% 十 X2 = 10Xi，X2-0解析：題目中已經(jīng)明確給出了用兩階段法來(lái)求解線性規(guī)劃模型，所以這道題就只能用此方法來(lái)解答， 考查的就是基礎(chǔ)的兩階段法，往年沒(méi)有考過(guò)，考生往往也就疏忽了對(duì)基礎(chǔ)知識(shí)的復(fù)習(xí)，做起來(lái)就比較生 疏，而且中間不小心算錯(cuò)了，后面的都白算，因此應(yīng)該重視基礎(chǔ)知識(shí)的復(fù)習(xí)以及加強(qiáng)計(jì)算能力。解：將模型化為如下形式，其中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àn)數(shù)表明未達(dá)到最優(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àn)數(shù)表明還未達(dá)到最優(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由上表可知，非基變量檢驗(yàn)數(shù)全部0,已達(dá)到最優(yōu)解，且基變量中不含有人工變量，所以轉(zhuǎn)入第二階段：恢復(fù)原來(lái)的目標(biāo)函數(shù)，繼續(xù)用單純形法求解。改變后如下表：CjT2300CBXBbXIX2X3X40X31/4001-1/83X25010-1/22

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

13、 (2)使最優(yōu)解不變的C 2的變化范圍；Xg r-21對(duì)應(yīng)的系數(shù)變?yōu)閍, = 0，模型的解會(huì)有什么變化？J21-.5-(4)增加一個(gè)新的約束條件2xX25X3- 50,模型的解會(huì)有什么變化？解析：這是一道綜合計(jì)算題，既考查了對(duì)偶單純形法的應(yīng)用又考查了靈敏度分析的計(jì)算，這是每年必考的計(jì)算題之一，雖然變化的類型不算多，但靈活性比較高，需要自己總結(jié)歸納，解：(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此時(shí)，所有的非基變量檢驗(yàn)數(shù)均小于0,達(dá)到最優(yōu)解，最優(yōu)解為(為必氏必風(fēng))=(0,0,2,4,0)，目標(biāo)函數(shù)最優(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)解不會(huì)發(fā)生變化。(4)增加一個(gè)新的約束條件2X1 X2 5XA 50，引入松弛變量X6化為2X1 X2 5X3 XA = 50 ,其中X6 -0，把X6作為基變量，然后把這個(gè)方程的系數(shù)補(bǔ)加到題目中給出單純形表的最后一行中，得下表Cj-5513000CBXBbX1X2X3X4X5X65X220-1131000X510160-2-4100X650215001進(jìn)行初等變換，使基變量的系數(shù)矩陣變?yōu)閱挝痪仃?，如下?Cj-5513000CBXBbX1X2X3X4X5X65X220-1131000X510

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

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

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

19、Xi3，X33, X31可以構(gòu)成一個(gè)閉回路，故不可作為初始可行解。（2）構(gòu)造綜合表，在綜合表的最右邊補(bǔ)一列，在最下面補(bǔ)一行，然后分別計(jì)算差值并填入表中，如下 表：、銷地 產(chǎn)地BiB2B3產(chǎn)量差值A(chǔ)iXiix2x13153A2x21x22x23112A3X31X32X33204銷量181216送=46差值215在上表中，最大差值5來(lái)自第二歹U,在第二歹U中沒(méi)有被標(biāo)識(shí)的變量所對(duì)應(yīng)的最小運(yùn)價(jià)是C13 = 2,在這里選擇變量X!3作為基變量。X3=15,并將取值畫上圈，處理后的綜合表如下:肖地產(chǎn)地B1B2XXA2x21x22A3x31x32銷量1812差值21B3產(chǎn)量差值2153x23112x3320

20、416Z=465對(duì)上表重新計(jì)算差值，按照上述方法找出基變量，處理后的綜合表如下:、銷地 產(chǎn)地BiB2B3產(chǎn)量差值A(chǔ)XX2150A2x21Xx23112A3X312X33204銷量181216送=46差值311重復(fù)上述步驟，處理后的綜合表如下:、銷地產(chǎn)地BiB2AiXXA23XA 3x312銷量1812差值30B3產(chǎn)量差值2150X114x3320216Z=461重復(fù)上述步驟，處理后的綜合表如下:、銷地 產(chǎn)地BiB2B3產(chǎn)量差值A(chǔ)iXX2150A23XX110A3628200銷量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,按照位勢(shì)法寫入表中，得下表:、銷地產(chǎn)地-4B2產(chǎn)量、。、1XX153A23XX116A320銷量181216送=46計(jì)算出所有非基變量的檢驗(yàn)數(shù)，并將求出的檢驗(yàn)數(shù)填到綜合表中對(duì)應(yīng)的非基變量xij的位置,如下表：、銷地產(chǎn)地、0Bi-4B22B3產(chǎn)量0A1559132*15153A23*1272116A36*21*28*20銷量181216送=46表中沒(méi)有負(fù)檢驗(yàn)數(shù)，說(shuō)明已經(jīng)是最優(yōu)解，即（心必廠乂彳廠乂彳？，X33）=（15,11,7,12,1）調(diào)運(yùn)方案為從A1運(yùn)到B3 15噸，從A2運(yùn)到B11噸，從A3運(yùn)到B1 7噸，從A3運(yùn)到B? 12噸，從A3運(yùn)到 B31 噸。則目標(biāo)函數(shù)值z(mì)=（2