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

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

設(shè)max

z=CXAX=bX

≥

0

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

123求解步驟：432利潤(rùn)12kg40材料B16kg04材料A8臺(tái)時(shí)

21設(shè)備臺(tái)時(shí)限制

ⅡⅠ§2對(duì)偶問(wèn)題的提出

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

z=2x1

+

3x21x1

+

2x2≤84x1

≤

16

4x2

≤

12x1，x2

≥

0

5現(xiàn)在出租，設(shè)y1為設(shè)備單位臺(tái)時(shí)的租金y2,y3為材料A、B轉(zhuǎn)讓附加費(fèi)(kg-1)則M2為M1的對(duì)偶問(wèn)題，反之亦然。M2:min

w=8y1

+

16y2

+

12y3y1+4y2

≥

22y1

+4y3≥3y1,y2,y3

≥

032利潤(rùn)12kg40材料B16kg04材料A8臺(tái)時(shí)

21設(shè)備臺(tái)時(shí)限制

ⅡⅠ6一般的，原問(wèn)題：max

z=CXAX

≤

bX

≥

0

對(duì)偶問(wèn)題：min

w=YbYA

≥

CY

≥

0比較：max

zmin

w

決策變量為n個(gè)約束條件為n個(gè)

約束條件為m個(gè)決策變量為m個(gè)“≤”“≥”7§3對(duì)偶問(wèn)題的化法1、典型情況

[eg.2]max

z=x1

+

2x2

+

x32x1

+

x2≤

62x2

+

x3≤

8x1,x2,x3

≥

0對(duì)偶：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對(duì)偶：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無(wú)約束一般，原問(wèn)題第i個(gè)約束取等式，對(duì)偶問(wèn)題第i個(gè)變量無(wú)約束。2x1

+

x2

+

3x3≤

3-2x1

-

x2

-

3x3

≤-393、含“≥”的max問(wèn)題

[eg.4]max

z=x1

+

2x2

+

4x32x1

+

x2

+

3x3

≥

3x1

+

2x2

+

5x3

≤

4x1,x2,x3

≥

0對(duì)偶：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問(wèn)題第i個(gè)約束取“≥”，則min問(wèn)題第i個(gè)變量

≤

0；②min問(wèn)題第i個(gè)約束取“≤”，則max問(wèn)題第i個(gè)變量

≤

0；③原問(wèn)題第i個(gè)約束取等式，對(duì)偶問(wèn)題第i個(gè)變量

無(wú)約束；④max問(wèn)題第j個(gè)變量

≤

0,則min問(wèn)題第j個(gè)約束取“≤”；⑤min問(wèn)題第j個(gè)變量

≤

0

，則max問(wèn)題第j個(gè)約束取“≥”

；⑥原問(wèn)題第j個(gè)變量無(wú)約束，對(duì)偶問(wèn)題第j個(gè)約束取等式。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無(wú)約束對(duì)偶：max

w=5y1

+

4y2

+

6y3y1

+

y2

≥

2y1

+

y3

≤

3-3y1

+

2y2

+

y3

≤

-5y1

-

y2

+

y3=1y1

≥

0,y2

≤

0,y3無(wú)約束12§4對(duì)偶問(wèn)題的性質(zhì)1、對(duì)稱性對(duì)偶問(wèn)題的對(duì)偶為原問(wèn)題.131415推論：(1)max問(wèn)題任一可解的目標(biāo)值為min問(wèn)題目標(biāo)值的一個(gè)下界；(2)min問(wèn)題任一可解的目標(biāo)值為max問(wèn)題目標(biāo)值的一個(gè)上界。3、無(wú)界性若原問(wèn)題(對(duì)偶問(wèn)題)為無(wú)界解，則對(duì)偶問(wèn)題(原問(wèn)題)為無(wú)可行解。注：該性質(zhì)的逆不存在。若原(對(duì)偶)問(wèn)題為無(wú)可行解，對(duì)偶(原問(wèn)題)問(wèn)題或?yàn)闊o(wú)界解，或?yàn)闊o(wú)可行解。164、最優(yōu)性

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

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

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

z=CX

+

0Xs=(C0)(XXs)TAX

+

Xs=bX,Xs

≥

0min

w=Yb

+

YS0YA

-

Ys=C

Y,Ys

≥

0

檢驗(yàn)數(shù)：σ

=(C0)-

CBB-1(AI)

=(C-

CBB-1A-

CBB-1)

=(σcσs)

σc

=

C

-

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

σs

=

-

CBB-1

Xs對(duì)應(yīng)的檢驗(yàn)數(shù)22[eg.6]已知：min

w=20y1

+

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

+

2y2

≥

1①試用松弛性求對(duì)偶-ys22y1

+

y2

≥

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

+

3y2

≥

3③-ys43y1

+

2y2

≥

4④y1,y2

≥

0

解：對(duì)偶問(wèn)題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對(duì)偶問(wèn)題的經(jīng)濟(jì)含義——影子價(jià)格最優(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對(duì)偶單純形法

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

≥

0，使σj

≤

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

≤

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

≥

0步驟：(1)保持σj

≤

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

(2)判別XB=B-1b

≥

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

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

①出基變量，

②入基變量，

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

[eg.8]用對(duì)偶單純形法求解

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目標(biāo)值：w*=-z*=429§7靈敏度分析分析

變化對(duì)最優(yōu)解的影響。3031例1已知下述問(wèn)題的最優(yōu)解及最優(yōu)單純形表,32最優(yōu)單純形表如下:0-1/8-3/2000-1/81/2102311/2-2004001/4001420003233由最優(yōu)單純形表得:3435不可行!用對(duì)偶單純形法計(jì)算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