线性规划的启发式初始化单纯形法求解示例

字数 4958 2025-12-09 04:09:32

线性规划的启发式初始化单纯形法求解示例

问题描述

我们考虑一个经典的线性规划问题：求解一个变量取值范围非负，包含不等式约束的线性规划。单纯形法是求解此类问题的核心算法。虽然单纯形法在理论上可能遍历所有顶点（最坏情况指数时间），但在实际应用中通常非常高效。然而，单纯形法的第一步——找到一个初始的基本可行解（BFS）——有时并不容易。特别是对于标准形式（$\mathbf{Ax = b, x \ge 0}$，且 $\mathbf{b} \ge 0$）的问题，如果约束矩阵 $\mathbf{A}$ 中不包含一个现成的单位矩阵，我们就需要引入人工变量并使用两阶段法或大M法。本示例将展示一种启发式初始化方法（也称为阶段0或Criss-Cross初始化），其目标是尽量不引入或少引入人工变量，直接构造一个初始基，从而可能加速单纯形法的第一阶段。

具体问题：
最大化目标函数： $Z = 3x_1 + 5x_2$
满足约束：

$x_1 + x_3 = 4$
$2x_2 + x_4 = 12$
$3x_1 + 2x_2 + x_5 = 18$
$x_1, x_2, x_3, x_4, x_5 \ge 0$

注意：这个问题实际上已经是一个标准形式，并且约束矩阵中已经包含了一个单位矩阵（对应松弛变量 $x_3, x_4, x_5$），因此初始基本可行解（BFS）是显而易见的：$(x_1, x_2, x_3, x_4, x_5) = (0, 0, 4, 12, 18)$，基变量是 $x_3, x_4, x_5$。但是，为了演示启发式初始化的思想，我们将假装这个单位矩阵不存在，或者约束是更一般的等式形式，然后尝试去构造一个初始基。

解题过程

步骤1：将问题转化为便于启发式处理的形式

原始问题已经是等式约束，且右端常数非负。我们将其写成增广矩阵形式（忽略目标函数，先专注于找到可行解）：

约束系统 $\mathbf{Ax = b}$:

\[\begin{aligned} x_1 & & &+ x_3 & & &= 4 \\ & & 2x_2 & & + x_4 & &= 12 \\ 3x_1 &+ 2x_2 & & & &+ x_5 &= 18 \\ \end{aligned} \]

其中， $x_1, x_2, x_3, x_4, x_5 \ge 0$。

我们的目标是：从变量集合 ${x_1, x_2, x_3, x_4, x_5}$ 中选出3个作为基变量，使得当非基变量设为0时，解出的基变量值非负。

步骤2：启发式初始化策略——最小不可行度法

一种常见的启发式策略是“最小不可行度”法。其核心思想是：

任意选择一个候选的基（即选择与约束数量相等的一组变量）。
求解对应的基系统 $\mathbf{Bx_B = b}$，其中 $\mathbf{B}$ 是基变量对应的系数子矩阵。
如果解出的 $\mathbf{x_B} \ge 0$，那么我们就找到了一个初始BFS。
如果解出的 $\mathbf{x_B}$ 中有负分量，则这个基不可行。我们计算一个“不可行度”度量，例如负分量的个数或负分量的绝对值之和。
通过替换基变量（类似于单纯形法的换基操作，但可能允许目标函数暂时无定义或不可用），尝试减少不可行度，直到找到一个可行的基。

在本例中，我们故意忽略现成的松弛变量基，进行演示。

步骤2.1：第一次尝试基选择

假设我们任意选择 ${x_1, x_2, x_3}$ 作为初始基。对应的系数矩阵和方程组为：

\[\begin{bmatrix} 1 & 0 & 1 \\ 0 & 2 & 0 \\ 3 & 2 & 0 \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 4 \\ 12 \\ 18 \end{bmatrix} \]

求解这个系统（例如使用高斯消元法）：

