4運(yùn)籌學(xué)第二章線性規(guī)劃的對偶理論課件

運(yùn)籌學(xué)基礎(chǔ)1第二章線性規(guī)劃

對偶問題的提出原問題與對偶問題的關(guān)系對偶問題的基本性質(zhì)對偶單純形法靈敏度分析2運(yùn)籌學(xué)基礎(chǔ)解：設(shè)生產(chǎn)x1的產(chǎn)品I，x2的產(chǎn)品II，則目標(biāo)函數(shù)maxz＝2x1+3x2約束條件x1+2x2≤84x1≤164x2≤12

x1﹑x2≥0線性規(guī)劃的對偶理論例1

某廠可生產(chǎn)產(chǎn)品Ⅰ和Ⅱ，生產(chǎn)I需1臺設(shè)備，4單位原料A，生產(chǎn)II需2臺設(shè)備，4單位原料B。該廠每生產(chǎn)一件產(chǎn)品Ⅰ獲利2元﹐每生產(chǎn)一件產(chǎn)品Ⅱ獲利3元。現(xiàn)有8臺設(shè)備，16單位原料A，12單位原料B，問如何安排計(jì)劃使獲利最多?運(yùn)籌學(xué)基礎(chǔ)3第二章線性規(guī)劃

對偶問題的提出

原問題與對偶問題的關(guān)系對偶問題的基本性質(zhì)對偶單純形法靈敏度分析44.1對偶問題的提出運(yùn)籌學(xué)基礎(chǔ)我們從另一個角度來討論這個問題：假設(shè)不生產(chǎn)產(chǎn)品Ⅰ﹑Ⅱ，而將所有資源出租或外售。問題：考慮每種資源如何定價。54.1對偶問題的提出運(yùn)籌學(xué)基礎(chǔ)例1產(chǎn)品Ⅰ：1臺設(shè)備，4單位原料A，獲利2元；產(chǎn)品Ⅱ：2臺設(shè)備，4單位原料B，獲利3元?，F(xiàn)有：8臺設(shè)備，16單位原料A，12單位原料B設(shè)y1，y2，y3分別表示出售單位設(shè)備臺時的租金和出讓原材料A，B的附加額。根據(jù)題意可得：

y1+4y2≥2，2y1+4y3≥3，

ω=8y1+16y2+12y3要實(shí)現(xiàn)出租的愿望，只能在滿足≥所有產(chǎn)品的利潤條件下，必須使ω盡可能的小。

64.1對偶問題的提出運(yùn)籌學(xué)基礎(chǔ)為此需解決如下的線性規(guī)劃問題：

y1+4y2≥22y1+4y3≥3minω=8y1+16y2+12y2

y1

，y2

，y3≥0maxz＝2x1+3x2x1＋2x2≤84x1≤164x2≤12x1﹐x2≥0與關(guān)系？對原模型設(shè)：124004A=C=(2，3)

b=(8,16,12)TX=（x1，x2）TY=（y1，y2，y3）則可得:74.1對偶問題的提出運(yùn)籌學(xué)基礎(chǔ)maxz=CXAX≤b

（5.1）X≥0

y1+4y2≥22y1+4y3≥3minω=8y1+16y2+12y3

y1

，y2

，y3≥0maxz＝2x1+3x2x1＋2x2≤84x1≤164x2≤12x1﹐x2≥0與有何關(guān)系？對愿模型設(shè)：124004A=C=(2，3)

b=(8,16,12)TX=（x1，x2）TY=（y1，y2，y3）則可得:minω=YbYA≥C

（5.2）Y≥0和我們把（5.2）式的問題稱為（5.1）式問題的對偶線性規(guī)劃問題。運(yùn)籌學(xué)基礎(chǔ)8第二章線性規(guī)劃

對偶問題的提出原問題與對偶問題的關(guān)系對偶問題的基本性質(zhì)對偶單純形法靈敏度分析94.2原問題與對偶問題的關(guān)系運(yùn)籌學(xué)基礎(chǔ)1﹒對稱式的對偶“≤”不等式約束條件的原問題與“≥”不等式約束條件的對偶問題，稱為對稱式的一對對偶問題。原問題：maxz=c1x1+c2x2+…+cnxn

