对偶线性规划

从拉格朗日乘子法出发，找原线性规划的对偶线性规划（罚函数的思想）

①将非平凡约束转化为惩罚项，先暂时保留平凡约束，构造拉格朗日函数（与原函数的优化方向相同）
例子如下：
对偶线性规划
②每给定一个 $p$ ，就可以得到松弛问题的一个最优解 $g(p)$

③由于在松弛问题中 $p(b-AX)$ 可以 $\leq 0$ ，因此原问题最佳解 $x^*$ 也必定是松弛问题的可行解，即：

上式表明：任意给定一个 $p$ ，松弛问题的最佳值 $g(p)$ 都是原问题最佳值 $cx^*$ 的下界。
因此，求解 $\mathop{max}\limits_{p}[g(p)]$ 等价于求解原问题的最佳值

④从求 $\mathop{max}\limits_{p}[g(p)]$ ，将原线性规划转化为对偶线性规划

额外说明

关于对偶线性规划平凡约束的确定方法
即如何确定 $p$ 值，才能在松弛问题中体现出惩罚的含义，例如：

从拉格朗日乘子法出发，找原线性规划的对偶线性规划（罚函数的思想）

额外说明

相关推荐