運(yùn)籌學(xué)LP的對(duì)偶問(wèn)題與靈敏度分析

1、第3章 LP的對(duì)偶問(wèn)題與靈敏度分析1 1 原問(wèn)題與對(duì)偶問(wèn)題原問(wèn)題與對(duì)偶問(wèn)題 大自然中任何事物之間的關(guān)系均可以用陰陽(yáng)八卦的思想來(lái)理解，有著生生相克的特性。一件事物有正面，還有反面；有積極作用，還有消極作用。對(duì)偶問(wèn)題正是如此！ 陰陽(yáng)機(jī)器廠(chǎng)在計(jì)劃期內(nèi)生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需設(shè)備A、B、C臺(tái)時(shí)如下：產(chǎn)品產(chǎn)品資源限量設(shè)備A11300臺(tái)時(shí)設(shè)備B21400臺(tái)時(shí)設(shè)備C01250臺(tái)時(shí)該工廠(chǎng)每生產(chǎn)一單位產(chǎn)品可獲利50元，每生產(chǎn)一單位產(chǎn)品可獲利100元，問(wèn)工廠(chǎng)應(yīng)該怎樣安排生產(chǎn)，才能獲利最多？ 設(shè)產(chǎn)品的計(jì)劃產(chǎn)量為x1，產(chǎn)品的計(jì)劃產(chǎn)量為x2， 則有線(xiàn)性規(guī)劃問(wèn)題LP1： 目標(biāo)函數(shù)： 約束條件：0,250400

2、2300. .10050max212212121xxxxxxxtsxxz 現(xiàn)假定有另一八卦機(jī)器廠(chǎng)，該廠(chǎng)的規(guī)模較小一些，想租用陰陽(yáng)廠(chǎng)的設(shè)備進(jìn)行生產(chǎn)。那么陰陽(yáng)廠(chǎng)的領(lǐng)導(dǎo)應(yīng)該給自己的設(shè)備制定一個(gè)怎樣的出租價(jià)格呢？ 設(shè)出租設(shè)備A、B、C的價(jià)格分別定為 y1、y2、y3。該問(wèn)題可從兩個(gè)角度進(jìn)行分析：對(duì)于陰陽(yáng)廠(chǎng)，總租金應(yīng)當(dāng)不低于原利潤(rùn)： 生產(chǎn)產(chǎn)品所需設(shè)備臺(tái)時(shí)不應(yīng)當(dāng)?shù)陀谠麧?rùn)： 生產(chǎn)產(chǎn)品所需設(shè)備臺(tái)時(shí)不應(yīng)當(dāng)?shù)陀谠麧?rùn)：對(duì)于八卦廠(chǎng)，希望支付的總租金最少，即：50221yy100321yyy321250400300minyyyf 因此可以建立另一線(xiàn)性規(guī)劃問(wèn)題LP2： 目標(biāo)函數(shù)： 約束條件：0,100502. .25

3、0400300min32132121321yyyyyyyyt syyyf 在這種情況下，我們稱(chēng)LP1、LP2互為對(duì)偶問(wèn)題，即一個(gè)為原問(wèn)題，另一個(gè)則為對(duì)偶問(wèn)題。 原問(wèn)題 對(duì)偶問(wèn)題), 2 , 1( 0), 2 , 1(. .min11miynjcyat sybfimijiijmiii), 2 , 1(0), 2 , 1(. .max11njxmibxatsxczjnjijijnjjj 用矩陣形式，可表達(dá)為： 原問(wèn)題 對(duì)偶問(wèn)題0YCYAYbTTTtsf. .min0XbAXCX.maxtsz 在上例中，原問(wèn)題與對(duì)偶問(wèn)題的矩陣形式可以寫(xiě)作： 原問(wèn)題 對(duì)偶問(wèn)題032132132110050101211

4、. .)250400300(minyyyyyytsyyyf0212121250400300101211. .)10050(maxxxxxtsxxz二者之間的關(guān)系： 原問(wèn)題中求目標(biāo)函數(shù)極大化問(wèn)題，對(duì)偶問(wèn)題中求目標(biāo)函數(shù)極小化問(wèn)題。 原問(wèn)題中約束條件的個(gè)數(shù)等于對(duì)偶問(wèn)題中變量的個(gè)數(shù)。 原問(wèn)題約束條件中符號(hào)為 號(hào)，對(duì)偶問(wèn)題中約束條件符號(hào)為 號(hào)。 原問(wèn)題目標(biāo)函數(shù)的系數(shù)是其對(duì)偶問(wèn)題約束條件的右端項(xiàng)?？捎萌缦卤砀駚?lái)表示：原問(wèn)題（求極大）右端項(xiàng)對(duì)偶問(wèn)題（求極?。゜1 y1b2 y2. . . .bm ymc1 c2 cnx1 x2 xna11 a12 a1na21 a22 a2n. . . . . . . .

