运筹学 第三章 线性规划的对偶原理.ppt

1、1,第三章线性规划的对偶原理,单纯形法的矩阵描述 A为mn阶矩阵 RankA=m,取B为可行基,N为非基，,2,求解步骤：,3,4,现在不再生产，将设备材料出租出让，确定租费及转让费？ 设y1为设备单位台时的租金，y2,y3为材料A、B转让附加费(kg-1) 目标函数，约束条件？,则M2为M1的对偶问题， 反之亦然。,5,一般的，原问题：max z = CX AX b X 0,对偶问题：min w = Yb YA C Y 0,比较： max z min w 决策变量为n个 约束条件为n个 约束条件为m个 决策变量为m个 “” “” 约束条件的限定向量 目标函数的价值向量 目标函数的价值向量 约

2、束条件的限定向量,6,二、 对偶问题的化法 1、典型情况（对称形式） 例2max z = x1 + 2x2 + x3 2x1 + x2 6 2x2 + x3 8 x1,x2,x3 0,7,2、含等式的情况 例3max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 = 3 x1 + 2x2 + 5x3 4 x1,x2,x3 0,一般，原问题第i个约束取等式，对偶问题第i个变量自由变量。,8,3、含“”的max问题 例4max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 3 x1 + 2x2 + 5x3 4 x1,x2,x3 0,9,一般: max问题

3、第i个约束取“”，则min问题第i个变量 0 ；, min问题第i个约束取“”，则max问题第i个变量 0 ；, 原问题第i个约束取等式，对偶问题第i个变量 自由变量；, max问题第j个变量 0 ,则min问题第j个约束取“” ；, min问题第j个变量 0 ，则max问题第j个约束取“” ；, 原问题第j个变量自由变量，对偶问题第j个约束取等式。,10,例5 min z = 2x1 + 3x2 - 5x3 + x4 x1 + x2 - 3x3 + x4 5 2x1 + 2x3 - x4 4 x2 + x3 + x4 = 6 x1 0,x2,x3 0,x4自由变量,11,2 对偶问题的基本性

4、质和基本定理,1、对称性定理 对偶问题的对偶为原问题.,原问题：max z = CX AX b X 0 (1),对偶问题：min w = Yb YA C Y 0 (2),证：,(2)作变换：,(2)等价于：,对偶,令z=w,即为(1), (2)的对偶问题为(1)。,12,证：,推论： (1)max问题任一可行解的目标值为min问题目标值的一个下界； (2)min问题任一可行解的目标值为max问题目标值的一个上界。,13,3、无界性（性质2的推论） 若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。,注：该性质的逆不存在。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为

5、无可行解。,14,4、最优性 设X*，Y*分别为原问题和对偶问题可行解， 当CX*=Y*b时， X*，Y*分别为最优解。,证：,X*为最优解,Y*为最优解,15,5、对偶定理 若原问题有最优解，那么对偶问题也有最优解，且目标值相等。,证：,16,5、对偶定理 若原问题有最优解，那么对偶问题也有最优解，且目标值相等。,推论（单纯形乘子Y的定理）： 原问题有一个对应于基B的最优解，则此时的Y是对偶问题的一个最优解。,例：书P25,17,对偶问题中，解的情况有： 1.都有有限最优解 2.都无可行解 3.一个有无界解，另一个无可行解,18,6、松弛性 若X*，Y*分别为原问题及对偶问题的可行解， 那么

6、Ys*X*=0，Y*Xs*=0， 当且仅当X*，Y*分别为最优解。,证：,将b，C代入目标函数，,19,7、检验数与解的关系 原问题附加变量最优检验数的值为对偶问题的最优解。,检验数： = (C 0)- CBB-1(A -I) = (C- CBB-1A CBB-1) = (c s) c = C - CBB-1A X对应的检验数 s = CBB-1 Xs对应的检验数,例：书P25,4 =2，5 =3,20,求对偶问题的最优解: 1.单纯形乘子Y的定理 2.松弛性 3.检验数与解的关系,21,例6已知：min w = 20y1 + 20y2 的最优解为y1*=1.2,y2*=0.2 -ys1 y1

7、 + 2y2 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,22,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*待定

8、 由 3y1* + 2y2* = 4 =右边 ys4* = 0 x4*待定,最优解：x1* = 0 x2* = 0 x3* = 4 x4* = 4 xs1* = 0 xs2* = 0 最大值：z* = 28 = w*,y1*=1.2, y2*=0.2 ys1*x1* =0 ys2*x2* =0 ys3*x3* =0 ys4*x4* =0 y1*xs1* =0 y2*xs2* =0,y1 + 2y2 - ys1* = 1 2y1 + y2 - ys2* = 2 2y1 + 3y2 - ys3* =3 3y1 + 2y2 - ys4* = 4 x1 + 2x2 + 2x3 + 3x4 +xs1 =

