管理運籌學模擬試題及答案

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

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

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

4、線性規(guī)劃、A人工變量B .松弛變量確定換入變量 構造基本矩陣時，可用的變量有 C. 負變量 D 剩余變量（）E 穩(wěn)態(tài)變量5線性規(guī)劃問題的主要特征有 A目標是線性的BD.求目標最小值E計算題（共 60 分）1.下列線性規(guī)劃問題化為標準型。（.約束是線性的 .非線性.求目標最大值(10 分)2.min Zx1+5x2-2x3X2 X36x2 3x35X2100, X20, X3符號不限（10 分）2x2+3x3滿足r X12x1XiJ X1寫出下列問題的對偶問題min Z滿足4x, +5x2 6X3=78為 9x2 10x3 1112x1 13屜 14X10,X2無約束，X30BlB2B3B4產量

5、Al10671241610&日9A35410LO4銷S52463.用最小元素法求下列運輸問題的一個初始基本可行解（10 分）4 .某公司有資金10萬元，若投資用于項目i(i 1,2,3)的投資額為Xi時，其收益分別為gi(xi)4xi,g（X2） 9x2,g(X3) 2x3,問應如何分配投資數(shù)額才能使總收益最大?（15 分）5.求圖中所示網絡中的最短路。(15分)學網絡教育學管理運籌學參考答案一、單選題4. A 5. D 6. B二、多選題1. ABE 2. ABE 3. ACD三、計算題7. C9. B4. AD5. AB1、max(-z)=x1 5X2 2皿X3)心-右一(

6、3;-+首二 62工1 + X； + 3(h； 一 x, =5町一屯1 = 10%工1，屯工滬屯"旺,工5> 02、寫出對偶問題BlB203B4產sAl3t4'A2450A3L4錯a5243、解:maxW=7y1 11y2 14y3"id ij. + H V. 4-17 'll- > idfk(Sj4. 解：狀態(tài)變量Sk為第k階段初擁有的可以分配給第k到底3個項目的資金額； 決策變量Xk為決定給第k個項目的資金額；狀態(tài)轉移方程為Sk 1 Sk xk ；最優(yōu) 指標函數(shù)fk(sk)表示第k階段初始狀態(tài)為2時，從第k到第3個項目所獲得的最大收益, 即為

7、所求的總收益。遞推方程為：fk(Sk)-；0遼瓦f4(S4)0當k=3時有max gk(xk) fk (Sk 1)(k 1,2,3)max0 x3 S322 s3,max 2x30 x3 S3f36)當x3S3時，取得極大值f3(S3)即:2x1當k=2時有：f3(S3)f2 (s2) max 9x20 x S2max 9x2082max 9X2082令h2(S2,X2)2s22(S2 X2)29x22(S2 x2)用經典解析方法求其極值點。dh2dx22(82X2)( 1) 0解得:X2S2所以X2d2h24f 0d X；9So 4是極小值點。極大值點可能在0，雖端點取得： f2(0) 2S

8、2-當 f2(0) f2 (S2)時，解得 529/ 2當 S2 f 9/2 時，當 82 P 9/2 時，f2(S2) 9S2f2(0) f f2(S2)，此時,X2當k=1時,f2(0) P f2(S2)，此時，X2masX4Xi f2(S2)fi(S)當 f2(S2) 9s2 時,fi(Si)masX4xi 9siS29xi但此時82SXi當 f2(S2)max 9$ 5xi0 Xi S|i0 0 i0f 9/2，與S2P 9/2矛盾，所以舍去。24xi 2(Si Xi)fi(10)2s2 時，hi(Si,Xi)似 2(s Xi)2dxi4(S2X2)( I) 0解得:X2Sd2h2 d

9、 x；if 0比較0,i0兩個端點XiXi所以xi 0 時，fi(i0) i0時，03 i是極小值點。200fi(i0)所以再由狀態(tài)轉移方程順推：10s2 s1 x1* 10 0因為s2 f 9/2所以x20， s3 s2 x2 100 10x3s3 10因此最優(yōu)投資方案為全部資金用于第3 個項目，可獲得最大收益 200 萬元。5. 解：用 DiJkstra 算法的步驟如下，(J = 2, 3 7)P ( Vl )= 0且V2 ,V3是T標號，則修改上個點的T 標號分別為T v2min T v2 ,P v1w12=min ,0 5 5T v3min T v3 ,P v1w13=min ,0 2

10、 2所有 T標號中，T ( V3)最小，令P(V3 )= 2第二步：V3是剛得到的P標號，考察V3v3,v4，V3,V6a，且 v5，v6 是 T 標號T v4min T V4 ,P V3w34min ,2 7 9T v6min ,2+ 4 = 6所有T標號中，T ( V2)最小，令P(v2 )= 5第三步：V2是剛得到的P標號，考察V2T v4min T V4 ,P V2w24=min 9,5 27T v5min T V5 ,P V2w25_ min ,5 712所有 T標號中，T ( v)最小，令P宀)=6第四步：V6是剛得到的P標號，考察V6T v4min T V4 ,P V6w64=m

