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

第三章線性規(guī)劃的對偶理論與靈敏度分析

線性規(guī)劃的對偶問題

對偶問題的基本性質(zhì)影子價格對偶單純形法靈敏度分析運籌學(xué)線性規(guī)劃對偶問題共18頁，您現(xiàn)在瀏覽的是第1頁!第二節(jié)對偶問題的基本性質(zhì)為了便于討論，下面不妨總是假設(shè)：運籌學(xué)線性規(guī)劃對偶問題共18頁，您現(xiàn)在瀏覽的是第2頁!原線性規(guī)劃問題的矩陣表達(dá)式加上松弛變量后為：

一、單純形法的矩陣描述上式中Xs為松弛變量，，I為m×m單位矩陣。

運籌學(xué)線性規(guī)劃對偶問題共18頁，您現(xiàn)在瀏覽的是第3頁!非基變量基變量XBXNXS0XSbBNICj-zjCBCN0

當(dāng)?shù)舾刹胶?，基變量為XB時，則該步的單純形表中由XB系數(shù)組成的矩陣為I。又因單純形法的迭代是對約束增廣矩陣進(jìn)行的行的初等變換，對應(yīng)XS的系數(shù)矩陣在新表中應(yīng)為B-1。故當(dāng)基變量為XB時，新的單純形表具有如下形式?；兞糠腔兞縓BXNXSCBXBB-1bIB-1NB-1

Cj-zj0CN-CBB-1N-CBB-1

運籌學(xué)線性規(guī)劃對偶問題共18頁，您現(xiàn)在瀏覽的是第4頁!（5）當(dāng)B為最優(yōu)基時，應(yīng)有:

這時從檢驗數(shù)行看出，若取其相反數(shù)恰好是其對偶問題的一個可行解。將這個解代入對偶問題的目標(biāo)函數(shù)值，有：

因XB的檢驗數(shù)可寫為:

則有稱為單純形乘子，若令基變量非基變量XBXNXSCBXBB-1bIB-1NB-1

Cj-zj0CN-CBB-1N-CBB-1

XN的檢驗數(shù)

XS的檢驗數(shù)

XB的檢驗數(shù)

所以XA的檢驗數(shù)

運籌學(xué)線性規(guī)劃對偶問題共18頁，您現(xiàn)在瀏覽的是第5頁!兩個問題的最終單純形表見下頁：

原問題變量松弛變量

x1x2x3x4x5x315/20015/4－15/2x17/21001/4－1/2x23/2010－1/43/2000-1/4-1/2

對偶問題的剩余變量對偶問題變量y4y5y1y2y3

對偶問題變量對偶問題的剩余變量

y1y2y3y4y5y21/4－5/410－1/41/4y31/215/2011/2－3/215/2007/23/2

原問題松弛變量x3x4x5原問題變量x1x2運籌學(xué)線性規(guī)劃對偶問題共18頁，您現(xiàn)在瀏覽的是第6頁!三、線性規(guī)劃的對偶定理弱對偶性（弱對偶定理）證明：運籌學(xué)線性規(guī)劃對偶問題共18頁，您現(xiàn)在瀏覽的是第7頁!2.最優(yōu)性（最優(yōu)解判別定理）證明：設(shè)xj*是原問題的最優(yōu)解，yi*是對偶問題的最優(yōu)解運籌學(xué)線性規(guī)劃對偶問題共18頁，您現(xiàn)在瀏覽的是第8頁!4.互補松弛性（互補松弛定理）在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為非零的，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對應(yīng)的對偶變量一定為0。也即運籌學(xué)線性規(guī)劃對偶問題共18頁，您現(xiàn)在瀏覽的是第9頁!運籌學(xué)線性規(guī)劃對偶問題共18頁，您現(xiàn)在瀏覽的是第10頁!Cjc1c2cn000CBXBbx1x2xnxn+1xn+2xn+m0xn+1b1a11a12a1n1000xn+2b2a21a22a2n0100xn+mbmam1am2amn001cj-zjc1c2cn000非基變量基變量XBXNXS0XSbBNICj-zjCBCN0

