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

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

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

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

X2為產品1，2的產量2X1+2X2

12X1+2X2

84X1

164X2

12X1X2

0maxZ=2X1+3X2221212X1840X21604

12

(23)

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

y2,

y3,

y4分別為A,B,C,D設備的單價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月對偶問題的性質：(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月對偶關系對應表

原問題對偶問題目標函數類型maxmin目標函數系數目標函數系數右邊項系數與右邊項的對應關系右邊項系數目標函數系數變量數與約束數變量數n約束數n的對應關系約束數m變量數m原問題變量類型與

0

對偶問題約束類型變量

0約束

的對應關系無限制＝原問題約束類型與

0對偶問題變量類型約束

變量

0的對應關系＝無限制第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或將原問題變形為第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月產品A，B產量X1，X2，Z為利潤例1、3X1+X2+X3=483X1+4X2+X4=120X1…X40maxZ=5X1+6X23X1+X2

483X1+4X2120X1,X2

0機器臺時勞動工時第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月觀察結論:①一對對偶問題都有最優(yōu)解，且目標函數值相等。②最優(yōu)表中有兩個問題的最優(yōu)解。第21頁，課件共56頁，創(chuàng)作于2023年2月1.7.2對偶問題解的性質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月其目標函數值為yb=CBB-1b設(P)的最優(yōu)解為X，其目標函數值為X=CBB-1bC所以是(D)的最優(yōu)解。y第26頁，課件共56頁，創(chuàng)作于2023年2月推論：分別為(P),(D)可行解，又是最優(yōu)解，則有Xy,XyC=b證明：對應基為B，則y=CBB-1是(D)的可行解。XX=yb

C有yb(最優(yōu)解)y又由定理1，有X=Cyb第27頁，課件共56頁，創(chuàng)作于2023年2月定理4(松緊定理)互補松弛性原問題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的檢驗數是ym+j(P)的xn+i的檢驗數是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﹡代入，知②,③,④為嚴格不等式∴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對偶解的經濟意義(1)、Z=CBB-1b+

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

Z

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

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

yi的準確經濟意義與建模有關。情況①模型中，目標函數系數Ci表示利潤時，

yi不是真正的影子價格，只表示資源bi增加1單位時，企業(yè)目標增加的凈利潤。情況②模型中，目標函數系數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，（即檢驗數）。迭代保持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月

關于①的解釋：第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