5、am1 am2 amn b1b2. bm右端項(xiàng) c1 c2 cn例1：寫(xiě)出下述線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題0,2003510046440632. .643max321321321321321xxxxxxxxxxxxtsxxxz解：第一步：將5x1-3x2+x3 =200轉(zhuǎn)換成： 5x1-3x2+x3200 和 5x1-3x2+x3200,然后將所有的約束條件寫(xiě)成（亦可），有0,200352003510046440632. .643max321321321321321321xxxxxxxxxxxxxxxtsxxxz第二步：令與上式中四個(gè)約束條件對(duì)應(yīng)的對(duì)偶變量分別為y1,y2,y3,y3(因?yàn)樗鼈z來(lái)自于

6、同一個(gè)約束條件），則有對(duì)偶問(wèn)題：0 , ,6 64 33433 5562. . 200200100440min33213321332133213321yyyyyyyyyyyyyyyytsyyyyf第三步：再令y3=y3-y3，則有最終的對(duì)偶問(wèn)題：無(wú)約束321321321321321, 0,6643433562. .200100440minyyyyyyyyyyyytsyyyf例2：寫(xiě)出下述LP的對(duì)偶問(wèn)題：0, 030351546324624. .347min32132321321321xxxxxxxxxxxtsxxxz無(wú)約束按照上述三個(gè)步驟，求得其對(duì)偶問(wèn)題為：無(wú)約束32132132121321,

