運籌學第二章線性規(guī)劃的對偶理論復習題

1、第二章線性規(guī)劃的對偶理論1消序IIIIII單件 利潤 (元)A321200B413300C223250可用工時604020農(nóng)2-11、某廠生產(chǎn)A、B、C三種產(chǎn)品，每種產(chǎn)品要 經(jīng)過I、II、III三道工序加工，設每件產(chǎn)品在每道 匸序上加匸所消耗的匸時，每道工序可供利用的工 時上限，以及每件產(chǎn)品的利潤如表2-1所示.試列出使總利潤最大的線性規(guī)劃模型，并寫出 它的對偶問題，同時，就這個對偶問題作出經(jīng)濟上的解釋.解：設® x2,忑分別表示A、B、C各產(chǎn)品的數(shù)最，Z表示總產(chǎn)值則：)£)x z = 200兀 + 300.V, + 250x3st. 3x1 + 4x, + 2x3 <

2、; 602xx + x2 + 2x3 < 40X + 3x, + 3x3 < 20x(/ = l,2,3)>0原問題的對偶問題為niiii w = 60y】+ 40y2 + 20 y3st. 3j| + 2y2 + y3> 2004片+弘+ 3旳丫3002% + 2y2 + 3y3 > 250Ji »0,)3»0經(jīng)濟解釋ms分別表示給別人代工時所得收入,對廠方而言,w越大越好,但定 價不能太高，耍對方容易接受，應考慮使總收入即對方的總支出盡可能少才比較合理, 廠方不會吃巧，對方也容易接受。2、寫出下列線性規(guī)劃問題的對偶問題:(1) maxz =

3、 lOXj +x2 + 2“s. t. +x2 +2x3 <10+x2 + x5 < 20Xj > 0(y = 1,2,3)解:win w= 10+ 20st. + y2 > 102% + 為2y2>0(2) ininz=2xt +2x2 +4x.s. t.2Xj + 3x2 + 5Xy > 23xt + 兀2 + 7兀3 < 3X + 4x2 + 6.v3 < 5Xj > 0(7 = 1,2,3)解 miax vv：=2% + 3y2 + 5y3$/. 2yx + 3% + % < 23yt + y2 + 4y3 <25y,

4、+ 7y2 + 6y3 <4Ji »0,)3<0(3) maxz = 5.v1 + 6.v, + 3x3s. t x1 +2x2 +2x3 = 5Xj + 5x«> x3 > 34血 + 7x2 + 3Xj < 8X無約束，x2 >0 , x5 <0解:Jilin vv = 5) + 3y2 + 8v3st yi-y2 + 4y3 = 52j| + 5% + 7% A 6 2%-力 + 33 53 川由，y2 <0, y3>0(4) nun z = 3召 + 2x2 一 3x, + Ax4X 2x2 一 3Xj + 4x

5、4 < 3x2 +3心 +4小 >-52兀-3x2 - 7x3 _ 4x4 = 2Xi >0,x4 <O,x2,x3無約束解：max w = 3y】一 5y2 + 2y3st. y + 2y2<3- 2% + 52-3%=2-3% + 3%_7%=-34+42-473 >4% <0, y2 >0, y3 <03、應用對偶理論證明線性規(guī)劃問題.max z = xk+x2s. t. - x, + x2 + x3 <2-2x, +x2 -x3 < 12°有可行解，但無最優(yōu)解.(o)證明：x= 0 是線性問題的可行解，即該問題

6、存在可行解;乂 其對偶問題為：nun w = 2y1 + y2st. -Ji - 2y2 > 1% + 為1X - % n 0Ji no, y2 >0yl9y2 >0'-y-2y2 <0這與約束條件(1)不符該對偶問題無可行解二原問題無最優(yōu)解。4、應用弱對偶定理，證明線性規(guī)劃問題niaxz = Xj +2x2 +x3s. t. xk+x2-x3 <2 xl-x2+xi = l2x, + x2 + x3 >2X >0,a2 <O,a35E約朿的最人值不超過1.證明：該線性問題的對偶問題為：nnn w = 2 + y2 + 2y3st. x

7、+2 + 2兒 n 1乳- +唇2丁 + 為+，3 = 1% >0,為自由，% <0易知丫 = (0,1,0) 丁是對偶問題的一個可行解，由對偶問題的對偶定理可得：(°)cx° < y°b = 1 (2,1,2) = 1BK1X Z < 1即最大值不超過15、應用對偶理論，證明線性規(guī)劃問題niaxz = 3兀 +2x2s. t. - xt +2x2 <43兀 +2x, < 14 xt -x2 <3 xx2 >0有最優(yōu)解，并證明其對偶問題也有最優(yōu)解.證明：對偶問題nun w= +14 y2 + 3旳sf. -J. +

