運籌學對偶理論

1.4線性規(guī)劃的對偶理論一、

線性規(guī)劃的對偶問題的提出及其數(shù)學模型例1生產(chǎn)計劃問題（資源利用問題）

勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價50元/個，椅子銷售價格30/個，生產(chǎn)桌子和椅子要求需要木工和油漆工兩種工種。生產(chǎn)一個桌子需要木工4小時，油漆工2小時。生產(chǎn)一個椅子需要木工3小時，油漆工1小時。該廠每個月可用木工工時為120小時，油漆工工時為50小時。問該廠如何組織生產(chǎn)才能使每月的銷售收入最大？生產(chǎn)計劃問題的數(shù)學模型

maxZ=50x1+30x2s.t.4x1+3x21202x1+x250x1,x20

如果我們換一個角度，考慮另外一種經(jīng)營問題。假如有一個企業(yè)家有一批等待加工的訂單，有意租用該家具廠的木工和油漆工資源來加工他的產(chǎn)品。因此，家具廠要同該企業(yè)家談判付出租每個木工（或油漆工）工時的價格。問此時應如何構造數(shù)學模型？建立模型需要考慮：1、決策變量？2、目標函數(shù)？3、約束條件？

假設y1,y2分別表示每個木工和油漆工工時的租金。建模關注點：1、企業(yè)家認為自己付的租金越少越好；2、家具廠認為有利可圖，才肯把資源出租給企業(yè)家。企業(yè)家希望所付總租金最小，其目標函數(shù)可表示為：

minS=120y1+50y2目標函數(shù)中的系數(shù)120，50分別表示可供出租的木工和油漆工工時數(shù)。

該企業(yè)家所付的租金不能太低，否則家具廠的管理者覺得無利可圖而不肯出租給他。因此他付的租金應不低于家具廠利用這些資源所能得到的利益：

4y1+2y2503y1+y230y1,y20

于是得到數(shù)學模型：

minS=120y1+50y2s.t.4y1+2y2503y1+y230y1,y20生產(chǎn)計劃問題資源出租合理定價問題模型(1)可以理解為家具廠內(nèi)部管理：合理安排生產(chǎn)計劃追求銷售收入最大；模型(2)可以理解為家具廠外部談判：出租手中的資源獲得合理的租金。原問題與對偶問題模型(1)和模型(2)

既有區(qū)別又有聯(lián)系。區(qū)別在于模型反映的內(nèi)容是不同的；聯(lián)系在于它們使用了相同的數(shù)據(jù)。如果模型(1)稱為原問題（P），則模型(2)稱為對偶問題（D）。任何線性規(guī)劃問題都有對偶問題。原問題與對偶問題之間沒有嚴格的界限，它們互為對偶。若已知一個原問題的數(shù)學模型，能否直接寫出其對偶問題的數(shù)學模型？有何規(guī)律？二、

原問題與對偶問題的對應關系例1.1(P)(D)原問題與對偶問題：

P（D）D（P）目標函數(shù)系數(shù)c←→右端常數(shù)項b

系數(shù)矩陣A←→系數(shù)矩陣A約束條件←→變量T（個數(shù)）（符號）變量與約束之間的關系規(guī)律：“正常對正常，反常對反?！闭Ｇ闆r下，首先線性規(guī)劃問題的所有變量都應是大于或等于0；其次，最大化問題的約束都應是“≤”形式的，而最小化問題的約束都應是“≥”形式的。只要原問題模型中的變量和約束都符合這些規(guī)律，則對偶問題模型中的變量和約束也一定符合這些規(guī)律；如果原問題模型中的變量和約束違反這些規(guī)律，則對偶問題模型中的變量和約束也一定違反這些規(guī)律；正常情況下原問題（或?qū)ε紗栴}）：P（或D）D（或P）原問題與對偶問題對應關系表

原問題（或?qū)ε紗栴}）

對偶問題（或原問題）

目標函數(shù)MaxZ目標函數(shù)MinW約束條件數(shù)：m個第i個約束條件類型為“≤”第i個約束條件類型為“≥”第i個約束條件類型為“=”

變量數(shù)：m個第i個變量≥0第i個變量≤0第i個變量是自由變量

變量數(shù)：n個第j個變量≥0第j個變量≤0第j個變量是自由變量

