第七章 對偶問題和對偶單純形法ppt課件

1、第七章 對偶問題和對偶單純形法一、問題的提出一、問題的提出二、對偶問題和原問題二、對偶問題和原問題的轉換的轉換三、對偶規(guī)劃的性質三、對偶規(guī)劃的性質四、對偶單純形法四、對偶單純形法五、交替單純形法五、交替單純形法一、問題的提出一、問題的提出v原問題：原問題：a和和b產量各為多少可以使產量各為多少可以使利潤最大？利潤最大？25010C40012B30011A資源限量資源限量ba 產品產品設備設備 10050利潤利潤一、問題的提出一、問題的提出v原原LP 模型：模型：v Max z= 50 x1+100 x2 s.t：1x1+1x2300 2x1+1 x2400 0 x1+1 x2250 x1 0，

2、 x2 0一、問題的提出一、問題的提出v若考慮將三種設備出租，如何合理確定若考慮將三種設備出租，如何合理確定各設備的租金各設備的租金y1、 y2 、 y3 （元（元/臺時）？臺時）？v目標函數(shù)：目標函數(shù)：min z= 300y1+400 y2+250 y3v約束條件：約束條件：y1+2y2 50v y1+ y2+ y3 100v y1、 y2、y3 0一、問題的提出一、問題的提出v這樣兩個線性規(guī)劃問題就是一對對偶問這樣兩個線性規(guī)劃問題就是一對對偶問題。題。v稱其中一個為原問題稱其中一個為原問題LP問題），另一問題），另一個為對偶問題個為對偶問題DLP問題）。問題）。v由于它們內在的聯(lián)系，可以根

3、據(jù)其中一由于它們內在的聯(lián)系，可以根據(jù)其中一個模型，寫出其對偶問題的模型。個模型，寫出其對偶問題的模型。二、對偶問題和原問題的轉換二、對偶問題和原問題的轉換vLP問題和問題和DLP問題的關系：問題的關系： 規(guī)范形規(guī)范形(LP) Max z = cT x s.t. Ax b x 0(DLP) Min f = bT ys.t. AT y c y 0二、對偶問題和原問題的轉換二、對偶問題和原問題的轉換v1、對于規(guī)范型，直接按對應關系轉換、對于規(guī)范型，直接按對應關系轉換v例：例： Max z= 20 x1+ 8 x2 +6 x3 s.t： 8x1+ 3x2 +2x3 250 2x1+x2 50 4x1+

4、3x3 150 x1 ，x2 ，x3 0v寫出該線性規(guī)劃問題的對偶問題。寫出該線性規(guī)劃問題的對偶問題。二、對偶問題和原問題的轉換二、對偶問題和原問題的轉換v則對偶問題為：則對偶問題為：vMin f=250 y1+ 50 y2 + 150 y3v s.t： 8y1+ 2y2 +4y3 20v 3y1+y2 8v 2 y1+3y3 6v y1 ，y2 ，y3 0二、對偶問題和原問題的轉換二、對偶問題和原問題的轉換v2、對于非規(guī)范形式，先化為規(guī)范形式、對于非規(guī)范形式，先化為規(guī)范形式v例：例： 寫出線性規(guī)劃模型的對偶問題寫出線性規(guī)劃模型的對偶問題vMin z= 3x1+ 4 x2 +6 x3 v s.

5、t： x1+ 3x2 -2x3 + x4 25v 2x1+7x3 + 2x4 60v 2x1+2x2-4x3 30v x1 ，x2 ，x4 0 ，x3 無非負約束無非負約束二、對偶問題和原問題的轉換二、對偶問題和原問題的轉換v首先轉換為規(guī)范形首先轉換為規(guī)范形vMin z= 3x1+ 4 x2 +6 x3v變?yōu)樽優(yōu)镸ax(-z)= -3x1- 4 x2 -6 x3 v約束條件約束條件x1+ 3x2 -2x3 + x4 25v等同于等同于x1+ 3x2 -2x3 + x4 25和和v x1+ 3x2 -2x3 + x4 25聯(lián)立聯(lián)立二、對偶問題和原問題的轉換二、對偶問題和原問題的轉換v2x1+7x