从第二行直接得：$2x_2 = 12 \Rightarrow x_2 = 6$。
将 $x_2=6$ 代入第三行：$3x_1 + 2*6 = 18 \Rightarrow 3x_1 = 6 \Rightarrow x_1 = 2$。
将 $x_1=2$ 代入第一行：$2 + x_3 = 4 \Rightarrow x_3 = 2$。
解得：$\mathbf{x_B} = (x_1, x_2, x_3) = (2, 6, 2)$。所有值均非负。

非常幸运！我们第一次尝试就得到了一个可行的基。此时的解是 $(x_1, x_2, x_3, x_4, x_5) = (2, 6, 2, 0, 0)$。这实际上是一个基本可行解，但对应的基 ${x_1, x_2, x_3}$ 不是我们通常从松弛变量开始的那个基。

步骤3：从启发式得到的初始基开始标准单纯形法

现在我们有了一个初始BFS: $(2, 6, 2, 0, 0)$，基变量为 $x_1, x_2, x_3$，非基变量为 $x_4, x_5$。

我们需要将目标函数 $Z = 3x_1 + 5x_2$ 用非基变量表示出来。为此，我们需要用非基变量表示基变量。

当前的基系统为：

$x_1 + x_3 = 4$ ...(1)
$2x_2 = 12 - x_4$ ...(2)
$3x_1 + 2x_2 + x_5 = 18$ ...(3)

但是注意，我们的基是 ${x_1, x_2, x_3}$，所以我们应该从方程中消除非基变量 $x_4, x_5$，得到 $x_1, x_2, x_3$ 的表达式。

从(2)式：$x_2 = 6 - \frac{1}{2}x_4$。
从(1)式：$x_3 = 4 - x_1$。
(3)式可以用来验证或求 $x_1$，但更好的方法是我们直接用(1)和(3)消去 $x_5$ 来表示 $x_1$？实际上，我们需要用非基变量 ($x_4, x_5$) 表示所有基变量 ($x_1, x_2, x_3$)。

我们有三个方程，但基变量有三个，非基变量有两个。我们可以将方程组通过行变换，变成每个方程只含一个基变量和非基变量的形式（即得到基矩阵 $\mathbf{B}$ 的逆乘以约束的表示）。

计算 $\mathbf{B}^{-1} \mathbf{A}$ 和 $\mathbf{B}^{-1}\mathbf{b}$ 可能更系统。但我们也可以直接代数推导。

从(2): $x_2 = 6 - 0.5x_4$。 (A)
将(A)和(1) $x_1 = 4 - x_3$ 代入(3):
$3(4 - x_3) + 2(6 - 0.5x_4) + x_5 = 18$
$12 - 3x_3 + 12 - x_4 + x_5 = 18$
$-3x_3 - x_4 + x_5 = -6$
所以 $x_3 = 2 + \frac{1}{3}x_4 - \frac{1}{3}x_5$。 (B)
然后从(1): $x_1 = 4 - x_3 = 4 - (2 + \frac{1}{3}x_4 - \frac{1}{3}x_5) = 2 - \frac{1}{3}x_4 + \frac{1}{3}x_5$。 (C)

现在我们有了：
$x_1 = 2 - \frac{1}{3}x_4 + \frac{1}{3}x_5$
$x_2 = 6 - \frac{1}{2}x_4$
$x_3 = 2 + \frac{1}{3}x_4 - \frac{1}{3}x_5$

代入目标函数：
$Z = 3x_1 + 5x_2 = 3(2 - \frac{1}{3}x_4 + \frac{1}{3}x_5) + 5(6 - \frac{1}{2}x_4)$
$Z = 6 - x_4 + x_5 + 30 - 2.5x_4$
$Z = 36 - 3.5x_4 + x_5$

步骤4：进行单纯形迭代

