第二章對偶問題與靈敏度分析

第二章對偶問題與靈敏度分析1第1頁，課件共56頁，創(chuàng)作于2023年2月第二章：第一部分LP的對偶理論1.7.1

對偶問題例12加工能力(小時/天)

A2212B128C4016D041223銷售收入產(chǎn)品設(shè)備第2頁，課件共56頁，創(chuàng)作于2023年2月設(shè)X1，

X2為產(chǎn)品1，2的產(chǎn)量2X1+2X2

12X1+2X2

84X1

164X2

12X1X2

0maxZ=2X1+3X2221212X1840X21604

12

(23)

X1X2第3頁，課件共56頁，創(chuàng)作于2023年2月設(shè)y1,

y2,

y3,

y4分別為A,B,C,D設(shè)備的單價2y1+y2+4y322y1+2y2+443y1…y4

021402204y1y2y3y4

23第4頁，課件共56頁，創(chuàng)作于2023年2月(y1y2y3y4)22124004

(2,3)minW=12y1+8y2+16y3+12y4y1…y4“影子價格”第5頁，課件共56頁，創(chuàng)作于2023年2月“對稱型”定義：對偶問題minW=yb

yA

Cy0A矩陣y,C行向量b列向量minW=bTyATy

CTy0A矩陣y,b列向量C行向量maxZ=CX

AX

bX0A矩陣X,b列向量C行向量原問題第6頁，課件共56頁，創(chuàng)作于2023年2月對偶問題的性質(zhì)：(1)、對偶問題的對偶問題是原問題。(2)、maxZ=CX

AX=bX0的對偶問題是minW=yb

yACy為自由第7頁，課件共56頁，創(chuàng)作于2023年2月例1、寫出下面問題的對偶規(guī)劃maxZ=5X1+6X23X1-2X2=74X1+X2

9X1,X2

0第8頁，課件共56頁，創(chuàng)作于2023年2月解：3X1-2X2

73X1-2X2

74X1+X2

9maxZ=5X1+6X23X1-2X2

7-3X1+2X2

-74X1+X2

9X1,X2

0y1'y1"y2第9頁，課件共56頁，創(chuàng)作于2023年2月對偶問題令y1=

y1'

-y1"

3y1'

-3y1"

+4y25

-2y1'

+2y1"

+y2

6y1'

,y1",y2

0minW=7y1'

-7y1"

+9y2minW=7y1+9y23y1+4y25

-2y1+y2

6y1自由

,y2

0第10頁，課件共56頁，創(chuàng)作于2023年2月(3)、原問題第k個約束為等式，對偶問題第k個變量是自由變量。原問題第k個變量是自由變量，則對偶問題第k個約束為等式約束。第11頁，課件共56頁，創(chuàng)作于2023年2月對偶關(guān)系對應(yīng)表

原問題對偶問題目標(biāo)函數(shù)類型maxmin目標(biāo)函數(shù)系數(shù)目標(biāo)函數(shù)系數(shù)右邊項(xiàng)系數(shù)與右邊項(xiàng)的對應(yīng)關(guān)系右邊項(xiàng)系數(shù)目標(biāo)函數(shù)系數(shù)變量數(shù)與約束數(shù)變量數(shù)n約束數(shù)n的對應(yīng)關(guān)系約束數(shù)m變量數(shù)m原問題變量類型與

0

對偶問題約束類型變量

0約束

的對應(yīng)關(guān)系無限制＝原問題約束類型與

0對偶問題變量類型約束

變量

0的對應(yīng)關(guān)系＝無限制第12頁，課件共56頁，創(chuàng)作于2023年2月例2、寫對偶規(guī)劃minZ=4X1+2X2-3X3-X1+2X2

62X1+3X3

9X1+5X2-2X3=

4X2,X30第13頁，課件共56頁，創(chuàng)作于2023年2月maxW=6y1+9y2+4y3-y1+2y2+y3=

42y1+5y323y2-2y3

