第2章-對偶理論和靈敏度分析課件

第二章 對偶理論與靈敏度分析§1單純形法的矩陣描述

設(shè)max

z=CXAX=bX

≥

0

A為m×n階矩陣RankA=m,取B為可行基,N為非基，

1第二章 對偶理論與靈敏度分析§1單純形法的矩陣描述12233求解步驟：4求解步驟：432利潤12kg40材料B16kg04材料A8臺時

21設(shè)備臺時限制

ⅡⅠ§2對偶問題的提出

[eg.1]制定生產(chǎn)計劃M1:max

z=2x1

+

3x21x1

+

2x2≤84x1

≤

16

4x2

≤

12x1，x2

≥

0

532利潤12kg40材料B16kg04材料A8臺時21設(shè)備現(xiàn)在出租，設(shè)y1為設(shè)備單位臺時的租金y2,y3為材料A、B轉(zhuǎn)讓附加費(kg-1)則M2為M1的對偶問題，反之亦然。M2:min

w=8y1

+

16y2

+

12y3y1+4y2

≥

22y1

+4y3≥3y1,y2,y3

≥

032利潤12kg40材料B16kg04材料A8臺時

21設(shè)備臺時限制

ⅡⅠ6現(xiàn)在出租，設(shè)y1為設(shè)備單位臺時的租金則M2為M1的對一般的，原問題：max

z=CXAX

≤

bX

≥

0

對偶問題：min

w=YbYA

≥

CY

≥

0比較：max

zmin

w

決策變量為n個約束條件為n個

約束條件為m個決策變量為m個“≤”“≥”7一般的，原問題：maxz=CXAX≤b§3對偶問題的化法1、典型情況

[eg.2]max

z=x1

+

2x2

+

x32x1

+

x2≤

62x2

+

x3≤

8x1,x2,x3

≥

0對偶：min

w=6y1

+

8y22y1

≥

1y1

+

2y2≥

2

y2≥

1y1,y2

≥

08§3對偶問題的化法對偶：minw=6y1+82、含等式的情況

[eg.3]max

z=x1

+

2x2

+

4x32x1

+

x2

+

3x3=3x1

+

2x2

+

5x3

≤

4x1,x2,x3

≥

0對偶：min

w=3y1’-3y1”+4y22y1’-2y1”+y2

≥

1y1’-y1”+2y2

≥

23y1’-3y1”+5y2

≥

4y1’,y1”,y2

≥

0令y1=y1’-y1”,則：

min

w=3y1+4y22y1

+y2

≥

1y1

+2y2

≥

23y1

+5y2

≥

4y2

≥

0，y1無約束一般，原問題第i個約束取等式，對偶問題第i個變量無約束。2x1

+

x2

+

3x3≤

3-2x1

-

x2

-

3x3

≤-392、含等式的情況對偶：minw=3y1’-3y1”3、含“≥”的max問題

[eg.4]max

z=x1

+

2x2

+

4x32x1

+

x2

+

3x3

≥

3x1

+

2x2

+

5x3

≤

4x1,x2,x3

≥

0對偶：min

w=-3y1’

+

4y2-2y1’

+

y2

≥

1-y1’

+

2y2

≥

2-3y1’

+

5y2

≥

4y1’,y2

≥

0令y1=-y1’，則：

min

w=3y1

+

4y22y1

+

y2

≥

1y1

+

2y2

≥

23y1

+

5y2

≥

4y1

≤

0,y2

≥

0-2x1

-

x2

-

3x3

≤-3103、含“≥”的max問題對偶：minw=-3y1’一般:①max問題第i個約束取“≥”，則min問題第i個變量

≤

0；②min問題第i個約束取“≤”，則max問題第i個變量

≤

0；③原問題第i個約束取等式，對偶問題第i個變量

無約束；④max問題第j個變量

≤

0,則min問題第j個約束取“≤”；⑤min問題第j個變量

≤

0

，則max問題第j個約束取“≥”

；⑥原問題第j個變量無約束，對偶問題第j個約束取等式。約束條件符號判斷：max->min相同，min->max相反決策變量符號判斷：max->min相反，min->max相同11一般:②min問題第i個約束取“≤”，則max問題第i個[eg.5]min

z=2x1

+

3x2

-

5x3

+

x4x1

+

x2

-

3x3

+x4

≥

52x1

+

2x3

-

x4

≤

4

x2

+

x3

+

x4=6x1

≤

0,x2,x3

≥

0,x4無約束對偶：max

w=5y1

+

4y2

+

6y3y1

+

y2

≥

2y1

+

y3

≤

3-3y1

+

2y2

+

y3

≤

-5y1

-

y2

+

y3=1y1

≥

0,y2

≤

0,y3無約束12[eg.5]minz=2x1+3x2-5x對偶問題的基本性質(zhì)一、單純形法計算的矩陣描述MaxZ=CXAX≤bX≥0其中X＝(x1,x2……xn)TMaxZ=CX+0XsAX+IXs=bX,Xs≥0其中Xs＝(xn+1,xn+2……xn+m)TI為m×m的單位矩陣13對偶問題的基本性質(zhì)一、單純形法計算的矩陣描述MaxZ=CX