11、in 9,6 27T v5min T V5 ,P V6w65因為 v1,v2v1,v3AT ( VJ )=第一步：T v7min12,6T v7,Pv6w67=min,612所有T標號中，T （ v）, T （ V5 ）同時標號，令P （ V4）=p（ V5）= 7第五步：同各標號點相鄰的未標號只有v7T v7 min T v7 ,P v5w57= min 12,7 310至此：所有的T標號全部變?yōu)镻標號,計算結束。故V至V7的最短路為 10 。管理運籌學模擬試題一、單選題（每題2分，共20分。）1. 目標函數(shù)取極?。╩inZ）的線性規(guī)劃問題可以轉化為目標函數(shù)取極大的線性規(guī)劃問 題求解，原問題

12、的目標函數(shù)值等于（A. maxZ B. max（-Z）2. 下列說法中正確的是（A.基本解一定是可行解C.）。C.若B是基，則B一定是可逆）。max(-Z)B.基本可行解的每個分量一定非負D.非基變量的系數(shù)列向量一定是線性相關的3. 在線性規(guī)劃模型中，沒有非負約束的變量稱為（A.多余變量4. 當滿足最優(yōu)解， 且檢驗數(shù)為零的變量的個數(shù)大于基變量的個數(shù)時，A.多重解B .松弛變量）C .人工變量D .自由變量可求得（）。B.無解C.正則解D.退化解5. 對偶單純型法與標準單純型法的主要區(qū)別是每次迭代的基變量都滿足最優(yōu)檢驗但不 完全滿足（A）。.等式約束B .迂”型約束C .“ ”約束D .非負約束

13、6.7.A.8.則對偶問題的變量 C.松弛變量 在運輸方案中出現(xiàn)退化現(xiàn)象，是指數(shù)字格的數(shù)目 等于 m+n B. 大于 m+n-1 C. 小于 樹T的任意兩個頂點間恰好有一條（ A.邊B.初等鏈C.歐拉圈若G中不存在流f增流鏈，則f為G的（原問題的第1個約束方程是=”型,A.多余變量B.自由變量yi 是（）。D.非負變量( )m+n-1)。D. 等于 m+n-1D.回路9.A10. 對偶單純型法與標準單純型法的主要區(qū)別是每次迭代的基變量都滿足最優(yōu)檢驗但不 完全滿足（ ）A.等式約束 B.迂”型約束C. 型約束二、判斷題題（每小題 2 分，共 10分）1. 線性規(guī)劃問題的一般模型中不能有等式約束。

