第七章 对偶问题和对偶单纯形法

第七章 对偶问题和对偶单纯形法一、问题的提出二、对偶问题和原问题的转换三、对偶规划的性质四、对偶单纯形法五、交替单纯形法一、问题的提出v原问题： a和 b产量各为多少可以使利润最大？25010C40012B30011A资源限量ba 产品设备 10050利润一、问题的提出v原 LP 模型：v Max z= 50x1+100 x2 s.t： 1x1+1x23002x1+1 x24000x1+1 x2250x1 0， x2 0一、问题的提出v若考虑将三种设备出租，如何合理确定各设备的租金 y1、 y2 、 y3 （元 /台时）？v目标函数： min z= 300y1+400 y2+250 y3v约束条件： y1+2y2 50v y1+ y2+ y3 100v y1、 y2、 y3 0一、问题的提出v这样两个线性规划问题就是一对对偶问题。v称其中一个为原问题（ LP问题），另一个为对偶问题（ DLP问题）。v由于它们内在的联系，可以根据其中一个模型，写出其对偶问题的模型。二、对偶问题和原问题的转换vLP问题和 DLP问题的关系：规范形 (LP) Max z = cT x s.t. Ax b x 0(DLP)Min f = bT ys.t. AT y cy 0二、对偶问题和原问题的转换v1、对于规范型，直接按对应关系转换v例： Max z= 20x1+ 8 x2 +6 x3 s.t： 8x1+ 3x2 +2x3 2502x1+x2 504x1+3x3 150x1 ， x2 ， x3 0v写出该线性规划问题的对偶问题。二、对偶问题和原问题的转换v则对偶问题为：vMin f=250 y1+ 50 y2 + 150 y3v s.t： 8y1+ 2y2 +4y3 20v 3y1+y2 8v 2 y1+3y3 6v y1 ， y2 ， y3 0二、对偶问题和原问题的转换v2、对于非规范形式，先化为规范形式v例： 写出线性规划模型的对偶问题vMin z= 3x1+ 4 x2 +6 x3 v s.t： x1+ 3x2 -2x3 + x4 25v 2x1+7x3 + 2x4 60v 2x1+2x2-4x3 30v x1 ， x2 ， x4 0 ， x3 无非负约束二、对偶问题和原问题的转换v首先转换为规范形vMin z= 3x1+ 4 x2 +6 x3v变为 Max(-z)= -3x1- 4 x2 -6 x3 v约束条件 x1+ 3x2 -2x3 + x4 25v等同于 x1+ 3x2 -2x3 + x4 25和v x1+ 3x2 -2x3 + x4 25联立二、对偶问题和原问题的转换v2x1+7x3 + 2x4 60可转化为v-2x1-7x3 - 2x4 - 60vx3 无非负约束，则令 x3 x3- x3vx3- x3 0v则原 LP模型可以化为规范形：二、对偶问题和原问题的转换vMax (-z)= -3x1- 4 x2 -6 x3+6 x3 v s.t： x1+ 3x2 -2 x3+2 x3 + x4 25v -x1- 3x2 +2 x3-2 x3 - x4 -25v -2x1-7 x3+ 7x3 - 2x4 -60v 2x1+2x2-4 x3+4 x3 30v x1 ,x2 ,x3, x3 ,x4 0二、对偶问题和原问题的转换v 故 DLP可写出：v Min f 25 y1-25 y2 -60 y3 +30 y4v s.t： y1- y2 -2 y3 +2y4 -3v 3y1-3y2 +2y4 -4v -2y1+2y2 -7y3 -4 y4 -6v 2y1-2y2 +7y3 +4y4 6v y1-y2 -2y3 0v y1 ， y2 ， y3 ， y4 ， y5 0二、对偶问题和原问题的转换v将 DLP模型整理可得：vMin f 25 y5+60 y3 +30 y4v s.t： y5+2 y3 +2y4 -3v 3y5+2y4 -4v -2y5+7y3 -4y4 -6v y5+2y3 0v y5 无非负约束， y3 0， y4 0LP与 DLP的一般对应关系原 问题 LP 对 偶 问题 DLP目 标 函数 maxz minf 目 标 函数变 量 xj（ j 1，2n ）n个 n个 约 束条件 j （ j 1， 2n ）0 0 无 约 束 约 束条件 i （ i1， 2m ）m个 m个 变 量 yj（ i 1，2m ） 0 0 无 约 束目 标 函数 变 量的系数cj（ j 1， 2n ）约 束条件右端 项cjT（ j 1， 2n ）约 束条件右端 项bi（ i 1， 2m ）目 标 函数 变 量的系数biT（ i 1， 2m ）练习v写出下面 LP问题的 DLP模型vMin z= x1+ 2 x2 +5 x3 v s.t： 2x1+ 3x2 +x3 10v 3x1+x2 + x3 50v x1+x3 20v x1 0 ， x2 0 ， x3 无非负约束三、对偶规划的性质v1、对称性：v对偶问题的对偶是原问题。v2、弱对偶性：v若 X是原问题（ max）的可行解， Y是对偶问题（ min）的可行解，则存在CXbTY三、对偶规划的性质v 推论 a ： 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。v 推论 b：若原问题解无界，则其对偶问题无可行解；若对偶问题解无界，则原问题无可行解。（逆命题不成立）v 推论 c：若原问题有可行解而对偶问题无可行解，则原问题无界；反之，对偶问题有可行解而原问题无可行解，则对偶问题解无界。三、对偶规划的性质v3、最优性：v若 x,y分别是原问题和对偶问题的可行解,且 cx=bTy ，那么 x,y分别为原问题和对偶问题的最优解。三、对偶规划的性质v4、强对偶性：v若原问题和对偶问题都有可行解，则两者都有最优解，且最优目标函数值相等。三、对偶规划的性质v 5、互补松弛定理：v 在原问题的最优解中，如果对应某一约束条件的对偶变量值不为 0，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为 0，即v 若 Yi*0，则有 aijxj* biv 若 aijxj*bi ，则有 Yi* 0对偶问题解的意义 若 x*,y* 分别为（ LP）和（ DLP）的最优解， 那么， cx* = bT y* 。 根据 f = bTy*=b1y1*+b2y2*+ +bmym* 可知 f / bi = yi* yi*表示 bi 变化 1个单位对目标 f 产生的影响。对偶问题解的意义 因此：对偶问题的最优解就是原问题中相应资源常数项的影子价格。 若 B是初始基在最优表中的形式，影子价格向量 Y* = BCB 确定影子价格在原问题和对偶问题中的对应关系后，可以由原问题最优单纯形表求对偶问题最优解。对偶问题解的意义v 如范例最优表：2-250-5000j=cj zj21250250507550zj2501001075x25011-2000x450-1010150x10007550比值bi/ai2bx5x4x3x2x1CB基变量 XB迭代次数对偶问题解的意义v原问题的最优解为：vx1=50 x2=250 x4=50v对偶问题的最优解为：vy1=50 y2=0 y3=50 （影子价格）四、对偶单纯形法v 最优表特征：基向量为单位向量右端项非负2-500-5000j=cj zj275005005010050zj25010010100x25011-2000x450-1010150x100010050比值bi/ai2bx5x4x3x2x1CB基变量 XB迭代次数检验数非正四、对偶单纯形法v 单纯形法的迭代： 保证基向量为单位向量保证右端项非负000010050j=cj zj0500000zj250100100x5400010120x4300001110x300010050比值bi/ai2bx5x4x3x2x1CB基变量 XB迭代次数检验数由正变为非正右端项由负变为非负保证基向量为单位向量四、对偶单纯形法v 对偶单纯形法的迭代：基 变量 XB CBx1 x2 x3 x4 x5 x6 b50 100 0 0 0 0x1 50 1 0 1 0 -1 0 50x4 0 0 0 -2 1 1 0 50x2 100 0 1 0 0 1 0 250x6 0 0 0 -10 0 -20 1 -3000zj 50 100 50 0 50 0 27500j 0 0 -50 0 -50 0 保证检验 数非正四、对偶单纯形法v 在满足对偶单纯形迭代前提条件的表上确定主行和出基变量：基 变量 XB CBx1 x2 x3 x4 x5 x6 b50 100 0 0 0 0x1 50 1 0 1 0 -1 0 50x4 0 0 0 -2 1 1 0 50x2 100 0 1 0 0 1 0 250x6 0 0 0 -10 0 -20 1 -3000zj 50 100 50 0 50 0 27500j 0 0