管理運籌學(xué)模擬試題與答案

1、.四川大學(xué)網(wǎng)絡(luò)教育學(xué)院模擬試題(A)管理運籌學(xué) 一、單選題（每題分，共 20 分。）1 目標函數(shù)取極小 （ minZ ）的線性規(guī)劃問題可以轉(zhuǎn)化為目標函數(shù)取極大的線性規(guī)劃問題求解 ，原問題的目標函數(shù)值等于 （）。A. maxZB. max(-Z)C. max(-Z)D.-maxZ2.下列說法中正確的是（）。 基本解一定是可行解 基本可行解的每個分量一定非負 若 B 是基，則 B 一定是可逆 非基變量的系數(shù)列向量一定是線性相關(guān)的3 在線性規(guī)劃模型中，沒有非負約束的變量稱為（）多余變量B松弛變量C 人工變量D 自由變量4. 當滿足最優(yōu)解 ，且檢驗數(shù)為零的變量的個數(shù)大于基變量的個數(shù)時，可求得（）。 多

2、重解 無解正則解 退化解5 對偶單純型法與標準單純型法的主要區(qū)別是每次迭代的基變量都滿足最優(yōu)檢驗但不完全滿足（）。A 等式約束B“”型約束C“”約束D 非負約束6. 原問題的第 個約束方程是“型”，則對偶問題的變量yi 是（）。 多余變量 自由變量松弛變量 非負變量7.在運輸方案中出現(xiàn)退化現(xiàn)象，是指數(shù)字格的數(shù)目()。A.等于 m+nB.大于 m+n-1C.小于 m+n-1D.等于 m+n-18.樹的任意兩個頂點間恰好有一條（）。 邊 初等鏈 歐拉圈 回路9 若 G 中不存在流f 增流鏈 ，則 f 為 G 的 （）。A 最小流B 最大流C 最小費用流D 無法確定10.對偶單純型法與標準單純型法的

3、主要區(qū)別是每次迭代的基變量都滿足最優(yōu)檢驗但不完全滿足 （） 等式約束“”型約束“”型約束 非負約束二、多項選擇題 （每小題 4 分，共 20 分）1 化一般規(guī)劃模型為標準型時，可能引入的變量有（）A 松弛變量B 剩余變量C 非負變量D 非正變量E 自專業(yè) .專注.由變量2 圖解法求解線性規(guī)劃問題的主要過程有（）A 畫出可行域B求出頂點坐標C 求最優(yōu)目標值D 選基本解E選最優(yōu)解3 表上作業(yè)法中確定換出變量的過程有（）A 判斷檢驗數(shù)是否都非負B 選最大檢驗數(shù)C 確定換出變量D 選最小檢驗數(shù)E確定換入變量4 求解約束條件為“”型的線性規(guī)劃 、構(gòu)造基本矩陣時，可用的變量有（）A 人工變量B 松弛變量C

4、. 負變量D 剩余變量E 穩(wěn)態(tài)變量5 線性規(guī)劃問題的主要特征有（）A 目標是線性的B 約束是線性的C求目標最大值D 求目標最小值E非線性三、計算題（共 60 分）1. 下列線性規(guī)劃問題化為標準型 。 (10 分 )min Zx1 +5x2 -2x3x1x 2x 36滿足2x1x 23x 35x1x210x10, x20, x3符號不限2.寫出下列問題的對偶問題(10 分)min Z4 x12x2 +3x34x1 +5x 26x 3=7滿足8x19x 210x 31112x113x214x10, x2 無約束， x3 03. 用最小元素法求下列運輸問題的一個初始基本可行解(10 分)專業(yè) .專注

5、.4 某公司有資金10 萬元，若投資用于項目i(i 1,2,3)的投資額為 xi時，其收益分別為 g1 ( x1 )4x1, g (x2 ) 9x2 ,g(x3 ) 2x3 , 問應(yīng)如何分配投資數(shù)額才能使總收益最大？ (15 分)5 求圖中所示網(wǎng)絡(luò)中的最短路 。（ 15 分）四川大學(xué)網(wǎng)絡(luò)教育學(xué)院模擬試題(A)管理運籌學(xué) 參考答案一、單選題1.C2.B 3.D4. A5. D6. B7. C 8.B9. B10.D二、多選題1. ABE2. ABE3. ACD4. AD5. AB三、計算題1、 max(-z)= x15x2'2( x3'x3'' )2、 寫出對偶問

