運籌學 復習練習題

《運籌學 復習練習題》由會員分享，可在線閱讀，更多相關《運籌學 復習練習題（5頁珍藏版）》請在裝配圖網上搜索。

1、串講練習題 1. 某公司生產的產品A，B，C和D都要經過下列工序：刨、立銑、鉆孔和裝配。已知每單位產品所需工時及本月四道工序可用生產時間如下表所示： 刨 立銑 鉆孔 裝配 A 0.5 2.0 0.5 3.0 B 1.0 1.0. 0.5 1.0. C 1.0 1.0 1.0 2.0 D 0.5 1.0 1.0 3.0 可用生產時間（小時） 1800 2800 3000 6000 又知四種產品對利潤貢獻及本月最少銷售需要單位如下： 產品 最少銷售需要單位 元/單位 A 100 2 B 600 3 C 500

2、 1 D 400 4 問該公司該如何安排生產使利潤收入為最大？（建立模型） 2．已知線性規(guī)劃問題 min z=2x1-x2+2x3 -x1+x2+x3=4 -x1+x2-x3≤6 x1≤0,x2≥0,x3無約束 （1） 寫出其對偶問題并化為標準型式。 （2） 用單純形法求出原問題的最優(yōu)解。 3．應用對偶問題性質，求出下面問題的最優(yōu)解。 4.某混合飼料場為某種動物配置飼料。已知此動物的生長速

3、度與飼料中的三種營養(yǎng)成分甲、乙、丙有關，且每頭動物每天需要營養(yǎng)甲85g、乙5g、丙15g?，F有五種飼料中都含有這三種營養(yǎng)成分，每種飼料每公斤所含營養(yǎng)成分及每種飼料成本如下表所示。求既滿足動物生長需要又使成本最低的飼料配方。 飼料 營養(yǎng)甲/g 營養(yǎng)乙/g 營養(yǎng)丙/g 成本/元 1 0.50 0.10 0.08 2 2 2.00 0.06 0.70 6 3 3.00 0.04 0.35 5 4 1.50 0.15 0.25 4 5 0.80 0.20 0.02 3 5.京成畜產品公司計劃在市區(qū)的東西南北四區(qū)建立銷售門市部，擬議中有1

4、0個位置可供選擇，考慮到各地區(qū)居民的生活水平及居民居住密集度，規(guī)定：在東區(qū)由三個點至多選擇兩個；在西區(qū)由兩個點中至少選一個；在南區(qū)由兩個點中至少選一個；在北區(qū)由三個點中至少選兩個。各點的設備投資及每年可獲利潤由于地點不同都是不一樣的，預測情況如下表。但投資總額不能超過720萬元，問應選擇哪幾個銷售點可使年利潤為最大。 投資額 100 120 150 80 70 90 80 140 160 180 利潤 36 40 50 22 20 30 25 48 58 61 6．已知下表為求解某線性規(guī)劃問題的最終單純形

5、表，表中為松弛變量，問題的約束條件為形式。 5/2 0 1/2 1 1/2 0 5/2 1 -1/2 0 -1/6 1/3 0 -4 0 -4 -2 （1） 寫出原線性規(guī)劃問題的數學模型； （2） 寫出原問題的對偶問題； （3） 直接由上表寫出對偶問題的最優(yōu)解。 7．已知線性規(guī)劃問題 max z=2x1+x2 5x2≤15 6x1+2x2≤24 x1+x2 ≤5

6、 x1,x2≥0 （1）寫出其對偶問題并化為標準型式； （2）用單純形法求出原問題的最優(yōu)解；唯一最優(yōu)解 （3）根據最終單純形表寫出其對偶問題的最優(yōu)解，三種資源的影子價格各為多少并說明其涵義； （4）若第三種資源增加3單位，問最優(yōu)解有何變化，資源的影子價格變?yōu)槎嗌佟? 8．運輸問題 課后習題3.3（1）（2） 9．指派問題 課后習題5.7 10．最小樹問題 課后習題10.4，10.5 11．最短路問題 課后習題10.6 10.7 12.最大流問題：10.12,10.13 部分答案： 2．解：（1）其對偶問題為： 化成標準型式為：

7、 （2）原問題的準標準型為： 用大M法求解 Cj -2 -1 2 -2 M 0 θ cB xB b x2 x4 x5 x6 x7 M 0 X6 x7 4 6 ［1］ 1 1 -1 1 0 1 1 -1 1 0 1 4 6 檢驗數σ -2-M –1-M 2-M M-2 0 0 -2 0 X7 4 2 1 1 1 -1 1 0 0

8、 0 -2 ［2］ -1 1 - 1 檢驗數σ 0 1 0 -4 M+2 0 -2 -2 X5 5 1 1 1 0 0 1/2 1/2 0 0 -1 1 -1/2 1/2 檢驗數σ 0 1 0 0 M 2 所以，原問題的最優(yōu)解為： 4．解：設為每千克混合飼料中所含5種飼料的重量 目標函數為： 約束條件有： 6．解：（1）首先設a、b、c表示對應原模型的價值系數，則由檢驗數的計算

9、公式，得 解此方程組，得：a=6，b=-2，c=10 再由單純形表與原模型標準型的特點，得 有這兩個關系式，可得：所以：愿問題的模型為： （2）由原問題的模型，得到其對偶問題模型： （3）由對偶理論，從原問題的最終單純形表中，直接得到對偶問題的最優(yōu)解： 7．（2）唯一最優(yōu)解 （3）其對偶問題的最優(yōu)解為： 第一種資源影子價格為0，第二種資源為1/4，第三種資源為1/2 其含義為：每增加一個單位的第一種資源，最優(yōu)值不會增加，每增加一個單位的第二種資源，最優(yōu)值增加1/4，每增加一個單位的第三種資源，最優(yōu)值會增加1/2。所以要想增加最優(yōu)值，可

10、以增加第二和第三種資源。 （4）第三種資源增加三個單位，= 新最優(yōu)解為： 13．有七個城市V1,V2,…，V7其公路網如下圖所示，弧旁數字為該段公路的長度，有一批貨物要從V1運到V7，試用迪克斯特拉算法或雙標號法求出走那條路距離最短。 用狄克斯特拉算法或雙標號法標號 （7分） 得到最短路路徑：V1—V3—V4—V5—V7（2分） 最短路路權：10（1分） 14.幾個工地之間建立一個局域網，由于條件不同，各工地間相連的費用不同，如下圖所示，求A,B,C,D,E間的最小連線方案。（10分） 工地A 工地B 工地C 工地D 工地E A 0 7 11 5 3 B 7 0 10 14 4 C 11 10 0 13 7 D 5 14 13 0 6 E 3 4 7 6 0 由對稱表格畫出連通圖（4分） 由破圈法或避圈法得到最小樹（4分），最小權和22（2分）