運籌學第2章

1、Chapter2 對偶理論 ( Duality Theory ),,單純形法的矩陣描述對偶問題的提出線性規(guī)劃的對偶理論對偶問題的經(jīng)濟解釋－影子價格對偶單純形法靈敏度分析(選講)掌握WinQSB軟件求解對偶規(guī)劃,本章主要內容：,√,√,√,學習要點：1. 理解對偶理論，掌握描述一個線性規(guī)劃問題 的對偶問題。 2. 能夠運用對偶單純形法來求解線性規(guī)劃問題。

2、 3. 會用互補松弛條件來考慮一對對偶問題的界。 4. 了解影子價格、靈敏度分析以及用WinQSB求 解對偶規(guī)劃問題。,2.1 單純形法的矩陣描述,,,,,每一列的含義？每個表中的B和B-1的查找？,單純形法的矩陣描述,單純形法的矩陣描述,,單純形法的矩陣描述,單純形法的矩陣描述,單純形法的矩陣描述,2.3 對偶問題的提出,對偶

3、理論是線性規(guī)劃中最重要的理論之一，是深入了解線性規(guī)劃問題結構的重要理論基礎。同時，由于問題提出本身所具有的經(jīng)濟意義，使得它成為對線性規(guī)劃問題系統(tǒng)進行經(jīng)濟分析和敏感性分析的重要工具。那么，對偶問題是怎樣提出的，為什么會產(chǎn)生這樣一種問題呢？,對偶問題的提出,倆家具制造商間的對話：,唉!我想租您的木工和油漆工一用。咋樣？價格嘛……好說，肯定不會讓您兄弟吃虧。,王老板做家具賺了大錢，可惜我老李有高科技產(chǎn)品，卻苦于沒有足夠的木工和油漆工咋辦？只

4、有租咯。,Hi：王老板，聽說近來家具生意好呀，也幫幫兄弟我哦!,家具生意還真賺錢，但是現(xiàn)在的手機生意這么好，不如干脆把我的木工和油漆工租給他，又能收租金又可做生意。,價格嘛……好商量， 好商量。只是…...,王 老 板,李 老 板,引例1,對偶問題的提出,王老板的家具生產(chǎn)模型：x1 、 x2是桌、椅生產(chǎn)量。Z是家具銷售總收入（總利潤）。max Z = 50x1 + 30x2s.t. 4x1+3x2 ≤ 120（

5、木工） 2x1+ x2 ≤ 50 （油漆工） x1，x2 ≥ 0原始線性規(guī)劃問題，記為（P）,王老板的資源出租模型：y1、 y2單位木、漆工出租價格。W是資源出租租金總收入。min W =120y1 + 50y2s.t. 4y1+2y2 ≥ 50 3y1+ y2 ≥ 30 y1，y2 ≥ 0對偶線性規(guī)劃問題

6、，記為（D）,,,所得不得低于生產(chǎn)的獲利（不吃虧原則）要使對方能夠接受 （競爭性原則）,兩個原則,對偶問題的提出,王老板按（D）的解 y1 、y2出租其擁有的木、漆工資源，既保證了自己不吃虧（出租資源的租金收入并不低于自己生產(chǎn)時的銷售收入），又使得出租價格對李老板有極大的吸引力（李老板所付出的總租金W最少）。,按時下最流行的一個詞，叫什么來著————,對偶問題的提出,設三種資源的使用單價分別為 y1 , y2 , y3,y

7、1 y2 y3,生產(chǎn)單位產(chǎn)品A的資源消耗所得不少于單位產(chǎn)品A的獲利,生產(chǎn)單位產(chǎn)品B的資源消耗所得不少于單位產(chǎn)品B的獲利,y1 +3 y2 ? 40,2y1 + 2 y2 + 2y3 ? 50,引例2,通過使用所有資源對外加工所獲得的收益,W = 30y1 + 60 y2 + 24y3,對偶問題的提出,根據(jù)原則2 ，對方能夠接受的價格顯然是越低越好，因此此問題可歸結為以下數(shù)學模型：,Min W = 30y1 + 60 y2

