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

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

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

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

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

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

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

該企業(yè)家所付的租金不能太低，否則家具廠(chǎng)的管理者覺(jué)得無(wú)利可圖而不肯出租給他。因此他付的租金應(yīng)不低于家具廠(chǎ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)于家具廠(chǎng)的模型并且使用相同的數(shù)據(jù)，區(qū)別在于模型反映的實(shí)質(zhì)內(nèi)容是不同的。模型(4.1)是站在家具廠(chǎng)經(jīng)營(yíng)者立場(chǎng)追求銷(xiāo)售收入最大，模型(4.2)是則站在家具廠(chǎng)對(duì)手的立場(chǎng)追求所付的租金最少。如果模型(4.1)稱(chēng)為原問(wèn)題，則模型(4.2)稱(chēng)為對(duì)偶問(wèn)題。任何線(xiàn)性規(guī)劃問(wèn)題都有對(duì)偶問(wèn)題，而且都有相應(yīng)的意義。例2.2營(yíng)養(yǎng)配餐問(wèn)題

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

x3，x40

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

（4.5）

x0(II)Ming=ybs.t.Atyct

（4.6）

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

a11a12….a1nb1A=a21a22….a2nb

=

b2

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

am1am2….amnbm

c1x10y1c2x20y2Ct=X=0=yt=……………..…..cnxn0ym原問(wèn)題（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題（或原問(wèn)題）目標(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è)行約束取“＝”線(xiàn)性規(guī)劃的原問(wèn)題與對(duì)偶問(wèn)題的變換規(guī)則表：例2-3：寫(xiě)出下列線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題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解：該問(wèn)題的對(duì)偶問(wèn)題：

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

y2

x1，x2，

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

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

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

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該問(wèn)題的對(duì)偶問(wèn)題：

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

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

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

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

y12x1+x34

y2’

-2x1-x3-4

y2”

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

寫(xiě)出對(duì)偶問(wèn)題

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ù)約束此類(lèi)問(wèn)題稱(chēng)為非對(duì)稱(chēng)型對(duì)偶問(wèn)題。前面的問(wèn)題稱(chēng)為對(duì)稱(chēng)型對(duì)偶問(wèn)題。例2-7：寫(xiě)出下列線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題

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ì)偶問(wèn)題的基本定理(對(duì)稱(chēng)性定理)課本Th2.5.2

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

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

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

步驟1確定原問(wèn)題（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èn)題無(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ì)偶單純形法解下列線(xiàn)性規(guī)劃問(wèn)題

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ù)全為非正，稱(chēng)為對(duì)偶可行；而常數(shù)項(xiàng)全是負(fù)數(shù)，稱(chēng)為原始不可行。常數(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ì)偶單純形法解下列線(xiàn)性規(guī)劃問(wèn)題

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

1-x1-2x2+x36x1，x2，x30解：將原問(wèn)題化成

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èn)題無(wú)可行解。例2-11用對(duì)偶單純形法求解下述問(wèn)題

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

2x1+x2+4x3≥2

2x1+2x2+4x4≥3

x1,x2,x3,x4≥0解：令=-Z，則問(wèn)題可變?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）為初始基，易見(jiàn)所有檢驗(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ì)偶單純形法。一般情況下，如果問(wèn)題能夠用對(duì)偶單純形法計(jì)算，計(jì)算量會(huì)少于單純形法。但是，對(duì)偶單純形法并不是一種普遍算法，它有一定的局限性，不是任何線(xiàn)性規(guī)劃問(wèn)題都能用對(duì)偶單純形法計(jì)算的。當(dāng)線(xiàn)性規(guī)劃問(wèn)題具備下面條件時(shí)，可以用對(duì)偶單純形法求解：

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