管理系統(tǒng)運籌學模擬精彩試題及問題詳解2

1、實用文檔四 川 大 學 網(wǎng) 絡 教 育 學 院 模 擬 試 題( a ) 管理運籌學一、單選題（每題分，共20 分。 ）1 目標函數(shù)取極?。╩inz）的線性規(guī)劃問題可以轉化為目標函數(shù)取極大的線性規(guī)劃問題求解，原問題的目標函數(shù)值等于（）。a. maxz b. max(-z) c. max(-z) d.-maxz 2.下列說法中正確的是（） ?；窘庖欢ㄊ强尚薪饣究尚薪獾拿總€分量一定非負若 b是基， 則 b一定是可逆非基變量的系數(shù)列向量一定是線性相關的3在線性規(guī)劃模型中，沒有非負約束的變量稱為（）多余變量 b松弛變量 c人工變量 d自由變量4. 當滿足最優(yōu)解，且檢驗數(shù)為零的變量的個數(shù)大于基變量的

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

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

4、變量 d剩余變量 e穩(wěn)態(tài)變量實用文檔5線性規(guī)劃問題的主要特征有（）a 目標是線性的 b約束是線性的 c求目標最大值d 求目標最小值 e非線性三、計算題（共60 分）1. 下列線性規(guī)劃問題化為標準型。(10 分) 123min+5-2zxxx123123121236235100,0,xxxxxxxxxxx 符號不限2. 寫出下列問題的對偶問題 (10 分) 123min42+3zxxx123123121234+56=78910111213140,0 xxxxxxxxxxx無約束，3. 用最小元素法求下列運輸問題的一個初始基本可行解(10 分 ) 4某公司有資金10 萬元，若投資用于項目(1,2,

5、3)ii ix的投資額為時，其收益分別為11122()4,()9,gxx g xx33()2,g xx問應如何分配投資數(shù)額才能使總收益最大？(15 分) 5 求圖中所示網(wǎng)絡中的最短路。（15 分）滿足滿足實用文檔四 川 大 學 網(wǎng) 絡 教 育 學 院 模 擬 試 題( a )管理運籌學參考答案一、單選題1.c 2.b 3.d 4. a 5. d 6. b 7. c 8.b 9. b 10.d 二、多選題1. abe 2. abe 3. acd 4. ad 5. ab 三、計算題1、max(-z)=123352()xxxx2、寫出對偶問題maxw=12371114yyy3、解：4解：狀態(tài)變量ks

6、為第 k 階段初擁有的可以分配給第k 到底 3 個項目的資金額；決策變量kx為決定給第 k 個項目的資金額；狀態(tài)轉移方程為1kkkssx；最優(yōu)指標函數(shù)()kkfs表示第 k 階段初始狀態(tài)為ks時， 從第 k 到第 3個項目所獲得的最大收益，()kkfs即為所求的總收益。遞推方程為：10()()() (1,2,3)maxkkkkkkkkxsfsgxfsk44()0fs當 k=3 時有3323330()2maxxsfsx當33xs時，取得極大值223s，即：實用文檔332233330()22maxxsfsxx當 k=2 時有：222222330()9()maxxsfsxfs22223092maxx

7、sxs22222092()maxxsxsx令2222222(,)92()h sxxsx用經(jīng)典解析方法求其極值點。由222292()( 1)0dhsxdx解得：2294xs而222240d hd x所以2294xs是極小值點。極大值點可能在 0 ，2s 端點取得：222(0)2fs，222()9fss當222(0)()ffs時，解得29/ 2s當29 / 2s時，222(0)()ffs，此時，*20 x當29/2s時，222(0)()ffs，此時，*22xs當 k=1 時，11111220()4()maxxsfsxfs當222()9fss時，11111110()499maxxsf sxsx111

8、110959maxxssxs但此時211100109/ 2ssx，與29 /2s矛盾，所以舍去。當2222()2fss時，121111010(10)42()maxxfxsx令2111111(,)42()h s xxsx由122144()( 1)0dhsxdx解得：211xs而222210d hd x所以111xs是極小值點。實用文檔比較0,10 兩個端點10 x時，1(10)200f110 x時，1(10)40f*10 x所以再由狀態(tài)轉移方程順推：*21110010ssx因為29 / 2s所以*20 x，*32210010ssx因此*3310 xs最優(yōu)投資方案為全部資金用于第3 個項目，可獲得

