2005學(xué)年《運籌學(xué)》試題A(1)匯總

1、、單項選擇題 （102=20分）1 判斷下面哪個模型不是線性規(guī)劃模型（）B. minZ =龍+ 7航- X2+ 4x 0112.下列哪個關(guān)于線性規(guī)劃最優(yōu)解的描述是正確的（）A.線性規(guī)劃問題的每一個基本解對應(yīng)可行域的一個頂點；B.若分別為某一個線性規(guī)劃問題的最優(yōu)解，則也是該線性規(guī)劃問題的最優(yōu)解，其中為任意實數(shù)；C.每個線性規(guī)劃問題的兩條約束直線的交點都對應(yīng)一個基本解；運籌學(xué)試題 A 切x, + 5 x3 b鬲 A0X、max Z = x + 2 x, +圧上.+ 5xys 6A, 0,禺2 0D. max Z- Xj + 2 x, -iX、D.每個線性規(guī)劃問題的基本解一定是某兩個約束直線方程的交

2、點；J、彳巧*嗎-2 鬲工山3.已知某線性規(guī)劃問題的約束為% 2 ,判斷下列各點哪個是該線性規(guī)劃問題的可行域的頂點（）A.X X= （1,10, 22, 14；B.X X= （3, -1, 7, 1；C.X X= （2, 4, 0, 7；D.X X= （3, 5, 1,1；4.若將原來求極小的線性規(guī)劃問題轉(zhuǎn)化為其對偶問題，下列說法正 確的是（）A.原問題第 i i 個變量，則轉(zhuǎn)化后的第 i i 個約束條件類型為；B.原問題第 i i 個變量為自由變量，則轉(zhuǎn)化后的第 i i 個約束條件類型為；C.原問題第 j j 個約束條件類型為，則轉(zhuǎn)化后的第 j j 個變量為自由變量；D.原問題第 j j 個

3、約束條件類型為，則轉(zhuǎn)化后的第 j j 個變量；5.線性規(guī)劃問題min Z二3州 +5.V,2A, ；Bz i /f - I；CA i t ；D丄 $ p Z 丨.（16 分）用大 M 方法求解下面的線性規(guī)劃問題:min Z - 3A, + Sx2齊+禺21斗 4- 2A; 4州 2 0. Jtj 20三、（18 分）某工廠生產(chǎn) 3 種產(chǎn)品 A, B, C,每種產(chǎn)品的單位利潤為 4, 1, 5;而生產(chǎn)每件商品所需耗費的勞動力資源分別為 2,1, 3;而所需的原材料分別為 3,2, 5;而在一周內(nèi)，勞動力資源取多為 性規(guī)劃模型求得最優(yōu)表如下表所示：30個單位, 原材料供應(yīng)最多為60 個；建立線4

4、1 5 0 0b4151 1/2 3/2 1/2 00 1 1 2 E 600根據(jù)最優(yōu)表回答下列問題：1. 要使得生產(chǎn)計劃不改變，A 產(chǎn)品的單位利潤的允許變動范圍是什么？（4 分）2. 若增加一種產(chǎn)品，其利潤為 6,所需的單位勞動力和原材料分別為 2 和5,則問是否要調(diào)整生產(chǎn)計劃，若需調(diào)整，求修改方案；（6 分）3. 若每周的勞動力可以多提供 20 個，則是否要修改生產(chǎn)計劃？若要修改，求修改方案（8 分）四、（16 分）現(xiàn)要在 5 個工人中確定出 4 個人來分別完成 4 項任務(wù)。每項任務(wù)只能由一個人來完成，而且每個人只能完成一項任務(wù)。每個工人完成每項任務(wù)所需的工時數(shù)如下表所示任務(wù)工人ABCDI

5、9437II4656III5475IVV10674試用運輸模型和方法找出一個工作分配方案，使得總工時最少。五、（16 分）設(shè)某公司擬將五臺設(shè)備分配給下屬的甲、乙、丙三個工廠。各個 工廠獲得設(shè)備后，可以為公司帶來的盈利如下表所示：工廠設(shè)備臺數(shù)甲乙丙000013542710639111141211125131113問：分配給各個工廠多少臺設(shè)備，可以為公司帶來盈利的總利潤的總和最大六、（6 分）求下圖的最小生成樹:七、（8 分）一個理發(fā)店只有一個理發(fā)師，有三個空椅供等待理發(fā)的人使用。設(shè)顧客以泊松 流來到系統(tǒng)，平均每小時 5 人；理發(fā)師的理發(fā)時間服從負指數(shù)分布，平均一個 人需要 10 分鐘。求系統(tǒng)各個

6、狀態(tài)的發(fā)生概率以及系統(tǒng)的平均排隊等待時間。答案一、單項選擇題1. C 2. D 3. A 4. D 5. B 6. D 7. D 8. C 9. A 10. C解：將問題標(biāo)準(zhǔn)化得:.（4分）max ZF= - 3 - A/q顯然系數(shù)矩陣中沒有單位陣，故在第一個約束中增加一個人工變量得新問題（8 分）F 面用表格單純形法求解該問題:M-3 M-5 -MM 0 00 -2 -3 0 3-Z3M.（14 分）此時人工變量，故有最優(yōu)解，對應(yīng)原問題的最優(yōu)解為；最優(yōu)值為 3。.（ 16 分）-3 -5 0 01-1 0 11/11 2 0 1 04/1-301 1 -1 0 10 1 1 1 -1斗解:1

