本文共 800 字，大约阅读时间需要 2 分钟。

线性规划和对偶问题

任一线性规划问题都存在另一与之伴随的线性规划问题，它们组成一对互为对偶的线性规划问题。

线性规划的对偶问题与原问题互为对偶，线性规划的原问题与对偶问题地位具有对称关系。

原问题和对偶问题的转化

例子

原问题：

对偶问题：

转化方法

1、原问题有几个约束，对偶问题就有几个变量

对偶问题的性质

在这里给出对偶问题的一些基本结论，暂不做证明

定理1：假设 $x_0$ 和 ${\lambda }_0$ 分别是原问题和对偶问题的可行解，如果 $c^T{x}_0\ge {\lambda }_0^{T}b$，那么 $x_0$ 和 ${\lambda }_0$ 分别是各自问题的最优解。

定理2（对偶定理）：如果原问题有最优解，那么其对偶问题也有最优解，并且它们目标函数的最优解相同。

定理3（互补松弛条件）：$x$ 和 $\lambda$ 分别是原问题和对偶问题的可行解，则它们分别是各自问题的最优解的充分必要条件为