項目非基變量基變量XBXNXs0XsbBNIcj-zjCBCN0……項目基變量非基變量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1對應(yīng)初始單純形表中的單位矩陣I，迭代后的單純形表中為B-1；初始單純形表中基變量Xs=b，迭代后的表中為XB=B-1b；約束矩陣（A，I）＝（B，N，I），迭代后為（B-1B，B-1N，B-1I）＝（I，B-1N，B-1)；初始單純形表中xj的系數(shù)向量為Pj，迭代后為Pj’，且Pj’=B-1Pj。14非基變量基變量XBmaxZ=4.5x1+5x2s.t.3x1+2x2≤244x1+5x2≤40x1,x2≥0minw=24y1+40y2s.t.3y1+4y2≥4.52y1+5x2≥5y1,y2≥0y1y2x1x2maxZ=4.5x1+5x2s.t.3x1+2x2+x3=244x1+5x2+x4=40x1,x2,x3,x4,≥0minw=24y1+40y2s.t.3y1+4y2-y3=4.52y1+5x2-y4=5y1,y2,y3,y4≥0y1y2x1x215maxZ=4.5x1+5x2minw=24y1+40y2y1cj4.5500θCBXBbx1x2x3x40x3243210120x44045018cj-zj4.55000x387/501-2/540/75x284/5101/510cj-zj1/200-14.5x140/7105/7-2/75x224/701-4/73/7cj-zj00-5/14-6/7Z=4.5×40/7＋5×24/7=300/7解原問題：16cj4.5500θCBXBbx1x2x3x40x324321解對偶問題：w=24×5/14＋40×6/7=300/7cj244000θCBYBby1y2y3y424y15/1410-5/74/740y26/7012/7-3/7cj-zj0040/724/717解對偶問題：w=24×5/14＋40×6/7=300/7cjcj4.5500θCBXBbx1x2x3x44.5x140/7105/7-2/75x224/701-4/73/7cj-zj00-5/14-6/7cj244000θCBYBby1y2y3y424y15/1410-5/74/740y26/7012/7-3/7cj-zj0040/724/7(x3,x4)=(0,0)(y3,y4)=(0,0)-y1-y2-y4-y3x1x2x4x3原問題對偶問題18cj4.5500θCBXBbx1x2x3x44.5x140/二、對偶問題的基本性質(zhì)原始問題maxz=CXs.t.AX≤b X≥0對偶問題minw=Y’bs.t.ATY≥C’ Y≥01.弱對偶性若X‘為原問題的可行解，Y’為對偶問題的可行解，則恒有CX’≤Y’b19二、對偶問題的基本性質(zhì)原始問題對偶問題1.弱對偶性19推論：原問題任一可行解的目標(biāo)函數(shù)是其對偶問題目標(biāo)函數(shù)值的下界，反之對偶問題任一可行解的目標(biāo)函數(shù)是其原問題目標(biāo)函數(shù)的上界。如原問題有可行解且目標(biāo)函數(shù)值無界，則其對偶問題無可行解；反之對偶問題有可行解且目標(biāo)函數(shù)無界，則原問題無可行解。（對偶問題無可行解時，其原問題無界解或無可行解。若原問題有可行解而其對偶問題無可行解時，原問題目標(biāo)函數(shù)無界若對偶問題有可行解而其原問題無可行解時，對偶問題目標(biāo)函數(shù)無界。20推論：202.最優(yōu)性若X‘為原問題的可行解，Y’為對偶問題的可行解，且CX‘＝Y(jié)’b則X’，Y‘分別為原問題和對偶問題的最優(yōu)解。3.強對偶性若原問題和對偶問題均具有可行解，則兩者均具有最優(yōu)解，且他們的最優(yōu)解的目標(biāo)值相等。212.最優(yōu)性3.強對偶性214.互補松弛定理在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為0，則該約束條件取嚴(yán)格等式，既松弛變量或剩余變量為0；反之如果對應(yīng)某一約束條件的對偶變量值不為0，則該約束條件取嚴(yán)格不等式，既松弛變量或剩余變量不為0.若yi’＞0,即xsi=0若yi’＝0,即xsi＞0即xsi·yi=0同理若xj’＞0,即ysj=0若xj’＝0,即ysj＞0即ysj·xj=0224.互補松弛定理若yi’＞0,即xsi=0同理22maxZ=4.5x1+5x2s.t.3x1+2x2+x3=244x1+5x2+x4=40x1,x2,x3,x4,≥0y1y2minw=24y1+40y2s.t.3y1+4y2-y3=4.52y1+5x2-y4=5y1,y2,y3,y4≥0x1x2X3=0,3x1+2x2=24,y1=14/5X4=0,4x1+5x2=40,y2=6/7y3=0,3y1+4y2=5,x1=40/7y4=0,2y1+5y2=5,x2=24/723maxZ=4.5x1+5x2y1y2minw=24y1+40利用互補松弛關(guān)系求解線性規(guī)劃minz=6x1+8x2+3x3s.t.x1+x2≥1x1+2x2+x3≥-1x1,x2,x3≥0maxw=y1-y2s.t.y1+y2≤6y1+2y2≤8y2≤3y1,y2≥0原始問題對偶問題012345678654321w1w2y=-1y=1y=3y=6最優(yōu)解為(y1,y2)=(6,0)maxy=6先用圖解法求解對偶問題。24利用互補松弛關(guān)系求解線性規(guī)劃minz=6x1+8x2+3xminz=6x1+8x2+3x3s.t.x1+x2≥1x1+2x2+x3≥-1x1,x2,x3≥0maxw=y1-y2s.t.y1+y2≤6y1+2y2≤8y2≤3y1,y2≥0maxw=y1-y2s.t.y1+y2+y3=6y1+2y2+y4=8y2+y5=3y1,y2,y3,y4,y5≥0(y1,y2)=(6,0)(y1,y2,y3,y4,y5)=(6,0,0,2,3)minz=6x1+8x2+3x3s.t.x1+x2-x4=1x1+2x2+x3-x5=-1x1,x2,x3,x4,x5≥0(x1,x2,x3|x4,x5)(y1,y2|y3,y4,y5)x2=x3=x4=0x1=1,x5=2引進剩余變量求對偶引進松弛變量圖解法求解代入約束求出松弛變量互補松弛關(guān)系代入約束求解(x1,x2,x3,x4,x5)=(1,0,0,0,2)25minz=6x1+8x2+3x3maxw=y1-y2ma§4對偶問題的性質(zhì)

