线性规划和对偶问题

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

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

原问题和对偶问题的转化

例子

原问题：

对偶问题：

转化方法

1、原问题有几个约束，对偶问题就有几个变量
2、原来的约束系数矩阵转个置就是对偶问题的约束系数矩阵
3、原来的目标函数系数变对偶问题约束常量，原来的约束常量变对偶问题的目标系数
4、左边求最大，右边求最小，按照这个模板带进去就可以了 ——大佬

对偶问题的性质

在这里给出对偶问题的一些基本结论，暂不做证明
弱对偶引理：假设 x x x 和 λ λ λ 分别是线性规划的原问题和对偶问题（对称形式及非对称形式）的可行解，则 x T x ≥ λ T b x^Tx\ge λ^Tb xTx≥λTb ，即“极大值 ≤ \le ≤ 极小值”。

定理1：假设 x 0 x_0 x0​ 和 λ 0 λ_0 λ0​ 分别是原问题和对偶问题的可行解，如果 c T x 0 ≥ λ 0 T b c^Tx_0\ge λ_0^Tb cTx0​≥λ0T​b，那么 x 0 x_0 x0​ 和 λ 0 λ_0 λ0​ 分别是各自问题的最优解。

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

定理3（互补松弛条件）： x x x 和 λ λ λ 分别是原问题和对偶问题的可行解，则它们分别是各自问题的最优解的充分必要条件为
1.      ( c T − λ T A ) x = 0 2.      λ T ( A x − b ) = 0 \begin{aligned} & 1.\ \ \ \ (c^T-λ^TA)x=0 \\ & 2.\ \ \ \ λ^T(A_x-b)=0 \end{aligned} ​1.    (cT−λTA)x=02.    λT(Ax​−b)=0​