對偶問題與靈敏度分析

運(yùn)籌學(xué)

——第3章對偶問題與靈敏度分析湖南大學(xué)工商管理學(xué)院本講內(nèi)容什么是對偶問題單純形法的矩陣描述對偶問題的性質(zhì)線性規(guī)劃的靈敏度分析什么是對偶問題？例1（生產(chǎn)計劃問題）：某工廠在計劃期內(nèi)要安排A、B兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品的利潤與所需的勞力、設(shè)備臺時及原材料消耗，如下：產(chǎn)品A產(chǎn)品B資源限額勞動力設(shè)備原材料9434510360工時200臺時300公斤單位產(chǎn)品利潤70120問：如何安排生產(chǎn)使該廠獲利最大？maxz=70x1+120x2s.t.9x1＋4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0對偶問題的提出考慮上一講的生產(chǎn)計劃問題，若設(shè)備和原料都用于對外加工，工廠收取加工費(fèi)。試問：該廠設(shè)備工時、勞動力和原料該如何定價？顯然，工廠給這些生產(chǎn)要素定價，既要保證自己的利益，又要使自己的價格具有競爭力價格越高越好價格越低越好一個合理的定價是：收取的加工費(fèi)不能低于自己生產(chǎn)所得收益，在此前提下使總加工費(fèi)盡量小。即：Minw=360y1+200y2+300y3s.t.9y1+4y2+3y3≥704y1+5y2+10y3≥120y1,y2≥0該線性規(guī)劃問題與原問題互為對偶問題對偶的定義

(LP)Maxz=CX

(DP)Minw=Ybs.t.AX≤bs.t.YA≥CX≥0Y≥0若一個問題的某約束為等式，那么對應(yīng)的對偶問題的相應(yīng)變量無非負(fù)限制；反之，若一個問題的某變量無非負(fù)限制，那么對應(yīng)的對偶問題的相應(yīng)約束為等式。原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標(biāo)函數(shù)max目標(biāo)函數(shù)min約束條件m個m個變量≤≥0≥≤0=無約束變量n個n個約束條件≥0≥≤0≤無約束=約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)建立對偶問題的規(guī)則約束條件變量右端項(xiàng)價值系數(shù)對于上表，特別把握以下要點(diǎn)：maxmin求max的對偶問題時，變量反號求min的對偶問題時，約束反號＝無限制例1：寫出下列規(guī)劃問題的對偶問題Maxz=2x1+2x2-4x3

s.t.X1+3x2+3x3≤304x1+2x2+4x3≤80X1,x2,x3≥0解：minw=30y1+80y2

s.t.y1+4y2≥23y1+2y2≥23y1+4y2≥-4y1,y2≥0例2：寫出下列規(guī)劃問題的對偶問題minz=2x1+8x2-4x3

s.t.X1+3x2-3x3≥30-x1+5x2+4x3=804x1+2x2-4x3≤50X1≤0,x2≥0,x3無限制解：maxw=30y1+80y2＋50y3

s.t.y1-y2+4y3≥23y1+5y2+2y3≤8

－3y1+4y2－4y3＝-4y1≥0,y2無限制,y3≤0單純形法的矩陣描述單純形法的矩陣描述設(shè)有線性規(guī)劃問題Maxz=CXAX≤bX≥0加上松弛變量XS=(xn+1,xn+2,…,xn+m),化為標(biāo)準(zhǔn)型Maxz=CX＋0XsAX+IXS=bX≥0,XS≥0單純形法的矩陣描述設(shè)A中存在一可行基B，相應(yīng)的變量可分為基變量XB和非基變量XN，價值系數(shù)也分為CB,CN，即A=(B,N)X=(XB,XN)TC=(CB,CN)Maxz=CX＋0XsAX+IXS=bX≥0,XS≥0因而于是Maxz=CX＋0XsAX+IXS=bX≥0,XS≥0代入XB,目標(biāo)值檢驗(yàn)數(shù)令XN=0,XS=0,得基可行解目標(biāo)值0zIb0C矩陣形式描述的單純形表關(guān)于對偶問題的基本定理定理1（弱對偶定理）若X(0),Y(0)

分別為（LP）和（DP）的可行解，那么CX(0)≤Y(0)b。(證明)該定理說明：如果原問題是最大化問題，則它的任意可行解對應(yīng)的目標(biāo)函數(shù)值都會小于等于其對偶問題(極小化)的任一可行解對應(yīng)的目標(biāo)函數(shù)值證明：由X(0),Y(0)

