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

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

3、A B 靈敏度分析。A cij B aij C bi D xj3.線性規(guī)劃模型有解指的是模型有 B 和 D 兩種可能。A 不可行解 B唯一解 C 無界限解 D 多重解 4.線性規(guī)劃模型約束條件方程組中含有型的求解方法有 ACD 。A 兩階段法 B 分枝定界法 C 大M法 D 對偶單純形法 5.整數(shù)規(guī)劃模型求解的分枝定界法會用到 A 或 C 。A 單純形法 B 匈牙利法 C 對偶單純形法 D 表上作業(yè)法三 判斷對錯（在括號內(nèi)打或，在橫線上說明錯誤原因，每題3分，共18分，不說明錯誤原因不得分。）1.線性規(guī)劃模型如果有最優(yōu)解，則只能在可行域D極點上達(dá)到。（ ） 如果存在多重解，其它點也能使目標(biāo)函數(shù)

4、達(dá)到最優(yōu)。 2.把線性規(guī)劃模型加入松弛變量或多余變量，目的是為了確定基本可行解而構(gòu)造單位矩陣。（ ） 目的是把約束條件方程的不等式變換為等式。 3.原問題最優(yōu)解也可以從對偶問題的最優(yōu)單純形表中讀出來。（ ） 4.用單純形法求解時，檢驗數(shù)為零的變量一定是基變量。（ ） 如果模型存在多重最優(yōu)解時，也存在非基變量的檢驗數(shù)為零。 5.運輸問題的解可能會有唯一解、多重解、無界解、不可行解。（ ） 運輸問題必定有最優(yōu)解，有可能是唯一最優(yōu)解，也有可能出現(xiàn)多重解。 6.對整數(shù)規(guī)劃模型的非整數(shù)解用湊整方法處理后得到的解一定也是模型的最優(yōu)解（ ） 湊整得到的解有時不是可行解，有時既使是可行解但不一定是最優(yōu)解。 四

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

6、最優(yōu)解不會改變，但目標(biāo)函數(shù)值可能會發(fā)生改變，因為盡管基變量xj沒有改變，但cj發(fā)生了變動，那么目標(biāo)函數(shù)的cjxj項取值就發(fā)生了變動，從而可能造成目標(biāo)函數(shù)值變動。（4分）五 計算題（共30分）1.（10分）有如下線性規(guī)劃模型：請用單純形法求解并判斷此模型解的情況。 解：將模型化為標(biāo)準(zhǔn)型：初始單純形表如下：cj11000cBxBbx1x2x3x4x5000x3x4x5423-21-31-11100010001zj00000cj-zj11000迭代求解，得到如下單純形表：cj11000cBxBbx1x2x3x4x5010x3x1x5829010-1-1-2100213001zj1-1010cj-zj

7、020-10上表中非基變量x2的檢驗數(shù)為正數(shù)，應(yīng)該作為換入變量，但所對應(yīng)的列向量全部小于0，另外也沒有其它非基變量可作為換入變量，所以此線性規(guī)劃模型為無界解。判卷標(biāo)準(zhǔn)：求解過程8分，出現(xiàn)錯誤適當(dāng)扣分，模型解判定2分。 2.（10分）某公司需要把三個存儲地A1、A2、A3的貨物運往三個銷售地B1、B、B3，已知三個存儲地A1、A2、A3分別有貨物7噸、4噸、9噸，三個銷售地B1、B、B3分別需要貨物3噸、6噸、5噸。另外，如果剩余貨物，三個存儲地A1、A2、A3將分別收取單位存儲費10、8、5。從各工廠到銷售地的單位產(chǎn)品運費如下表所示。 銷地產(chǎn)地B1B 2B 3A13113A 2192A 374

8、10求解分析：三個存儲地的貨物總量為20，三個銷售地總銷售量為14，產(chǎn)銷不平衡，虛擬一個銷售點B4，令其銷量b4=20-14=6。求解的某一過程如下表所示： 銷地產(chǎn)地2B19B23B310B4產(chǎn)量0A1 3 11 3 107-1A2 1 9 2 84-5A3 7 4 10 59銷量3656=20請解決以下問題：（1）求出所花費用最低的運輸方案。（7分）解：計算出所有非基變量的檢驗數(shù)，并將求出的檢驗數(shù)填到綜合表中對應(yīng)的非基變量xij的位置，如下表所示： （判卷標(biāo)準(zhǔn)：此過程2分） 銷地產(chǎn)地2B19B23B310B4產(chǎn)量0A1 13 211 3 107-1A2 1 19 2 -184-5A3 107

