管理運籌學模擬試題三

1、管理運籌學模擬試題三一判斷下列說法是否正確，并對錯誤加以改正。（每題2分，合計10 分）1. 圖解法不能判斷 LP問題的基可行解是否退化。2. 若線性規(guī)劃問題和對偶問題都具有可行解，則該線性規(guī)劃問題一定具 有有限最優(yōu)解。3. 對偶單純形法只能求解 LP問題的對偶問題，不能求解LP問題。4. 產銷不平衡的運輸問題，沒有最優(yōu)解。5. 顧客相繼到達的間隔時間服從負指數(shù)分布，則輸入過程一定是泊松流。二填空題（每空2分，合計40分）1. 圖解法求解LP問題其可行域非空時， 若LP規(guī)劃問題存在最優(yōu)解，它一定在有界可行域的處得到。2. 大M法求解LP問題，加入人工變量，最終表中所有人工變量= 時,該LP問題

2、有可行解，并且達到最優(yōu)值。3. 對偶單純形法求解 LP問題，若所有的bi, b i，則得到該問題的最優(yōu)解。4. 線性規(guī)劃的約束條件個數(shù)與其對偶問題的 相等；而若線性規(guī)劃的約束條件是等式方程則對偶問題的 。5. 用于確定初始基的最小元素法，是優(yōu)先選取單位運價表中 開始確定供銷關系。6. 產銷不平衡的問題中， 若產大于銷，則增加一個假想的 ,將問題化為產銷平衡問題；反之，若銷大于產，則增加一個假象的 。7. 目標規(guī)劃中引進正、負偏差d+, d_, d+ x d_=。8. 匈牙利法常用于求解問題。9. 求最小支撐樹常用的兩個方法為 禾廿。10. 賦權有向圖中從 Vs到Vt權最小的路，稱為，該路徑的權

3、稱為從Vs到Vt。11. 排隊論中逗留時間= + 。12. 泊松分布的概率密度為, 期望EN(t)= ，方差 VarN(t)=三 按要求做出模型，不需計算(每題10分，合計20分)1 將下面的線性規(guī)劃問題化為標準型min z = 5x1 + x 2 + x 3 ,s.t. 3x1 + x 2 - x 3 < 7 ,xi - 2x2 + 4x 3 > 6,x 2 + 3x 3 = 10,x1 ,x 2 > 0 , x 3無符號限制.2. 試列出下述問題的目標規(guī)劃模型東風電視機廠生產I型和n型兩種電視，兩種電視都很暢銷，生產多少就 可以賣出多少。但兩種關鍵生產資源A和B受到限制。

4、如表30.1所示,表 30.1 :單位消耗、'資源產品In現(xiàn)有資源原材料A /公斤23100原材料B /公斤4280利潤（百兀/臺）45現(xiàn)原材料供應商 A要減少10公斤供應。另外，市場上I型電視供不應求, 需增加產量，由于I型電視的利潤較薄，故總利潤勢必下降。東風廠管理 部門經過認真分析后，對下階段生產經營提出了3個目標：a. 原材料A的每日用量控制在 90公斤以內；b. I型電視機的日產量在 15臺以上；c. 日利潤超過140 （百元）試列出該目標規(guī)劃模型。四 對偶問題計算（每題10分，合計10分） 已知線性規(guī)劃問題：Max z = 3xi + 2x2s.t. Xi+ 2x2 w 4

5、43xi + 2x2 w 14xi X2 W3x i, x 2 >0要求：1、寫出它的對偶問題；2、找出原問題和對偶問題的一個可行解；3、應用對偶理論證明原問題和對偶問題都存在最優(yōu)解。五 指派問題計算題 （每題10分，合計10分）某市計劃在今年內修建四座廠房，發(fā)電廠，化肥廠，機械廠，食品廠，分別記為B1, B2, B3, B4,該市有四個大的建筑隊 A1, A2, A3，A4，都可以承擔任務。所需費用見表 41.1所示。因希望盡早完工，故需把四個建筑 隊都動用起來，同時政府經費緊張，問怎樣指派才能使總費用最少？電用/萬元隊名B1B2B3B4A13452A28576A39645A45366

6、六 排隊論計算題（每題10分，合計10分）某理發(fā)店有兩個理發(fā)員， 顧客按強度為1/20人每分鐘的Poisson過程到達,服務時間服從指數(shù)分布且每服務一個顧客平均需要25分鐘，試求:（1）在系統(tǒng)內的顧客的平均數(shù)（2）在系統(tǒng)內排隊等候的顧客平均數(shù)（3）在系統(tǒng)內顧客排隊等候所花費時間的平均值參考答案一、判斷下列說法是否正確， 并對錯誤加以改正。（每題2分，合計10分）1. 正確。2. 錯誤。該線性規(guī)劃問題具有有限最優(yōu)解或無限最優(yōu)解 。3. 錯誤。跟單純形法一樣是求解LP問題的一種方法。4. 錯誤?？苫癁楫a銷平衡問題求得最優(yōu)解。5. 錯誤。不一定。其逆命題成立。二、填空題（每空2分，合計40分）1頂點

7、2 03bi > 04 i w 05變量數(shù)6變量無約束7最小運費8銷地9產地10 d +x d= 011指派問題12破圈法13避圈法14 Vs到Vt的最短路15距離16等待時間17服務時間18Pn(t)(t)net,t 0,n n!19t20 t0,1,2 ,L三、按要求做出模型，不需計算(每題10分，合計20分)1 .解：在3X1 + x 2 - x 3 w 7和X1 - 2x2 + 4x36中引入松弛變量下，X6, X7,并令X3= X4 X5,此處X4, xs> 0,可得其標準形如下：min z = 5x1+ x 2 + x 4 X5,s.t. 3x1+ x 2 - (x 4

8、 X5)+ x6= 7,X1- 2x 2 + 4(x 4 X5) X7= 6,x 2 + 3(x 4 X5)= 10,x1 ,x 2 ,x 3 ,x 7 > 0.這里通過變量代換X3 = X4 X5,將X3轉化為2個新引進的非負變量X4, X5 的差的形式，這點并不改變 X3的本質。2. 解 設 di表示原材料A的實際日用量未達到目標值的部分；di表示A的實際日用量超出目標值的部分。 d2和d2分別表示I型電 視機的日產量未達到和超出目標值的部分，d3和d3分別表示日利潤未達到和超出目標值的部分。minz dd2d3s.t2 X13x2didi=904x12x280Xid2d2154x1

9、5x2d3d3140Xi,X2,di ,di ,d2,d2,d3 ,d30四、對偶問題計算(每題10分，合計10分)解：1、它的對偶問題為：Min w = 4yi+14y2+3y3s.t.- yi+3y2+y332yi+2y2-y 3 > 2yi,y 2,y 3 >02 、容易看出，原問題存在可行解X=( 0,0 ),對偶問題存在可行解Y=(0,i,0 )3、根據(jù)對偶理論的強對偶性，因為原問題和對偶問題都存在可行解，則兩者都存在最優(yōu)解。五、指派問題計算題(每題i0分，合計i0分)解該問題是一個典型的指派問題，其系數(shù)矩陣為3452123085763021化簡為9645520153662033用匈牙利法求解得X11X24X33X421,其余 X