当前单纯形表（等价形式）：
基变量：$x_1, x_2, x_3$
解：$(2, 6, 2)$， $Z=36$
目标行系数（相对成本系数）：对于非基变量 $x_4$ 系数为 $-3.5$， $x_5$ 系数为 $+1$。

最优性检验：最大化问题中，当所有非基变量的相对成本系数 $\le 0$ 时达到最优。现在 $x_5$ 的系数 $+1 > 0$，说明增加 $x_5$ 能增加 $Z$。因此当前解不是最优的。

选择进基变量：$x_5$（正系数最大者，通常规则）。
选择出基变量：我们需要保证基变量在 $x_5$ 增加时保持非负。
从基变量的表达式看：
$x_1 = 2 + \frac{1}{3}x_5$ （$x_4$ 固定为0时） -> 随 $x_5$ 增加而增加，无限制。
$x_2 = 6$ -> 与 $x_5$ 无关，无限制。
$x_3 = 2 - \frac{1}{3}x_5$ -> 当 $x_5$ 增加时减小。为了保证 $x_3 \ge 0$，需要 $2 - \frac{1}{3}x_5 \ge 0 \Rightarrow x_5 \le 6$。
所以 $x_5$ 最多能增加到6，此时 $x_3$ 减小为0。因此，出基变量是 $x_3$。

旋转变换（Pivot）：
新的基变量为 $x_1, x_2, x_5$。我们需要重新用非基变量 $x_3, x_4$ 表示基变量和目标函数。
从之前的关系式(B) $x_3 = 2 + \frac{1}{3}x_4 - \frac{1}{3}x_5$，可以解出 $x_5$：
$x_5 = 6 + x_4 - 3x_3$。
代入(C): $x_1 = 2 - \frac{1}{3}x_4 + \frac{1}{3}(6 + x_4 - 3x_3) = 2 - \frac{1}{3}x_4 + 2 + \frac{1}{3}x_4 - x_3 = 4 - x_3$。
(A)式不变: $x_2 = 6 - \frac{1}{2}x_4$。
所以：
$x_1 = 4 - x_3$
$x_2 = 6 - \frac{1}{2}x_4$
$x_5 = 6 + x_4 - 3x_3$

代入目标函数 $Z = 36 - 3.5x_4 + (6 + x_4 - 3x_3) = 42 - 2.5x_4 - 3x_3$。

现在目标函数中非基变量 $x_3, x_4$ 的系数均为负（$-3$ 和 $-2.5$）。满足最优性条件。

因此，最优解为：$x_3=0, x_4=0$，则 $x_1=4, x_2=6, x_5=6$。
最优值 $Z = 42$。

这与从松弛变量基 ${x_3, x_4, x_5}$ 出发，经过两次迭代得到的结果完全一致。

总结

启发式初始化的目的是在不引入人工变量的情况下，通过试探性地选择基变量来直接获得一个初始基本可行解（BFS）。
其核心是定义一个“不可行度”度量，并通过类似单纯形换基的操作来减少该度量，直到找到可行基。在本例中，我们第一次尝试就成功了，但这在复杂问题中可能需要多次迭代。
一旦获得一个初始BFS，就可以无缝衔接标准的单纯形法进行优化迭代。
这种方法的优势在于避免了“两阶段法”中第一阶段求解辅助问题的开销，如果启发式策略有效，可以加速整体求解过程。但其风险是，在某些问题上，寻找可行基的启发式过程本身可能耗时，并且不能保证一定成功（此时仍需退回两阶段法）。它属于一种实用加速技巧。

