運籌學(第五版)習題答案

《運籌學(第五版)習題答案》由會員分享，可在線閱讀，更多相關《運籌學(第五版)習題答案（63頁珍藏版）》請在裝配圖網上搜索。

1、運籌學習題答案 第一章（39頁） 1.1用圖解法求解下列線性規(guī)劃問題，并指出問題是具有唯一最優(yōu)解、無窮多最優(yōu)解、無界解還是無可行解。 （1）max 5+1050 +1 4 ，0 （2）min z=+1.5 +33 +2 ，0 （3）max z=2+2 --1 -0.5+2 ，0 （4）max z=+ -0 3--3 ，0 解： （1）（圖略）有唯一可行解，max z=14 （2）（圖略）有唯一可行解，min z=9/4 （3）（圖略）無界解 （4）（圖略）無可行解 1.2將下列線性規(guī)劃問題變換成標準型，并列出初始單純形表。 （1）min z

2、=-3+4-2+5 4-+2-=-2 ++3-14 -2+3-+22 ，，0，無約束 （2）max 0 (i=1…n; k=1,…,m) （1）解：設z=-,=-, ,0 標準型： Max =3-4+2-5(-)+0+0-M-M s. t . -4+-2+-+=2 ++3-++=14 -2+3-+2-2-+=2 ,,,,,,,,0 初始單純形表: 3 -4 2 -5 5 0 0 -M -M b -M 2 -4 1 -2 1 -1 0 0 0 1 2

3、 0 14 1 1 3 -1 1 1 0 0 0 14 -M 2 -2 [3] -1 2 -2 0 -1 1 0 2/3 - 4M 3-6M 4M-4 2-3M 3M-5 5-3M 0 -M 0 0 (2)解：加入人工變量，，，…，得： Max s=(1/)-M-M-…..-M s.t. (i=1,2,3…,n) 0, 0, (i=1,2,3…n; k=1,2….,m) M是任意正整數(shù) 初始單純形表： -M -M … -M … … …

4、b … … … … -M 1 1 0 … 0 1 1 … … 0 0 … 0 -M 1 0 1 … 0 0 … … 0 0 … 0 … … … … … … … … … … … … … … … … -M 1 0 0 … 1 0 0 … 0 … 1 1 … 1 -s nM 0 0 … 0 … … … 1.3在下面的線性規(guī)劃問題中找出滿足約束條件的所有

5、基解。指出哪些是基可行解，并代入目標函數(shù)，確定最優(yōu)解。 （1）max z=2+3+4+7 2+3--4=8 -2+6-7=-3 ,,,0 (2)max z=5-2+3-6 +2+3+4=7 2+++2=3 0 （1）解： 系數(shù)矩陣A是： 令A=(，，，) 與線形無關，以（，）為基，，為基變量。 有 2+3=8++4 -2=-3-6+7 令非基變量，=0 解得：=1；=2 基解=（1，2，0，0為可行解 =8 同理，以（，）為基，基解=（45/13，0，-14/13，0是非可行解； 以（，）為基，基解=（34/

6、5，0，0，7/5是可行解，=117/5； 以（，）為基，基解=（0，45/16，7/16，0是可行解，=163/16； 以（，）為基，基解=（0，68/29，0，-7/29是非可行解； 以（，）為基，基解=（0，0，-68/31，-45/31是非可行解； 最大值為=117/5；最優(yōu)解=（34/5，0，0，7/5。 （2）解： 系數(shù)矩陣A是： 令A=(，，，) ，線性無關，以（，）為基，有： +2=7-3-4 2+=3--2 令 ，=0得 =-1/3，=11/3 基解=（-1/3，11/3，0，0為非可行解； 同理，以（，）為基，基解=（2/5，0，11/5，

7、0是可行解=43/5； 以（，）為基，基解=（-1/3，0，0，11/6是非可行解； 以（，）為基，基解=（0，2，1，0是可行解，=-1； 以（，）為基，基解=（0，0，1，1是=-3； 最大值為=43/5；最優(yōu)解為=（2/5，0，11/5，0。 1.4分別用圖解法和單純形法求解下列線性規(guī)劃問題，并指出單純形迭代每一步相當于圖形的哪一點。 （1）max z=2+ 3+515 6+224 ，0 （2）max z=2+5 4 212 3+218 ，0 解：（圖略） （1）max z=33/4 最優(yōu)解是(15/4,3/4) 單純形法：

8、 標準型是max z=2++0+0 s.t. 3+5+=15 6+2+=24 ,,,0 單純形表計算： 2 1 0 0 b 0 15 3 5 1 0 5 0 24 [6] 2 0 1 4 -z 0 2 1 0 0 0 3 0 [4] 1 -1/2 3/4 2 4 1 1/3 0 1/6 12 -z -8 0 1/3 0 -1/3 1 3/4 0 1 1/4 -1/8 2 15/4 1 0 -1/

9、12 5/24 -z -33/4 0 0 -1/12 -7/24 解為：（15/4，3/4，0，0 Max z=33/4 迭代第一步表示原點；第二步代表C點（4，0，3，0； 第三步代表B點（15/4，3/4，0，0 。 （2）解：（圖略） Max z=34 此時坐標點為（2，6） 單純形法，標準型是： Max z=2+5+0+0+0 s.t. +=4 2+=12 3+2+=18 ,,,,0 (表略) 最優(yōu)解 X=（2，6，2，0，0 Max z=34 迭代第一步得=（0，0，4，12，18表示

