運籌學(xué)線性規(guī)劃對偶問題PPT課件

1、原線性規(guī)劃問題的矩陣表達式加上松弛變量后為： 一、單純形法的矩陣描述上式中XsXs為松弛變量， ，I為m mm m單位矩陣。 0, 00maxsssXXbIXAXXCXz),(21mnnnsxxxX0, 0,. .000 21212211222222121111212111212211mnnnnmmnnmnmmnnnnnnmnnnnnxxxxxxbxxaxaxabxxaxaxabxxaxaxatsxxxxcxcxczMax第1頁/共17頁Cjc1c2cn000CBXBbx1x2xnxn+1xn+2xn+m0 xn+1b1a11a12a1n1000 xn+2b2a21a22a2n0100 xn+

2、mbmam1am2amn001cj-zjc1c2cn000非基變量非基變量基變量基變量XB XNXS0 XS bB NICj-zjCB CN0 單純形法計算時，總選取單純形法計算時，總選取I I為為初始基初始基，對應(yīng)基變量為對應(yīng)基變量為XsXs。設(shè)迭代若干步后，設(shè)迭代若干步后，基變量為基變量為X XB B，在初始單純形表中的在初始單純形表中的系數(shù)矩陣為系數(shù)矩陣為B B。B B將在初始單純形表中單獨將在初始單純形表中單獨列出，而列出，而A A中去掉若干列后剩下的列組成矩陣中去掉若干列后剩下的列組成矩陣N N，這樣初始單純形表可列成如這樣初始單純形表可列成如下形式。下形式。 第2頁/共17頁非基變

3、量非基變量基變量基變量XB XNXS0 XS bB NICj-zjCB CN0 當(dāng)?shù)舾刹胶?，基變量為?dāng)?shù)舾刹胶螅兞繛閄 XB B時時，則該步的單純形表中由則該步的單純形表中由X XB B系數(shù)組成的系數(shù)組成的矩陣為矩陣為I I。又因單純形法的迭代是對約束增廣矩陣進行的行的又因單純形法的迭代是對約束增廣矩陣進行的行的初等變換初等變換，對對應(yīng)應(yīng)X XS的系數(shù)矩陣在新表中應(yīng)為的系數(shù)矩陣在新表中應(yīng)為B B-1-1。故當(dāng)基變量為故當(dāng)基變量為X XB B時，新的單純形表具有如時，新的單純形表具有如下形式。下形式。 基變量基變量非基變量非基變量XBXN XSCB XB B B-1-1 bIB B-

4、1-1 N B B-1-1 Cj-zj0CN -CB B B-1-1 N -CB B B-1-1 第3頁/共17頁 當(dāng)?shù)蠡兞繛閄B時，其在初始單純形表中的系數(shù)矩陣為B B，則有：（1 1）對應(yīng)初始單純形表中的單位矩陣I I，迭代后的單純形表中為B B-1-1 （2）初始單純形表中基變量Xs=bXs=b，迭代后的表中 XB= B B-1-1 b（3）初始單純形表中約束系數(shù)矩陣為 ，迭代后的表中約束系數(shù)矩陣為( (B B-1-1 左乘) ) :INBIA,1111111,BNBIIBNBBBIBAB非基變量非基變量基變量基變量XB XNXS0 XS bB NICj-zjCB CN0基變量基變

5、量非基變量非基變量XBXN XSCB XB B B-1-1 bIB B-1-1 N B B-1-1 Cj-zj0CN -CB B B-1-1 N -CB B B-1-1 （4）若初始矩陣中變量Xj的系數(shù)向量為Pj ，迭代后為 ，則有:jPjjPBP1第4頁/共17頁（5）當(dāng)B B為最優(yōu)基時，應(yīng)有: : 01NBCCBN01BCB這時從檢驗數(shù)行看出，若取其相反數(shù)恰好是其對偶問題的一個可行解。將這個解代入對偶問題的目標函數(shù)值，有： 因XB的檢驗數(shù)可寫為: : zbBCbYwB11BCYB0YCYA則有稱為單純形乘子，若令1BCB基變量基變量非基變量非基變量XBXN XSCB XB B B-1-1

