§1線性規(guī)劃的對偶問題的提出

每個(gè)線性規(guī)劃都有另一個(gè)線性規(guī)劃(對偶問題)與它密切相關(guān)，對偶理論揭示了原問題與對偶問題的內(nèi)在聯(lián)系。

0,0768940453643.3032max212121212133???íì￡+￡+￡++=xxxxxxxxtsxxz矩陣形式

0.max3￡=XbAXt.sCXz實(shí)際問題提出：某廠生產(chǎn)甲、乙兩種產(chǎn)品，產(chǎn)量、利潤、設(shè)備臺(tái)時(shí)如下模型所示第二章線性規(guī)劃的對偶理論

從另一個(gè)角度討論這個(gè)問題：另一方面，工廠決定設(shè)備轉(zhuǎn)讓、收取租金，確定租價(jià)。設(shè)y1，y2，y3分別為設(shè)備A、B、C每臺(tái)時(shí)的租價(jià)，同意租讓的原則：產(chǎn)品甲租讓的租費(fèi)不低于原利潤32元，其余產(chǎn)品類似。工廠將所有設(shè)備臺(tái)時(shí)都出租，其收入和約束為：矩陣形式

為什么目標(biāo)取最?。孔饨鸲ǖ脑礁呔筒粫?huì)有人來租，問題就沒有實(shí)際意義，工廠和接受者都愿意的條件為上述規(guī)劃問題的解。其中Y=（y1，y2，y3）§２線性規(guī)劃的對偶理論原問題與對偶問題的數(shù)學(xué)模型原問題：對偶問題：

標(biāo)準(zhǔn)對偶問題化成對偶問題的標(biāo)準(zhǔn)形

1.若原問題的約束條件全部是等式約束

總結(jié)：原問題與對偶問題的對應(yīng)關(guān)系

2.其它形式，按線性規(guī)劃化標(biāo)準(zhǔn)形的方法進(jìn)行進(jìn)一步有原問題（或?qū)ε紗栴}）對偶問題（或原問題）

目標(biāo)函數(shù)maxz目標(biāo)函數(shù)minw

約束條件:m個(gè)對偶變量數(shù):m個(gè)變量

第i個(gè)約束條件類型約束為≤對偶變量:yi

≥0

第i個(gè)約束條件類型約束為≥對偶變量:yi

≤0

第i個(gè)約束條件類型約束為=對偶變量:yi是自由變量

決策變量總數(shù):n個(gè)約束條件總數(shù)為n個(gè)

決策變量xi≥0第j個(gè)約束條件類型為≥

決策變量xi≤0第j個(gè)約束條件類型為≤

決策變量xi是自由變量第j個(gè)約束條件類型為=

原問題中的價(jià)值向量與對偶問題中的資源向量對換,“上下對換”.

原問題:X在C和A的右邊;對偶問題:Y在b和A的左邊,“左右對換”

對偶問題的基本性質(zhì)和基本定理1.對稱性定理：對偶問題的對偶是原問題證明：2.弱對偶性定理

若X（0）和Y（0）分別是原問題和對偶問題的可行解，則有CX（0）≤Y（0）b3.若原問題（對偶問題）可行，但目標(biāo)函數(shù)無界，則其對偶問題（原問題）無可行解。4.最優(yōu)性定理

若X（0）和Y（0）分別是原問題和對偶問題的可行解，且有CX（0）=Y（0）b,則X（0）和Y（0）分別是原問題和對偶問題的最優(yōu)解。

5.對偶定理

有一對對偶的線性規(guī)劃問題，若其中一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且相應(yīng)的目標(biāo)函數(shù)值相等。

綜上，一對對偶問題的解必然為下列情況之一：1、原問題和對偶問題都有解，且目標(biāo)函數(shù)值相等2、一個(gè)問題具有無界解，另一個(gè)問題無可行解3、原問題和對偶問題都無可行解6.互補(bǔ)松弛定理