10、原點，迭代第二步得=（0，6，4，0，6，第三步迭代得到最優(yōu)解的點。 1.5以1.4題（1）為例，具體說明當目標函數(shù)中變量的系數(shù)怎樣變動時，滿足約束條件的可行域的每一個頂點，都可能使得目標函數(shù)值達到最優(yōu)。 解：目標函數(shù)：max z=+ (1)當0時 =-（/）+z/ 其中，k=-/ =-3/5，=-3 l k 時， ，同號。 當0時，目標函數(shù)在C點有最大值 當0時，目標函數(shù)在原點最大值。 l k時，，同號。 當0， 目標函數(shù)在B點有最大值； 當0，目標函數(shù)在原點最大值。 l k 0時，， 同號。 當0時，目標函數(shù)在A點有最大值 當0時，目標函數(shù)

11、在原點最大值。 l k 0時， ，異號。 當0， 0時，目標函數(shù)在A點有最大值； 當0， 0時，目標函數(shù)在C點最大值。 l k= 時，， 同號 當0時，目標函數(shù)在AB線斷上任一點有最大值 當0，目標函數(shù)在原點最大值。 l k= 時，， 同號。 當0時，目標函數(shù)在BC線斷上任一點有最大值 當0時，目標函數(shù)在原點最大值。 l k=0時，=0 當0時，目標函數(shù)在A點有最大值 當0，目標函數(shù)在OC線斷上任一點有最大值 （2）當=0時，max z= l 0時，目標函數(shù)在C點有最大值 l 0時，目標函數(shù)在OA線斷上任一點有最大值 l =0時，在可行域任何一點取最大值。

12、 1.6分別用單純形法中的大M法和兩階段法求解下列線性問題，并指出屬于哪類解。 （1）max z=2+3-5 ++15 2-5+24 ，0 （2）min z=2+3+ +4+28 3+26 ，，0 （3）max z=10+15+12 5+3+9 -5+6+1515 2++5 ，，0 （4）max z=2-+2 ++6 -2+2 2-0 ，，0 解：（1）解法一：大M法 化為標準型： Max z=2+3-5-M+0-M s.t. +++=7 2-5+-+=10 ,,,,,0 M是任意大整數(shù)。 單純形表： 2 3 -5 -M 0

13、 -M b -M 7 1 1 1 1 0 0 7 -M 10 [2] -5 1 0 -1 1 5 -z 17M 3M+2 3-4M 2M-5 0 -M 0 -M 2 0 [7/2] 1/2 1 1/2 -1/2 4/7 2 5 1 -5/2 1/2 0 -1/2 1/2 - -z 2M-10 0 (7/2)M+8 0.5M-6 0 0.5M+1 -1.5M-1 3 4/7 0 1 1/7 2/7 1/7

14、-1/7 2 45/7 1 0 6/7 5/7 -1/7 1/7 -z -102/7 0 0 -50/7 -M-16/7 -1/7 -M+1/7 最優(yōu)解是： X=（45/7，4/7，0，0，0 目標函數(shù)最優(yōu)值 max z=102/7 有唯一最優(yōu)解。 解法二： 第一階段數(shù)學模型為 min w= + S.t. ++ + =7 2 -5 + - + =10 ,,,，,0 （單純形表略） 最優(yōu)解 X=（45/7，4/7，0，0，0 目標函數(shù)最優(yōu)值 min w=0 第二階段單純形表為： 2 3 -

15、5 0 b 3 4/7 0 1 1/7 1/7 2 45/7 1 0 6/7 -1/7 -z -102/7 0 0 -50/7 -1/7 最優(yōu)解是 X=（45/7，4/7，0，0，0 Max z=102/7 （2）解法一：大M法 =-z 有max =-min （-）=-min z 化成標準形： Max =-2-3-+0+0-M-M S.T. +4+2-+=4 3+2-+=6 ,,,，,，0 （單純性表計算略） 線性規(guī)劃最優(yōu)解X=（4/5，9/5，0，0，

16、0 ，0 目標函數(shù)最優(yōu)值 min z=7 非基變量的檢驗數(shù)=0，所以有無窮多最優(yōu)解。 兩階段法： 第一階段最優(yōu)解X=（4/5，9/5，0，0，0，0 是基本可行解,min w=0 第二階段最優(yōu)解（4/5，9/5，0，0，0，0 min z=7 非基變量的檢驗數(shù)=0，所以有無窮多最優(yōu)解。 （3）解：大M法 加入人工變量，化成標準型： Max z=10 +15 +12 +0 +0 +0 -M s.t. 5 +3 + + =9 -5 +6 +15 + =15 2 + + - + =5 ,,,，,，0 單純形表計算略 當所有非基

