西南交通大學(xué)運(yùn)籌學(xué)IA考試題

1、線訂裝封密 線訂裝封密 線訂裝封密 名姓 號(hào)學(xué) 級(jí)班題號(hào)一二三四五六七八九十總成績(jī)得分閱卷教師簽字：西南交通大學(xué)2013 2014學(xué)年第（二）學(xué)期考試試卷課程代碼0220510課程名稱 運(yùn)籌學(xué)（運(yùn)輸）I考試時(shí)間120分鐘一填空題（共20分，每題2分）1.線性規(guī)劃模型中，沒有取值約束的決策變量也稱為自由變量 。2,把滿足線性規(guī)劃模型約束條件方程組的解稱為可行解 。3.線性規(guī)劃模型無解指的是無可行解 和無界解兩種可能。4,對(duì)線性規(guī)劃模型求解，確定基本可行解的方法是構(gòu)造單位矩陣 。.對(duì)偶問題最優(yōu)目標(biāo)函數(shù)值和原問題最優(yōu)目標(biāo)函數(shù)值是相等 的。, 值靈敏度分析就是在不改變?cè)瓉碜顑?yōu)解基變量但基變量取值可以變

2、動(dòng)的前提下，求出0值的允許變動(dòng)范圍。.運(yùn)輸問題的表上作業(yè)法中，任意一個(gè)非基變量都能和若干個(gè) 基變量構(gòu)成唯一的閉回路。.標(biāo)準(zhǔn)指派問題模型的目標(biāo)函數(shù)是min 形式。9,匈牙利法需要把指派問題的系數(shù)矩陣轉(zhuǎn)換為等效 矩陣。10.0-1規(guī)劃求解方法只檢查部分組合，此方法稱為隱枚舉 法。二選擇題（共15分，每題3分）1,用對(duì)偶單純形法求解時(shí)，要求線性規(guī)劃模型中的 B0A約束方程右端值biB未知數(shù)XjC目標(biāo)函數(shù)系數(shù)CjD約束方程系數(shù)aj2.線性規(guī)劃模型靈敏度分析中，不改變?cè)瓉碜顑?yōu)解基變量及其取值的情況，從而求出值的允許變動(dòng)范圍，指的是 A B靈敏度分析。 TOC o 1-5 h z A CjBajCbiDX

3、j3,線性規(guī)劃模型有解指的是模型有B 和 D 兩種可能。A不可行解 B 唯一解 C 無界限解 D 多重解4,線性規(guī)劃模型約束條件方程組中含有A型的求解方法有ACDA兩階段法 B 分枝定界法 C大M法 D 對(duì)偶單純形法5,整數(shù)規(guī)劃模型求解的分枝定界法會(huì)用到與或_C。A單純形法 B 匈牙利法 C 對(duì)偶單純形法D表上作業(yè)法三 判斷對(duì)錯(cuò)（在括號(hào)內(nèi)打X或，在橫線上說明錯(cuò)誤原因，每題 3分， 共18分，不說明錯(cuò)誤原因不得分。）.線性規(guī)劃模型如果有最優(yōu)解，則只能在可行域D極點(diǎn)上達(dá)到。（X ） 如果存在多重解，其它點(diǎn)也能使目標(biāo)函數(shù)達(dá)到最優(yōu)。.把線性規(guī)劃模型加入松弛變量或多余變量,目的是為了確定基本可行解 而構(gòu)

4、造單位矩陣。（X ）目的是把約束條件方程的不等式變換為等式。 TOC o 1-5 h z .原問題最優(yōu)解也可以從對(duì)偶問題的最優(yōu)單純形表中讀出來。Fv）.用單純形法求解時(shí)，檢驗(yàn)數(shù)為零的變量一定是基變量。）如果模型存在多重最優(yōu)解時(shí)，也存在非基變量的檢驗(yàn)數(shù)為零。.運(yùn)輸問題的解可能會(huì)有唯一解、多重解、無界解、不可行解。fx）運(yùn)輸問題必定有最優(yōu)解，有可能是唯一最優(yōu)解，也有可能出現(xiàn)多重解。.對(duì)整數(shù)規(guī)劃模型的非整數(shù)解用湊整方法處理后得到的解一定也是模型 的最優(yōu)解（x ）湊整得到的解有時(shí)不是可行解，有時(shí)既使是可行解但不一定是最優(yōu)解。四簡(jiǎn)答題（共12分） TOC o 1-5 h z .線性規(guī)劃模型中所謂的“線性

5、”主要指的是？（4分）答：（1）目標(biāo)函數(shù)是線性的函數(shù)形式，有可能是求最大值，如追求利潤(rùn)最大，也有可能是求最小值，如追求成本最低。 （2分）（2）約束條件方程組由線性的等式或線性的不等式組成，有&、=、三種形式。（2分）.線性規(guī)劃模型的Cj靈敏度分析中，如果q在允許的范圍內(nèi)變動(dòng)時(shí)，目 標(biāo)函數(shù)值是否也會(huì)發(fā)生改變？為什么？（ 8分）答：（1）當(dāng)c對(duì)應(yīng)的變量為為非基變量時(shí)，最優(yōu)解不會(huì)改變，目標(biāo)函數(shù)值也不會(huì)改變，因?yàn)楸M管Cj發(fā)生了變動(dòng)，但作為非基變量 Xj的取值為0,所以目標(biāo)函數(shù)中CjXj 項(xiàng)的取值仍然為0。（4分）（2）當(dāng)Cj對(duì)應(yīng)的變量Xj為基變量時(shí)，最優(yōu)解不會(huì)改變，但目標(biāo)函數(shù)值可能會(huì)發(fā)生 改變，因?yàn)?/p>