8、3y2 + y3 > 32) + 2y2 - y3 > 2爪0, y2>0,由題易知X二(3, 0)丫是原問題的一個可行解，Y= (0, 1, OF是對偶問題的一個可行解由對偶問題的推論2- 3可得它們都有最優(yōu)解。即得證。6、已知標準線性規(guī)劃問題niaxz = exAx - bQ0具有最優(yōu)解，假設將右端向量b改為另一向量d,如果改變后的問題是可行的, 試證該問題一定有最優(yōu)解.7、考慮下列原始線性規(guī)劃niaxz = 2 兀i + x2 4- 3%,s. t a; +,r2 +2x3 5 52召 4-3x2 +4兀$ = 12勺 > 0(； = 1,2,3)(1) 寫出其對

9、偶問題；(2) 己知(3,2,0)是上述原始問題的最優(yōu)解，根據(jù)互補松弛定理，求出對偶 問題的最優(yōu)解：(3) 如果上述規(guī)劃中的第一個約束為資源約束，寫出這種資源的影子價格.解:(1)對偶問題：imn iv = 5yt +12y.,st. + 2y2 > 2Ji + 3% » 12y + 4，2 n 3y >0, %無符號限制(2) 由題知原問題的最優(yōu)解為/ = (3,2,0)7：由互補松弛定理得：在對偶問題中對應第一，二個約束為緊，第三個約束條件為松，即，y； + 2y； = 2.*21 f y 1 = 4+ 3y2 = 1 二>< t°才、2 ly：

10、 = i2” +4 >3對偶規(guī)劃問題的垠優(yōu)解y； =（44）（3）影子價格為Yi = 4 ：8、已知線性規(guī)劃問題max 乙=X + 2.v7 + 3x5 + 4x4s. t. 斗 + 3.v, + 2x3 + 3x4 < 20+ x2 + 3.v3 + 2x4 < 20Xj > 0（y = l, -,4）其對偶問題的最優(yōu)解為y； = 1.2,y： =0.2 ,試根據(jù)對偶理論求出原問題的最優(yōu)解.解：先寫出其對偶問題。nun iv = 20y）+ 20y2si. yx + 2y2 > 1 3% + y2>2 2yi+3y2- 3納 + 2y2 n 4X no,

11、y2>0對偶規(guī)劃問題的仗優(yōu)解y： = 1.2, y； = 0.2,代入約束條件，知第1, 2約束條件成立嚴格不等式, 由互補松弛定理，原規(guī)劃最優(yōu)解中相應變Mx； = X： = 0乂#，），；不為0,則在原問題規(guī)劃中對應的約束條件為緊,得J 2x3 + 3x4 = 20 Jx； = 43x3 + 2x4 = 20=>x； = 4原對偶規(guī)劃問題的瑕優(yōu)解 十=（0、044）9、已知某線性規(guī)劃問題的最優(yōu)單純形表如2-2所示，表中兀，心為松弛變量，問題的約束為W形式(1) 寫出原線性規(guī)劃問題；(2) 寫出原問題的對偶問題:M接山衣2-2寫出對偶問題的最優(yōu)解.解:(1)由表知B"N

12、=-p/20、-1/6 1/3丿；S/2、令8 =21 Xllj表2-2耳兀屯R兀b01/211/205/21-1/20-1/61/35/20、I =則p、0B* =ZN =1/20>(-1/61/3八兀211°nB =1/21/2 丿1/2(一1/61/3八b丿=> N =1 2、Q/2) f<5、A =；B"=>/? =-1 1丿2丿=(一4,一2)=>2< 1/2 0-1/6 1/3-(> C；)C廣6C3 = 10C+(-4. -2)4、cl=-4 => C. = -2原線性問題為： max z = 6兀 一 2x2

13、+ 10x3 st. x2 + 2x3<53兀-x, + x3 <10 兀(i = i,2,3)no(2) niin w= +10y2st. 3y2 > 6 X-以-22y, + y2 >10 八0, y2>0 x= (5/2,0,5/2/； Z* = 40;即.= y5 = 0=6卜=4Ex + y2=> j > 2 = 2二 ior*=(4, 2)t w*=40；10、某廠擬生產(chǎn)甲、乙、丙三種產(chǎn)品， 都需要在A、B兩種設備上加工,有關數(shù) 據(jù)如表2-3所示.（1）如何充分發(fā)揮設備能力，使產(chǎn) 品總產(chǎn)值最大？（2）若為了提高產(chǎn)量，以每臺時350 元租金租

14、用外廠A設備，問是否合算？設備、單耗（臺時/件）設備冇效臺時（每月）甲乙丙A12 1400321 2500產(chǎn)值（T元/件）32 1表2-3解:（1）設勺耳，厲分別表示甲、乙、丙各產(chǎn)品的數(shù)屋，Z表示總產(chǎn)值則:i）ax Z = 3舌 + 2xz + x3st. 兀 + 2x2 + x3 <400lx、+ x2 + 2x3 < 500兀（心 1,2,3） 10化為標準形：z = 3兀 + 2x2 + Xyst. xL + 2x. + x5 +x4 = 4002" + x, + 2.v3+x5= 500兀(2 1,2,3,4,5) AOC32100bGXbXxX：Xsx；Xs0X

15、.121104000Xs21201500檢驗數(shù)321000X,03/201-1/21503X】11/2101/2250檢驗數(shù)01/2-20-3/225020102/3-1/31003X,101-1/32/3200檢驗數(shù)00-2-1/3- 4/3-800/= (200J 00/；ZJOO;(2)原問題的對偶問題為imn w = 400y)+ 500)、st. y + 2y2>i2ji + 為2Ji + 2y2>l八0, y2>0此時，八，y扮別表示出租A, B設備所得利潤，由(1)中的最優(yōu)表得y；=l/3,即如出租A設備可獲得1000/3元，而1000/3<350所以不合

16、算。11、己知某實際問題的線性規(guī)劃模型為inaxz =工 c內(nèi)Xj >0(7 = 1,2/,/!)若第i項資源的影子價格為y, (/ = 1,2,7)(1)若第一個約束條件兩端乘以2,變?yōu)?#163; （2列）形 < 2b., >-1久是對應丁這個新約束條件的影子價格，求人與兒的關系;10(2)令虬=3兀，用小/3替換模型中所有的勺，問影子價格是否變化？若召不可能在最優(yōu)皋中出現(xiàn)，問x是否町能在最優(yōu)基中岀現(xiàn);(3) 如果目標函數(shù)變?yōu)閙ax Z =工 2c jXj問影子價格有何改變？(4) 如果模型中約束條件變?yōu)閚2(1宀=bi i = 1,2,a>=i問、(2)、(3)中

17、的結(jié)論是變化?解：(1)由影子價格的定義可得:送伶2(2) 由(1)可知幾只與b的值有關.當?shù)南禂?shù)由3變?yōu)閤的系數(shù)1/3時，y,的值并 不發(fā)生變化；&不可能在最優(yōu)基中出現(xiàn)，x也不可能在繪優(yōu)基中出現(xiàn)7 = 士。兒=士巧=w(3) 當目標函數(shù)由Z = tCJXj變?yōu)?C兀時,q增大了兩倍>-iy-i影子價格y,也增大了兩倍。(4) 分別相同。12. 用對偶單純形法求解卜列線牲觀劃問題:(1) min z = 1 Ox, + 5x2 + 4 牙,3召 + 2x2 一 3Xj > 3+2x3 >10解：先將問題化為標準式n)ax z = 一10兀 一 5x2 - 4x3 +

