管理運(yùn)籌學(xué)-02-5對(duì)偶原理ppt課件

1、第3節(jié) 對(duì)偶與靈敏度分析2一、 線性規(guī)劃的對(duì)偶關(guān)系二、 線性規(guī)劃的對(duì)偶性質(zhì)三、靈敏度分析四、對(duì)偶關(guān)系的經(jīng)濟(jì)解釋第第3節(jié)節(jié) 對(duì)偶與靈敏度分析對(duì)偶與靈敏度分析3線性規(guī)劃的對(duì)偶關(guān)系線性規(guī)劃的對(duì)偶關(guān)系 由于原擬用于生產(chǎn)每件甲產(chǎn)品的1個(gè)A工時(shí)和3個(gè)c工時(shí)能創(chuàng)造3百元利潤(rùn)，所以出租上述數(shù)量的各資源的盈利起碼應(yīng)不低于3百元。 2y1+y2+4y3 2 2140A B C D車間車間 產(chǎn)品產(chǎn)品 甲甲 乙乙單耗工時(shí)單耗工時(shí)/ /件）件）加工能力加工能力（工時(shí)（工時(shí)/ /天）天）利潤(rùn)利潤(rùn) 2 3 2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 12 x1 ， x2 0 第3節(jié) 對(duì)偶與靈敏度分

2、析4線性規(guī)劃的對(duì)偶關(guān)系線性規(guī)劃的對(duì)偶關(guān)系第3節(jié) 對(duì)偶與靈敏度分析5線性規(guī)劃的對(duì)偶關(guān)系線性規(guī)劃的對(duì)偶關(guān)系 min w = 8y1 + 12y2 + 36y3 y1 + 3y3 3 2y2 + 4y3 5 y1 , y2, y3 0 s.t. X*= (4,6)Tz* = 42第3節(jié) 對(duì)偶與靈敏度分析6線性規(guī)劃的對(duì)偶關(guān)系線性規(guī)劃的對(duì)偶關(guān)系對(duì)偶結(jié)構(gòu)用矩陣表示為： max z = CX AXb X0 s.t. (原問題原問題):(對(duì)偶問題對(duì)偶問題): min w = Yb YAC Y0 s.t.記向量和矩陣為： 第3節(jié) 對(duì)偶與靈敏度分析7其他形式的對(duì)偶問題其他形式的對(duì)偶問題若模型中原問題約束條件的符號(hào)

3、與標(biāo)準(zhǔn)形式相反變變 形形對(duì)偶變量對(duì)偶變量Y令令Y=Y第3節(jié) 對(duì)偶與靈敏度分析8其他形式的對(duì)偶問題其他形式的對(duì)偶問題若模型中原問題變量的符號(hào)與標(biāo)準(zhǔn)形式相反設(shè)設(shè)X= -X對(duì)偶問題對(duì)偶問題對(duì)偶變量對(duì)偶變量Y第3節(jié) 對(duì)偶與靈敏度分析9對(duì)偶問題典式對(duì)偶問題典式第3節(jié) 對(duì)偶與靈敏度分析其他形式的對(duì)偶問題其他形式的對(duì)偶問題10關(guān)系：一般對(duì)偶關(guān)系關(guān)系：一般對(duì)偶關(guān)系第3節(jié) 對(duì)偶與靈敏度分析線性規(guī)劃的對(duì)偶關(guān)系線性規(guī)劃的對(duì)偶關(guān)系11 例例2-21 max z = 8 x1 + 5 x2 - x1 +2 x2 4 3 x1 - x2 = 7 2 x1 +4 x2 8 x1, x2 0 min w = 4y1 +7y2