17、變量為負數(shù)，人工變量=0.5，所以原問題無可行解。 兩階段法（略） （4）解法一：大M法 單純形法，（表略）非基變量的檢驗數(shù)大于零，此線性規(guī)劃問題有無界解。 兩階段法略 1.7求下述線性規(guī)劃問題目標函數(shù)z的上界和下界； Max z=+ 其中：，，，，，，， 解： l 求Z的上界 Max z=3+6 s.t. -+212 2+414 ，0 加入松弛變量，化成標準型，用單純形法解的，最優(yōu)解 X=（0，7/2，5，0 目標函數(shù)上界為z=21 存在非基變量檢驗數(shù)等于零，所以有無窮多最優(yōu)解。 l 求z的下界 線性規(guī)劃模型： Max Z= +4

18、 s.t. 3+58 4+610 ，0 加入松弛變量，化成標準型，解得： 最優(yōu)解為 X=（0，8/5，0，1/5 目標函數(shù)下界是z=32/5 1.8表1-6是某求極大化線性規(guī)劃問題計算得到的單純形表。表中無人工變量，，，，d，，為待定常數(shù)，試說明這些常數(shù)分別取何值時，以下結論成立。 （1）表中解為唯一最優(yōu)解；（2）表中解為最優(yōu)解，但存在無窮多最優(yōu)解；（3）該線性規(guī)劃問題具有無界解；（4）表中解非最優(yōu)，對解改進，換入變量為，換出變量為。 基b d 4 1 0 0 2 -1 -3 0 1 -1 0 3

19、 -5 0 0 -4 1 0 0 -3 0 解： （1）有唯一最優(yōu)解時，d0，0，0 （2）存在無窮多最優(yōu)解時，d0，0，=0或d0，=0，0. （3）有無界解時，d0，0，0且 （4）此時，有d0，0并且，，3/d/4 1.9某晝夜服務的公交線路每天個時間段內所需司機和乘務員人數(shù)如下： 班次 時間 所需人數(shù) 1 6點到10點 60 2 10點到14點 70 3 14點到18點 60 4 18點到22點 50 5 22點到2點 20 6 2點到6點 30 設司機和乘務人員分別在各時間區(qū)段一開始時上

20、班，并連續(xù)上班8小時，問該公交線路至少配備多少司機和乘務人員。列出線型規(guī)劃模型。 解 ： 設（k=1，2，3，4，5，6）為個司機和乘務人員第k班次開始上班。 建立模型： Min z=+++++ s.t. +60 +70 +60 +50 +20 +30 ,,,,, 0 1.10某糖果公司廠用原料A、B、C加工成三種不同牌號的糖果甲乙丙，已知各種糖果中ABC含量，原料成本，各種原料的每月限制用量，三種牌號糖果的單位加工費用及售價如表所示： 原料 甲 乙 丙 原料成本（元/千克） 每月限制用量（千克） A 60%

21、 15% 2 2000 B 1.5 2500 C 20% 60% 50% 1 1200 加工費 0.5 0.4 0.3 售價 3.4 2.85 2.25 問該廠每月應當生產這三種牌號糖果各多少千克，使得獲利最大？建立數(shù)學模型。 解: 解：設，，是甲糖果中的A，B，C成分，，，是乙糖果的A，B，C成分，，，是丙糖果的A，B，C成分。 線性規(guī)劃模型： Max z=0.9+1.4+1.9+0.45+0.95+1.45-0.05+0.45+0.95 s.t. -0.4+0.6+0.60 -0.2-0.2+

22、0.80 -0.85+0.15+0.150 -0.6-0.6+0.40 -0.7-0.5+0.50 ++2000 ++2500 ++1200 ,,,,,,,, 0 1.11某廠生產三種產品I、、III。每種產品經過AB兩道加工程序，該廠有兩種設備能完成A工序，他們以,表示；有三種設備完成B工序，分別為，，；產品I可以在AB任何一種設備上加工，產品可以在任何規(guī)格的A設備上加工，但完成B工序時，只能在設備上加工；產品III只能在，上加工。已知條件如下表，要求安排最優(yōu)生產計劃，使該廠利潤最大化。 設備 產品 設備有效臺時 滿

23、負荷時的設備費用 I II III 5 10 6000 300 7 9 12 10000 321 6 8 4000 250 4 11 7000 783 7 4000 200 原料費 0.25 0.35 0.5 單價 1.25 2.00 2.8 解： 產品1，設,完成A工序的產品，件；B工序時，,，完成B工序的，，件，產品，設,完成A工序的產品，件；B工序時，完成B的產品為件；產品111，完成A工序的件，完成B工序的件； + = + + + = 建立數(shù)學模型：

24、 Max z=(1.25-0.25)*( + )+(2-0.35)*( + )+(2.8-0.5) -(5 +10 )300/6000-(7 +9 +12 )321/10000-(6 +8 )250/4000-(4 +11 )783/7000-7 *200/4000 s.t 5 +10 6000 7 +9 +12 10000 6 +8 4000 4 +11 7000 7 4000 + = + + + = ,,,,,,,, 0 最優(yōu)解為X=（1200，230，0，859，571，0，500，500，324 最優(yōu)值1147. 試題： 1. （2005年華