約束條件數(shù)：n個第i個約束條件類型為“≥”第i個約束條件類型為“≤”第i個約束條件類型為“=”

例1：寫出下列線性規(guī)劃問題的對偶問題

minS=x1+2x2+3x3s.t.2x1+3x2+5x3

2

3x1+x2+7x33x1，x2，

x30該問題的對偶問題：

maxz=2y1+3y2s.t.2y1+3y213y1+y225y1+7y23y10，y20例2：寫出下列線性規(guī)劃問題的對偶問題

minS=2x1+3x2-5x3s.t.x1+x2-x3

52x1

+x3=4x1，x2，

x30該問題的對偶問題為：

maxz=5y1+4y2s.t.y1+2y22y1

3-y1+y2-5y10，y2無非負約束練習1：寫出下列線性規(guī)劃問題的對偶問題

minS=3x1-2x2+x3s.t.x1+2x2=12x2

-x3-22x1+x33x1-2x2+3x34x1，x20

，

x3無非負限制練習1答案解:對偶問題為：

maxz=y1-2y2+3y3+4y4s.t.y1+2y3+y432y1+2y2-2y4-2-y2+y3+3y4=1y20

，y3,y40，y1無非負約束三、

對偶性質(zhì)定理定理1、對稱性定理：對偶問題的對偶是原問題。

例1.1(P)(D)定理2、弱對偶定理（弱對偶性）：設和分別是問題（P）和（D）的可行解，則必有定理2可以用來判斷原問題（對偶問題）目標函數(shù)值的上界（下界）。

推論:原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界；反之對偶問題任一可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界。定理2

推論:若和分別是問題（P）和（D）的可行解，則是（D）的目標函數(shù)最小值的一個下界；是（P）的目標函數(shù)最大值的一個上界。定理2例1、試驗證弱對偶性原理。（P）解：（D）

由觀察可知：=（1.1.1.1），=（1.1），分別是（P）和（D）的可行解。=10，

=40，故有，弱對偶定理成立。＜

由觀察可知：=（1.1.1.1），=（1.1），分別是（P）和（D）的可行解。CX=10，Yb=40。由推論可知，W

的最小值不能小于10，Z

的最大值不能超過40。定理3無界性：在一對對偶問題（P）和（D）中，若其中一個問題可行但目標函數(shù)無界，則另一個問題不可行；反之不成立。

定理3無界性：在一對對偶問題（P）和（D）中，若其中原問題（對偶問題）為無界解，則其對偶問題（原問題）無可行解；反之不成立。

無界例2：（P）無可行解（D）例3、已知顯然，這兩個問題都無可行解。

定理3

推論：在一對對偶問題（P）和（D）中，若一個可行（如P），而另一個不可行，（如D），則該可行的問題無界。例4：試用對偶性質(zhì)證明原問題無界。

解：=（0.0.0）是P的一個可行解，而D的第一個約束條件不能成立（因為y1,

y2≥0)。因此，對偶問題不可行，由定理3推論可知，原問題無界。定理5、對偶性若原問題有最優(yōu)解,則對偶問題也一定有最優(yōu)解，且目標函數(shù)值相等。

綜上所述，一對對偶問題中解的對應關系，只能有下面三種情況之一出現(xiàn)：①.若P和D的任意一個有最優(yōu)解，則另一個也有最優(yōu)解，且目標函數(shù)的最優(yōu)值相等，即有CX*=Y*b；②.一個問題無界，則另一個問題無可行解；③.兩個都無可行解。

P有最優(yōu)解的充要條件是D有最優(yōu)解。若X*

和Y*分別是P和D的可行解，則它們分別是P和D的最優(yōu)解的充要條件是CX*=Y*b。最優(yōu)解存在定理：若P和D同時存在可行解，則它們必都存在最優(yōu)解。最優(yōu)性判別定理：若X*和Y*分別是P和D的可行解且CX*=Y*b，則X*、Y*分別是問題P和D的最優(yōu)解。定理4、最優(yōu)性思考：根據(jù)上述定理如何判斷原問題有（或者沒有）最優(yōu)解？練習：試用對偶理論討論下列原問題是否有最優(yōu)解？對偶性質(zhì)定理總結：定理2弱對偶定理：判斷原問題（對偶問題）目標函數(shù)值的上界（下界）。定理3、4、5：判斷原問題（對偶問題）有無最優(yōu)解。

