第2章-对偶理论和灵敏度分析课件

第二章 对偶理论与灵敏度分析§1单纯形法的矩阵描述

设max

z=CXAX=bX

≥

0

A为m×n阶矩阵RankA=m,取B为可行基,N为非基，

1第二章 对偶理论与灵敏度分析§1单纯形法的矩阵描述12233求解步骤：4求解步骤：432利润12kg40材料B16kg04材料A8台时

21设备台时限制

ⅡⅠ§2对偶问题的提出

[eg.1]制定生产计划M1:max

z=2x1

+

3x21x1

+

2x2≤84x1

≤

16

4x2

≤

12x1，x2

≥

0

532利润12kg40材料B16kg04材料A8台时21设备现在出租，设y1为设备单位台时的租金y2,y3为材料A、B转让附加费(kg-1)则M2为M1的对偶问题，反之亦然。M2:min

w=8y1

+

16y2

+

12y3y1+4y2

≥

22y1

+4y3≥3y1,y2,y3

≥

032利润12kg40材料B16kg04材料A8台时

21设备台时限制

ⅡⅠ6现在出租，设y1为设备单位台时的租金则M2为M1的对一般的，原问题：max

z=CXAX

≤

bX

≥

0

对偶问题：min

w=YbYA

≥

CY

≥

0比较：max

zmin

w

决策变量为n个约束条件为n个

约束条件为m个决策变量为m个“≤”“≥”7一般的，原问题：maxz=CXAX≤b§3对偶问题的化法1、典型情况

[eg.2]max

z=x1

+

2x2

+

x32x1

+

x2≤

62x2

+

x3≤

8x1,x2,x3

≥

0对偶：min

w=6y1

+

8y22y1

≥

1y1

+

2y2≥

2

y2≥

1y1,y2

≥

08§3对偶问题的化法对偶：minw=6y1+82、含等式的情况

[eg.3]max

z=x1

+

2x2

+

4x32x1

+

x2

+

3x3=3x1

+

2x2

+

5x3

≤

4x1,x2,x3

≥

0对偶：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无约束一般，原问题第i个约束取等式，对偶问题第i个变量无约束。2x1

+

x2

+

3x3≤

3-2x1

-

x2

-

3x3

≤-392、含等式的情况对偶：minw=3y1’-3y1”3、含“≥”的max问题

[eg.4]max

z=x1

+

2x2

+

4x32x1

+

x2

+

3x3

≥

3x1

+

2x2

+

5x3

≤

4x1,x2,x3

≥

0对偶：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

≤-3103、含“≥”的max问题对偶：minw=-3y1’一般:①max问题第i个约束取“≥”，则min问题第i个变量

≤

0；②min问题第i个约束取“≤”，则max问题第i个变量

≤

0；③原问题第i个约束取等式，对偶问题第i个变量

无约束；④max问题第j个变量

≤

0,则min问题第j个约束取“≤”；⑤min问题第j个变量

≤

0

，则max问题第j个约束取“≥”

；⑥原问题第j个变量无约束，对偶问题第j个约束取等式。约束条件符号判断：max->min相同，min->max相反决策变量符号判断：max->min相反，min->max相同11一般:②min问题第i个约束取“≤”，则max问题第i个[eg.5]min

z=2x1

+

3x2

-

5x3

+

x4x1

+

x2

-

3x3

+x4

≥

52x1

+

2x3

-

x4

≤

4

x2

+

x3

+

x4=6x1

≤

0,x2,x3

≥

0,x4无约束对偶：max

w=5y1

+

4y2

+

6y3y1

+

y2

≥

2y1

+

y3

≤

3-3y1

+

2y2

+

y3

≤

-5y1

-

y2

+

y3=1y1

≥

0,y2

≤

0,y3无约束12[eg.5]minz=2x1+3x2-5x对偶问题的基本性质一、单纯形法计算的矩阵描述MaxZ=CXAX≤bX≥0其中X＝(x1,x2……xn)TMaxZ=CX+0XsAX+IXs=bX,Xs≥0其中Xs＝(xn+1,xn+2……xn+m)TI为m×m的单位矩阵13对偶问题的基本性质一、单纯形法计算的矩阵描述MaxZ=CX