9、 20 2x1 + x2 + 3x3 + 2x4 +xs2 = 20,23,8、对偶问题的经济含义影子价格 最优情况：z* = w* = b1y1* + + biyi* + + bmym*,b1： 8 9 Q2(4，2.5) z* = 15.5 z* = z*- z* = 3/2 = y1* b2：16 17 Q2”(4.25，1.875) z*” = 14.125 z* = z*”- z* = 1/8 = y2* b3：12 13 z* = 0 = y3*,Q2,Q2”,Q2（4，2） z =14,条件3未满足，再增加b，不会带来z的增加， 故该资源价值为0.,24,3 对偶单纯形法 单纯形

10、法：由 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)；,25,(4)取主变换，得到新的XB。,(3)基变换 换出变量，,换入变量（最大负比值规则），,重复（2）-（4）步，求出结果。,26,例8用对偶单纯形

11、法求解 min w = 2x1 + 3x2 + 4x3 x1 + 2x2 + x3 1 2x1 - x2 + 3x3 4 x1,x2,x3 0,min w = 2x1 + 3x2 + 4x3 + 0 x4 + 0 x5 x1 + 2x2 + x3 - x4 1 2x1 - x2 + 3x3 x5 4 x1,x2,x3,x4,x5 0,27,min w = 2x1 + 3x2 + 4x3 + 0 x4 + 0 x5 - x1 - 2x2 - x3 + x4 - 1 - 2x1 + x2 - 3x3 + x5 - 4 x1,x2,x3,x4,x5 0,28,*,-4,-2.5,2,-0.5,0.5

12、,0,1,0,1,1.5,4,-0.5,x1,-0.5,1,x4,0,2,0,0,1,1,29,初始检验数中有负数？对偶不可行,1、构造扩充问题 增加一个变量和一个约束条件 2、求基本解（初始对偶可行） 检验数中最小的负数 换入变量 新增变量为换出变量 取主变换后全部检验数非负 3、用对偶单纯形法求解扩充问题 扩充问题无可行解，则原问题无可行解 扩充问题有最优解，则原问题有可行解，且如扩充问题的目标函数值与M无关，则为原问题最优解。,30,例：,标准型：,扩充问题：,31,*,2M,-3,6-M,1,0,0,0,0,1,1,4,1,x1,0,M-8,x4,0,-2,0,0,2,2,0,x5,1

13、 1 1 0 0 1 M,0,1,-1,32,作业 P81 1.12(1),33,4 灵敏度分析,分析 变化对最优解的影响。,1、保持原最优基的变化范围； 2、原最优基不再最优时，求新的最优解的最简便方法,34,35,例1 已知下述问题的最优解及最优单纯形表,36,最优单纯形表如下:,37,由最优单纯形表得:,38,39,不可行!,用对偶单纯形法计算,40,4,20,4,41,42,43,例2 求例1 c4的变化范围,使最优解不变.,解:,44,分析:,45,方法:,例3 求例1 c2的变化范围,使最优解不变.,46,解:,0,1/8,3/2,0,0,0,-1/8,1/2,1,0,2,-3,1

14、,1/2,-2,0,0,4,x5,0,0,1/4,0,0,1,4,x1,-2,x5,x4,x3,x2,x1,b,XB,CB,0,0,0,-3,-2,x2,47,48,改变C，求新的最优解? 只需修改最终表上的C及检验数，得到新的迭代表，继续求解。,例3 c2=1,求新的最优解.,-2,-2,1,1/4,c2=-3，若c2=4？,最优解不变.,0 0 -1/2 5/8 0,1,1,继续用单纯形法求解.,49,分析:,50,51,例4 求例1 a24的变化范围,使最优解不变.,解:,x4为非基变量，故只影响x4的检验数。,52,基变量约束系数的变化 会导致问题变得相当复杂，所以重新计算。,53,四

15、、增加一个新变量 例5 在例1的基础上，企业要增加一个 新产品,每件产品需2个台时，原材料A 6kg， 原材料B 3kg，利润 5元/件，问如何安排各产 品的产量，使利润最大？ 解：,54,表明生产新品有利。,55,56,-5/4,0,1/8,3/2,0,0,1/4,0,-1/8,1/2,1,0,2,-3,2,1,1/2,-2,0,0,4,x5,0,3/2,0,1/4,0,0,1,4,x1,-2,x5,x4,x3,x2,x1,b,XB,CB,-5,0,0,0,-3,-2,x2,8/3,4/2,8,i,x3,2,14,57,五、增加一个新的约束条件 1、原最优解满足新约束，则最优解不变。 2、若不满足，则需求新的最优解。 例:原问题： 加条件：,58,需求新