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 对偶问题

下述例子来自维基百科，整体解释比较清晰：
一个线性规划问题（“原问题”）的对偶线性规划问题（“对偶问题”）是另一个线性规划问题，由原问题以一定方式派生而来：

1. 原问题中的每个变量都变为对偶问题中的一个限制条件；
2. 原问题中的每个限制条件都变为对偶问题中的一个变量；
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}\) \(x_{i}\geq 0\) \(x_{j}\leq 0\) \(x_{k}\in \mathbb {R} \)	n个限制条件 \(A^{T}y\lesseqqgtr c\) 第i个限制条件为 \(\geq c_{i}\) 第j个限制条件为 \(\leq c_{j}\) 第k个限制条件为 \(=c_{k}\)
m个限制条件 \(Ax\lesseqqgtr b\) 第i个限制条件为 \(\geq b_{i}\) 第j个限制条件为 \(\leq b_{j}\) 第k个限制条件为 \(=b_{k}\)	m个变量 \(y_{1},\ldots ,y_{m}\) \(y_{i}\leq 0\) \(y_{j}\geq 0\) \(y_{k}\in \mathbb {R} \)

我们称甲、乙互为对偶问题，即：甲为乙的对偶问题，乙为甲的对偶问题。
特别地， 若所有限制条件的符号方向相同，我们有以下形式：

以下形式：

名称	问题甲	问题乙
对称对偶问题	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}
\)
而相应的对偶问题就可以表达成以下矩阵形式：

\(\begin{equation}
\begin{aligned}
\text{maximize} \quad &\mathbf{y}^T \mathbf{b} \\
\text{subject to} \quad &\mathbf{y}^T \mathbf{A} \ge \mathbf{c}^T, \, \mathbf{y} \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