分別為原問題和對偶問題的可行解則,AX(0)≤b,X(0)≥0Y(0)A≥C,Y(0)≥0因此，Y(0)AX(0)≤Y(0)b于是，CX(0)≤Y(0)bMaxz=2x1+2x2-4x3

s.t.X1+3x2+3x3≤304x1+2x2+4x3≤80X1,x2,x3≥0minw=30y1+80y2

s.t.y1+4y2≥23y1+2y2≥23y1+4y2≥-4y1,y2≥0例如任意取一些可行解試試看？定理2（無界性）若一個問題無界，則另一個問題不可行maxz=x1+x2

s.t.-2x1+x2

≤40x1-x2

≤20x1,x2≥0可行域Minw=40y1+20y2s.t.-2y1+y2

≥

1y1-y2≥1y1,y2

≥0對偶問題顯然無可行解！例如定理3（最優(yōu)性定理）若X(0),Y(0)

分別為（LP）和（DP）的可行解，且CX(0)=Y(0)b，那么X(0),Y(0)分別為（LP）和（DP）的最優(yōu)解證明設(shè)X*是LP問題的任一可行解，由弱對偶性CX*≤Y(0)b=CX(0)從而X(0)是最優(yōu)解同理Y(0)是最優(yōu)解定理4（對偶定理）若其中一個問題有最優(yōu)解，則另一個問題也有最優(yōu)解，且兩者最優(yōu)值相等證明證明：設(shè)X*是LP問題的最優(yōu)解，相應(yīng)的最優(yōu)基為B，則檢驗(yàn)數(shù)必定滿足令則有因而Y*是對偶問題的可行解又因而Y*是對偶問題的最優(yōu)解0zIb0C定理5（互補(bǔ)松弛定理）原問題及其對偶問題的可行解X(0)和Y(0)是最優(yōu)解的充要條件是：

Y(0)XS=0，YSX(0)=0XS,YS分別為原問題松弛向量和對偶問題剩余向量該定理說明：一對對偶問題達(dá)到最優(yōu)，當(dāng)且僅當(dāng)松約束對應(yīng)的對偶變量必定是緊的利用互補(bǔ)松馳定理，可以在知道一個問題的最優(yōu)解時，求解其對偶問題的最優(yōu)解例：Minz=2x1+3x2+5x3+2x4+3x5s.t.X1+x2+2x3+x4+3x5≥42x1-2x2+3x3+x4+x5≥3

xj≥0,j=1,…,5Maxw=4y1+3y2s.t.y1+2y2≤2y1-2y2≤32y1+3y2≤5y1+y2≤23y1+y2≤3y1,y2≥0對偶問題y1*=4/5,y2*=3/5對偶問題的最優(yōu)解4/5-2*3/5=-2/5<3約束條件是松的也即ys>0,由互補(bǔ)松弛定理知X(0)ys=0所以x2=0同理，x3=0,x4=0又y1*>0,而Y(0)xs=0,知xs＝0，即原問題第一個約束取等式同理，第2個約束也取等式定理6若原問題最優(yōu)解存在，則原問題最優(yōu)單純形表的檢驗(yàn)數(shù)行中，松弛變量的檢驗(yàn)數(shù)和剩余變量的檢驗(yàn)數(shù)的相反數(shù)即為對偶問題最優(yōu)解對偶最優(yōu)解的經(jīng)濟(jì)含義——影子價格由對偶定理求z*對bi的偏導(dǎo)數(shù)所以對偶最優(yōu)解為原問題各資源的影子價格影子價格非資源的市場價格，而是指系統(tǒng)達(dá)到最優(yōu)狀態(tài)時，資源的單位變化引起目標(biāo)最優(yōu)值的變化對偶單純形法是求解線性規(guī)劃的另一的基本方法。它是根據(jù)對偶原理和單純形法的原理而設(shè)計出來的，因此稱為對偶單純形法。不要簡單理解為是求解對偶問題的單純形法。由對偶理論可以知道，對于一個線性規(guī)劃問題，我們能夠通過求解它的對偶問題來找到它的最優(yōu)解。什么是對偶單純形法？也就是說，求解原問題（LP）時，可以從（LP）的一個基本解（并不一定是基可行解）開始，逐步迭代，使目標(biāo)函數(shù)值（Z=Yb=CBB-1b=CX）減少，當(dāng)?shù)絏B=B-1b≥0時，即找到了（LP）的最優(yōu)解，這就是對偶單純形法。同原始單純形求法一樣，求解對偶問題（DP），也可以從（DP）的一個基本可行解開始，從一個基本可行解（迭代）到另一個基本可行解，使目標(biāo)函數(shù)值減少。例一、用對偶單純形法求解：解：將模型轉(zhuǎn)化為cj-9-12-15000cBxBbx1x2x3x4x5x60x4-10-2-2-11000x5-12-2-3-10100x6-14-1-1-5001(-9/-1.-12/-1.

-15/-5)-Z′

