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

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

3、與標準形式相反變變 形形對偶變量對偶變量Y令令Y=Y第3節 對偶與靈敏度分析8其他形式的對偶問題其他形式的對偶問題若模型中原問題變量的符號與標準形式相反設設X= -X對偶問題對偶問題對偶變量對偶變量Y第3節 對偶與靈敏度分析9對偶問題典式對偶問題典式第3節 對偶與靈敏度分析其他形式的對偶問題其他形式的對偶問題10關系：一般對偶關系關系：一般對偶關系第3節 對偶與靈敏度分析線性規劃的對偶關系線性規劃的對偶關系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節 對偶與靈敏度分析線性規劃的對偶關系線性規劃的對偶關系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節 對偶與靈敏度分析線性規

5、劃的對偶關系線性規劃的對偶關系13練習練習解解 第3節 對偶與靈敏度分析線性規劃的對偶關系線性規劃的對偶關系14對偶問題的性質對偶問題的性質 性質性質1 對稱性對稱性 對偶問題的對偶是原問題。對偶問題的對偶是原問題。 第3節 對偶與靈敏度分析15性質性質2 弱對偶性弱對偶性 設設X, Y分別為原問題與對偶問題的任意分別為原問題與對偶問題的任意 可行解，則存在可行解，則存在 CX Yb 第3節 對偶與靈敏度分析對偶問題的性質對偶問題的性質16性質性質3 無界性無界性 若原問題對偶問題為無界解，則其對若原問題對偶問題為無界解，則其對偶問題原問題無可行解。偶問題原問題無可行解。原問題原問題對偶問題對

6、偶問題注：逆命題不真，原問題與對偶問題均無可行解。注：逆命題不真，原問題與對偶問題均無可行解。第3節 對偶與靈敏度分析對偶問題的性質對偶問題的性質17性質性質4 可行解是最優解時的性質可行解是最優解時的性質 設設X是原問題的可行解，是原問題的可行解，Y是對偶問題的可行解。當是對偶問題的可行解。當CX=Yb時，時，X，Y分別是原問題分別是原問題與對偶問題的最優解。與對偶問題的最優解。 第3節 對偶與靈敏度分析對偶問題的性質對偶問題的性質18性質性質5 對偶定理對偶定理 若原問題有最優解，那么對偶問題也有最若原問題有最優解，那么對偶問題也有最優解；且目標函數相等。優解；且目標函數相等。 第3節 對

7、偶與靈敏度分析對偶問題的性質對偶問題的性質19性質性質6 兼容性兼容性 該性質主要討論原問題檢驗數與對偶問題解該性質主要討論原問題檢驗數與對偶問題解的關系。原問題與對偶問題標準化后，具有相同的分量個數。的關系。原問題與對偶問題標準化后，具有相同的分量個數。這些分量相互之間存在著對應的關系。原問題單純形表的檢這些分量相互之間存在著對應的關系。原問題單純形表的檢驗數行對應其對偶問題的一個基本解，且目標函數值相等。驗數行對應其對偶問題的一個基本解，且目標函數值相等。我們把這樣一對基本解稱為互補基本解。我們把這樣一對基本解稱為互補基本解。 第3節 對偶與靈敏度分析對偶問題的性質對偶問題的性質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節 對偶與靈敏度分析對偶問題的性質對偶問題的性質21 (P)的基本解 與(D)的基本解 相互對應, 且二者目標值相等。我們把這樣一對基本解 與 ，稱為(P)與(D)的互補基本解。 (P) 目目 標標 值值 (D) 序序號號 極極點點 基基 本本 解解 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節 對偶與靈敏度分析對偶問題的性質對偶問題的性質22性質性質7 互補松弛性互補松弛性 設設X，Y分別為原問題和對偶問題的可分別為原問題和對偶問題的可行解，那么行解，那么YXS=0 和和 YSX=0；當且僅當，；當且僅當，X，Y為最優為最優解。解。 第3節 對偶與靈敏度分析對偶問題的性質對偶問題的性質23 由對偶問題的第由對偶問題的第1個約束條件，可知對偶問題無

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

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

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