運(yùn)籌學(xué)線性規(guī)劃對(duì)偶問題

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

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

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

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

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

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

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

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

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

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

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

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

XN的檢驗(yàn)數(shù)

XS的檢驗(yàn)數(shù)

XB的檢驗(yàn)數(shù)

所以XA的檢驗(yàn)數(shù)

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

原問題變量松弛變量

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

對(duì)偶問題的剩余變量對(duì)偶問題變量y4y5y1y2y3

對(duì)偶問題變量對(duì)偶問題的剩余變量

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

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

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

當(dāng)?shù)蠡兞繛閄B時(shí)，其在初始單純形表中的系數(shù)矩陣為B，則有：（1）對(duì)應(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，迭代后為，則有:運(yùn)籌學(xué)線性規(guī)劃對(duì)偶問題共18頁，您現(xiàn)在瀏覽的是第12頁!

例1

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

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

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