8、 + 24y3,y1 + 3y2 ? 402y1 + 2 y2 + 2y3 ? 50y1 , y2 , y3 ? 0,,s.t,目標函數(shù),約束條件,原線性規(guī)劃問題稱為原問題，此問題為對偶問題，y1 , y2 , y3為對偶變量，也稱為影子價格,對偶問題的提出,2.4 線性規(guī)劃的對偶理論,,,,,,,,,,,,,,,,,,,,,Max Z= 40x1 +50x2,x1 + 2x2 ? 30

9、3x1 + 2x2 ? 60 2x2 ? 24 x1，x2 ? 0,,s.t,原問題（對偶問題）,對偶問題（原問題）,一、 原問題與對偶問題的對應關系,3個約束2個變量,2個約束 3個變量,線性規(guī)劃的對偶理論,對偶問題的形式,定義 設原線性規(guī)劃問題為 則稱下列線性規(guī)劃問題,為其對偶問題，其中yi (i=1,2,…,m) 稱為對偶變量,上述對偶問題稱為對稱型對偶問題,原問題簡記為(P)，對偶問

10、題簡記為(D),稱問題(P)和(D )為一對對偶問題,線性規(guī)劃的對偶理論,對稱型問題的對偶規(guī)則,1、給每個原始約束條件定義一個非負對偶變量yi(i=1,2,…,m)；2、使原問題的目標函數(shù)系數(shù) cj 變?yōu)槠鋵ε紗栴}約束條 件的右端常數(shù)；3、使原問題約束條件的右端常數(shù) bi 變?yōu)槠鋵ε紗栴}目 標函數(shù)的系數(shù)；4、將原問題約束條件的系數(shù)矩陣轉置，得到其對偶問 題約束條件的系數(shù)矩陣；5、改變約束問題不

11、等號的方向，即將“≤”改為“≥”；6、原問題為“max”型，對偶問題為“min”型。,線性規(guī)劃的對偶理論,原始問題Max Z=CXs.t. AX≤bX ≥0,,,,b,A,C,≤,Max,,,,,,,n,m,對偶問題Min W=Ybs.t.YA≥CY ≥0,,,,≥,Min,C,AT,b,,,,,,,n,m,,,,,,,,,,,,,,,,,,,,,,,,,,線性規(guī)劃的對偶理論,當原問題為求極小值時，對偶問題為求

12、極大值。原始問題中目標函數(shù)的系數(shù)變成對偶問題中約束條件的右端；原始問題中約束條件的右端變成對偶問題中目標函數(shù)的系數(shù)。原始問題約束條件系數(shù)矩陣的轉置對應對偶問題中約束條件的系數(shù)矩陣。原始問題的約束條件個數(shù)決定對偶問題變量的個數(shù)；原始問題變量個數(shù)，決定對偶問題的約束個數(shù)。原始問題的約束方程的匹配形式?jīng)Q定對偶問題變量的符號；原始問題決策變量的符號決定所對應對偶問題的約束方程的匹配形式。,,線性規(guī)劃的對偶理論,求線性規(guī)劃問題的對偶規(guī)劃,

13、解：由原問題的結構可知為對稱型對偶問題,例1,線性規(guī)劃的對偶理論,求線性規(guī)劃問題的對偶規(guī)劃,解：由原問題的結構可知不是對稱型對偶問題，可先化為對稱型，再求其對偶規(guī)劃。,,例2,線性規(guī)劃的對偶理論,求線性規(guī)劃問題的對偶規(guī)劃,解：由原問題的結構可知不是對稱型對偶問題，可先化為對稱型，再求其對偶規(guī)劃。,,例3,線性規(guī)劃的對偶理論,上式已為對稱型對偶問題，故可寫出它的對偶規(guī)劃,令,則上式化為,線性規(guī)劃的對偶理論,對偶問題的非對稱形式,min z

14、= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15,max w=6y1+12y2+8y3+15y4s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3-