6、題maxW=7 y1 11y2 14 y3專業(yè) .專注.3、解：4 解：狀態(tài)變量 sk 為第 k 階段初擁有的可以分配給第k 到底 3 個項目的資金額；決策變量 xk 為決定給第 k 個項目的資金額 ；狀態(tài)轉(zhuǎn)移方程為 sk 1skxk ；最優(yōu)指標函數(shù) fk (sk )表示第 k 階段初始狀態(tài)為 sk 時，從第 k 到第 3 個項目所獲得的最大收益，fk (sk ) 即為所求的總收益。遞推方程為 ：f k ( sk)max gk (xk) f k s(k 1 ) k( 1, 2, 3)0 xkskf 4 ( s4 )0當 k=3 時有f3 ( s3 )max 2 x320 x3 s3當 x3 s

7、3 時，取得極大值 2 s32，即：f3 (s3)max 2x322x320x3s3當 k=2 時有：f2 (s2 )max0xs9x22f3 ( s3 )22max 9x22s320x2s2max 9x22(s2x2 )0x2s2令h2 ( s2 , x2 )9x22 (s2x22 )用經(jīng)典解析方法求其極值點 。dh292( s2x2 )( 1)0由dx2x2s29解得：4d 2 h240而d x22專業(yè) .專注.x29所以s2是極小值點 。4極大值點可能在 0， s2 端點取得 ：f 2 (0) 2s22，f2 ( s2 ) 9s2當 f2 (0)f2 (s2 ) 時，解得s2 9 / 2

8、當 s29 / 2時， f 2 (0)f2 (s2 ) ，此時， x2*0當 s29 / 2 時， f 2 (0)f2 (s2 ) ，此時， x2*s2f1 (s1)max 4x1f 2 ( s2 )當 k=1 時，0x1s1當 f2 (s2 )f1( s1 )max 4x19s19x19s2 時，0 x1 s1max 9s15x19s10 x1 s1但此時s2 s1x110 0 10 9/2s29 / 2矛盾，所以舍去 。，與當 f2 (s2 )2f1 (10)max 4x12(s1x1 )22s2 時，0 x1 10令h1( s1 , x1 )4x1 2 (s1x12 )dh144( s2

9、x2 )( 1)0由dx1解得：x2s11d 2 h210而d x22所以x1s11 是極小值點 。比較 0,10 兩個端點x10 時， f1(10)200x110 時， f1(10)40x1*0所以再由狀態(tài)轉(zhuǎn)移方程順推 ：s2s1*10010x1因為s29 / 2所以x2*0 ， s3s2x2*10010因此x3*s310最優(yōu)投資方案為全部資金用于第3 個項目，可獲得最大收益200 萬元 。專業(yè) .專注.5. 解：用 Dijkstra 算法的步驟如下 ，P（ v1 ） 0T（ v j ）（ j 2 ， 37）第一步 ：因為 v1 ,v2 ， v1, v3A且 v2 ， v3 是 T 標號，則

10、修改上個點的T 標號分別為 ：T v2min T v2, P v1w12= min,055T v3min T v3, P v1w13= min,022所有 T 標號中 ， T（ v3 ）最小 ，令 P（ v3 ） 2第二步 ： v3 是剛得到的P 標號，考察 v3v3 ,v4 ， v3 ,v6A ，且 v5 ， v6 是 T 標號Tv4minTv4, P v3 w34= min,279Tv6min,24 6所有 T 標號中 ， T（ v2 ）最小 ，令 P（ v2 ） 5第三步 ： v2 是剛得到的P 標號，考察 v2Tv4minTv4, Pv2w24= min 9,527Tv5minTv5,

11、 Pv2w25 min,5712所有 T 標號中 ， T（ v6 ）最小 ，令 P（ v6 ） 6第四步 ： v6 是剛得到的P 標號，考察 v6Tv4minTv4, Pv6w64= min 9,627Tv5minTv5, Pv6w65 min 12,6 1 7T v7 minT v7 , Pv6 w67 min,6 612專業(yè) .專注.所有 T 標號中 ， T（ v4 ）， T（ v5 ）同時標號 ，令 P（ v4 ） =P （ v5 ） 7第五步 ：同各標號點相鄰的未標號只有v7T v7min T v7 , P v5w57 min 12,7 3 10至此 ：所有的 T 標號全部變?yōu)镻 標號