1、對稱性對偶問題的對偶為原問題.26§4對偶問題的性質(zhì)1、對稱性2627272828推論：(1)max問題任一可解的目標(biāo)值為min問題目標(biāo)值的一個下界；(2)min問題任一可解的目標(biāo)值為max問題目標(biāo)值的一個上界。3、無界性若原問題(對偶問題)為無界解，則對偶問題(原問題)為無可行解。注：該性質(zhì)的逆不存在。若原(對偶)問題為無可行解，對偶(原問題)問題或為無界解，或為無可行解。29推論：3、無界性注：該性質(zhì)的逆不存在。若原(對偶)問4、最優(yōu)性

設(shè)X*，Y*分別為原問題和對偶問題可行解，當(dāng)

CX*=Y*b時，X*，Y*分別為最優(yōu)解。304、最優(yōu)性305、對偶定理若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，且目標(biāo)值相等。315、對偶定理31∴Y*為對偶問題的最優(yōu)解，且原問題和對偶問題的目標(biāo)值相等。證畢6、松弛性

若X*，Y*分別為原問題及對偶問題的可行解，那么Ys*X*=0，Y*Xs*=0，當(dāng)且僅當(dāng)X*，Y*分別為最優(yōu)解。證明：32∴Y*為對偶問題的最優(yōu)解，且原問題和對偶問題6、松弛性證明：將b,C分別代入目標(biāo)函數(shù)：33將b,C分別代入目標(biāo)函數(shù)：33其中：用分量表示：34其中：用分量表示：34

7、檢驗數(shù)與解的關(guān)系(1)原問題非最優(yōu)檢驗數(shù)的負(fù)值為對偶問題的一個基解。(2)原問題最優(yōu)檢驗數(shù)的負(fù)值為對偶問題的最優(yōu)解。分析：max

z=CX

+

0Xs=(C0)(XXs)TAX

+

Xs=bX,Xs

≥

0min

w=Yb

+

YS0YA

-

Ys=CY,Ys

≥

0

檢驗數(shù)：σ

=(C0)-

CBB-1(AI)

=(C-

CBB-1A-

CBB-1)

=(σcσs)

σc

=

C

-

CBB-1AX對應(yīng)的檢驗數(shù)

σs

=

-

CBB-1

Xs對應(yīng)的檢驗數(shù)357、檢驗數(shù)與解的關(guān)系分析：maxz=CX+[eg.6]已知：min

w=20y1

+

20y2的最優(yōu)解為y1*=1.2,y2*=0.2-ys1y1

+

2y2

≥

1①試用松弛性求對偶-ys22y1

+

y2

≥

2②問題的最優(yōu)解。-ys32y1

+

3y2

≥

3③-ys43y1

+

2y2

≥

4④y1,y2

≥

0

解：對偶問題max

z=x1

+

2x2

+

3x3

+

4x4x1

+

2x2

+

2x3

+

3x4

≤

20+xs12x1

+

x2

+

3x3

+

2x4

≤

20+xs2x1,x2,x3,x4

≥

0y1*xs1*=0y2*xs2*=0ys1*x1*=0ys2*x2*=0ys3*x3*=0ys4*x4*=036[eg.6]已知：minw=20y1+20y2

∵y1*=1.2,y2*0.2

>0∴xs1*=xs2*=0

由①

y1*

+

2y2*=1.6>1∴ys1*>0∴x1*=0

由②2y1*

+

y2*=2.6>2

∴ys2*>0∴x2*=0

由③2y1*

+

3y2*=3=右邊∴ys3*=0∴x3*待定

由④3y1*

+

2y2*=4=右邊

∴ys4*=0∴x4*待定有2x3*

+

3x4*

=

203x3*

+

2x4*

=

20∴x3*

=

4

x4*

=

4

∴最優(yōu)解：x1*

=0x2*

=0x3*

=4x4*

=4xs1*

=0xs2*

