【正文】 1 2 31 2 31 2 31 2 31 2 322212:10 , , 0MinW u u uu u uu u uSTu u uu u u? ? ?? ? ???? ? ???? ? ? ??? ??? 無 約 束1 2 32M a x Z x x x? ? ?:ST???????1 2 3x x x??1 2 3x x x??1 2 32 x x x??2121 0x ? 20x ?3x 無 約 束???13 原問題 對偶問題 目標函數(shù) Max z Min w 變量 n個 約束條件 n個 ≥ ≤ = ≤0 ≥0 無約束 約束條件 m個 ≥ ≤ = 變量 m個 ≥0 ≤0 無約束 約束條件右端項 目標函數(shù)變量的系數(shù) 目標函數(shù)變量的系數(shù) 約束條件右端項 原問題 對偶問題 14 第二節(jié) LP問題的對偶理論 若 X(0),Y(0)分別為 (L),(D)的可行解，則有 CX(0)≤Y(0)b 定理 1(弱對偶定理 ): 極大化原問題目標函數(shù)值總是不大于其對偶問題的目標函數(shù)值。 稱變量 yi為第 一個 LP的第 i個對偶變量， 或第 一個 LP的第 i約束相應(yīng)的對偶變量 4 二、對偶問題 （ 1）對稱 LP問題的定義 Max Z C XA X bSTX..0??????Min W Y bY A CSTY..0??????（ 2）對稱 LP問題的對偶問題 ()L ()DMin W Y bY A CSTY..0??????第一類對稱形式 第二類對稱形式 Max Z C XA X bSTX..0??????（ 1）變量為非負； （ 2）約束條件為不等式。1 第二章 線性規(guī)劃的對偶理論 窗含西嶺千秋雪，門泊東吳萬里船 本章主要內(nèi)容 ： ? 線性規(guī)劃的對偶問題概念、理論及經(jīng)濟意義 ? 線性規(guī)劃的對偶單純形法 ? 線性規(guī)劃的靈敏度分析 2 第一節(jié) 對偶問題的提出 材料 產(chǎn)品 甲 乙 丙 丁 單件 收益 A 3 2 1 1 2022 B 4 1 3 2 4000 C 2 2 3 4 3000 限額 600 400 300 200 假設(shè)工廠考慮不進行生產(chǎn)而把全部資源都轉(zhuǎn)讓，問如何定價這些資源，既能使其獲利不低于安排生產(chǎn)所獲得的收益，又能使資源租讓具有競爭力。 一、引例 Max Z = 2022x1+4000x2+3000x3 . 3x1+4x2+2x3≤600 2x1+ x2+2x3≤400 x1+3x2+3x3≤300 x1+2x2+4x3≤200 x1, x2, x3≥0 ???Min W =600y1+400y2+300y3+200y4 . 3y1+2y2+ y3+ y4≥2022 4y1+ y2+3y3+2y4≥4000 2y1+2y2+3y3+4y4≥3000 y1, y2, y3, y4≥0 ???x1 x2 x3 y1 y2 y3 y4 3 比較上述模型，可以得出兩者之間的一些關(guān)系： 1. 兩個問題，一個是極大化，另一個是極小化； 2. 一個問題的 變量 數(shù)等于另一問題的 方程 數(shù)，反之亦然； 3. 一個問題的 目標 函數(shù)系數(shù)是另一個問題的約束方程 右端 常數(shù)，反之亦然； 4. 兩個問題的約束方程系數(shù)矩陣互為轉(zhuǎn)置。 對于 max ，約束為“ ?” ； 對于 min，約束為“ ?” 5 例 1 寫出下列 LP問題的對偶問題 對偶 Max Z =2x1+3x2 . x1+ 2x2≤8 4x1 ≤ 16 4x2≤ 12 x1 ,x2 ≥0 ???Min W =8y1+16y2+12y3 . y1+4y2 ≥2 2y1 +4y3 ≥3 y1 ,y2,y3 ≥0 ???6 （ 3）對偶問題的對偶是原問題 推導(dǎo)過程 變形 對偶 變 形 對偶 變 形 ()LMax Z=CX . AX≤b X≥0 ???()DMin W=Yb . YA≥C Y≥0 ???Max W ’= Yb . YA≤ C Y≥0 ???Min Z ’= (C)X . (A)X≥ (b) X≥0 ???()DDMax W ’= Y(b) . Y(A)≤ (C) Y≥0 ???7 121 2 31 2 31 2 31 2 3343 3 4 748:1, , 0Min W x xx x xx x xSTx x xx x x??? ? ???? ? ???? ? ??? ??1 2 31 2 31 2 31 2 31 2 3783 4 334: 4 0, , 0Max Z y y yy y yy y ySTy y yy y y? ? ?? ? ???? ? ? ???? ? ??? ??例 2 寫出下列 LP問題的對偶問題 解 : 上述 LP問題的 對偶問題為： 8 三、非對稱 LP問題的對偶問題 例 3 寫出下列 LP問題的對偶問題 解：用 x2= x2’, x3=x3’x3’’代入上述 LP問題，并將其化為第一類對稱形式 Max Z = x1+2x2+x3 x1+x2x3 ≤2 . x1 x2+x3 = 1 2x1+x2+x3 ≥2 x1≥0, x2≤0 ,x3無約束 ??? Max Z = x1－ 2x2’ +x3’ － x3’’ x1 － x2’ － x3’+x3’’ ≤ 2 x1+x2’+x3’ － x3’’ ≤ 1 . － x1 － x2’ － x3’+x3’’ ≤－ 1 － 2x1+x2’ － x3’+x3’’ ≤－ 2 x1, x2’, x3’, x3’’ ≥0 ?????x1 x2+x3 ≤ 1 x1 x2+x3 ≥ 1 x1 x2+x3 ≤ 1 x1 +x2x3 ≤ 1 2x1x2x3 ≤ 2 9 上述第一類對稱形式 LP問題的對偶問題為： 則上述問 題變?yōu)椋? Min W =2y1+y2 － y3－ 2y4 y1+y2 － y3－ 2y4 ≥ 1 － y1+y2 － y3 +y4 ≥2 . － y1+y2 － y3－ y4 ≥ 1 y1 － y2+y3 +y4 ≥1 y1, y2, y3, y4 ≥0 ???Min W =2u1+u2+2u3 u1+u2+2u3 ≥1 . u1 － u2+ u3 ≤2 － u1+u2+ u3 =1 u1≥0, u3≤0 ,u2無約束 ???令 u1= y1 u2=y2－ y3 u3=－ y4 Max Z = x1－ 2x2’ +x3’ － x3’’ x1 － x2’ － x3’+x3’’ ≤ 2 x1+x2’+x3’ － x3’’ ≤ 1 . x1 － x2’ － x3’+x3’’ ≤－ 1 － 2x1+x2’ － x3’+x3’’ ≤－ 2 x1, x2’, x3’, x3’’ ≥0 ?????y1+y2 y3 y4 ≤ 1 y1y2+y3 y4 ≤ 2 10 (D) Min W =2u1+u2+2u3 u1+u2+2u3 ≥1 . u1 u2+ u3 ≤2 u1+u2+ u3 =1 u1≥0, u3≤0 ,u2無約束 ???(L) Max Z = x1+2x2+x3 x1+x2x3 ≤2 . x1 x2+x3 = 1 2x1+x2+x3 ≥2 x1≥0, x2≤0 ,x3無約束 ???對偶關(guān)系： 一個問題第 i個變量的約束情況決定另一問題第 i個約束不等式的方向，反之亦然。 證明： max z=CX。X≥0……(L) min w=Yb。Y≥0……(D) 由于 X(0)是 (L)的可行解，有 AX(0)≤b, X(0)≥0. 由于 Y(0)是 (D)的可行解，有 Y(0)≥0. Y(0)左乘不等式組 AX(0)≤b的兩邊得： Y(0)AX(0)≤ Y(0)b (1) 15 min w=Yb。Y≥0……(D) 又 Y(0)A≥C 用 X(0)(X(0)≥0)右乘上式，得 Y(0)AX(0) ≥CX(0) (2) 由（ 1），（ 2） 得： CX(0)≤Y(0)AX(0)≤Y(0)b 所以 CX(0)≤Y(0)b 16 推論 1(P119) 若對偶問題有無界解，則其原問題無可行解； 若對偶問題無可行解，則其原問題或有無界解或無可行解。 17 推論 2 極大化問題（ L）的任何一個可行解所對應(yīng)的目標函數(shù)值都是其對偶問題 （ D） 目標函數(shù)值的下界。 推論 3 Yb≥CX(0) CX ≤ Y(0)b max z=CX。 X≥0……(L) min w=Yb。 Y≥0……(D) 18 例 4 考慮下面一對 LP問題 其對偶問題為： 由于 X(0) =(1,1,1,1)T, Y(0)=(1,1)T分別為(L),(D)的可行解， Max Z = x1+2x2+3x3 +4x4 x1+2x2+2x3+3x4 ≤20 . 2x1+ x2+3x3+2x4 ≤20 x1,x2,x3,x4 ≥0 ??? Min W = 20y1+20y2 y1+2y2 ≥ 1 2y1+ y2 ≥ 2 . 2y1+3y2 ≥ 3 3y1+2y2 ≥ 4 y1,y2≥0 ???????Z(0)=10 W(0)=40 W≥10 推論 2 Z≤40 推論 3 故 Z≤40,W≥10. 19 例 121 2 31 2 31 2 3m ax221, , 0z x xx x xx x xx x x??? ? ? ?? ? ? ?? 試用對偶理論證明上述線性規(guī)劃問題無最優(yōu)解 證明：首先看到該問題存在可行解，如 X=(0,0,0) 上述問題的對偶問題為 1212121212m i n 22110,0 w y yyyyyyyyy??? ? ??????由第一約束條件知對偶問題無可行解，因原問