18、0x4 + 0x5_3召 一 2x2 + 3x5 + x4 = 一 3- 2x3+x5= -10取初始1E則基B = (Pl P5) = I則原問題己化為關丁基B的典式,c23100BCBX.X,X2Xs人Xs0X：-3-2310-30x5-40-201-10檢驗數(shù)-10_5-40000£-9-2013/2-18-4x52010-1/25檢驗數(shù)-2_500-220-10X：12/90-1/9-1/62-4x50-4/912/9-1/61檢驗數(shù)0-41/90-2/9-7/324可得原問題的最優(yōu)解為:24./ = (20J,0.0)Z4 = -24.Z = 24, / = (2/27/3

19、)$(2) nun z = 2Xj + 3忑 + 4x3s. t. 兀 +2x2 +x3 > 32Xj 一 x? + 3心 > 4Xnx19x5 >0將問題化為：imx Z = _2兀 一 3.v2 - 4x3st. _片_2忑_屯+兀=_3_2兀 + x2- 3x3+ x5 = -4x.(/= 1,2,3,4,5) > 0c32100BCBXbX：X：&X,Xs0X.-1-2-110-30Xs1-301-4檢驗數(shù)-2-3-4000Xi0-5/21/21-1/2-13X,1-1/23/20-1/22檢驗數(shù)0-4-10-12502x201-1/5-2/51/52/