15、y4 -1 y1 0,y2 ,y3 0,y4 0,≥,≤,=,≤,unr,≥,≤,≥,=,≤,≥,x1≥0,x2≤0,x3: unr,,線性規(guī)劃的對偶理論,1 原問題為“max”，對偶問題為“min”；2 原問題中目標函數(shù)系數(shù) ci 變?yōu)槠鋵ε紗栴}約束條件的右端常數(shù)；3 原問題約束條件的右端常數(shù) bi 變?yōu)槠鋵ε紗栴}目標函數(shù)的系數(shù)；4 原問題約束條件的系數(shù)矩陣轉置，即為其對偶

16、問題的系數(shù)矩陣；5 原問題的變量個數(shù)n等于其對偶問題的約束條件個數(shù)n，原問題 約束條件的個數(shù)m等于其對偶問題變量的個數(shù)m；6 在求極大值的原問題中，“≤”，“≥”和“=”的約束條件分別對應其對偶變量“≥0”，“≤0”和“無符號限制”；7 在求極大值的原問題中，變量“≥0”，“≤0”和“無符號限制”分別對應其對偶約束條件的“≥”，“≤”和“=”約束.,混合型問題的對偶規(guī)則：,線性規(guī)劃的對偶理論,線性規(guī)劃的對偶理論,Max Z=

17、40x1+ 50x2,x1+2x2 ? 303x1+2x2 ? 60 2x2 ? 24 x1 , x2 ?0,s.t,y1y2y3,Min W = 30y1+ 60y2 + 24y3,y1+3y2 + 0y3 ? 402y1+2y2 + 2y3 ? 50 y1 , y2 , y3 ?0,s.t,Max W′= -30y1- 60y2 - 24y3,,y1+3y2 + 0y3 – y4 =

18、402y1+2y2 + 2y3 – y5 = 50 y1 , y2 , y3 , y4 , y5 ?0,s.t,例4,,,二、 對偶問題的解,線性規(guī)劃的對偶理論,Max W′= -30y1- 60y2 - 24y3 +0(y4 + y5 )-M (y6 + y7 ),,y1+3y2 + 0y3 – y4 + y6 = 402y1+2y2 + 2y3 – y5 + y7 = 50 y1 , y2 , y3 , y4 , y5

19、 ?0,s.t,線性規(guī)劃的對偶理論,,線性規(guī)劃的對偶理論,,線性規(guī)劃的對偶理論,線性規(guī)劃的對偶理論,原問題與其對偶問題的變量與解的對應關系： 在單純形表中，原問題的松弛變量對應對偶問題的變量，對偶問題的剩余變量對應原問題的變量。,線性規(guī)劃的對偶理論,原問題最優(yōu)表,對偶問題最優(yōu)表,線性規(guī)劃的對偶理論,性質1 對稱性定理：對偶問題的對偶是原問題,,,三、 對偶原理,線性規(guī)劃的對偶理論,,,,對偶的定義,簡要證明：,線性規(guī)劃的對偶理論

20、,性質2 弱對偶原理(弱對偶性)：設 和 分別是問題(P)和(D)的可行解，則必有,推論1: 原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界；反之，對偶問題任意可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界。,證明：,(1) 當X和Y為原問題和對偶問題的一個可行解,有,原問題目標函數(shù)值,對偶問題目標函數(shù)值,線性規(guī)劃的對偶理論,推論2: 在一對對偶問題（P）和（D）中，若其中一個問題可行但目標函數(shù)無界，則另一個問

21、題無可行解；反之不成立。這也是對偶問題的無界性。,線性規(guī)劃的對偶理論,推論3：在一對對偶問題（P）和（D）中，若一個可行（如P），而另一個不可行（如D），則該可行的問題目標函數(shù)值無界。,已知原問題(LP)，,試估計它的目標函數(shù)值的界,并驗證弱對偶定理.,例5,線性規(guī)劃的對偶理論,解：,問題(LP)的對偶問題(DP)為,(DP),,線性規(guī)劃的對偶理論,由觀察可知,分別是原問題和對偶問題的可行解。,，弱對偶定理成立。,且由推論1知，對偶問題