4、 +8y3 - y1 +3 y2 + 2y3 8 2 y1 - y2 + 4y3 5 y1 0 , y2 自在，自在，y3 0s.t.s.t.y1 y2y3第3節(jié) 對(duì)偶與靈敏度分析線性規(guī)劃的對(duì)偶關(guān)系線性規(guī)劃的對(duì)偶關(guān)系12例例2-22max z = 2y1+5y2+1y3 2 y1+3 y2 +1y3 3 1 y1 -5 y2 +1y3 2 3 y1 +1y3 -1y1 0,y2 0,s.t.解解 min = 3 x1+2 x2 -1 x3 2 x1+1 x2+3x3 2 3 x1 -5 x2 5 1 x1+1 x2+1 x3 = 1 x10, x3 0 s.t. 第3節(jié) 對(duì)偶與靈敏度分析線性規(guī)

5、劃的對(duì)偶關(guān)系線性規(guī)劃的對(duì)偶關(guān)系13練習(xí)練習(xí)解解 第3節(jié) 對(duì)偶與靈敏度分析線性規(guī)劃的對(duì)偶關(guān)系線性規(guī)劃的對(duì)偶關(guān)系14對(duì)偶問題的性質(zhì)對(duì)偶問題的性質(zhì) 性質(zhì)性質(zhì)1 對(duì)稱性對(duì)稱性 對(duì)偶問題的對(duì)偶是原問題。對(duì)偶問題的對(duì)偶是原問題。 第3節(jié) 對(duì)偶與靈敏度分析15性質(zhì)性質(zhì)2 弱對(duì)偶性弱對(duì)偶性 設(shè)設(shè)X, Y分別為原問題與對(duì)偶問題的任意分別為原問題與對(duì)偶問題的任意 可行解，則存在可行解，則存在 CX Yb 第3節(jié) 對(duì)偶與靈敏度分析對(duì)偶問題的性質(zhì)對(duì)偶問題的性質(zhì)16性質(zhì)性質(zhì)3 無(wú)界性無(wú)界性 若原問題對(duì)偶問題為無(wú)界解，則其對(duì)若原問題對(duì)偶問題為無(wú)界解，則其對(duì)偶問題原問題無(wú)可行解。偶問題原問題無(wú)可行解。原問題原問題對(duì)偶問題對(duì)

6、偶問題注：逆命題不真，原問題與對(duì)偶問題均無(wú)可行解。注：逆命題不真，原問題與對(duì)偶問題均無(wú)可行解。第3節(jié) 對(duì)偶與靈敏度分析對(duì)偶問題的性質(zhì)對(duì)偶問題的性質(zhì)17性質(zhì)性質(zhì)4 可行解是最優(yōu)解時(shí)的性質(zhì)可行解是最優(yōu)解時(shí)的性質(zhì) 設(shè)設(shè)X是原問題的可行解，是原問題的可行解，Y是對(duì)偶問題的可行解。當(dāng)是對(duì)偶問題的可行解。當(dāng)CX=Yb時(shí)，時(shí)，X，Y分別是原問題分別是原問題與對(duì)偶問題的最優(yōu)解。與對(duì)偶問題的最優(yōu)解。 第3節(jié) 對(duì)偶與靈敏度分析對(duì)偶問題的性質(zhì)對(duì)偶問題的性質(zhì)18性質(zhì)性質(zhì)5 對(duì)偶定理對(duì)偶定理 若原問題有最優(yōu)解，那么對(duì)偶問題也有最若原問題有最優(yōu)解，那么對(duì)偶問題也有最優(yōu)解；且目標(biāo)函數(shù)相等。優(yōu)解；且目標(biāo)函數(shù)相等。 第3節(jié) 對(duì)

7、偶與靈敏度分析對(duì)偶問題的性質(zhì)對(duì)偶問題的性質(zhì)19性質(zhì)性質(zhì)6 兼容性兼容性 該性質(zhì)主要討論原問題檢驗(yàn)數(shù)與對(duì)偶問題解該性質(zhì)主要討論原問題檢驗(yàn)數(shù)與對(duì)偶問題解的關(guān)系。原問題與對(duì)偶問題標(biāo)準(zhǔn)化后，具有相同的分量個(gè)數(shù)。的關(guān)系。原問題與對(duì)偶問題標(biāo)準(zhǔn)化后，具有相同的分量個(gè)數(shù)。這些分量相互之間存在著對(duì)應(yīng)的關(guān)系。原問題單純形表的檢這些分量相互之間存在著對(duì)應(yīng)的關(guān)系。原問題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問題的一個(gè)基本解，且目標(biāo)函數(shù)值相等。驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問題的一個(gè)基本解，且目標(biāo)函數(shù)值相等。我們把這樣一對(duì)基本解稱為互補(bǔ)基本解。我們把這樣一對(duì)基本解稱為互補(bǔ)基本解。 第3節(jié) 對(duì)偶與靈敏度分析對(duì)偶問題的性質(zhì)對(duì)偶問題的性質(zhì)20 :

