對偶性及對偶單純形法

2-4對偶性及對偶單純形法一線性規(guī)劃的對偶理論1.對偶線性規(guī)劃例2．1生產(chǎn)計劃問題（資源利用問題）

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

maxg=50x1+30x2s.t.4x1+3x21202x1+x250(4.1)x1,x20

如果我們換一個角度，考慮另外一種經(jīng)營問題。假如有一個企業(yè)家有一批等待加工的訂單，有意利用該家具廠的木工和油漆工資源來加工他的產(chǎn)品。因此，他要同家具廠談判付給該廠每個工時的價格?？梢詷嬙煲粋€數(shù)學模型來研究如何既使家具廠覺得有利可圖肯把資源出租給他，又使自己付的租金最少？

假設y1,y2分別表示每個木工和油漆工工時的租金，則所付租金最小的目標函數(shù)可表示為：

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

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

4y1+2y2503y1+y230y1,y20

得到另外一個數(shù)學模型：

mins=120y1+50y2s.t.4y1+2y2503y1+y230(4.2)y1,y20模型(4.1)和模型(4.2)既有區(qū)別又有聯(lián)系。聯(lián)系在于它們都是關于家具廠的模型并且使用相同的數(shù)據(jù)，區(qū)別在于模型反映的實質內容是不同的。模型(4.1)是站在家具廠經(jīng)營者立場追求銷售收入最大，模型(4.2)是則站在家具廠對手的立場追求所付的租金最少。如果模型(4.1)稱為原問題，則模型(4.2)稱為對偶問題。任何線性規(guī)劃問題都有對偶問題，而且都有相應的意義。例2.2營養(yǎng)配餐問題

假定一個成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質和800毫克的鈣。如果市場上只有四種食品可供選擇，它們每千克所含的熱量和營養(yǎng)成分和市場價格見下表。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費用最??？各種食物的營養(yǎng)成分表解：設xj為第j種食品每天的購入量，則配餐問題的線性規(guī)劃模型為：minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455(4.3)400x1+200x2+300x3+500x4800x1，x2，

x3，x40

該問題的對偶問題：maxg=3000y1+55y2+800y3s.t.1000y1+50y2+400y314800y1+60y2+200y36900y1+20y2+300y33200y1+10y2+500y32y1，y2，y30(4.4)該問題的對偶問題(4.4)經(jīng)濟意義可解釋為：市場上有一廠商生產(chǎn)三種可代替食品中的熱量、蛋白質和鈣的營養(yǎng)素，該廠商希望它的產(chǎn)品既有市場競爭力，又能帶來最大利潤，因此需要構造一個模型來研究定價問題。以上模型的變量為各營養(yǎng)素單位營養(yǎng)量的價格，目標函數(shù)反映廠商利潤最大的目標，約束條件反映市場的競爭條件，即：用于購買與某種食品營養(yǎng)價值相同的營養(yǎng)素的價格應小于該食品的市場價格。線性規(guī)劃的對偶關系：（I）MaxS=Cxs.t.Axb

（4.5）

x0(II)Ming=ybs.t.Atyct

（4.6）

y0（4.5)(4.6)稱作互為對偶問題。其中一個稱為原問題，另一個稱為它的對偶問題。

a11a12….a1nb1A=a21a22….a2nb

=

b2

。。。。。。。。。。。。。。。

am1am2….amnbm

c1x10y1c2x20y2Ct=X=0=yt=……………..…..cnxn0ym原問題（或對偶問題）對偶問題（或原問題）目標函數(shù)maxZ價值系數(shù)資源系數(shù)目標函數(shù)minW資源系數(shù)價值系數(shù)行約束的個數(shù)為m第i個行約束取“≤”第ι個行約束取“＝”對偶變量的個數(shù)為m第i個變量yi

≥0第ι個變量yι無限制原變量的個數(shù)為n第j個變量xj

≥0第k個變量xk無限制行約束的個數(shù)為n第j個行約束取“≥”第k個行約束取“＝”線性規(guī)劃的原問題與對偶問題的變換規(guī)則表：例2-3：寫出下列線性規(guī)劃問題的對偶問題minS=12x1+8x2+16x3+12x4s.t.2x1+x2+4x3

22x1+2x2+4x43x1，x2，x3，x40minS=12x1+8x2+16x3+12x4

s.t.2x1+x2+4x3

2y12x1+2x2+4x43y2x1，x2，

x3，x40解：該問題的對偶問題：