=0

最大值：z*

=28

=w*37∵y1*=1.2,y2*0.2>0∴xs1§5對偶問題的經(jīng)濟含義——影子價格最優(yōu)情況：z*=w*=b1y1*

+

···

+

biyi*

+

···

+

bmym*x2x1Q2

[eg.7]max

z

=

2x1

+

3x2x1

+

2x2

≤

84x1

≤

16

4x2

≤

12x1,x2

≥

0b1：89Q2’(4，2.5)z*’=15.5

Δz*=z*’-

z*=3/2=y1*b2：1617Q2”(4.25，1.875)z*”=14.125

Δz*=z*”-

z*=1/8=y2*b3：1213Δz*=0=y3*Q2’Q2”38§5對偶問題的經(jīng)濟含義——影子價格x2x1Q2[e§6對偶單純形法

單純形法：由XB=B-1b

≥

0，使σj

≤

0，j=1,···,m對偶單純形法：由σj

≤

0(j=1,···,n)，使XB=B-1b

≥

0步驟：(1)保持σj

≤

0，j=1,···,n，確定XB，建立計算表格；

(2)判別XB=B-1b

≥

0是否成立？①若成立，XB為最優(yōu)基變量；②若不成立，轉(zhuǎn)(3)；

39§6對偶單純形法步驟：(1)保持σj≤0，j=(4)消元運算，得到新的XB。(3)基變換

①出基變量，

②入基變量，

重復(fù)（2）-（4）步，求出結(jié)果。40(4)消元運算，得到新的XB。(3)基變換②入基變量，重

[eg.8]用對偶單純形法求解

min

w=2x1

+

3x2

+

4x3x1

+

2x2

+

x3

≥

12x1

-

x2

+

3x3

≥

4x1,x2,x3

≥

0解：max

z=-2x1

-

3x2

-

4x3

+

0x4

+

0x5-x1

-

2x2

-

x3

+

x4

=-1-2x1

+

x2

-

3x3

+

x5=-4x1,x2,x3,x4,x5

≥

041[eg.8]用對偶單純形法求解解：maxz=-2x-2-3-400CBXBbx1x2x3x4X50x4-10x5-4出出出∵x4,x5<0

∴非最優(yōu)0x410-5/21/21-1/2-2x121-1/23/20-1/2-2-3-400CBXBbx1x2x3x4X50x4-1-1-2-1100x5-4-21-301-2-3-400CBXBbx1x2x3x4X50x4-1-1-2-1100x5-4-21-301-2-3-4001--4/30x410-5/21/21-1/2-2x121-1/23/20-1/20-4-10-1∵x1,x4>0

∴最優(yōu)最優(yōu)解：x1*=2，x2*=0，x3*=0，x4*=1，x5*=0目標(biāo)值：w*=-z*=442-2-3-400CBXBbx1x2x3x4X50x4-10x對偶單純形法練習(xí)：43對偶單純形法練習(xí)：43復(fù)習(xí)：

1、寫出如下問題的對偶問題約束條件符號判斷：max->min相同，min->max相反決策變量符號判斷：max->min相反，min->max相同44復(fù)習(xí)：

1、寫出如下問題的對偶問題約束條件符號判斷：44復(fù)習(xí)：

2、用對偶單純形法求解線性規(guī)劃問題145復(fù)習(xí)：

2、用對偶單純形法求解線性規(guī)劃問題145§7靈敏度分析分析

變化對最優(yōu)解的影響。46§7靈敏度分析分析變化對最優(yōu)解的影響。44747例1已知下述問題的最優(yōu)解及最優(yōu)單純形表,48例1已知下述問題的最優(yōu)解及最優(yōu)單純形表,48最優(yōu)單純形表如下:0-1/8-3/2000-1/81/2102311/2-2004001/4001420003249最優(yōu)單純形表如下:0-1/8-3/2000-1/81/210由最優(yōu)單純形表得:50由最優(yōu)單純形表得:505151不可行!用對偶單純形法計算52不可行!用對偶單純形法計算52-3/4-1/20001/400103x23-1/2-1/41002x3001/40014x120-1/8-3/200

0-1/81/2102+2311/2-2004-8x5001/40014+0x12ix5x4x3x2x1bXBCB00032x23/4－－－－[-2]53-3/4-1/20001/400103x23-1/2-1/4如下題：

（1）若增大到32，試分析最優(yōu)性的變化。

（2）請分析在什么范圍內(nèi)變化，問題的最優(yōu)基不變。最優(yōu)單純形表：-1/2-1/4000

3/2-1/40103/21-1/21/40017/2x12-15/25/410015/2x30ix5x4x3x2x1b基CB00012x254如下題：

（1）若增大到32，試分析最優(yōu)性的變化。

（5555例2求例1c4的變化范圍,使最優(yōu)解不變.0-1/8-3/200

0-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x2解:56例2求例1c4的變化范圍,使最優(yōu)解不變.0-1/8-分析:57分析:57方法:例3求例1c2的變化范圍,使最優(yōu)解不變.0-1/8-3/200

0-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x258方法:例3求例1c2的變化范圍,使最優(yōu)解不變.0-1解:0-1/8-3/200

0-1/81/21023+11/2-2004x5001/40014x12ix5x4x3x2x1bXBCB0003+2x259解:0-1/8-3/200 0-1/81/21023+11/6060當(dāng)目標(biāo)函數(shù)中cj發(fā)生變化，將影響最終單純形表非基變量的檢驗數(shù)。如果是非基變量的價值系數(shù)發(fā)生變化，只影響該非基變量的檢驗數(shù)，如果變化后的檢驗數(shù)仍然小于等于0，則最優(yōu)解不變；如果是基變量的價值系數(shù)發(fā)生變化，將影響所有非基變量的檢驗數(shù)，只有當(dāng)所有的非基變量檢驗數(shù)都仍然小于等于0，最優(yōu)解才不變。61當(dāng)目標(biāo)函數(shù)中cj發(fā)生變化，將影響最終單純形表非基變量的如下題：

（1）若c1變?yōu)?.5，c2變?yōu)?，試分析最優(yōu)性的變化。