6、3 + 2x4 60可轉化為可轉化為v-2x1-7x3 - 2x4 - 60vx3 無非負約束，則令無非負約束，則令x3 x3- x3vx3- x3 0v則原則原LP模型可以化為規(guī)范形：模型可以化為規(guī)范形：二、對偶問題和原問題的轉換二、對偶問題和原問題的轉換vMax (-z)= -3x1- 4 x2 -6 x3+6 x3 v s.t： x1+ 3x2 -2 x3+2 x3 + x4 25v -x1- 3x2 +2 x3-2 x3 - x4 -25v -2x1-7 x3+ 7x3 - 2x4 -60v 2x1+2x2-4 x3+4 x3 30v x1 ,x2 ,x3, x3 ,x4 0二、對偶問

7、題和原問題的轉換二、對偶問題和原問題的轉換v故故DLP可寫出：可寫出：vMin f25 y1-25 y2 -60 y3 +30 y4v s.t： y1- y2 -2 y3 +2y4 -3v 3y1-3y2 +2y4 -4v -2y1+2y2 -7y3 -4 y4 -6v 2y1-2y2 +7y3 +4y4 6v y1-y2 -2y3 0v y1 ，y2 ，y3 ，y4 ，y5 0二、對偶問題和原問題的轉換二、對偶問題和原問題的轉換v將將DLP模型整理可得：模型整理可得：vMin f25 y5+60 y3 +30 y4v s.t： y5+2 y3 +2y4 -3v 3y5+2y4 -4v -2y

8、5+7y3 -4y4 -6v y5+2y3 0v y5 無非負約束，無非負約束， y3 0，y4 0LP與DLP的一般對應關系原問題原問題LP對偶問題對偶問題DLP目標函數(shù)目標函數(shù)maxzminf目標函數(shù)目標函數(shù)變量變量xj（j1，2n）n個個n個個約束條件約束條件j （j1，2n）00無約束無約束約束條件約束條件i （i1，2m）m個個m個個變量變量yj（i1，2m）00無約束無約束目標函數(shù)變量的系數(shù)目標函數(shù)變量的系數(shù)cj（j1，2n）約束條件右端項約束條件右端項cjT（j1，2n）約束條件右端項約束條件右端項bi（i1，2m）目標函數(shù)變量的系數(shù)目標函數(shù)變量的系數(shù)biT（i1，2m）練習練習

9、v寫出下面寫出下面LP問題的問題的DLP模型模型vMin z= x1+ 2 x2 +5 x3 v s.t： 2x1+ 3x2 +x3 10v 3x1+x2 + x3 50v x1+x3 20v x1 0 ，x2 0 ，x3 無非負約束無非負約束三、對偶規(guī)劃的性質三、對偶規(guī)劃的性質v1、對稱性：、對稱性：v對偶問題的對偶是原問題。對偶問題的對偶是原問題。v2、弱對偶性：、弱對偶性：v若若X是原問題是原問題max的可行解，的可行解，Y是對是對偶問題偶問題min的可行解，則存在的可行解，則存在CXbTY三、對偶規(guī)劃的性質三、對偶規(guī)劃的性質v推論推論 a ： 原問題任一可行解的目標函數(shù)值是其對偶原問題

10、任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界；反之對偶問題任一可行解問題目標函數(shù)值的下界；反之對偶問題任一可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界。的目標函數(shù)值是其原問題目標函數(shù)值的上界。v推論推論b：若原問題解無界，則其對偶問題無可行解；：若原問題解無界，則其對偶問題無可行解；若對偶問題解無界，則原問題無可行解。（逆命題若對偶問題解無界，則原問題無可行解。（逆命題不成立）不成立）v推論推論c：若原問題有可行解而對偶問題無可行解，：若原問題有可行解而對偶問題無可行解，則原問題無界；反之，對偶問題有可行解而原問題則原問題無界；反之，對偶問題有可行解而原問題無可行解，則對偶問題解無界。無

