運(yùn)籌學(xué)習(xí)題集(第二章)

1、判斷題判斷正誤，如果錯誤請更正第二章 線形規(guī)劃的對偶理論1. 原問題第 i 個約束是 <= 約束 ,那么對偶變量 yi>=0.2. 互為對偶問題 ,或那么同時都有最優(yōu)解 ,或那么同時都無最優(yōu)解 .3. 原問題有多重解 ,對偶問題也有多重解 .4. 對偶問題有可行解 ,原問題無可行解 ,那么對偶問題具有無界解 .5. 原問題無最優(yōu)解 ,那么對偶問題無可行解 .6. 設(shè) X,Y 分別為 minZ=CX| AX>=b,X>=0和 maxw=Yb| YA<=C,Y>=0 的可行解,那么有(1) CX<=Yb;(2) CX 是 w 的上界 ;(3) 當(dāng) X,Y

2、為最優(yōu)解 ,CX=Yb;(4) 當(dāng) CX=Yb 時,有 YXs+YsX=0;(5) X 為最優(yōu)解且 B 是最優(yōu)基時 ,那么 Y=CBB-1 是最優(yōu)解 ;(6) 松弛變量Ys的檢驗數(shù)是入s,那么X=-入s是根本解，假設(shè)Ys是最優(yōu)解，那么X=-入s是最 優(yōu)解 ., 那么都有最優(yōu)解 .8. 原問題具有無界解 , 那么對偶問題可行 .9. 假設(shè) X,Y 是原問題與對偶問題的最優(yōu)解 . 那么 X=Y.10. 假設(shè)某種資源影子價格為 0, 那么該資源一定有剩余 .11 影子價格就是資源的價格 .12. 原問題可行對偶問題不可行 , 可用對偶單純形法計算 .13. 對偶單純形法比值失效說明原問題具有無界解

3、.14. 對偶單純形法是直接解對偶問題的一種解法 .15. 減少一個約束 , 目標(biāo)值不會比原來變差 .16. 增加一個約束 , 目標(biāo)值不會比原來變好 .17 增加一個變量 , 目標(biāo)值不會比原來變差 .18. 減少一個非基變量 , 目標(biāo)值不變 .19. 當(dāng)Cj(j=1,2,3,n)在允許的最大范圍內(nèi)同時變化時，最優(yōu)解不變。選擇題在以下各題中，從 4 個備選答案中選出一個或從5 個備選答案中選出25 個正確答案。第二章 線性規(guī)劃的對偶理論1. 如果斷策變量數(shù)列相等的兩個線規(guī)劃的最優(yōu)解相同，那么兩個線性規(guī)劃A 約束條件相同B 目標(biāo)函數(shù)相同 C 最優(yōu)目標(biāo)函數(shù)值相同 D 以上結(jié)論都不對2. 對偶單純形法

4、的最小比值規(guī)那么是為了保證 A 使原問題保持可行 B 使對偶問題保持可行 C 逐步消除原問題不可行性D 逐步消除對偶問題不可行性3. 互為對偶的兩個線性規(guī)劃問題的解存在關(guān)系 A 假設(shè)最優(yōu)解存在， 那么最優(yōu)解相同 B 原問題無可行解， 那么對偶問題也無可行解C 對偶問題無可行解， 原問題可能無可行解 D 一個問題無界，那么另一個問題無可行解E 一個問題無可行解，那么另一個問題具有無界解4. 標(biāo)準(zhǔn)形式原問題max的最優(yōu)表中的檢驗數(shù)為入 1,入2,入n，松弛變量的檢驗數(shù)為入n+1,入n+2, 入n+m,那么對偶問題的最優(yōu)解為A 入1，入2,入 nB 入 1，入 2,入 nC 入 n+1,入 n+2,