若X（0）和Y（0）分別是原問題和對偶問題的可行解，則X（0）和Y（0）都是最優(yōu)解的充要條件是Y（0）

Xs=0和YsX（0）=0。

其中Xs=(xs1,xs2,…,xsm)T，xs1,xs2,…,xsm

分別是原問題的松弛變量.

Ys=(ys1,ys2,…,ysn)T，ys1,ys2,…,ysn分別是對偶問題的剩余變量。

松弛的含義是如果有某個(gè)原始最優(yōu)解X(0)，使得對某個(gè)下標(biāo)j，滿足X(0)j>0(對原問題是松的)，那么與之對應(yīng)的對偶約束在最優(yōu)的情況下為等式，即ysj=0(對對偶問題是緊的)；如果原始約束在最優(yōu)情況下對某個(gè)下標(biāo)i滿足x(0)si>0(對原問題是松的)，那么，對偶最優(yōu)解中與之對應(yīng)的y(0)i=0(對偶問題是緊的)。例4已知線性規(guī)劃問題

maxz=x1+x2

-x1+x2+x3

≤2

-2x1+x2-x3

≤1

x1,x2,x3≥0

試用對偶理論證明上述線性規(guī)劃問題無最優(yōu)解。

證:首先看到該問題存在可行解，例如X=(0,0,0)

而上述問題的對偶問題為

minω=2y1+y2

-y1-2y2≥1

y1+y2≥1

y1-y2≥0

y1,y2≥0

由第一約束條件可知對偶問題無可行解，因而無最優(yōu)解。由此原問題也無最優(yōu)解。例5已知線性規(guī)劃問題

minω=2x1+3x2+5x3+2x4+3x5

x1+x2+2x3+x4+3x5

≥42x1-x2+3x3+x4+x5

≥3xj≥0,j=1,2,3,4,5

已知其對偶問題的最優(yōu)解為y1*=4/5,y2*=3/5；z=5。試用對偶理論找出原問題的最優(yōu)解.解:

先寫出它的對偶問題

maxz=4y1+3y2y1+2y2≤2y1-y2≤32y1+3y2≤5y1+y2≤23y1+y2≤3y1,y2≥0將y1*,y2*的值代入上述約束條件，得(2),(3),(4)為嚴(yán)格不等式；由互補(bǔ)松弛性得x2*=x3*=x4*=0

因y1,y2

0，原問題的兩個(gè)約束條件應(yīng)取等式，故有

x1*+3x5*=42x1*+x5*=3

求解后得x1*=1，x5*=1故原問題的最優(yōu)解為

X*=(1,0,0,0,1)T最優(yōu)值為ω*=5§３對偶問題的經(jīng)濟(jì)解釋（影子價(jià)格）由對偶定理知，當(dāng)達(dá)到最優(yōu)解時(shí)有：

z=CX（0）=Y（0）b=y1（0）b1+y2（0）b2+…+ym（0）bm在最優(yōu)解處，常數(shù)項(xiàng)bi

的微小改變對目標(biāo)函數(shù)值的影響（在不改變最優(yōu)基情況下）有這說明若原問題的bi增加一個(gè)單位，則由此引起的最優(yōu)目標(biāo)函數(shù)值增加量，就等于該約束條件相對應(yīng)的對偶變量yi的最優(yōu)值。因此，最優(yōu)對偶變量yi的值，就相當(dāng)于對單位變化的第i種資源在實(shí)現(xiàn)最大利潤時(shí)的一種價(jià)格估計(jì)，這種估計(jì)被稱之為影子價(jià)格。原問題：可以理解為資源的合理利用使總利潤最大對偶問題：估計(jì)資源的價(jià)值問題（但并不是第ｉ種資源的實(shí)際成本，而是根據(jù)企業(yè)制造產(chǎn)品的收益估計(jì)資源的單位價(jià)值，既資源在最優(yōu)產(chǎn)品組合時(shí)具有的潛在價(jià)值）影子價(jià)格：不同于市場價(jià)格，是企業(yè)內(nèi)部估計(jì)或核算價(jià)格例：某廠生產(chǎn)Ⅰ、Ⅱ種產(chǎn)品要消耗鋼、煤、機(jī)械加工時(shí)間，現(xiàn)有資源數(shù)和利潤表如下，試制定一個(gè)最優(yōu)生產(chǎn)計(jì)劃。單位消耗Ⅰ