（2）請確定c2變化范圍，使問題最優(yōu)性不變。最優(yōu)單純形表：-1/2-1/4000

3/2-1/40103/21-1/21/40017/2x12-15/25/410015/2x30ix5x4x3x2x1b基CB00012x262如下題：

（1）若c1變?yōu)?.5，c2變?yōu)?，試分析最優(yōu)性的分析:63分析:636464例5在例1的基礎(chǔ)上，企業(yè)要增加一個新產(chǎn)品Ⅲ,每件產(chǎn)品需2個臺時，原材料A6kg，原材料B3kg，利潤5元/件，問如何安排各產(chǎn)品的產(chǎn)量，使利潤最大？解：532利潤12340料B16604料A8221設(shè)備bⅢⅡⅠ65例5在例1的基礎(chǔ)上，企業(yè)要增加一個532利潤12表明生產(chǎn)新品有利。66表明生產(chǎn)新品有利。665/40-1/8-3/200

1/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500032x2ix’3675/40-1/8-3/200 1/40-1/81/210235/40-1/8-3/200

1/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500032x28/34/28ix’3[2]0-5/8-7/16-1/400

0-1/8-3/163/4103/2311/21/4-10020-3/4-1/83/2011x12x5x4x3x2x1bXBCB500032x2ix’3x’35685/40-1/8-3/200 1/40-1/81/21023如下題：

若式中x2變?yōu)?、4、1，產(chǎn)品利潤變?yōu)?，試分析最優(yōu)性的變化。最優(yōu)單純形表：-1/2-1/4000

3/2-1/40103/21-1/21/40017/2x12-15/25/410015/2x30ix5x4x3x2x1b基CB00012x269如下題：

若式中x2變?yōu)?、4、1，產(chǎn)品利潤變?yōu)?，試分析最小結(jié)1、對偶問題及其化法※原問題決策變量決定對偶問題約束條件關(guān)系※原問題約束條件決定對偶問題決策變量取值方向。70小結(jié)1、對偶問題及其化法※原問題決策變量決定對偶問題約束條件2、檢驗數(shù)的計算方法712、檢驗數(shù)的計算方法713、對偶問題的性質(zhì)4、對偶單純形法●弱對偶性●無界性●最優(yōu)性●松弛性●檢驗數(shù)與對偶問題的解723、對偶問題的性質(zhì)4、對偶單純形法●弱對偶性●無界性●最優(yōu)性對偶單純形法的特點：當(dāng)約束條件為“≥”時，不需要引入人工變量，從而使計算更為簡便。用對偶單純形法求解時，目標(biāo)函數(shù)必須是求極大化的。73對偶單純形法的特點：73步驟：1.確定初始解一般設(shè)松弛變量為初時基可行解2.判斷若所有的基變量值均≥0，則此解為線性規(guī)劃問題的最優(yōu)解，若存在基變量的值≤0，則問題還沒有達到最優(yōu)解，需要進行改進。3.改進選擇換出變量min{bi’/bi≤0}假設(shè)選取xk為換出變量選擇換入變量θ＝min{(cj-zj)/arj|arj＜0,cj-zj＜0}則假設(shè)選取xl為換出變量4.迭代。使得alk＝1，其余aik為074步驟：74Minw=5y1+2y2+4y3s.t.3y1+y2+2y3≥46y1+3y2+5y3≥10y1,y2,y3≥0舉例：Maxw’=-5y1-2y2-4y3s.t.-3y1-y2-2y3≤-4-6y1-3y2-5y3≤-10y1,y2,y3≥0Maxw’=-5y1-2y2-4y3s.t.-3y1-y2-2y3+y4=4-6y1-3y2-5y3+y5=10yi≥0(i=1,2,…,5)75Minw=5y1+2y2+4y3舉例：Maxw’=-5y1-cj-5-2-400CBXBby1y2y3y4y5θ0y4-4-3-1-2100y5-10-6-3-5015/62/34/5cj-zj-5-2-4000y4-2/3-10-1/31-1/3122-2y210/3215/30-1/3cj-zj-10-2/30-2/3-5y12/3101/311/3-2y220112-1cj-zj00-1/3-1-1/3此時對偶問題和原問題都達到可行，所以均達到了最優(yōu)解Y＝（2/3.2,0,0,0)W’=-22/3W=22/376cj-5-2-400CBXBby1y2y3y4y5θ0y4-5、靈敏度分析前提條件:原線性規(guī)劃問題已取得了最優(yōu)解；每次只討論一種參數(shù)的變化，而參數(shù)之間的變化互不關(guān)聯(lián)。775、靈敏度分析前提條件:77常用公式：78常用公式：787979目標(biāo)函數(shù)：maxz=2x1+3x2約束條件：x1+2x2≤84x1≤164x2≤12x1，x2≥02x14100?00x5400-2?13x2201?-1/8000-3/2-1/8080目標(biāo)函數(shù)：maxz=2x1+3x22x14100第一二章總結(jié)線性規(guī)劃問題的引出線性規(guī)劃的一般模型線性規(guī)劃的標(biāo)準(zhǔn)形式單純形法的原理單純形法大M法和兩階段法81第一二章總結(jié)線性規(guī)劃問題的引出81對偶問題的提出根據(jù)原問題寫對偶問題對偶問題的基本性質(zhì)對偶單純形表靈敏度分析82對偶問題的提出82課后題復(fù)習(xí)——原問題對偶問題關(guān)系83課后題復(fù)習(xí)——原問題對偶問題關(guān)系83課后題復(fù)習(xí)——對偶理論及性質(zhì)84課后題復(fù)習(xí)——對偶理論及性質(zhì)84課后題復(fù)習(xí)——兩種單純形法區(qū)別85課后題復(fù)習(xí)——兩種單純形法區(qū)別85課后題復(fù)習(xí)——對偶單純形法計算步驟86課后題復(fù)習(xí)——對偶單純形法計算步驟86課后題復(fù)習(xí)——靈敏度分析87課后題復(fù)習(xí)——靈敏度分析87第二章 對偶理論與靈敏度分析§1單純形法的矩陣描述