0-9-12-15000cj-9-12-15000cBxBbx1x2x3x4x5x60x4-36/5-9/5-9/5010-1/50x5-46/5-9/5-14/5001-1/5-15x314/51/51/5100-1/5(-30/-9.-45/-14.-15/-1)-Z′

42-6-9000-3cj-9-12-15000cBxBbx1x2x3x4x5x60x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14(-3/-9.-45/-9.-33/-1)-15x315/71/140101/14-3/14-Z′

501/7-3/14000-45/14-33/14cj-9-12-15000cBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9-Z′

72000-1/3-3-7/3

所以，

X*=（2.2.2.0.0.0），

Z′*=－72，

原問題Z*=72

其對偶問題的最優(yōu)解為：

Y*=(1/3.3.7/3)，W*=72練習(xí)：cj-2-3-400cBxBbx1x2x3x4x50x4-3-1-2-1100x5-4-21-301-Z

-2-3-400cj-2-3-400cBxBbx1x2x3x4x50x4-10-5/21/21-1/2-2x121-1/23/20-1/2-Z

0-4-10-1cj-2-3-400cBxBbx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5-Z

28/500-3/5-8/5-1/5Y=（8/5.1/5）X=（2/5.11/5.0）Z=28/5靈敏度分析為什么要進(jìn)行靈敏度分析？前面對線性規(guī)劃的討論，價值系數(shù)c，資源系數(shù)b和技術(shù)系數(shù)矩陣A都是已知常數(shù)。但現(xiàn)實(shí)中，這些系數(shù)可能只是估計量，存在誤差或隨著時間的推移可能有些許變化糟糕！這個月產(chǎn)品市場價格與原計劃時發(fā)生變化了。年初安排的生產(chǎn)計劃還是最優(yōu)的么？價值系數(shù)變化的靈敏度分析設(shè)只有一個價值系數(shù)cj發(fā)生變化，其它系數(shù)不變，那么cj在什么范圍內(nèi)變化而最優(yōu)解不變呢？例(生產(chǎn)計劃問題)maxz=70x1+120x2s.t.9x1＋4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0模型價值系數(shù)變化的靈敏度分析設(shè)只有一個價值系數(shù)cj發(fā)生變化，其它系數(shù)不變，那么cj在什么范圍內(nèi)變化而最優(yōu)解不變呢？例(生產(chǎn)計劃問題)最優(yōu)單純形表cj70120000CBXBbX1X2X3X4X5

070120X3X1X2842024001-3.121.161000.4-0.2010-0.120.164280000-13.6-5.2考慮C2發(fā)生變化價值系數(shù)變化的靈敏度分析設(shè)只有一個價值系數(shù)cj發(fā)生變化，其它系數(shù)不變，那么cj在什么范圍內(nèi)變化而最優(yōu)解不變呢？例(生產(chǎn)計劃問題)最優(yōu)單純形表cj70c2

000CBXBbX1X2X3X4X5

070c2X3X1X2842024001-3.121.161000.4-0.2010-0.120.164280000-28+0.12c2

14-0.16c2

顯然只要-28+0.12c2≤014-0.16c2≤0

成立，則最優(yōu)解不變！

即

87.5≤c2≤233.33右端項(xiàng)變化的靈敏度分析考察單純形表0zIb0Cb變化只影響因此，只要B-1b≥0,則最優(yōu)基不變從而對偶最優(yōu)解不變，也即影子價格不變例如生產(chǎn)計劃問題,考慮b3變化的靈敏度分析最優(yōu)單純形表由此可見，(p3,p1,p2)是最優(yōu)基，即B-1b≥0解得227.586≤b3≤400計算機(jī)靈敏度分析的例子生產(chǎn)計劃問題Excel生產(chǎn)計劃問題DM多個參數(shù)變化的靈敏度分析百分之百法則：(1)對