11、可行解，則對偶問題解無界。三、對偶規(guī)劃的性質三、對偶規(guī)劃的性質v3、最優(yōu)性：、最優(yōu)性：v若若x,y分別是原問題和對偶問題的可行解分別是原問題和對偶問題的可行解,且且cx=bTy ，那么，那么x,y分別為原問題和對分別為原問題和對偶問題的最優(yōu)解。偶問題的最優(yōu)解。三、對偶規(guī)劃的性質三、對偶規(guī)劃的性質v4、強對偶性：、強對偶性：v若原問題和對偶問題都有可行解，則兩若原問題和對偶問題都有可行解，則兩者都有最優(yōu)解，且最優(yōu)目標函數(shù)值相等。者都有最優(yōu)解，且最優(yōu)目標函數(shù)值相等。三、對偶規(guī)劃的性質三、對偶規(guī)劃的性質v5、互補松弛定理：、互補松弛定理：v在原問題的最優(yōu)解中，如果對應某一約束條在原問題的最優(yōu)解中，如

12、果對應某一約束條件的對偶變量值不為件的對偶變量值不為0，則該約束條件取嚴格，則該約束條件取嚴格等式；反之，如果約束條件取嚴格不等式，等式；反之，如果約束條件取嚴格不等式，則其對應的對偶變量一定為則其對應的對偶變量一定為0，即，即v若若Yi*0，則有，則有aijxj*biv假設假設aijxj*bi ，則有，則有Yi*0對偶問題解的意義對偶問題解的意義若若x*,y* 分別為分別為LP和和DLP的最優(yōu)解，的最優(yōu)解， 那么，那么， cx* = bT y* 。 根據(jù)根據(jù) f = bTy*=b1y1*+b2y2*+bmym* 可知可知 f / bi = yi* yi*表示表示 bi 變化變化1個單位對目標

13、個單位對目標 f 產生的影響。產生的影響。對偶問題解的意義對偶問題解的意義因此：對偶問題的最優(yōu)解就是原問題中相應因此：對偶問題的最優(yōu)解就是原問題中相應資源常數(shù)項的影子價格。資源常數(shù)項的影子價格。若若B是初始基在最優(yōu)表中的形式，影子價格是初始基在最優(yōu)表中的形式，影子價格向量向量 Y* = BCB確定影子價格在原問題和對偶問題中的對應確定影子價格在原問題和對偶問題中的對應關系后，可以由原問題最優(yōu)單純形表求對偶關系后，可以由原問題最優(yōu)單純形表求對偶問題最優(yōu)解。問題最優(yōu)解。對偶問題解的意義對偶問題解的意義v如范例最優(yōu)表：如范例最優(yōu)表：2-250-5000 j=cjzj21250250507550zj2

14、501001075x25011-2000 x450-1010150 x10007550比值比值bi/ai2bx5x4x3x2x1CB基變基變量量XB迭代迭代次數(shù)次數(shù)對偶問題解的意義對偶問題解的意義v原問題的最優(yōu)解為：原問題的最優(yōu)解為：vx1=50 x2=250 x4=50v對偶問題的最優(yōu)解為：對偶問題的最優(yōu)解為：vy1=50 y2=0 y3=50 （影子價格）（影子價格）四、對偶單純形法四、對偶單純形法v最優(yōu)表特征：最優(yōu)表特征：基向量為基向量為單位向量單位向量右端項右端項非負非負2-500-5000 j=cjzj275005005010050zj25010010100 x25011-2000

15、x450-1010150 x100010050比值比值bi/ai2bx5x4x3x2x1CB基變基變量量XB迭代迭代次數(shù)次數(shù)檢驗數(shù)非正檢驗數(shù)非正四、對偶單純形法四、對偶單純形法v單純形法的迭代：單純形法的迭代：保證基向量保證基向量為單位向量為單位向量保證右端保證右端項非負項非負000010050 j=cjzj0500000zj250100100 x5400010120 x4300001110 x300010050比值比值bi/ai2bx5x4x3x2x1CB基變基變量量XB迭代迭代次數(shù)次數(shù)檢驗數(shù)由正檢驗數(shù)由正變?yōu)榉钦優(yōu)榉钦叶隧椨叶隧椨韶撟冇韶撟優(yōu)榉秦摓榉秦摫ＷC基向量保證基向量為單位向量為單