22、目標函數(shù)W的下界為10，原問題目標函數(shù)Z的上界為40。,且原問題的目標函數(shù)值為,對偶問題的目標函數(shù)值為,故,,,線性規(guī)劃的對偶理論,例：利用對偶性質判斷下面問題有無最優(yōu)解,例6,解：此問題的對偶問題為,不能成立，因此對偶問題不可行。故由推論3知原問題無界。,,,,線性規(guī)劃的對偶理論,性質3 最優(yōu)性定理：如果 是原問題的可行解， 是其對偶問題的可行解，并且:,則 是原問題的最優(yōu)解， 是其對偶問題的最優(yōu)解。,線性規(guī)

23、劃的對偶理論,性質4 強(主)對偶性：若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標函數(shù)值相等。,還可推出另一結論：若一對對偶問題中的任意一個有最優(yōu)解，則另一個也有最優(yōu)解，且目標函數(shù)最優(yōu)值相等；若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。,一對對偶問題的關系，有且僅有下列三種：都有最優(yōu)解，且目標函數(shù)最優(yōu)值相等；兩個都無可行解；一個問題無界，則另一問題無可行解。,線性規(guī)劃的對偶理論,證明：當X*為原問題的

24、一個最優(yōu)解，B為相應的最優(yōu)基，通過引入松弛變量Xs，將問題(P)轉化為標準型,,,,,,,說明Y*可行,,,線性規(guī)劃的對偶理論,問題:（1）由性質4可知，對偶問題最優(yōu)解的表達式 Y*=?,（2）求 Y*是否有必要重新求解(D)?,—不必?？梢詮脑瓎栴}（P）的單純形終表獲得。,,線性規(guī)劃的對偶理論,性質5 互補松弛性：設X0和Y0分別是P問題 和 D問題 的可行解，則它們分別是最優(yōu)解的充要條件是：,其中：Xs、Ys為松弛變量。,在線性規(guī)

25、劃問題的最優(yōu)解中，若對應某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；另一方面，如果約束條件取嚴格不等式，則其對應的變量一定為零。,緊約束與松約束,線性規(guī)劃的對偶理論,一個約束稱為緊約束，如果該約束在所有最優(yōu)解上的值使左右取等號。 即我們把嚴格等式約束稱為緊約束（或起作用約束）.,不是緊約束的約束稱為松約束。 即把某一最優(yōu)解處取嚴格不等式的約束稱為松約束（或不起作用約束）。,對于最優(yōu)解X*和Y*而言，松約束