25、南理工大學）設某種動物每天至少需要700克蛋白質、30克礦物質、100毫 克維生素?，F(xiàn)有5種飼料可供選擇，每種飼料每公斤營養(yǎng)成分的含量及單價如下表所示： 試建立既滿足動物生長需要，又使費用最省的選用飼料方案的線性規(guī)劃模型。 表 1—1 飼料 蛋白質（克） 礦物質（克） 維生素（毫克） 價格（元/公斤） 1 3 1 0.5 0.2 2 2 0.5 1 0.7 3 1 0.2 0.2 0.4 4 6 2 2 0.3 5 18 0.5 0.8 0.8 解題分析：這是一道較簡單的數(shù)學規(guī)劃模型問題，根據題意寫出約束即可。 解題過程：

26、 第二章（67頁） 2.1用改進單純形法求解以下線性規(guī)劃問題。 （1）Max z=6-2+3 2-+32 +44 ，，0 （2）min z=2+ 3+=3 4+36 +23 ,0 解： （1） 先化成標準型： Max z=6-2+3+0+0 s.t. 2-+2+=2 +4+=4 ,,,, 0 令=（，）= =（,,=(0,0) =(,,)= , =（，， =(6,-2,3)，=,= 非基變量的檢驗數(shù) =-==(6,-2,3) 因為的檢驗數(shù)等于6，是最大值，所以，為換入變量， =；= 由規(guī)則得： =1 為換出變量。

27、 =(，)=,=（,，=(6,0). =(,,), =（，， =(0，-2，3)，=,= 非基變量的檢驗數(shù) =（-3，1，-3） 因為的檢驗數(shù)為1，是正的最大數(shù)。所以為換入變量； = 由規(guī)則得： =6 所以是換出變量。 =(，)=,=（,，=(6,-2). =(,，), =（，， =(0，0，3)，=,= 非基變量的檢驗數(shù) =（-2，-2，-9） 非基變量的檢驗數(shù)均為負數(shù)，愿問題已達最優(yōu)解。 最優(yōu)解X= 即：X=（4,6,0 目標函數(shù)最優(yōu)值 max z=12 （2） 解 ： Min z=2++0+M+M+0 S.T. 3++=3

28、 4+3-+=6 +2+=3 ,,,,, 0 M是任意大的正數(shù)。 （非基變量檢驗數(shù)計算省略） 原問題最優(yōu)解是X=（0.6，1.2，0） 目標函數(shù)最優(yōu)值： z=12/5 2.2已知某線性規(guī)劃問題，用單純形法計算得到的中間某兩步的加算表見表，試將空白處數(shù)字填上。 3 5 4 0 0 0 b 5 8/3 2/3 1 0 1/3 0 0 0 14/3 -4/3 0 5 -2/3 1 0 0 20/3 5/3 0 4 -2/3 0 1 - -1/3 0 4 -5/3

29、 0 0 . . . 15/41 8/41 -10/41 -6/41 5/41 4/41 -2/41 -12/41 15/41 - 解： 3 5 4 0 0 0 b 5 8/3 0 14/3 0 20/3 - . . . 5 80/41 0 1 0 15/41

30、 4 50/41 0 0 1 -6/41 3 44/41 1 0 0 -2/41 - 0 0 0 -45/41 2.3寫出下列線性規(guī)劃問題的對偶問題。 （1）min z= 2 +2 +4 2 +3 +5 2 3 + +7 3 +4 +6 5 ,, 0 （1） 解：對偶問題是： Max w=2-3-5 s.t. 2-3-2 3--42 5-7-64 ,,0 (2)max z= +2+3 +4 -+--3=5 6+7+3-58 12-9-9+920 ,0; 0;無

31、約束 解： 對偶問題： Min w=5+8+20 S.t. -+6+121 +7-92 -+3-93 -3-5+9=4 無約束，0；0 （3）min z= i=1,…,m j=1,…,n 0 解： 對偶問題: max w=+ s.t. + , 無約束 i=1,2,….m; j=1,2,….n (4) Max z= , i=1,…., , i= 0,當j=1，….， 無約束，當j= 解： Min w= s.t. j=1,2,3… j=+1, +2,….n 0 i=1,2….

32、 無約束， i=+1, +2….m 2.4判斷下列說法是否正確，并說明為什么. (1)如線性規(guī)劃問題的原文題存在可行解，則其對偶問題也一定存在可行解。 （2）如線性規(guī)劃的對偶問題無可行解，則原問題也一定無可行解。 （3）如果線性規(guī)劃問題的原問題和對偶問題都具有可行解，則該線性規(guī)劃問題一定有有限最優(yōu)解。 (1)錯誤，原問題有可行解，對偶問題可能存在可行解，也可能不存在； （2）錯誤，對偶問題沒有可行解，原問題可能有可行解也可能有無界解； （3）錯誤，原問題和對偶問題都有可行解，則可能有有限最優(yōu)解也可能有無界解； 2.5設線性規(guī)劃問題1是： Max = ，i=1，2…

33、，m （）是其對偶問題的最優(yōu)解。 又設線性規(guī)劃問題2是 Max + ，i=1，2…，m 其中是給定的常數(shù)，求證： + 解： 證明：把原問題用矩陣表示： Max =CX s.t. AXb X0 b=（,... 設 可行解為,對偶問題的最優(yōu)解=（，… ）已知。 Max =CX s.t. AXb+k X0 k=（,... 設可行解為，對偶問題最優(yōu)解是,對偶問題是， Min w=Y(b+k) S.t. YA C Y 0 因為是最優(yōu)解，所以（b+k）（b+k） 是目標函數(shù)的可行解，Ab+k ；A（b+k）b+

