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

第二章对偶问题与灵敏度分析第一页，共五十六页，2022年，8月28日1第二章：第一部分LP的对偶理论

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

A2212B128C4016D041223销售收入产品设备第二页，共五十六页，2022年，8月28日设X1，

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

12X1+2X2

84X1

164X2

12X1X2

0maxZ=2X1+3X2221212X1840X21604

12(23)

X1X2第三页，共五十六页，2022年，8月28日设y1,

y2,

y3,

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

021402204y1y2y3y423第四页，共五十六页，2022年，8月28日(y1y2y3y4)22124004(2,3)minW=12y1+8y2+16y3+12y4y1…y4“影子价格”第五页，共五十六页，2022年，8月28日“对称型”定义：对偶问题minW=yb

yA

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

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

AX

bX0A矩阵X,b列向量C行向量原问题第六页，共五十六页，2022年，8月28日对偶问题的性质：(1)、对偶问题的对偶问题是原问题。(2)、maxZ=CX

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

yACy为自由第七页，共五十六页，2022年，8月28日例1、写出下面问题的对偶规划maxZ=5X1+6X23X1-2X2=74X1+X2

9X1,X2

0第八页，共五十六页，2022年，8月28日解：3X1-2X2

73X1-2X2

74X1+X2

9maxZ=5X1+6X23X1-2X27-3X1+2X2

-74X1+X2

9X1,X2

0y1'y1"y2第九页，共五十六页，2022年，8月28日对偶问题令y1=

y1'

-y1"

3y1'

-3y1"

+4y25

-2y1'

+2y1"

+y2

6y1'

,y1",y2

0minW=7y1'

-7y1"

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

-2y1+y2

6y1自由

,y2

0第十页，共五十六页，2022年，8月28日(3)、原问题第k个约束为等式，对偶问题第k个变量是自由变量。原问题第k个变量是自由变量，则对偶问题第k个约束为等式约束。第十一页，共五十六页，2022年，8月28日对偶关系对应表

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

0

对偶问题约束类型变量

0约束

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

0对偶问题变量类型约束

变量

0的对应关系＝无限制第十二页，共五十六页，2022年，8月28日例2、写对偶规划minZ=4X1+2X2-3X3-X1+2X2

62X1+3X3

9X1+5X2-2X3=

4X2,X30第十三页，共五十六页，2022年，8月28日maxW=6y1+9y2+4y3-y1+2y2+y3=

42y1+5y323y2-2y3

-3y10,y20,y3自由第十四页，共五十六页，2022年，8月28日minZ=4X1+2X2-3X3X1-2X2

-

62X1+3X3

9X1+5X2-2X3=

4X2,X30或将原问题变形为第十五页，共五十六页，2022年，8月28日maxW=-6y1+9y2+4y3y1+2y2+y3=

4-2y1+5y323y2-2y3

-3y1,y20,y3自由对偶规划第十六页，共五十六页，2022年，8月28日产品A，B产量X1，X2，Z为利润例1、3X1+X2+X3=483X1+4X2+X4=120X1…X40maxZ=5X1+6X23X1+X2483X1+4X2120X1,X2

0机器台时劳动工时第十七页，共五十六页，2022年，8月28日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第十八页，共五十六页，2022年，8月28日3y1+3y25

y1+4y2

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

y1+4y2-y4+y6=

6minW=48y1+120y2+My5+My6第十九页，共五十六页，2022年，8月28日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第二十页，共五十六页，2022年，8月28日观察结论:①一对对偶问题都有最优解，且目标函数值相等。②最优表中有两个问题的最优解。第二十一页，共五十六页，2022年，8月28日1.7.2对偶问题解的性质maxZ=CX

AX≤bX0(P)minW=yb

yACy0(D)第二十二页，共五十六页，2022年，8月28日定理1、(弱对偶定理)分别为(P),(D)的可行解，则有CbX，yXy证明：由AXb,y0有yAXby由AyC,X0有yAXCX所以CXyAXyb第二十三页，共五十六页，2022年，8月28日推论2、(P)有可行解,但无有限最优解，则(D)无可行解。定理2、yX,分别为(P),(D)的可行解，且XyC=b,则它们是(P),(D)

的最优解。证明：对任X，有CXby=CXX最优推论1、(P),(D)都有可行解，则必都有最优解。第二十四页，共五十六页，2022年，8月28日定理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第二十五页，共五十六页，2022年，8月28日其目标函数值为yb=CBB-1b设(P)的最优解为X，其目标函数值为X=CBB-1bC所以是(D)的最优解。y第二十六页，共五十六页，2022年，8月28日推论：分别为(P),(D)可行解，又是最优解，则有Xy,XyC=b证明：对应基为B，则y=CBB-1是(D)的可行解。XX=ybC有yb(最优解)y又由定理1，有X=Cyb第二十七页，共五十六页，2022年，8月28日定理4(松紧定理)互补松弛性原问题maxZ=cx