單純形法計算時，總選取I為初始基，對應(yīng)基變量為Xs。設(shè)迭代若干步后，基變量為XB，在初始單純形表中的系數(shù)矩陣為B。B將在初始單純形表中單獨列出，而A中去掉若干列后剩下的列組成矩陣N，這樣初始單純形表可列成如下形式。運籌學(xué)線性規(guī)劃對偶問題共18頁，您現(xiàn)在瀏覽的是第11頁!

當(dāng)?shù)蠡兞繛閄B時，其在初始單純形表中的系數(shù)矩陣為B，則有：（1）對應(yīng)初始單純形表中的單位矩陣I，迭代后的單純形表中為B-1

（2）初始單純形表中基變量Xs=b，迭代后的表中

XB=B-1

b（3）初始單純形表中約束系數(shù)矩陣為

，迭代后的表中約束系數(shù)矩陣為(B-1左乘):非基變量基變量XBXNXS0XSbBNICj-zjCBCN0基變量非基變量XBXNXSCBXBB-1bIB-1NB-1

Cj-zj0CN-CBB-1N-CBB-1

（4）若初始矩陣中變量Xj的系數(shù)向量為Pj，迭代后為，則有:運籌學(xué)線性規(guī)劃對偶問題共18頁，您現(xiàn)在瀏覽的是第12頁!

例1

兩個互為對偶的線性規(guī)劃問題，兩者分別加上松弛和剩余變量后為：二、原規(guī)劃與對偶規(guī)劃問題的變量及解之間的對應(yīng)關(guān)系運籌學(xué)線性規(guī)劃對偶問題共18頁，您現(xiàn)在瀏覽的是第13頁!二、原規(guī)劃與對偶規(guī)劃問題的變量及解之間的對應(yīng)關(guān)系●對偶(min型)變量的最優(yōu)解等于原問題松弛變量檢驗數(shù)的絕對值●對偶問題最優(yōu)解的剩余變量解值等于原問題對應(yīng)變量的檢驗數(shù)的絕對值●由于原問題和對偶問題是相互對偶的，因此對偶問題的檢驗數(shù)與原問題的解也有類似上述關(guān)系?！窀话愕刂v，不管原問題是否標(biāo)準(zhǔn)，在最優(yōu)解的單純型表中，都有原問題虛變量(松弛或剩余)的檢驗數(shù)對應(yīng)其對偶問題實變量

(對偶變量)的最優(yōu)解，原問題實變量(決策變量)的檢驗數(shù)對應(yīng)其對偶問題虛變量

(松弛或剩余變量)的最優(yōu)解。因此，原問題或?qū)ε紗栴}只需求解其中之一就可以了。運籌學(xué)線性規(guī)劃對偶問題共18頁，您現(xiàn)在瀏覽的是第14頁!弱對偶定理推論:●max問題的任何可行解目標(biāo)函數(shù)值是其對偶min問題目標(biāo)函數(shù)值的下限；min問題的任何可行解目標(biāo)函數(shù)值是其對偶max問題目標(biāo)函數(shù)值的上限?！袢绻瓎栴}（對偶問題）為無界解，則其對偶問題（原問題）無可行解?！袢绻瓎栴}（對偶問題）有可行解，其對偶問題（原問題）無可行解，則原問題（對偶問題）為無界解。注意：如果原問題（對偶問題）無可行解，對偶問題（原問題）具有無界解或無可行解。運籌學(xué)線性規(guī)劃對偶問題共18頁，您現(xiàn)在瀏覽的是第15頁!3.強對偶性（對偶定理）定理如果原問題和對偶問題都有可行解，則它們都有最優(yōu)解，且它們的最優(yōu)解的目標(biāo)函數(shù)值相等。證：步，證明都有最優(yōu)解。原問題和對偶問題都有可行解，由弱對偶定理推論1可知，原問題目標(biāo)函