34、Yk 原問題和對偶問題的最優(yōu)函數(shù)值相等，所以不等式成立，證畢。 2.6已知線性規(guī)劃問題 Max z= = 用單純形法求解，得到最終單純形表如表所示，要求： （1） 求，，，，，，，的值； （2） 求的值； 3/2 1 0 1 1/2 -1/2 2 1/2 1 0 -1 2 -3 0 0 0 -4 解： （1）初始單純形表的增廣矩陣是： = 最終單純形表的增廣矩陣為 = 是作初等變換得來的，將作初等變換，使得的第四列和第五列的矩陣成為的單位矩陣。有： =9/2； =1； =4；

35、 =5/2； =1； =2； =9； =5 由檢驗計算得： =-3； ==0 2.7已知線性規(guī)劃問題 Max z=2++5+6 s.t. 2++8 2+2++212 0，j=1,…4 對偶變量，，其對偶問題的最優(yōu)解是=4，，試應用對偶問題的性質，求原問題的最優(yōu)解。 解： 對偶問題是： Min w=8+12 s.t. 2+22 21 +5 +26 ，0 互補松弛性可知，如，是原問題和對偶問題的可行解，那么，=0和 =0，當且僅當，是最優(yōu)解。 設 X,Y是原問題和對偶問題的可行解，=（，，，） 有： Y=0; 且 X=0

36、==0，原問題約束條件取等號，=4；=4 最優(yōu)解X=（0，0，4，4 目標函數(shù)最優(yōu)值為44。 2.8試用對偶單純形法求解下列線性規(guī)劃問題。 （1）min z=+ 2+4 +77 ,0 (2) min z=3+2++4 2+4+5+ 0 3- +7-2 2 5+2++10 15 ,, , 0 解： （1） 取w=-z，標準形式： Max w=--+0+0 s.t. -2-+=-4 --7+=-7 ，，，0 單純形法求解（略）： 最優(yōu)解： X=（21/13，10/13，0，0 目標函數(shù)最優(yōu)值為31/13。

37、 （2）令：w=-z，轉化為標準形式： Max w=-3-2--4+0+0+0 s.t. -2-4-5-+=0 -3+-7+2+=-2 -5-2--6+=-15 ，，，，，，0 單純形法略 原問題最優(yōu)解： X=（3，0，0，0，6，7，0 目標函數(shù)最優(yōu)值為9。 2.9現(xiàn)有線性規(guī)劃問題 max z=- 5+5+13 - ++3 20 12 +4+10 90 ，， 0 先用單純形法求出最優(yōu)解，然后分析在下列各種條件下，最優(yōu)解分別有什么變化？ （1） 約束條件1的右端常數(shù)20變?yōu)?0 （2） 約束條件2的右端常數(shù)90變?yōu)?0 （3） 目標函數(shù)中的系數(shù)變

38、為8 （4） 的系數(shù)向量變?yōu)? （5） 增加一個約束條件2+3+550 （6） 將約束條件2變?yōu)?0+5+10100 解： 把原問題化成標準型的： Max z=-5 +5 +13 +0 +0 s.t - + +3 + =20 12 +4 +10 + =90 ，，，，0 單純形法解得： 最優(yōu)解： X=（0，20，0，0，10 目標函數(shù)最優(yōu)值為100。 非基變量的檢驗數(shù)等于0，原線性問題有無窮多最優(yōu)解。 （1）約束條件的右端常數(shù)變?yōu)?0 有 因此 單純形法解得： 最優(yōu)解： X=（0，0，9，3，0 目標函數(shù)最優(yōu)值為117。 （2）約束條件右

39、端常數(shù)變?yōu)?0 有 因此 單純形法解得，最優(yōu)解： X=（0，5，5，0，0 目標函數(shù)最優(yōu)值為90。 （3）的系數(shù)變成8，是非基變量，檢驗數(shù)小于0，所以最優(yōu)解不變。 （4）的系數(shù)向量變?yōu)? 是非基變量，檢驗數(shù)等于-5，所以最優(yōu)解不變。 （5）解：加入約束條件 用對偶單純形表計算得： X=（0，25/2，5/2，0，15，0 目標函數(shù)最優(yōu)值為95。 （6）改變約束條件，沒有變化， 線性規(guī)劃問題的最優(yōu)解不變。 2.10已知某工廠計劃生產I,II,III三種產品，各產品在ABC設備上加工，數(shù)據如下表， 設備代號 I II III 每月設備 有效臺

40、時 A 8 2 10 300 B 10 5 8 400 C 2 13 10 420 單位產品利潤/千元 3 2 2.9 （1）如何充分發(fā)揮設備能力，使生產盈利最大？ （2）如果為了增加產量，可借用其他工廠的設備B，每月可借用60臺時，租金為1.8萬元，問借用是否合算？ （3）若另有兩種新產品IV,V，其中IV為10臺時，單位產品利潤2.1千元；新產品V需用設備A為4臺時，B為4臺時，C為12臺時，單位產品盈利1.87千元。如A,B,C設備臺時不增加，分別回答這兩種新產品投產在經濟上是否劃算？ （4）對產品工藝重新進行設計，改進結構，改進后生產每

