西南交通大學(xué)管理運籌學(xué)929-2018年試題和解析

1、西南交通大學(xué)管理運籌學(xué) 9292018 年試題和解析( 總 10 頁)-本頁僅作為文檔封面，使用時請直接刪除即可-內(nèi)頁可以根據(jù)需求調(diào)整合適字體及大小-2222機(jī)密啟用前西南交通大學(xué) 2018 年碩士研究生招生入學(xué)考試試卷試題代碼：929試題名稱：管理運籌學(xué)一考試時間：201712考生注意：3150效；請在答題紙上按要求填寫試題代碼和試題名稱；試卷不得拆開，否則遺失后果自負(fù)。一、 問答題（60分，共10小題，每小題6分）（答在試卷上的內(nèi)容無效1、線性規(guī)劃模型中，何謂自由變量自由變量和決策變量是什么關(guān)系解答：用設(shè)定的未知數(shù)來表示線性規(guī)劃問題問題中的未知量，這個設(shè)定的未知量就叫做決策變量，決策變量沒

2、有非負(fù)約束即為自由變量；自由變量一定是決策變量，但決策變量不一定是自由變量。2、請分別解釋無可行解、無界解、最優(yōu)解的概念。解答：無可行解：約束方程組沒有公共解，造成線性規(guī)劃模型無解的解。無界解：沒有任何一個可行解能使得目標(biāo)函數(shù)達(dá)到最優(yōu)，即目標(biāo)函數(shù)沒有上界或下界。最優(yōu)解：在線性規(guī)劃模型的所有可行解中，使得目標(biāo)函數(shù)達(dá)到最優(yōu)的解3、說明下面的數(shù)學(xué)模型不符合線性規(guī)劃模型的什么特點z 6x 4x x 3xx 23303s.t. x 1 x1833(2x )2 2x3 49x ,10312解答：此模型不符合線性規(guī)劃模型目標(biāo)函數(shù)應(yīng)該是線性函數(shù)的特點；此模型不符合線性規(guī)劃模型目標(biāo)函數(shù)求最大值最小值的特點；式的

3、特點。4、以目標(biāo)函數(shù)Min 型為例，從基本可行解、求檢驗數(shù)以及基本可行解改進(jìn)3333三個方面說明單純形法和表上作業(yè)法的區(qū)別。解答：本可行解。檢驗數(shù)：單純形法是算出機(jī)會費用 zj以后，直接計算檢驗數(shù)的代數(shù)式c zjj，而表上作業(yè)法是通過另外的閉回路法或者位勢法來計算檢驗數(shù)。c zjj 0 的情況下進(jìn)一步改進(jìn)基本可行解，即若基本可行解不是最小值，那么需要迭代調(diào) 通過行運算進(jìn)行迭代。5、用表上作業(yè)法求運輸問題的檢驗數(shù)的方法有閉回路法和位勢法，位勢法的思路是針對基變量 xiju 和viju vij c 。請利用閉回路ij法的思路及以下圖形的回路， 證明位勢法求非基變量檢驗數(shù)的公式ciju v 。ijx

4、ijxxijxijxi jxi j證明：基變量基變量因為 xij, xi j, xi j是基變量，由已知條件有以下方程：u vij c ,u vijic,u vi ji ci j根據(jù)閉回路法，非基變量的檢驗數(shù)為ij (cijci j) (cijci j) cijcijci jci j故證得ij c uij即ijv 。j c u vuijijv u vji c u vijij6、針對整數(shù)規(guī)劃的分枝定界法：先使用什么方法求出不考慮整數(shù)約束的最優(yōu)解（3）xk取值為整數(shù)，但用分支定界算法求出 bk 的值不是整數(shù)，那么需要使用什么方法求出分支以后的解（3） 3 分）4444解答：法求得最優(yōu)解。分枝法：在