9、最大收益200 萬元。5. 解：用 dijkstra算法的步驟如下，p（1v） 0 t（jv）（j2，37）第一步：因為21,vv，31,vva且2v，3v是 t標號，則修改上個點的t 標號分別為：12122,minwvpvtvt =min,05513133,minwvpvtvt =min,022所有 t標號中， t（3v）最小，令p（3v） 2 第二步：3v是剛得到的p標號，考察3v34,v v，36,v va，且5v，6v是 t 標號44334min,t vtvp vw =min,2796min,2t v4 6所有 t標號中， t（2v）最小，令p（2v） 5 第三步：2v是剛得到的p標號

10、，考察2v44224min,t vt vp vw=min 9,52755225min,t vt vp vwmin,5712所有 t標號中， t（6v）最小，令p（6v） 6 實用文檔第四步：6v是剛得到的p標號，考察6v44664min,t vt vp vw=min 9,62755665min,t vt vp vwmin 12,61777667min,t vt vp vwmin,6612所有 t標號中， t（4v） ，t（5v）同時標號，令p（4v）=p（5v） 7 第五步：同各標號點相鄰的未標號只有7v57577,minwvpvtvtmin 12,7310至此：所有的t 標號全部變?yōu)閜標號，

11、計算結束。故1v至7v的最短路為 10。管理運籌學模擬試題2 一、單選題（每題分，共 20 分。 ）1目標函數(shù)取極?。╩inz）的線性規(guī)劃問題可以轉化為目標函數(shù)取極大的線性規(guī)劃問題求解，原問題的目標函數(shù)值等于（）。a. maxz b. max(-z) c. max(-z) d.-maxz 2. 下列說法中正確的是（） 。基本解一定是可行解基本可行解的每個分量一定非負若 b是基，則b一定是可逆非基變量的系數(shù)列向量一定是線性相關的3在線性規(guī)劃模型中，沒有非負約束的變量稱為（）a多余變量 b松弛變量 c人工變量 d自由變量4. 當滿足最優(yōu)解， 且檢驗數(shù)為零的變量的個數(shù)大于基變量的個數(shù)時，可求得（）

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

13、區(qū)別是每次迭代的基變量都滿足最優(yōu)檢驗但不完全滿足（）實用文檔等式約束 “”型約束 “”型約束非負約束二、判斷題題（每小題2 分，共 10 分）1線性規(guī)劃問題的一般模型中不能有等式約束。（）2對偶問題的對偶一定是原問題。（）3產地數(shù)與銷地數(shù)相等的運輸問題是產銷平衡運輸問題。（）4對于一個動態(tài)規(guī)劃問題，應用順推或逆解法可能會得出不同的最優(yōu)解。（）5在任一圖g中，當點集v確定后，樹圖是g中邊數(shù)最少的連通圖。（）三、計算題（共70 分） 1 、某工廠擁有a,b,c 三種類型的設備，生產甲、 乙兩種產品，每件產品在生產中需要使用的機時數(shù)，每件產品可以獲得的利潤，以及三種設備可利用的機時數(shù)見下表：求： （

14、1）線性規(guī)劃模型； （ 5 分）（2）利用單純形法求最優(yōu)解；（15 分）4.如圖所示的單行線交通網(wǎng)，每個弧旁邊的數(shù)字表示這條單行線的長度?，F(xiàn)在有一個人要從1v出發(fā)，經(jīng)過這個交通網(wǎng)到達8v，要尋求使總路程最短的線路。（15 分）實用文檔5. 某項工程有三個設計方案。據(jù)現(xiàn)有條件，這些方案不能按期完成的概率分別為0.5,0.7,0.9,即三個方案均完不成的概率為0.5 0.7 0.9=0.315 。為使這三個方案中至少完成一個的概率盡可能大，決定追加2 萬元資金。 當使用追加投資后，上述方案完不成的概率見下表，問應如何分配追加投資，才能使其中至少一個方案完成的概率為最大。(15 分) 管理運籌學模擬

15、試題2 參考答案一、單選題1.c 2.b 3.d 4. a .5. d 6. b 7. c 8.b 9. b 10.d 二、多選題1. 2. 3. 4. 5. 三、計算題1. 解： （1）12max15002500zxx123265xx滿足12240 xx2375x12,0 x x（2）bcbxb1500 2500 0 0 0 1x2x3x4x5x0 3x65 3 2 1 0 0 32.追加投資（萬元）各方案完不成的概率1 2 3 0 1 2 0.50 0.30 0.25 0.70 0.50 0.30 0.90 0.70 0.40 實用文檔5 0 4x40 2 1 0 1 0 40 0 5x7