16、位向量四、對偶單純形法四、對偶單純形法v對偶單純形法的迭代：對偶單純形法的迭代：基變基變量量XBCBx1x2x3x4x5x6b501000000 x1501010-1050 x4000-211050 x2100010010250 x6000-100-201-3000zj5010050050027500 j00-500-500保證檢驗保證檢驗數(shù)非正數(shù)非正四、對偶單純形法四、對偶單純形法v在滿足對偶單純形迭代前提條件的表上確定在滿足對偶單純形迭代前提條件的表上確定主行和出基變量：主行和出基變量：基變基變量量XBCBx1x2x3x4x5x6b501000000 x1501010-1050 x4000

17、-211050 x2100010010250 x6000-100-201-3000zj50100500500 27500 j00-500-5001、按、按最小最小b值原則值原則確定主確定主行和出行和出基變量基變量四、對偶單純形法四、對偶單純形法v確定主列和進基變量確定主列和進基變量0-500-5000 j2.550-2011-10 x525000010100 x201000 x65 j /alj2750005010050zj-30000-10000 x6501-2000 x450010150 x10010050bx4x3x2x1CB基變基變量量XB1、按最、按最小比值原小比值原則確定主則確定主

18、列和進基列和進基變量變量主元主元四、對偶單純形法四、對偶單純形法基變量基變量XBCBx1x2x3x4x5x6b501000000 x150101.500-1/20200 x4000-2.5101/20-100 x210001-0.5001/20100 x50000.501-1/20150zj5010025002.520000 j00-5000-2.5 j /alj20v迭代：與原始單純形法一樣，通過行變換將迭代：與原始單純形法一樣，通過行變換將主列變?yōu)橹髟獮橹髁凶優(yōu)橹髟獮?的單位列。的單位列。四、對偶單純形法四、對偶單純形法基變基變量量XBCBx1x2x3x4x5x6b501000000 x1

19、5010060-1/50140 x30001-40-1/5040 x2100010-201/25120 x5000021-1/25130zj5010001000319000 jcjzj000-1000-3v所有所有b值都大于值都大于0，該表中的解為可行解，故，該表中的解為可行解，故最優(yōu)解為最優(yōu)解為140，120，40，0，130，0）。）。四、對偶單純形法四、對偶單純形法對偶單純形法過程：對偶單純形法過程：1、建立初始對偶單純形表、建立初始對偶單純形表,對應一個基對應一個基本解本解,所有檢驗數(shù)均非正；所有檢驗數(shù)均非正；2、若、若b0,則得到最優(yōu)解則得到最優(yōu)解,停頓；若有停頓；若有b 0 則選其

20、中最小的則選其中最小的bl所在的第所在的第l行的基變行的基變量為出基變量；量為出基變量；四、對偶單純形法四、對偶單純形法3、若所有、若所有alj0( j = 1,2,n )，則原問，則原問題無可行解題無可行解,停頓；若有停頓；若有alj0 則選則選=min j / aljalj0)最小原則）最小原則）先確定離基變量先確定離基變量（最小（最小b0值原則）；值原則）；后確定進基變量后確定進基變量（比值（比值 j /alj (alj0)最最小原則）小原則）原始基本解原始基本解的進化的進化從可行到最優(yōu)從可行到最優(yōu)從非可行到可行從非可行到可行（最優(yōu)）（最優(yōu)）五、交替單純形法五、交替單純形法v不管是原始單純形法，還是對偶單純形不管是原始單純形法，還是對偶單純形法，初始表都有前提條件。法，初始表都有前提條件。v如果兩種方法的初始條件都不能滿足，如果兩種方法的初始條件都不能滿足，怎么辦？怎么辦？五、交替單純形法五、交替單純形法v例如：例如： Max z= -3x1+2x2-x3 v s.t： -x1-x2+x3 - 4v 2x1+3x2 +x320v 3x1+x2+x3 28v x1 ，x2 ，x3 0五、交替單純形法五、交替單純形法基變量基變量XBCBx1x2x3x4x5x6b-32-1000 x40-1-11100-4x50231010