-3y10,y20,y3自由第14頁，課件共56頁，創(chuàng)作于2023年2月minZ=4X1+2X2-3X3X1-2X2

-

62X1+3X3

9X1+5X2-2X3=

4X2,X30或?qū)⒃瓎栴}變形為第15頁，課件共56頁，創(chuàng)作于2023年2月maxW=-6y1+9y2+4y3y1+2y2+y3=

4-2y1+5y323y2-2y3

-3y1,y20,y3自由對偶規(guī)劃第16頁，課件共56頁，創(chuàng)作于2023年2月產(chǎn)品A，B產(chǎn)量X1，X2，Z為利潤例1、3X1+X2+X3=483X1+4X2+X4=120X1…X40maxZ=5X1+6X23X1+X2

483X1+4X2120X1,X2

0機(jī)器臺時勞動工時第17頁，課件共56頁，創(chuàng)作于2023年2月X=(8,24)TZ=184

5600X1X2X3X4

XB056000X34831100X41203(4)011801/200-3/20X318(9/4)01-1/46X2303/4101/418400-2/9-13/95X18

104/9-1/96X22401-1/31/3第18頁，課件共56頁，創(chuàng)作于2023年2月3y1+3y25

y1+4y2

6minW=48y1+120y23y1+3y2-y3+y5=5

y1+4y2-y4+y6=

6minW=48y1+120y2+My5+My6第19頁，課件共56頁，創(chuàng)作于2023年2月4812000M

My1y2y3y4y5y6yB11M48-4M120-7M

M

M00M

y5533-1010M

y661

40-101yB180+1/2M18-9/4M0M30-3/4M0-30+7/4M

My51/29/40-13/41-3/4120

y23/2

1/410-1/401/4yB18400824M-8M-24

48y12/91

0-4/91/34/9-1/3120y213/9011/9-1/3-1/91/3y=(2/9,13/9),Z=184第20頁，課件共56頁，創(chuàng)作于2023年2月觀察結(jié)論:①一對對偶問題都有最優(yōu)解，且目標(biāo)函數(shù)值相等。②最優(yōu)表中有兩個問題的最優(yōu)解。第21頁，課件共56頁，創(chuàng)作于2023年2月1.7.2對偶問題解的性質(zhì)maxZ=CX

AX≤bX0(P)minW=yb

yACy0(D)第22頁，課件共56頁，創(chuàng)作于2023年2月定理1、(弱對偶定理)分別為(P),(D)的可行解，則有C

bX，yXy證明：由AXb,y0有yAXby由AyC,X0有yAXCX所以CX

yAX

yb第23頁，課件共56頁，創(chuàng)作于2023年2月推論2、(P)有可行解,但無有限最優(yōu)解，則(D)無可行解。定理2、yX,分別為(P),(D)的可行解，且XyC=b,則它們是(P),(D)

的最優(yōu)解。證明：對任X，有CX

by=CXX最優(yōu)

推論1、(P),(D)都有可行解，則必都有最優(yōu)解。第24頁，課件共56頁，創(chuàng)作于2023年2月定理3、B為(P)的最優(yōu)基，則y=CBB-1是(D)的最優(yōu)解。<稱B為對偶最優(yōu)基，為對偶最優(yōu)解>y證明：由CBB-1BB-1bC-CBB-1A-CBB-1B-1AB-1有C-CBB-1A0-CBB-10

即yACy0所以是(D)的可行解。y第25頁，課件共56頁，創(chuàng)作于2023年2月其目標(biāo)函數(shù)值為yb=CBB-1b設(shè)(P)的最優(yōu)解為X，其目標(biāo)函數(shù)值為X=CBB-1bC所以是(D)的最優(yōu)解。y第26頁，課件共56頁，創(chuàng)作于2023年2月推論：分別為(P),(D)可行解，又是最優(yōu)解，則有Xy,XyC=b證明：對應(yīng)基為B，則y=CBB-1是(D)的可行解。XX=yb

C有yb(最優(yōu)解)y又由定理1，有X=Cyb第27頁，課件共56頁，創(chuàng)作于2023年2月定理4(松緊定理)互補(bǔ)松弛性原問題maxZ=cx

