運籌學：教案61_對偶理論(

1、復習上節(jié)課的內容復習上節(jié)課的內容基變量基變量非基變量非基變量 XBXNXSI0B-1 NCN-CBB-1NB-1-CBB-1B-1b-CBB-1b單純形表的矩陣形式單純形表的矩陣形式 XB=B-1b jjjBjjBjjBPBPPCcPBCcbBCz111 cj 2 3 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 8 16 12 1 4 0 2 0 4 1 0 0 0 1 0 0 0 1 - -z 0 2 3 0 0 0 cj 2 3 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x4 x2 2 8 3 1 0 0

2、 0 0 1 1 - -4 0 0 1 0 - -1/21/2 2 1/4 - -z - -13 0 0 - -2 0 1/41/4 如例如例1 的初始表和第三張表的初始表和第三張表4 4 線性規(guī)劃的對偶理論線性規(guī)劃的對偶理論本節(jié)重點：本節(jié)重點：對偶問題的定義對偶問題的定義互補松弛定理的應用互補松弛定理的應用單純形表檢驗數行與對偶基單純形表檢驗數行與對偶基本解的對應關系本解的對應關系對偶問題的定義對偶問題的定義 0XbAX. t . sCXzmax 0ssXXbXAX. t . sCXzmax，標準型為：標準型為： 定義如下：原問題 (P)的對偶問題是問題(D) (P) 0 XbAXCXzma

3、x (D) 0 YCYAYbmin Prime problem Dual problem 展開式如下 （P） 0 21121112112211 nmnmnm2m1nnnx,x,xbbxxxaaaaaaxcxcxczMax （D）0 212111211212211 mnmnm2m1nmmmy,y,y)c ,c ,c(aaaaaa)y,y,y(bybybymin 互為轉置互為轉置列向量列向量行向量行向量n個變量個變量n個約束個約束一一般般，對對偶偶問問題題有有如如下下的的對對應應關關系系： 原原問問題題( (或或對對偶偶問問題題) ) 對對偶偶問問題題( (或或原原問問題題) ) 目目標標函函數數

4、 m ma ax x z n個個 變變 0 量量 0 無無約約束束 目目標標函函數數 m mi in n n n個個 約約 束束 條條 = = 件件 約約 m m個個 束束 條條 件件 = = 約約束束條條件件右右端端項項 目目標標函函數數變變量量的的系系數數 m m個個 0 變變 0 量量 無無約約束束 目目標標函函數數變變量量的的系系數數 約約束束條條件件右右端端項項 例例3 3 試求下述線性規(guī)劃問題的對偶問題試求下述線性規(guī)劃問題的對偶問題 無約束無約束432143243143214321006 42 2 53 532x;x,x;xxxxxxxxxxxxxxxzmin 解：設對偶變量為解：

5、設對偶變量為y1,y2,y3,對偶問題模型為對偶問題模型為：Max w=5y1+4y2+6y3 y1 +2y2 y1 + y3 -3y1 +2y2 +y3 y1 - y2 +y323-5=1y10, y20, y3無約束無約束1 對對稱稱性性 原原問問題題和和對對偶偶問問題題的的概概念念是是相相對對的的。 (P) 0 YCYAYbmin (D) 0 XbAXCXzmax 4.2 對偶問題的基本性質對偶問題的基本性質證明：證明： 0 - )max(YCYAYb 2、 弱弱對對偶偶性性 對對于于(P)的的任任一一可可行行解解X和和(D)的的任任一一可可行行解解 Y，有有bYXC 。 證證： 由由于

6、于CAY ，0 X 有有 XCXAY 又又 0 Y,bXA，所所以以 XCXAYbY 。 注意：注意：(D)無可行解，無可行解，(P)不一定為無界解。不一定為無界解。 此性質還說明：此性質還說明：(P)有可行解，有可行解，(D)不一定有可行解。不一定有可行解。3、無界性、無界性 若（若（P）問題可行，但目標函數無界，則（）問題可行，但目標函數無界，則（D）問題不可行。問題不可行。（D）不可行）不可行（P）無界）無界 （P）不可行）不可行例例1 已知線性規(guī)劃問題已知線性規(guī)劃問題),(max3210132232332132121 jxxxxxxxxxZj 試用對偶理論證明上試用對偶理論證明上述問題

7、無最優(yōu)解述問題無最優(yōu)解(無界無界)。無界性定理。無界性定理。（P）可行，但無界）可行，但無界 則則（D）不可行。）不可行。（D）不可行）不可行（P）無界）無界（P）不可行）不可行對偶問題對偶問題0033321222121212121 yyyyyyyyyyW,minX（0）=（0，0，0）T是是原問題的一個可行解原問題的一個可行解對偶問題不可行對偶問題不可行4、 可行解是最優(yōu)解時的性質可行解是最優(yōu)解時的性質 設設 是是(P)的可行解，的可行解， 是是(D)的可行解，當的可行解，當 時，時， 是最優(yōu)解。是最優(yōu)解。X Y bYXC YX , 5、對偶定理、對偶定理 若（若（P）有最優(yōu)解，則（）有最優(yōu)

8、解，則（D）也有最優(yōu)解，且目）也有最優(yōu)解，且目標函數最優(yōu)值相等。標函數最優(yōu)值相等。利用弱對偶定理利用弱對偶定理6、互補松弛定理、互補松弛定理如何應用該定理？如何應用該定理？02121 *),(smssmxxxyyy0*2*2*1*1smmssxyxyxy 設設X*和和Y*分別分別(P）問題）問題(D）問題的可行解，則它）問題的可行解，則它們分別是最優(yōu)解的充要條件是們分別是最優(yōu)解的充要條件是Y*XS*=0和和YS*X*=00*2*2*1*1smmssxyxyxy0002211 *smmssxyxyxy00001111 *yxxyss則則若若則則若若對偶變量不為對偶變量不為0，原問題相應，原問題相

9、應約束式是等式約束式是等式例例4 4 已知線性規(guī)劃問題已知線性規(guī)劃問題 5210 3 32 432 32532543215432154321,j ,xxxxxxxxxxxxxxxxminj 已知其對偶問題的最優(yōu)解為已知其對偶問題的最優(yōu)解為541/y* ，532/y* ；z z = 5= 5。試用對偶理論找出原問題的最優(yōu)解。試用對偶理論找出原問題的最優(yōu)解。 原問題約束為原問題約束為不等式，相應不等式，相應對偶變量為對偶變量為0最優(yōu)解點最優(yōu)解點 解：先寫出它的對偶問題先寫出它的對偶問題 0 (5) 3 3 (4) 2 (3) 532 (2) 3 (1) 22 3421212121212121 y,

10、yyyyyyyyyyyyyzmax 將將*y1, ,*y2的值代入約束條件，得的值代入約束條件，得(2)(2)，(3)(3)，(4)(4)為嚴格不等式；由互為嚴格不等式；由互補松弛性得補松弛性得0432 *xxx。因。因 y1，y2 0；原問題的兩個約束條；原問題的兩個約束條件應取等式，故有件應取等式，故有 3 243 5151 *xxxx 求解后得到求解后得到1151 x,x；故原問題的最優(yōu)解為；故原問題的最優(yōu)解為 X* = (1，0，0，0，1)T； * = 5 練練習習： 096628342max321432214214321jxxxxxxxxxxxxxxxxz 已已知知；原原問問題題的

11、的最最優(yōu)優(yōu)解解為為 X X* *= =( (2 2, ,2 2, ,4 4, ,0 0) )試試根根據據對對偶偶理理論論，直直接接求求出出對對偶偶問問題題的的最最優(yōu)優(yōu)解解。 7、(P)的單純形表的檢驗數行對應的單純形表的檢驗數行對應(D)的一個基解，其對的一個基解，其對應關系是應關系是 X XS C -CBB-1A -CBB-1 -YS -Y (證略證略) 意義：單純形法迭代過程中，檢驗數的相反數對應對偶變意義：單純形法迭代過程中，檢驗數的相反數對應對偶變量基解的值量基解的值 Y = C CB BB B- -1 1， YS = - -C+C CB BB B- -1 1A A。由于有大于零的檢。

12、由于有大于零的檢驗數，故對應的對偶解為不可行解；驗數，故對應的對偶解為不可行解； 最終單純表中檢驗數最終單純表中檢驗數都非正，故此時對應的對偶解為基可行解，也是最優(yōu)解。都非正，故此時對應的對偶解為基可行解，也是最優(yōu)解?？芍瑔渭冃畏ㄊ窃诮猓芍?，單純形法是在解（P P）時，保持）時，保持(P)(P)解的可行性，改解的可行性，改進（進（D D）解的可行性，最后當得到對偶的基可行解時，）解的可行性，最后當得到對偶的基可行解時，也就也就得到了了(P)(P)、(D)(D)的最優(yōu)解。的最優(yōu)解。 檢驗數行檢驗數行5 5 對偶問題的經濟解釋對偶問題的經濟解釋 影子價格影子價格 (P)的最終單純形表中松弛變量

13、的檢驗數對應的最終單純形表中松弛變量的檢驗數對應(D)的最優(yōu)解。的最優(yōu)解。 當某約束條件的右端常數增加一個單位時當某約束條件的右端常數增加一個單位時（假設原問題的最優(yōu)基不變），原問題的目標函數（假設原問題的最優(yōu)基不變），原問題的目標函數最優(yōu)值增加的數量。最優(yōu)值增加的數量。Z*=CX*=Y*b =(y1*,y2*, ,ym*)b1b2bm=y1*b1+y2*b2+ym*bm當某個右端常數當某個右端常數bi bi+1時時bi+1yi*+yi*(bi+1)=Y*b+yi*=Z*+yi*第第I種資源的影子價種資源的影子價格是第格是第i個約束條件個約束條件的右端常數增加一的右端常數增加一個單位時，目標函

14、個單位時，目標函數增加的數量數增加的數量 甲甲 乙乙可用量可用量機械設備機械設備 1 28原材料原材料A 4 016原材料原材料B 0 412 X X(3)(3)=(4=(4，2 2，0 0，0, 4)0, 4)T T， z z3 3 =14=14cj23000CBXBbx1x2 x3x4x5203x1x5x2442100001-2-3/2-1/81/8010-1400-3/2 -1/800125051321 *,.,.yyy經濟意義：經濟意義：在其它條件在其它條件不變的情況不變的情況下，下，單位資源變單位資源變化所引起的化所引起的目標函數的目標函數的最優(yōu)值的變最優(yōu)值的變化?；?。影子價格影子價

15、格 產品產品資源資源 現有資源數現有資源數鋼材鋼材1 2100（噸）（噸）煤煤2 2180（噸）（噸）機時機時1 6240（小時）（小時）利潤（萬元）利潤（萬元）1 30,24061802210023max2121212121xxxxxxxxxxZx1x2x3x4x5 -zXB-13500-3/40-1/4x130103/20-1/2x45000-5/211/2x23501-1/401/4X*=(30,35,0,50,0)T, Z*=135y1*=3/4y2*=0,y3*=1/4影子價格影子價格經濟意義：經濟意義：在其它條件不變的情況下，在其它條件不變的情況下，單位資源變化所引起的目標函數的最

16、優(yōu)值的變化。單位資源變化所引起的目標函數的最優(yōu)值的變化。6 對偶單純形法對偶單純形法保持對偶可行性，保持對偶可行性，逐步改進主可行性逐步改進主可行性，求解主問題。，求解主問題。 當當b有負分量，有負分量，A中有一明顯初始對偶可行中有一明顯初始對偶可行基基(檢驗數均非正檢驗數均非正)，因而易得一初始解時，可用，因而易得一初始解時，可用對偶單純形法求解。對偶單純形法求解。 0 XbAXCXZmax設設B為一個基為一個基 010bBX)(基本解基本解X（0）為基本可行為基本可行解的條件？解的條件？B-1b0X（0）為最優(yōu)解的為最優(yōu)解的條件？條件？01 ABCCB原原原始可行性條件原始可行性條件原始最

17、優(yōu)性條件原始最優(yōu)性條件令令Y=CBB-1，代入原始最優(yōu)性條件，代入原始最優(yōu)性條件，YAC無符號限制無符號限制YCYAYbW min對偶可行性條件對偶可行性條件計算步驟：計算步驟： 10 求初始基解，其檢驗數均非正。求初始基解，其檢驗數均非正。 20 計算計算liibbmin ，若，若 bl 0，則已得到最優(yōu)解，結束；，則已得到最優(yōu)解，結束；否則第否則第 l 行的基變量為換出變量。行的基變量為換出變量。 30 若若 alj 0 （ j） ，則無可行解，結束；否則計算） ，則無可行解，結束；否則計算 lkkljljjjaaamin 0 ，xk 為換入變量為換入變量 40 以以 alk 為主元素作旋

18、轉運算，為主元素作旋轉運算， xk 取代原第取代原第 l 行基變行基變量，返回量，返回 20。 例例 用對偶單純形法求解用對偶單純形法求解 43210242323443214321421,max jxxxxxxxxxxxxZj單純形法單純形法大大M 法法 621024232346432154321421,max jxxxxxxxxxxxxxxZj剩余變量、剩余變量、人工變量人工變量 用（用（-1）乘不等式兩邊，再引入松弛變量。）乘不等式兩邊，再引入松弛變量。cj -1 -4 0 -3 0 0CBXBb x1 x2 x3 x4 x5 x600 x5x6-3-2 -1 -2 1 - 1 1 0 2

19、 1 -4 -1 0 10 -1 -4 0 -3 0 0先選出基變量先選出基變量后選進基變量后選進基變量原問題，原問題，符合原始符合原始最優(yōu)性條最優(yōu)性條件，但不件，但不可行可行1132411 ,mincj -1 -4 0 -3 0 0CBXBb x1 x2 x3 x4 x5 x6-10 x1x63-8 1 2 - 1 1 -1 0 0 -3 -2 -3 2 13 0 -2 -1 -2 -1 0cj -1 -4 0 -3 0 0CBXBb x1 x2 x3 x4 x5 x6-10 x1x63-8 1 2 - 1 1 -1 0 0 -3 -2 -3 2 13 0 -2 -1 -2 -1 0-10 x1x374 1 7/2 0 5/2 -2 -1/2 0 3/2 1 3/2 -1 -1/2 7 0 -1/2 0 -1/2 -2 -1/2最優(yōu)解最優(yōu)解X*=（7，0，4，0）TZ*=-7 解解： 先先將將這這問問題題化化成成下下列列形形式式， 以以便便得得到到對對偶偶問問題題的的初初始始可可行行基基 （P）5210 4 3 2 3 2 43253214321321,j ,xxxxxxxxxxxxzmaxj 例例6 用對偶單純形法求解用對偶單純形法求解0,43232432min321321321321xxxxxxxxxxxxw（P）單單純純形形表表：1 -