26、的對偶約束是緊約束.,以上關系稱為對偶問題的互補松弛關系或松緊關系。在計算上，若已知一個問題的最優(yōu)解，則可利用互補松弛條件求另一個問題的最優(yōu)解.,緊約束與松約束,松緊關系,非常重要,線性規(guī)劃的對偶理論,證: (必要性）,,,線性規(guī)劃的對偶理論,Max Z=CXs.t.AX+XS=bX, XS ≥0,Min W=Ybs.t. YA-YS=CW, WS ≥0,XTYS=0YTXS=0,,,,,,,,,,,,m,n,

27、=,Y,YS,AT,-I,C,,,n,,,,,,,,,,,=,A,XS,I,b,,,,n,m,m,X,原始問題和對偶問題變量、松弛變量的維數(shù),線性規(guī)劃的對偶理論,,,,,,,,,x1 xj xn xn+1 xn+i xn+m,對偶問題的變量 對偶問題的松弛變量,原始問題的變量 原始問題的松弛變量,xjym+j=0

28、yixn+i=0(i=1,2,…,m; j=1,2,…,n)在一對變量中，其中一個大于0，另一個一定等于0,線性規(guī)劃的對偶理論,性質5的應用：該性質給出了已知一個問題最優(yōu)解求另一個問題最優(yōu)解的方法，即已知Y＊求X＊或已知X＊求Y＊,互補松弛條件,由于變量都非負，要使求和式等于零，則必定每一分量為零，因而有下列關系： 若Y＊≠0，則Xs必為0；若X＊≠0，則Ys必為0利用上述關系，建立對偶問題（或原問題）的

29、約束線性方程組，方程組的解即為最優(yōu)解。,線性規(guī)劃的對偶理論,已知線性規(guī)劃,的最優(yōu)解是X＊=(6,2,0)T,求其對偶問題的最優(yōu)解Y＊。,解：寫出原問題的對偶問題，即,,標準化,例7,線性規(guī)劃的對偶理論,設對偶問題最優(yōu)解為Y＊＝(y1，y2),由互補松弛性定理可知，X＊和 Y＊滿足：,即：,因為x1≠0，x2≠0，所以對偶問題的第一、二個約束的松弛變量等于零，即y3＝0，y4＝0，帶入方程中：,解此線性方程組得y1=1,y2=1,從而對偶

30、問題的最優(yōu)解為：Y＊=(1,1)，最優(yōu)值w=26。,線性規(guī)劃的對偶理論,已知線性規(guī)劃,的對偶問題的最優(yōu)解為Y＊=(0,-2)，求原問題的最優(yōu)解。,解: 對偶問題是,例8,線性規(guī)劃的對偶理論,設原問題最優(yōu)解為X＊＝(x1，x2 ，x3)T ,由互補松弛性定理知，X＊和 Y＊滿足：,將Y＊帶入由方程可知，y3＝y(tǒng)5＝0，y4＝1。,∵y2=-2≠0 ∴x5＝0又∵y4=1≠0 ∴x2＝0,將x2，x5分別帶入原問題約束方程

31、中，得：,解方程組得：x1=-5,x3=-1, 所以原問題的最優(yōu)解為,X＊=(-5,0,-1)，最優(yōu)值z=-12,線性規(guī)劃的對偶理論,試用對偶原理求解線性規(guī)劃問題,已知其對偶規(guī)劃的最優(yōu)解為,練習,線性規(guī)劃的對偶理論,,解：,該問題的對偶規(guī)劃為,線性規(guī)劃的對偶理論,利用松緊關系，,代入對偶規(guī)劃的約束條件得下列約束是松約束，,,將最優(yōu)解,松約束,緊約束,其對偶約束是緊約束,線性規(guī)劃的對偶理論,設原問題的最優(yōu)解為,緊約束,線性規(guī)劃的對偶理論

32、,對偶規(guī)劃可以用線性規(guī)劃的單純形法求解。由對偶原理可見，原問題與對偶問題之間有緊密聯(lián)系，因此我們能夠通過求解原問題來找出對偶問題的解，反之依然?；パa松弛條件就可以解決由原問題的最優(yōu)解直接求出對偶問題的最優(yōu)解。,對偶問題解的求法,線性規(guī)劃的對偶理論,原問題與對偶問題解的對應關系小結,線性規(guī)劃的對偶理論,思考題,判斷下列結論是否正確，如果不正確，應該怎樣改正？,1）任何線性規(guī)劃都存在一個對應的對偶線性規(guī)劃.2）原問題第i個約束是“≤”

33、約束，則對偶變量yi≥0.3）互為對偶問題，或者同時都有最優(yōu)解，或者同時都無最優(yōu)解.4）對偶問題有可行解，則原問題也有可行解.5）原問題有多重解，對偶問題也有多重解.6）對偶問題有可行解，原問題無可行解，則對偶問題具有無界解.7）原問題無最優(yōu)解，則對偶問題無可行解.8）對偶問題不可行，原問題可能無界解.9）原問題與對偶問題都可行，則都有最優(yōu)解.10）原問題具有無界解，則對偶問題不可行.11）對偶問題具有無界解，則原問題

34、無最優(yōu)解.12）若X*、Y*是原問題與對偶問題的最優(yōu)解，則X*=Y*.,線性規(guī)劃的對偶理論,2.5 影子價格,,單位產(chǎn)品消耗的資源(噸/件)),原始問題是利潤最大化的生產(chǎn)計劃問題,總利潤(元),產(chǎn)品產(chǎn)量(件),單位產(chǎn)品的利潤(元/件),消耗的資源(噸),剩余的資源(噸),資源限量(噸),,,,,,,影子價格,對偶問題——資源定價問題,,,,對偶問題是資源定價問題，對偶問題的最優(yōu)解y1、y2、...、ym稱為m種資源的影子價格（S