项目非基变量基变量XBXNXs0XsbBNIcj-zjCBCN0……项目基变量非基变量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1；初始单纯形表中基变量Xs=b，迭代后的表中为XB=B-1b；约束矩阵（A，I）＝（B，N，I），迭代后为（B-1B，B-1N，B-1I）＝（I，B-1N，B-1)；初始单纯形表中xj的系数向量为Pj，迭代后为Pj’，且Pj’=B-1Pj。14非基变量基变量XBmaxZ=4.5x1+5x2s.t.3x1+2x2≤244x1+5x2≤40x1,x2≥0minw=24y1+40y2s.t.3y1+4y2≥4.52y1+5x2≥5y1,y2≥0y1y2x1x2maxZ=4.5x1+5x2s.t.3x1+2x2+x3=244x1+5x2+x4=40x1,x2,x3,x4,≥0minw=24y1+40y2s.t.3y1+4y2-y3=4.52y1+5x2-y4=5y1,y2,y3,y4≥0y1y2x1x215maxZ=4.5x1+5x2minw=24y1+40y2y1cj4.5500θCBXBbx1x2x3x40x3243210120x44045018cj-zj4.55000x387/501-2/540/75x284/5101/510cj-zj1/200-14.5x140/7105/7-2/75x224/701-4/73/7cj-zj00-5/14-6/7Z=4.5×40/7＋5×24/7=300/7解原问题：16cj4.5500θCBXBbx1x2x3x40x324321解对偶问题：w=24×5/14＋40×6/7=300/7cj244000θCBYBby1y2y3y424y15/1410-5/74/740y26/7012/7-3/7cj-zj0040/724/717解对偶问题：w=24×5/14＋40×6/7=300/7cjcj4.5500θCBXBbx1x2x3x44.5x140/7105/7-2/75x224/701-4/73/7cj-zj00-5/14-6/7cj244000θCBYBby1y2y3y424y15/1410-5/74/740y26/7012/7-3/7cj-zj0040/724/7(x3,x4)=(0,0)(y3,y4)=(0,0)-y1-y2-y4-y3x1x2x4x3原问题对偶问题18cj4.5500θCBXBbx1x2x3x44.5x140/二、对偶问题的基本性质原始问题maxz=CXs.t.AX≤b X≥0对偶问题minw=Y’bs.t.ATY≥C’ Y≥01.弱对偶性若X‘为原问题的可行解，Y’为对偶问题的可行解，则恒有CX’≤Y’b19二、对偶问题的基本性质原始问题对偶问题1.弱对偶性19推论：原问题任一可行解的目标函数是其对偶问题目标函数值的下界，反之对偶问题任一可行解的目标函数是其原问题目标函数的上界。如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目标函数无界，则原问题无可行解。（对偶问题无可行解时，其原问题无界解或无可行解。若原问题有可行解而其对偶问题无可行解时，原问题目标函数无界若对偶问题有可行解而其原问题无可行解时，对偶问题目标函数无界。20推论：202.最优性若X‘为原问题的可行解，Y’为对偶问题的可行解，且CX‘＝Y’b则X’，Y‘分别为原问题和对偶问题的最优解。3.强对偶性若原问题和对偶问题均具有可行解，则两者均具有最优解，且他们的最优解的目标值相等。212.最优性3.强对偶性214.互补松弛定理在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为0，则该约束条件取严格等式，既松弛变量或剩余变量为0；反之如果对应某一约束条件的对偶变量值不为0，则该约束条件取严格不等式，既松弛变量或剩余变量不为0.若yi’＞0,即xsi=0若yi’＝0,即xsi＞0即xsi·yi=0同理若xj’＞0,即ysj=0若xj’＝0,即ysj＞0即ysj·xj=0224.互补松弛定理若yi’＞0,即xsi=0同理22maxZ=4.5x1+5x2s.t.3x1+2x2+x3=244x1+5x2+x4=40x1,x2,x3,x4,≥0y1y2minw=24y1+40y2s.t.3y1+4y2-y3=4.52y1+5x2-y4=5y1,y2,y3,y4≥0x1x2X3=0,3x1+2x2=24,y1=14/5X4=0,4x1+5x2=40,y2=6/7y3=0,3y1+4y2=5,x1=40/7y4=0,2y1+5y2=5,x2=24/723maxZ=4.5x1+5x2y1y2minw=24y1+40利用互补松弛关系求解线性规划minz=6x1+8x2+3x3s.t.x1+x2≥1x1+2x2+x3≥-1x1,x2,x3≥0maxw=y1-y2s.t.y1+y2≤6y1+2y2≤8y2≤3y1,y2≥0原始问题对偶问题012345678654321w1w2y=-1y=1y=3y=6最优解为(y1,y2)=(6,0)maxy=6先用图解法求解对偶问题。24利用互补松弛关系求解线性规划minz=6x1+8x2+3xminz=6x1+8x2+3x3s.t.x1+x2≥1x1+2x2+x3≥-1x1,x2,x3≥0maxw=y1-y2s.t.y1+y2≤6y1+2y2≤8y2≤3y1,y2≥0maxw=y1-y2s.t.y1+y2+y3=6y1+2y2+y4=8y2+y5=3y1,y2,y3,y4,y5≥0(y1,y2)=(6,0)(y1,y2,y3,y4,y5)=(6,0,0,2,3)minz=6x1+8x2+3x3s.t.x1+x2-x4=1x1+2x2+x3-x5=-1x1,x2,x3,x4,x5≥0(x1,x2,x3|x4,x5)(y1,y2|y3,y4,y5)x2=x3=x4=0x1=1,x5=2引进剩余变量求对偶引进松弛变量图解法求解代入约束求出松弛变量互补松弛关系代入约束求解(x1,x2,x3,x4,x5)=(1,0,0,0,2)25minz=6x1+8x2+3x3maxw=y1-y2ma§4对偶问题的性质