41、件產品I，需要設備A為9臺時，設備B為12臺時，設備C為4臺時，單位產品利潤4.5千元，問這對原計劃有何影響？ 解： （1）設：產品三種產品的產量分別為，，，，建立數(shù)學模型： Max z=3+2+2.9 s.t. 8+2+10300 10+5+8400 2+13+10420 ,,0 把上述問題化為標準型，用單純形法解得： 最優(yōu)解： X=（338/15，116/5，22/3，0，0，0 目標函數(shù)最優(yōu)值為2029/15。 （2） 設備B的影子價格為4/15千元/臺時，借用設備的租金為0.3千元每臺時。 所以，借用B設備不合算。 （3） 設備,V生產的產量為，，

42、系數(shù)向量分別為： 檢驗數(shù)=-0.06，所以生產不合算， =37/300，生產V合算。 單純形法計算得： 最優(yōu)解： X=（107/4，31/2，0，0，0，0，55/4 目標函數(shù)最優(yōu)值為10957/80。 （4）改進后,檢驗數(shù)=253/300，大于零。 所以，改進技術可以帶來更好的效益。 2.11分析下列參數(shù)規(guī)劃中當t變化時最優(yōu)解的變化情況。 （1）Max =(3-6t) +(2-2t) +(5-5t) (t0) s.t. +2+ 430 3+2 460 +4 420 ，，0 （2）Max =(7+2t)+(12+t) +(10-t) (t

43、0) s.t. ++ 20 2+2+ 30 ，，0 （3）Max =2+ (0 t 25) s.t. 10+2t + 25-t 10+2t ，0 （4）Max =21+12+18+15 (0 t 59) s.t. 6+3+6+3 30+t 6-3+12+6 78-t 9+3-6+9 135-2t ，，，0 解： （1）化成標準形式： Max =(3-6t) +(2-2t) +(5-5t) +0+0+0 (t0) s.t. +2++=430 3+2+=460 +4+=420 ，，，，, 0 令t=0，用單純形表計算，

44、 3-6t 2-2t 5-5t 0 0 0 B 2-2t 100 -1/4 1 0 0.5 -1/4 0 - 5-5t 230 3/2 0 1 0 1/2 0 460 0 20 2 0 0 -2 [1] 1 20 -z 1350t -1350 t-4 0 0 t-1 2t-2 0 t增大，t大于1，首先出現(xiàn)，大于0，所以當0t1時有最優(yōu)解。 X=（0，100，230，0，0，20 目標函數(shù)最優(yōu)值為1350（t-1） （0t1）。 t=1是第一

45、臨界點。 t大于1時，是換出變量。 t大于1，最優(yōu)解是：X=（0，0， 0，430，460，420 目標函數(shù)最優(yōu)值為 Max =0， （t大于1） （2） 化成標準型，然后令t=0，單純形法解得： t開始增大時，當t大于8/3時，首先出現(xiàn)大于0，所以0t8/3，得最優(yōu)解。 目標函數(shù)最優(yōu)值Max =220，（0t8/3） 所以，t=8/3為第一臨界點。 當8/35，首先大于0，8/3

46、）。 所以，t=5為第二臨界點。 當t>5時，是換入變量，為換出變量，單純性法計算， 當t繼續(xù)增大，所有檢驗數(shù)都非正，所以當t>5，最優(yōu)解： X=（15，0，0，5 目標函數(shù)最優(yōu)值為105+30t， t〉0 (3)化成標準型，令t=0,用單純形法計算得： 當t開始增大，t大于5時，首先出現(xiàn)小于0，當0t5，最優(yōu)解為： X=（10+2t，0，10+2t，5-t，0 目標函數(shù)最優(yōu)值為6t+30 ，（0t5）。 所以t=5是第一臨界點。 當t大于5時，是換出變量，是換入變量。用對偶單純形法計算， 當t大于5時，最優(yōu)解為： X=（10+2t，15+t，0，0，t-5

47、目標函數(shù)最優(yōu)值為35+5t。 （4）解： 先化為標準型，令t=0，用單純形法計算，得： 當t開始增大，當t大于6時，首先出現(xiàn)小于0，當0t6，有最優(yōu)解： X=（0，0，0，10+t/3，0，18-3t，45-5t 目標函數(shù)最優(yōu)值為150+5t （0t6）。 當t大于6時，首先出現(xiàn)小于0，是換出變量，是換入變量，使用單純形法計算得：t繼續(xù)增大，當t大于11時，首先小于零，是換出變量，為換入變量，對偶單純形法迭代得： 當 t≤59，有最優(yōu)解： X=（0，t/3-2，t/8-11/8，59/4-t/4，0，0，0 目標函數(shù)最優(yōu)值為5t/2+345/2 ，（11

48、 試題： 1. （2006年西北工業(yè)大學）已知線性規(guī)劃： （1） 用單純形法求解該線性規(guī)劃問題的最優(yōu)解和最優(yōu)值； （2） 寫出線性規(guī)劃的對偶問題； （3） 求解對偶問題的最優(yōu)解和最優(yōu)值。 解題分析：本題考察了線性規(guī)劃與對偶問題的知識，要求讀者熟知對偶理論。 解題過程： ，有無窮多解。 對偶問題為： 2. （2005年東南大學）寫出如下線性規(guī)劃問題的對偶問題： 無限制 并利用弱對偶性說明的最大值不大于1。 解題過程：原問題的對偶問題為： 由于（0，1，0）是上述對偶問題的可行解，由弱對偶性可知，對原問題的任一可行解 都有