a11

a12…a1n

am1

am2…amn·········x1xn···b1bm···≤

x1，x2，…，xn≥0對偶問題：minω=b1y1+b2y2+…+bmym

a11

a12…a1n

am1

am2…amn·········≥

y1，y2，…，ym≥0(y1,y2,…,ym)(c1,c2,…,cn)

n個變量，m個約束條件

m個變量，n個約束條件10運(yùn)籌學(xué)基礎(chǔ)2﹒約束條件全部為“=”的對偶maxz=CXAX＝bX≥0原問題：maxz=CXAX≤bX≥0AX≥b等價maxz=CXAX≤bX≥0－AX≤－bmaxz=CXX≥0A－AX≤b－bminω=(Y1,Y2)Y1,Y2≥0A－A≥Cb－b(Y1,Y2)其中

Y1=(y1,y2,…ym)，Y2=(ym+1,ym+2,…y2m)等價等價minω=YbY為無約束YA≥Cminω=(Y1－Y2)bY1,Y2≥0(Y1－Y2)A≥C令Y=(Y1－Y2)對偶問題對偶問題114.2原問題與對偶問題的關(guān)系運(yùn)籌學(xué)基礎(chǔ)3﹒約束條件為“≥”的對偶maxz=CXAX≥bX≥0原問題：maxz=CX－AX≤－

bX≥0minω=Y1(－b)Y1(－A)≥CY1≥0minω=YbYA≥CY≤0等價對偶問題令Y=

－Y1對偶問題12運(yùn)籌學(xué)基礎(chǔ)4﹒變量≤0的對偶maxz=CXAX≤bX≤0原問題：令X=

－X1maxz=C(－X1)A(－X1)≤bX1≥0maxz=(－C)X1(－A)X1≤bX1≥0minω=YbY

(－A)≥－CY≥0minω=YbY

A≤CY≥0對偶問題對偶問題等價13運(yùn)籌學(xué)基礎(chǔ)5﹒變量無約束的對偶maxz=CXAX≤bX無約束原問題：令X=X1－X2X1，X2≥0maxz=CX1－CX2X1,X2≥0AX1－AX2≤bmaxz=(C,－C)X1,X2≥0≤bX1X2(A,－A)X1X2等價minω=YbY≥0Y(A,－A)≥(C,－C)對偶minω=YbYA≥CY≥0－YA≥－Cminω=YbYA

＝CY≥0minω=YbYA≥CY≥0YA≤C等價等價等價對偶問題14運(yùn)籌學(xué)基礎(chǔ)6﹒原問題與對偶問題的關(guān)系表原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標(biāo)函數(shù)maxzn個變量變量≥0變量≤0變量無約束目標(biāo)函數(shù)minω

n個約束條件約束≥約束≤約束=m個約束條件約束≥約束≤約束=約束條件右端項(xiàng)目標(biāo)函數(shù)變量系數(shù)m個變量變量≤0變量≥0變量無約束目標(biāo)函數(shù)變量系數(shù)約束條件右端項(xiàng)15運(yùn)籌學(xué)基礎(chǔ)例：求下列線性規(guī)劃問題的對偶問題maxz＝5x1+4x2+6x3x1+2x2≥2x1+x3≤3﹣3x1+2x2+x3≤﹣5x1≥0

﹐x2≤0,x3無約束

x1－x2+x3=1C=(5,4,6)

b=(2,3,-5,1)T120101-321A=1-11解：因原問題有3個變量，4個約束條件，所以對偶問題4個變量，3個約束條件。設(shè)變量Y=(y1,y2,y3,y4)minω=2y1+3y2－5y3+y4于是

y1+y2－3y3+y4≥52y1+2y3－y4≤4

y2+y3+y4＝6y1≤0,y2,y3≥0,y4無約束YAC確定約束條件運(yùn)籌學(xué)基礎(chǔ)16第二章線性規(guī)劃

對偶問題的提出

原問題與對偶問題的關(guān)系

