对于一个线性规划问题，若其有最优解，那么其对偶问题也有最优解，且最优值相等。
如果对于一个困难的线性规划问题，其对偶形式比较简单，此时就可以通过线性规划对偶，解决其对偶问题，从而解决原问题。
线性规划的原问题与对偶问题的变化规则：
对于一个标准型线性规划：
\[\max \quad C^Tx\\ s.t. \quad Ax\le B\\ x\ge 0 \]其对偶线性规划为：
\[\min \quad B^Ty\\ s.t. \quad A^Ty\ge C\\ y\ge 0 \]这里还有一张表格，可以应对更一般的线性规划对偶：
| 原问题（或对偶问题） | 对偶问题（或原问题） |
|---|---|
| 目标函数 \(\max X\) | 目标函数 \(\min Y\) |
| 变量 \(\begin{cases}n\ 个 \\ \ge 0 \\ \le 0 \\ 无约束\end{cases}\) | 约束条件 \(\begin{cases}n\ 个 \\ \ge \\ \le \\ =\end{cases}\) |
| 约束条件 \(\begin{cases}m\ 个 \\ \le \\ \ge \\ =\end{cases}\) | 变量 \(\begin{cases}m\ 个 \\ \ge 0 \\ \le 0 \\ 无约束\end{cases}\) |
例 \(1\)：求下列线性规划问题的对偶问题。
\[\min X=2x_1+3x_2-5x_3+x_4 \]\[\begin{cases}x_1+x_2-3x_3+x_4\ge 5\\2x_1+2x_3-x_4\le 4\\x_2+x_3+x_4=6\\x_1\le 0\\x_2,x_3\ge 0\\x_4\ 无约束\end{cases} \]解 \(1\)：
将 \(\min X\) 变为 \(\max Y\)，设 \(3\) 个变量 \(y_1,y_2,y_3\) 分别对应 \(3\) 条限制，一共 \(4\) 条限制对应 \(4\) 个变量，并且将限制中的常量与目标函数中的系数互换。
\[\max Y = 5 y_1 + 4 y_2 + 6 y_3 \]\[\begin{cases}y_1+2y_2\ge 2\\y_1+y_3\le 3\\-3y_1+2y_2+y_3\le -5\\y_1-y_2+y_3=1\\y_1\ge 0\\y_2\le 0\\y_3\ 无约束\end{cases} \] 标签：le,end,线性规划,笔记,ge,cases,对偶 From： https://www.cnblogs.com/FidoPuppy/p/18241241