8、max z = 3x1 +5x2 x1 8 2x2 12 3x1 + 4x2 36 x1 ， x2 0s.t.( ( P1)P1):min w=8y1+12y2+36y3 y1 +3y3 3 2y2+4y3 5 y1 , y2, y3 0s.t.( ( D1)D1): max z = 3x1 +5x2 x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36 x1, x2 , x3 , x4 , x5 0s.t.( ( Ps)Ps):min w=8y1+12y2+36y3 y1 +3y3 -y4 = 3 2y2+4y3 -y5 = 5 y1 , y2 , y3 ,

9、y4 , y5 0s.t.( ( Ds)Ds)X*= (4 ,6)TY*= (0 , ,1)T *b (4 ,6 ,4, 0 ,0)T *= (0, ,1, 0 ,0)Tz*= 42 = w*第3節(jié) 對(duì)偶與靈敏度分析對(duì)偶問題的性質(zhì)對(duì)偶問題的性質(zhì)21 (P)的基本解 與(D)的基本解 相互對(duì)應(yīng), 且二者目標(biāo)值相等。我們把這樣一對(duì)基本解 與 ，稱為(P)與(D)的互補(bǔ)基本解。 (P) 目目 標(biāo)標(biāo) 值值 (D) 序序號(hào)號(hào) 極極點(diǎn)點(diǎn) 基基 本本 解解 k Xk可可 行行 z = w Yk可可 行行 基基 本本 解解 k 1 O (0 ，0 ，8 ， 12 ， 36) 是是 0 否否 (0 ，0 ，0

10、，- -3 ，- -5) 2 A (8 ，0 ，0 ， 12 ， 12) 是是 24 否否 (3 ，0 ，0 ， 0 ，- -5) 3 D (0 ，6 ，8 ，0 ， 12) 是是 30 否否 (0 ， 5/2 ， 0 ，- -3 ， 0) 4 B (8 ，3 ，0 ，6 ， 0) 是是 39 否否 (- 3/4 ， 0 ， 5/4 ， 0 ， 0) 5 C (4 ，6 ，4 ，0 ， 0) 42 (0 ， 1/2 ， 1 ，0 ，0) 6 E (12 ， 0 ，- -4 ， 12 ， 0) 36 (0 , , 0 , , 1 , , 0 , , - -1) 7 G (0 ，9 ，8 ，- -

11、6 ， 0) 否否 45 是是 (0 , , 0 , , 5/4 , , 3/4 , , 0) 8 F (8 ，6 ，0 ，0 , , - 12) 12) 否否 54 是是 (3 , , 5/2 , , 0 , , 0 , , 0) 第3節(jié) 對(duì)偶與靈敏度分析對(duì)偶問題的性質(zhì)對(duì)偶問題的性質(zhì)22性質(zhì)性質(zhì)7 互補(bǔ)松弛性互補(bǔ)松弛性 設(shè)設(shè)X，Y分別為原問題和對(duì)偶問題的可分別為原問題和對(duì)偶問題的可行解，那么行解，那么YXS=0 和和 YSX=0；當(dāng)且僅當(dāng)，；當(dāng)且僅當(dāng)，X，Y為最優(yōu)為最優(yōu)解。解。 第3節(jié) 對(duì)偶與靈敏度分析對(duì)偶問題的性質(zhì)對(duì)偶問題的性質(zhì)23 由對(duì)偶問題的第由對(duì)偶問題的第1個(gè)約束條件，可知對(duì)偶問題無(wú)