對偶問題的基本性質(zhì)對偶單純形法靈敏度分析174.3對偶問題的基本性質(zhì)運(yùn)籌學(xué)基礎(chǔ)1﹒對稱性：對偶問題的對偶問題是原問題。證：設(shè)原問題為：maxz=CX；AX≤b；X≥0則對偶問題為：minω=Yb；YA≥C；Y≥0因minω=max(﹣ω)max(﹣ω)=﹣Yb；﹣YA≤﹣C；Y≥0min(﹣ω1)=﹣CX；﹣AX≥﹣b；X≥0對偶問題又因min(﹣ω1)

=max(ω1)max(ω1)=CX；AX≤b；X≥0這就是原問題。184.3對偶問題的基本性質(zhì)運(yùn)籌學(xué)基礎(chǔ)2﹒弱對偶性：若X(0)是原問題的可行解，Y(0)是對偶問題的可行解，則存在CX(0)≤Y(0)b。證：設(shè)原問題為：maxz=CX；AX≤b；X≥0則因X(0)是原問題的可行解，所以AX(0)≤b又因Y(0)是對偶問題的可行解，所以Y(0)A≥C

Y

(0)

AX(0)≤Y

(0)

b

因此，CX(0)≤Y(0)

AX(0)≤Y(0)

b結(jié)論成立。對偶問題為：minω=Yb；YA≥C；Y≥0Y

(0)

AX(0)≥CX

(0)

194.3對偶問題的基本性質(zhì)運(yùn)籌學(xué)基礎(chǔ)3﹒無界性：若原問題無界解，則其對偶問題無可行解。證：由弱對偶性可知結(jié)論成立。(CX

(0)≤Y(0)

b)4﹒最優(yōu)性：若X(0)是原問題的可行解，Y(0)是對偶問題的可行解，且CX(0)=Y(0)

b

，則X(0)，Y(0)是最優(yōu)解。證：設(shè)Y(1)是對偶問題的任意可行解，由性質(zhì)2可得Y(1)

b≥CX(0)=Y(0)b

，則Y(0)

是對偶問題的最優(yōu)解。設(shè)X(1)是原問題的任意可行解，由性質(zhì)2可得CX

(0)=Y(0)b≥CX(1)

，則X(0)

是原問題的最優(yōu)解。204.3對偶問題的基本性質(zhì)運(yùn)籌學(xué)基礎(chǔ)5﹒對偶定理：若原問題有最優(yōu)解，那么對偶問題也有優(yōu)解；且目標(biāo)函數(shù)值相等。證：設(shè)X(0)

是原問題的最優(yōu)解，它對應(yīng)的基B，必有C－CBB-1A≤0，且z=CX(0)=CBB-1b

。令Y(0)=CBB-1顯然，Y(0)A≥C

。所以Y(0)是對偶問題的可行解。又因Y(0)b=CBB-1b=CX(0)由性質(zhì)4可知Y

(0)是對偶問題的最優(yōu)解。因此，結(jié)論成立。21運(yùn)籌學(xué)基礎(chǔ)6﹒互補(bǔ)松弛性：若X(0)是原問題的可行解，Y(0)是對偶問題的可行解，則YξX(0)=0和Y(0)Xξ=0當(dāng)且僅當(dāng)X(0)，Y(0)是最優(yōu)解。證：maxz=CXAX+xξ=bX≥0，Xξ

≥0設(shè)原問題和對偶問題的標(biāo)準(zhǔn)型是minω=YbYA－Yξ=CY≥0，Yξ

≥0將原問題目標(biāo)函數(shù)中的系數(shù)向量C用C=YA－Yξ代替：

z=(YA－Yξ)X=YAX

－YξX(5.3)對偶問題目標(biāo)函數(shù)中的系數(shù)向量，用b=AX+Xξ代替：

ω=Y(AX+Xξ)=YAX+YXξ(5.4)①YξX(0)=0和Y(0)

Xξ=0,則Y(0)b=Y

(0)

AX

(0)=CX(0)②X(0),Y(0)

最優(yōu)解,則Y(0)b=Y

(0)

AX

(0)=CX(0)(性質(zhì)3),所以Yξ

X(0)=0和Y(0)