49、 而，所以的最大值不大于1。 第三章（86頁） 3.1判斷表中給出的調運方案能否作為用表上作業(yè)法求解時的最初解？為什么？ 表3—1 銷地產地 1 2 3 4 產量 1 0 15 15 2 15 10 25 3 5 5 銷量 5 15 15 10 表3—2 銷地 產地 1 2 3 4 5 產量 1 150 250 400 2 200 300 500 3 250 50 300 4 90 210 30

50、0 5 80 20 100 銷量 240 410 550 330 70 解： 表3—1中，有5個數(shù)字格，作為初始解，應該有m+n-1=3+4-1=6個數(shù)字格，所以表3-1的調運方案不能作為用表上作業(yè)法求解時的初始解。 表3-2中，有10個數(shù)字格，而作為初始解，應該有m+n-1=9個數(shù)字格，所以表3-2的調運方案不能作為表上作業(yè)法的初始解。 3.2 表3-3和表3-4中分別給出兩個運輸問題的產銷平衡表和單位運價表，試用伏格爾法直接給出近似最優(yōu)解。 表3-3 銷地 產地 1 2 3 產量 1 5 1 8 12

51、 2 2 4 1 14 3 3 6 7 4 銷量 9 10 11 表3-4 銷地 產地 1 2 3 4 5 產量 1 10 2 3 15 9 25 2 5 20 15 2 4 30 3 15 5 14 7 15 20 4 20 15 13 M 8 30 銷量 20 20 30 10 25 解： （1）在表3-3中分別計算出各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下列。得到： 銷地 產地 1 2 3 行差額

52、1 5 1 8 4 2 2 4 1 1 3 3 6 7 3 列差額 1 3 6 從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，上表中，第三列是最大差額列，此列中最小元素為1，由此可以確定產地2的產品應先供應給銷售地3，得到下表： 銷地 產地 1 2 3 產量 1 11 12 2 14 3 4 銷量 9 10 11 同時將運價表第三列數(shù)字劃去，得 銷地 產地 1 2 產量 1 5 1 12 2 2 4 14

53、3 3 6 4 銷量 9 10 對上表中的元素，計算各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下列，重復上面的步驟，直到求出初始解，最終結果是： 銷地 產地 1 2 3 產量 1 2 10 12 2 3 11 14 3 4 4 銷量 9 10 11 （2）3-4分別計算出各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下列。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素。（方法同3-3相同） 最終得出原問題的初始解： 銷地 產地

54、1 2 3 4 5 產量 1 25 2 20 30 3 20 4 30 銷量 20 20 30 10 25 3.3用表上作業(yè)法求給出運輸問題的最優(yōu)解（M是任意大正數(shù)） （1） 銷地 產地 甲 乙 丙 丁 產量 1 3 7 6 4 5 2 2 4 3 2 2 3 4 3 8 5 3 銷量 3 3 2 2 解： （1）計算出各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下列。

55、 從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，丙列中的最小元素為3，由此可以確定產地2的產品應先供應丙的需要，而產地2的產量等于丙地的銷量，故在（2，丙）處填入0，同時將運價表中的丙列和第二行的數(shù)字劃去，得到： 銷地 產地 甲 乙 丙 丁 產量 1 3 7 4 5 2 2 3 4 3 5 3 銷量 3 3 2 對上表中的元素分別計算各行和各列的次最小運費和最小運費的差額，填入該標的最右列和最下行，重復步驟，直到求出初始解為止。得到下表： 銷地 產地 甲 乙 丙

56、丁 產量 1 3 2 5 2 2 0 2 3 0 3 3 銷量 3 3 2 2 使用位勢法進行檢驗： 上表中，數(shù)字格處填入單位運價并增加一行一列，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令+=（i，jB，B為基，下同）來確定和，得到下表： 銷地 產地 甲 乙 丙 丁 1 3 4 0 2 3 2 -2 3 4 3 1 3 2 5 4 由=-（+）（i，j為非基，下同）計算所有空格的檢驗數(shù)，并在每個格的右上角填入單位運價

57、，得到下表 銷地 產地 甲 乙 丙 丁 1 3 0 7 5 6 1 4 0 0 2 2 1 4 4 3 0 2 0 -2 3 4 0 3 0 8 2 5 0 1 3 2 5 4 由上表可以看出，所有的非基變量檢驗數(shù)≥0，此問題達到最優(yōu)解。 又因為=0，此問題有無窮多最優(yōu)解。 總運費min z=3*3+3*3+2*3+2*4=32 （2） 銷地 產地 甲 乙 丙 丁 產量 1 10 6 7 12 4 2 16 10 5 9 9 3

58、 5 4 10 10 4 銷量 5 2 4 6 解：（2）計算出各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下列。 從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，甲列是最大差額列，甲列的最小元素是5，所以產地3的產品先供應甲的需求，同時將運價表中產地3所在行的數(shù)字劃去。 對上表中的元素分別計算各行和各列的次最小運費和最小運費的差額，填入該標的最右列和最下行，重復步驟，直到求出初始解為止。得到下表： 銷地 產地 甲 乙 丙 丁 產量 1 1 2 1 4 2 3 6 9