线性规划的启发式初始化单纯形法求解示例问题描述我们考虑一个经典的线性规划问题：求解一个变量取值范围非负，包含不等式约束的线性规划。单纯形法是求解此类问题的核心算法。虽然单纯形法在理论上可能遍历所有顶点（最坏情况指数时间），但在实际应用中通常非常高效。然而，单纯形法的第一步——找到一个初始的基本可行解（BFS）——有时并不容易。特别是对于标准形式（$\mathbf{Ax = b, x \ge 0}$，且 $\mathbf{b} \ge 0$）的问题，如果约束矩阵 $\mathbf{A}$ 中不包含一个现成的单位矩阵，我们就需要引入人工变量并使用两阶段法或大M法。本示例将展示一种启发式初始化方法（也称为阶段0 或 Criss-Cross初始化），其目标是尽量不引入或少引入人工变量，直接构造一个初始基，从而可能加速单纯形法的第一阶段。具体问题：最大化目标函数： $Z = 3x_ 1 + 5x_ 2$ 满足约束： $x_ 1 + x_ 3 = 4$ $2x_ 2 + x_ 4 = 12$ $3x_ 1 + 2x_ 2 + x_ 5 = 18$ $x_ 1, x_ 2, x_ 3, x_ 4, x_ 5 \ge 0$ 注意：这个问题实际上已经是一个标准形式，并且约束矩阵中已经包含了一个单位矩阵（对应松弛变量 $x_ 3, x_ 4, x_ 5$），因此初始基本可行解（BFS）是显而易见的：$(x_ 1, x_ 2, x_ 3, x_ 4, x_ 5) = (0, 0, 4, 12, 18)$，基变量是 $x_ 3, x_ 4, x_ 5$。但是，为了演示启发式初始化的思想，我们将假装这个单位矩阵不存在，或者约束是更一般的等式形式，然后尝试去构造一个初始基。解题过程步骤1：将问题转化为便于启发式处理的形式原始问题已经是等式约束，且右端常数非负。我们将其写成增广矩阵形式（忽略目标函数，先专注于找到可行解）：约束系统 $\mathbf{Ax = b}$: $$ \begin{aligned} x_ 1 & & &+ x_ 3 & & &= 4 \\ & & 2x_ 2 & & + x_ 4 & &= 12 \\ 3x_ 1 &+ 2x_ 2 & & & &+ x_ 5 &= 18 \\ \end{aligned} $$ 其中， $x_ 1, x_ 2, x_ 3, x_ 4, x_ 5 \ge 0$。我们的目标是：从变量集合 ${x_ 1, x_ 2, x_ 3, x_ 4, x_ 5}$ 中选出3个作为基变量，使得当非基变量设为0时，解出的基变量值非负。步骤2：启发式初始化策略——最小不可行度法一种常见的启发式策略是“最小不可行度”法。其核心思想是：任意选择一个候选的基（即选择与约束数量相等的一组变量）。求解对应的基系统 $\mathbf{Bx_ B = b}$，其中 $\mathbf{B}$ 是基变量对应的系数子矩阵。如果解出的 $\mathbf{x_ B} \ge 0$，那么我们就找到了一个初始BFS。如果解出的 $\mathbf{x_ B}$ 中有负分量，则这个基不可行。我们计算一个“不可行度”度量，例如负分量的个数或负分量的绝对值之和。通过替换基变量（类似于单纯形法的换基操作，但可能允许目标函数暂时无定义或不可用），尝试减少不可行度，直到找到一个可行的基。在本例中，我们故意忽略现成的松弛变量基，进行演示。步骤2.1：第一次尝试基选择假设我们任意选择 ${x_ 1, x_ 2, x_ 3}$ 作为初始基。对应的系数矩阵和方程组为： $$ \begin{bmatrix} 1 & 0 & 1 \\ 0 & 2 & 0 \\ 3 & 2 & 0 \\ \end{bmatrix} \begin{bmatrix} x_ 1 \\ x_ 2 \\ x_ 3 \end{bmatrix} \begin{bmatrix} 4 \\ 12 \\ 18 \end{bmatrix} $$ 求解这个系统（例如使用高斯消元法）：从第二行直接得：$2x_ 2 = 12 \Rightarrow x_ 2 = 6$。将 $x_ 2=6$ 代入第三行：$3x_ 1 + 2* 6 = 18 \Rightarrow 3x_ 1 = 6 \Rightarrow x_ 1 = 2$。将 $x_ 1=2$ 代入第一行：$2 + x_ 3 = 4 \Rightarrow x_ 3 = 2$。解得：$\mathbf{x_ B} = (x_ 1, x_ 2, x_ 3) = (2, 6, 2)$。所有值均非负。非常幸运！我们第一次尝试就得到了一个可行的基。此时的解是 $(x_ 1, x_ 2, x_ 3, x_ 4, x_ 5) = (2, 6, 2, 0, 0)$。这实际上是一个基本可行解，但对应的基 ${x_ 1, x_ 2, x_ 3}$ 不是我们通常从松弛变量开始的那个基。步骤3：从启发式得到的初始基开始标准单纯形法现在我们有了一个初始BFS: $(2, 6, 2, 0, 0)$，基变量为 $x_ 1, x_ 2, x_ 3$，非基变量为 $x_ 4, x_ 5$。我们需要将目标函数 $Z = 3x_ 1 + 5x_ 2$ 用非基变量表示出来。为此，我们需要用非基变量表示基变量。当前的基系统为： $x_ 1 + x_ 3 = 4$ ...(1) $2x_ 2 = 12 - x_ 4$ ...(2) $3x_ 1 + 2x_ 2 + x_ 5 = 18$ ...(3) 但是注意，我们的基是 ${x_ 1, x_ 2, x_ 3}$，所以我们应该从方程中消除非基变量 $x_ 4, x_ 5$，得到 $x_ 1, x_ 2, x_ 3$ 的表达式。从(2)式：$x_ 2 = 6 - \frac{1}{2}x_ 4$。从(1)式：$x_ 3 = 4 - x_ 1$。 (3)式可以用来验证或求 $x_ 1$，但更好的方法是我们直接用(1)和(3)消去 $x_ 5$ 来表示 $x_ 1$？实际上，我们需要用非基变量 ($x_ 4, x_ 5$) 表示所有基变量 ($x_ 1, x_ 2, x_ 3$) 。我们有三个方程，但基变量有三个，非基变量有两个。我们可以将方程组通过行变换，变成每个方程只含一个基变量和非基变量的形式（即得到基矩阵 $\mathbf{B}$ 的逆乘以约束的表示）。计算 $\mathbf{B}^{-1} \mathbf{A}$ 和 $\mathbf{B}^{-1}\mathbf{b}$ 可能更系统。但我们也可以直接代数推导。从(2): $x_ 2 = 6 - 0.5x_ 4$。 (A) 将(A)和(1) $x_ 1 = 4 - x_ 3$ 代入(3): $3(4 - x_ 3) + 2(6 - 0.5x_ 4) + x_ 5 = 18$ $12 - 3x_ 3 + 12 - x_ 4 + x_ 5 = 18$ $-3x_ 3 - x_ 4 + x_ 5 = -6$ 所以 $x_ 3 = 2 + \frac{1}{3}x_ 4 - \frac{1}{3}x_ 5$。 (B) 然后从(1): $x_ 1 = 4 - x_ 3 = 4 - (2 + \frac{1}{3}x_ 4 - \frac{1}{3}x_ 5) = 2 - \frac{1}{3}x_ 4 + \frac{1}{3}x_ 5$。 (C) 现在我们有了： $x_ 1 = 2 - \frac{1}{3}x_ 4 + \frac{1}{3}x_ 5$ $x_ 2 = 6 - \frac{1}{2}x_ 4$ $x_ 3 = 2 + \frac{1}{3}x_ 4 - \frac{1}{3}x_ 5$ 代入目标函数： $Z = 3x_ 1 + 5x_ 2 = 3(2 - \frac{1}{3}x_ 4 + \frac{1}{3}x_ 5) + 5(6 - \frac{1}{2}x_ 4)$ $Z = 6 - x_ 4 + x_ 5 + 30 - 2.5x_ 4$ $Z = 36 - 3.5x_ 4 + x_ 5$ 步骤4：进行单纯形迭代当前单纯形表（等价形式）：基变量：$x_ 1, x_ 2, x_ 3$ 解：$(2, 6, 2)$， $Z=36$ 目标行系数（相对成本系数）：对于非基变量 $x_ 4$ 系数为 $-3.5$， $x_ 5$ 系数为 $+1$。最优性检验：最大化问题中，当所有非基变量的相对成本系数 $\le 0$ 时达到最优。现在 $x_ 5$ 的系数 $+1 > 0$，说明增加 $x_ 5$ 能增加 $Z$。因此当前解不是最优的。选择进基变量：$x_ 5$（正系数最大者，通常规则）。选择出基变量：我们需要保证基变量在 $x_ 5$ 增加时保持非负。从基变量的表达式看： $x_ 1 = 2 + \frac{1}{3}x_ 5$ （$x_ 4$ 固定为0时） -> 随 $x_ 5$ 增加而增加，无限制。 $x_ 2 = 6$ -> 与 $x_ 5$ 无关，无限制。 $x_ 3 = 2 - \frac{1}{3}x_ 5$ -> 当 $x_ 5$ 增加时减小。为了保证 $x_ 3 \ge 0$，需要 $2 - \frac{1}{3}x_ 5 \ge 0 \Rightarrow x_ 5 \le 6$。所以 $x_ 5$ 最多能增加到6，此时 $x_ 3$ 减小为0。因此，出基变量是 $x_ 3$ 。旋转变换（Pivot）：新的基变量为 $x_ 1, x_ 2, x_ 5$。我们需要重新用非基变量 $x_ 3, x_ 4$ 表示基变量和目标函数。从之前的关系式(B) $x_ 3 = 2 + \frac{1}{3}x_ 4 - \frac{1}{3}x_ 5$，可以解出 $x_ 5$： $x_ 5 = 6 + x_ 4 - 3x_ 3$。代入(C): $x_ 1 = 2 - \frac{1}{3}x_ 4 + \frac{1}{3}(6 + x_ 4 - 3x_ 3) = 2 - \frac{1}{3}x_ 4 + 2 + \frac{1}{3}x_ 4 - x_ 3 = 4 - x_ 3$。 (A)式不变: $x_ 2 = 6 - \frac{1}{2}x_ 4$。所以： $x_ 1 = 4 - x_ 3$ $x_ 2 = 6 - \frac{1}{2}x_ 4$ $x_ 5 = 6 + x_ 4 - 3x_ 3$ 代入目标函数 $Z = 36 - 3.5x_ 4 + (6 + x_ 4 - 3x_ 3) = 42 - 2.5x_ 4 - 3x_ 3$。现在目标函数中非基变量 $x_ 3, x_ 4$ 的系数均为负（$-3$ 和 $-2.5$）。满足最优性条件。因此，最优解为：$x_ 3=0, x_ 4=0$，则 $x_ 1=4, x_ 2=6, x_ 5=6$。最优值 $Z = 42$。这与从松弛变量基 ${x_ 3, x_ 4, x_ 5}$ 出发，经过两次迭代得到的结果完全一致。总结启发式初始化的目的是在不引入人工变量的情况下，通过试探性地选择基变量来直接获得一个初始基本可行解（BFS）。其核心是定义一个“不可行度”度量，并通过类似单纯形换基的操作来减少该度量，直到找到可行基。在本例中，我们第一次尝试就成功了，但这在复杂问题中可能需要多次迭代。一旦获得一个初始BFS，就可以无缝衔接标准的单纯形法进行优化迭代。这种方法的优势在于避免了“两阶段法”中第一阶段求解辅助问题的开销，如果启发式策略有效，可以加速整体求解过程。但其风险是，在某些问题上，寻找可行基的启发式过程本身可能耗时，并且不能保证一定成功（此时仍需退回两阶段法）。它属于一种实用加速技巧。