Ax

+

xs=bx,

xs0x=x1xn…xs=xn+1xn+m…若x,y分別為(P),(D)的可行解，則x,y為最優(yōu)解xj

ym+j=0且

xn+i

yi=0(j=1……n)(i=1……m)第28頁，課件共56頁，創(chuàng)作于2023年2月對偶問題min

=yb

yA

-

ys=cy,

ys0y=(y1…ym)ys=(ym+1…ym+n)第29頁，課件共56頁，創(chuàng)作于2023年2月證明：()∵

yA

c∴

yAx

cx∵

Ax

b∴

yAx

yb∵

cx≡

yb∴cx≡

yAx≡yb(yA-c)x≡0yA-c=ys0x0第30頁，課件共56頁，創(chuàng)作于2023年2月∴ym+j

xj=0(j=1…n)由y(Ax-b)≡0同理可得y

xs≡0xn+i

yi=0(i=1…m)(ym+1…ym+n)x1xn…≡0第31頁，課件共56頁，創(chuàng)作于2023年2月第32頁，課件共56頁，創(chuàng)作于2023年2月()∵

xj

ym+j=

0(j=1…n)∴

ym+j

xj=

0j=1nys

x=

0∵ys=yA-c

∴(yA-c)x=0

yAx=cx同理，yAx=yb∴cx=yb第33頁，課件共56頁，創(chuàng)作于2023年2月

xjym+j(j=1…n)

yixn+i(i=1…m)(P)的xj的檢驗(yàn)數(shù)是ym+j(P)的xn+i的檢驗(yàn)數(shù)是yi第34頁，課件共56頁，創(chuàng)作于2023年2月例：min

=5y1+y23y1+y29y1+y25y1+8y28y1,

y20(P)maxZ=9x1+5x2+8x33x1+x2+x35x1+x2+8x31

x1,

x2,

x30(D)第35頁，課件共56頁，創(chuàng)作于2023年2月95800x1x2x3x4x5CBxB0958000

x45311100

x5111801CBxB90-4-640-90

x420-2-231-39

x1111801(P)最優(yōu)解(0,9,0,4,64),

=9第36頁，課件共56頁，創(chuàng)作于2023年2月n=3m=2xn+i

yi=0(i=1……m)

(i=1,2)xj

ym+j=0(j=1……n)

xj

y2+j(j=1……3)x3+i

yix1

y3x2

y4x3

y5x4

y1x5

y2第37頁，課件共56頁，創(chuàng)作于2023年2月例：min

=2x1+3x2+5x3+2x4+3x5其對偶解y1﹡=4/5y2﹡=3/5Z﹡=5用對偶理論求(P)的最優(yōu)解x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53

xi0(i=1…5)(P)第38頁，課件共56頁，創(chuàng)作于2023年2月解：(D)為maxZ

=4y1+3y2y1+2y22①y1-y23②2y1+3y25③y1+y22④3y1+y23⑤y1,

y20第39頁，課件共56頁，創(chuàng)作于2023年2月將y1﹡，y2﹡代入，知②,③,④為嚴(yán)格不等式∴x2=x3=x4=0∴x

=(1,0,0,0,1)T

Z=5由y1﹡，y2﹡﹥0知原約束為等式

x1+3x5=42x1+x5=3第40頁，課件共56頁，創(chuàng)作于2023年2月1.7.3對偶解的經(jīng)濟(jì)意義(1)、Z=CBB-1b+

(CN-CBB-1N)XN(*)Z=Z(b)b為資源對(*)求偏導(dǎo)：

Z

b=CBB-1=y對偶解y：b的單位改變量所引起的目標(biāo)函數(shù)改變量。第41頁，課件共56頁，創(chuàng)作于2023年2月經(jīng)濟(jì)解釋：W=yb=(y1…ym)b1bm…=b1y1+b2y2+…+bmymbi：

