1、 對偶的定義 對偶問題的性質 對偶的經濟解釋SUES1、掌握寫出對偶問題的方法，原問題與其對偶問題的對應關系2、掌握對偶問題的基本理論和性質 3、理解影子價格的定義和意義4、理解并掌握對偶單純形方法的思想和步驟5、掌握線性規劃靈敏度分析 (1) 資源數量 bi 發生變化的分析 (2) 目標函數中價值系數 cj 發生變化的分析對偶問題概念：對偶問題概念：任何一個線性規劃問題都有一個與之相對應任何一個線性規劃問題都有一個與之相對應的線性規劃問題，如果前者稱為原始問題，后者的線性規劃問題，如果前者稱為原始問題，后者就稱為就稱為“對偶對偶”問題。問題。對偶問題是對原問題從另一角度進行的描述對偶問題是對

2、原問題從另一角度進行的描述其最優解與原問題的最優解有著密切的聯系，在其最優解與原問題的最優解有著密切的聯系，在求得一個線性規劃最優解的同時也就得到對偶線求得一個線性規劃最優解的同時也就得到對偶線性規劃的最優解，反之亦然。性規劃的最優解，反之亦然。對偶理論就是研究線性規劃及其對偶問題的對偶理論就是研究線性規劃及其對偶問題的理論，是線性規劃理論的重要內容之一。理論，是線性規劃理論的重要內容之一。 ABC擁有量工 時1113材 料1479單件利潤233321332maxxxxZ0, 0, 09743. .321321321xxxxxxxxxtsABC擁有量工 時1113材 料1479單件利潤233假

3、設有客戶提出要求，購買工廠所擁有的假設有客戶提出要求，購買工廠所擁有的工時和材料，為客戶加工別的產品，由客工時和材料，為客戶加工別的產品，由客戶支付工時費和材料費。那么工廠給工時戶支付工時費和材料費。那么工廠給工時和材料制訂的最低價格應是多少，才值得和材料制訂的最低價格應是多少，才值得出賣工時和材料出賣工時和材料 ?ABC擁有量工 時1113材 料1479單件利潤233出賣資源獲利應不少于生產產品的獲利出賣資源獲利應不少于生產產品的獲利; 約束約束價格應該盡量低，這樣，才能有競爭力價格應該盡量低，這樣，才能有競爭力; 目標目標價格應該是非負的價格應該是非負的 ABC擁有量工 時1113材 料1

4、479單件利潤233用用y1和和y2分別表示工時和材料的出售價格分別表示工時和材料的出售價格總利潤最小總利潤最小 min W=3y1+9y2保證保證A產品利潤產品利潤 y1+y22 保證保證B產品利潤產品利潤 y1+4y23 保證保證C產品利潤產品利潤 y1+7y23 售價非負售價非負 y10 y20ABC擁有量工 時1113材 料1479單件利潤2332193minyyW0, 037342. .21212121yyyyyyyyts321332maxxxxZ0, 0, 09743. .321321321xxxxxxxxxts1 122minnnZc xc xc x111112121222221

5、212. .,0nnmmmnnmnxbaaaaaaxbstaaaxbx xx1122maxmmWb yb yb y111121112222221212. .,0mmnnmnmnmycaaaaaaycstaaaycy yy對稱形式的對偶問題原始問題原始問題min f(x)=CTXs.t.AXbX 0對偶問題對偶問題max z(y)=bTys.t. ATyCy 0minbACTCATbTmaxmnmn對偶問題的特點對偶問題的特點l（1）目標函數在一個問題中是求最大值在）目標函數在一個問題中是求最大值在另一問題中則為求最小值另一問題中則為求最小值l（2）一個問題中目標函數的系數是另一個）一個問題中目