1、对称性对偶问题的对偶为原问题.26§4对偶问题的性质1、对称性2627272828推论：(1)max问题任一可解的目标值为min问题目标值的一个下界；(2)min问题任一可解的目标值为max问题目标值的一个上界。3、无界性若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。注：该性质的逆不存在。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。29推论：3、无界性注：该性质的逆不存在。若原(对偶)问4、最优性

设X*，Y*分别为原问题和对偶问题可行解，当

CX*=Y*b时，X*，Y*分别为最优解。304、最优性305、对偶定理若原问题有最优解，那么对偶问题也有最优解，且目标值相等。315、对偶定理31∴Y*为对偶问题的最优解，且原问题和对偶问题的目标值相等。证毕6、松弛性

若X*，Y*分别为原问题及对偶问题的可行解，那么Ys*X*=0，Y*Xs*=0，当且仅当X*，Y*分别为最优解。证明：32∴Y*为对偶问题的最优解，且原问题和对偶问题6、松弛性证明：将b,C分别代入目标函数：33将b,C分别代入目标函数：33其中：用分量表示：34其中：用分量表示：34

7、检验数与解的关系(1)原问题非最优检验数的负值为对偶问题的一个基解。(2)原问题最优检验数的负值为对偶问题的最优解。分析：max

z=CX

+

0Xs=(C0)(XXs)TAX

+

Xs=bX,Xs

≥

0min

w=Yb

+

YS0YA

-

Ys=CY,Ys

≥

0

检验数：σ

=(C0)-

CBB-1(AI)

=(C-

CBB-1A-

CBB-1)

=(σcσs)

σc

=

C

-

CBB-1AX对应的检验数

σs

=

-

CBB-1

Xs对应的检验数357、检验数与解的关系分析：maxz=CX+[eg.6]已知：min

w=20y1

+

20y2的最优解为y1*=1.2,y2*=0.2-ys1y1

+

2y2

≥

1①试用松弛性求对偶-ys22y1

+

y2

≥

2②问题的最优解。-ys32y1

+

3y2

≥

3③-ys43y1

+

2y2

≥

4④y1,y2

≥

0

解：对偶问题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*=036[eg.6]已知：minw=20y1+20y2

∵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

