《管理運(yùn)籌學(xué)》歷模擬試卷及答案

1、管理運(yùn)籌學(xué)歷年模擬試卷（一）一、單選題（每題 分，共 20 分。）1目標(biāo)函數(shù)取極?。?minZ）的線性規(guī)劃問題可以轉(zhuǎn)化為目標(biāo)函數(shù)取極大的線性規(guī)劃問題求解，原問題的目標(biāo)函數(shù)值等于（）。A. maxZ B. max(-Z) C. max(-Z) D.-maxZ 2. 下列說法中正確的是（）?；窘庖欢ㄊ强尚薪?每個(gè)分量一定非負(fù) 若 B是基，則 B一定是可逆 數(shù)列向量一定是線性相關(guān)的基本可行解的 非基變量的系3在線性規(guī)劃模型中，沒有非負(fù)約束的變量稱為（）多余變量 B松弛變量 C人工變量 D自由變量4. 當(dāng)滿足最優(yōu)解， 且檢驗(yàn)數(shù)為零的變量的個(gè)數(shù)大于基變量的個(gè)數(shù)時(shí)，可求得（）。多重解 無解 正則解退化解

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

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

4、變量5線性規(guī)劃問題的主要特征有（）A目標(biāo)是線性的 B約束是線性的 C求目標(biāo)最大值D求目標(biāo)最小值 E非線性三、計(jì)算題（共 60 分）1. 下列線性規(guī)劃問題化為標(biāo)準(zhǔn)型。(10 分) min Z x 1 +5 x 2-2 x 3x 1 x 2 x 3 6滿足 2 x 1 x 2 3 x 3 5x 1 x 2 10 x 1 0, x 2 0, x 符號(hào)不限2. 寫出下列問題的對(duì)偶問題 (10 分) min Z 4 x 1 2 x 2 +3 x 34 x 1 +5 x 2 6 x 3 =78 x 1 9 x 2 10 x 3 11滿足12 x 1 13 x 2 14x 1 0, x 2 無約束，x 3

5、03. 用最小元素法求下列運(yùn)輸問題的一個(gè)初始基本可行解 (10 分) 4某公司有資金 10 萬元，若投資用于項(xiàng)目i i1,2,3)的投資額為x i時(shí)，其收益分別為g x 1)x g x 2)9x 2,g x 3)2x 問應(yīng)如何分配投資數(shù)額才能使總收益最大？(15 分) 5 求圖中所示網(wǎng)絡(luò)中的最短路。 （15 分）管理運(yùn)籌學(xué)歷年模擬試卷（一）參考答案一、單選題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 三、計(jì)算題1、max(-z)=x 15 x 22( x 3 x 3)2、

6、寫出對(duì)偶問題maxW= 7y 111y 214y 33、解：4解：狀態(tài)變量 ks為第 k 階段初擁有的可以分配給第 k 到底 3 個(gè)項(xiàng)目的資金額；決策變量 kx為決定給第 k 個(gè)項(xiàng)目的資金額；狀態(tài)轉(zhuǎn)移方程為 s k 1 s k x ；最優(yōu)指標(biāo)函數(shù) f k ( s k )表示第 k 階段初始狀態(tài)為 ks時(shí)，從第 k 到第 3 個(gè)項(xiàng)目所獲得的最大收益，f k ( s k )即為所求的總收益。遞推方程為：f k ( s k ) max 0 x k s k g k ( x k ) f k ( s k 1 ) ( k 1,2,3)f 4 ( s 4 ) 0當(dāng) k=3 時(shí)有f3(s 3)max 0 x 3

7、 s 322 x 32 )當(dāng)x 3s 時(shí)，取得極大值22 3s，即：f 3(s 3)max 0 x 3 s 322 x 322 x 3當(dāng) k=2 時(shí)有：f2(s 2)max 0 x 2 s 292 x 2f3(s 3)0 max x 2 s 29 x 22 2 s 30 max 2 29x22(s 2x2)令h s x 2)9 x 22(s 2x 2用經(jīng)典解析方法求其極值點(diǎn)。由dh 292(s 2x2)( 1)0dx 2解得：x2s 294而2 d h 2402 d x 2所以x2s 29是極小值點(diǎn)。4極大值點(diǎn)可能在 0 ，2s 端點(diǎn)取得：2f 2 (0) 2 s ，f 2 ( s 2 ) 9

8、 s 2當(dāng) f 2 (0) f 2 ( s 2 ) 時(shí)，解得 s 2 9/ 2當(dāng) s 2 9 / 2 時(shí)，f 2 (0) f 2 ( s 2 )，此時(shí)，x *2 0*當(dāng) s 2 9/ 2 時(shí)，f 2 (0) f 2 ( s 2 )，此時(shí)，x 2 s 2當(dāng) k=1 時(shí)，f 1 ( s 1 ) max 0 x 1 s 1 4 x 1 f 2 ( s 2 )當(dāng) f 2 ( s 2 ) 9 s 時(shí)，f s 1 ) max 0 x 1 s 1 4 x 1 9 s 1 9 x 1max 0 x 1 s 1 9 s 1 5 x 1 9 s 1但此時(shí) s 2 s 1 x 1 10 0 10 9/ 2，與 s

9、2 9 / 2 矛盾，所以舍去。當(dāng) f 2 ( s 2 ) 2 s 時(shí)，2 f 1 (10) max 0 x 1 10 4 x 1 2( s 1 x 1 ) 2令 h s x 1 1 1 ) 4 x 1 2( s 1 x 1 ) 2dh 1 4 4( s 2 x 2 )( 1) 0由 dx 1解得：x 2 s 1 12 d h 22 1 0而 d x 2 所以 x 1 s 1 1 是極小值點(diǎn)。比較 0,10 兩個(gè)端點(diǎn) x 1 0 時(shí)，f 1(10) 200 x 1 10 時(shí)，f 1(10) 40* x 1 0所以再由狀態(tài)轉(zhuǎn)移方程順推：s 2s 1* x 110010200 萬元。因?yàn)閟 29

10、/ 2所以* x 20，s 3s 2* x 210010因此* x 3s 310最優(yōu)投資方案為全部資金用于第3 個(gè)項(xiàng)目，可獲得最大收益5. 解：用 Dijkstra算法的步驟如下，P（v ） 0 T（jv）（j2，3 7）第一步：因?yàn)?v 1, v 2，v 1,v 3 A且 v ，3v是 T 標(biāo)號(hào)，則修改上個(gè)點(diǎn)的 T 標(biāo)號(hào)分別為：T v 2 min T v 2 , P v 1 w 12 = min ,0 5 5T v 3 min T v 3 , P v 1 w 13 = min ,0 2 2所有 T 標(biāo)號(hào)中， T（v ）最小，令 P（v ） 2 第二步：3v是剛得到的 P標(biāo)號(hào)，考察 v 3v

11、v 4，v v 6 A ，且 v ，v 是 T 標(biāo)號(hào)T v 4 min T v 4 , P v 3 w 34 = min ,2 7 9T v 6 min ,24 6所有 T 標(biāo)號(hào)中， T（2v）最小，令 P（v ）5 第三步：2v是剛得到的 P標(biāo)號(hào)，考察 v 2T v 4 min T v 4 , P v 2 w 24=min 9,5 2 7T v 5 min T v 5 , P v 2 w 25min ,5 7 12所有 T 標(biāo)號(hào)中， T（6v）最小，令 P（6v）6 第四步：6v是剛得到的 P標(biāo)號(hào)，考察 v 6T v 4 min T v 4 , P v 6 w 64=min 9,6 2 7T v 5 min T v 5 , P v 6 w 65min 12