14、2. 對偶問題的對偶一定是原問題。3. 產地數(shù)與銷地數(shù)相等的運輸問題是產銷平衡運輸問題。4. 對于一個動態(tài)規(guī)劃問題，應用順推或逆解法可能會得出不同的最優(yōu)解。）。.最小流 B .最大流 C .最小費用流D .無法確定D.非負約束(）樹圖是G中邊數(shù)最少的連通圖。產品甲Q產品乙-設備能力/hd設®A"3卩餉設SB*24片設備Cd0門7加釉越（元八牛Z1孔22刃2生產甲、乙兩種產品，每件產品在生產中需要使 以及三種設備可利用的機時數(shù)見下表：5.在任一圖G中，當點集V確定后， 三、計算題（共70分）1、某工廠擁有 A,B,C三種類型的設備, 用的機時數(shù)，每件產品可以獲得的利潤，求：（

15、1 ）線性規(guī)劃模型；（5分）（2）利用單純形法求最優(yōu)解；（15分）2用對偶理論判斷下面線性規(guī)劃是否存在最優(yōu)解，10分）屮 maxz = 2西十2禺L 五十2花5化滿足:3工1 + 2 叼 <14+J3. 判斷下表中的方案能否作為表上作業(yè)法求解E輸問題的初皓方累，說朋理由口心分”硝地4嚴4BlE3B341產壘口2Alv1020p30'vd3020時5DA弘eIN4J銷量d105035Qd4.如圖所示的單行線交通網，每個弧旁邊的數(shù)字表示這條單行線的長度。現(xiàn)在有一個人要 從Vi出發(fā)，經過這個交通網到達 V8，要尋求使總路程最短的線路。（15分）5.某項工程有三個設計方案。 案均完不成的

16、概率為XX =。萬元資金。當使用追加投資后， 能使其中至少一個方案完成的概率為最大?！?即三個方2據現(xiàn)有條件，這些方案不能按期完成的概率分別為 為使這三個方案中至少完成一個的概率盡可能大，決定追加上述方案完不成的概率見下表，問應如何分配追加投資，才（15 分）追加投資（萬元）各方案完不成的概率123012管理運籌學模擬試題 2參考答案單選題4. A .5. D 6. B 7. C9. B二、多選題1.X 2. V3. X4. V5i. V三、計算題1.解：（1） maXZ 1500x12500X23為 2x265滿足2為X2403x275Xi,X20CBXb11X2X

17、3X4X50X365321000x4021010400X5750300125z0150025000000X3153010-2/350x152001-1/32500X22501001/3z-625001500000-2500/3-1500X15101/30-2/90x500-2/311/92500X22501001/3z-7000000-5OO0-5OO*T最優(yōu)解x(5,25,o,5,O)最優(yōu)目標值=70000元2. 解：此規(guī)劃存在可行解x (0,1)"，其對偶規(guī)劃min W 4y1 14y2 3y3yi 3y22yiyi,y2,y30對偶規(guī)劃也存在可行解y滿足:y 3(0,1,0)T

18、，因此原規(guī)劃存在最優(yōu)解。2y2 y32理由如下:3、解：可以作為初始方案。(1) 滿足產銷平衡(2) 有m+n-1個數(shù)值格(3) 不存在以數(shù)值格為頂點的避回路4. 解:心'刃=十工n '陽：=-?35.解：此題目等價于求使各方案均完不成的概率最小的策略。策過程的第k個階段，k= 1, 2, 3。把對第k個方案追加投資看著決Xk第k個階段，可給第k, k+1，3個方案追加的投資額。UkDk-對第k個方案的投資額Uk Uk 0,1,2且UkXkXk 1 Xk UkVk,3階段指標函數(shù)CXjUk P Xk，Uk過程指標函數(shù)3C Xk > UkVk 1,3i k，這里的P Xk，

19、Uk是表中已知的概率值。fk Xk以上的用逆序算法求解min C xk>uk fk 1 xkk = 1, 2, 31 , f4 X41k= 3 時,f3 X3minCz得表:/J 心 1+J21戶+J2盧AOd0.30如0門0.卻a沖*0 7*2D.如0 4戶0%扣表1卩*S 0乞七! X心L/W0Q0屮0.7X0.P4JOp1職0.7X0.7 卩0 5X0 %0 45k20 7X0 40.5 乂 訃0 2了門丄口 表22P、叫 g 0片4&知心3y?巧冷pP0護1QAa0,5X0；帀0.3X0.45 屮0J5xa.e3<j0.135oa*最優(yōu)策略：Ul = 1, u2=1

20、, U3=0或U1 = 0, u2 =2, U3 =0 ,至少有一個方案完成的最大概率為四川大學網絡教育學院模管理運籌學二、 多選題(每題2分，共20分)1.求運輸問題表上作業(yè)法中求初始基本可行解的方法一般有A 西北角法 B 最小元素法 C 單純型法 D .2建立線性規(guī)劃問題數(shù)學模型的主要過程有A.確定決策變量B .確定目標函數(shù)C 確定約束方程 D3化一般規(guī)劃模型為標準型時，可能引入的變量有伏格爾法.解法A .松弛變量 B .剩余變量 C .自由變量 D .非正變量 &就課本范圍內，解有型約束方程線性規(guī)劃問題的方法有A .大M法 B.兩階段法C .標號法 D .統(tǒng)籌法(位勢法(.結果(

21、.非負變量( ) 對偶單純型法10.線性規(guī)劃問題的主要特征有A1.2.3.4.5.6.7.8.9.目標是線性的 B .約束是線性的 C .求目標最大值 D .求目標最小值 辨析正誤（每題2分，共10分） 線性規(guī)劃問題的一般模型中不能有等式約束。線性規(guī)劃問題的每一個基本可行解對應可行域上的一個頂點。 線性規(guī)劃問題的基本解就是基本可行解。同一問題的線性規(guī)劃模型是唯一。 對偶問題的對偶一定是原問題。 產地數(shù)與銷地數(shù)相等的運輸問題是產銷平衡運輸問題。 對于一個動態(tài)規(guī)劃問題，應用順推或逆解法可能會得出不同的最優(yōu)解。 在任一圖G中，當點集V確定后，樹圖是 G中邊數(shù)最少的連通圖。 若在網絡圖中不存在關于可行

22、流f的增流鏈時，f即為最大流。（ ）E 非線性( ( ( ( ( ( ( () ) ) ) ) ) ) ) )10 .無圈且連通簡單圖 G是樹圖。三、計算題（共70分）1、某工廠要制作100套專用鋼架，每套鋼架需要用長為 2.9m , 2.1m , 1.5m的圓 鋼各一根。已知原料每根長7.4m，現(xiàn)考慮應如何下料，可使所用的材料最?。慨a品甲產品乙設備能力/h設備A3265設備B2140設備C0375利潤/（元/件）15002500求：（1）寫出線性規(guī)劃模型（10分）（2）將上述模型化為標準型（5分）2、求解下列線性規(guī)劃問題，（15 分）并根據最優(yōu)單純形法表中的檢驗數(shù),給出其對偶問題的最優(yōu)解。m

23、ax z滿足4x1 3x2 7x3X, 2x2 2x31003x1 x2 3x3100Xi, X2,X303.4.用Dijkstra算法計算下列有向圖的最短路。（15分）示。大?5.某集團公司擬將 6千萬資金用于改造擴建所屬的A、B、C三個企業(yè)。每個企業(yè)的利潤增長額與所分配到的投資額有關，各企業(yè)在獲得不同的投資額時所能增加的利潤如下表所 集團公司考慮要給各企業(yè)都投資。問應如何分配這些資金可使公司總的利潤增長額最（15 分）各企業(yè)獲取不同投資額時増加的利潤表單位：千萬元）投資歆y、ABCL2342<55731110g4151314網絡教育學院模擬試題（C ） 管理運籌學參考答案1.多選題4

24、. ABE判斷題X 2. V 35. ABX 4. X 5.V 6. X 7. X 8. V 9. V 10. V三、計算題1.解 分析：利用7.4m長的圓鋼截成2.9m , 2.1 m ,1.5m的圓鋼共有如下表所 示的8中下料方案。方案毛胚/m方案1方案2方案3方案4方案5方案6方案7方案8211100000210321010130234合計剩余料 頭0設X1 , x2 ,沁,x4 , x5 , x6 , x7 , x8分別為上面8中方案下料的原材料根數(shù)。min z X1 X2 x3 x4 x5 x6 x7 x8滿足2花 + 礙+ 2心 + 可 00兀1十花十3曲十2蘇十3可十4 王100

25、丙*花住3*召，衛(wèi)5*h&叼西之02.解：引入松弛變量滄"5將模型化為標準型，經求解后得到其最優(yōu)單純型表: 最優(yōu)單純型表基變量bXX2X3X4XX2253/4103/41/2X3255/4011/41/2i-25010/4001/22*T由此表可知，原問題的最優(yōu)解X (O,25,25),最優(yōu)值為250.表中兩個松弛變量的檢驗數(shù)分別為一1/2 , 2，由上面的分析可知，對偶問題的最優(yōu)解為(1/ 2,2)。因為應該有 n+m-1=5+4-1=8有數(shù)值的格。3. 解：不能作為初始方案,4. 解：P ( Vi )= 0第一步:=(J = 2, 3 7)因為 Vi,V2 , Vi,V3

26、 , Vi,V4A且V2 ,TV3 , V4是T標號，則修改上個點的 T標號分別為:mn_ minmnminV4min _ minT V2 , P Vi,0T V3,0T V4,0,P Vi5 5,P Vi3 3Wi2Wi3Wi4(V2 )最小，令 p ( V2 )= 2所有T標號中，T第二步：V2是剛得到的P標號，考察V2V2,V3 , V2,V6A，且 V3 , V6 是 T 標號T V3min T V3 ,P V2w23=min 5,2 2 4 T V6min,27 =9所有 T 標號中， T（ v4 ）最小，令 Pv4)第三步： V4 是剛得到的 P 標號，考察 T V5min T V

27、5 ,P V4w45= min ,3 5 8v4所有 T 標號中， T（V3 ）最小，令 PV3)第四步： V3 是剛得到的 P 標號，考察 T V5 min T V5 ,P V3= min 8,4w3537v3T V6min T V6= min 9,4,P V3w3659v5)第五步：v是剛得到的P 標號，考察TV6min T V6,PV5w56= min 9,718TV7min T V7,PV5w57= min ,7714v5 ）最小，令 P所有 T 標號中， TT（v6 ）最小，令 P所有 T 標號中，第 6 步： V6 是剛得到的 P 標號，考察 T V7min T V7 ,P V6w67min 14,8 5 13v5v6)v62）v7 )= 13T（ v7）= P至此：所有的T標號全部變?yōu)镻標號，計算結束。故Vi至V7的最短路為 13。5. 解：第一步：