16、5 0 3 0 0 1 25 z0 1500 2500 0 0 0 0 3x15 3 0 1 0 -2/3 5 0 4x15 2 0 0 1 -1/3 7.5 2500 2x25 0 1 0 0 1/3 _ z-62500 1500 0 0 0 -2500/3 - 1500 1x5 1 0 1/3 0 -2/9 _ 0 4x5 0 0 -2/3 1 1/9 _ 2500 2x25 0 1 0 0 1/3 _ z-70000 0 0 -500 0 -500 最優(yōu)解*(5,25,0,5,0)tx最優(yōu)目標值 = 70000 元2. 解：此規(guī)劃存在可行解(0,1)tx，其對偶規(guī)劃123min4143w

17、yyy滿足：12333yyy123222yyy123,0y yy對偶規(guī)劃也存在可行解(0,1,0)ty，因此原規(guī)劃存在最優(yōu)解。3、解：可以作為初始方案。理由如下：（1）滿足產銷平衡（2）有 m+n-1個數(shù)值格（3）不存在以數(shù)值格為頂點的避回路4. 解：實用文檔5.解：此題目等價于求使各方案均完不成的概率最小的策略。把對第 k 個方案追加投資看著決策過程的第k 個階段， k1， 2，3。kx-第 k 個階段，可給第k, k+1 ， 3 個方案追加的投資額。ku-對第 k 個方案的投資額kkkkkkkkuxxxuuud12 , 1 , 0且階段指標函數(shù)kkkkuxpuxc, 這里的kkuxp,是表

18、中已知的概率值。過程指標函數(shù)1,44113, 133,minxfxfuxcxfvuxcvkkkkdukkkkikkkkk以上的 k1，2，3 用逆序算法求解k3 時，3333,min33uxcxfdu得表：實用文檔最優(yōu)策略：1u1，2u=1, 3u=0 或1u0，2u=2, 3u=0，至少有一個方案完成的最大概率為1-0.135=0.865 四 川 大 學 網(wǎng) 絡 教 育 學 院 模 擬 試 題( c ) 管理運籌學二、多選題（每題 2 分，共 20 分）1 求運輸問題表上作業(yè)法中求初始基本可行解的方法一般有（） a 西北角法 b最小元素法 c單純型法 d伏格爾法 e位勢法2建立線性規(guī)劃問題數(shù)

19、學模型的主要過程有（）a 確定決策變量 b 確定目標函數(shù) c確定約束方程 d 解法 e結果3化一般規(guī)劃模型為標準型時，可能引入的變量有（） a 松弛變量 b剩余變量 c自由變量 d 非正變量 e非負變量8就課本范圍內，解有“”型約束方程線性規(guī)劃問題的方法有（） a大 m法 b兩階段法 c標號法 d統(tǒng)籌法 e對偶單純型法實用文檔10線性規(guī)劃問題的主要特征有（） a 目標是線性的 b 約束是線性的 c 求目標最大值 d 求目標最小值 e 非線性二、辨析正誤（每題2 分，共 10 分）1線性規(guī)劃問題的一般模型中不能有等式約束。（）2線性規(guī)劃問題的每一個基本可行解對應可行域上的一個頂點。（）3線性規(guī)劃

20、問題的基本解就是基本可行解。（）4同一問題的線性規(guī)劃模型是唯一。（）5對偶問題的對偶一定是原問題。（）6產地數(shù)與銷地數(shù)相等的運輸問題是產銷平衡運輸問題。（）7對于一個動態(tài)規(guī)劃問題，應用順推或逆解法可能會得出不同的最優(yōu)解。（）8在任一圖g中，當點集v確定后，樹圖是g中邊數(shù)最少的連通圖。（）9若在網(wǎng)絡圖中不存在關于可行流f 的增流鏈時，f 即為最大流。（）10無圈且連通簡單圖g是樹圖。（）三、計算題（共70分）1、某工廠要制作 100套專用鋼架，每套鋼架需要用長為2.9m , 2.1m , 1.5m的圓鋼各一根。已知原料每根長 7.4m ， 現(xiàn)考慮應如何下料， 可使所用的材料最??？產品甲產品乙設備

