清华大学《运筹学》教材相应的授课文档第二章

1、1,第二章对偶理论与灵敏度分析,1 单纯形法的矩阵描述 设max z = CX AX = b X 0 A为mn阶矩阵 RankA=m ,取B为可行基, N为非基，,2,3,4,求解步骤：,5,6,现在出租，设y1为设备单位台时的租金 y2,y3为材料A、B转让附加费(kg-1),则M2为M1的对偶问题， 反之亦然。,7,一般的，原问题：max z = CX AX b X 0,对偶问题：min w = Yb YA C Y 0,比较： max z min w 决策变量为n个 约束条件为n个 约束条件为m个 决策变量为m个 “” “”,8,3 对偶问题的化法 1、典型情况 eg.2max z = x

2、1 + 2x2 + x3 2x1 + x2 6 2x2 + x3 8 x1,x2,x3 0,9,2、含等式的情况 eg.3max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 = 3 x1 + 2x2 + 5x3 4 x1,x2,x3 0,一般，原问题第i个约束取等式，对偶问题第i个变量无约束。,10,3、含“”的max问题 eg.4max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 3 x1 + 2x2 + 5x3 4 x1,x2,x3 0,11,一般: max问题第i个约束取“”，则min问题第i个变量 0 ；, min问题第i个约束取“”，则

3、max问题第i个变量 0 ；, 原问题第i个约束取等式，对偶问题第i个变量 无约束；, max问题第j个变量 0 ,则min问题第j个约束取“” ；, min问题第j个变量 0 ，则max问题第j个约束取“” ；, 原问题第j个变量无约束，对偶问题第j个约束取等式。,12,eg.5min z = 2x1 + 3x2 - 5x3 + x4 x1 + x2 - 3x3 + x4 5 2x1 + 2x3 - x4 4 x2 + x3 + x4 = 6 x1 0,x2,x3 0,x4无约束,13,4 对偶问题的性质,1、对称性 对偶问题的对偶为原问题.,14,15,16,推论： (1) max问题任一

4、可解的目标值为min问题目标值的一个下界； (2) min问题任一可解的目标值为max问题目标值的一个上界。,3、无界性 若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。,注：该性质的逆不存在。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。,17,4、最优性 设X*，Y*分别为原问题和对偶问题可行解，当 CX*=Y*b时， X*，Y*分别为最优解。,18,5、对偶定理 若原问题有最优解，那么对偶问题也有最优解， 且目标值相等。,19,Y*为对偶问题的最优解，且原问题和对偶问题 的目标值相等。 证毕,6、松弛性 若X*，Y*分别为原问题及对偶问题的可行解，

5、 那么Ys*X*=0，Y*Xs*=0，当且仅当X*，Y*分别为 最优解。,证明：,20,将b,C分别代入目标函数：,21,其中：,用分量表示：,22,7、检验数与解的关系 (1)原问题非最优检验数的负值为对偶问题的一个基解。 (2)原问题最优检验数的负值为对偶问题的最优解。,检验数： = (C 0)- CBB-1(A I) = (C- CBB-1A - CBB-1) = (c s) c = C - CBB-1A X对应的检验数 s = - CBB-1 Xs对应的检验数,23,eg.6已知：min w = 20y1 + 20y2 的最优解为y1*=1.2,y2*=0.2 -ys1 y1 + 2y

6、2 1 试用松弛性求对偶 -ys2 2y1 + y2 2 问题的最优解。 -ys3 2y1 + 3y2 3 -ys4 3y1 + 2y2 4 y1,y2 0,y1*xs1* = 0 y2*xs2* = 0 ys1*x1* = 0 ys2*x2* = 0 ys3*x3* = 0 ys4*x4* = 0,24,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*待定 由 3y

7、1* + 2y2* = 4 =右边 ys4* = 0 x4*待定,最优解：x1* = 0 x2* = 0 x3* = 4 x4* = 4 xs1* = 0 xs2* = 0 最大值：z* = 28 = w*,25,5 对偶问题的经济含义影子价格 最优情况：z* = w* = b1y1* + + biyi* + + bmym*,26,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是否成立？ 若成立，X

8、B为最优基变量； 若不成立，转(3)；,27,(4)消元运算，得到新的XB。,(3)基变换 出基变量，,入基变量，,重复（2）-（4）步，求出结果。,28,eg.8用对偶单纯形法求解 min w = 2x1 + 3x2 + 4x3 x1 + 2x2 + x3 1 2x1 - x2 + 3x3 4 x1,x2,x3 0,29,x4,x5 0 非最优,x1,x4 0 最优,最优解：x1* = 2，x2* = 0，x3* = 0，x4* = 1，x5* = 0 目标值：w* = -z* = 4,30,7 灵敏度分析,分析 变化对最优解的影响。,31,32,例1 已知下述问题的最优解及最优单纯形表,33,最优单纯形表如下:,34,由最优单纯形表得:,35,36,不可行!,用对偶单纯形法计算,37,3/4,-2,38,39,例2 求例1 c4的变化范围,使最优解不变.,解:,40,分析:,41,方法:,例3 求例1 c2的变化范围,使最优解不变.,42,解:,43,44,分析:,45,46,例4 求例1 a24的变化范围,使最优解不变.,解:,47,例5 在例1的基础上，企业要增加一个 新产品,每件产品需2个台时，原材料A 6kg， 原材料B 3kg，利润 5元/件，问如何安排各产 品的产量，使利润最大？ 解：,48,表明生产新品有利。,49,50,