1 线性规划

线性规划(Linear Programming, LP) 属于运筹学之下的数学规划分支中的一个重要分支。

解决的问题：在实际的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。

总而言之，线性规划问题是在一组线性约束条件的限制下，通过调整决策变量的取值，求得一线性目标函数最大或最小的问题。

理论基础

详见算法导论-第29章 线性规划

计算机求解

Matlab 求解

Matlab 标准形式

Matlab 中，线性规划问题的标准形式为：

\[ \begin{array}{l}\displaystyle \min _x \quad \boldsymbol{f}^\mathrm{T}\boldsymbol{x} \,, \\ \text{s.t.} \left\{ \begin{array}{l} \boldsymbol{A} \cdot \boldsymbol{x} \leqslant \boldsymbol{b} \,, \\ \text{Aeq} \cdot \boldsymbol{x} = \text{beq} \,, \\ \text{lb} \leqslant \boldsymbol{x} \leqslant \text{ub} \,. \end{array} \right. \end{array} \]

其中：

• \(\boldsymbol{f},\boldsymbol{x},\boldsymbol{b},\text{beq},\text{lb},\text{ub}\) 为列向量
  • \(\boldsymbol{f}\) 称为价值向量
  • \(\boldsymbol{x}\) 称为决策向量
  • \(\boldsymbol{b}\) 称为资源向量
• \(\boldsymbol{A},\text{Aeq}\) 为矩阵

linprog 函数

[x, fval] = linprog(f, A, b)
[x, fval] = linprog(f, A, b, Aeq, beq)
[x, fval] = linprog(f, A, b, Aeq, beq, lb, ub)

其中：

• 输入值
  • f 为目标函数的系数向量（求最小值形式下的）
  • A 和 b 对应线性不等式约束
  • Aeq 和 beq 对应线性等式约束
  • lb 和 ub 对应决策向量的下界向量和上界向量
• 返回值
  • x 返回决策向量的取值
  • fval 返回目标函数的最优值

当线性规划不是 Matlab 标准形式时，需要将其转换为 Matlab 标准形式再进行求解。

例如：

\[ \begin{array}{l}\displaystyle \max _x \quad \boldsymbol{c}^\mathrm{T}\boldsymbol{x} \,, \\ \text{s.t.} \quad \boldsymbol{A}\boldsymbol{x} \geqslant \boldsymbol{b} \,. \end{array} \]

需要转化为

\[ \begin{array}{l}\displaystyle \min _x \quad -\boldsymbol{c}^\mathrm{T}\boldsymbol{x} \,, \\ \text{s.t.} \quad -\boldsymbol{A}\boldsymbol{x} \leqslant -\boldsymbol{b} \,. \end{array} \]

求解示例

例

求解下列线性规划问题：

\[ \begin{array}{l} \max \quad z = 2x_1 + 3x_2 - 5x_3 \,, \\ \text{s.t.} \quad \left\{ \begin{array}{l} x_1 + x_2 + x_3 = 7 \,, \\ 2x_1 - 5x_2 + x_3 \geqslant 10 \,, \\ x_1 + 3x_2 + x_3 \leqslant 12 \,, \\ x_1, x_2, x_3 \geqslant 0 \,. \end{array} \right. \end{array} \]

解：

1. 转换为 Matlab 标准形式：

   \[ \begin{array}{l}\displaystyle \min _x \quad w = -2x_1 - 3x_2 + 5x_3 \,, \\ \text{s.t.} \quad \left\{ \begin{array}{l} \begin{bmatrix} -2 & 5 & -1 \\ 1 & 3 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} \leqslant \begin{bmatrix} -10 \\ 12 \end{bmatrix} \,, \\ \left[1, 1, 1\right]\cdot\left[x_1, x_2, x_3\right]^\mathrm{T} = 7 \,, \\ \left[x_1, x_2, x_3\right]^\mathrm{T} \geqslant \left[0, 0, 0\right]^\mathrm{T} \,. \end{array} \right. \end{array} \]

2. 求解的 Matlab 代码：

   f = [-2; -3; 5];
   A = [-2, 5, -1; 1, 3, 1];
   b = [-10; 12];
   Aeq = [1, 1, 1];
   beq = 7;
   lb = [0; 0; 0];
   [x, y] = linprog(f, A, b, Aeq, lb)
   x, y = -y
   

   求得最优解 \(x_1 = 6.4286\)，\(x_2 = 0.5714\)，\(x_3 = 0\)，对应最优值 \(z = 14.5714\)。

Python 求解

使用 Python 的 SciPy 库进行计算。

标准形式

Python 中，线性规划问题的标准形式为：

\[ \begin{array}{l}\displaystyle \min _x \quad \boldsymbol{c}^\mathrm{T}\boldsymbol{x} \,, \\ \text{s.t.} \left\{ \begin{array}{l} \text{A\_ub} \cdot \boldsymbol{x} \leqslant \text{b\_ub} \,, \\ \text{A\_eq} \cdot \boldsymbol{x} = \text{b\_eq} \,, \\ \boldsymbol{x} \in \text{bounds} \,. \end{array} \right. \end{array} \]

scipy.optimize 中的 linprog 函数

result = linprog(c, A_ub, b_ub, A_eq, b_eq, bounds, method)

• 参数
  • c 为目标函数的系数向量（求最小值形式下的）
  • A_ub 和 b_ub 对应线性不等式约束
  • A_eq 和 b_eq 对应线性等式约束
  • bounds 为表示决策变量定义域的 \(n\times 2\) 矩阵，None 表示无穷
  • method 为求解方法，默认为 highs
• 返回值
  • result 有多个参数，通过 . 运算符访问
    • x 为最优解向量
    • fun 为目标函数的最优值（min）
    • nit 迭代次数
    • ……

求解示例

例

求解下列线性规划问题：

\[ \begin{array}{l} \max \quad z = 2x_1 + 3x_2 - 5x_3 \,, \\ \text{s.t.} \quad \left\{ \begin{array}{l} x_1 + x_2 + x_3 = 7 \,, \\ 2x_1 - 5x_2 + x_3 \geqslant 10 \,, \\ x_1 + 3x_2 + x_3 \leqslant 12 \,, \\ x_1, x_2, x_3 \geqslant 0 \,. \end{array} \right. \end{array} \]

代码：

from scipy.optimize import linprog
import numpy as np
# 系数向量
c = np.array([-2, -3, 5])
# 线性不等式约束
A_ub = np.array(
    [
        [-2, 5, -1],
        [1, 3, 1],
    ]
)
b_ub = np.array([-10, 12])
# 线性等式约束
A_eq = np.array(
    [
        [1, 1, 1],
    ]
)
b_eq = np.array([7])
# 决策变量的上下界
bounds = np.array([[0, None], [0, None], [0, None]])
# 调用线性规划函数求解
result = linprog(c, A_ub, b_ub, A_eq, b_eq, bounds)
# print(result)
# 由于求的是最大值，需要取负
y = -result.fun
print(f"最大值：{y}\n最优解：{result.x}")

可转化为线性规划的问题

目标函数决策变量均加绝对值

问题

\[ \begin{array}{c} \min \quad \boldsymbol{f}^\mathrm{T}\left[\,|x_1|, |x_2|, \cdots, |x_n|\,\right] \,, \\ \text{s.t.} \quad \boldsymbol{Ax} \leqslant \boldsymbol{b} \,. \end{array} \]

其中，\(\boldsymbol{x} = \left[ x_1, x_2, \cdots, x_n \right]^\mathrm{T}\)，\(\boldsymbol{A}\) 为 \(m \times n\) 矩阵，\(\boldsymbol{b}\) 为 \(m\) 维向量。

将其转变为线性规划问题，关键在于以下事实：

对于任意的 \(x_i\)，均存在 \(u_i, v_i \geqslant 0\) 满足

\[ x_i = u_i - v_i \,, |x_i| = u_i + v_i \,. \]

反解出 \(\displaystyle u_i = \frac{|x_i| + x_i}{2}, v_i = \frac{|x_i| - x_i}{2}\)，就可以满足 \(u_i, v_i \geqslant 0\)。

记 \(\boldsymbol{u} = [ u_1, \ldots, u_n ]^\mathrm{T} , \boldsymbol{v} = [ v_1, \ldots, v_n ]^\mathrm{T}\)，就可以将上面的数学规划问题转变为线性规划问题：

\[ \begin{array}{l} \min \quad \boldsymbol{f}^\mathrm{T} (\boldsymbol{u} + \boldsymbol{v}) \,, \\ \text{s.t.} \quad \left\{ \begin{array}{l} \boldsymbol{A}(\boldsymbol{u} - \boldsymbol{v}) = [\boldsymbol{A}, -\boldsymbol{A}] \begin{bmatrix} \boldsymbol{u} \\ \boldsymbol{v} \end{bmatrix} \leqslant \boldsymbol{b} \,, \\ \boldsymbol{u}, \boldsymbol{v} \geqslant 0 \,. \end{array} \right. \end{array} \]

可令 \(\boldsymbol{y} = \begin{bmatrix}\boldsymbol{u}\\\boldsymbol{v}\end{bmatrix}\)，进一步化简得到

\[ \begin{array}{l} \min \quad \boldsymbol{f}^\mathrm{T} (\boldsymbol{u} + \boldsymbol{v}) = [\boldsymbol{f}^\mathrm{T},\boldsymbol{f}^\mathrm{T}]\,\boldsymbol{y} \,, \\ \text{s.t.} \quad \left\{ \begin{array}{l} [\boldsymbol{A}, -\boldsymbol{A}] \boldsymbol{y} \leqslant \boldsymbol{b} \,, \\ \boldsymbol{u}, \boldsymbol{v} \geqslant 0 \,. \end{array} \right. \end{array} \]

例

求下列数学规划问题：

\[ \begin{array}{l} \min \quad z = |x_1| + 2|x_2| + 3|x_3| + 4|x_4| \,, \\ \text{s.t.} \quad \left\{ \begin{array}{l} x_1 - x_2 - x_3 + x_4 \leqslant -2 \,, \\ x_1 - x_2 + x_3 - 3x_4 \leqslant -1 \,, \\ x_1 - x_2 - 2x_3 + 3x_4 \leqslant -\dfrac{1}{2} \,. \end{array} \right. \end{array} \]

解：

1. 转化为线性规划问题： 做变换 \(u_i = \dfrac{|x_i| + x_i}{2}\)，\(v_i = \dfrac{|x_i| - x_i}{2}\)，\(i=1,2,3,4\)，并令 \(\boldsymbol{y} = \begin{bmatrix}\boldsymbol{u}\\\boldsymbol{v}\end{bmatrix}\)，得到

   \[ \begin{array}{l} \min \quad \boldsymbol{c}^\mathrm{T} \boldsymbol{y} \,, \\ \text{s.t.} \quad \left\{ \begin{array}{l} [\boldsymbol{A}, -\boldsymbol{A}] \begin{bmatrix} \boldsymbol{u}\\\boldsymbol{v} \end{bmatrix} \leqslant \boldsymbol{b} \,, \\ \boldsymbol{y} \geqslant 0 \,. \end{array} \right. \end{array} \]

   其中

   \[ \begin{array}{l} \boldsymbol{c} = [1, 2, 3, 4, 1, 2, 3, 4]^\mathrm{T} \,, \\ \boldsymbol{A} = \begin{bmatrix} 1 & -1 & -1 & 1 \\ 1 & -1 & 1 & -3 \\ 1 & -1 & -2 & 3 \end{bmatrix} \,, \\ \boldsymbol{b} = \left[-2, -1, -\dfrac{1}{2}\right]^\mathrm{T} \,. \end{array} \]

2. 求解的 Matlab 代码：

   c = 1:4; c = [c, c]';
   A = [1, -1, -1, 1; 1, -1, 1, -3; 1, -1, -2, 3];
   A = [A, -A];
   b = [-2, -1, -1/2]';
   [y, z] = linprog(c, A, b, [], [], zeros(8, 1))
   x = y(1:4) - y(5:end)
   

   求得最优解 \(x_1 = -2\)，\(x_2 = x_3 = x_4 = 0\)，对应最优值 \(z = 2\)。

min-max 问题

这个问题主要是要搞清楚决策变量是什么。

\[ \min_{x_i} \{\max_{y_i} \left|\varepsilon _i\right| \}\texttt{，其中} \, \varepsilon _i = x_i - y_i \]

这个问题，如果取 \(\displaystyle z = \max _{y_i} |\varepsilon _i|\)，则有 \(|x_i - y_i| \leqslant z\)，即 \(-z \leqslant x_i - y_i \leqslant z\) 可以转化为下面的问题：

\[ \begin{array}{l} \min \quad z \,, \\ \text{s.t.} \left\{ \begin{array}{l} x_1 - y_1 \leqslant z, \ldots, \, x_n - y_n \leqslant z \,, \\ y_1 - x_1 \leqslant z, \ldots, \, y_n - x_n \leqslant z \,. \end{array} \right. \end{array} \]

稍微整理一下形式，得到

\[ \begin{array}{l} \min \quad z \,, \\ \text{s.t.} \left\{ \begin{array}{l} x_1 - z \leqslant y_1, \ldots, \, x_n - z \leqslant y_n \,, \\ - x_1 - z \leqslant -y_1, \ldots, \, - x_n - z \leqslant -y_n \,. \end{array} \right. \end{array} \]

这就是一个线性规划问题了。其中，决策变量为 \(x_1, \ldots, x_n, z\)，而 \(y_1, \ldots, y_n\) 不是决策变量。

若写成矩阵形式：

\[ \begin{array}{l}\displaystyle \min _x \quad \boldsymbol{f}^\mathrm{T}\boldsymbol{u} \,, \\ \text{s.t.} \left\{ \begin{array}{l} \boldsymbol{A} \cdot \boldsymbol{u} \leqslant \boldsymbol{b} \,, \\ \text{lb} \leqslant \boldsymbol{u} \leqslant \text{ub} \,. \end{array} \right. \end{array} \]

其中，\(\text{lb}\) 和 \(\text{ub}\) 是可能的决策变量的下界和上界，以及

\[ \begin{array}{l} \boldsymbol{u} = \left[ x_1, \ldots, x_n, z \right]^\mathrm{T} \,, \\ \boldsymbol{f} = [ \overbrace{0, \ldots, 0}^\text{n个0} , 1]^\mathrm{T} \,, \\ \boldsymbol{b} = \left[ y_1, \ldots, y_n, -y_1, \ldots, -y_n \right]^\mathrm{T} \,, \\ \boldsymbol{A} = \begin{bmatrix} 1 & 0 & \cdots & 0 & -1 \\ 0 & 1 & \cdots & 0 & -1 \\ \vdots & \vdots & \ddots & \vdots & -1 \\ 0 & 0 & \cdots & 1 & -1 \\ -1 & 0 & \cdots & 0 & -1 \\ 0 & -1 & \cdots & 0 & -1 \\ \vdots & \vdots & \ddots & \vdots & -1 \\ 0 & 0 & \cdots & -1 & -1 \end{bmatrix} . \end{array} \]

实际问题

投资的收益与风险

问题描述

市场上有 \(n\) 种资产 \(s_{i}(i=1,2,\cdots ,n)\) 可以选择，现用数额为 \(M\) 的相当大的资金作一个时期的投资。这 \(n\) 种资产在这一时期内购买 \(s_{i}\) 的平均收益率为 \(r_{i}\)，风险损失率为 \(q_{i}\)，投资越分散，总的风险越少，总体风险可用投资的 \(s_{i}\) 中最大的一个风险来度量。

购买 \(s_{i}\) 时要付交易费，费率为 \(p_{i}\)，当购买额不超过给定值 \(u_{i}\) 时，交易费按购买 \(u_{i}\) 计算。另外，假定同期银行存款利率是 \(r_{0}\)，既无交易费又无风险（\(r_{0}=5\%\)）。

已知 \(n=4\) 时相关数据如表 1.1 所列。

表 1.1 投资的相关数据

资产	\(r_i/\%\)	\(q_i/\%\)	\(p_i/\%\)	\(u_i/元\)
\(s_1\)	28	2.5	1	103
\(s_2\)	21	1.5	2	198
\(s_3\)	23	5.5	4.5	52
\(s_4\)	25	2.6	6.5	40

试给该公司设计一种投资组合方案，即用给定资金 \(M\)，有选择地购买若干种资产或存银行生息，使净收益尽可能大，总体风险尽可能小。

问题分析

三要素：

• 决策变量：投资项目 \(s_i\) 的金额为 \(x_i\) \((i = 1, 2, \ldots, n)\)
• 目标函数：净收益 \(Q\) 最大，总风险 \(a\) 最小
• 约束条件：总资金 \(M\) 有限；每笔投资都是非负数

条件解读：

1. 总资金 \(M\) 相当大，而且题目设定的 \(u_i\) 很小，\(p_i u_i\) 更小，因此可以认为 \(x_i\) 均超过 \(u_i\)
   • 原本交易费应为 \(\max \{p_i u_i, p_i x_i\}\)，简化后直接用 \(p_i x_i\) 表示即可

模型建立

目标函数

\[ \left\{ \begin{array}{l}\displaystyle \max \sum_{i=1}^n (r_i - p_i) x_i \,, \\ \displaystyle \min \{\max_{1\leqslant i \leqslant n} \{q_i x_i\}\} \,. \end{array} \right. \]

约束条件

\[ \left\{ \begin{array}{l}\displaystyle \sum_{i=1}^n x_i \leqslant M \,, \\ x_i \geqslant 0 , \quad i = 1, 2, \ldots, n \,. \end{array} \right. \]

这是一个多目标规划问题，目标函数有两个，一个是最大化净收益，一个是最小化风险。因此需要考虑简化目标，变成一个目标的线性规划问题。

模型简化

固定风险水平

给定风险一个界限 \(a\) 作为能接受的最大风险率，同时尽可能地提高收益。

目标函数

\[ \displaystyle \max \sum_{i=1}^n (r_i - p_i) x_i \,. \]

约束条件

\[ \left\{ \begin{array}{l} \dfrac{q_i x_i}{M} \leqslant a , \quad i = 1, 2, \ldots, n \,, \\ \displaystyle \sum_{i=1}^n x_i \leqslant M \,, \\ x_i \geqslant 0 , \quad i = 1, 2, \ldots, n \,. \end{array} \right. \]

固定盈利水平

要求盈利水平至少达到 \(k\) 以上，同时尽可能降低风险。

目标函数

\[ \min \{\max_{1\leqslant i \leqslant n} \{q_i x_i\}\} \,. \]

约束条件

\[ \left\{ \begin{array}{l} \displaystyle \sum_{i=1}^n (r_i - p_i) x_i \geqslant k \,, \\ \displaystyle \sum_{i=1}^n x_i \leqslant M \,, \\ x_i \geqslant 0 , \quad i = 1, 2, \ldots, n \,. \end{array} \right. \]