20、53x>1014/10l/5-4/1011/5檢驗數(shù)00-9/5-8/5-1/5-28/5x= (11/5,2/5,0)f；Z" = -2 8 / 5; Z$ = 28/5(3) nun z = 2X +x2 s. t. 3兀 +x2 > 34xt + 3x: > 6x1 + 2x, < 3xx2 >0解：(3) max z = -2xt-x2st.- x2 + x4 =_3_糾_3耳+ x5 = -6 + 2x2+ 忑=3x,(/ = l,2,3,4,5,6)>0c350000BCbXbXxX：X,X,x5&0X4-3-10100-30X

21、s-40Z3010_60Xe1200013檢驗數(shù)-2-100000£z3-10100-30Xs4/3010-1/3020Xs1200013檢驗數(shù)-2-10000-2X】11/30-1/30010x50-4/914/9-1/302/3005/301/3012檢驗數(shù)0-1/30-2/3002(4) iiun z = 3石 + 2x2 + x3s. t.+ x2 + x3 <6X +x3> 4x2- Xj> 3Xj >0 (j = 1,2,3)解：化為：inax Z = _3勺-2x2 - x3st. 兀 + x2 + x3 + x4 = 6-x2+x3+ 兀=_3

22、兀(2 1,2,3,4,5,6)2 016Ci38000 58旺X2心兀4兀5D3101/20-2100000-3110500801001350檢驗數(shù)00-3/20-2-3100表2-3C-3-2-1000bCbXBXix2XsX.x5人0石11110060Xs-10zl010-400-11001-3檢驗數(shù)- 3-2-10000X,0101102-1xs1010-1040Xszl-10011r檢驗數(shù)-2-200-100£0101102-1Xs0211001-3-3Xx1100-1-1檢驗數(shù)0000-3-20£001111-1-2x201-100-13-3£1010

23、-104檢驗數(shù)0000_3-2由表知，此題無可行解。13、己知線性規(guī)劃問題niaxz = 3.Vj +&匚s. t2jj +4x2 <16006x1 + 2x, < 1800x2 < 350XZ >0用單純形法求解時得最終單純形表如表2-3所示.17（1）要保持現(xiàn)有最優(yōu)解不變，分別求sc,的變化范圍；（2）要保持現(xiàn)有最優(yōu)解不變,分別求blfb2, %的變化范圍;（3）當®變?yōu)?00時，求新的最優(yōu)解.解：（1）由表知，CG為基變最的系數(shù) 、C； = max + ；= -rAC* = Jinn+d=iGw 0,4ACC = Jinx+t=-2AC* = J

24、JUll 4- 1 = co C, G 6,4-00)(2) 參見教材P67的方法求Z(3) .® = 500 任300,400故優(yōu)解將發(fā)生變化;b = (00150).Ab=B_1Ab =5/2 0 -2Y-31 100 0 1 kJ00150300、=1500J C38000bcBxBXxx2X3X；x53Xx101/20z2-2000£00-311020008x201001500檢驗數(shù)00-3/20-20X5-1/20-1/4011000X：50-1/2101000188X：1/21100400檢驗數(shù)-10-200-3200/ = (0,400/； Ze = 3200

25、;14、己知線性規(guī)劃問題niaxz = 10“ +5x?s. t. 3冊 +4氐 <95x, + 2x2 < 8 xl9x2 20用單純形法求得最終單純形表如表2-4所示，試用靈敏皮分析的方法分別判斷:(1) 目標函數(shù)系數(shù)q或°分別在什么范圍內(nèi)變動，現(xiàn)最優(yōu)解不變；(2) 約束條件右端常數(shù),*中，當保持一個不變時，另一個在什么范圍內(nèi)變化,現(xiàn)有的故優(yōu)皋不變：(3) 問題的目標函數(shù)變?yōu)閘iiaxz = 12“ +4.v,時，最優(yōu)解有什么變化；約束條件右端常數(shù)項由叫19 7時，最優(yōu)解有什么變化?表2-453800bCb旺X.心5015/14-3/143/21010-1/72/71