設(shè)max

z=CXAX=bX

≥

0

A為m×n階矩陣RankA=m,取B為可行基,N為非基，

88第二章 對偶理論與靈敏度分析§1單純形法的矩陣描述1892903求解步驟：91求解步驟：432利潤12kg40材料B16kg04材料A8臺時

21設(shè)備臺時限制

ⅡⅠ§2對偶問題的提出

[eg.1]制定生產(chǎn)計劃M1:max

z=2x1

+

3x21x1

+

2x2≤84x1

≤

16

4x2

≤

12x1，x2

≥

0

9232利潤12kg40材料B16kg04材料A8臺時21設(shè)備現(xiàn)在出租，設(shè)y1為設(shè)備單位臺時的租金y2,y3為材料A、B轉(zhuǎn)讓附加費(kg-1)則M2為M1的對偶問題，反之亦然。M2:min

w=8y1

+

16y2

+

12y3y1+4y2

≥

22y1

+4y3≥3y1,y2,y3

≥

032利潤12kg40材料B16kg04材料A8臺時

21設(shè)備臺時限制

ⅡⅠ93現(xiàn)在出租，設(shè)y1為設(shè)備單位臺時的租金則M2為M1的對一般的，原問題：max

z=CXAX

≤

bX

≥

0

對偶問題：min

w=YbYA

≥

CY

≥

0比較：max

zmin

w

決策變量為n個約束條件為n個

約束條件為m個決策變量為m個“≤”“≥”94一般的，原問題：maxz=CXAX≤b§3對偶問題的化法1、典型情況

[eg.2]max

z=x1

+

2x2

+

x32x1

+

x2≤

62x2

+

x3≤

8x1,x2,x3

≥

0對偶：min

w=6y1

+

8y22y1

≥

1y1

+

2y2≥

2

y2≥

1y1,y2

≥

095§3對偶問題的化法對偶：minw=6y1+82、含等式的情況

[eg.3]max

z=x1

+

2x2

+

4x32x1

+

x2

+

3x3=3x1

+

2x2

+

5x3

≤

4x1,x2,x3

≥

0對偶：min

w=3y1’-3y1”+4y22y1’-2y1”+y2

≥

1y1’-y1”+2y2

≥

23y1’-3y1”+5y2

≥

4y1’,y1”,y2

≥

0令y1=y1’-y1”,則：

min

w=3y1+4y22y1

+y2

≥

1y1

+2y2

≥

23y1

+5y2

≥

4y2

≥

0，y1無約束一般，原問題第i個約束取等式，對偶問題第i個變量無約束。2x1

+

x2

+

3x3≤

3-2x1

-

x2

-

3x3

≤-3962、含等式的情況對偶：minw=3y1’-3y1”3、含“≥”的max問題

[eg.4]max

z=x1

+

2x2

+

4x32x1

+

x2

+

3x3

≥

3x1

+

2x2

+

5x3

≤

4x1,x2,x3

≥

0對偶：min

w=-3y1’

+

4y2-2y1’

+

y2

≥

1-y1’

+

2y2

≥

2-3y1’

+

5y2

≥

4y1’,y2

≥

0令y1=-y1’，則：

min

w=3y1

+

4y22y1

+

y2

≥

1y1

+

2y2

≥

23y1

+

5y2

≥

4y1

≤

0,y2

≥

0-2x1