6、標函數的系數是另一個問題中約束條件的右端項問題中約束條件的右端項l（3）一個問題中的約束條件個數等于另一）一個問題中的約束條件個數等于另一個問題中的變量數個問題中的變量數l（4）原問題的約束系數矩陣與對偶問題的）原問題的約束系數矩陣與對偶問題的約束系數矩陣互為轉置矩陣約束系數矩陣互為轉置矩陣 一 般線性規劃問題的對偶問題1 122minnnfc xc xc xnjjmnmnmmnnnnxbxaxaxabxaxaxabxaxaxa1), 0(0),(),(),(22112222212111212111或符號不限1122maxmmzb yb yb y11121211121222221122,)1(

7、 , )( , )( , )0(0mmmmnnmnmnjima ya ya yca ya yayca ya yaycy 符號不限 或對偶問題對應表對偶問題對應表原問題（對偶問題）原問題（對偶問題）對偶問題（原問題）對偶問題（原問題）目標函數目標函數min目標函數目標函數max約束條件：約束條件： m個個第第i個約束類型為個約束類型為“”第第i個約束類型為個約束類型為“”第第i個約束類型為個約束類型為“” 變量數：變量數： m個個第第i個變量個變量0第第i個變量個變量0第第i個變量是自由變量個變量是自由變量 變量數：變量數：n個個第第j個變量個變量 0第第j個變量個變量 0第第j個變量是自由變量

8、個變量是自由變量 約束條件：約束條件：n個個第第j個約束類型為個約束類型為“”第第j個約束類型為個約束類型為“”第第j個約束類型為個約束類型為“” 例寫出如下LP問題的對偶問題123min23fxxx123123123123,3264235390,xxxxxxxxxxxx符號不限0,123max659zyyy123123123123,y0,y03412232353yyyyyyyyyy符號不限對偶問題對偶問題的性質1、對偶的對偶就是原始問題、對偶的對偶就是原始問題max z=-CTXs.t. -AX-bX 0min y=-bTWs.t. -ATW-CW 0max y=bTWs.t. ATWCW

9、0min z=CTXs.t. AXb X 0對偶的定義對偶的定義對偶的定義對偶的定義2、對偶問題的性質（1）弱對偶性（可行解的目標函數值之間的關系）弱對偶性（可行解的目標函數值之間的關系） 設設X、Y分別是原始問題和對偶問題的可行解分別是原始問題和對偶問題的可行解 cjxjbiyiminTfC X. .0TA YCstYmaxTzb YTTTTTC XA YXY AXY bb Y. .0AXbstX11 (1,2, ) (1,2,) (1,2, ) (1,2,)jinmjjiijijixjny imc xb yxjny im 如果是原問題的可行解是其對偶問題的可行解且有則是原問題的最優解是其對

10、偶問題的最優解（3）最優性）最優性（2）無界性）無界性如果原問題（對偶問題）具有無界解，如果原問題（對偶問題）具有無界解，則其對偶問題（原問題）無可行解。則其對偶問題（原問題）無可行解。 無界性在一對對偶問無界性在一對對偶問題，若其中一個問題可行題，若其中一個問題可行但目標函數無界，則另一但目標函數無界，則另一個問題不可行；反之不成個問題不可行；反之不成立。這也是對偶問題的無立。這也是對偶問題的無界性。界性。關于無界性有如下結論：關于無界性有如下結論：問題無界問題無界無可無可行解行解無可行解無可行解無可行解無可行解問題無界問題無界對偶問題對偶問題原問題原問題 0,024 2max2121212

11、1xxxxxxxxZ無界無界如：如：（原）（原） 0,012 24min21212121yyyyyyyyW無可無可行解行解（對）（對）已知已知12123123123 : max22 21,0Zxxxxxxxxx x x 原1212121212: min221 2 0,0Wyyyyyyyyy y對試用對偶理論證明原問題無界。試用對偶理論證明原問題無界。 解：解： =（0.0.0）是）是 原問題的一個可行解，而原問題的一個可行解，而 對偶對偶問題問題 的第一個約束條件不能成立（因為的第一個約束條件不能成立（因為y1 , y2 0)。因。因此，對偶問題不可行，可知，原問題無界。此，對偶問題不可行，可

12、知，原問題無界。_X（4）強對偶性（最優解的目標函數之間的關系）強對偶性（最優解的目標函數之間的關系）如果原問題有最優解，則其對偶問題也一定有如果原問題有最優解，則其對偶問題也一定有最優解，且兩者的目標函數值相等最優解，且兩者的目標函數值相等在線性規劃問題的最優解中，在線性規劃問題的最優解中，如果對應某一約束條件的對偶變量值為非零，如果對應某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；則該約束條件取嚴格等式；反之如果約束條件取嚴格不等式，反之如果約束條件取嚴格不等式，則其對應的對偶變量一定為零。則其對應的對偶變量一定為零。即即1100niijjijnijjiijya xba xby如

13、果，則如果，則123123123123min 23. .33122,0 xxxstxxxxxxx xx例2給定線性規劃問題121 11(,),7 7Tyy y已知對偶問題的最優解為試用互補松弛性質求原問題的最優解.1212121212max2. .322331,0yys tyyyyyyyy12312,0,y yxy y將最優解的值代入約束條件，得第3個約束為嚴格不等式，由互補松弛性得又由于的值均大于零，因此原問題的兩個約束條件應取等式，故有12312331232xxxxxx解：先寫出它的對偶問題12123min4,5/7,( ,)(4/7,5/7,0)23/7TTxxxx xxf求解后得到/7

