一般数学模型

\begin{align}
\max(\text{或 } \min) \quad & z = \sum_{j=1}^{n} c_j x_j \\
\text{s.t.} \quad & \left\{
\begin{aligned}
& \sum_{j=1}^{n} a_{ij} x_j \leq (\text{或 } =, \geq) b_i \quad (i = 1, \cdots, m) \\
& x_j \geq 0 \quad (j = 1, \cdots, n)
\end{aligned}
\right.
\end{align}

矩阵形式：

\begin{align}
\max(\text{或 } \min) \quad & z = \mathbf{c}^T \mathbf{x} \\
\text{s.t.} \quad & \left\{
\begin{aligned}
& \mathbf{A} \mathbf{x} \leq (\text{或 } =, \geq) \mathbf{b} \\
& \mathbf{x} \geq \mathbf{0}
\end{aligned}
\right.
\end{align}

其中：

• $\mathbf{x} = (x_1, x_2, \cdots, x_n)^\mathrm{T} \in \mathbb{R}^n$为决策变量向量
• $\mathbf{c} = (c_1, c_2, \cdots, c_n)^\mathrm{T} \in \mathbb{R}^n$ 为价值系数向量
• $A = (a_{ij})_{m \times n} \in \mathbb{R}^{m \times n}$ 为约束系数矩阵
• $\mathbf{b} = (b_1, b_2, \cdots, b_m)^\mathrm{T} \in \mathbb{R}^m$ 为资源向量

三个关键要素

要素	示例	含义
决策变量	$x_1, x_2, \ldots, x_n$​	需要求解的未知量
目标函数	$z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n$​	线性函数，要最大化或最小化
约束条件	$A\mathbf{x} \leq \mathbf{b}, \quad \mathbf{x} \geq 0$	线性不等式或等式

标准形式

为了让同一套算法、同一套理论、同一套软件能毫无歧义地处理所有 LP 问题，规定的线性规划问题标准形式如下：

\begin{align}
\max \quad & z = \sum_{j=1}^{n} c_j x_j \\
\text{s.t.} \quad & \left\{
\begin{aligned}
& \sum_{j=1}^{n} a_{ij} x_j = b_i \quad (i = 1, \cdots, m) \\
& x_j \geq 0 \quad (j = 1, \cdots, n)
\end{aligned}
\right.
\end{align}

标准形式的五个要素：

1. 目标函数：求最大值（max）
2. 约束条件：全部为等式约束（=）
3. 决策变量：全部非负（x ≥ 0）
4. 右端项：全部非负（b ≥ 0）
5. 系数矩阵：任意实数

标准化方法

接下来以一个非标准形式线性规划问题为例介绍如何进行标准化。

例1：

\begin{align}
\min \quad & z = 3x_1 - 2x_2 + 5x_3 \\
\text{s.t.} \quad & \left\{
\begin{aligned}
& 2x_1 + x_2 - x_3 \leq 10 \\
& x_1 - 3x_2 + 2x_3 \geq 5 \\
& 4x_1 + 2x_2 + x_3 = -15 \\
& x_1 \geq 0,\ x_2 \leq 0,\ x_3 \text{ 无约束}
\end{aligned}
\right.
\end{align}

1、目标函数求最小值 → 转化为求最大值

最小化 $z$ 等价于最大化 $−z$，令 $z'=-z$ ，转化规则如下：

$$\min \, z = \mathbf{c}^T \mathbf{x} \ \Longleftrightarrow\ \max \, z' = -\mathbf{c}^T \mathbf{x}$$

例题应用：$$\min \, z = 3x_1 - 2x_2 + 5x_3 \ \Rightarrow\ \max \, z' = -3x_1 + 2x_2 - 5x_3$$

2、不等式约束→ 转化为等式

在约束为≤时引入非负松弛变量 $s_i$ 表示剩余的未使用资源，转化规则如下（实际题目通常用 $x_{n+1}, x_{n+2}, \dots$ 作为松弛/剩余变量）：

$$\sum_{j=1}^{n} a_{ij}x_j \leq b_i \ \Longleftrightarrow\ \sum_{j=1}^{n} a_{ij}x_j + s_i = b_i,\ s_i \geq 0$$

例题应用：$$2x_1 + x_2 - x_3 \leq 10 \ \Rightarrow\ 2x_1 + x_2 - x_3 + x_4 = 10,\ x_4 \geq 0$$

在约束为≥时引入非负剩余变量 $s_i$ 表示超出需求的产量，转化规则如下：

$$\sum_{j=1}^{n} a_{ij}x_j \geq b_i \ \Longleftrightarrow\ \sum_{j=1}^{n} a_{ij}x_j - s_i = b_i,\ s_i \geq 0$$

例题应用：$$x_1 - 3x_2 + 2x_3 \geq 5 \ \Rightarrow\ x_1 - 3x_2 + 2x_3 - x_5 = 5,\ x_5 \geq 0$$

3、右端项为负→ 两边乘以-1

转化规则如下：

$$\sum_{j=1}^{n} a_{ij}x_j \geq b_i,\ b_i < 0 \ \Longleftrightarrow\ \sum_{j=1}^{n} (-a_{ij})x_j \leq -b_i,\ -b_i > 0$$

例题应用（等式约束）：

$$-4x_1 + -2x_2 + -x_3 = 15$$

如果是不等式约束转化后要加入松弛/剩余变量

4、非正变量（x ≤ 0）→ 变量替换

转化规则如下：

$$x_j \leq 0 \ \Longleftrightarrow\ x_j = -x_j',\ x_j' \geq 0$$

例题应用：$$x_2 \leq 0 \ \Rightarrow\ x_2 = -x_2',\ x_2' \geq 0$$

替换后的影响：目标函数和约束条件中的$x_2$ 全部替换为 $-x_2'$

5、自由变量（无符号约束）→ 差分替换

因为任何实数都可以表示为两个非负数的差，引入两个非负变量，转化规则如下：

$$x_j \text{ 无约束 } \Longleftrightarrow x_j = x_j' - x_j'',\ x_j' \geq 0,\ x_j'' \geq 0$$

例题应用：$$x_3 \text{ 无约束 } \Longleftrightarrow x_3 = x_3' - x_3'',\ x_3' \geq 0,\ x_3'' \geq 0$$

替换后的影响：目标函数和约束条件中的$x_3$ 全部替换为 $x_3' - x_3''$

解的概念

解的分类层次：

可行解（Feasible Solution）：满足所有约束条件的解称为可行解。

可行域（Feasible Region）：所有可行解的集合，可行域是 $n$ 维空间中的一个凸多面体。

最优解（Optimal Solution）：在所有可行解中，使目标函数达到最大值（或最小值）的解称为最优解，可能不唯一。

基：一般线性规划问题的标准形式的约束方程是$Ax = b \quad (A\in\mathbb{R}^{m\times n},\; n>m)$其中：

• 秩$r(A)=m$，即行满秩，约束彼此独立。
• $n>m$意味着变量多于方程，故有无穷多解，需借助线性规划方法寻找最优解。

在 $A$ 中任选 $m$ 个线性无关的列，它们构成一个 $m\times m$ 的可逆矩阵：$B = \bigl(P_{j_1}, P_{j_2}, \dots, P_{j_m}\bigr)$这个 $B$ 就称为线性规划问题的一个基。

基本解（Basic Solution）：对于标准型线性规划$A\mathbf{x} = \mathbf{b}$，其中 $A$ 是 $m\times n$ 矩阵，$\operatorname{rank}(A) = m$。

步骤：

1. 从 $\mathbf{A}$ 的 $n$ 个列向量中选取 $m$ 个线性无关的列向量，构成基矩阵 $\mathbf{B}$
2. 其余 $n-m$ 个列向量对应的变量称为非基变量，令其为 0
3. 求解方程组 $B\mathbf{x}_B = \mathbf{b}$，得到基变量 $\mathbf{x}_B$
4. ​得到的解 $\mathbf{x} = (\mathbf{x}_B, \mathbf{0})$ 称为基本解

基本可行解（Basic Feasible Solution, BFS）：满足非负约束的基本解称为基本可行解，对应可行域的顶点（极点）。即：

\begin{align*}
\mathbf{x} = \begin{pmatrix} \mathbf{x}_B \\ \mathbf{0} \end{pmatrix}, \quad \mathbf{x}_B = B^{-1}\mathbf{b} \geq \mathbf{0}
\end{align*}

基本定理

定理1：若线性规划问题存在可行解，则问题的可行域是凸集

定理2：$X$ 是基本可行解 ⇔ $X$ 是可行域的顶点（极点）

定理3：如果线性规划问题有可行解且目标函数有界，则必存在最优解，且至少有一个最优解是基本可行解

图解法

例2：

\begin{align}
\max \quad & z = 50x_1 + 60x_2 \\
\text{s.t.} \quad & \left\{
\begin{aligned}
& 2x_1 + 3x_2 \leq 92 \\
& 3x_1 + 2x_2 \leq 80 \\
& x_1 + 2x_2 \leq 60 \\
& x_1, x_2 \geq 0
\end{aligned}
\right.
\end{align}

图解法步骤：

一、建立坐标系

• 横轴：$x_1$（产品1的产量）
• 纵轴：$x_2$（产品2的产量）

二、绘制约束条件，寻找可行域

• 约束1：$2x_1 + 3x_2 \leq 92$
• 约束2：$3x_1 + 2x_2 \leq 80$
• 约束3：$x_1 + 2x_2 \leq 60$

可行域为所有约束的交集形成凸多边形（阴影区域）：

可行域的顶点（按逆时针方向）：

1. O(0,0)：原点
2. A(0,30)：约束3与纵轴的交点
3. B(4,28)：约束1与约束3的交点
4. C(11.2, 23.2)：约束1与约束2的交点
5. D(33.33,0)：约束1与横轴的交点

可行域如图所示：

三、绘制目标函数等值线，寻找最优解

绘制目标函数$z = 50x_1 + 60x_2$的平行线族（不同 $z$ 值）用来表示目标函数线的平行移动，与可行域最后接触的点即为最优解，如图所示：

最优解：顶点 C(11.2,23.2)，$max \quad z=1952.0$

线性规划解的不同情况

1.唯一最优解：目标函数线与可行域在一个顶点相切。

2.无穷多最优解：目标函数线与一条边界线平行，该边上的所有点都是最优解，若例题中的目标函数改为$\max \quad z = 40x_1 + 60x_2$，则解的情况如图所示：

3.无界解：因为缺少关键约束，可行域无界，目标函数值可无限增大。

4.无可行解：约束条件相互矛盾，可行域为空集。

具体步骤

接着通过例2来讲解单纯形法的具体步骤，先将例2转化为标准型：

\begin{align}
\max \quad & z = 50x_1 + 60x_2 + x_3 + x_4 + x_5\\
\text{s.t.} \quad & \left\{
\begin{aligned}
& 2x_1 + 3x_2 + x_3 = 92 \\
& 3x_1 + 2x_2 + x_4 = 80 \\
& x_1 + 2x_2 + x_5 = 60 \\
& x_1, x_2, x_3, x_4, x_5\geq 0
\end{aligned}
\right.
\end{align}

一、列出初始基可行解和初始单纯形表

例2增广矩阵为

由于约束都是"≤"形式，引入的松弛变量系数矩阵为单位矩阵，构成一个基，对应变量$x_3 ， x_4 ， x_5$是基变量，令非基变量为零，初始基可行解为$\mathbf{X} = (0, 0, 92, 80, 60)^T$。若存在“≥”或“=”约束，或右端为负，需用两阶段法或大 M 法先解辅助问题。初始单纯形表如下：

\begin{array}{|c|c|c|ccccc|}
\hline
& & c_j & 50 & 60 & 0 & 0 & 0 & \\
\hline
C_B & X_B & b & x_1 & x_2 & x_3 & x_4 & x_5 \\
\hline
0 & x_3 & 92 & 2 & 3 & 1 & 0 & 0 \\
0 & x_4 & 80 & 3 & 2 & 0 & 1 & 0 \\
0 & x_5 & 60 & 1 & 2 & 0 & 0 & 1 \\
\hline
\end{array}

组成部分：

1. 基变量列$\mathbf{X_b}$：$x_{1}, x_{2}, ..., x_{m}$
   • $\mathbf{B}$ 是基矩阵，包含 $m$ 个线性无关的列
2. 基变量系数列$\mathbf{C_B}$：$c_{1}, c_{2}, ..., c_{m}$表示当前基变量在目标函数里对应的系数
3. 决策变量行：$x_1, x_2, ..., x_n$包含所有变量
4. 系数矩阵区域：$a_{ij}$为约束系数，表示变量 $x_j$ 在第 $i$ 个约束中的系数
   • 对于基变量，对应的列是单位向量
5. b列：$b_i$表示约束的右端常数项

二、最优性检验

增加检验数行$\sigma_j$，计算公式为$\sigma_j = c_j - \sum_{i=1}^{m} c_Ba_{ij}$。所有检验数$\sigma_j≤0$，且基变量中不含有人工变量时，表中基可行解为最优解，表则称为最终单纯形表。如果存在至少一个非基变量检验数 = 0，则为多重解。如果存在 $\sigma_k > 0$且$a_{ik} \leq 0 \forall i$，则问题无界。

三、基变换，进行迭代

1.确认进基变量：检验数$\sigma_j＞0$时，选择满足$\sigma_k = \max\{\sigma_j \mid \sigma_j > 0\}$的$x_k$作为进基变量。

2.确认出基变量： 根据$\theta = \min\left\{\frac{b_i}{a_{ik}} \mid a_{ik} > 0, i = 1,...,m\right\}=\frac{b_l}{a_{lk}}$计算得到的$x_{l}$为出基变量，主元素为${a_{lk}}$。在例2中${a_{32}}$为主元，加上方括号[]：

\begin{array}{|c|c|c|ccccc|c|}
\hline
& & c_j & 50 & 60 & 0 & 0 & 0 & \\
\hline
C_B & X_B & b & x_1 & x_2 & x_3 & x_4 & x_5 & \theta_i \\
\hline
0 & x_3 & 92 & 2 & 3 & 1 & 0 & 0 & 30.67 \\
0 & x_4 & 80 & 3 & 2 & 0 & 1 & 0 & 40 \\
0 & x_5 & 60 & 1 & [2] & 0 & 0 & 1 & 30 \\
\hline
& & {\sigma_j} & 50 & 60 & 0 & 0 & 0 \\
\hline
\end{array}

3.迭代（用进基变量$x_k$替换出基变量$x_{l}$得到一个新基）并作出出新单纯形表：

将主元${a_{lk}}$所在的$k$列$\mathbf{P_k}$转化为单位向量：

• $l$行所在的数字全部除以主元${a_{lk}}$
• 通过初等行变换将主元${a_{lk}}$所在$k$列上的数字变成0（除主元以外）

例2经过第一次迭代后单纯形表如下：

\begin{array}{|c|c|c|ccccc|c|}
\hline
& & c_j & 50 & 60 & 0 & 0 & 0 & \\
\hline
C_B & X_B & b & x_1 & x_2 & x_3 & x_4 & x_5 & \theta_i \\
\hline
0 & x_3 & 2 & 1/2 & 0 & 1 & 0 & -3/2 & 4 \\
0 & x_4 & 20 & 2 & 0 & 0 & 1 & -1 & 10 \\
60 & x_2 & 30 & 1/2 & 1 & 0 & 0 & 1/2 & 60 \\
\hline
& & \sigma_j & 20 & 0 & 0 & 0 & -30 & \\
\hline
\end{array}

4.重复二、三步直到计算结束。

例2的最终单纯形表如下：

\begin{array}{|c|c|c|ccccc|}
\hline
& & c_j & 50 & 60 & 0 & 0 & 0 \\
\hline
C_B & X_B & b & x_1 & x_2 & x_3 & x_4 & x_5 \\
\hline
50 & x_1 & 56/5 & 1 & 0 & -2/5 & 3/5 & 0 \\
0 & x_5 & 12/5 & 0 & 0 & -4/5 & 1/5 & 1 \\
60 & x_2 & 116/5 & 0 & 1 & 3/5 & -2/5 & 0 \\
\hline
& & \sigma_j & 0 & 0 & -16 & -6 & 0 \\
\hline
\end{array}