maxg=2y1+3y2s.t.2y1+2y212y1+2y284y1164y212y1，y20例2-4：寫出下列線性規(guī)劃問題的對偶問題maxS=10x1+x2+2x3s.t.X1+x2+2x310y14x1+2x2-x320

y2

x1，x2，

x30解：該問題的對偶問題：

ming=10y1+20y2s.t.y1+4y210y1+2y212y1-y22y1，y2

0例2-5：寫出下列線性規(guī)劃問題的對偶問題

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

2

3x1+x2+7x33x1，x2，

x30解：用（-1）乘以第二個約束方程兩邊

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

2y1

-3x1-x2-7x3-3y2x1，x2，

x30該問題的對偶問題：

maxg=2y1-3y2s.t.2y1-3y213y1-y225y1-

7y23y1，y20例2-6：寫出下列線性規(guī)劃問題的對偶問題

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

52x1+x3=4x1，x2，x30解：將原問題的約束方程寫成不等式約束形式：minS=2x1+3x2-5x3s.t.x1+x2-x35

y12x1+x34

y2’

-2x1-x3-4

y2”

x1，x2,x30引入變量y1,y2’，y2”

寫出對偶問題

maxg=5y1+4y2’-4y2”

s.t.y1+2y2’-2y2”

2y1

3-y1+y2’-y2”

-5y1，y2’，y2”

0令y2=y2’-y2”

得到

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

3-y1+y2-5y10，y2無非負約束此類問題稱為非對稱型對偶問題。前面的問題稱為對稱型對偶問題。例2-7：寫出下列線性規(guī)劃問題的對偶問題

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

y1

2x2-x3-2

y2

2x1+x33

y3

x1-2x2+3x34

y4

x1，x20

，

x3無非負限制

minS=3x1-2x2+x3s.t.x1+2x2=1y1-2x2+x32y22x1+x33y3x1-2x2+3x34y4x1，x20

，

x3無非負限制解:綜合運用對偶原則得到maxg=y1+2y2+3y3+4y4s.t.y1+2y3+y432y1-2y2-2y4-2y2+y3+3y4=1y2,y3,y40，y1無非負約束2.對偶問題的基本定理(對稱性定理)課本Th2.5.2

對偶問題的對偶就是原問題.對偶問題的基本定理推理一:對偶問題中,任意一個可行解,都產(chǎn)生了另一個問題的目標函數(shù)的界。推理二:若原問題和對偶問題都有可行解,則它們都有最優(yōu)解。推理三:若互為對偶問題中任意一個有可行解,但無最優(yōu)解,則另一個就無可行解。對偶問題的基本定理定理(最優(yōu)準則)

若原問題的某一個可行解與對偶問題的某一可行解的目標函數(shù)值相等,則它們分別是原問題與對偶問題的最優(yōu)解.對偶問題的基本定理定理(對偶定理)課本Th2.5.1

若原問題有最優(yōu)解,則對偶問題也有最優(yōu)解,且最優(yōu)值相等.原問題與對偶問題解的對應關系二、對偶單純形法原始單純形法其基本思路：在換基迭代過程中，始終保持基變量值非負，逐步使檢驗數(shù)變成非正，最后求得最優(yōu)解或判斷無最優(yōu)解。對偶單純形法其基本思路：在換基迭代過程中，始終保持檢驗數(shù)非正，逐步使基變量值變成非負，最后求得最優(yōu)解或判斷無最優(yōu)解。對偶單純形法計算步驟如下：

步驟1確定原問題（L）的初始基B，使所有檢驗數(shù)，即Y=CBB-1是對偶可行解，建立初始單純形表。