∴最优解：x1*

=0x2*

=0x3*

=4x4*

=4xs1*

=0xs2*

=0

最大值：z*

=28

=w*37∵y1*=1.2,y2*0.2>0∴xs1§5对偶问题的经济含义——影子价格最优情况：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”38§5对偶问题的经济含义——影子价格x2x1Q2[e§6对偶单纯形法

单纯形法：由XB=B-1b

≥

0，使σj

≤

0，j=1,···,m对偶单纯形法：由σj

≤

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

≥

0步骤：(1)保持σj

≤

0，j=1,···,n，确定XB，建立计算表格；

(2)判别XB=B-1b

≥

0是否成立？①若成立，XB为最优基变量；②若不成立，转(3)；

39§6对偶单纯形法步骤：(1)保持σj≤0，j=(4)消元运算，得到新的XB。(3)基变换

①出基变量，

②入基变量，

重复（2）-（4）步，求出结果。40(4)消元运算，得到新的XB。(3)基变换②入基变量，重

[eg.8]用对偶单纯形法求解

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

≥

041[eg.8]用对偶单纯形法求解解：maxz=-2x-2-3-400CBXBbx1x2x3x4X50x4-10x5-4出出出∵x4,x5<0

∴非最优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

∴最优最优解：x1*=2，x2*=0，x3*=0，x4*=1，x5*=0目标值：w*=-z*=442-2-3-400CBXBbx1x2x3x4X50x4-10x对偶单纯形法练习：43对偶单纯形法练习：43复习：

1、写出如下问题的对偶问题约束条件符号判断：max->min相同，min->max相反决策变量符号判断：max->min相反，min->max相同44复习：

1、写出如下问题的对偶问题约束条件符号判断：44复习：

2、用对偶单纯形法求解线性规划问题145复习：

2、用对偶单纯形法求解线性规划问题145§7灵敏度分析分析

变化对最优解的影响。46§7灵敏度分析分析变化对最优解的影响。44747例1已知下述问题的最优解及最优单纯形表,48例1已知下述问题的最优解及最优单纯形表,48最优单纯形表如下:0-1/8-3/2000-1/81/2102311/2-2004001/4001420003249最优单纯形表如下:0-1/8-3/2000-1/81/210由最优单纯形表得:50由最优单纯形表得:505151不可行!用对偶单纯形法计算52不可行!用对偶单纯形法计算52-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]53-3/4-1/20001/400103x23-1/2-1/4如下题：

（1）若增大到32，试分析最优性的变化。

（2）请分析在什么范围内变化，问题的最优基不变。最优单纯形表：-1/2-1/4000

3/2-1/40103/21-1/21/40017/2x12-15/25/410015/2x30ix5x4x3x2x1b基CB00012x254如下题：

（1）若增大到32，试分析最优性的变化。

（5555例2求例1c4的变化范围,使最优解不变.0-1/8-3/200

0-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x2解:56例2求例1c4的变化范围,使最优解不变.0-1/8-分析:57分析:57方法:例3求例1c2的变化范围,使最优解不变.0-1/8-3/200

0-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x258方法:例3求例1c2的变化范围,使最优解不变.0-1解:0-1/8-3/200

0-1/81/21023+11/2-2004x5001/40014x12ix5x4x3x2x1bXBCB0003+2x259解:0-1/8-3/200 0-1/81/21023+11/6060当目标函数中cj发生变化，将影响最终单纯形表非基变量的检验数。如果是非基变量的价值系数发生变化，只影响该非基变量的检验数，如果变化后的检验数仍然小于等于0，则最优解不变；如果是基变量的价值系数发生变化，将影响所有非基变量的检验数，只有当所有的非基变量检验数都仍然小于等于0，最优解才不变。61当目标函数中cj发生变化，将影响最终单纯形表非基变量的如下题：

（1）若c1变为1.5，c2变为2，试分析最优性的变化。

（2）请确定c2变化范围，使问题最优性不变。最优单纯形表：-1/2-1/4000

3/2-1/40103/21-1/21/40017/2x12-15/25/410015/2x30ix5x4x3x2x1b基CB00012x262如下题：