5、入 n+mD D入 n+1,入 n+2,入 n+m5. 原問題與對偶問題都有可行解，那么A原問題有最優(yōu)解，對偶問題可能沒有最優(yōu)解B原問題與對偶問題可能都沒有最優(yōu)解C可能一個問題有最優(yōu)解，另一個問題具有無界解D原問題與對偶問題都有最優(yōu)解計算題線性規(guī)劃問題和對偶問題2.1對于如下的線性規(guī)劃問題min z = 3xi + 2x2 +xas.t. x1 + x2+ x315(1)2x1 - x2+ x39-x1 + 2x2+2x38x1 x2x301、寫出題目中線性規(guī)劃問題的對偶問題；2、分別求出原始問題和對偶問題的最優(yōu)解求解的次序和方法不限 解答：1、寫出題目中線性規(guī)劃問題的對偶問題；解：max w

6、 = 15y1+ 9y 2 + 8y 3s.t. y1 + 2y2 - y 33(1)y1 - y2 + 2y 32y1 + y2 + 2y 31y10、y 20、y302、分別求出原始問題和對偶問題的最優(yōu)解求解的次序和方法不限解：先將原問題化成以下形式，那么有min z=3x1+ 2x 2+ x3s.t. x1+ x 2+ x 3+ x 4=15(1)-2x1+ x 2-x3+ x 5=-9-x1+ 2x 2+2x 3+x 6=8x1x 2 x 3 X4x 5 x 60X1X2為X5X6右端z-3-2-1000X411110015X5-21-1010-9X6-1：22001:8X1X2用為X

7、5X6右端z-1：-300-10:9X4-1201106X32-110-109X6-540021P-10X1XX3%X5X右端z0-19/500-7/5-1/511X40：6/5013/5-1/5:8關(guān)03/510-1/52/55X1-4/500-2/5-1/52原始問題的最優(yōu)解為Xi X2 X3 X4 X5 X6=2, 0, 5, 8, 0, 0，minz=11對偶問題的最優(yōu)解為yi y 2 y 3 y 4 y 5 y 6= 0, 7/5 , -1/5 , 0, 19/5 , 0，maxw=112.2對于以下線性規(guī)劃問題max z = -X1- 2x 2s.t. -2x1 + 3x 212(

8、1)-3x1 + x 26x1 + 3x 23x10 , x 201、寫出標(biāo)準(zhǔn)化的線性規(guī)劃問題；2、用單純形表求出這個線性規(guī)劃問題的最優(yōu)解和最優(yōu)的目標(biāo)函數(shù)值；3、寫出這個極大化線性規(guī)劃問題的對偶問題；4、求出對偶問題的最優(yōu)解和最優(yōu)解的目標(biāo)函數(shù)值；5、第2個約束右端常數(shù) b2=6在什么范圍內(nèi)變化，最優(yōu)解保持不變。解答：1、寫出標(biāo)準(zhǔn)化的線性規(guī)劃問題:令 X1 =:-X1max z*=X1-2x 2s.t.2x1* + 3x 2+ x 3=12(1)3x*1+ x 2+ x4=6-x1* + 3x 2-x5 = 3x*1 x 2 x 3X4 x 502、 6分用單純形表求出這個線性規(guī)劃問題的最優(yōu)解和

9、最優(yōu)的目標(biāo)函數(shù)值*X1X2關(guān)XX5R右端Z'1-M3M-200-M03MX323100012%3101006R-1300-113*X1KX3為X5R右端Z'1/3000-2/32/3-M2%01019Xi10/30011/3-1/35茨-1/3100-1/3I 1/31*X1茨X3XX5R右端Z'000-1/10-7/1021/30-M3/2001-9/109/2*X1003/101/10-1/103/20101/103/2此時最優(yōu)解為X、Xz、X3、X4 X5=-3/2 , 3/2 , 9/2 , 0 , 0maxz=-3/2 3、寫出這個極大化線性規(guī)劃問題的對偶問題

10、；min w = 12y1+ 6y 2 + 3y 3s.t. -2y1 - 3y 2 + y 3-1(1)3y1 + y 2 + 3 y 3-2(2)yi0、y20、y304、求出對偶問題的最優(yōu)解和最優(yōu)解的目標(biāo)函數(shù)值；此時最優(yōu)解為yi、y2、y3、y4 y 5= 0, 1/10,-7/10, 0, 0minw =-3/25、那么有1 b211，最優(yōu)解不變。2.3LP問題：max z =X1+ 2x 2 +3x3 + 4x 4s.t. x1+ 2x 2 + 2x 3 + 3x 420(1)2x1+ x 2 + 3x 3 + 2x 420(2)x1、X 2、 X3、 x 40的最優(yōu)解為0，0,4,