35、hadow Price）,原始和對偶問題都取得最優(yōu)解時，最大利潤 Max z=Min w,總利潤(元),資源限量(噸),資源價格(元/噸),影子價格,在一對 P 和 D 中，若 P 的某個約束條件的右端項常數(shù) bi （第 i 種資源的擁有量）增加一個單位時，所引起目標函數(shù)最優(yōu)值z* 的改變量稱為第 i 種資源的影子價格，其值等于D問題中對偶變量 yi*。,由對偶問題得基本性質可得：,1. 影子價格的數(shù)學分析：,影子價格,2. 影子價

36、格的經(jīng)濟意義1）影子價格是一種邊際價格在其它條件不變的情況下，單位資源數(shù)量的變化所引起的目標函數(shù)最優(yōu)值的變化。即對偶變量yi 就是第 i 種資源的影子價格。即：,影子價格,資源影子價格的性質,影子價格越大，說明這種資源越是相對緊缺影子價格越小，說明這種資源相對不緊缺如果最優(yōu)生產(chǎn)計劃下某種資源有剩余，這種資源的影子價格一定等于0,影子價格,,,0,,,,X2,X1,X= (15,7.5) Z=975,,X= (15.5,7.25

37、) Z=982.5,,,X= (14.5,8.25) Z=992.5,,,,,,0,,,,X2,X1,X= (15,7.5) Z=975,,,,0,,,,X2,X1,X= (15,7.5) Z=975,,,X= (14.5,8.25) Z=992.5,,,,0,,,,X2,X1,X= (15,7.5) Z=975,,X= (15.5,7.25) Z=982.5,,,,,0,,,,X2,X1,X= (15,7.5) Z=975,,,,,0

38、,,,,X2,X1,X= (15,7.5) Z=975,,X= (15.5,7.25) Z=982.5,,,X= (14.5,8.25) Z=992.5,,2）影子價格是一種機會成本影子價格是在資源最優(yōu)利用條件下對單位資源的估價，這種估價不是資源實際的市場價格。因此，從另一個角度說，它是一種機會成本。,若第i 種資源的單位市場價格為mi ，則有當yi* > mi 時，企業(yè)愿意購進這種資源，單位純利為yi*－mi ，則有利可圖

39、；當yi* < mi 時，企業(yè)有償轉讓這種資源，可獲單位純利mi－yi * ，否則，企業(yè)無利可圖，甚至虧損。,結論：若yi* > mi 則購進資源 i，可獲單位純利yi*－mi ； 若yi* < mi則轉讓資源 i ，可獲單位純利mi－yi 。,影子價格,,y1y2ym,產(chǎn)品的機會成本,機會成本表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤,增加單位資源可以增加的利潤,減少一件產(chǎn)品可以節(jié)省的資源,影子價

40、格,,,,機會成本,利潤,差額成本,產(chǎn)品的差額成本（Reduced Cost）,,差額成本=機會成本 - 利潤,影子價格,,3）影子價格在資源利用中的應用 根據(jù)對偶理論的互補松弛性定理: Y*Xs=0 , YsX*=0表明生產(chǎn)過程中如果某種資源 bi 未得到充分利用時，該種資源的影子價格為0；若當資源資源的影子價格不為0時，表明該種資源在生產(chǎn)中已耗費完。,影子價格,yixn+i=0,如果yi >0，則xn

41、+i =0,如果xn+i >0，則yi =0,影子價格大于0的資源，在最優(yōu)生產(chǎn)計劃條件下沒有剩余,ym+jxj=0,如果ym+j >0，則xj =0,如果xj >0，則ym+j =0,最優(yōu)生產(chǎn)計劃條件下有剩余的資源，其影子價格等于0,差額成本大于0（機會成本大于利潤）的產(chǎn)品，不安排生產(chǎn),安排生產(chǎn)的產(chǎn)品，差額成本等于0（機會成本等于利潤）,互補松弛關系經(jīng)濟解釋,影子價格,4）影子價格對單純形表計算的解釋,單純形表中的檢驗

