第二章对偶问题与灵敏度分析

第二章对偶问题与灵敏度分析1第1页，课件共56页，创作于2023年2月第二章：第一部分LP的对偶理论1.7.1

对偶问题例12加工能力(小时/天)

A2212B128C4016D041223销售收入产品设备第2页，课件共56页，创作于2023年2月设X1，

X2为产品1，2的产量2X1+2X2

12X1+2X2

84X1

164X2

12X1X2

0maxZ=2X1+3X2221212X1840X21604

12

(23)

X1X2第3页，课件共56页，创作于2023年2月设y1,

y2,

y3,

y4分别为A,B,C,D设备的单价2y1+y2+4y322y1+2y2+443y1…y4

021402204y1y2y3y4

23第4页，课件共56页，创作于2023年2月(y1y2y3y4)22124004

(2,3)minW=12y1+8y2+16y3+12y4y1…y4“影子价格”第5页，课件共56页，创作于2023年2月“对称型”定义：对偶问题minW=yb

yA

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

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

AX

bX0A矩阵X,b列向量C行向量原问题第6页，课件共56页，创作于2023年2月对偶问题的性质：(1)、对偶问题的对偶问题是原问题。(2)、maxZ=CX

AX=bX0的对偶问题是minW=yb

yACy为自由第7页，课件共56页，创作于2023年2月例1、写出下面问题的对偶规划maxZ=5X1+6X23X1-2X2=74X1+X2

9X1,X2

0第8页，课件共56页，创作于2023年2月解：3X1-2X2

73X1-2X2

74X1+X2

9maxZ=5X1+6X23X1-2X2

7-3X1+2X2

-74X1+X2

9X1,X2

0y1'y1"y2第9页，课件共56页，创作于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页，创作于2023年2月(3)、原问题第k个约束为等式，对偶问题第k个变量是自由变量。原问题第k个变量是自由变量，则对偶问题第k个约束为等式约束。第11页，课件共56页，创作于2023年2月对偶关系对应表

原问题对偶问题目标函数类型maxmin目标函数系数目标函数系数右边项系数与右边项的对应关系右边项系数目标函数系数变量数与约束数变量数n约束数n的对应关系约束数m变量数m原问题变量类型与

0

对偶问题约束类型变量

0约束

的对应关系无限制＝原问题约束类型与

0对偶问题变量类型约束

变量

0的对应关系＝无限制第12页，课件共56页，创作于2023年2月例2、写对偶规划minZ=4X1+2X2-3X3-X1+2X2

62X1+3X3

9X1+5X2-2X3=

4X2,X30第13页，课件共56页，创作于2023年2月maxW=6y1+9y2+4y3-y1+2y2+y3=

42y1+5y323y2-2y3

-3y10,y20,y3自由第14页，课件共56页，创作于2023年2月minZ=4X1+2X2-3X3X1-2X2

-

62X1+3X3

9X1+5X2-2X3=

4X2,X30或将原问题变形为第15页，课件共56页，创作于2023年2月maxW=-6y1+9y2+4y3y1+2y2+y3=

4-2y1+5y323y2-2y3

-3y1,y20,y3自由对偶规划第16页，课件共56页，创作于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页，创作于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页，创作于2023年2月3y1+3y25

y1+4y2

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

y1+4y2-y4+y6=

6minW=48y1+120y2+My5+My6第19页，课件共56页，创作于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页，创作于2023年2月观察结论:①一对对偶问题都有最优解，且目标函数值相等。②最优表中有两个问题的最优解。第21页，课件共56页，创作于2023年2月1.7.2对偶问题解的性质maxZ=CX

AX≤bX0(P)minW=yb

yACy0(D)第22页，课件共56页，创作于2023年2月定理1、(弱对偶定理)分别为(P),(D)的可行解，则有C

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

yAX

yb第23页，课件共56页，创作于2023年2月推论2、(P)有可行解,但无有限最优解，则(D)无可行解。定理2、yX,分别为(P),(D)的可行解，且XyC=b,则它们是(P),(D)

的最优解。证明：对任X，有CX

by=CXX最优

推论1、(P),(D)都有可行解，则必都有最优解。第24页，课件共56页，创作于2023年2月定理3、B为(P)的最优基，则y=CBB-1是(D)的最优解。<称B为对偶最优基，为对偶最优解>y证明：由CBB-1BB-1bC-CBB-1A-CBB-1B-1AB-1有C-CBB-1A0-CBB-10