26、檢驗數(shù)00-5/14-25/14-25/2解:1) . G變化時,L6OAIqR+-rvlqvlG.P n、vl0vlsslwq口 L_c l二03AI3Aq 尸g+qLxqv+82M趙氐J5押(zOAIq6cooL0LOLDQD61oOv-Hor-HoOv-Hi-Hoor-MoOC|QrrOJVLD 寸r-HLDOJLDV1CO><coLDCMof <oOX盤ooo9 Tvlqvl8Tr<= LVI0V1# I 走0 匚C L 二 q口龍Al龍A/ = (8/5,0,21/5,0/C-3-2-10bCbXbXxx2X,X,0Xs3410110X*52019檢驗數(shù)105

27、0000x3015/14-3/14212Xi10-1/711檢驗數(shù)00-5/14-25/1 1-20宀(l,2O0)T15、己知線性規(guī)劃問題表2-5max z = 2xl- x2 + x338000bCrXRX|X2旺r斗s. t.2X|111106Xj + x2 + x5 < 600311110檢驗數(shù)03-1-20-12廠0 (; = 1,2,3)用單純形法求得最終單純形表如表2-5所示，試分別求當下列情況發(fā)生時的最優(yōu)解：(1)冃標函數(shù)變?yōu)閙axz = 2X+3卞2+心：約束條件右端項由變?yōu)長 4(3) 增加一個新的約束條件-x, +2x2 >2L8(0丿Z1解：由表知C2的影響

28、范Fhl為C2 (-8, 2:當忖標兩數(shù)變?yōu)閙ax乙=2兀+ 3x2 + “時，最優(yōu)解將發(fā)生變化c23100BCbXBX,X2XsX.X,2X：1111660Xs0311110檢驗數(shù)01-1-202X,102/32/3-1/38/33Xz011/31/31/310/3檢驗數(shù)00-4/3-7/3-1/3-46/3化 F = (8/3J0/3.0/； Z，= 46/3;3C23100bCBXbXtX：XsX.X52X】1111030Xs031117檢驗數(shù)0-3-1-206x=(3X)A0,7)r； Zw = 6;b = B 仏/?=(3) JEx* = (6,0,0,0,10/代入約束條件- +

29、3>2 V -6 + 0 > 2不成立,該問題的最優(yōu)解將發(fā)生變化, x _ 2x2 + x6 = -2C2-11000BCBXbXiX：XsX.Xs&2X：11110060X,031110100Xe1-20001-2檢驗數(shù)0-3-1-2002X,11110060X,031110100Xe0-3-1-101-8檢驗數(shù)0_3-1-2002X,102/32/301/310/30X,0000112-1X2011/31/30-1/38/3檢驗數(shù)00000-1-12/3F = (10/3,8/300,2)'； Z* =4;16、已知線性規(guī)劃問題max z = -5x1 + 5.

30、v, +13.v3s. t. - £ + 兀 + 3x3 < 20A12xa +4x, +10x3 < 90B廠 >0 (; = 1,2,3)先用單純形法求出垠優(yōu)解，再分析在下列條件單獨變化的情況下最優(yōu)解的變化:(1) 約束條件B的右端項山90變?yōu)?0；(2) 目標函數(shù)中心的系數(shù)由13變?yōu)?amp;r- 2)(3)變最兀的系數(shù)(包括目標函數(shù))由-1變?yōu)?丿5X(6)(4)變量匕的系數(shù)(包括目標函數(shù))由1變?yōu)?420 增加一個約束條件2孔+ 3冬+ 5心 50 ；(6)原約束條件(2)變?yōu)?0人+5兀+10小S100.解：化為:n)ax z = 一5兀 + 5x2 +

31、 13屯st. 一 召 + 兀 + 3“ + x4 = 20 12xl+4x1 + Qx3 +x5=901,2,3,4,5)2 0c-3-2-100BCBXBX：X：XsX：x50X,-11310200X,124100190檢驗數(shù)-j5130013X,-1/31/311/3020/30X,46/32/30-10/3170/3檢驗數(shù)-2/32/30-105x2-11310200x5160-2-4110檢驗數(shù)00-2_50-100(1)A/?=0、/ = (020,0,040/； Z# = 100;AZ? = B ' Nb =< 1 o) <-4 1 丿r020)0 )> =1-20,C_551300bCBXxX：X,X.：<55x2-11310200X,160z2-41-10檢驗數(shù)00-2_505X22310_53/2513X,-8012-1/25BJ21檢驗數(shù)-1600-1-1-90(2)C-55800bCBX»X,