42、數(shù),其中cj表示第j種產(chǎn)品的價格; 表示生產(chǎn)該種產(chǎn)品所消耗的各項資源的影子價格的總和，即產(chǎn)品的隱含成本。,當產(chǎn)值大于隱含成本時，即 ，表明生產(chǎn)該項產(chǎn)品有利，可在計劃中安排；否則 ，用這些資源生產(chǎn)別的產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。,影子價格,2.6 對偶單純形法,對偶單純形法是求解線性規(guī)劃的另一個基本方法。它是根據(jù)對偶原理和單純形法原理而設計出來的，因此稱為對偶

43、單純形法。不要簡單理解為是求解對偶問題的單純形法。,對偶單純形法原理,對偶單純形法基本思路：,找出一個對偶問題的可行基，保持對偶問題為可行解的條件下，判斷XB是否可行（XB為非負），若否，通過變換基解，直到找到原問題基可行解（即XB為非負），這時原問題與對偶問題同時達到可行解，由定理4可得最優(yōu)解。,對偶單純形法,找出一個DP的可行基,LP是否可行（XB ≥0）,保持DP為可行解情況下轉移到LP的另一個基本解,最優(yōu)解,,,,,,,是,否

44、,循環(huán),,結束,對偶單純形法,先回顧一下單純形算法：它是從線性規(guī)劃的一個基可行解迭代到另一個基可行解的過程，在迭代過程中，保持基解的可行性，逐步消除基解的檢驗數(shù)的非負性，即,,為了求解線性規(guī)劃，我們也可以從線性規(guī)劃的一個基解迭代到另一個基解，在迭代過程中，保持基解的檢驗數(shù)的非正性，逐步消除基解的不可行性，即,,對偶單純形法,如果原問題(P)的一個基本解X與對偶問題(D)的基可 行解Y對應的檢驗數(shù)向

45、量滿足條件 則稱X為原問題(P)的一個正則解。,求解原問題(P)時，可以從(P)的一個正則解開始，迭代到另一個正則解，使目標函數(shù)值增加，當?shù)秸齽t解滿足原始可行性條件(即xi≥0)時，就找到了原問題(P)的最優(yōu)解。 這一方法稱為對偶單純形法,對偶單純形法,定義,對偶單純形法,,,原問題解空間,對偶問題解空間,,,,,,,,可行解,可行解,基本解,基本解,正則解,正則解,基可

46、行解,基可行解,,,最優(yōu)解,,,,對偶單純形法,對偶單純法的迭代步驟：,（1）找一個正則基B和初始正則解X(0)，將問題（P）化為關于基B的典式，列初始對偶單純形表.,設正則解,的典式為：,對偶單純形法,將上面的典式轉換成前面所學習過的單純形表：,,,對偶單純形法,,,,,,對偶單純形法,,,,,,,,,,,,對偶單純形法,用對偶單純形法計算,例9,對偶單純形法,由于初始正則解有負分量，于是取min{-3,-4}=-4x5為換出變量，

47、取,x1為換入變量，得新基{x4,x1} ，?51= -2為主元,,,,對偶單純形法,基變換的過程：,主元變?yōu)?，即用-2去除單純形表中基變量x5所在的行；主元所在列的其它元變?yōu)?，消去非基變量x1所在的列的其余元-1，-2；得新基{x4,x1}的單純形表,,,,對偶單純形法,,基變換的過程：,,,,,,對偶單純形法,,可見正則解的有負分量，由于x4=1 , 所以取x4為換出變量，取,x2為換入變量，得新基{x2,x1} ，?42

48、=-5/2為主元,,,,對偶單純形法,此時正則解是可行解，也是最優(yōu)解。 X*=(11/5，2/5，0，0，0)；z*=-28/5,,進行基變換，得新正則解的單純形表：,對偶單純形法,,,例10,,例11,,例12,對偶單純形法的迭代步驟中,如何找一個初始正則解？,初始正則解的確定,標準形線性規(guī)劃問題,選定的基B，不妨設,對偶單純形法,可行基B的典式為,右端常數(shù)中有負數(shù)，而檢驗數(shù)全非正，則基B為正則基，相應的