反映原問題與對偶問題解的幾種對應關系。練習：試用對偶理論判斷下列線性規(guī)劃問題是否有最優(yōu)解？（1）（2）答案：（1）無最優(yōu)解（無界解）（2）有最優(yōu)解定理6互補松弛性定理：根據(jù)原問題（或?qū)ε紗栴}）最優(yōu)解，直接求出對偶問題（或原問題）的最優(yōu)解?；パa松弛定理（松緊定理）描述了線性規(guī)劃問題達到最優(yōu)時，一個問題的變量和另一個問題約束的松緊性之間的對應關系。定理6、互補松弛定理：

在線性規(guī)劃的最優(yōu)解中，如果對應某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；另外，如果約束條件取嚴格不等式，則其對應的對偶變量為零。(見教材)進一步解釋：在線性規(guī)劃的最優(yōu)解中，如果一個問題的某一變量不等于0,則對應的另一個問題的約束一定取嚴格等式(緊約束)；如果一個問題的某一約束取嚴格不等式(松約束),則對應的另一個問題的變量一定為0?；パa松弛定理：

在線性規(guī)劃問題的最優(yōu)解中：

P（D）D（P）變量X(或Y)≠0，則約束條件（=）。約束條件（＞或＜），則變量Y(或X)=0。例3：見教材p20y*=(4/5,3/5)Z*=5練習1、已知原問題的最優(yōu)解為X*=（50/7，200/7）T，Z*=4100/7試求對偶問題的最優(yōu)解。解：將X*=（50/7，200/7）T代入原問題中，有：所以，根據(jù)互補松弛條件，必有y*1=0;又因為x1*、x2*≠0，因此，兩個對偶約束取等號，聯(lián)立方程得到最優(yōu)解為：

Y*=（0，32/7，6/7），W*=4100/7。(1)<(2)=(3)=練習2、已知原問題的最優(yōu)解為X*=（2，2，4，0）T，試求對偶問題的最優(yōu)解。答案：y*=(4/5,3/5,1,0)例4、已知試通過求對偶問題的最優(yōu)解來求解原問題的最優(yōu)解。解：對偶問題為用圖解法求出：Y*=（1.3），W=11。(1.3)（1）（2）（3）（4）（5）將y*1=1，y*2=3代入對偶約束條件，（1）（2）（5）式為緊約束，（3）（4）為松約束。則根據(jù)互補松弛條件，必有x*3=x*4=0

又由于y*1=1≠0，y*2=3≠0，原問題的約束必為等式，即化簡為因此，原問題為無窮多最優(yōu)解。

令x5=0,得到x1=1，x2=2

即X*1=（1.2.0.0.0）T為原問題的一個最優(yōu)解，Z=11。再令x5=2/3，得到x1=5/3，x2=0即X*2=（5/3.0.0.0.2/3）T也是原問題的一個最優(yōu)解，Z=11。定理7、若原問題P與對偶問題D分別如下：則原問題單純形表中檢驗數(shù)的相反數(shù)對應其對偶問題的一個基本解。例5、cj1018000cBxBbx1x2x3x4x50x317052100170/20x410023010100/30x515015001150/5Z01018000cj1018000cBxBbx1x2x3x4x50x3540/7001-23/711/710x150/71005/7-3/718x2200/7010-1/72/7Z4100/7000-32/7-6/7初始表最終表

由上表可知：X*=（50/7.200/7）T，Z*=4100/7對偶問題的最優(yōu)解：Y*=（0.32/7.6/7），W*=4100/7檢驗數(shù)σ3=0，σ4=-32/7,σ5=-6/7對偶最優(yōu)解是原問題松弛變量對應的檢驗數(shù)的相反數(shù)。練習：利用定理7求下面線性規(guī)劃問題的對偶最優(yōu)解。

用表格單純形法求解如下：10-14/3-1/30121/31/3

12

X1X2

23

193/40-3/41-1/41/417/401/4

3/49/4

X4

X2

03

5/40-9/40-3/427/4

Z00-1-5/3-1/38Z233000Z3/19/41111014701

3