12、可行解；根據(jù)對(duì)偶問題的性質(zhì)，個(gè)約束條件，可知對(duì)偶問題無(wú)可行解；根據(jù)對(duì)偶問題的性質(zhì)，可知原問題只存在無(wú)界解和無(wú)可行解兩種情況。任意找到原問題的一個(gè)可行解，可知原問題只存在無(wú)界解和無(wú)可行解兩種情況。任意找到原問題的一個(gè)可行解，如如X=（1，0T，因此可以判斷原問題有可行解，因此原問題解的情況應(yīng)為無(wú)界，因此可以判斷原問題有可行解，因此原問題解的情況應(yīng)為無(wú)界解。解。第3節(jié) 對(duì)偶與靈敏度分析對(duì)偶問題的性質(zhì)對(duì)偶問題的性質(zhì)24第3節(jié) 對(duì)偶與靈敏度分析對(duì)偶問題的性質(zhì)對(duì)偶問題的性質(zhì)25第3節(jié) 對(duì)偶與靈敏度分析對(duì)偶問題的性質(zhì)對(duì)偶問題的性質(zhì)26對(duì)偶單純形法對(duì)偶單純形法第3節(jié) 對(duì)偶與靈敏度分析27對(duì)偶單純形法對(duì)偶單純

13、形法第3節(jié) 對(duì)偶與靈敏度分析28對(duì)偶單純形法對(duì)偶單純形法（2為使迭代后表中對(duì)偶問題的解仍為可行解，令為使迭代后表中對(duì)偶問題的解仍為可行解，令稱稱ark為主元素，為主元素，xk為進(jìn)基變量；為進(jìn)基變量；（3進(jìn)行矩陣行變換，得到新的基。重復(fù)以上步驟。進(jìn)行矩陣行變換，得到新的基。重復(fù)以上步驟。4當(dāng)所有的當(dāng)所有的bi0時(shí)，當(dāng)前解是最優(yōu)解。時(shí)，當(dāng)前解是最優(yōu)解。 當(dāng)存在當(dāng)存在br0，且對(duì)所對(duì)應(yīng)的行中所有分量，且對(duì)所對(duì)應(yīng)的行中所有分量arj0。則第。則第r行的約束方程為行的約束方程為第3節(jié) 對(duì)偶與靈敏度分析29對(duì)偶單純形法對(duì)偶單純形法 當(dāng)存在當(dāng)存在br0，且對(duì)所對(duì)應(yīng)的行中所有分量，且對(duì)所對(duì)應(yīng)的行中所有分量ar

14、j0。則第。則第r行的約束方程為行的約束方程為 因因arj0j=m+1,n）,又又br0，故不可能存在，故不可能存在xj0j=1,n的解，故原問題無(wú)可行解，這時(shí)對(duì)偶問題的解，故原問題無(wú)可行解，這時(shí)對(duì)偶問題的目標(biāo)函數(shù)值無(wú)界。的目標(biāo)函數(shù)值無(wú)界。第3節(jié) 對(duì)偶與靈敏度分析 例例2-26 用對(duì)偶單純形法求解以下問題用對(duì)偶單純形法求解以下問題30對(duì)偶單純形法對(duì)偶單純形法第3節(jié) 對(duì)偶與靈敏度分析31 列出初始單純形表列出初始單純形表Cj -4 -12 -18 0 0第3節(jié) 對(duì)偶與靈敏度分析對(duì)偶單純形法對(duì)偶單純形法32Cj -4 -12 -18 0 0當(dāng)前基既是原始可行基，又是對(duì)偶可行基，因而是最優(yōu)基。當(dāng)前基既是原始可行基，又是對(duì)偶可行基，因而是最優(yōu)基。最優(yōu)解為最優(yōu)解為x1=0，x2=3/2，x3=1，max z，=-36，即即min z=36第3節(jié) 對(duì)偶與靈敏度分析對(duì)偶