9、 4 1210 59銷量3656=20上表中，有x24的檢驗數(shù)為負(fù)值，說明當(dāng)前的基本解還不是最優(yōu)解，把x24作為換入變量，繼續(xù)求解如下表所示：（判卷標(biāo)準(zhǔn)：此過程3分） 銷地產(chǎn)地3B19B23B310B4產(chǎn)量0A1 3 11 3 107-2A2 1 9 2 84-5A3 7 4 10 59銷量3656=20對上表用閉回路法或位勢法繼續(xù)求檢驗數(shù)，得到下表： （判卷標(biāo)準(zhǔn)：此過程1分） 銷地產(chǎn)地3B19B23B310B4產(chǎn)量0A1 03 211 3 107-2A2 1 29 12 84-5A3 97 4 1210 59銷量3656=20上表沒有負(fù)檢驗數(shù)，說明已經(jīng)找到最優(yōu)解。最優(yōu)運輸方案為：（1分）(x

10、13,x14,x21,x24,x32,x34)=(5,2,3,1,6,3)（2）在求出的最優(yōu)運輸方案下，支出的總費用為多少？運輸費用為多少？存儲費用為多少？ （3分） 解：在最優(yōu)運輸方案(x13,x14,x21,x24,x32,x34)=(5,2,3,1,6,3)下，支出的總費用為：z=35+102+13+81+46+53=85。運輸費用為：35+13+46=42。存儲費用為：102+81+53=43。（判卷標(biāo)準(zhǔn)：此過程每問1分）3.（10分）某企業(yè)計劃生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需要的設(shè)備臺時以及原材料A和B的消耗分別如下表所示： 資源消耗產(chǎn)品設(shè)備(臺時) 原材料A(kg)原材料B(k

11、g)124004資源數(shù)量81612該工廠每生產(chǎn)一件產(chǎn)品獲利2萬元，每生產(chǎn)一件產(chǎn)品獲利3萬元。設(shè)x1、x2分別表示、兩種產(chǎn)品的產(chǎn)量（在此假設(shè)產(chǎn)品小數(shù)），建立的線性規(guī)劃模型如下：求解的最優(yōu)單純形表如下表所示：cj23000cBxBbx1x2x3x4x5203x1x5x24421000010-21/21/41/2-1/8010zj233/21/80cj-zj00-3/2-1/80由最優(yōu)單純形表可知，、兩種產(chǎn)品的產(chǎn)量分別是4和2，那么獲得的最大總利潤就為z=24+32=14（萬元）。請解決以下問題：（1）如果將原材料A、B出讓、設(shè)備出租，如何定價才能使所得收入不低于生產(chǎn)、兩種產(chǎn)品所得的最佳利潤？（2分

12、）（2）如果某商家給出設(shè)備租金0元、原材料A單位售價0元、原材料B單位售價2萬元的方案，是否可以接受？為什么？（2分）（3）若把可用的設(shè)備臺時由8增加到10，是否改變生產(chǎn)方案？如果改變，求出新的生產(chǎn)方案以及利潤變化情況（6分）解：（1）通過最優(yōu)單純形表可讀出對偶問題最優(yōu)解，即設(shè)備租金為3/2，原材料A售價為1/8，而原材料B的售價為0。（判卷標(biāo)準(zhǔn)：此過程錯一問扣1分）（2）可以接受，因為總利潤為2*12=24萬元，高于基本利潤14萬元。（判卷標(biāo)準(zhǔn)：此過程錯一問扣1分）（3）多增加設(shè)備臺時，意味著對b1的靈敏度分析，根據(jù)公式有：Max-2/(1/2)b1Min -4/(-2) ,-4b12，即b

13、1的靈敏度范圍為4，10。（判卷標(biāo)準(zhǔn)：此過程2分）多增加2個設(shè)備臺時，即b1=2，在靈敏度范圍內(nèi)，新的解為：XN=XO+b1*P3=4 4 2+2*0 -2 1/2=4 0 3即新生產(chǎn)方案為產(chǎn)品生產(chǎn)量為4，產(chǎn)品生產(chǎn)量為3。（判卷標(biāo)準(zhǔn)：此過程錯3分）新的最大總利潤為：2*4+3*3=17，總利潤會增加，增加了17-14=3萬元。或利用邊際值可知q1=|z2+1|=3/2。總利潤會增加3/2*(10-8)=3萬元。（判卷標(biāo)準(zhǔn)：此過程1分）六 建模題（5分）一架貨運飛機有效載重為24t，可運輸貨物重量及運費收入見下表所示：貨物123456重量(t)8136957收入(元)352423在飛機載重量的限制下，選擇一組收入最多的貨物運輸；另外，在貨物4、6當(dāng)中