Ⅱ現(xiàn)有資源數(shù)鋼煤機(jī)時(shí)１２２２１６１００１８０２４０利潤１３解得：對偶問題:由互補(bǔ)松弛條件：解得：所以：鋼增加一噸，收入增加3/4萬煤增加一噸，收入增加0

機(jī)時(shí)增加一個(gè)，收入增加1/4萬

煤本身沒有用完，再增加量，收入也不會(huì)增加，而另兩種資源已經(jīng)用完，再增加資源才會(huì)增加收益影子價(jià)格在經(jīng)濟(jì)管理中的作用:指示企業(yè)內(nèi)部挖潛的方向：yi高,對目標(biāo)增益貢獻(xiàn)大,應(yīng)重視此資源的組織、采購；(2)指導(dǎo)企業(yè)的購銷決策：yi*是新增資源的價(jià)值，在最優(yōu)產(chǎn)品不變的情況下，購入資源價(jià)格大于yi*時(shí)，企業(yè)虧損，若企業(yè)有市價(jià)高于影子價(jià)格的資源，應(yīng)設(shè)法將其轉(zhuǎn)讓；(3)用影子價(jià)格分析工藝改變后對資源節(jié)約的收益:(4)指導(dǎo)企業(yè)間的分工協(xié)作:

企業(yè)接受外協(xié)加工時(shí)，制定收費(fèi)標(biāo)準(zhǔn)可依據(jù)影子價(jià)格，以使雙方都有利潤，可以促進(jìn)協(xié)作；當(dāng)外協(xié)單位支付的報(bào)酬不低于影子價(jià)格時(shí)，企業(yè)可以接受，合作可以促進(jìn)產(chǎn)品更新?lián)Q代，以發(fā)揮各自優(yōu)勢。例：A、B、C三廠生產(chǎn)車床、刨床，若只生產(chǎn)一種產(chǎn)品，每天效率表如右圖。三個(gè)廠車、刨床需求比例為1：2，試制定最優(yōu)分工協(xié)作計(jì)劃，使總的套數(shù)最多。解：A、B、C三廠編號(hào)為1，2，3

車、刨床的編號(hào)為1，2效率車床刨床ABC4223為第i廠生產(chǎn)第j種產(chǎn)品的時(shí)間比例則：三廠生產(chǎn)車床總數(shù)：三廠生產(chǎn)刨床總數(shù)：展開得：總套數(shù)為E，則解得：生產(chǎn)車床：3/4×5=15/4（臺(tái)）生產(chǎn)刨床：4×1+1/4×2+3×1=15/2（臺(tái)）A廠只生產(chǎn)刨床，B廠3/4生產(chǎn)車床，1/4生產(chǎn)刨床C廠只生產(chǎn)刨床此計(jì)劃能否執(zhí)行看較單獨(dú)生產(chǎn)獲利增加情況A廠單獨(dú)生產(chǎn)：解得A廠生產(chǎn)能力：2/3×1=2/3臺(tái)車床

1/3×4=4/3臺(tái)刨床（每天生產(chǎn)一臺(tái)車床或4臺(tái)刨床而需求比例為1:2）（用2/3的能力生產(chǎn)車床，1/3的能力生產(chǎn)刨床）B廠單獨(dú)生產(chǎn)：B廠生產(chǎn)能力：1/6×5=5/6臺(tái)車床

5/6×2=5/3臺(tái)刨床解得：C廠單獨(dú)生產(chǎn)：解得：C廠生產(chǎn)能力：3/7×2=6/7臺(tái)車床

4/7×3=12/7臺(tái)刨床