Xξ=0。X(0)

，Y(0)

是最優(yōu)解22運(yùn)籌學(xué)基礎(chǔ)7﹒設(shè)原問題：maxz=CX；AX+Xξ=b；X,Xξ≥0對偶問題：minω=Yb；YA－Yξ=C；Y,Yξ≥0。則原問題單純形表的檢驗(yàn)數(shù)行對應(yīng)其對偶問題的一個基解。其關(guān)系如表：ＸＢＸＮＸξ0Yξ1CN1－CBB-1N1﹣Yξ2－CBB-1﹣Y這里Yξ1對應(yīng)原問題的基變量XB的剩余變量，Yξ2對應(yīng)原問題的非基變量XN的剩余變量。證：maxz=CBXB+CNXNBXB+BXN+Xξ=bXN,XB,Xξ

≥0設(shè)B是一可行基，于是A=(B,N)minω=YbYB－Yξ1=CB

(5.5)Y,Yξ1

Yξ2≥0YN－Yξ2=CN

(5.6)234.3對偶問題的基本性質(zhì)運(yùn)籌學(xué)基礎(chǔ)證：maxz=CBXB+CNXNBXB+BXN+Xξ=bX,XB,Xξ

≥0設(shè)B是一可行基，于是A=(B,N)minω=YbYB－Yξ1=CB

(5.5)Y,Yξ1

Yξ2≥0YN－Yξ2=CN

(5.6)其中Yξ=(Yξ1,Yξ2)當(dāng)原問題的解為：XB=B-1b

時，其檢驗(yàn)參數(shù)為CN－CBB-1N

與－CBB-1。令Y=CBB-1，將它代入(5.5)和

(5.6)得Yξ1=0，﹣Yξ2=CN－CBB-1N

因此，結(jié)論成立。244.3對偶問題的基本性質(zhì)運(yùn)籌學(xué)基礎(chǔ)8﹒單純形乘子Y的定理：若B是原問題的一最優(yōu)可行基，則單純形乘子Y=CBB-1是對偶問題的一個最優(yōu)解。證：設(shè)X

(0)

是對應(yīng)基B的原問題的最優(yōu)解，則顯然，YA≥C

。所以Y

是對偶問題的可行解。又因Yb=CBB-1b=CX

(0)由性質(zhì)4可知Y

是對偶問題的最優(yōu)解。因此，結(jié)論成立。C－CBB-1A≤0，且z=CX

(0)CBB-1b

。根據(jù)本性質(zhì)，可以從原問題最優(yōu)解的單純形表中直接得到對偶問題的最優(yōu)解。25運(yùn)籌學(xué)基礎(chǔ)9﹒最優(yōu)對偶變量(影子價格)的經(jīng)濟(jì)解釋從對偶定理可知，當(dāng)達(dá)到最優(yōu)解時，原問題和對偶問題的目標(biāo)函數(shù)值相等，即z=CX(0)=Y(0)b=CBB-1b.也即z=CX(0)=Y(0)b=CBB-1b=y1(0)b1+y2(0)b2

+…+ym(0)bm

其中X(0),Y(0)分別是原問題和對偶問題的最優(yōu)解。現(xiàn)在考慮在最優(yōu)解處，常數(shù)項(xiàng)bi的微小變動對目標(biāo)函數(shù)值的影響(不改變原來的最優(yōu)基).求z對bi的偏導(dǎo)數(shù)，可得：y1(0)

＝?z—?b1,y2(0)

＝?z—?b2,ym(0)

＝?z—?bm,…這說明，若原問題的某一約束條件的右端常數(shù)項(xiàng)bi