第i種資源的數(shù)量yi：對偶解bi增加bi,其它資源數(shù)量不變時,目標(biāo)函數(shù)的增量Z=biyiyi：反映bi的邊際效益(邊際成本)例1中y1=2/9,當(dāng)機(jī)器臺時數(shù)增加1個單位時，工廠可增加利潤2/9個單位。第42頁，課件共56頁，創(chuàng)作于2023年2月(3)、應(yīng)用情況①某資源對偶解>0，該資源有利可圖，可增加此種資源量；某資源對偶解為0，則不增加此種資源量。情況②直接用影子價格與市場價格相比較，進(jìn)行決策，是否買入該資源。第43頁，課件共56頁，創(chuàng)作于2023年2月(2)、影子價格由(1)的經(jīng)濟(jì)解釋可知，yi的大小與系統(tǒng)內(nèi)資源對目標(biāo)的貢獻(xiàn)有關(guān)，是資源的一種估價，稱為影子價格。

yi的準(zhǔn)確經(jīng)濟(jì)意義與建模有關(guān)。情況①模型中，目標(biāo)函數(shù)系數(shù)Ci表示利潤時，

yi不是真正的影子價格，只表示資源bi增加1單位時，企業(yè)目標(biāo)增加的凈利潤。情況②模型中，目標(biāo)函數(shù)系數(shù)Ci表示成本時，

yi是真正的影子價格。第44頁，課件共56頁，創(chuàng)作于2023年2月例1：MaxZ=2X1+X2X1+X2+X3=

52X2+X354X2+6X3

9X1,X2,X30第45頁，課件共56頁，創(chuàng)作于2023年2月1.7.4對偶單純形法思路：(max型)單純形法：找基B，滿足B-1b0，但C

-CBB-1A不全0，（即檢驗(yàn)數(shù)）。迭代保持B-1b0，使C

-CBB-1A0，即CBB-1AC第46頁，課件共56頁，創(chuàng)作于2023年2月對偶單純形法：找基B，滿足C

-CBB-1A0，但B-1b不全0迭代保持C

-CBB-1A0，使B-1b0第47頁，課件共56頁，創(chuàng)作于2023年2月maxZ=2X1+X2X1+X2+X3=

52X2+X3+X4=5-4X2-6X3+X5=-9X1…X5

0B=(P3P4P1P2)CN-CBB-1N=(1,0)-(2,0,0)1121-4-2=(-1,-2)第48頁，課件共56頁，創(chuàng)作于2023年2月21000X1X2X3X4X5CBXB100-1-2002

X15111000X45021100X5-90(-4)-601XB31/400-1/20-1/4X111/410-1/201/4X41/200-211/2X29/4013/20-1/4第49頁，課件共56頁，創(chuàng)作于2023年2月對偶單純形法基本步驟max型(min型)(1)、作初始表，要求全部λj

0(0)(2)、判定：B-1b全0，停。否則，取max{B-1b}=(B-1b)l

B-1b<0令第l行的Xjl為換出變量.第50頁，課件共56頁，創(chuàng)作于2023年2月(3)、確定換入變量①若Xil行的alj全0，停，原問題無可行解。②若Xil行的alj有alj<0,則求λjλkθ=min{}=aljalkalj<0

Xk為換入變量λkalk(4)、以alk為主元，換基迭代第51頁，課件共56頁，創(chuàng)作于2023年2月

關(guān)于①的解釋：第l個方程(B-1b)l=xil+

aljxjjN即xil=(B-1b)l-

aljxj

<0

0>0某xj從0↗，xil不能變>0②為保持λj

0，即對偶解可行性第52頁，課件共56頁，創(chuàng)作于2023年2月例2minZ=2X1+3X2+4X3X1+2X2+X3

32X1-X2+3X34X1,X2,X30minZ=2X1+3X2+4X3-X1-2X2-X3+X4=-

3-2X1+X2-3X3+X5=-

4X1…X5

0第53頁，課件共56頁，創(chuàng)作于2023年2月23400XBX1X2X3X4X50234000

X4-3-1-2-1100

X5