步驟2檢查基變量的取值，若XB=B-1b≥0，則已得最優(yōu)解，計算停；否則求min{(B-1b)i│(B-1b)i＜0｝=(B-1b)ι確定單純形表第L行對應的基變量為旋出變量。

步驟3若所有aιj≥0,則原問題無可行解，計算停；否則，計算θ=min｛σj/aιj│aιj

＜0

｝=σk/aιk確定對應的xk為旋入變量。

步驟4

以aιk為主元作（L，K）旋轉變換，得新的單純形表，轉步驟2?？梢宰C明，按上述方法進行迭代，所得解始終是對偶可行解。

例2-9：用對偶單純形法解下列線性規(guī)劃問題

minS=x1+4x2+3x4s.t.x1+2x2-x3+x43-2x1-x2+4x3+x4

2x1，x2，

x3，x40解：此題可用人工變量方法求，但也可用對偶單純形法。

maxS’=-x1-4x2-3x4s.t.-x1-2x2+x3-x4+x5=-32x1+x2-4x3-x4+x6=-2x1，x2,x3，x4，x5,x6

0計算檢驗數(shù)全為非正，稱為對偶可行；而常數(shù)項全是負數(shù)，稱為原始不可行。常數(shù)項是負數(shù)且最小為3，確定出基變量x5。用出基變量x5行的所有負數(shù)分別去除對應的檢驗數(shù)，最小值對應的為進基變量x1，交叉元素為主元（-1）主元運算：第一行乘（-1）主元運算：第二行加上第一行（-2）計算檢驗數(shù)確定出基變量x6

確定進基變量X3，主元（-2）主元運算：第二行乘（-1/2）主元運算：第一行加第二行計算檢驗數(shù)：全為非正。但此時常數(shù)b已全大于零，最優(yōu)解=（7，0，4，0）最優(yōu)值S’=-7S=7例2-10：用對偶單純形法解下列線性規(guī)劃問題

minS=x1+2x2s.t.-x1+2x2-x3

1-x1-2x2+x36x1，x2，x30解：將原問題化成

maxS’=-x1-2x2s.t.x1-2x2+x3+x4=-1x1+2x2-x3+x5=-6x1，x2，x3，x4,x5

0常數(shù)項最小出基變量X5，按比值無法比較。常數(shù)項次小出基變量X4，按比值X2為進基變量。主元（-2）主元運算：第一行乘（-1/2）主元運算：第二行加第一行（-2）計算檢驗數(shù)：全小于零。但常數(shù)項為負數(shù)的行元素全大于零，原問題無可行解。例2-11用對偶單純形法求解下述問題

minZ=12x1+8x2+16x3+12x4

2x1+x2+4x3≥2

2x1+2x2+4x4≥3

x1,x2,x3,x4≥0解：令=-Z，則問題可變?yōu)閙ax=-12x1-8x2-16x3-12x4

-

2x1-x2-4x3+x5=-2

-2x1-2x2

-4x4+x6=-3

x1,x2,x3,x4,x5,x6≥0取B=（P5,P6）為初始基，易見所有檢驗數(shù)σj≤0，從而可建立單純形表，計算結果如下：

C-12-8-16-1200CBXBB-1bX1X2X3X4X5X600X5X6-2-3

-2-1-4010-2-20［-4］01σ-12-8-16-12000-12X5X4-23/4

-2［-1］-40101/21/2010-1/4σ

-6-2-1600-3-8-12X2X42-1/4

2140-10［-1/2］

0-211/2-1/4σ

-20-80-2-3-8-12X2X111/2

01-441-1104-2-11/2σ

000-4-4-2L=2，K=4L=1，K=2L=2，K=1最優(yōu)解：X1=1/2，X2=1，X3=X4=0,minZ=14本例如果用單純形法計算，確定初始基可行解時需引入兩個人工變量，計算量要多于對偶單純形法。一般情況下，如果問題能夠用對偶單純形法計算，計算量會少于單純形法。但是，對偶單純形法并不是一種普遍算法，它有一定的局限性，不是任何線性規(guī)劃問題都能用對偶單純形法計算的。當線性規(guī)劃問題具備下面條件時，可以用對偶單純形法求解：

①問題標準化后，價值系數(shù)全非正；②所有約束全是不等式。例2-11：某種農(nóng)作物在生長過程中至少需要氮肥33公斤，磷肥24公斤，鉀肥42公斤。已知有甲、乙、丙、丁四種復合肥料的每公斤價格和含氮、磷、鉀肥數(shù)量如下表。問應如何使用這些肥料，既能滿足作物生長的需要，又能使施肥成本最低？原始數(shù)據(jù)表解：設用甲、乙、丙、丁為X1、X2、X3、X4公斤。數(shù)學模型為：minS=4x1+15x2+10x3+13x4s.t.0.03x1+0.3x2+0.15x4330.05x1+0.2x3+0.1x4240.14x1+0.07x4

24x1，x2，

x3，x40也可將模型化為：maxS=-4x1-15x2-10x3-13x4-0.03x1-0.3x2-0.15x4+x5=-33-0.05x1-0.2x3-0.1x4+x6=-24-0.14x1-0.07x4+x7=-24x1，x2，x3，x4,x5，x6,x70

初始可行基B1