线性规划 (Linear Programming)
1 概念
在数学中，线性规划（Linear Programming，简称 LP）特指目标函数和约束条件皆为线性的最优化问题。
通常线性规划问题包含：
1）一个需要极大化的线性目标函数 \operatorname{max} \mathbf{z}（表示为 m 个决策变量 x_1, \cdots , x_m 的加权和）：
\begin{equation}\operatorname{max} \mathbf{z}=c_{1} x_{1}+c_{2} x_{2}+\ldots+c_{m} x_{m}\end{equation}
2）线性形式的问题约束，表示为 m 个决策变量满足 n 个方程约束或不等式约束：
\begin{equation}\text { s.t. }\left\{\begin{array}{l}a_{11} x_{1}+a_{12} x_{2}+\ldots+a_{1 m} x_{m} \leq b_{1} \\a_{21} x_{1}+a_{22} x_{2}+\ldots+a_{2 m} x_{m} \leq b_{2} \\\cdots \\a_{n 1} x_{1}+a_{n 2} x_{2}+\ldots+a_{n m} x_{m} \leq b_{n}\end{array}\right.\end{equation}
3）决策变量非负，表示为：
\begin{equation}x_{1}, x_{2}, \ldots, x_{m} \geq 0\end{equation}
2 标准型
描述线性规划问题最直观的形式就是标准型，通常表示为：
\begin{equation}\begin{aligned}\text{maximize} \quad &\mathbf{c}^{T} \mathbf{x} \\\text{subject to} \quad &\mathbf{A} \mathbf{x} \leq \mathbf{b}, \mathbf{x} \geq 0\end{aligned}\end{equation}
可以证明：任意线性规划的一般形式，都可以通过对目标函数取负、添加松弛变量等操作，化成标准形式。
3 对偶问题
下述例子来自维基百科，整体解释比较清晰：
一个线性规划问题（“原问题”）的对偶线性规划问题（“对偶问题”）是另一个线性规划问题，由原问题以一定方式派生而来：
- 原问题中的每个变量都变为对偶问题中的一个限制条件；
- 原问题中的每个限制条件都变为对偶问题中的一个变量；
- 原问题若是求目标函数的最大值，则对偶问题是求最小值，反之亦然。
3.1 对偶问题的构建
对于以下形式的两个线性规划问题：
| 问题甲 | 问题乙 |
|---|---|
| 最大化目标函数 \max _{x}c^{T}x=\max _{x}\sum _{i}c_{i}x_{i} | 最小化目标函数 \min _{y}b^{T}y=\min _{y}\sum _{i}b_{i}y_{i} |
n个变量 x_{1},\ldots ,x_{n}
| n个限制条件 A^{T}y\lesseqqgtr c
|
m个限制条件 Ax\lesseqqgtr b
| m个变量 y_{1},\ldots ,y_{m}
|
我们称甲、乙互为对偶问题，即：甲为乙的对偶问题，乙为甲的对偶问题。
特别地， 若所有限制条件的符号方向相同，我们有以下形式：
以下形式：
| 名称 | 问题甲 | 问题乙 |
|---|---|---|
| 对称对偶问题 | Maximize cTx 满足 Ax ≤ b, x ≥ 0 | Minimize bTy 满足 ATy ≥ c, y ≥ 0 |
| 非对称对偶问题 | Maximize cTx 满足 Ax ≤ b | Minimize bTy 满足 ATy = c, y ≥ 0 |
| Maximize cTx 满足 Ax = b, x ≥ 0 | Minimize bTy 满足 ATy ≥ c |
3.2 线性规划对偶问题
每个线性规划问题，称为原问题，都可以变换为一个对偶问题。可将“原问题”表达成矩阵形式：
\begin{equation}\begin{aligned}\text{maximize} \quad &\mathbf{c}^T \mathbf{x} \\\text{subject to} \quad &\mathbf{A}\mathbf{x} \le \mathbf{b}, \, \mathbf{x} \ge 0\end{aligned}\end{equation}
而相应的对偶问题就可以表达成以下矩阵形式：
这里用 y来作为未知向量。
4 线性规划求解
典型的线性规划求解使用单纯形法，后续再记录。
参考文献
[1] https://zh.wikipedia.org/zh-cn/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92
[2] https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html
[3] https://kirainmoe.com/blog/post/simplex-algorithm/
[4] https://zh.wikipedia.org/zh-cn/%E5%B0%8D%E5%81%B6%E7%B7%9A%E6%80%A7%E8%A6%8F%E5%8A%83