对偶线性规划
数学术语
每个线性规划问题都有一个与之对应的对偶问题。对偶问题是以原问题的约束条件和目标函数为基础构造而来的。对偶问题也是一个线性规划问题,因此可以采用单纯形法求解。对偶问题的最优解也可以通过原问题的最优解得到,反之亦然。而且,在某些情况下,利用对偶理论求解线性规划问题更为简单,而且有助于深入了解待求问题的本质。
信息介绍
每个线性规划问题都有一个与之对应的对偶问题。对偶问题是以原问题的约束条件和目标函数为基础构造而来的。对偶问题也是一个线性规划问题,因此可以采用单纯形法求解。对偶问题的最优解也可以通过原问题的最优解得到,反之亦然。而且,在某些情况下,利用对偶理论求解线性规划问题更为简单,而且有助于深入了解待求问题的本质。
对偶线性规划的经济背景是:若原问题是利用有限资源安排最优生产方案,以获得最大总产值的线性规划问题,则它的对偶问题就是在相同资源的条件下,正确估计资源的使用价值,以达到支付最少费用的线性规划问题.简言之,若原问题为求解资源的最优配置问题,则对偶问题就是求解估价资源的使用价值问题。
基本性质
原始线性规划与对偶线性规划问题不仅在数学模型的形式上存在着相互对应的关系,而且它们的目标函数、可行解及最优解之间也存在着确定的联系。
设有一对线性规划问题为:
(1)原始问题
满足
(2)对偶问题
满足
定理:互为对偶的线性规划(1)和(2)有最优解的充分必要条件是它们同时有可行解。
证明:必要性是显然的,下面来证明充分性。
设是(1)的可行解,是(2)的可行解。
则有
若是(1)的任意一个可行解,则有
成立。用左乘式子,得
用右乘不等式的两边,得
由和两个式子,得
上式说明原始问题(1)的目标函数在可行解集合上有上界,所以(1)有最优解。
设是(2)的任意一个可行解,用同样的推理方法可得
上式表示对偶问题(2)的目标函数在可行解集合上有下界,所以(2)有最优解。证明完毕。
参考资料
最新修订时间:2023-01-07 20:29
目录
概述
信息介绍
基本性质
参考资料