线性规划 (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 对偶问题

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

  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 ≤ bx ≥ 0 Minimize bTy 满足 ATy ≥ cy ≥ 0
非对称对偶问题 Maximize cTx 满足 Ax ≤ b Minimize bTy 满足 ATy = cy ≥ 0
Maximize cTx 满足 Ax = bx ≥ 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

Add a Comment

您的电子邮箱地址不会被公开。 必填项已用*标注