5、最優(yōu)解中選擇一個不符合整數(shù)約束條件的xj其值為 b ，以jjjjjb x x 別加入原 LP 與jjjj7、利用Ford-Fulkerson算法對網(wǎng)絡(luò)的流量進(jìn)行調(diào)整時，必須遵守容量約束條件和流量守恒條件。請利用以下圖形示例解釋：在增加網(wǎng)絡(luò)的流量時，為何增流鏈前向邊的流量要加上調(diào)整量 （xv v v y ）3 4 5v3v37，38，3v54，26，3v46，5v 點接受流量4之和為8v 點發(fā)出流量4之和4解析：針對中間點v4，接收流量之和與發(fā)出流量之和均為 8，滿足流量守恒，針xv v y ，邊(v v 是接收流量的邊，而邊(v v 是中間點發(fā)出流3 4 5344454量的邊。若給增流鏈 xv

6、 v v3 4 5y 加上調(diào)整量 ，就會導(dǎo)致中間點v4接收量之和為8+ ，為了滿足流量守恒的條件，中間點v48+ ，所以需要把增流鏈前向邊的流量要加上調(diào)整量 。8、假設(shè)某統(tǒng)籌圖的關(guān)鍵路線有 2 條，如果某一個非關(guān)鍵工序的工序時間長，關(guān)鍵路線的狀態(tài)有什么變化？9、解析：若該非關(guān)鍵工序的工序時間延長后不超過關(guān)鍵工序的工序時間，那么統(tǒng)籌圖的關(guān)鍵路線不變；若該非關(guān)鍵工序的工序時間延長后超過關(guān)鍵工序的工序時間，那么統(tǒng)籌圖的關(guān)鍵路線變?yōu)樵撀肪€。11、對線性規(guī)劃模型目標(biāo)函數(shù)的cj進(jìn)行靈敏度分析時，如果 cj在允許范圍內(nèi)變動，那么模型的目標(biāo)函數(shù)值是否會改變?yōu)槭裁唇馕觯寒?dāng)c xj為非基變量時，若cj在允許范圍內(nèi)

7、變動，最優(yōu)解不會改變。另外，目標(biāo)函數(shù)值也不會改變。盡管c發(fā)生了變動，但作為非基變量 x 的jj0，所以目標(biāo)函數(shù)中c xjj項的取值仍然為 0。5555當(dāng)c xj為基變量時，如果cj在允許范圍內(nèi)變動，最優(yōu)解不會改沒有改變，但cj發(fā)生了變動，所以目標(biāo)函數(shù)c xjj項的取值也發(fā)生了變動，從而造成目標(biāo)函數(shù)值變動。10、在排隊系統(tǒng)中，如果顧客到達(dá)時間的間隔是均衡固定的，是否會產(chǎn)生排隊現(xiàn)象？為什么解析：會產(chǎn)生排隊現(xiàn)象。理由是：排隊現(xiàn)象的產(chǎn)生是由于顧客到達(dá)的時間存在隨機(jī)性或者服務(wù)員的服務(wù)時間存在隨機(jī)性，因此在顧客到達(dá)的時間間隔均衡固定的情況下，服務(wù)時間不均衡固定是會產(chǎn)生排隊現(xiàn)象的。二、 計算題（75 分，共

8、 3 小題）（答在試卷上的內(nèi)容無效）(25B乙兩種產(chǎn)品獲利最多的生產(chǎn)方案，此方案求解過程如下表所示。已知 x、xx x x5454212均為松弛變量。cj23000cBxBbx1x2x3x4x52x21010-1/20 x800-4123x301001/4zj2320-1/4c zjj00-201/4請解決以下問題：求解該企業(yè)獲利最多的生產(chǎn)方案以及獲得的最大利潤。（10）如果該企業(yè)打算制定將設(shè)備出租、A和 B此方案的線性規(guī)劃模型是什么（10）上面第（2）個問題中的線性規(guī)劃模型的最優(yōu)解是什么（4） 5 分）解答：題中單純性表中仍然有正檢驗數(shù)c z55 1/ 4 ，所以沒有達(dá)到最優(yōu)解，并且存在有a

9、cBcB203cjxBx5x4x2zjc zjb4422x11003x20010 x30-21/20 x41/41/2-1/80 x50102j0303/2-3/21/8-1/8000，需要迭代循環(huán)求解，迭代后的單純形表如下：6666上表中所有的檢驗數(shù)都是小于等于 0 的，所以已經(jīng)達(dá)到了最優(yōu)，其中最優(yōu)解為(x x x x x (4, 2,0,0, 4) 4212345z 14元。此問題即是寫出對偶問題的線性規(guī)劃模型，但必須先寫出原問題的的線性x x x 均為345松弛變量，所以在初始單純形表中，它們對應(yīng)的矩陣是單位矩陣，這需要在對x x x345對應(yīng)的矩陣變?yōu)閱挝痪仃?，結(jié)果如cBcB000cj

10、xBx3x4x523000bx1x2x3x4x581210016400101204001基于上表，可以寫出此方案的線性規(guī)劃模型如下：max z 2x13x2 x 2x 84x12 1614x 12x 0, 1,2j如果把生產(chǎn)方案看作原問題，那么將設(shè)備出租、AB兩種原材料出售獲利的方案可以看作是對偶問題。基于生產(chǎn)方案原問題的模型，即可寫出對偶問題的線性規(guī)劃模型：min q 8y116y212y3 y 4y 22 4y2 3 yj1 0, j3 1,2,3（5） 上面第（2）問的中線性規(guī)劃模型的最優(yōu)解即是對偶問題的最優(yōu)解，從第（1）個問題中的最優(yōu)單純形表即可讀出對偶問題決策變量的最優(yōu)解：y z1m

11、1 z 3/ 2,y3 z zm241/ 8, y3 z zm35 0,其中m 2 。y y12, y ) (3 / 2,1/ 8,0)3（25）57請設(shè)計半年以后的運輸方案。77775,1,25,1,2v33,1,3v46,1,23,0,52,0,4v1v64,4,3v24,4,35,4,3v5解答：首先找到增流鏈v v v134 v 取調(diào)整量 2 76網(wǎng)絡(luò)圖如下：5,3,25,3,2v33,3,3v46,3,23,0,52,0,4v1v64,4,3v24,4,35,4,3v5然后構(gòu)建此時運輸量為7的網(wǎng)絡(luò)圖的增流網(wǎng)絡(luò)G，如下圖所示：f3,-23,-2v33,-3v43,23,-22,23,5

