线性规划基础
线性规划指的是目标函数以及约束条件都是线性函数时的最优化问题。对于最一般的情况，我们可以用如下的形式刻画要解决的问题：
- 目标函数： $c(x_1, \cdots, x_n)=\sum_{j=1}^n c_j x_j$，我们想要最大化（或者最小化也可以）它，这里 $c_i$ 可正可负。
- 约束条件： $\sum_{j=1}^n a_{ij}x_j\le b_i$ （当然，$\ge$ 或者 $=$ 也是可以的，它们都可以用 $\le$ 表示）。有 $m$ 条约束条件（$a$ 的下标就是这么来的）。
- 对于变量的非负性约束：有些 $x_i$ 可以随便取，但是有些 $x_i$ 不能小于 $0$。（其实规定所有变量必须不低于 $0$ 是等价的）
这个模型有些复杂，它可以被规约到一个难度完全相同，但是表达形式更简单的问题。我们称这种最简形式为标准型：
- 目标函数：$c(x_1, \cdots, x_n)=\sum_{j=1}^n c_jx_j$，我们想要最大化它。
- 约束条件：$\sum_{j=1}^n a_{ij}x_j=b_i$。（全部改成 $\le$ 则被称作松弛型线性规划）
- 对于变量的非负性约束：$\forall i, x_i\ge 0$。
之后将系数 $a_{ij}$ 合并为矩阵 $\mathbf A\in M_{m\times n}$，将目标函数的系数合并为列向量 $\mathbf c=(c_1, \cdots, c_n)^\top$