增加一個單位，則由此引起的最優(yōu)目標(biāo)函值的增加量，就等于該約束條件相對應(yīng)的對偶變量的最優(yōu)值。最優(yōu)變量yi(0的值，就相當(dāng)于對單位第I種資源在實(shí)現(xiàn)最大利潤時的一種估價。這種估價是針對具體企業(yè)具體產(chǎn)品而存在的一種特殊價格，稱它為“影子價格”。“影子價格”對市場有調(diào)節(jié)作用。26運(yùn)籌學(xué)基礎(chǔ)例已知線性規(guī)劃問題

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

x1,x2,x3,x4,x5≥0其對偶問題的最優(yōu)解為y1*=4/5,y2*=3/5；z=5。試用對偶理論找出原問題的最優(yōu)解。解：對偶問題maxz＝4y1+3y2y1+2y2≤2①y1－y2≤3②2y1+3y2≤5③y1﹐y2≥0y1+y2≤2④3y1+y2≤3⑤C=(2,3,5,2,3)

b=(4,3)T11213A=2-1311YAC確定約束條件

Y=(y1,y2)原對min變≥0≤0無max約≤≥＝約≥≤＝變≥0≤0無關(guān)系表形成27運(yùn)籌學(xué)基礎(chǔ)原對min變≥0≤0無max約≤≥＝約≥≤＝變≥0≤0無解：對偶問題maxz＝4y1+3y2y1+2y2≤2①y1－y2≤3②2y1+3y2≤5③y1﹐y2≥0y1+y2≤2④3y1+y2≤3⑤C=(2,3,5,2,3)

b=(4,3)T11213A=2-1311YAC確定約束條件

Y=(y1,y2)關(guān)系表形成設(shè)Xξ=(xξ1,

xξ2)T，Yξ=(yξ1,

yξ2,

yξ3,

yξ4,

yξ5)把y1*=4/5,y2*=3/5代入約束條件中可得Yξ=(0,

14/5

,8/5

,2/5

,

0)據(jù)互補(bǔ)松弛性：YξX*=0YξX*=14/5x2*+8/5x3*+2/5x4*=0所以x2*=x3*=x4*=0又因Y*Xξ=4/5xξ1+3/5xξ2=0所以xξ1=xξ2=0284.3對偶問題的基本性質(zhì)運(yùn)籌學(xué)基礎(chǔ)設(shè)Xξ=(xξ1,

xξ2)T，Yξ=(yξ1,

yξ2,

yξ3,

yξ4,

yξ5)把y1*=4/5,y2*=3/5代入約束條件中可得Yξ=(0,

14/5

,8/5

,2/5

,

0)據(jù)互補(bǔ)松弛性：YξX*=0YξX*=14/5x2*+8/5x3*+2/5x4*=0所以x2*=x3*=x4*=0又因Y*Xξ=4/5xξ1+3/5xξ2=0所以xξ1=xξ2=0因?yàn)樗?/p>

x1*+x2*

+2x3*

+x4*

+3x5*

+xξ1=42x1*

－x2*

+3x3*

+x4*

+x5*

+xξ2=3

x1*+3x5*

=42x1*

+x5*

=3x1*=1，x5*=1因此，原問題最優(yōu)解為X*=(1，0，0，0，1)T，ω*=5。運(yùn)籌學(xué)基礎(chǔ)29第二章線性規(guī)劃

對偶問題的提出

原問題與對偶問題的關(guān)系對偶問題的基本性質(zhì)

對偶單純形法靈敏度分析304.4對偶單純形法運(yùn)籌學(xué)基礎(chǔ)1﹑對偶單純形法與單純形法的區(qū)別1.1對偶單純形法的思路原理：由性質(zhì)7可知：在單純形表中進(jìn)行迭代時，在b列中得到的是原問題的基可行解，而在檢驗(yàn)數(shù)行得到的是對偶問題的基解。通過逐步迭代，當(dāng)在檢驗(yàn)數(shù)行得到對偶問題的解也是基可行解時，根據(jù)性質(zhì)4，5可知，已得到最優(yōu)解。即原問題與對偶問題都是最優(yōu)解。思路：在進(jìn)行迭代時，保持對偶問題的解是基可行解，即cj－CBB-1pj≤0，而原問題通過逐步迭代，達(dá)到基可行解，這樣就得到最優(yōu)解。314.4對偶單純形法運(yùn)籌學(xué)基礎(chǔ)1.2對偶單純形法與單純形法的區(qū)別單純形法：在迭代中，保持b列中得到的是原問題的基可行解，逐步得到對偶問題的基可行解。對偶單純形法：在逐步迭代中，保持檢驗(yàn)數(shù)行cj－CBB-1pj≤0，即保持對偶問題的解是基可行解。通過迭代得到原問題的基可行解。說明：對偶單純法是運(yùn)用對偶原理求解原問題的一種方法，而不是求解對偶問題的單純法。2﹑對偶單純形法求解步驟2.1對偶可行的基解：

