清華大學(xué)運籌學(xué)課件第二章

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

設(shè)max

z=CXAX=bX

≥

0

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

123求解步驟：432利潤12kg40材料B16kg04材料A8臺時

21設(shè)備臺時限制

ⅡⅠ§2對偶問題的提出

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

z=2x1

+

3x21x1

+

2x2≤84x1

≤

16

4x2

≤

12x1，x2

≥

0

5現(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一般的，原問題：max

z=CXAX

≤

bX

≥

0

對偶問題：min

w=YbYA

≥

CY

≥

0比較：max

zmin

w

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

約束條件為m個決策變量為m個“≤”“≥”7§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

≥

082、含等式的情況

[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

≤-393、含“≥”的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

≤-310一般:①max問題第i個約束取“≥”，則min問題第i個變量

≤

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

≤

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

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

≤

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

≤

0

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

；⑥原問題第j個變量無約束，對偶問題第j個約束取等式。11[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§4對偶問題的性質(zhì)1、對稱性對偶問題的對偶為原問題.131415推論：(1)max問題任一可解的目標值為min問題目標值的一個下界；(2)min問題任一可解的目標值為max問題目標值的一個上界。3、無界性若原問題(對偶問題)為無界解，則對偶問題(原問題)為無可行解。注：該性質(zhì)的逆不存在。若原(對偶)問題為無可行解，對偶(原問題)問題或為無界解，或為無可行解。164、最優(yōu)性

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

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

若X*，Y*分別為原問題及對偶問題的可行解，那么Ys*X*=0，Y*Xs*=0，當且僅當X*，Y*分別為最優(yōu)解。證明：19將b,C分別代入目標函數(shù)：20其中：用分量表示：217、檢驗數(shù)與解的關(guān)系(1)原問題非最優(yōu)檢驗數(shù)的負值為對偶問題的一個基解。(2)原問題最優(yōu)檢驗數(shù)的負值為對偶問題的最優(yōu)解。分析：max

z=CX

+

0Xs=(C0)(XXs)TAX

+

Xs=bX,Xs

≥

0min

w=Yb

+

YS0YA

-

Ys=C

Y,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ù)22[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*=023

∵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*24§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”25§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)；

26(4)消元運算，得到新的XB。(3)基變換

①出基變量，

②入基變量，

重復(fù)（2）-（4）步，求出結(jié)果。27

[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

≥

028-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目標值：w*=-z*=429§7靈敏度分析分析

變化對最優(yōu)解的影響。3031例1已知下述問題的最優(yōu)解及最優(yōu)單純形表,32最優(yōu)單純形表如下:0-1/8-3/2000-1/81/2102311/2-2004001/4001420003233由最優(yōu)單純形表得:3435不可行!用對偶單純形法計算36-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]3738例2求例1c4的變化范圍,使最優(yōu)解不變.0-1/8-3/200

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

0-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x241解:0-1/8-3/200

0-1/81/2102311/2