6、bIB B-1-1 N B B-1-1 Cj-zj0CN -CB B B-1-1 N -CB B B-1-1 XN的檢驗數(shù) XS的檢驗數(shù) 0ICCBBXB的檢驗數(shù) 01ABCCB所以XA的檢驗數(shù) 第5頁/共17頁 例1 1 兩個互為對偶的線性規(guī)劃問題，兩者分別加上松弛和剩余變量后為： 543210002maxxxxxxz)5 ,.1(05242615552142132jxxxxxxxxxj543210052415minyyyyyw) 5 , 1(0125265321432iyyyyyyyyi二、原規(guī)劃與對偶規(guī)劃問題的變量及解之間的對應(yīng)關(guān)系第6頁/共17頁兩個問題的最終單純形表見下頁： jjzc

7、 原問題變量松弛變量 x1 x2x3 x4 x5 x3 15/20 01 5/4 15/2x1 7/21 00 1/4 1/2x2 3/20 10 1/4 3/20 0 0 -1/4 -1/2 對偶問題的剩余變量對偶問題變量y4 y5 y1 y2 y3jjzc 對偶問題變量對偶問題的剩余變量 y1 y2 y3y4 y5 y2 1/4 5/4 1 0 1/4 1/4y3 1/2 15/2 0 11/2 3/2 15/2 0 07/2 3/2 原問題松弛變量 x3 x4 x5原問題變量x1 x2第7頁/共17頁二、原規(guī)劃與對偶規(guī)劃問題的變量及解之間的對應(yīng)關(guān)系對偶對偶( (minmin型型) )變量

8、的最優(yōu)解等于原問題變量的最優(yōu)解等于原問題松弛變量松弛變量檢驗數(shù)的檢驗數(shù)的絕對值絕對值對偶問題最優(yōu)解的剩余變量解值等于原問題對偶問題最優(yōu)解的剩余變量解值等于原問題對應(yīng)變量對應(yīng)變量的檢的檢驗數(shù)的絕對值驗數(shù)的絕對值由于原問題和對偶問題是相互對偶的，因此對偶問題的檢由于原問題和對偶問題是相互對偶的，因此對偶問題的檢驗數(shù)與原問題的解也有類似上述關(guān)系驗數(shù)與原問題的解也有類似上述關(guān)系。更一般地講，不管原問題是否標準，在更一般地講，不管原問題是否標準，在最優(yōu)解的單純型表最優(yōu)解的單純型表中，都有原問題中，都有原問題虛變量虛變量( (松弛或剩余松弛或剩余) ) 的檢驗數(shù)對應(yīng)其對的檢驗數(shù)對應(yīng)其對偶問題偶問題實變量實

9、變量 ( (對偶變量對偶變量) )的最優(yōu)解的最優(yōu)解，原問題原問題實變量實變量( (決策決策變量變量) ) 的檢驗數(shù)對應(yīng)其對偶問題的檢驗數(shù)對應(yīng)其對偶問題虛變量虛變量 ( (松弛或剩余變量松弛或剩余變量) )的最優(yōu)解。因此，原問題或?qū)ε紗栴}只需求解其中之一就的最優(yōu)解。因此，原問題或?qū)ε紗栴}只需求解其中之一就可以了?？梢粤?。第8頁/共17頁三、線性規(guī)劃的對偶定理三、線性規(guī)劃的對偶定理1. 弱對偶性（弱對偶定理）證明：證明： miiinjjjminjijijmiinjjijmiiiminjijijnjjmiiijnjjjybxcyxayxaybyxaxyaxc111111111111)()(第9頁/共

10、17頁弱弱對偶定理推論對偶定理推論: :max問題問題的任何可行解目標函數(shù)值是其的任何可行解目標函數(shù)值是其對偶對偶min問題問題目標目標函數(shù)值的下限；函數(shù)值的下限； min問題的任何可行解目標函數(shù)值是其對問題的任何可行解目標函數(shù)值是其對偶偶max問題目標函數(shù)值的上限。問題目標函數(shù)值的上限。如果原問題（對偶問題）為無界解，則其對偶問題（原問如果原問題（對偶問題）為無界解，則其對偶問題（原問題）無可行解。題）無可行解。如果原問題（對偶問題）有可行解，其對偶問題（原問題）如果原問題（對偶問題）有可行解，其對偶問題（原問題）無可行解，則原問題（對偶問題）為無界解。無可行解，則原問題（對偶問題）為無界解

11、。u注意：注意：如果原問題（對偶問題）無可行解，對偶問題（原如果原問題（對偶問題）無可行解，對偶問題（原問題）具有無界解或無可行解。問題）具有無界解或無可行解。第10頁/共17頁2. 2. 最優(yōu)性（最優(yōu)解判別定理）證明：設(shè)xj*是原問題的最優(yōu)解， yi*是對偶問題的最優(yōu)解miiimiiinjjjnjjjmiiinjjjmiiinjjjmiiimiiinjjjnjjjybybxcxcybxcybxcybybxcxc11*1*11*1*1111*1*1,第11頁/共17頁3.強對偶性（對偶定理）定理定理 如果原問題和對偶問題都有可行解，則它們都有最優(yōu)如果原問題和對偶問題都有可行解，則它們都有最優(yōu)解

12、，且它們的最優(yōu)解的目標函數(shù)值相等。解，且它們的最優(yōu)解的目標函數(shù)值相等。證：第一步，證明都有最優(yōu)解。證：第一步，證明都有最優(yōu)解。原問題和對偶問題都有可原問題和對偶問題都有可行解，由弱對偶定理推論行解，由弱對偶定理推論1可知，原問題目標函數(shù)有上界，可知，原問題目標函數(shù)有上界，對偶問題的目標函數(shù)有下界，故一定存在最優(yōu)解。對偶問題的目標函數(shù)有下界，故一定存在最優(yōu)解。 第二步，證明最優(yōu)解的目標函數(shù)值相等。第二步，證明最優(yōu)解的目標函數(shù)值相等。根據(jù)單純形根據(jù)單純形法的矩陣描述，原問題有最優(yōu)解，對偶問題為可行解，且法的矩陣描述，原問題有最優(yōu)解，對偶問題為可行解，且二者的目標函數(shù)值相等，根據(jù)最優(yōu)性定理，二者的解均