即yACy0所以是(D)的可行解。y第25页，课件共56页，创作于2023年2月其目标函数值为yb=CBB-1b设(P)的最优解为X，其目标函数值为X=CBB-1bC所以是(D)的最优解。y第26页，课件共56页，创作于2023年2月推论：分别为(P),(D)可行解，又是最优解，则有Xy,XyC=b证明：对应基为B，则y=CBB-1是(D)的可行解。XX=yb

C有yb(最优解)y又由定理1，有X=Cyb第27页，课件共56页，创作于2023年2月定理4(松紧定理)互补松弛性原问题maxZ=cx

Ax

+

xs=bx,

xs0x=x1xn…xs=xn+1xn+m…若x,y分别为(P),(D)的可行解，则x,y为最优解xj

ym+j=0且

xn+i

yi=0(j=1……n)(i=1……m)第28页，课件共56页，创作于2023年2月对偶问题min

=yb

yA

-

ys=cy,

ys0y=(y1…ym)ys=(ym+1…ym+n)第29页，课件共56页，创作于2023年2月证明：()∵

yA

c∴

yAx

cx∵

Ax

b∴

yAx

yb∵

cx≡

yb∴cx≡

yAx≡yb(yA-c)x≡0yA-c=ys0x0第30页，课件共56页，创作于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页，创作于2023年2月第32页，课件共56页，创作于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页，创作于2023年2月

xjym+j(j=1…n)

yixn+i(i=1…m)(P)的xj的检验数是ym+j(P)的xn+i的检验数是yi第34页，课件共56页，创作于2023年2月例：min

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

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

x1,

x2,

x30(D)第35页，课件共56页，创作于2023年2月95800x1x2x3x4x5CBxB0958000

x45311100

x5111801CBxB90-4-640-90

x420-2-231-39

x1111801(P)最优解(0,9,0,4,64),

=9第36页，课件共56页，创作于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页，创作于2023年2月例：min

=2x1+3x2+5x3+2x4+3x5其对偶解y1﹡=4/5y2﹡=3/5Z﹡=5用对偶理论求(P)的最优解x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53

xi0(i=1…5)(P)第38页，课件共56页，创作于2023年2月解：(D)为maxZ

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

y20第39页，课件共56页，创作于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页，创作于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页，创作于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页，创作于2023年2月(3)、应用情况①某资源对偶解>0，该资源有利可图，可增加此种资源量；某资源对偶解为0，则不增加此种资源量。情况②直接用影子价格与市场价格相比较，进行决策，是否买入该资源。第43页，课件共56页，创作于2023年2月(2)、影子价格由(1)的经济解释可知，yi的大小与系统内资源对目标的贡献有关，是资源的一种估价，称为影子价格。

yi的准确经济意义与建模有关。情况①模型中，目标函数系数Ci表示利润时，

yi不是真正的影子价格，只表示资源bi增加1单位时，企业目标增加的净利润。情况②模型中，目标函数系数Ci表示成本时，

yi是真正的影子价格。第44页，课件共56页，创作于2023年2月例1：MaxZ=2X1+X2X1+X2+X3=

52X2+X354X2+6X3

9X1,X2,X30第45页，课件共56页，创作于2023年2月1.7.4对偶单纯形法思路：(max型)单纯形法：找基B，满足B-1b0，但C

-CBB-1A不全0，（即检验数）。迭代保持B-1b0，使C

-CBB-1A0，即CBB-1AC第46页，课件共56页，创作于2023年2月对偶单纯形法：找基B，满足C

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

-CBB-1A0，使B-1b0第47页，课件共56页，创作于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页，创作于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页，创作于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页，创作于2023年2月(3)、确定换入变量①若Xil行的alj全0，停，原问题无可行解。②若Xil行的alj有alj<0,则求λjλkθ=min{}=aljalkalj<0

Xk为换入变量λkalk(4)、以alk为主元，换基迭代第51页，课件共56页，创作于2023年2月

关于①的解释：第l个方程(B-1b)l=xil+

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

aljxj

<0

0>0某xj从0↗，xil不能变>0②为保持λj

0，即对偶解可行性第52页，课件共56页，创作于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页，创作于2023年2月23400XBX1X2X3X4X50234000

X4-3-1-2-1100

X5