2014管理運籌學(xué)一

1、試題代碼：929西南交通大學(xué)2014年碩士研究生招生入學(xué)考試試題名稱：管理運籌學(xué)一考試時間：2014年1月考生請注意：1、本試題共五題，共4頁，滿分150分，請認真檢查；2、答題時，直接將答案內(nèi)容寫在考場提供的答題紙上，答在試卷上的內(nèi)容無效；3、請在答題紙上按要求填寫試題代碼和試題名稱；4、試卷不得拆開，否則遺失后果自負。一判斷題（20分，共5小題）（答在試卷上的內(nèi)容無效）（對錯誤的選項應(yīng)改錯或說明原因）對一個有n個變量m個約束條件的標準型線性規(guī)劃模型，其可行域的頂點恰好為 TOC o 1-5 h z Cm個。（X ）解析：可以舉個例子，假設(shè)是2兩個變量2個約束條件，那么可行域的頂點并不恰好

2、為1個。指派問題系數(shù)矩陣的某一行（列）各元素分別減去該行（列）的最小元素，得到的新矩陣求得的最優(yōu)解和原系數(shù)矩陣求得的最優(yōu)解相同。（V ）整數(shù)規(guī)劃模型的最優(yōu)目標函數(shù)值一定不大于其對應(yīng)的線性規(guī)劃模型的最優(yōu)目標函數(shù)值。（V ）對于一個動態(tài)規(guī)劃問題，應(yīng)用順序解法或逆序解法可能會得到不同的結(jié)果。（X ）解析：順序法和逆序法是解決動態(tài)規(guī)劃問題的兩種方法，對于同一個動態(tài)規(guī)劃問題，無論使 用的是哪種方法，最后得出的結(jié)果是一定的，相同的。改錯：對于一個動態(tài)規(guī)劃問題，應(yīng)用順序解法或逆序解法得到相同的結(jié)果。存儲策略就是決定補充存儲數(shù)量的策略。（X ）解析：存儲策略不止是決定補充存儲數(shù)量，而且還決定補充時間，這里題目

3、說的不全面。改錯：決定何時補充，補充多少數(shù)量的辦法稱之為存儲策略。二、簡答題（20分，共2小題）（答在試卷上的內(nèi)容無效）（10分）如下所示的網(wǎng)絡(luò)，每條弧旁邊的數(shù)字是（。、f ），（。、f分別表示該弧的 ij ij ij ij容量和流量）。試判斷該網(wǎng)絡(luò)流是否為最大流，并找出其最小截集。解析：這是一道考查網(wǎng)絡(luò)的流中最大流的基礎(chǔ)題，判斷網(wǎng)絡(luò)流是否為最大流，首先知道該如 何判斷，就是看網(wǎng)絡(luò)圖中還是否存在增流鏈，是對課本中求網(wǎng)絡(luò)最大流方法步驟的考查，判 斷找出了最大流，根據(jù)被標號的點和未被標號的點就找出了最小截集，這里給出兩種解法。（由于是簡答題，解法一可以簡略一些回答） 解法一：1、標記過程（1）先給