（1）若c1变为1.5，c2变为2，试分析最优性的分析:63分析:636464例5在例1的基础上，企业要增加一个新产品Ⅲ,每件产品需2个台时，原材料A6kg，原材料B3kg，利润5元/件，问如何安排各产品的产量，使利润最大？解：532利润12340料B16604料A8221设备bⅢⅡⅠ65例5在例1的基础上，企业要增加一个532利润12表明生产新品有利。66表明生产新品有利。665/40-1/8-3/200

1/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500032x2ix’3675/40-1/8-3/200 1/40-1/81/210235/40-1/8-3/200

1/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500032x28/34/28ix’3[2]0-5/8-7/16-1/400

0-1/8-3/163/4103/2311/21/4-10020-3/4-1/83/2011x12x5x4x3x2x1bXBCB500032x2ix’3x’35685/40-1/8-3/200 1/40-1/81/21023如下题：

若式中x2变为8、4、1，产品利润变为3，试分析最优性的变化。最优单纯形表：-1/2-1/4000

3/2-1/40103/21-1/21/40017/2x12-15/25/410015/2x30ix5x4x3x2x1b基CB00012x269如下题：

若式中x2变为8、4、1，产品利润变为3，试分析最小结1、对偶问题及其化法※原问题决策变量决定对偶问题约束条件关系※原问题约束条件决定对偶问题决策变量取值方向。70小结1、对偶问题及其化法※原问题决策变量决定对偶问题约束条件2、检验数的计算方法712、检验数的计算方法713、对偶问题的性质4、对偶单纯形法●弱对偶性●无界性●最优性●松弛性●检验数与对偶问题的解723、对偶问题的性质4、对偶单纯形法●弱对偶性●无界性●最优性对偶单纯形法的特点：当约束条件为“≥”时，不需要引入人工变量，从而使计算更为简便。用对偶单纯形法求解时，目标函数必须是求极大化的。73对偶单纯形法的特点：73步骤：1.确定初始解一般设松弛变量为初时基可行解2.判断若所有的基变量值均≥0，则此解为线性规划问题的最优解，若存在基变量的值≤0，则问题还没有达到最优解，需要进行改进。3.改进选择换出变量min{bi’/bi≤0}假设选取xk为换出变量选择换入变量θ＝min{(cj-zj)/arj|arj＜0,cj-zj＜0}则假设选取xl为换出变量4.迭代。使得alk＝1，其余aik为074步骤：74Minw=5y1+2y2+4y3s.t.3y1+y2+2y3≥46y1+3y2+5y3≥10y1,y2,y3≥0举例：Maxw’=-5y1-2y2-4y3s.t.-3y1-y2-2y3≤-4-6y1-3y2-5y3≤-10y1,y2,y3≥0Maxw’=-5y1-2y2-4y3s.t.-3y1-y2-2y3+y4=4-6y1-3y2-5y3+y5=10yi≥0(i=1,2,…,5)75Minw=5y1+2y2+4y3举例：Maxw’=-5y1-cj-5-2-400CBXBby1y2y3y4y5θ0y4-4-3-1-2100y5-10-6-3-5015/62/34/5cj-zj-5-2-4000y4-2/3-10-1/31-1/3122-2y210/3215/30-1/3cj-zj-10-2/30-2/3-5y12/3101/311/3-2y220112-1cj-zj00-1/3-1-1/3此时对偶问题和原问题都达到可行，所以均达到了最优解Y＝（2/3.2,0,0,0)W’=-22/3W=22/376cj-5-2-400CBXBby1y2y3y4y5θ0y4-5、灵敏度分析前提条件:原线性规划问题已取得了最优解；每次只讨论一种参数的变化，而参数之间的变化互不关联。775、灵敏度分析前提条件:77常用公式：78常用公式：787979目标函数：maxz=2x1+3x2约束条件：x1+2x2≤84x1≤164x2≤12x1，x2≥02x14100¼00x5400-2½13x2201½-1/8000-3/2-1/8080目标函数：maxz=2x1+3x22x14100第一二章总结线性规划问题的引出线性规划的一般模型线性规划的标准形式单纯形法的原理单纯形法大M法和两阶段法81第一二章总结线性规划问题的引出81对偶问题的提出根据原问题写对偶问题对偶问题的基本性质对偶单纯形表灵敏度分析82对偶问题的提出82课后题复习——原问题对偶问题关系83课后题复习——原问题对偶问题关系83课后题复习——对偶理论及性质84课后题复习——对偶理论及性质84课后题复习——两种单纯形法区别85课后题复习——两种单纯形法区别85课后题复习——对偶单纯形法计算步骤86课后题复习——对偶单纯形法计算步骤86课后题复习——灵敏度分析87课后题复习——灵敏度分析87第二章 对偶理论与灵敏度分析§1单纯形法的矩阵描述