12、 ，計算結(jié)束 。 故 v1 至 v7 的最短路為 10。管理運籌學(xué) 模擬試題2一、單選題（每題分 ，共 20 分。）1 目標函數(shù)取極小 （ minZ ）的線性規(guī)劃問題可以轉(zhuǎn)化為目標函數(shù)取極大的線性規(guī)劃問題求解 ，原問題的目標函數(shù)值等于 （）。A. maxZB. max(-Z)C. max(-Z)D.-maxZ2.下列說法中正確的是（）。 基本解一定是可行解基本可行解的每個分量一定非負 若 B 是基 ，則 B 一定是可逆 非基變量的系數(shù)列向量一定是線性相關(guān)的3 在線性規(guī)劃模型中，沒有非負約束的變量稱為（）A 多余變量B 松弛變量C 人工變量D 自由變量4. 當滿足最優(yōu)解 ，且檢驗數(shù)為零的變量的個

13、數(shù)大于基變量的個數(shù)時，可求得（ ）。 多重解 無解 正則解 退化解5 對偶單純型法與標準單純型法的主要區(qū)別是每次迭代的基變量都滿足最優(yōu)檢驗但不完全滿足 （）。A 等式約束B“”型約束C“”約束D 非負約束6. 原問題的第 個約束方程是 “型” ，則對偶問題的變量yi 是（）。 多余變量自由變量松弛變量非負變量7. 在運輸方案中出現(xiàn)退化現(xiàn)象，是指數(shù)字格的數(shù)目()。A.等于 m+nB.大于 m+n-1C.小于 m+n-1D.等于 m+n-18.樹的任意兩個頂點間恰好有一條（）。 邊 初等鏈 歐拉圈 回路9 若 G 中不存在流f 增流鏈 ，則 f 為 G 的（）。專業(yè) .專注.A 最小流B 最大流C

14、 最小費用流D 無法確定10.對偶單純型法與標準單純型法的主要區(qū)別是每次迭代的基變量都滿足最優(yōu)檢驗但不完全滿足 （） 等式約束“”型約束“”型約束非負約束二、判斷題題 （每小題 2 分，共 10 分）1線性規(guī)劃問題的一般模型中不能有等式約束。（）2對偶問題的對偶一定是原問題 。（）3產(chǎn)地數(shù)與銷地數(shù)相等的運輸問題是產(chǎn)銷平衡運輸問題。（）4對于一個動態(tài)規(guī)劃問題 ，應(yīng)用順推或逆解法可能會得出不同的最優(yōu)解。 （）5在任一圖 G 中，當點集 V 確定后，樹圖是 G 中邊數(shù)最少的連通圖。（）三、計算題（共 70 分）1、某工廠擁有A,B,C 三種類型的設(shè)備，生產(chǎn)甲 、乙兩種產(chǎn)品 ，每件產(chǎn)品在生產(chǎn)中需要使用

15、的機時數(shù) ，每件產(chǎn)品可以獲得的利潤，以及三種設(shè)備可利用的機時數(shù)見下表：求：（ 1）線性規(guī)劃模型；（ 5 分）（ 2 ）利用單純形法求最優(yōu)解；（ 15 分）4. 如圖所示的單行線交通網(wǎng)，每個弧旁邊的數(shù)字表示這條單行線的長度。現(xiàn)在有一個人要專業(yè) .專注.從 v1 出發(fā) ，經(jīng)過這個交通網(wǎng)到達 v8 ，要尋求使總路程最短的線路。（ 15 分）5. 某項工程有三個設(shè)計方案。據(jù)現(xiàn)有條件，這些方案不能按期完成的概 率分別為0.5,0.7,0.9, 即三個方案均完不成的概率為0.5 ×0.7 ×0.9=0.315 。 為使這三個方案中至少完成一個的概率盡可能大，決定追加2 萬元資金 。當使

16、用追加投資后，上述方案完不成的概率見下表 ，問應(yīng)如何分配追加投資，才能使其中至少一個方案完成的概率為最大。(15 分 )各方案完不成的概率追加投資123（萬元）00.500.700.9010.300.500.7020.250.300.40管理運籌學(xué)模擬試題2 參考答案一、單選題1.C 2.B3.D 4. A.5. D6. B7. C 8.B9. B10.D二、多選題1.× 2. 3.× 4.5.三、計算題1. 解：（ 1） max z 1500x12500x23x12x265專業(yè) .專注. .滿足2x1x2403x27 5x1 , x20（ 2）cBxBb'1500

17、2500000x1x2x3x4x50x3653210032.50x44021010400x5750300125z0150025000000x3153010-2/350x4152001-1/37.52500x22501001/3_z-625001500000-2500/3-1500x15101/30-2/9_0x4500-2/311/9_2500x22501001/3_z-7000000-5000-500最優(yōu)解x*(5,25,0,5,0) T最優(yōu)目標值= 70000 元2. 解：此規(guī)劃存在可行解 x (0,1)T ，其對偶規(guī)劃mi nw4y11y42y33滿足：y13y 2y 332 y12 y