7、 0, 033464562734. .301524maxyyyyyyyyyyytsyyyf原問(wèn)題與對(duì)偶問(wèn)題互化關(guān)系表：原問(wèn)題與對(duì)偶問(wèn)題互化關(guān)系表：原問(wèn)題（對(duì)偶問(wèn)題）原問(wèn)題（對(duì)偶問(wèn)題）目標(biāo)函數(shù)（目標(biāo)函數(shù)（max）對(duì)偶問(wèn)題（原問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）目標(biāo)函數(shù)（目標(biāo)函數(shù)（min）個(gè)個(gè)變變量量無(wú)約束無(wú)約束目標(biāo)函數(shù)中變量的系數(shù)目標(biāo)函數(shù)中變量的系數(shù)約個(gè)約個(gè)束束 條條 件件 約束條件右端項(xiàng)約束條件右端項(xiàng)個(gè)個(gè) 約約 束束 條條= 件件約束條件右端項(xiàng)約束條件右端項(xiàng)個(gè)個(gè) 變變 量量無(wú)約束無(wú)約束目標(biāo)函數(shù)中變量的系數(shù)目標(biāo)函數(shù)中變量的系數(shù)2 對(duì)偶問(wèn)題的基本性質(zhì)化標(biāo)準(zhǔn)形：)3(0,)2(.) 1 (MaxssXXbXAX

8、TSCXZ設(shè)有LP問(wèn)題： 0.MaxXbAXTSCXZ不違背一般，設(shè)B是一個(gè)可行基，與B相應(yīng)，做矩陣分塊如下： 一、單純形法的矩陣描述),(),(),(NBACCCXXXNBNB式（1），（2）可表示為：(,) (,)( ,) (,)TBNBNTBNSZCCXXB NXXXb即：)5()4(bXNXBXXCXCZsNBNNBB式（5）兩端左乘B-1得：)6(111bBXBNXBXsNB由式（6）得：)7(111sNBXBNXBbBX 帶入式（4）得： 由式（8）得單純形法的最優(yōu)性條件為：111111()()(8)BBNNBNsNNBNBNBsZC XC XCB bB NXB XC XC B b

9、CC B N XC B X0011BCNBCCBBN二、單純形表的矩陣結(jié)構(gòu) 由（7），（8）可構(gòu)造單純形表：三、對(duì)偶規(guī)劃與原規(guī)劃最優(yōu)解的關(guān)系當(dāng)原問(wèn)題得到最優(yōu)解時(shí)，必有： 0011BCNBCCBBN令： ，上式等價(jià)為：1BCYB0YCYA可知這是對(duì)偶規(guī)劃的一個(gè)可行解且此時(shí)： ，可見(jiàn)對(duì)偶規(guī)劃與原規(guī)劃最優(yōu)解的目標(biāo)函數(shù)值相等，不是偶然的。zbBCYbWB1四、由原規(guī)劃最終單純形表確定對(duì)偶規(guī)劃最優(yōu)解 考察單純形表結(jié)構(gòu)，可在原規(guī)劃得到最優(yōu)解時(shí)，同時(shí)直接得到對(duì)偶規(guī)劃最優(yōu)解，這已經(jīng)是明確的問(wèn)題。 并且由： 還可發(fā)現(xiàn)對(duì)偶問(wèn)題的最優(yōu)解y= 實(shí)際是原問(wèn)題松弛變量的檢驗(yàn)數(shù)的相反數(shù)。110sBsBCBExCB 松 弛

10、變 量的 檢 驗(yàn) 數(shù)1BC B舉例MAX 50 x1+100 x2+0s1+0s2+0s3. S.T. x1 + x2+ s1+ 0s2+ 0s3=300, 2x1 + x2+ 0s1+ s2+ 0s3=400, 0 x1 + x2+ 0s1+ 0s2+ s3=250, x1,x2,s1,s2,s30迭代次數(shù)基變量CB x1 x2 s1 s2 s3 b比值bi/aij 50 100 0 0 0 2x1S2x2500100 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 15050250Zj 50 100 50 0 50 0 0 -50 0 -5027500jjjzc Lindo求解

11、對(duì)偶問(wèn)題 min 300y1+400y2+250y3 st y1+y2=50 y1+y2+y3=100 end五、對(duì)偶問(wèn)題基本性質(zhì)五、對(duì)偶問(wèn)題基本性質(zhì)其對(duì)偶問(wèn)題的最優(yōu)解。是是原問(wèn)題的最優(yōu)解，則，且有是其對(duì)偶問(wèn)題的可行解是原問(wèn)題的可行解，最優(yōu)性。如果恒有是其對(duì)偶的可行解，則是原問(wèn)題的可行解，弱對(duì)偶性。如果), 1(), 1(), 1(), 1(. 2), 1(), 1(. 11111miynjxybxcmiynjxybxcmiynjxijnjmiiijjijnjmiiijjij. 0.0. 5minmax,. 4. 311injijijnjijijiybxabxayfz，則如果，則如果為零，也即

12、對(duì)偶變量一定格不等式，則其對(duì)應(yīng)的反之如果約束條件取嚴(yán)取嚴(yán)格等式；為非零，則該約束條件約束條件的對(duì)偶變量值果對(duì)應(yīng)某一劃問(wèn)題的最優(yōu)解中，如互補(bǔ)松弛性。在線(xiàn)性規(guī)。解，且有偶問(wèn)題也一定具有最優(yōu)則其對(duì)優(yōu)解理）。如果原問(wèn)題有最強(qiáng)對(duì)偶性（或稱(chēng)對(duì)偶定解。問(wèn)題（原問(wèn)題）無(wú)可行，則其對(duì)偶對(duì)偶問(wèn)題）具有無(wú)界解無(wú)界性。如果原問(wèn)題（6.zf線(xiàn)性規(guī)劃的原問(wèn)題及其對(duì)偶問(wèn)題之間存在一對(duì)互補(bǔ)的基解，其中原問(wèn)題的松弛變量對(duì)應(yīng)對(duì)偶問(wèn)題的變量，對(duì)偶問(wèn)題的剩余變量對(duì)應(yīng)原問(wèn)題的變量；這些互相對(duì)應(yīng)的變量如果在一個(gè)問(wèn)題的解中是基變量，則在另一問(wèn)題的解中是非基變量；將這對(duì)互補(bǔ)的基解分別代入原問(wèn)題和對(duì)偶問(wèn)題的目標(biāo)函數(shù)有：3 3 對(duì)偶單純形法對(duì)偶

13、單純形法單純形法是在保持原問(wèn)題的所有約束條件的常數(shù)大于等于零的情況下，通過(guò)迭代，使得所有的檢驗(yàn)數(shù)都小于等于零，最后求得最優(yōu)解。對(duì)偶單純形法則是在保持原問(wèn)題的所有檢驗(yàn)數(shù)都小于等于零的情況下，通過(guò)迭代，使得所有約束條件的常數(shù)都大于等于零，最后求得最優(yōu)解。優(yōu)點(diǎn)：初始解可以是非可行解；對(duì)于一些大于等于號(hào)約束條件可以不添加人工變量，只需把兩邊同乘以-1，化成小于等于約束。缺點(diǎn)：1.不是所有初始解其檢驗(yàn)數(shù)都小于等于零。 在單純形法中，原問(wèn)題的最優(yōu)解滿(mǎn)足：對(duì)偶單純形法計(jì)算步驟如下：11jjj1 LB=C0Y=BBC B PC B步驟確定原問(wèn)題（ ）的初始基 ，使得所有檢驗(yàn)數(shù)，即是對(duì)偶可行解，建立初始單純形表

14、。-1B-1-1-12 X =B b0minB bB b0B bllj步驟檢查基變量的取值，若，則已得最優(yōu)解，計(jì)算停；否則求（） （）（）jkkk 0=min/0/Xljljljl步驟3 若所有a，則原問(wèn)題無(wú)可行解，計(jì)算停；否則，計(jì)算aaa確定對(duì)應(yīng)的為旋入變量。k4 lk2l步驟以a 為主元作（ ， ）旋轉(zhuǎn)變換，得新的單純形表，轉(zhuǎn)步驟 ?？梢宰C明，按上述方法進(jìn)行迭代，所得解始終是對(duì)偶可行解。 例1 已知線(xiàn)性規(guī)劃問(wèn)題 試分析1和2分別在什么范圍內(nèi)變化時(shí)，問(wèn)題的最優(yōu)解不變。4 靈敏度分析靈敏度分析 1122121212max(2)(3)2212416. .515,0zxxxxxstxx x一、目標(biāo)

15、函數(shù)中系數(shù)一、目標(biāo)函數(shù)中系數(shù)Cj的靈敏度分析的靈敏度分析 分析：此例中目標(biāo)函數(shù)的系數(shù)cj的變化僅僅影響到檢驗(yàn)數(shù)j的變化，所以將Cj的變化直接反映到最終單純形表中。 解：當(dāng)1=2=0時(shí)，上述LP問(wèn)題的最終單純形表如上表所示。（i）對(duì)基變量x1的目標(biāo)函數(shù)系數(shù)進(jìn)行靈敏度分析：將1的變化反映到最終單純形表中：表中的解仍為最優(yōu)解的條件是：-1-1/210 -1/5+1/510 故有-211時(shí)，該LP問(wèn)題的最優(yōu)解不變。（ii）類(lèi)似的可以得到，其他條件不變的情況下，2-1時(shí)，該LP問(wèn)題的最優(yōu)解不變。-2/5+1/5（3+ 2 ）二、約束條件右端常數(shù)項(xiàng)二、約束條件右端常數(shù)項(xiàng)bi的靈敏度分析的靈敏度分析例2 L

16、P問(wèn)題121212212max501003002400A. .250B,0zxxxxxxstxx x設(shè)備臺(tái)時(shí)原料原料分別分析右端常數(shù)項(xiàng)在什么范圍內(nèi)變化時(shí)，最優(yōu)基不變。分析：原問(wèn)題的最終單純形表如下為，11*111012 110200100bBb 1*15050 20250bb15025右端常數(shù)項(xiàng)的靈敏度分析：（i）使問(wèn)題最優(yōu)基不變的條件是 （ii）類(lèi)似的，使問(wèn)題最優(yōu)基不變的第二個(gè)約束條件右端常數(shù)項(xiàng)的變化范圍是：2-50 (iii）同樣，-50350 即200250+3300時(shí)，對(duì)偶價(jià)格不變，原問(wèn)題的最優(yōu)基不會(huì)發(fā)生變化。三、增加一個(gè)量的靈敏度分析三、增加一個(gè)量的靈敏度分析實(shí)際中，增加一個(gè)變量的計(jì)

17、算步驟如下：實(shí)際中，增加一個(gè)變量的計(jì)算步驟如下：（1）計(jì)算）計(jì)算 ;（2）計(jì)算）計(jì)算 ；（3）若）若 ，只需將，只需將 和和 的值直接反映到最終單純形的值直接反映到最終單純形表中，原最優(yōu)解不變；表中，原最優(yōu)解不變；若若 ，則按單純形法繼續(xù)迭代計(jì)算。，則按單純形法繼續(xù)迭代計(jì)算。1jjjjBjczcC BP1jjpBp0jjpj0j例例3 在例在例1中，若增加一個(gè)變量中，若增加一個(gè)變量x6，有，有c6=4，P6=(2,4,5)T，試分析問(wèn)，試分析問(wèn)題的最優(yōu)解的變化。題的最優(yōu)解的變化。解：解：61/2 01/52242 0 3214/5441 0 1/544 3 1001/555 166041PB

18、P 代入最后一張單純形表中，有16 例5：某工廠(chǎng)計(jì)劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原料的消耗，以及資源的限制，如下表所示：資源限制設(shè)備11300臺(tái)時(shí)原料A21400千克原料B01250千克 該工廠(chǎng)每生產(chǎn)一單位產(chǎn)品可獲利50元，每生產(chǎn)一單位產(chǎn)品可獲利100元，問(wèn)工廠(chǎng)應(yīng)分別生產(chǎn)多少個(gè)產(chǎn)品和 產(chǎn)品才能使工廠(chǎng)獲利最多？補(bǔ)充（約束方程系數(shù)矩陣A靈敏度分析）該問(wèn)題的數(shù)學(xué)模型為： OBF: MAX 50 x1+100 x2. S.T. x1+x2 300, 2x1+x2 400, x2 250 xj 0 迭代次數(shù)基變量CB x1 x2 s1 s2 s3 b比值bi/a

19、ij 50 100 0 0 0 2x1S2x2500100 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 15050250Zj 50 100 50 0 50 0 0 -50 0 -5027500jjjzc 其最終單純形表如下： 現(xiàn)假設(shè)該廠(chǎng)除了生產(chǎn)、產(chǎn)品外，現(xiàn)試制成一種新產(chǎn)品，已知生產(chǎn)產(chǎn)品，每件需要設(shè)備2臺(tái)時(shí)，并消耗A原料0.5公斤，B原料1.5公斤，獲利150元，問(wèn)該廠(chǎng)是否應(yīng)該生產(chǎn)該產(chǎn)品和生產(chǎn)多少？ 解：顯然x3是非基變量。主要來(lái)計(jì)算x3的檢驗(yàn)數(shù)。經(jīng)過(guò)初等行變換，x3所在列的系數(shù)變成：025175150,1755 . 11005 . 0505 . 125 . 05 . 15 .

20、021001121016666zcz這時(shí)，61pB迭代次數(shù)基變量CB x1 x2 s1 s2 s3 x3 b比值 50 100 0 0 0 150 x1S2x2500100 1 0 1 0 -1 0.5 0 0 -2 1 1 -2 0 1 0 0 1 1.55050250Zj 50 100 50 0 50 175 0 0 -50 0 -50 -2527500jjjzc 新單純形表如下： 假設(shè)上例題中產(chǎn)品的工藝結(jié)構(gòu)有了改進(jìn)，這時(shí)生產(chǎn)1件產(chǎn)品需要設(shè)備1.5臺(tái)時(shí)，并消耗A原料2公斤，B原料1公斤，獲利160元，問(wèn)該廠(chǎng)的原生產(chǎn)計(jì)劃是否需要修改？035125160,12511005 . 050105 . 0125 . 11001121016666zcz這時(shí)，61pB 解：x3所在列的系數(shù)變成：迭代次數(shù)基變量CB x1 x2 s1 s2 s3 x3 b比值 50 100 0 0 0 160 2x1S2x2500100 1 0 1 0 -1 0.5 0 0 -2 1 1 0 0 1 0 0 1 15050250100250Zj 50 100 50 0 50 125 0 0 -50 0 -50 3527500jjjzc 新單純形表如下：迭代次數(shù)基變量CB x1 x2 s1 s2 s3 x3 b