2.2对偶问题的基本性质.ppt

4.1 对偶模型的提出 4.2 原模型与对偶模型的线性规划模型之 间的关系 4.3 对偶模型的基本性质 4.4 对偶模型的经济意义——影子价格 4.5 对偶模型最优解和影子价格 4.6 对偶单纯形法 设生产A、B产品数分别为x1、x2，则数学模型为 4.3 对偶模型的基本性质 对称性 弱对偶性 最优解性 强对偶性（对偶定理） 互补松弛性 （1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。 （2）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。 原问题与对偶问题的解和目标函数值之间的关系 4.5.2 影子价格 1．在一般线性规划模型中，并非所有的约束都是资源约束（如产量约束,这样的约束也有影子价格即销售量对利润的贡献），但每个约束条件对应的对偶解分量yi﹡都可以解释为目标最优值z﹡对右端项bi的变化率，即bi增加一个单位时z﹡的改变量。由于yi﹡的符号可为正，也可为负，故随着bi的增加，z﹡可能增加，也可能减少。 2．大多数的计算机软件(包括本书所用到的QM)沿用如下的输出惯例：打印输出的影子价格是当右端项增加时目标最优值的改进率而不是变化率。改进的意思在最大化模型中是增加，在最小化模型中则是减少；正的改进率使前者的目标最优值增加，使后者的目标最优值减少；而负的改进率将使目标最优值受到“损害”，故它的作用正好相反。 对偶问题 X（0）=（0，0，0）T是原问题的一个可行解 原问题 对偶问题不可行 若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。 y1≥0， y2≥0， 不满足该约束条件 性质3??最优性 设 是原问题的可行解， 是对偶问题的可行 解，当 时， 是最优解。 利用弱对偶定理 同理可知, 也是最优解. 对任何可行解，均有 ，故 是目标函数取值最小的可行解，因而是最优解。 性质4 强对偶性（对偶定理） 若原问题有最优解，则对偶问题也有最优解，且目标函数最优值相等。 证：设 是原问题的最优解 ，它对应的基矩阵必存 在 ，即得到 若这时 是对偶问题的可行解，它使 因原问题的最优解 使目标函数取值 由此得到 可见 是对偶问题的最优解。 Z * =W * 最优解 无可行解 无界解 最优解 无界解 无可行解 目标函数 对偶问题 关系 原问题 性质5 互补松弛性 设X*和Y*分别原问题和对偶问题的可行解，那么 Y*XS*=0和 YS*X*=0 ，当且仅当X*，Y*是最优解。 AX*≤ b AX*+XS*= b XS* =b-AX* Y*（b-AX*)=0 Y*XS*=0 充分必要条件 Y*（b-AX*)=0 (Y*A-C)X*=0 对偶变量不为0，原问题相应约束式是等式 原问题约束为不等式，相应对偶变量为0 最优解点 已知线性规划问题 【例4-5】 已知线性规划模型 （1）写出该模型的对偶模型 （2）已知原模型的最优解为：X=（2，2，4，0）T 根据对偶理论，直接求对偶模型的最优解。 （1）对偶模型是： （2）已知原模型的最优解为：X=（2，2，4，0）T 根据对偶理论，直接求对偶模型的最优解。 （2）根据原模型的最优解为X=（2，2，4，0）T 将其代入原问题的约束条件，得原模型的松弛变量： x5=0，x6=0，x7=1，x8=0 约束条件 (3) 为严格不等式，由互补松弛定理知：y3*=0 由原模型的最优解为X=（2，2，4，0）T ，根据互补松弛定理知： y5=0，y6=0，y7=0， 求解上面的方程组得：y1*=4/5 ， y2*=3/5 ， y3*=0, y4* =1 设对偶模型的剩余变量为y5，y6，y7，y8， 当某约束条件的右端常数增加一个单位时（假设原问题的最优基不变），原问题的目标函数最优值增加的数量。 目标函数Z=CBB-1b和检验数CN-CBB-1N中都有乘子Y=CBB-1,Y的经济意义？