7、.設(shè)此時 A 的利潤變?yōu)闉?，由于為基變量，所以影響所有的檢驗數(shù)計算各個非基變量的檢驗數(shù)得= 5 - 3c, y 2Yd，要使生產(chǎn)計劃不變，則要求所有檢驗數(shù)仍然非正，即有2.增加商品 D 后，最優(yōu)表變?yōu)镴b4 1 5 0 0 64151 1/2 3/2 1/2 0 115/10151 1/2 1/2 1/2 115/8一0 1 -1 2 600 2_汕口 4 們 0），從而得嚀3；（4分）415/21/2 1/4 5/4 1/4 -1/2 0615/21/2 1/4 1/4 1/4 1/2 10即生產(chǎn)計劃調(diào)整為 生產(chǎn) A 為 15/2, D 為 15/2,此時的利潤為 75;（6 分）3.此時從

8、 30 變?yōu)?50如Tkf25計算-v2門，知需要調(diào)整生產(chǎn)計劃，利用對偶單純形方法計算:-3/2251 1/2 3/2 1/2 0151 1/2 1/2 3/2 1100-750 -3/2 -3/2 -5/2 -1 0比值4204/3 2/3 5/3 0 1/3010-2/3 -1/3 -1/3 1 -2/3Z800 -5/3 -5/3 0 -4/3四、解：將該問題轉(zhuǎn)化為運輸問題進行求解；將工人看作是產(chǎn)地，每個產(chǎn)地的產(chǎn)量 為 1（只能完成一件事情），將任務(wù)看成銷地，每個銷地的銷量為1 （每件事情只能由一個工人來完成），將每個工人完成各種任務(wù)的所需的時間數(shù)看成各 產(chǎn)地和各銷地之間的距離或者單位運

9、輸成本，則原問題轉(zhuǎn)化為運輸問題。. .（4 分）總產(chǎn)量”為 5，總銷量”為 4,所以是產(chǎn)大于銷的問題。需虛擬一個銷地E，其銷量為 1,且 E 與各產(chǎn)地之間的距離為 0. . （6 分）用最小元素法和閉回路法求得的最優(yōu)表為ABCDE4/3所以計劃調(diào)整為生產(chǎn)A 為 20,此時的利潤為 80（8分）I00100II10III01IV00V00.（6 分）即，應(yīng)由 I 完成 C, II 完成 A, III 完成 B,完成所有任務(wù)的最少時間為 3+4+4+3= 14五、 解：把 5 臺設(shè)備分配給 3 各工廠可以以次分為三個階段（k= 1, 2, 3）。設(shè)每個階段初尚未分配出的設(shè)備數(shù)目為狀態(tài)變量，記為，顯

10、然；設(shè)相應(yīng)工廠分配的設(shè)備數(shù)為決策變量，記為，顯然；（2 分）則有狀態(tài)轉(zhuǎn)移方程：; . .（2 分）效應(yīng)函數(shù)為：4 也網(wǎng)）見題中表格；伽）訶血（心訃基本方程為：時-；.（2 分）逆序求解最優(yōu)值集與最優(yōu)決策集:0 000 000 100 01IV 完成 D，V 不參加；其最優(yōu)值即.（2 分）（可）=op仏（坷也）| 時，由于 ：，所以，顯然此時 為的單調(diào)增函數(shù)，1:有下列元素：（0） = 0.0,（0）- 0；（1） = 4,叭（1=1；4（2） = 6,冬（2） = 2;如11哲=3;（町=】2,UJ4） = 4;（5）-13,UJ5）- 5;（兩）=0忙也J+（電），一時，因此 為A(0) =

11、 max 0 + 0 = 0,0+ A|0+4maxi - max5+如）0+ (2)0 + 6/ (2) = max * 5+ KO)卜=max 5+4 I10+ (0)10 + 0o+o+ W)W)o+lllo+lll5+ A5+6/(3) = max=wax卜io+ A（】）叭4|n+他iiii + +o|o|(0+ z；(4)0+125+5 + 11 (4) = max * H) + /；(2)* = muxm10 + 6H+&111 + 41 1 + /；(o)1(0) = 0;吐M 1；3(2) = 2;2(3) 2;w3(4) = 1,2;二= 10.=1&*=1

12、4,(6 分)順序求最優(yōu)路線和最優(yōu)決策：最優(yōu)路線為：I 亠 T； L；或者因此，最優(yōu)的分配方案為 甲廠 0 臺，乙廠 2 臺，丙廠 3 臺；或者，甲廠 2 臺，乙廠 2 臺，丙廠 1 臺。六、哄W)(0 + B 11 15+ 5+12()+ f；(3)110+11-mux J11+ (2)111 + 611+ 4hi + 4】+(0)111*0卜二21、w.(5) - 2;化(5 _ mnx0+ (5)0+213+ (4)3 + 167+百7 + 14 = mux9+ f(2)9 + 1012+ r(i)12 + 513+ Z：(0)1】3 + j(=max2111(5) =0.2; 時,$ （殲 2 2 0 0 卩他（內(nèi)如+g g） ，