59、 3 4 4 銷量 5 2 4 6 使用位勢法進行檢驗： 上表中，數(shù)字格處填入單位運價，并增加一行一列，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令=0，由 +=（i，jB，B為基，下同）來確定和. 由=-（+）（i，jN）計算所有空格的檢驗數(shù)，并在每個格的右上角填入單位運價，得到下表 銷地 產地 甲 乙 丙 丁 1 10 0 6 7 12 1 0 2 16 8 10 6 5 0 9 0 -2 3 5 0 4 3 10 8 10 4

60、-5 10 6 7 11 由上表可以看出，所有的非基變量檢驗數(shù)≥0，此問題達到最優(yōu)解。 此問題有唯一最優(yōu)解。 總運費min z=118 （3） 銷地 產地 甲 乙 丙 丁 戊 產量 1 10 20 5 9 10 5 2 2 10 8 30 6 6 3 1 20 7 10 4 2 4 8 6 3 7 5 9 銷量 4 4 6 2 4 解：（3）此問題是一個產銷不平衡的問題，產大于銷。增加一個假象銷售地己，令單位運價為0。銷量為2。這樣就達到了產銷平衡。 用伏格爾法求初始解

61、： 計算出各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下列。 從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，產地1所在的行是最大差額行，最小元素0，說以一產地的產品應該優(yōu)先供應己的需要，同時劃掉己列的數(shù)字。 對上表中的元素分別計算各行和各列的次最小運費和最小運費的差額，填入該標的最右列和最下行，重復步驟，直到求出初始解為止。得到下表： 銷地 產地 甲 乙 丙 丁 戊 己 產量 1 3 2 5 2 4 2 6 3 2 2 4 4 3 2

62、 9 銷量 4 4 6 2 4 2 使用位勢法進行檢驗： 上表中，數(shù)字格處填入單位運價，并增加一行一列，在列中填入（i=1，2，3，4），在行中填入（j=1，2，3，4，5，6），先令=0，由 +=（i，jB，B為基，下同）來確定和. 由=-（+）（i，jN）計算所有空格的檢驗數(shù)，并在每個格的右上角填入單位運價。 由上表可以看出，所有的非基變量檢驗數(shù)≥0，此問題達到最優(yōu)解。 又因為=0，此問題有無窮多最優(yōu)解。 總運費min z=90 （4） 銷地 產地 甲 乙 丙 丁 戊 產量 1 10 18 29 13

63、 22 100 2 13 M 21 14 16 120 3 0 6 11 3 M 140 4 9 11 23 18 19 80 5 24 28 36 30 34 60 銷量 100 120 100 60 80 解：（4）此問題是一個產銷不平衡的問題，產大于銷。增加一個假象銷售地己，令單位運價為0。銷量為40。這樣就達到了產銷平衡。 用伏格爾法求初始解： 計算出各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下行。 從行差額或者

64、列差額中找出最大的，選擇它所在的行或者列中的最小元素，同時劃掉所在列或行的元素。 對上表中的元素分別計算各行和各列的次最小運費和最小運費的差額，填入該標的最右列和最下行，重復步驟，直到求出初始解為止。 并用位勢法進行檢驗： 銷地 產地 甲 乙 丙 丁 戊 己 1 10 18 2 29 8 13 0 22 6 0 12 0 2 13 3 M M-16 21 0 14 1 16 0 0 12 0 3 0 0 6 0 11 0 3 0 M M-6 0 22 -10 4

65、9 4 11 0 23 7 18 10 19 8 0 17 -5 5 24 2 28 0 36 3 30 5 34 6 0 12 10 16 21 13 16 -12 由上表可以看出，所有的非基變量檢驗數(shù)≥0，此問題達到最優(yōu)解。 又因為=0，此問題有無窮多最優(yōu)解。 總運費min z=5520 3.4 已知運輸問題的產銷平衡表、單位運價表及最優(yōu)調運方案如下表所示 表1 銷地 產地 產量 5 10 15 0 10 15 25 5

66、5 銷量 5 15 15 10 表2 銷地 產地 10 1 20 11 12 7 9 20 2 14 16 18 （1）到的單位運價在什么范圍變化時，上述最優(yōu)方案不變？ （2）到的單位運價變?yōu)楹沃禃r，有無窮多最優(yōu)方案。除表1中方案外，至少寫出其他兩個。 解： (1)在對應表的數(shù)字格處（未知）填入單位運價，并增加一行，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令=0，由 +=（i，jB）來確定和. 由=-（+）（i，jN）計算所有空格的檢驗數(shù)，并在每個格的右上角填入單位運價（未知）。 最優(yōu)調運方案不變，則所有非基變量的檢驗數(shù)都是非負。所以： -30 +100 10-0 24-0 18-0 解得: 310 單位運價在此區(qū)間變化時，最優(yōu)調運方案不變。 （2）在對應表的數(shù)字格處（未知）填入單位運價，并增加一行，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令=0，由 +=（i，jB）來確定和. 由=-（+）（i，jN）計算所有空格的