Ax

+

xs=bx,

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

xn+iyi=0(j=1……n)(i=1……m)第二十八页，共五十六页，2022年，8月28日对偶问题min=yb

yA

-

ys=cy,

ys0y=(y1…ym)ys=(ym+1…ym+n)第二十九页，共五十六页，2022年，8月28日证明：()∵

yA

c∴

yAx

cx∵

Ax

b∴

yAx

yb∵

cx≡

yb∴cx≡

yAx≡yb(yA-c)x≡0yA-c=ys0x0第三十页，共五十六页，2022年，8月28日∴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第三十一页，共五十六页，2022年，8月28日第三十二页，共五十六页，2022年，8月28日()∵

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第三十三页，共五十六页，2022年，8月28日

xjym+j(j=1…n)

yixn+i(i=1…m)(P)的xj的检验数是ym+j(P)的xn+i的检验数是yi第三十四页，共五十六页，2022年，8月28日例：min=5y1+y23y1+y29y1+y25y1+8y28y1,

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

x1,

x2,

x30(D)第三十五页，共五十六页，2022年，8月28日95800x1x2x3x4x5CBxB0958000

x45311100

x5111801CBxB90-4-640-90

x420-2-231-39

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

=9第三十六页，共五十六页，2022年，8月28日n=3m=2xn+iyi=0(i=1……m)

(i=1,2)xjym+j=0(j=1……n)

xj

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

yix1

y3x2

y4x3

y5x4

y1x5

y2第三十七页，共五十六页，2022年，8月28日例：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)第三十八页，共五十六页，2022年，8月28日解：(D)为maxZ

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

y20第三十九页，共五十六页，2022年，8月28日将y1﹡，y2﹡代入，知②,③,④为严格不等式∴x2=x3=x4=0∴x

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

Z=5由y1﹡，y2﹡﹥0知原约束为等式

x1+3x5=42x1+x5=3第四十页，共五十六页，2022年，8月28日1.7.3对偶解的经济意义(1)、Z=CBB-1b+

(CN-CBB-1N)XN(*)Z=Z(b)b为资源对(*)求偏导：Zb=CBB-1=y对偶解y：b的单位改变量所引起的目标函数改变量。第四十一页，共五十六页，2022年，8月28日经济解释：W=yb=(y1…ym)b1bm…=b1y1+b2y2+…+bmymbi：

第i种资源的数量yi：对偶解bi增加bi,其它资源数量不变时,目标函数的增量Z=biyiyi：反映bi的边际效益(边际成本)例1中y1=2/9,当机器台时数增加1个单位时，工厂可增加利润2/9个单位。第四十二页，共五十六页，2022年，8月28日(3)、应用情况①某资源对偶解>0，该资源有利可图，可增加此种资源量；某资源对偶解为0，则不增加此种资源量。情况②直接用影子价格与市场价格相比较，进行决策，是否买入该资源。第四十三页，共五十六页，2022年，8月28日(2)、影子价格由(1)的经济解释可知，yi的大小与系统内资源对目标的贡献有关，是资源的一种估价，称为影子价格。

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

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

yi是真正的影子价格。第四十四页，共五十六页，2022年，8月28日例1：MaxZ=2X1+X2X1+X2+X3=

52X2+X354X2+6X3

9X1,X2,X30第四十五页，共五十六页，2022年，8月28日1.7.4对偶单纯形法思路：(max型)单纯形法：找基B，满足B-1b0，但C

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

-CBB-1A0，即CBB-1AC第四十六页，共五十六页，2022年，8月28日对偶单纯形法：找基B，满足C

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

-CBB-1A0，使B-1b0第四十七页，共五十六页，2022年，8月28日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)第四十八页，共五十六页，2022年，8月28日21000X1X2X3X4X5CBXB100-1-2002

X15111000X45021100X5-90(-4)-601XB31/400-1/20-1/4X111/410-1/201/4X41/200-211/2X29/4013/20-1/4第四十九页，共五十六页，2022年，8月28日对偶单纯形法基本步骤max型(min型)(1)、作初始表，要求全部λj

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

B-1b<0令第l行的Xjl为换出变量.第五十页，共五十六页，2022年，8月28日(3)、确定换入变量①若Xil行的alj全0，停，原问题无可行解。②若Xil行的alj有alj<0,则求λjλkθ=min{}=aljalkalj<0

Xk为换入变量λkalk(4)、以alk为主元，换基迭代第五十一页，共五十六页，2022年，8月28日关于①的解释：第l个方程(B-1b)l=xil+

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

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

0，即对偶解可行性第五十二页，共五十六页，2022年，8月28日例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第五十三页，共五十六页，2022年，8月28日23400XBX1X2X3X4X50234000

X4-3-1-2-1100