设max

z=CXAX=bX

≥

0

A为m×n阶矩阵RankA=m,取B为可行基,N为非基，

88第二章 对偶理论与灵敏度分析§1单纯形法的矩阵描述1892903求解步骤：91求解步骤：432利润12kg40材料B16kg04材料A8台时

21设备台时限制

ⅡⅠ§2对偶问题的提出

[eg.1]制定生产计划M1:max

z=2x1

+

3x21x1

+

2x2≤84x1

≤

16

4x2

≤

12x1，x2

≥

0

9232利润12kg40材料B16kg04材料A8台时21设备现在出租，设y1为设备单位台时的租金y2,y3为材料A、B转让附加费(kg-1)则M2为M1的对偶问题，反之亦然。M2:min

w=8y1

+

16y2

+

12y3y1+4y2

≥

22y1

+4y3≥3y1,y2,y3

≥

032利润12kg40材料B16kg04材料A8台时

21设备台时限制

ⅡⅠ93现在出租，设y1为设备单位台时的租金则M2为M1的对一般的，原问题：max

z=CXAX

≤

bX

≥

0

对偶问题：min

w=YbYA

≥

CY

≥

0比较：max

zmin

w

决策变量为n个约束条件为n个

约束条件为m个决策变量为m个“≤”“≥”94一般的，原问题：maxz=CXAX≤b§3对偶问题的化法1、典型情况

[eg.2]max

z=x1

+

2x2

+

x32x1

+

x2≤

62x2

+

x3≤

8x1,x2,x3

≥

0对偶：min

w=6y1

+

8y22y1

≥

1y1

+

2y2≥

2

y2≥

1y1,y2

≥

095§3对偶问题的化法对偶：minw=6y1+82、含等式的情况

[eg.3]max

z=x1

+

2x2

+

4x32x1

+

x2

+

3x3=3x1

+

2x2

+

5x3

≤

4x1,x2,x3

≥

0对偶：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无约束一般，原问题第i个约束取等式，对偶问题第i个变量无约束。2x1

+

x2

+

3x3≤

3-2x1

-

x2

-

3x3

≤-3962、含等式的情况对偶：minw=3y1’-3y1”3、含“≥”的max问题

[eg.4]max

z=x1

+

2x2

+

4x32x1

+

x2

+

3x3

≥

3x1

+

2x2

+

5x3

≤

4x1,x2,x3

≥

0对偶：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

≤-3973、含“≥”的max问题对偶：minw=-3y1’一般:①max问题第i个约束取“≥”，则min问题第i个变量

≤

0；②min问题第i个约束取“≤”，则max问题第i个变量

≤

0；③原问题第i个约束取等式，对偶问题第i个变量

无约束；④max问题第j个变量

≤

0,则min问题第j个约束取“≤”；⑤min问题第j个变量

≤

0

，则max问题第j个约束取“≥”

；⑥原问题第j个变量无约束，对偶问题第j个约束取等式。约束条件符号判断：max->min相同，min->max相反决策变量符号判断：max->min相反，min->max相同98一般:②min问题第i个约束取“≤”，则max问题第i个[eg.5]min

z=2x1

+

3x2

-

5x3

+

x4x1

+

x2

-

3x3

+x4

≥

52x1

+

2x3

-

x4

≤

4

x2

+

x3

+

x4=6x1

≤

0,x2,x3

≥

0,x4无约束对偶：max

