LP = 线性目标 + 线性约束
标准形式：在 \(A\mathbf{x} \le \mathbf{b}\)、\(\mathbf{x} \ge \mathbf{0}\) 的约束下最小化 \(\mathbf{c}^T\mathbf{x}\)。
18.06 · 第 31 课
在线性约束下求线性目标的最优值——这就是线性规划（linear programming）。可行域是凸多面体，最优解在顶点达到。对偶理论与 Farkas 引理揭示了约束与目标之间的深层对称。
线性规划问题由三部分组成：
完整写出来：
\[\begin{aligned} \min_{\mathbf{x}} \quad & \mathbf{c}^T \mathbf{x} \\ \text{s.t.} \quad & A \mathbf{x} \le \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{aligned}\]其中 \(A\) 是 \(m \times n\) 矩阵，\(\mathbf{b} \in \mathbb{R}^m\)，\(\mathbf{c} \in \mathbb{R}^n\)。
满足所有约束的 \(\mathbf{x}\) 构成可行域（feasible region）。每个不等式约束定义一个半空间，多个半空间的交集是一个凸多面体（convex polyhedron）。
凸性意味着：如果 \(\mathbf{x}\) 和 \(\mathbf{y}\) 都可行，则它们的任意凸组合 \(t\mathbf{x} + (1-t)\mathbf{y}\)（\(0 \le t \le 1\)）也可行。
关键定理：线性规划的最优解（如果存在）一定在多面体的某个顶点（vertex）处达到。这是单纯形法（simplex method）的理论基础——只需在顶点之间搜索。
顶点的代数描述：顶点是 \(n\) 个约束取等号（active constraints）的交点，且该点满足其余所有约束。每个顶点对应一个基可行解（basic feasible solution）。
每个线性规划问题（称为原问题，primal）对应一个对偶问题（dual）。对偶问题从约束中构造新的变量，给出原问题最优值的界。
原问题（最小化）：
\[\min \{\mathbf{c}^T \mathbf{x} : A\mathbf{x} \ge \mathbf{b},\; \mathbf{x} \ge \mathbf{0}\}\]对偶问题（最大化）：
\[\max \{\mathbf{b}^T \mathbf{y} : A^T \mathbf{y} \le \mathbf{c},\; \mathbf{y} \ge \mathbf{0}\}\]弱对偶定理：对偶问题的任何可行解 \(\mathbf{y}\) 给出原问题最优值的下界：\(\mathbf{c}^T \mathbf{x} \ge \mathbf{b}^T \mathbf{y}\)。
强对偶定理：如果原问题和对偶问题都有可行解，则它们的最优值相等。
Farkas 引理（Farkas' lemma）是线性规划对偶理论的基石。它给出一个线性系统有解的充要条件：
Farkas 引理：恰好下列两个命题之一成立：
几何含义：要么 \(\mathbf{b}\) 在 \(A\) 的列向量生成的锥（cone）内，要么存在一个超平面严格分离 \(\mathbf{b}\) 与该锥——两者必居其一。
问题 1：线性规划的最优解（如果存在）一定在哪里达到？
问题 2：线性规划的可行域是什么几何对象？
问题 3：关于线性规划的对偶性，下列哪项正确？
问题 4：Farkas 引理的核心内容是什么？
标准形式：在 \(A\mathbf{x} \le \mathbf{b}\)、\(\mathbf{x} \ge \mathbf{0}\) 的约束下最小化 \(\mathbf{c}^T\mathbf{x}\)。
半空间的交集构成凸多面体，最优解在顶点（基可行解）处达到。
弱对偶：对偶可行解给出下界；强对偶：若两者都可行则最优值相等。
要么线性系统有非负解，要么存在分离超平面——这是对偶理论的基石。
lecture_slides/lecture_34.pdf