對(duì)偶問題與靈敏度分析

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

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

(LP)Maxz=CX

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

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

分別為原問題和對(duì)偶問題的可行解則,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（無界性）若一個(gè)問題無界，則另一個(gè)問題不可行maxz=x1+x2

s.t.-2x1+x2

≤40x1-x2

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

≥

1y1-y2≥1y1,y2

≥0對(duì)偶問題顯然無可行解！例如定理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問題的任一可行解，由弱對(duì)偶性CX*≤Y(0)b=CX(0)從而X(0)是最優(yōu)解同理Y(0)是最優(yōu)解定理4（對(duì)偶定理）若其中一個(gè)問題有最優(yōu)解，則另一個(gè)問題也有最優(yōu)解，且兩者最優(yōu)值相等證明證明：設(shè)X*是LP問題的最優(yōu)解，相應(yīng)的最優(yōu)基為B，則檢驗(yàn)數(shù)必定滿足令則有因而Y*是對(duì)偶問題的可行解又因而Y*是對(duì)偶問題的最優(yōu)解0zIb0C定理5（互補(bǔ)松弛定理）原問題及其對(duì)偶問題的可行解X(0)和Y(0)是最優(yōu)解的充要條件是：

Y(0)XS=0，YSX(0)=0XS,YS分別為原問題松弛向量和對(duì)偶問題剩余向量該定理說明：一對(duì)對(duì)偶問題達(dá)到最優(yōu)，當(dāng)且僅當(dāng)松約束對(duì)應(yīng)的對(duì)偶變量必定是緊的利用互補(bǔ)松馳定理，可以在知道一個(gè)問題的最優(yōu)解時(shí)，求解其對(duì)偶問題的最優(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對(duì)偶問題y1*=4/5,y2*=3/5對(duì)偶問題的最優(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，即原問題第一個(gè)約束取等式同理，第2個(gè)約束也取等式定理6若原問題最優(yōu)解存在，則原問題最優(yōu)單純形表的檢驗(yàn)數(shù)行中，松弛變量的檢驗(yàn)數(shù)和剩余變量的檢驗(yàn)數(shù)的相反數(shù)即為對(duì)偶問題最優(yōu)解對(duì)偶最優(yōu)解的經(jīng)濟(jì)含義——影子價(jià)格由對(duì)偶定理求z*對(duì)bi的偏導(dǎo)數(shù)所以對(duì)偶最優(yōu)解為原問題各資源的影子價(jià)格影子價(jià)格非資源的市場(chǎng)價(jià)格，而是指系統(tǒng)達(dá)到最優(yōu)狀態(tài)時(shí)，資源的單位變化引起目標(biāo)最優(yōu)值的變化對(duì)偶單純形法是求解線性規(guī)劃的另一的基本方法。它是根據(jù)對(duì)偶原理和單純形法的原理而設(shè)計(jì)出來的，因此稱為對(duì)偶單純形法。不要簡單理解為是求解對(duì)偶問題的單純形法。由對(duì)偶理論可以知道，對(duì)于一個(gè)線性規(guī)劃問題，我們能夠通過求解它的對(duì)偶問題來找到它的最優(yōu)解。什么是對(duì)偶單純形法？也就是說，求解原問題（LP）時(shí)，可以從（LP）的一個(gè)基本解（并不一定是基可行解）開始，逐步迭代，使目標(biāo)函數(shù)值（Z=Yb=CBB-1b=CX）減少，當(dāng)?shù)絏B=B-1b≥0時(shí)，即找到了（LP）的最優(yōu)解，這就是對(duì)偶單純形法。同原始單純形求法一樣，求解對(duì)偶問題（DP），也可以從（DP）的一個(gè)基本可行解開始，從一個(gè)基本可行解（迭代）到另一個(gè)基本可行解，使目標(biāo)函數(shù)值減少。例一、用對(duì)偶單純形法求解：解：將模型轉(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

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

070120X3X1X2842024001-3.121.161000.4-0.2010-0.120.164280000-13.6-5.2考慮C2發(fā)生變化價(jià)值系數(shù)變化的靈敏度分析設(shè)只有一個(gè)價(jià)值系數(shù)cj發(fā)生變化，其它系數(shù)不變，那么cj在什么范圍內(nèi)變化而最優(yōu)解不變呢？例(生產(chǎn)計(jì)劃問題)最優(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)基不變從而對(duì)偶最優(yōu)解不變，也即影子價(jià)格不變例如生產(chǎn)計(jì)劃問題,考慮b3變化的靈敏度分析最優(yōu)單純形表由此可見，(p3,p1,p2)是最優(yōu)基，即B-1b≥0解得227.586≤b3≤400計(jì)算機(jī)靈敏度分析的例子生產(chǎn)計(jì)劃問題Excel生產(chǎn)計(jì)劃問題DM多個(gè)參數(shù)變化的靈敏度分析百分之百法則：(1)對(duì)