-

x2

-

3x3

≤-3973、含“≥”的max問題對偶：minw=-3y1’一般:①max問題第i個約束取“≥”，則min問題第i個變量

≤

0；②min問題第i個約束取“≤”，則max問題第i個變量

≤

0；③原問題第i個約束取等式，對偶問題第i個變量

無約束；④max問題第j個變量

≤

0,則min問題第j個約束取“≤”；⑤min問題第j個變量

≤

0

，則max問題第j個約束取“≥”

；⑥原問題第j個變量無約束，對偶問題第j個約束取等式。約束條件符號判斷：max->min相同，min->max相反決策變量符號判斷：max->min相反，min->max相同98一般:②min問題第i個約束取“≤”，則max問題第i個[eg.5]min

z=2x1

+

3x2

-

5x3

+

x4x1

+

x2

-

3x3

+x4

≥

52x1

+

2x3

-

x4

≤

4

x2

+

x3

+

x4=6x1

≤

0,x2,x3

≥

0,x4無約束對偶：max

w=5y1

+

4y2

+

6y3y1

+

y2

≥

2y1

+

y3

≤

3-3y1

+

2y2

+

y3

≤

-5y1

-

y2

+

y3=1y1

≥

0,y2

≤

0,y3無約束99[eg.5]minz=2x1+3x2-5x對偶問題的基本性質(zhì)一、單純形法計算的矩陣描述MaxZ=CXAX≤bX≥0其中X＝(x1,x2……xn)TMaxZ=CX+0XsAX+IXs=bX,Xs≥0其中Xs＝(xn+1,xn+2……xn+m)TI為m×m的單位矩陣100對偶問題的基本性質(zhì)一、單純形法計算的矩陣描述MaxZ=CX

項目非基變量基變量XBXNXs0XsbBNIcj-zjCBCN0……項目基變量非基變量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1對應(yīng)初始單純形表中的單位矩陣I，迭代后的單純形表中為B-1；初始單純形表中基變量Xs=b，迭代后的表中為XB=B-1b；約束矩陣（A，I）＝（B，N，I），迭代后為（B-1B，B-1N，B-1I）＝（I，B-1N，B-1)；初始單純形表中xj的系數(shù)向量為Pj，迭代后為Pj’，且Pj’=B-1Pj。101非基變量基變量XBmaxZ=4.5x1+5x2s.t.3x1+2x2≤244x1+5x2≤40x1,x2≥0minw=24y1+40y2s.t.3y1+4y2≥4.52y1+5x2≥5y1,y2≥0y1y2x1x2maxZ=4.5x1+5x2s.t.3x1+2x2+x3=244x1+5x2+x4=40x1,x2,x3,x4,≥0minw=24y1+40y2s.t.3y1+4y2-y3=4.52y1+5x2-y4=5y1,y2,y3,y4≥0y1y2x1x2102maxZ=4.5x1+5x2minw=24y1+40y2y1cj4.5500θCBXBbx1x2x3x40x3243210120x44045018cj-zj4.55000x387/501-2/540/75x284/5101/510cj-zj1/200-14.5x140/7105/7-2/75x224/701-4/73/7cj-zj00-5/14-6/7Z=4.5×40/7＋5×24/7=300/7解原問題：103cj4.5500θCBXBbx1x2x3x40x324321解對偶問題：w=24×5/14＋40×6/7=300/7cj244000θCBYBby1y2y3y424y15/1410-5/74/740y26/7012/7-3/7cj-zj0040/724/7104解對偶問題：w=24×5/14＋40×6/7=300/7cjcj4.5500θCBXBbx1x2x3x44.5x140/7105/7-2/75x224/701-4/73/7cj-zj00-5/14-6/7cj244000θCBYBby1y2y3y424y15/1410-5/74/740y26/7012/7-3/7cj-zj0040/724/7(x3,x4)=(0,0)(y3,y4)=(0,0)-y1-y2-y4-y3x1x2x4x3原問題對偶問題105cj4.5500θCBXBbx1x2x3x44.5x140/二、對偶問題的基本性質(zhì)原始問題maxz=CXs.t.AX≤b X≥0對偶問題minw=Y’bs.t.ATY≥C’ Y≥01.弱對偶性若X‘為原問題的可行解，Y’為對偶問題的可行解，則恒有CX’≤Y’b106二、對偶問題的基本性質(zhì)原始問題對偶問題1.弱對偶性19推論：原問題任一可行解的目標(biāo)函數(shù)是其對偶問題目標(biāo)函數(shù)值的下界，反之對偶問題任一可行解的目標(biāo)函數(shù)是其原問題目標(biāo)函數(shù)的上界。如原問題有可行解且目標(biāo)函數(shù)值無界，則其對偶問題無可行解；反之對偶問題有可行解且目標(biāo)函數(shù)無界，則原問題無可行解。（對偶問題無可行解時，其原問題無界解或無可行解。若原問題有可行解而其對偶問題無可行解時，原問題目標(biāo)函數(shù)無界若對偶問題有可行解而其原問題無可行解時，對偶問題目標(biāo)函數(shù)無界。107推論：202.最優(yōu)性若X‘為原問題的可行解，Y’為對偶問題的可行解，且CX‘＝Y(jié)’b則X’，Y‘分別為原問題和對偶問題的最優(yōu)解。3.強對偶性若原問題和對偶問題均具有可行解，則兩者均具有最優(yōu)解，且他們的最優(yōu)解的目標(biāo)值相等。1082.最優(yōu)性3.強對偶性214.互補松弛定理在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為0，則該約束條件取嚴(yán)格等式，既松弛變量或剩余變量為0；反之如果對應(yīng)某一約束條件的對偶變量值不為0，則該約束條件取嚴(yán)格不等式，既松弛變量或剩余變量不為0.若yi’＞0,即xsi=0若yi’＝0,即xsi＞0即xsi·yi=0同理若xj’＞0,即ysj=0若xj’＝0,即ysj＞0即ysj·xj=01094.互補松弛定理若yi’＞0,即xsi=0同理22maxZ=4.5x1+5x2s.t.3x1+2x2+x3=244x1+5x2+x4=40x1,x2,x3,x4,≥0y1y2minw=24y1+40y2s.t.3y1+4y2-y3=4.52y1+5x2-y4=5y1,y2,y3,y4≥0x1x2X3=0,3x1+2x2=24,y1=14/5X4=0,4x1+5x2=40,y2=6/7y3=0,3y1+4y2=5,x1=40/7y4=0,2y1+5y2=5,x2=24/7110maxZ=4.5x1+5x2y1y2minw=24y1+40利用互補松弛關(guān)系求解線性規(guī)劃minz=6x1+8x2+3x3s.t.x1+x2≥1x1+2x2+x3≥-1x1,x2,x3≥0maxw=y1-y2s.t.y1+y2≤6y1+2y2≤8y2≤3y1,y2≥0原始問題對偶問題012345678654321w1w2y=-1y=1y=3y=6最優(yōu)解為(y1,y2)=(6,0)maxy=6先用圖解法求解對偶問題。111利用互補松弛關(guān)系求解線性規(guī)劃minz=6x1+8x2+3xminz=6x1+8x2+3x3s.t.x1+x2≥1x1+2x2+x3≥-1x1,x2,x3≥0maxw=y1-y2s.t.y1+y2≤6y1+2y2≤8y2≤3y1,y2≥0maxw=y1-y2s.t.y1+y2+y3=6y1+2y2+y4=8y2+y5=3y1,y2,y3,y4,y5≥0(y1,y2)=(6,0)(y1,y2,y3,y4,y5)=(6,0,0,2,3)minz=6x1+8x2+3x3s.t.x1+x2-x4=1x1+2x2+x3-x5=-1x1,x2,x3,x4,x5≥0(x1,x2,x3|x4,x5)(y1,y2|y3,y4,y5)x2=x3=x4=0x1=1,x5=2引進剩余變量求對偶引進松弛變量圖解法求解代入約束求出松弛變量互補松弛關(guān)系代入約束求解(x1,x2,x3,x4,x5)=(1,0,0,0,2)112minz=6x1+8x2+3x3maxw=y1-y2ma§4對偶問題的性質(zhì)