6、盡管基變量Xj沒有改變，但Cj發(fā)生了變動(dòng)，那么目標(biāo)函數(shù)的CjXj項(xiàng) 取值就發(fā)生了變動(dòng),從而可能造成目標(biāo)函數(shù)值變動(dòng)。 （4分）五計(jì)算題（共30分）1. （10分）有如下線性規(guī)劃模型：max z = Xi X22xi + X2 4s.t.L 冷氣 - 3xi + X2 0請(qǐng)用單純形法求解并判斷此模型解的情況。解：將模型化為標(biāo)準(zhǔn)型：maX z = Xi X2 0 X3 0 x4 0 X5 一 2xi + X2 + X3=4s.t. J-X2+X4- 3xi + X2+ X5 = 3Xj 之 0, i =i,2,3,4,5初始單純形表如下：Cjii000CbXbbXiX2X3X4X50X34-2ii0

7、00X42i-i0i00X53-3i00izj00000Cj-Zjii000迭代求解，得到如下單純形表:Cjii000CbxbbXiX2X3X4X50X380-ii20iXi2i-i0i00X590-203iZji-i0i0Cj-Zj020-i0上表中非基變量X2的檢驗(yàn)數(shù)為正數(shù)，應(yīng)該作為換入變量，但所對(duì)應(yīng)的列向量全部小 于0,另外也沒有其它非基變量可作為換入變量，所以此線性規(guī)劃模型為無界解。 判卷標(biāo)準(zhǔn)：求解過程8分，出現(xiàn)錯(cuò)誤適當(dāng)扣分，模型解判定 2分。（i0分）某公司需要把三個(gè)存儲(chǔ)地 Ai、A2、A3的貨物運(yùn)往三個(gè)銷售地 Bi、B、B3,已知三個(gè)存儲(chǔ)地 Ai、A2、A3分別有貨物7噸、4噸、9

8、噸, 三個(gè)銷售地Bi、B、B3分別需要貨物3噸、6噸、5噸。另外，如果剩 余貨物，三個(gè)存儲(chǔ)地A” A2、A3將分別收取單位存儲(chǔ)費(fèi)i0、8、5。 從各工廠到銷售地的單位產(chǎn)品運(yùn)費(fèi)如下表所示。產(chǎn)地、銷地BiB 2B 3Ai3ii3A 2i92A 374i0求解分析：三個(gè)存儲(chǔ)地的貨物總量為 20,三個(gè)銷售地總銷售量為i4,產(chǎn)銷不平衡，虛擬一個(gè)銷售點(diǎn) B4,令其銷量b4=20-14=6。求解的某一 過程如下表所示：產(chǎn)地、銷地2B19B23B310B40A13X11X3107-1 A219X28X4-5 A37X410X59銷量36562 =20請(qǐng)解決以下問題：(1)求出所花費(fèi)用最低的運(yùn)輸方案。(7分)解

9、：計(jì)算出所有非基變量的檢驗(yàn)數(shù)，并將求出的檢驗(yàn)數(shù)填到綜合表中對(duì)應(yīng)的非基變量Xij的位置,如下表所示：(判卷標(biāo)準(zhǔn)：此過程 2分)產(chǎn)地銷地2Bi9B23B310B40Al311123107-1 a219128-14-5 A37104101259銷量36562=20上表中，有X24的檢驗(yàn)數(shù)為負(fù)值，說明當(dāng)前的基本解還不是最優(yōu)解，把X24作為換入變量，繼續(xù)求解如下表所示：(判卷標(biāo)準(zhǔn)：此過程 3分)產(chǎn)地口一銷地3Bi9B23B310B40Al3X11X3107-2 A219X2X84-5 A37X410X59銷量36562=20對(duì)上表用閉回路法或位勢(shì)法繼續(xù)求檢驗(yàn)數(shù)，得到下表：(判卷標(biāo)準(zhǔn)：此過程 1分)產(chǎn)地、

10、銷地3Bi9B23B310B40Al301123107-2 A21922184-5 A3794101259銷量36562=20上表沒有負(fù)檢驗(yàn)數(shù)，說明已經(jīng)找到最優(yōu)解。最優(yōu)運(yùn)輸方案為：(1分)(X13, X14, X21, X24, X32, X34)=(5,2,3,1,6,3)(2)在求出的最優(yōu)運(yùn)輸方案下，支出的總費(fèi)用為多少？運(yùn)輸費(fèi)用為多少？存儲(chǔ)費(fèi)用為多少？(3分)解：在最優(yōu)運(yùn)輸方案(X13, X14, X21, X24, X32,X34)=(5,2,3,1,6,3)下，支出的總費(fèi)用為:z=3X5+10 X2+1 X3+8X1+46+5X3=85。運(yùn)輸費(fèi)用為：3X5+1 X3+4 X6=42o 存儲(chǔ)費(fèi)用為:10 X2+8 X1+5 3=43。（判卷標(biāo)準(zhǔn)：此過程每問1分）（10分）某企業(yè)計(jì)劃生產(chǎn)I、II兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需要 的設(shè)備臺(tái)時(shí)以及原材料 A和B的消耗分別如下表所示：資源消耗 產(chǎn)品、設(shè)備（臺(tái)時(shí)）原材料A（kg）原材料B（kg）I1:410n204資源數(shù)量81612該工廠每生產(chǎn)一件產(chǎn)品I獲利2萬元，每生產(chǎn)一件產(chǎn)品II獲