w=5y1

+

4y2

+

6y3y1

+

y2

≥

2y1

+

y3

≤

3-3y1

+

2y2

+

y3

≤

-5y1

-

y2

+

y3=1y1

≥

0,y2

≤

0,y3无约束99[eg.5]minz=2x1+3x2-5x对偶问题的基本性质一、单纯形法计算的矩阵描述MaxZ=CXAX≤bX≥0其中X＝(x1,x2……xn)TMaxZ=CX+0XsAX+IXs=bX,Xs≥0其中Xs＝(xn+1,xn+2……xn+m)TI为m×m的单位矩阵100对偶问题的基本性质一、单纯形法计算的矩阵描述MaxZ=CX

项目非基变量基变量XBXNXs0XsbBNIcj-zjCBCN0……项目基变量非基变量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1；初始单纯形表中基变量Xs=b，迭代后的表中为XB=B-1b；约束矩阵（A，I）＝（B，N，I），迭代后为（B-1B，B-1N，B-1I）＝（I，B-1N，B-1)；初始单纯形表中xj的系数向量为Pj，迭代后为Pj’，且Pj’=B-1Pj。101非基变量基变量XBmaxZ=4.5x1+5x2s.t.3x1+2x2≤244x1+5x2≤40x1,x2≥0minw=24y1+40y2s.t.3y1+4y2≥4.52y1+5x2≥5y1,y2≥0y1y2x1x2maxZ=4.5x1+5x2s.t.3x1+2x2+x3=244x1+5x2+x4=40x1,x2,x3,x4,≥0minw=24y1+40y2s.t.3y1+4y2-y3=4.52y1+5x2-y4=5y1,y2,y3,y4≥0y1y2x1x2102maxZ=4.5x1+5x2minw=24y1+40y2y1cj4.5500θCBXBbx1x2x3x40x3243210120x44045018cj-zj4.55000x387/501-2/540/75x284/5101/510cj-zj1/200-14.5x140/7105/7-2/75x224/701-4/73/7cj-zj00-5/14-6/7Z=4.5×40/7＋5×24/7=300/7解原问题：103cj4.5500θCBXBbx1x2x3x40x324321解对偶问题：w=24×5/14＋40×6/7=300/7cj244000θCBYBby1y2y3y424y15/1410-5/74/740y26/7012/7-3/7cj-zj0040/724/7104解对偶问题：w=24×5/14＋40×6/7=300/7cjcj4.5500θCBXBbx1x2x3x44.5x140/7105/7-2/75x224/701-4/73/7cj-zj00-5/14-6/7cj244000θCBYBby1y2y3y424y15/1410-5/74/740y26/7012/7-3/7cj-zj0040/724/7(x3,x4)=(0,0)(y3,y4)=(0,0)-y1-y2-y4-y3x1x2x4x3原问题对偶问题105cj4.5500θCBXBbx1x2x3x44.5x140/二、对偶问题的基本性质原始问题maxz=CXs.t.AX≤b X≥0对偶问题minw=Y’bs.t.ATY≥C’ Y≥01.弱对偶性若X‘为原问题的可行解，Y’为对偶问题的可行解，则恒有CX’≤Y’b106二、对偶问题的基本性质原始问题对偶问题1.弱对偶性19推论：原问题任一可行解的目标函数是其对偶问题目标函数值的下界，反之对偶问题任一可行解的目标函数是其原问题目标函数的上界。如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目标函数无界，则原问题无可行解。（对偶问题无可行解时，其原问题无界解或无可行解。若原问题有可行解而其对偶问题无可行解时，原问题目标函数无界若对偶问题有可行解而其原问题无可行解时，对偶问题目标函数无界。107推论：202.最优性若X‘为原问题的可行解，Y’为对偶问题的可行解，且CX‘＝Y’b则X’，Y‘分别为原问题和对偶问题的最优解。3.强对偶性若原问题和对偶问题均具有可行解，则两者均具有最优解，且他们的最优解的目标值相等。1082.最优性3.强对偶性214.互补松弛定理在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为0，则该约束条件取严格等式，既松弛变量或剩余变量为0；反之如果对应某一约束条件的对偶变量值不为0，则该约束条件取严格不等式，既松弛变量或剩余变量不为0.若yi’＞0,即xsi=0若yi’＝0,即xsi＞0即xsi·yi=0同理若xj’＞0,即ysj=0若xj’＝0,即ysj＞0即ysj·xj=01094.互补松弛定理若yi’＞0,即xsi=0同理22maxZ=4.5x1+5x2s.t.3x1+2x2+x3=244x1+5x2+x4=40x1,x2,x3,x4,≥0y1y2minw=24y1+40y2s.t.3y1+4y2-y3=4.52y1+5x2-y4=5y1,y2,y3,y4≥0x1x2X3=0,3x1+2x2=24,y1=14/5X4=0,4x1+5x2=40,y2=6/7y3=0,3y1+4y2=5,x1=40/7y4=0,2y1+5y2=5,x2=24/7110maxZ=4.5x1+5x2y1y2minw=24y1+40利用互补松弛关系求解线性规划minz=6x1+8x2+3x3s.t.x1+x2≥1x1+2x2+x3≥-1x1,x2,x3≥0maxw=y1-y2s.t.y1+y2≤6y1+2y2≤8y2≤3y1,y2≥0原始问题对偶问题012345678654321w1w2y=-1y=1y=3y=6最优解为(y1,y2)=(6,0)maxy=6先用图解法求解对偶问题。111利用互补松弛关系求解线性规划minz=6x1+8x2+3xminz=6x1+8x2+3x3s.t.x1+x2≥1x1+2x2+x3≥-1x1,x2,x3≥0maxw=y1-y2s.t.y1+y2≤6y1+2y2≤8y2≤3y1,y2≥0maxw=y1-y2s.t.y1+y2+y3=6y1+2y2+y4=8y2+y5=3y1,y2,y3,y4,y5≥0(y1,y2)=(6,0)(y1,y2,y3,y4,y5)=(6,0,0,2,3)minz=6x1+8x2+3x3s.t.x1+x2-x4=1x1+2x2+x3-x5=-1x1,x2,x3,x4,x5≥0(x1,x2,x3|x4,x5)(y1,y2|y3,y4,y5)x2=x3=x4=0x1=1,x5=2引进剩余变量求对偶引进松弛变量图解法求解代入约束求出松弛变量互补松弛关系代入约束求解(x1,x2,x3,x4,x5)=(1,0,0,0,2)112minz=6x1+8x2+3x3maxw=y1-y2ma§4对偶问题的性质

