對(duì)偶性及對(duì)偶單純形法

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

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

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

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

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

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

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

4y1+2y2503y1+y230y1,y20

得到另外一個(gè)數(shù)學(xué)模型：

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

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

x3，x40

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

（4.5）

x0(II)Ming=ybs.t.Atyct

（4.6）

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

a11a12….a1nb1A=a21a22….a2nb

=

b2

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

am1am2….amnbm

c1x10y1c2x20y2Ct=X=0=yt=……………..…..cnxn0ym原問題（或?qū)ε紗栴}）對(duì)偶問題（或原問題）目標(biāo)函數(shù)maxZ價(jià)值系數(shù)資源系數(shù)目標(biāo)函數(shù)minW資源系數(shù)價(jià)值系數(shù)行約束的個(gè)數(shù)為m第i個(gè)行約束取“≤”第ι個(gè)行約束取“＝”對(duì)偶變量的個(gè)數(shù)為m第i個(gè)變量yi

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

≥0第k個(gè)變量xk無(wú)限制行約束的個(gè)數(shù)為n第j個(gè)行約束取“≥”第k個(gè)行約束取“＝”線性規(guī)劃的原問題與對(duì)偶問題的變換規(guī)則表：例2-3：寫出下列線性規(guī)劃問題的對(duì)偶問題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解：該問題的對(duì)偶問題：

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

y2

x1，x2，

x30解：該問題的對(duì)偶問題：

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

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

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

2

3x1+x2+7x33x1，x2，

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

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

2y1

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

x30該問題的對(duì)偶問題：

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

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

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”

寫出對(duì)偶問題

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無(wú)非負(fù)約束此類問題稱為非對(duì)稱型對(duì)偶問題。前面的問題稱為對(duì)稱型對(duì)偶問題。例2-7：寫出下列線性規(guī)劃問題的對(duì)偶問題

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

y1

2x2-x3-2

y2

2x1+x33

y3

x1-2x2+3x34

y4

x1，x20

，

x3無(wú)非負(fù)限制

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

，

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

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

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

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

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

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

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

＜0

｝=σk/aιk確定對(duì)應(yīng)的xk為旋入變量。

步驟4

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

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

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

2x1，x2，

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

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

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

確定進(jìn)基變量X3，主元（-2）主元運(yùn)算：第二行乘（-1/2）主元運(yùn)算：第一行加第二行計(jì)算檢驗(yàn)數(shù)：全為非正。但此時(shí)常數(shù)b已全大于零，最優(yōu)解=（7，0，4，0）最優(yōu)值S’=-7S=7例2-10：用對(duì)偶單純形法解下列線性規(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ù)項(xiàng)最小出基變量X5，按比值無(wú)法比較。常數(shù)項(xiàng)次小出基變量X4，按比值X2為進(jìn)基變量。主元（-2）主元運(yùn)算：第一行乘（-1/2）主元運(yùn)算：第二行加第一行（-2）計(jì)算檢驗(yàn)數(shù)：全小于零。但常數(shù)項(xiàng)為負(fù)數(shù)的行元素全大于零，原問題無(wú)可行解。例2-11用對(duì)偶單純形法求解下述問題

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）為初始基，易見所有檢驗(yàn)數(shù)σj≤0，從而可建立單純形表，計(jì)算結(jié)果如下：

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本例如果用單純形法計(jì)算，確定初始基可行解時(shí)需引入兩個(gè)人工變量，計(jì)算量要多于對(duì)偶單純形法。一般情況下，如果問題能夠用對(duì)偶單純形法計(jì)算，計(jì)算量會(huì)少于單純形法。但是，對(duì)偶單純形法并不是一種普遍算法，它有一定的局限性，不是任何線性規(guī)劃問題都能用對(duì)偶單純形法計(jì)算的。當(dāng)線性規(guī)劃問題具備下面條件時(shí)，可以用對(duì)偶單純形法求解：

①問題標(biāo)準(zhǔn)化后，價(jià)值系數(shù)全非正；②所有約束全是不等式。例2-11：某種農(nóng)作物在生長(zhǎng)過程中至少需要氮肥33公斤，磷肥24公斤，鉀肥42公斤。已知有甲、乙、丙、丁四種復(fù)合肥料的每公斤價(jià)格和含氮、磷、鉀肥數(shù)量如下表。問應(yīng)如何使用這些肥料，既能滿足作物生長(zhǎng)的需要，又能使施肥成本最低？原始數(shù)據(jù)表解：設(shè)用甲、乙、丙、丁為X1、X2、X3、X4公斤。數(shù)學(xué)模型為：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