18、2y3 2y1 , y2 , y3 0專業(yè) .專注.對偶規(guī)劃也存在可行解y(0,1,0) T ，因此原規(guī)劃存在最優(yōu)解 。3、解：可以作為初始方案 。 理由如下 ：（1）滿足產(chǎn)銷平衡（2）有 m+n-1 個數(shù)值格（3）不存在以數(shù)值格為頂點的避回路4.解：5.解：此題目等價于求使各方案均完不成的概率最小的策略。 把對第k 個方案追加投資看著決策過程的第k 個階段 ，k 1 ， 2， 3 。xk -第 k 個階段 ，可給第 k, k+1 ， ，3 個方案追加的投資額。u k -對第 k 個方案的投資額D kuk uk0,1,2且ukxkxk 1xkuk階段指標函數(shù) C xk , ukp xk , u

19、k,這里的 p xk , uk是表中已知的概率值 。過程指標函數(shù)3Vk ,3C xk , ukVk 1,3i kf k xkmin C xk , u kf k 1 xk 1, f 4 x4 1ukD k以上的 k 1 ， 2， 3用逆序算法求解專業(yè) .專注.f3 x3min C x3 , u3k 3 時，u3D3得表 ：最優(yōu)策略 ： u1 1， u 2 =1,u 3 =0 或u1 0， u2 =2,u3 =0 ，至少有一個方案完成的最大概率為1-0.135=0.865四川大學(xué)網(wǎng)絡(luò)教育學(xué)院模擬試題(C)管理運籌學(xué) 二、多選題（每題 2 分，共 20 分）1求運輸問題表上作業(yè)法中求初始基本可行解的

20、方法一般有（）專業(yè) .專注.A 西北角法B 最小元素法C 單純型法D 伏格爾法E 位勢法2建立線性規(guī)劃問題數(shù)學(xué)模型的主要過程有（）A 確定決策變量B 確定目標函數(shù)C 確定約束方程D 解法E 結(jié)果3化一般規(guī)劃模型為標準型時，可能引入的變量有（）A 松弛變量B剩余變量C 自由變量D 非正變量E 非負變量8 就課本范圍內(nèi)，解有 “”型約束方程線性規(guī)劃問題的方法有（）A 大 M 法B 兩階段法C 標號法D 統(tǒng)籌法E 對偶單純型法10線性規(guī)劃問題的主要特征有（）A 目標是線性的B 約束是線性的C 求目標最大值D 求目標最小值E 非線性二、辨析正誤 （每題 2 分，共 10 分）1線性規(guī)劃問題的一般模型中

21、不能有等式約束。（）2線性規(guī)劃問題的每一個基本可行解對應(yīng)可行域上的一個頂點。（）3線性規(guī)劃問題的基本解就是基本可行解。（）4同一問題的線性規(guī)劃模型是唯一。（）5對偶問題的對偶一定是原問題。（）6產(chǎn)地數(shù)與銷地數(shù)相等的運輸問題是產(chǎn)銷平衡運輸問題。（）7對于一個動態(tài)規(guī)劃問題 ，應(yīng)用順推或逆解法可能會得出不同的最優(yōu)解。 （）8 在任一圖 G 中，當點集 V 確定后 ，樹圖是 G 中邊數(shù)最少的連通圖 。（）9若在網(wǎng)絡(luò)圖中不存在關(guān)于可行流f 的增流鏈時 ， f 即為最大流 。（）10 無圈且連通簡單圖G 是樹圖 。（）三、計算題（共 70 分）1、 某工廠要制作 100 套專用鋼架 ，每套鋼架需要用長為

22、2.9m , 2.1m , 1.5m 的圓鋼各一根 。已知原料每根長 7.4m ，現(xiàn)考慮應(yīng)如何下料 ，可使所用的材料最?。慨a(chǎn)品甲產(chǎn)品乙設(shè)備能力 /h設(shè)備 A3265設(shè)備 B2140專業(yè) .專注.設(shè)備 C0375利潤 /(元 /件)15002500求：（ 1 ）寫出線性規(guī)劃模型 （10 分）（ 2）將上述模型化為標準型（5 分）2 、求解下列線性規(guī)劃問題，并根據(jù)最優(yōu)單純形法表中的檢驗數(shù)，給出其對偶問題的最優(yōu)解。（ 15 分）m ax z4x13x27x3x12 x22 x31 0 0滿足3x1x23 x31 0 0x1 , x2 , x303 斷下表中方案是否可作為運輸問題的初始方案，為什么 ？

