第29章线性规划

1. 综述¶

在给定有限的资源或竞争的约束下，很多问题都可以表述为最大化或最小化一个目标。

线性规划(Linear Programming, LP) 就是一种可以将目标函数表示为某些变量的一个线性函数，将约束条件表示为这些变量的线性等式或线性不等式的数学模型。

三要素：

决策变量：问题中需要确定的目标量，用于表明问题中用数量衡量的方案或措施等。
目标函数：决策变量的函数。目标通常为函数的最大值或最小值。
约束条件：决策变量的取值受到的约束限制条件，通常由含决策变量的等式或不等式表示。

两种线性规划的规范形式：

标准型：满足线性不等式约束的一个线性函数最大化问题。
松弛型：满足线性等式约束的一个线性函数最大化问题。

求解方法：

图解法：适用于二维变量的线性规划问题。
单纯形算法：常用的算法。
- 单纯形：\(n\) 维空间约束条件定义的半空间的交集形成的可行区域
- 单纯形算法以一个线性规划为输入，输出一个最优解。它从单纯形的某个顶点开始，沿着单纯形的边移动到目标函数值不小于当前顶点的相邻顶点，直到达到目标函数的极大值。。

1.1. 一般型¶

线性规划模型的一般型为

\[ \begin{array}{l}\displaystyle \max/\min \quad z = \sum_{j=1}^n c_j x_j \,, \\ \text{s.t.} \quad \left\{ \begin{array}{l}\displaystyle \sum_{j=1}^n a_{ij} x_j \leqslant (=, \geqslant) b_i, i = 1, 2, \ldots, m \,, \\ x_j \geqslant 0, j = 1, 2, \ldots, n \,. \end{array} \right. \end{array} \]

其中：

\(c_j\) 为价值系数
\(a_{ij}\) 为工艺系数
\(b_i\) 为资源限量

2. 标准型和松弛型¶

2.1. 描述解的术语¶

2.1.1. 解的概念¶

可行解：满足线性规划模型约束条件的解 \(\boldsymbol{x}\)。对应的目标函数值称为这个解拥有的目标值。
最优解：使目标函数达到最大值或最小值的可行解。此时对应的目标函数值称为最优目标值。
可行域：所有可行解构成的集合，记为 \(\mathbf{R}\)

2.1.2. 解的情况¶

唯一最优解：目标函数与可行域交于一点。
无穷多最优解：目标函数与可行域边界平行，有无穷多个最优解。
无界解：可行域无界，目标函数没有边界，不存在最优解。此时称线性规划是无界的。
无可行解：可行域 \(\mathbf{R}\) 为 \(\varnothing\)。此时称线性规划是不可行的，否则是可行的。

2.2. 标准型¶

满足线性不等式约束的一个线性函数最大化问题。

一般线性规划问题的标准型是

\[ \max \quad z = \sum_{j=1}^n c_j x_j \,, \tag{1} \]

\[ \text{s.t.} \left\{ \begin{array}{l}\displaystyle \sum_{j=1}^n a_{ij} x_j \leqslant b_i, i = 1, 2, \ldots, m \,, \\ x_j \geqslant 0, j = 1, 2, \ldots, n \,. \\ \end{array} \right. \tag{2} \]

矩阵形式

\[ \max \quad z = \boldsymbol{c}^\mathrm{T}\boldsymbol{x} \,, \tag{3} \]

\[ \text{s.t.} \left\{ \begin{array}{l} \boldsymbol{A}\boldsymbol{x} \leqslant \boldsymbol{b} \,, \\ \boldsymbol{x} \geqslant 0 \,. \\ \end{array} \right. \tag{4} \]

其中：

\(\boldsymbol{A}\) 是 \(m \times n\) 的系数矩阵

要求：

目标函数为求最大值
约束条件均为不等式方程
变量 \(x_j \geqslant 0\)

2.2.1. 转换线性规划为标准型¶

有以下 4 种情况可能不是标准型：

目标函数为求最小值
有变量不具有非负约束
可能有等式约束
可能有 \(\geqslant\) 的不等式约束

2.2.1.1. 目标函数为求最小值¶

目标函数系数均取相反数。

注意最后结论需要把求得的最小值取相反数得到原问题的最大值目标。

2.2.1.2. 变量不具有非负约束¶

假设 \(x_i\) 不具有非负约束，则可以引入 \(x_i^\prime \geqslant 0, x_i^{\prime\prime} \geqslant 0\)，然后将目标函数和约束条件中的所有 \(x_i\) 都换成 \(x_i^\prime - x_i^{\prime\prime}\)。

2.2.1.3. 有等式约束¶

\[ \begin{array}{c} f(x_1, \ldots, x_n) = b \\ \Updownarrow\\ \left\{ \begin{array}{l} f(x_1, \ldots, x_n) \leqslant b \\ f(x_1, \ldots, x_n) \geqslant b \end{array}\right. \end{array} \]

2.2.1.4. 有 ≥ 的不等式约束¶

\[ \begin{array}{c} f(x_1, \ldots, x_n) \geqslant b \\ \Updownarrow\\ -f(x_1, \ldots, x_n) \leqslant -b \end{array} \]

3. 求解¶

3.1. 图解法¶

决策变量数量较少时比较好用。

如以横轴为 \(x_1\)，纵轴为 \(x_2\) 建立坐标系，则目标函数和约束条件都可以用直线来表示。

如以 \(x_1, x_2, x_3\) 为轴建立坐标系，则目标函数和约束条件都可以用平面来表示。

而目标函数的方程实际上也是一条直线/一个平面，函数值大小决定了直线/平面的位置。通过平移直线/平面，就可以找到最优解。

第29章 线性规划