第三章线性规划的对偶理论

第三章 线性规划的对偶理论组合优化理论组合优化理论 Combinatorial Optimization Theory1 对偶问题的提出一、对偶问题的实例 产品 资源资源 甲 乙 限制A 3 2 65 B 2 1 40C 0 3 75单件利润 1500 2500 max z =1500x1+2500x2s.t. 3x1+2x2 652x1 +x2 40 (1)3x2 75x1 , x2 0最优解为： x1* =5 ， x2* =25 zmax =70000设 y1, y2, y3 分别为 A, B, C 三种资源出售的价格3y1 +2y2 15002y1 + y2 +3y3 2500w= 65y1 +40y2 +75y3 min w = 65y1 +40y2 +75y3 s.t. 3y1 +2y2 1500 (2)2y1 + y2 +3y3 2500y1, y2, y3 0最优解为： y1*= 500y2*= 0 ， y3* = 500,wmin = 70000如果称（ 1）为 LP 问题的原问题，则称（ 2）为（ 1）的对偶问题。第 三 章 线性规划 的对偶理论二、对偶问题的形式 1、对称型对偶问题max z = c1x1 + c2x2 + + cnxn s.t. a11x1 + a12x2 + + a1nxn b1a21x1 + a22x2 + + a2nxn b2(3) am1x1 + am2x2 + + amnxn bmxj 0 （ j = 1,2, ,n）min w = b1 y1 + b2 y2 + +bm ym s.t. a11y1 + a21 y2 + + am1ym c1a12y1 + a22y2 + + am2 ym c2(4) a1ny1 + a2ny2 + + amnym cnyi 0 （ i = 1,2, ,m）定义 1 设原 LP 问题为 则称 下列 LP 问题为其 对偶问题，其中 yi 0 （ i = 1,2, ,m） 称为对偶变量，并称（ 3）、（ 4）为一对对称型对偶问题max z=cx(P) s.t. Ax bx 0min w= yb(D) s.t. yA cy 01 对偶问题的提出2、非对称型对偶问题max z = cx(P) s.t. Ax = bx 0max z = cxs.t. Ax b-Ax -bx 0引入对偶变量 （ u,v）， 其中 u = (u1,u2,um)为对应于第一组不等式约束 Ax b 的对偶变量， v = (v1,v2, vm) 为 对应于第二组不等式约束 -Ax -b 的对偶变量，按对称型的结论：min w = (u-v) bs.t. (u-v) A cu,v 0令 y=u-vmin w= yb(D) s.t. yA cy 0 min w = yb(D) s.t. yA cy 无符号限制第 三 章 线性规划 的对偶理论3、混合型对偶问题max z = c1x1+c2x2(P) s.t. A11x1+A12x2 b1A21x1+A22x2 = b2A31x1+A32x2 b3x1 0, x2 无符号限制其中 Aij 为 mi nj 矩阵 ； bi为 mi维列向量 ； cj为 nj 维 行向量； xj 为 nj 维 列向量 ，i=1,2,3； j=1,2,且m1+m2+m3= m, n1+n2= n令 x2=x21 - x22 , x21 , x22 0. 化原问题为标准型：max z = c1 x1+c2( x21 - x22)s.t. A11x1+A12(x21 - x22)+Isxs = b1A21x1+A22 (x21 - x22) = b2A31x1+A32 (x21 - x22)- Itxt= b3 x1 , x21 , x22 ,xs , xt 0 min w = b1 y1+b2y2 +b3y3s.t. y1 A11+y2 A21+y3 A31 c1y1 A12+ y2 A22 +y3 A32 c2-y1 A12- y2 A22 -y3 A32 -c2y1 Is 0 -y3 It 0 y1 ,y2 , y3无符号限制按 非对称型min w = b1 y1+b2y2 +b3y3s.t. y1 A11+y2 A21+y3 A31 c1 y1 A12+ y2 A22 +y3 A32 = c2y1 0 , y2 无符号限制 , y3 0 1 对偶问题的提出原问题与对偶问题的关系原问题目标函数 max 目标函数 minm个=n个=n个 00无符号限制m个 00无符号限制目标函数的系数约束条件右端常数系数矩阵 A约束条件右端常数目标函数的系数系数矩阵 AT约束条件约束条件变量变量对偶问题e.g. 1 写出 (P)问题的 (D)问题max z=2x1+3x2-5x3+x4s.t. 4x1+x2-3x3+2x4 5 3x1-2x2 +7x4 4-2x1+3x2+4x3+x4=6x1 0, x2,x3 0 , x4 无符号限制min w=5y1+4y2+6y3s.t. 4y1+3y2-2y3 2 y1-2y2+3y3 3-3y1 +4y3 -52y1+7y2+y3 = 1y1 0, y20 , y3无符号限制2 对偶问题的基本性质讨论对称形式：（ P） 问题max z = cxs.t. Ax bx 0（ D） 问题min w = ybs.t. yA cy 0一、对偶规划的若干定理Theorem 1 (对称性定理 ) 对偶问题的对偶是原问题 .互为对偶proofTheorem 2 (弱对偶定理 ) 设 x0 和 y0 分别是（ P） 问题和（ D） 问题的可行解，则必有 c x0 y0 b .Corollary 1 如果 x* 和 y* 分别是（ P） 问题和（ D） 问题的可行解，且 c x* = y* b， 则 x* 和 y* 分别是（ P） 问题和（ D） 问题的最优解。proof向前2 对偶问题的基本性质Theorem 1 (对称性定理 )proof : 先将 (D)问题化成原问题形式（ D） 问题min w = ybs.t. yA cy 0设 xT为它的对偶变量 , 写出它的对偶问题即这就是 (P)问题 . 证毕2 对偶问题的基本性质Theorem 2 (弱对偶定理 )proof : 因为 x0 是 (P)问题的可行解 , 故必有Ax0 b , x0 0 (1)又 y0是问题 (D)的可行解 , 于是有y0A c , y0 0 (2) 用 y0 左乘不等式 (1) 两边 , 得y0Ax0 y0b 用 x0 左乘不等式 (2) 两边 , 得y0Ax0 cx0 从而有 cx0 y0b 证毕c x0 y0 b第 三 章 线性规划 的对偶理论Corollary 2 在一对对偶问题中，如果其中一个问题可行，但目标函数无界，则另一个问题不可行。Corollary 3 如果一对对偶问题都有可行解，则它们都有最优解。Theorem 3 (对偶定理 ) 如果（ P） 问题（ D） 问题）有最优解，那么（ D） 问题（ （ P） 问题）也有最优解，且目标函数值相等。 proofCorollary 4 (单纯形乘子定理 ) 如果（ P） 问题有最优解，最优基为 B， 则 y* = cBB-1 就是 （ D） 问题的一个最优解 。 向前2 对偶问题的基本性质Theorem 3 (对偶定理 )proof : 设 x*是（ P） 问题的最优解，它对应的基矩阵为 B， 引入松弛变量 xs=(xn+1， xn+2， , xn+m)T 将（ P） 问题化为标准形式 . 显然，该问题也有最优解由 最优性判别定理知令 则有即这 表明 是 （ D） 问题的可行解对应的目标函数值为 ：又 因为 x* 是 （ P） 问题的最优解，其目标函数值为：所以有则 由 Corollary 1 知 （ D） 问题有最优解，且两者的目标函数的最优值相等。同理可证，当 （ D） 问题有最优解时， （ P） 问题也有最优解，且目标函数相等。 证毕第三章 线性规划的对偶理论2 对偶问题的基本性质Corollary 5 对于对称形式 （ P） 问题，如果有最优解，则在其最优单纯形表中，松弛变量 x n+1 , x n+2 , x n+m的检验数（ ）的 负值即为（ D） 问题的一个最优解 。cBs xBsc0 xs检验数cB cN 0xB xN xsB N IcB cN 0bb0BcBBxB I B-1N B-1b0 cN - cBB-1N -cBB-1 -cBB-1by* = cBB-1 是 最优解此处记录了B 的逆矩阵B-1综上所述，（ P） 问题与（ D） 问题的解之间只有以下三种可能的关系：（ 1）两个问题都有可行解，从而都有最优解，分别设为 x*， y*,则必有 z* = cx* = y*b = w*；（ 2） 一个问题为无界，另一个问题必无可行解；（ 3）两个问题都无可行解。第 三 章 线性规划 的对偶理论Theorem 4 (互补松弛定理 ) 设 x* 和 y* 分别是（ P） 问题和（ D） 问题的可行解，则它们分别是（ P）、 （ D）问题的最优解的充要条件是： y* ( b Ax* ) = 0； ( y*A c ) x* = 0 同时成立 。proof因为 ， y* 0 , Ax* b , 由 y* ( b Ax* ) = 0 ， 有由 x* 0 , y*A c ， ( y*A c ) x* = 0， 有一个规划的某个约束成立严格不等式（约束条件为松），对应的对偶规划中变量取 0（变量是紧），当某个变量不为 0时（变量是松），对应的对偶规划中约束成立等式（约束条件是紧） 。 向前2 对偶问题的基本性质Theorem 4 (互补松弛定理 )proof : 必要性设 x*、 y*分别是 (P)问题和 (D)问题的最优解 .则所以由 推出于是充分性 由得又 x*、 y* 分别是 （ P） 问题和 （ D） 问题的可行解，所以 x*、 y* 分别是 （ P） 问题和 （ D） 问题的最优解。证毕2 对偶问题的基本性质二、对偶规划的求解1、利用原问题的最优单纯形表求对偶最优解的方法cBs xBsc0 xs检验数cB cN 0xB xN xsB N IcB cN 0bb0BcBBxB I B-1N B-1b0 cN - cBB-1N -cBB-1 -cBB-1bB-1第 三 章 线性规划 的对偶理论e.g. 2 求如下 LP 问题的对偶问题的最优解max z = 4x1+3x2+7x3s.t. x1+2x2+2x3 1003x1+ x2+3x3 100x1, x2, x3 0 解： 对偶问题为min w = 100y1+100y2s.t. y1+ 3y2 42y1+ y2 32y1+ 3y2 7y1, y2 0ccB xB37x2x3检验数4 3 7 0 0x1 x2 x3 x4 x5-3/4 1 0 3/45/4 0 1 -1/4-5/2 0 0 -1/2b2525-250-1/21/2-2原问题的最优解和最优值为：x*=(0,25,25)T z*=250由 推论 5可知：对偶问题的最优解和最优值为 y*= (1/2 , 2) w*= 2502 对偶问题的基本性质如果 （ P） 问题为：max z = cx(P) s.t. Ax = bx 0cBs xBsc0 xs检验数cB cN -MxB xN xRB N IcB cN -Mbb0BcBBxB I B-1N B-1 B-1b0 cN-cBB-1N -M-cBB-1 -cBB-1by*= cBB-1= -M-第 三 章 线性规划 的对偶理论2、利用互补松弛定理求对偶最优解e.g. 3 求如下 LP 问题的对偶问题的最优解max z=4x1+3x2s.t. x1+2x2 2x1-2x2 32x1+3x2 5x1+x2 23x1+x2 3x1, x2 0 解： 对偶问题为 :min w=2y1+3y2+5y3+2y4+3y5s.t. y1+ y2+2y3+ y4+3y5 42y1-2y2+3y3+ y4+ y5 3y1, y2, y3 ,y4,y5 02 对偶问题的基本性质max z=4x1+3x2s.t. x1+2x2 2 (1)x1-2x2 3 (2)(p) 2x1+3x2 5 (3)x1+x2 2 (4)3x1+x2 3 (5)x1, x2 0 可用图解法求解 （ P） 问题，得： x*=(4/5， 3/5)T z*=5min w=2y1+3y2+5y3+2y4+3y5s.t. y1+ y2+2y3+ y4+3y5 4(D) 2y1-2y2+3y3+ y4+ y5 3y1, y2, y3 ,y4,y5 0将 x* 代入（ P） 问题的约束条件，知：约束条件 (2)、 (3)、 (4)成立严格不等式由 互补松弛定理知： y2*=y3*=y4*=0 又因为 x1* ， x2* 不为零 所以 y1*+3y5* = 4 2y1*+ y5* = 3解得： y1*= y5* =1故 y*=(1,0,0,0,1) w*=5第 三 章 线性规划 的对偶理论Note: 在求解一个 LP问题时，往往需要先考虑一下，究竟是解它的原问题还是解它的对偶问题比较省事。一般来说，求解一个 LP问题的计算量，是同这个问题所包含约束条件的个数有密切关系的，如果约束条件的个数愈多，则基可行解中基变量的个数也随之增多，相应地迭代变换的计算量也愈大，根据经验，单纯形法的迭代次数大约是约束条件个数的 1 1.5倍 .因此，当 m n 则用其对偶问题求解较好。但是 ， m = 2， 不一样（见书中例）3 对偶问题的经济解释 影子价格一、影子价格的概念讨论对称形式：（ P） 问题max z = cxs.t. Ax bx 0（ D） 问题min w = ybs.t. yA cy 0 已知当（ P） 问题求得最优解 x*时，其（ D） 问题也得到最优解 y*， 且有bi 代表第 i种资源的拥有量；对偶变量 yi*的意义代表在资源最优利用条件下对单位第 i 种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价。 影子价格(shadow price)(1)由于 边际价格第 三 章 线性规划 的对偶理论e.g. 4 资源的合理利用问题资源产品 甲 乙ABC单位利润资源限制1111235 4908045max z = 5x1+4x2 s.t. x1+3x2 902x1+ x2 80(P) x1+ x2 45x1， x2 0min w = 90y1+80y2+45y3 s.t. y1+ 2y2+ y3 5 (D) 3y1+ y2+ y3 4y1， y2， y3 0cx1 x2 x3 x4 x55 4 0 0 00 0 0 -1 -3b-215cB xBx3 x1 x20 5 4 检验数0 0 1 2 -51 0 0 1 -10 1 0 -1 225 35 10x*= ( 35， 10， 25， 0， 0 )Tz*= 215y*=(0， 1， 3， 0， 0)w*=2153 对偶问题的经济解释 影子价格二、影子价格在经营管理中的应用1、影子价格能指示企业内部挖潜的方向如 e.g. 4 中 三种资源的影子价格分别为（ 0， 1， 3）重点要考虑第三种资源；2、影子价格在企业经营决策中的作用企业经营决策者可以把本企业资源的影子价格与当时的市场价格进行比较，当 第 i 种资源的影子价格价格低于市场价格时（特别是当影子价格为零时），则企业可以卖出该种资源，以获得较大的利润；反之买入。 第 三 章 线性规划 的对偶理论3、影子价格在新产品开发决策中的应用如在 e.g. 4 中 企业要生产一新产品，单件消耗三种资源的数量为 （ 2， 3， 2），则新产品的价格必须大于 02 + 13 + 32 = 9；4、利用影子价格分析现有产品价格变动对资源紧缺情况的影响如在 e.g. 4 中 产品的售价不是（ 5， 4），而是（ 5， 5），则影子价格为3 对偶问题的经济解释 影子价格5、利用影子价格分析工艺改变后对资源影响如在 e.g. 4 中 工艺过程改进后，使资源 C 能节约 2% ，则带来经济收益是 3 45 2% = 2.7Note:1、以上分析都是在最优基不变的条件下进行的；2、 影子价格虽然被定义为一种价格，但是还应对它有更为广义的理解。 如在 e.g. 4 中，增加约束条件 x1+ x2 40则 对偶变量 y4 表示什么意思？max z = 5x1+4x2 s.t. x1+3x2 902x1+ x2 80(P) x1+ x2 45x1， x2 04 对偶单纯形法一、对偶单纯形法的基本思路对偶单纯形法是根据对偶原理和单纯形法的原理而设计出来求解 LP 问题的一种方法（而不能简单地将它理解为是求解对偶问题的方法）。 原始单纯形法考察如下的 LP 问题及其对偶问题max z = cx(P) s.t. Ax = bx