1、对称性对偶问题的对偶为原问题.113§4对偶问题的性质1、对称性261142711528推论：(1)max问题任一可解的目标值为min问题目标值的一个下界；(2)min问题任一可解的目标值为max问题目标值的一个上界。3、无界性若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。注：该性质的逆不存在。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。116推论：3、无界性注：该性质的逆不存在。若原(对偶)问4、最优性

设X*，Y*分别为原问题和对偶问题可行解，当

CX*=Y*b时，X*，Y*分别为最优解。1174、最优性305、对偶定理若原问题有最优解，那么对偶问题也有最优解，且目标值相等。1185、对偶定理31∴Y*为对偶问题的最优解，且原问题和对偶问题的目标值相等。证毕6、松弛性

若X*，Y*分别为原问题及对偶问题的可行解，那么Ys*X*=0，Y*Xs*=0，当且仅当X*，Y*分别为最优解。证明：119∴Y*为对偶问题的最优解，且原问题和对偶问题6、松弛性证明：将b,C分别代入目标函数：120将b,C分别代入目标函数：33其中：用分量表示：121其中：用分量表示：34

7、检验数与解的关系(1)原问题非最优检验数的负值为对偶问题的一个基解。(2)原问题最优检验数的负值为对偶问题的最优解。分析：max

z=CX

+

0Xs=(C0)(XXs)TAX

+

Xs=bX,Xs

≥

0min

w=Yb

+

YS0YA

-

Ys=CY,Ys

≥

0

检验数：σ

=(C0)-

CBB-1(AI)

=(C-

CBB-1A-

CBB-1)