12、2,4v1v61,34,-3v24,-3v54,-3此時不存在負(fù)回路，說明當(dāng)前已是運輸量為 7 的最小費用流，總費用為：W ( f) 32 33 32 43 43 43 57A(25工序代號a 工序代號a b cdba,c工序時間（天）10534工序代號e f gh緊前工序a,d ef , g工序時間（天）5655問題如下：繪制上述建設(shè)工程的統(tǒng)籌圖。（5）利用事項的最早時間和最遲時間，確定出關(guān)鍵路線和工期（10）8888c工序節(jié)省出一臺挖掘機(jī)，而一臺挖掘機(jī)投入到其他工序，可使其它工序的工序時間減少 2到哪個工序可使工程的工期提前為什么（10）解答：d4d4f245e665 gh57a51013

13、cb53利用事項的最早時間和最遲時間，確定出關(guān)鍵路線為：014014141010d4f20202525245e66h575 g501a103c1515b5357即有兩條關(guān)鍵工序工期均為 25 天： 需要把挖掘機(jī)放到工序a或h2524有關(guān)鍵工序，2b4序a或h中的一個。現(xiàn)在對將挖掘機(jī)分別放到a 或h 進(jìn)行討論如下： 當(dāng)放于a 時，關(guān)鍵路線為99990 1201212882d4f1818232345e66h575 g501a83c1313b53554 、 當(dāng)放于h 時，關(guān)鍵路線為0140141410102d4f2920232345e66h375 g501a103c1515b5375 綜上所述：需要

14、把挖掘機(jī)放到工序a 或h 2523三、 建模題（15 分，共 1 小題）（答在試卷上的內(nèi)容無效）有一個運輸網(wǎng)絡(luò)如下圖所示，圖中各個邊給出了容量和費用。其中 x 有165x2有和兩種產(chǎn)品，數(shù)量分別為 412x 87y、y、為三個3123y167y2需要和兩49y3需要和兩種產(chǎn)品，需求量分別為 8噸和 13 噸；x2處的產(chǎn)品只能運送到需求地 y2x 處的3y 。3請將此網(wǎng)絡(luò)圖轉(zhuǎn)換為可用于求解的單源單匯、單一品種的網(wǎng)絡(luò)圖模型。10101010(+6)(+5)(-6)x1(7,5)x1(7,5)y1(8,5)(6,5)(4,5)v1x2(4,5)（3,5）(5,5)y2(9,5)v2(6,5)(3,5

15、)(6,5)v3(4,5)(8,5)(7,5)x3(8,5)y3(+4)(+12)(-4)(-9)(+8)(+7)(-8)(-13)解析：42471491122x* 生產(chǎn)產(chǎn)品2x* 生產(chǎn)產(chǎn)品3x x 拆成分別生產(chǎn)產(chǎn)品,的產(chǎn)地123x1x1x2x2 x3x3 ；yy y拆成分別銷售產(chǎn)品,的銷地123y1 y1 y2 y2 y3 y3 ，將轉(zhuǎn)運地v v拆成分別轉(zhuǎn)運產(chǎn)品，的12v1,v1 ,v1 ,v2,v2 ,v2 ,v3,v3 ,v3；最后得到如下單源單匯的網(wǎng)絡(luò)圖：(+6)(+6)(6,0,5)(6,0,5)(+5)v1(6,0,5)(6,0,0)(5,0,5)(8,0,0)(+4)xv1(5,0,5)y1(8,0,0)2(4,0,5)(14,0,0)(4,0,5)y1(5,0,0)(16,