23、（ 10 分）4. 用 Dijkstra 算法計算下列有向圖的最短路 。（ 15分）v2272v65v3v155v731137v45v55 某集團公司擬將6 千萬資金用于改造擴建所屬的A、 B、 C 三個企業(yè) 。 每個企業(yè)的利潤增長額與所分配到的投資額有關(guān)，各企業(yè)在獲得不同的投資額時所能增加的利潤如下表所示。 集團公司考慮要給各企業(yè)都投資。問應(yīng)如何分配這些資金可使公司總的利潤增長額最大？（ 15 分）專業(yè) .專注.四川大學(xué)網(wǎng)絡(luò)教育學(xué)院模擬試題(C)管理運籌學(xué) 參考答案三、多選題1.ABD2.ABC3.ABC4. ABE.5. AB二、判斷題1. ×2. 3×4.×

24、5. 6.×7.× 8. 9. 10. 三、計算題1. 解 分析：利用 7.4m 長的圓鋼截成 2.9m , 2.1 m ,1.5m 的圓鋼共有如下表所示的 8 中下料方案 。方方案方案方案方案方案方案方案方案案12345678毛胚 /m2.9211100002.1021032101.510130234合計7.37.16.57.46.37.26.66.0剩 余 料0.10.30.901.10.20.81.4頭設(shè) x1 ， x2 ， x3 ， x4 ， x5 ， x6 ， x7 ， x8 分別為上面 8 中方案下料的原材料根數(shù)。min zx1x2x3x4x5x6x7x8專業(yè)

25、.專注.2. 解 ：引入松弛變量 x4 , x5 將模型化為標準型 ，經(jīng)求解后得到其最優(yōu)單純型表：最優(yōu)單純型表基bix1x2x3x4x5變量x2253/4103/41/2x3255/4011/41/2i-25010/4001/22由此表可知 ，原問題的最優(yōu)解 x*(0, 25, 25)T ，最優(yōu)值為 250. 表中兩個松弛變量的檢驗數(shù)分別為 1/2, 2 ,由上面的分析可知 ，對偶問題的最優(yōu)解為 (1/ 2,2)T 。3.解：不能作為初始方案 ，因為應(yīng)該有 n+m-1=5+4-1=8有數(shù)值的格 。4.解： P（ v1 ） 0T（ v j ） （ j 2 ， 3 7）第一步 ：因為 v1 ,v2

26、 ， v1, v3 ， v1 , v4 A且 v2 ， v3 ， v4 是 T 標號，則修改上個點的T 標號分別為 ：T v2min T v2, P v1w12= min ,022T v3min T v3, P v1w13= min ,055專業(yè) .專注.T v4min T v4 , P v1w14= min,033所有 T 標號中 ， T（ v2 ）最小，令 P（ v2 ） 2第二步 ： v2 是剛得到的P 標號，考察 v2v2 , v3 ， v2 ,v6A ，且 v3 ， v6 是 T 標號T v3min T v3, P v2 w23= min 5,22 4T v6min ,27 9所有

27、T 標號中 ， T（ v4 ）最小，令 P（ v4 ） 3第三步 ： v4 是剛得到的P 標號，考察 v4T v5 min T v5, P v4w45 min ,358所有 T 標號中 ， T（ v3 ）最小，令 P（ v3 ） 4第四步 ： v3 是剛得到的P 標號，考察 v3T v5min T v5, P v3w35 min 8,437T v6min T v6, P v3w36 min 9,4 5 9所有 T 標號中 ， T（ v5 ）最小，令 P（ v5 ） 7第五步 ： v5 是剛得到的P 標號，考察 v5T v6min T v6, P v5w56 min 9,71 8T v7min T v7, P v5w57 min ,7714所有 T 標號中 ， T（ v6 ）最小，令 P（ v6 ） 8第 6 步： v6 是剛得到的P 標號，考察 v6T v7 min T v7, P v6w67 min 14,8513T（ v7 ） P（ v7 ） 13至此 ：所有的 T 標號全部變?yōu)镻 標號 ，計算結(jié)束 。 故 v1 至 v7 的最短路為 13。專業(yè) .專注.5. 解：第一步 ：構(gòu)造求對三個企業(yè)的最有投資分配 ，使總利潤額最大的動態(tài)規(guī)劃模型。（1） 階段 k ：按 A