49、 解為初始正則解，就可用對偶單純形法求解。,否則，若出現(xiàn)正檢驗數(shù)，X(0)就不是正則解。,為此，求初始正則基和初始正則解，可增加一個約束條件：,原問題(P)的典式擴充為下列問題:,擴充問題：,對偶單純形法,擴充問題的一個正則基和正則解是不難得到的。,對偶單純形法,擴充問題的兩種可能結果：,（1）若擴充問題無可行解，則原問題(P)也無可行解。,則把 x

50、0 作為換出變量，xk 作為換入變量，經(jīng)過一次迭代，就可得到一個正則解：,具體計算可以在單純形表上實現(xiàn).,,,證明:,則 一定是擴充問題的可行解，與假設矛盾。,令,對偶單純形法,（1）若擴充問題無可行解，則原問題(P)也無可行解。事實上，若原問題如果有可行解：,由于,所以,則 是擴充問題的可行解，又因擴充問題與原問題的目標函數(shù)相同，且都與 無關,所以必有,這與 是擴充問題的最優(yōu)解矛盾。,

51、對偶單純形法,（2）若擴充問題有最優(yōu)解,且目標函數(shù)最優(yōu)值與 M 無關,則有,必為原問題(P)的最優(yōu)解。事實上，如果原問題有可行解,對偶單純形法的理論解釋,對偶單純形法所使用的表格與原單純形法一樣，可將典式中的數(shù)據(jù)放在原單純形表上，即得到對偶單純形表，所不同的是這里保證在整個過程中,,不保證,,即右端常數(shù)中可以出現(xiàn)負數(shù)。,對偶單純形法,先定換出變量，再定換入變量。,設正則基

52、的典式為：,對偶單純形法,對偶單純形表,對偶單純形法的迭代方式與原單純形法基本一致.所不同的是：先定換出變量，再定換入變量，決定主元并作基變換得到一個新的正則解X(1),從而完成一次迭代.算法的后半部分與原單純形法完全一致.,對偶單純形法,,,(2)再選進基變量:假定xk為進基變量, 我們分析一下xk 應滿足什么條件,才能使迭代后得到的解仍為問題(P)的正則解.,(1)先選出基變量:若 則取與 相對應的基變量 xr 為出基變量.

53、,因為 ,而換基運算的第一步是用主元 去除第r 行中的各元素,為了使變換后 為正數(shù),所以主元 必須從第r 行的負元素中選取,即 .,,設主元處在第 k 列,于是換基運算后,各檢驗數(shù)變?yōu)?因為要求迭代后得到的解仍為正則解,于是,又因為,于是當 時,不等式(1)自然成立;,由此,則取與之相對應的非基變量 為換入變量。,

54、否則,當 時,要使不等式(1)成立,必須,又因為,于是當 時,不等式(1)自然成立;,對偶單純形法,,最后證明對應于新的正則解X(1),對偶問題(D)的目標函數(shù)值將得到改善.,這樣,上述求極大值問題(P)的迭代過程,實質上是在對對偶問題(D)求極小值,所以目標函數(shù)越小就越接近最優(yōu)解.直到得到對偶問題(D)的最小值,相應地也就求出了原問題(P)的最大值.,出基變量 與進

55、基變量 xk 確定以后,以 為主元進行換基運算(方法與原單純形法相同)即可得新的正則解X(1) .,這是因為 ,故,,和原始單純形法一樣,若對偶問題是非退化的(即對偶問題的每一個基可行解都是非退化的,或者說,對于原問題的每一個正則解，都有 ,

56、則每迭代一次,目標函數(shù)都將嚴格減小,從而一定能在有限次迭代后得到原問題的最優(yōu)解,或者判定它無解.,容易證明:若 ,且所有的 ,則原問題(P)無解(自己證明).,用對偶單純形法求解線性規(guī)劃問題時，當約束條件為“＞”時，不必引進人工變量，使計算簡化。當線性規(guī)劃問題中變量多于約束條件時，用對偶單純形法計算可以減少工作量。對偶單純形法應用于主