設(shè)X(0)是原問題的基解，其對應(yīng)的基為B，記Y=CBB-1，若Y是對偶問題的基可行解。即C－CBB-1A≤0，則稱X(0)是原問題的對偶可行的基解。32運(yùn)籌學(xué)基礎(chǔ)2.2對偶單純形法的計(jì)算步驟⑴列出初始單純形表⑵最優(yōu)性檢驗(yàn)

根據(jù)線性規(guī)劃問題，確定一個對偶可行的基解，列出初始單純形表。

檢查b列的數(shù)，若都為非負(fù)，則已得到最優(yōu)解。停止計(jì)算。若b列的數(shù)中，還有分量為負(fù)數(shù)，則進(jìn)行下一步計(jì)算。⑶確定換出變量

按min{(B-1b)i|(B-1b)i<0}=(B-1b)l

確定xl為換出變量。⑷確定換入變量①如果xl所在行各系數(shù)alj(j=1,2,…n).都有alj>0，則無可行解，停止計(jì)算。②如果有alj<0(

j=1,2,…n),則計(jì)算ck－zkθ＝mincj－zj———alj|alj<０＝———alk確定xk為換入變量，且保持得到的對偶問題的解是基可行解。⑸迭代運(yùn)算

以alk為主元素，對單純形表進(jìn)行迭代運(yùn)算，得到新單純表。重復(fù)⑵—⑸33運(yùn)籌學(xué)基礎(chǔ)⑴“按θ規(guī)則確定換入變量，確保變換后，對偶問題的解仍然是可行解?！钡淖C明：因經(jīng)過初等變換后aij′=—aikaljalkaij

－——aljalki≠li＝lδj′=cj－zj′=cj－i=1,i≠lm∑ciaij′

ck

—

aljalk

－=δj－

—δkaljalk=(－

－)alj≤0δkalk

—δjalj所以變換后，對偶問題的解是基可行解。（j是非基變量下角標(biāo)。）2.3兩個說明⑵初始對偶可行的基解的確定運(yùn)用對偶單純法，需要先給定一個對偶可行的基解，而這個解有時不易直接得到。我們可先構(gòu)造一個擴(kuò)充34運(yùn)籌學(xué)基礎(chǔ)⑵初始對偶可行的基解的確定運(yùn)用對偶單純法，需要先給定一個對偶可行的基解，而這個解有時不易直接得到。我們可先構(gòu)造一個擴(kuò)充問題，通過求解擴(kuò)充問題的解給出原問題的解。原問題如下，Ｂ是一基，Ｎ是非基向量構(gòu)成的矩陣。maxz＝ＣＸX≥0

＝bj∈N∑pjxjXB+增加一個變量xn+1，和一個約束條件

＝Mj∈N∑xjXn+1+M是大正數(shù)。于是擴(kuò)充問題maxz＝ＣＸX≥0

＝bj∈N∑pjxjXB+