14、故原問題的最優解為l練習已知線性規劃問題123451234512345min 23523. .2342330,1,2,5jxxxxxstxxxxxxxxxxxj(1,0,0,0,1)Tx 已知原問題的最優解為試用互補松弛性質找出對偶問題的最優解.影子價格對偶的經濟解釋1、原始問題是利潤最大化的生產計劃問題0 xxxxxxbxxaxaxabxxaxaxabxxaxaxa. t . sxcxcxczmaxmn2n1nn21mmnnmn22m11m22nnn222212111nnn1212111222211單位產品的利潤單位產品的利潤產品產量產品產量總利潤總利潤資源限量資源限量單位產品消耗的資源單位

15、產品消耗的資源剩余的資源剩余的資源消耗的資源消耗的資源2、對偶問題112211121211112122222211221212min. .0mmmmmmmmnnmnmm nnmmmm nzbwb wb wsta wa wa wwca wa wa wwca wa wa wwcwwwwww 資源限量資源限量資源價格資源價格總利潤總利潤對偶問題是資源定價問題，對偶問題的最優解對偶問題是資源定價問題，對偶問題的最優解w1、w2、.、wm稱為稱為m種資源的影子價格（種資源的影子價格（Shadow Price）原始和對偶問題都取得最優解時，原始和對偶問題都取得最優解時，最大利潤最大利潤 max z=min

16、 y3、資源影子價格的性質影子價格越大，說明這種資源越是相對緊缺影子價格越大，說明這種資源越是相對緊缺影子價格越小，說明這種資源相對不緊缺影子價格越小，說明這種資源相對不緊缺如果最優生產計劃下某種資源有剩余，這種資源如果最優生產計劃下某種資源有剩余，這種資源的影子價格一定等于的影子價格一定等于0種資源的邊際利潤第種資源的增量第最大利潤的增量iibzwiooi1122iimmzbwb wbwb wmmiii2211wbw)bb(wbwbzziiwbzw1w2wm4、產品的機會成本機會成本機會成本表示減少一件產品所節省的資源可以增加的利潤表示減少一件產品所節省的資源可以增加的利潤mmjiij2j2

17、1j1wawawawa增加單位資源可以增加的利潤增加單位資源可以增加的利潤減少一件產品可以節省的資源減少一件產品可以節省的資源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211l對偶單純形法的原理l對偶單純形法的應用步驟l對偶單純形法舉例l對偶單純形法的應用條件l對偶單純形法的優點和缺點l對偶單純形法并不是求解對偶問題解的方法，而是利用對偶理論求解原問題的解的方法。l單純形法是在原問題可行的基礎上，通過迭是在原問題可行的基礎上，通過迭代使代使對偶

18、問題達到可行，從而得到最優解。達到可行，從而得到最優解。根據對偶問題的對稱性，若根據對偶問題的對稱性，若原問題不可行而不可行而對偶問題可行，那么在保持對偶問題可行的可行，那么在保持對偶問題可行的基礎上，逐步迭代使基礎上，逐步迭代使原問題達到可行，也可達到可行，也可得到最優解。得到最優解。對于標準線性規劃問題：可行基B 若B對應的基本解是可行解最優基B 若B對應的基本解是最優解對偶可行基B 若CBB-1是對偶問題可行解 即 C-CBB-1A0 或 檢驗數0 min fCX. .Tst A YC0. .XbAXtsmax zbY最優基B可行基B 對偶可行基B單純形法可行基B 保持可行性 對偶可行基

19、B對偶單純形法可行基B 保持對偶可行性 對偶可行基B應用前提： 有一個基，其對應的基滿足: 單純形表的檢驗數行全部非正（對偶可行）； 變量取值可有負數（非可行解）。l找一個基（可以不是可行的），建立初始對偶單純形表，檢驗數全部非負；l若b列元素非負，則已經是最優基。反之，則取相應行的基變量為出基變量；l為保證能對基的可行性有所改進，則將來的主元應該為負數；為保證下一個基還能是對偶可行基，應使檢驗數仍為非負的。l主元變換 )3.2.1(01451232102215129min321321321321jxxxxxxxxxxxxxZj 例題例題:用對偶單純形法求解用對偶單純形法求解解:將上述模型轉化

20、為 01451232102215129max61632153214321321xxxxxxxxxxxxxxxxZ cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-10-2-2-11000 x5-12-2-3-10100 x6-14-1-1-5001(-9/-1.-12/-1. -15/-5)cj-Z 0-9-12-15000i列初始單純形表，取b中比較小的行對應的變量為換出基變量。cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-36/5-9/5-9/5010-1/50 x5-46/5-9/5-14/5001-1/5-15x314/51/51/5100-1/5 (-30/-9.-45/-14 .-15/-1)-Z 42-6-9000-3icj-9-12 -15000cBxBbx1x2x3x4x5x60 x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14(-3/-9.-45/-9. -33/-1)-15x315/71/140101/14-3/14-Z 501/7-3/14000-45/14-33/14c