11、4T，最優(yōu)值為Z=28。請用互補(bǔ)松弛定理計算其對偶問題的最優(yōu)解。解答：首先寫出此LP問題的對偶問題為:min w =20y1+ 20y 2s.t. y1+ 2y 21(1)2y1+ y 222y1+ 3y 233y 1+ 2y 24y 1、y 2、0將上述對偶問題的化成標(biāo)準(zhǔn)型，取松弛變量分別為V1、V2、 V3、V4,那么有min w = 20y1+ 20y 2s.t. y1+ 2y 2 -V1=12y1+ y 2 -V2=22y1+ 3y 2-V3=33y 1+ 2y 2 -V4=4(8)y1、y 2、0利用互補(bǔ)松弛定理可知:X3 = 4 > 0 ,又有 X 3 V3 = 0，所以有V

12、3 = 0代入式X4 = 4 > 0，又有 X 4 V4= 0所以有V4 = 0代入(8)式，那么有2y1+ 3y 2=:3(9)3y1+ 2y 2=:4(10)從中可計算出y1 = 6/5、y2 =1/5，那么w* =282.4 一個工廠用四種原料生產(chǎn)三種產(chǎn)品，生產(chǎn)每種產(chǎn)品要消耗的各種原料 數(shù)量表中“一表示相應(yīng)的產(chǎn)品不需要這種原料、各種產(chǎn)品的利潤以及各種原料的限量如下表所示。1、寫出原料限制條件下利潤最大化的線性規(guī)劃模型；2、寫出以上問題的對偶問題；3、 利潤最大的線性規(guī)劃問題的最優(yōu)解是產(chǎn)品A生產(chǎn)120件，產(chǎn)品B不生產(chǎn)，產(chǎn)品C生產(chǎn)52件，用互補(bǔ)松弛關(guān)系求四種原料的影子價格。原料消耗噸/

13、件產(chǎn)品A產(chǎn)品B產(chǎn)品C原料限量噸原料甲128102400原料乙610151500原料丙15181800原料丁20222000產(chǎn)品利潤120180210萬元/件解答：一個工廠用四種原料生產(chǎn)三種產(chǎn)品，生產(chǎn)每種產(chǎn)品要消耗的各種原料 數(shù)量表中“一表示相應(yīng)的產(chǎn)品不需要這種原料、各種產(chǎn)品的利潤以及各種原料的限量如下表所示。1.寫出原料限制條件下利潤最大化的線性規(guī)劃模型;max z =120X1+ 180X2 +210X3s.t. 12x1 +8x 2+10X32400(1)6x1 +10X 2+15X3150015x1 +18x 2180020x2+ 22x32000X10， X 20 X 302.寫出以上

14、問題的對偶問題；min w =:2400y1 + 1500 y2 +1800 y3+2000y4s.t. 12y1 + 6y 2 +15y3120(1)8y1 + 10y 2 + 18 y3 + 20 y18010y1 + 15y 2+22y4210y 10 ， y 20 y 30 y403.利潤最大的線性規(guī)劃問題的最優(yōu)解是產(chǎn)品A生產(chǎn)120件，產(chǎn)品B不生產(chǎn)，產(chǎn)品C生產(chǎn)52件，用互補(bǔ)松弛關(guān)系求四種原料的影子價格。maxz =120X1 +180X2+210 X3s.t. 12x1+8x2 +10X3+X4=2400(1)6x1+10x2 +15X3+x5 =150015x1+18x2+X6=180020x2 + 22x3+X7 =:20001 0， X 20X 30X 40 x50 X 60 X70X4 =440 X5 =0 X6 =0 X7 =856min w=2400y1 + 1500 y2+1800y3 +2000y4s.t. 12y1 + 6y2 +15y3-屮=120 (1)8y1 + 10y2 +18 y3+ 20 y4