＝Mj∈N∑xjXn+1+可以得基解XＢ（０）=bM由此易求一對偶可行的基解。354.4對偶單純形法運(yùn)籌學(xué)基礎(chǔ)若ＸＢ(0)不是對偶可行的，即檢驗(yàn)數(shù)中有正的。并設(shè)正檢驗(yàn)數(shù)中最大的一個為δk，則以δk相應(yīng)的變量xk為換入變量，以xn+1為換出變量，即以am+1,k為主元素進(jìn)行初等變換，可得到全部檢驗(yàn)數(shù)≤０，即得到一個對偶可行的基解。理由如下：初等變換前﹑后檢驗(yàn)數(shù)之間的關(guān)系:δj′=δj－———δkam+1jam+1k其中δj′是變換后新基下的檢驗(yàn)數(shù)。當(dāng)j∈N∪{n+1}時，am+1,j=1，所以δj′=δj－δk≤0當(dāng)j∈N∪{n+1}時，am+1,j=0,δj=0所以δj′=0﹨因此，變換后，有δj′≤0，得到的基解是對偶可行的。擴(kuò)充問題的解與原問題解的關(guān)系：若擴(kuò)充問題無可行解，則原問題無可行解。若擴(kuò)充問題的目標(biāo)函數(shù)最優(yōu)值與M無關(guān)，則得到原問題的最優(yōu)解。用對偶單純形法求擴(kuò)充問題的最優(yōu)解，依此得到原問題最優(yōu)解。36運(yùn)籌學(xué)基礎(chǔ)2.4舉例例用對偶單純形法求解x1+2x2+x3≥32x1－x2+3x3≥4minω=2x1+3x2+4x3x1,x2,x3≥0﹣x1﹣2x2﹣x3+

x4=﹣3﹣2x1+x2﹣3x3+x5=﹣4maxz=﹣2x1﹣3x2﹣4x3x1,x2,x3x4,x5≥0解：cj﹣2﹣3﹣400CBXBbx1x2x3x4x500x4x5﹣3﹣4﹣1[﹣2]﹣21﹣1﹣31001δj

﹣2﹣3﹣400θ1－4/3其中x4,x5為松弛變量37運(yùn)籌學(xué)基礎(chǔ)cj﹣2﹣3﹣400CBXBbx1x2x3x4x50﹣2x4x1﹣1201[﹣5/2]﹣1/21/23/210﹣1/2﹣1/2δj

0﹣4﹣10﹣1θ﹣8/5﹣﹣2cj﹣2﹣3﹣400CBXBbx1x2x3x4x5﹣3﹣2x2x12/511/50110﹣1/57/5﹣2/5﹣1/51/5﹣2/5δj

00﹣9/5﹣8/5﹣1/5原最優(yōu)X*=(11/5,2/5,0,0,0)T，對偶最優(yōu)Y*=(8/5,1/5)運(yùn)籌學(xué)基礎(chǔ)38第二章線性規(guī)劃

對偶問題的提出

原問題與對偶問題的關(guān)系對偶問題的基本性質(zhì)對偶單純形法

靈敏度分析394.5靈敏度分析運(yùn)籌學(xué)基礎(chǔ)在前面討論線性規(guī)劃問題時，假定aij,bi,cj都是常數(shù).但實(shí)際上這些參數(shù)往往是估計(jì)值和預(yù)測值.所謂靈敏度分析,就是要研究初始單純形表上的系數(shù)變化對最優(yōu)解的影響,研究這些系數(shù)在什么范圍內(nèi)變化時,原最優(yōu)基仍是最優(yōu)；若原最優(yōu)基不再是最優(yōu)的，如何用最簡便的方法找到新的最優(yōu)解。設(shè)資源br發(fā)生變化，即br′=br+Δbr。并假定其它系數(shù)不變。則解變化為XB′=B-1(b+Δb)，其中Δb=(0,…,Δbr，

…,0）T。由于br變化不影響檢驗(yàn)數(shù)，所以只要XB′≥0，最優(yōu)基不變,XB′是最優(yōu)解。1.資源數(shù)量變化的分析下面分析Δbr保持XB′≥0的取值范圍：B-1(b+Δb)=B-1b+B-1Δb=B-1b+B-10·Δbr0·40運(yùn)籌學(xué)基礎(chǔ)下面分析Δbr保持XB′≥0的取值范圍：B-1(b+Δb)=B-1b+B-1Δb=B-1b+B-10·Δbr0·B--10·Δbr0·=a1r′Δbr··air′Δbramr′Δbr=Δbra1r′··air′amr′要使XB′≥0，只有bi′+air′Δbr≥0,i=1,2,…,m所以air′Δbr≥﹣bi′,i=1,2,…,m①當(dāng)air′

>0時，Δbr≥﹣bi′/air′

②當(dāng)air′

<0時，Δbr≤﹣bi′/air′

于是得到max{﹣bi′/air′|air′>0}≤Δbr≤min{﹣bi′/air′|