4、源七標號（0，8）（2）對V進行檢查，從V出發(fā)的邊（V，V ）上，f vc，故V的標記為（+Vsss 1s1s11s 1其中，l(v ) = min b(v ),(c - f R= min、8,1= 1，邊(v ,v)上，f = c，/ ，故頃不到標記。V成為已檢查過的點。(3)取已標記而未檢查的點V，檢查V，在邊(v ,V )上，f 0，故七的標記為（-V4,l A，其中，(4)檢查 V4，邊(v2,V4)上l(V ) = min(v ), f = min(1,1) = 1，邊(v ,v )上，f = c ，故v 得不到標記。242,44 t4,t4,tt檢查v ,邊(v , v )上，f

5、V c ,故v的標記為(+V ,l(v ),其中， TOC o 1-5 h z 232,32,3323l(v ) = min(v ),(c - f )= min,1= 1。322,32,3檢查v ,邊(v , v )上，f V c ,故v的標記為(+v ,l(t),其中，3 t3,t3,tt3l(t) = min(v3),(c3t -f3t)= minb,2= 1,因匯v,得到標記，進行調(diào)整。故可以判斷該網(wǎng)絡(luò)流并非最大流。調(diào)整過程反向追蹤，按頂點的第一個標記找到一條增流鏈Q(jìng) = vvvvvv。s 1 4 2 3 t按0 = l(t) =1調(diào)整增流鏈上各邊的流量：=f +0= 3 +1 = 4=

6、f +0 = 1 +1 = 2=f +0 = 2 +1 = 332,3f = f +0 = 4 +1 = 5f = f -0= 1 -1 = 02,42,4其他邊上流量保持不變。調(diào)整后的得到網(wǎng)絡(luò)圖上一個新的可行流，如下圖重復(fù)上述標記過程，尋找增流鏈。給v標記(0，+8)，檢查v，邊(v , v )上，f = c， sss 1s ,1s ,1邊(vs，v2)上，fs,2=cs,2，均不符合標記條件，標號過程無法進行，算法結(jié)束。上圖給出的可行流即為該網(wǎng)絡(luò)的最大流。最大流為：v( f *) = fs1 +乙=/ t + /廣7。已標記的頂點 集合為匕=，未標記的頂點集合V =v,v ,v ,v ,v

7、 ，故有111234 tK(V ,V) = b , v ),(v , v )是該網(wǎng)絡(luò)的最小截集。11s 1 s 2解法二:查視vsv1v4v2v3標記vsv1v4v2v3vt標號+ 8+1+1-1+1+1增流鏈為Q = WWW ,修改量= s 1 4 2 3 t修改后該鏈為飽和鏈，繼續(xù)標號查視vs標記vs標號+ 8已不存在由七到匕的增流鏈。故可以判斷該網(wǎng)絡(luò)流不是最大流，已標記的頂點集合為匕= *，未標記的頂點集合V = V , v , v , v , v ，故有K（V ,V） = b , v ）,（v , v ）是該網(wǎng)絡(luò)的最小截集。11234 t11s 1 s 22.（10分）若如上所示的網(wǎng)絡(luò)

8、圖，已知各弧的單位流量費用為七7.，現(xiàn)要在已知最大流的基礎(chǔ)上求最小費用流，試簡述其方法。（不用計算結(jié)果）解析：這道簡答題考查的是最小費用流的算法過程，題目比較簡單，在課本中給出了詳細步 驟。解：（1）針對已知最大流為7的網(wǎng)絡(luò)圖G，構(gòu)建伴隨網(wǎng)絡(luò)流f的增流網(wǎng)絡(luò)Gf。（2）針對增流網(wǎng)絡(luò)G，查看是否存在基于伊的負回路；若不存在，說明當(dāng)前網(wǎng)絡(luò)流已經(jīng)是最小費用流，算法終止，否則轉(zhuǎn)到（3）。（3）針對存在的負回路C ,令6 = min V（e）, eG負回路的邊匕（4）針對負回路C對應(yīng)的運輸網(wǎng)絡(luò)G中的圈，判斷該圈是否為增流圈；若不是，轉(zhuǎn)到2） 繼續(xù)尋找負回路，否則轉(zhuǎn)（5）。（5）針對運輸網(wǎng)絡(luò)G中的增流圈，把

9、增流圈中方向與負回路方向一致的所有不飽和邊的流 量加上6 ；把增流圈中方向與負回路方向相反的所有正邊的流量減去6。（6）繼續(xù)尋找負回路，若有負回路，繼續(xù)調(diào)整，否則轉(zhuǎn)（1）。三、證明題（10分，共1小題）（答在試卷上的內(nèi)容無效）試用對偶理論證明下列線性規(guī)劃模型為無界解。max Z = 3x + 4 x + x-x + 2 x + 3 x 6s.t. - 3x + x - 4x 0123解析：對偶問題的基本性質(zhì)中弱對偶性是常考的證明題，這里考查的是弱對偶性里的推論3： 若原問題可行，而對偶問題不可行，則原問題的目標函數(shù)值無界。解：令氣=x2= %= 0，滿足約束條件，可知原問題可行。該問題的對偶問

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

11、益（萬元）A60100B4080C2070D4060E5090解：引入 0-1 變量七（i = A, B,C, D, E），設(shè) I,=1第i個項目被投資0第i個項目不被投資解析：這道題很明顯是一道考查0-1規(guī)劃的投資問題建模題，一般的思路是，針對第j個項 目，只有投資和不投資兩種狀態(tài)，所以可以用0-1變量I,來描述這兩種狀態(tài)：I, = 1表示投 資第j個項目，= 0表示不投資。但在現(xiàn)實的投資問題中會有許多特殊要求，像排斥問題、 優(yōu)先級問題、不可缺問題等，而這些需要通過約束條件方程來表述。0-1規(guī)劃問題模型的解 法采用隱枚舉法。max z = 100 x + 80 x + 70 x + 60 x

12、 + 90 x60 xA + 40 xB + 20 xc + 40 xD + 50工日 1500s.t.x + x + x = 1x + x 1x xC DX = 0或 1四、計算題（85分，共5小題）（答在試卷上的內(nèi)容無效）1.（15分）用兩階段法求下列線性規(guī)劃模型的最優(yōu)解。min z = 2 x + 3x1211/s.t.2 x1 + 4 x2 20 氣+ x2 =10 x , x 0 解析：題目中已經(jīng)明確給出了用兩階段法來求解線性規(guī)劃模型，所以這道題就只能用此方法 來解答，考查的就是基礎(chǔ)的兩階段法，往年沒有考過，考生往往也就疏忽了對基礎(chǔ)知識的復(fù) 習(xí)，做起來就比較生疏，而且中間不小心算錯了

13、，后面的都白算，因此應(yīng)該重視基礎(chǔ)知識的 復(fù)習(xí)以及加強計算能力。解：將模型化為如下形式，其中為松弛變量，x為多余變量，x，x為人工變量 TOC o 1-5 h z 3456min z = x + xf151 6x + x + x = 42 14 23s.t. 0( j =61,2,3,4,5,6)第一階段的初始單純性表如下:c. T000011cBXBbx1x2x3x4x5x60 x341/21/410001x520130-1101x610110001zj240-111c - z,-2-40100表中檢驗數(shù)表明還未達到最優(yōu)解，把x2作為換入變量，尤5作為換出變量，得到如下單純形表：c T0000

14、11cXbxxxxxxBB1234560 x37/35/12011/12-1/1200 x220/31/310-1/31/301x610/32/3001/3-1/31zj2/3001/3-1/31c - z.-2/300-1/34/30表中檢驗數(shù)表明還未達到最優(yōu)解，把七作為換入變量x6作為換出變量，得到如下單純形表：C . T000011CXbxxxxxxBB1234560 x31/4001-1/81/8-5/80 x25010-1/21/2-1/20 x151001/2-1/23/2zj0000o0c - z.000011由上表可知，非基變量檢驗數(shù)全部N0,已達到最優(yōu)解，且基變量中不含有人工

15、變量，所以 轉(zhuǎn)入第二階段：恢復(fù)原來的目標函數(shù)，繼續(xù)用單純形法求解。改變后如下表：c T2300cBXBbX1X2X3X40X31/4001-1/83X25010-1/22X151001/2z000-1/20001/2由檢驗數(shù)可知，上表已達到最優(yōu)解，求出的最優(yōu)解為1(X,X ,X ,X ,X ,X ) = (5,5,丁，0,0,0)目標函數(shù)值為z = 2X5 + 3X5 = 251 2 3 4 5 6J，目 4刀函 I 且/y z 八丁八。2. (25分)考慮如下線性規(guī)劃問題max z = 一5 x + 5 x +13 xx + x + 3x V 20s.t 12x + 4x +10 x 0(j

16、 = 1,2,3)i j分別對兩個約束條件引入松弛變量X4,X5，用單純形法得到如下最優(yōu)單純形表。不用重新求解，分別分析如下問題。b 10 （1）約束條件的右邊常數(shù)變?yōu)閎=202模型的解會有什么變化?（2）使最優(yōu)解不變的c 2的變化范圍;(3)X對應(yīng)的系數(shù)變?yōu)閏1aiia21-2模型的解會有什么變化?（4）增加一個新的約束條件2x + x + 5x 50，模型的解會有什么變化?解析：這是一道綜合計算題，既考查了對偶單純形法的應(yīng)用又考查了靈敏度分析的計算，這是每年必考的計算題之一，雖然變化的類型不算多，但靈活性比較高，需要自己總結(jié)歸納，熟練掌握。解：（1）B-1 =-10b = B-1b =-1

17、0一10 -=-10 一，代入單純形表得:-41-4120-20c j-551300CBXBbX1X2X3X4X55X210-113100X5-20160-2-41bj00-2-50X為換出變量，故X5-2-43為換入變量，得新的單純形表cj-551300CBXBbX1X2X3X4X55X2-202310-53/213X310-8012-1/2bj-1600-1-1X2為換出變量，4為換入變量，得新的單純形法如下:3 , X , X , X , X ) = (0,0,2,4,0)，目標函數(shù)最優(yōu)值為 z = 2612345(2) X2為基變量，故max (-2/3),(-5/1) Ac minb/(-1)即-2/3 Ac2 0那么c2值得允許變化范圍就是113/3,5。-10-10o0(3) B-1 =-41P： = B-1P1 =-415=55 =c -c p =-2-E 0- 0 =-2 0所以最優(yōu)解不會發(fā)生變化。11 B 15(4)增加一個新的約束條件2x +