管理运筹学讲义 第2章 对偶规划详解.ppt

第2章 对偶规划 原问题与对偶问题之间的对应规律见表 把LP看作一个使收益最大的生产计划问题，其中的技术约束看作资源约束，那么对偶问题的最优解y1*，y2*，…ym*分别称为m种资源的影子价格。下面将会看到，它与原问题最优解有密切关系，并在经济管理中有重要的作用。 写出下列LP的对偶问题： (1) (2) 解: 首先把问题改写为对称形式，再求它的对偶问题。 式（1）两边乘以（－1），成为－2x1+x2≤－1 把式（2）拆成两个不等式： x1+3x2≤5 －x1－3x2≤－5 然后令x1=－x1，x1≥0；令x2= x2－x2，x2≥0，x2≥0；把原问题变换为等价模型： 它的对偶模型是（假定对偶变量为y1，y2，y3） (a) (b) (c) 将（a）两边乘（－1），把（b）与（c）合并成一个等式，约束条件变为： 再令y1=－y1‘，y1≤0；令y2=y2’－y3‘，y2无符号约束，最后对偶问题成为： DP模型与原问题LP模型之间，对应规律表中（2）、（4）、（5）、（6）各项对应规律仍然成立，而（1）、（3）两项有所变动。仔细分析上述推导过程可以发现，如原问题的变量xj无符号约束，则对偶技术约束为等式；如xj≤0，则对偶技术约束的不等号要反向（由≥变为≤）；如原问题某个技术约束为等式，则对偶变量无符号约束；如原问题的某个技术约束不等式反向（由≤改为≥），则对偶变量≤0。总结这些规律，现将一般情形下对偶问题之间的对应规律，汇集在下表中。 为了便于记忆对偶约束之间的对应规律，约定下列术语。在求max值的LP中，把问题设想为合理利用某些资源以实现收益最大的模型，它的技术约束一般表示资源限制，通常为≤型的，称为正向约束；反之，如某个技术约束为≥型，则称为反向的；若约束为=型的，则称为双向的。对于求min值的LP，把问题设想为利用某些原料配制一种产品，使得成本最低的模型。这时技术约束一般表示质量要求，往往是≥型的，因此称为正向的；如某个技术约束为≤型的，则称为反向的；如约束为=型的，则称为双向的。 就变量的符号约束来说，总是把非负约束称为正向的，非正约束称为反向的，符号无约束称为双向的。 采用这些术语，对偶约束之间的对应规律可用一句话来概括：一个问题中的正向（或反号，或双向）技术约束，对应于另一个问题的正向（或反向，或双向）变量符号约束，即两个对偶约束，总属于同样的类型。利用这个规律，可以很容易地写出任意线性规划的对偶规划。 解: 原问题求min，对偶问题目标函数应求max，原问题三个技术约束分别为反向，正向，双向的，对偶变量约束分别为y1≤0，y2≥0，y3无约束；x1，x2，x3，x4的符号约束分别为正向，正向，反向，双向的，对偶技术约束分别为≤型，≤型，≥型与=型，从而可得对偶线性规划为： 推论1：原问题任一可行解的目标函数值是对偶问题函数值的下界；对偶问题的任一可行解的目标函数值是其原问题目标函数值的上界。 定理3（最优性判定定理） 设 ， 分别为问题L与D的可行解，且 ，则两者均为最优解。 证: 设X*是L的最优解，则 。由定理2，可得 ，但 ，故必有 ，从而 是L的最优解。同理可证 是D的最优解。 定理4（强对偶定理） 如果原问题有最优解，那么对偶问题也有最优解；设前者的最优基为B，则对偶最优解为Y*=CBB－1，且两者最优值相等。 定理5：互补松弛定理 在LP的最优解中，如果对应某一约束条件的对偶变量值非零，则该约束条件取严格等式。反之，如果约束条件取严格不等式，则对应的对偶变量一定为零。 即：若 则