21、能力 /h 設備 a 3 2 65 設備 b 2 1 40 設備 c 0 3 75 利潤 /( 元 / 件) 1500 2500 求： （1）寫出線性規(guī)劃模型（10 分）（2）將上述模型化為標準型（5 分）2、求解下列線性規(guī)劃問題，并根據(jù)最優(yōu)單純形法表中的檢驗數(shù)，給出其對偶問題的最優(yōu)解。（15 分）123ax437mzxxx12322100 xxx12333100 xxx123,0 x xx3 斷下表中方案是否可作為運輸問題的初始方案，為什么？（10 分）4.用 dijkstra算法計算下列有向圖的最短路。（15 分）滿足實用文檔v2v6v1v4v5v7v32352173517555某集團公司

22、擬將6 千萬資金用于改造擴建所屬的a、b、c三個企業(yè)。每個企業(yè)的利潤增長額與所分配到的投資額有關，各企業(yè)在獲得不同的投資額時所能增加的利潤如下表所示。集團公司考慮要給各企業(yè)都投資。問應如何分配這些資金可使公司總的利潤增長額最大？（15 分）四 川 大 學 網(wǎng) 絡 教 育 學 院 模 擬 試 題( c ) 管理運籌學參考答案三、多選題1.abd 2.abc 3.abc 4. abe .5. ab 二、判斷題1. 2. 3 4. 5. 6. 7. 8. 9. 10. 三、計算題1. 解分析：利用 7.4m 長的圓鋼截成 2.9m , 2.1 m ,1.5m 的圓鋼共有如下表所示的 8 中下料方案。

23、方案毛胚/m 方 案1 方 案2 方 案3 方 案4 方 案5 方 案6 方 案7 方 案8 2.9 2 1 1 1 0 0 0 0 2.1 0 2 1 0 3 2 1 0 1.5 1 0 1 3 0 2 3 4 合計7.3 7.1 6.5 7.4 6.3 7.2 6.6 6.0 剩 余 料頭0.1 0.3 0.9 0 1.1 0.2 0.8 1.4 設1x，2x，3x，4x，5x，6x，7x，8x分別為上面 8 中方案下料的原材料根數(shù)。12345678min zxxxxxxxx實用文檔2. 解 ：引入松弛變量45,xx將模型化為標準型，經(jīng)求解后得到其最優(yōu)單純型表：最優(yōu)單純型表基變量ib1x2

24、x3x4x5x2x3x25 25 3/4 1 0 3/4 1/2 5/4 0 1 1/4 1/2 i-250 10/4 0 0 1/2 2 由此表可知，原問題的最優(yōu)解*(0, 25,25)tx，最優(yōu)值為250. 表中兩個松弛變量的檢驗數(shù)分別為1/2 , 2 , 由上面的分析可知，對偶問題的最優(yōu)解為( 1/ 2,2)t。3. 解：不能作為初始方案，因為應該有n+m-1=5+4-1=8有數(shù)值的格。 4. 解： p（1v） 0 t（jv）（j2，37）第一步：因為21,vv，31,vv，avv41,且2v，3v，4v是 t標號，則修改上個點的t 標號分別為：12122,minwvpvtvt =220

25、,min13133,minwvpvtvt =550 ,min14144,minwvpvtvt =330 ,min所有 t標號中， t（2v）最小，令p（2v） 2 實用文檔第二步：2v是剛得到的p標號，考察2v32,vv，avv62,，且3v，6v是 t 標號23233,minwvpvtvt =422, 5min972,min6vt所有 t標號中， t（4v）最小，令p（4v） 3 第三步：4v是剛得到的p標號，考察4v45455,minwvpvtvt853,min所有 t標號中， t（3v）最小，令p（3v） 4 第四步：3v是剛得到的p標號，考察3v35355,minwvpvtvt734

26、,8min36366,minwvpvtvt954,9min所有 t標號中， t（5v）最小，令p（5v） 7 第五步：5v是剛得到的p標號，考察5v56566,minwvpvtvt817,9min57577,minwvpvtvt1477,min所有 t標號中， t（6v）最小，令p（6v） 8 第 6 步：6v是剛得到的p標號，考察6v67677,minwvpvtvt1358 ,14mint（7v） p（7v） 13 至此：所有的t 標號全部變?yōu)閜標號，計算結束。故1v至7v的最短路為 13。5. 解：第一步：構造求對三個企業(yè)的最有投資分配，使總利潤額最大的動態(tài)規(guī)劃模型。（1） 階段 k ：按 a、b、c的順序，每投資一個企業(yè)作為一個階段，k1，2，3，4 （2） 狀態(tài)變量kx：投