1、對稱性對偶問題的對偶為原問題.113§4對偶問題的性質(zhì)1、對稱性261142711528推論：(1)max問題任一可解的目標(biāo)值為min問題目標(biāo)值的一個下界；(2)min問題任一可解的目標(biāo)值為max問題目標(biāo)值的一個上界。3、無界性若原問題(對偶問題)為無界解，則對偶問題(原問題)為無可行解。注：該性質(zhì)的逆不存在。若原(對偶)問題為無可行解，對偶(原問題)問題或為無界解，或為無可行解。116推論：3、無界性注：該性質(zhì)的逆不存在。若原(對偶)問4、最優(yōu)性

設(shè)X*，Y*分別為原問題和對偶問題可行解，當(dāng)

CX*=Y*b時，X*，Y*分別為最優(yōu)解。1174、最優(yōu)性305、對偶定理若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，且目標(biāo)值相等。1185、對偶定理31∴Y*為對偶問題的最優(yōu)解，且原問題和對偶問題的目標(biāo)值相等。證畢6、松弛性

若X*，Y*分別為原問題及對偶問題的可行解，那么Ys*X*=0，Y*Xs*=0，當(dāng)且僅當(dāng)X*，Y*分別為最優(yōu)解。證明：119∴Y*為對偶問題的最優(yōu)解，且原問題和對偶問題6、松弛性證明：將b,C分別代入目標(biāo)函數(shù)：120將b,C分別代入目標(biāo)函數(shù)：33其中：用分量表示：121其中：用分量表示：34

7、檢驗數(shù)與解的關(guān)系(1)原問題非最優(yōu)檢驗數(shù)的負(fù)值為對偶問題的一個基解。(2)原問題最優(yōu)檢驗數(shù)的負(fù)值為對偶問題的最優(yōu)解。分析：max

z=CX

+

0Xs=(C0)(XXs)TAX

+

Xs=bX,Xs

≥

0min

w=Yb

+

YS0YA

-

Ys=CY,Ys

≥

0

檢驗數(shù)：σ

=(C0)-

CBB-1(AI)

=(C-

CBB-1A-

CBB-1)