Simplex 算法简介 | Baeldung 关于计算机科学

1. 简介

在本教程中，我们将展示 Simplex 算法的工作原理。

它被广泛用于解决现实世界的优化问题，这些问题的数学公式包括线性等式或不等式，例如，在物流、金融、工程等领域。

2. 线性规划基础

线性规划 (LP) 是在给定约束条件下找到问题的最优解。它有三个主要组成部分：目标函数、约束和可行域。

目标函数是我们想要优化的线性函数

$Z = c_1x_1 + c_2x_2 + \dots + c_nx_n$

其中 $Z$ 是结果值， $c_1, c_2, \dots, c_n$ 是系数， $x_1, x_2, \dots, x_n$ 是决策变量。

接下来，我们有约束——以线性不等式形式表达的规则和限制，它们定义了我们的可行域。这些约束通常反映了现实世界的限制，例如劳动力小时数、材料或机器容量。它们可以有两种形式：≤ 和 ≥ 不等式。

一个 ≤ 约束确保我们不超过资源限制，例如

$a_1x_1 + a_2x_2 + \dots + a_nx_n \leq b$

另一方面，一个 ≥ 约束设定了必须满足的最低要求，例如

$a_1x_1 + a_2x_2 + \dots + a_nx_n \geq b$

两种类型的约束都确定了可行域的边界，从而确定了哪些解是有效的。

最后，可行域是决策变量的几何空间，其中满足每个条件。我们的工作是在该区域内找到优化目标函数的那一点。

3. Simplex 算法基础

现在我们了解了线性规划及其关键组成部分，问题是：我们如何找到可行域中的最优解？Simplex 算法就在此时派上用场。

3.1. 步骤

Simplex 算法在线性规划问题的可行域中导航，从一个顶点移动到另一个顶点以找到最佳解决方案。

它不是检查每个点，而是 只检查区域的顶点，保证最优解位于其中：

我们从一个顶点开始，通过求解约束系统得到该顶点。然后，我们评估目标函数
接下来，我们确定最佳移动方向。 当前顶点的边表示可能的路径，算法选择提供目标函数最大改进（无论是最大化还是最小化）的路径
我们沿所选的边移动到顶点，更新我们的解决方案并重复该过程
最终，我们到达一个无法进一步改进的点，而该点就是最优解

Simplex 算法通过专注于顶点，无需不必要的计算就能找到最佳结果。

3.2. 为什么最优解始终位于顶点？

将可行域想象成被墙壁（约束条件）包围的平坦地形，目标函数就像倾斜在上面的一个平直的斜坡。由于斜坡是直的，而墙壁定义了地形，因此斜坡能够延伸到的最远距离总是会在最尖锐的点——角上。这些角，即边界相交的地方，为斜坡提供了坚实的“支撑”。

如果斜坡停留在任何内部点，它都可以滑动到附近的边缘或角上。这是因为目标函数和约束条件都是线性的，所以它们会引导斜坡直线到达一个角。因此，最优解始终位于这些角点上。

3.3. 松弛变量、剩余变量和人工变量

为了应用单纯形法，我们将约束不等式转换为等式，引入额外的变量。

松弛变量通过添加未使用的资源来处理 ≤ 约束。

例如

$a_1x_1 + a_2x_2 \leq b$

变为

$a_1x_1 + a_2x_2 + s_1 = b, \quad s_1 \geq 0$

其中 $s_1$ 表示剩余容量。

对于 ≥ 约束，我们使用剩余变量来扣除超过最小要求的量。

像这样的约束

$a_1x_1 + a_2x_2 \geq b$

重写为

$a_1x_1 + a_2x_2 - s_1 = b, \quad s_1 \geq 0$

其中 $s_1$ 表示超过 $b$ 的剩余量。

然而，仅使用剩余变量并不能保证可行的起始解，因此我们引入人工变量作为占位符来形成初始单纯形表。.

例如

$a_1x_1 + a_2x_2 - s_1 = b$

变为

$a_1x_1 + a_2x_2 - s_1 + p_1 = b, \quad s_1, p_1 \geq 0$

虽然人工变量 $p_1$ 有助于初始步骤，但它并不代表任何实际资源。因此，我们必须尽快使用大M法或两阶段法将其移除。

3.4. 基本变量和非基本变量

在单纯形法中，变量是基本变量或非基本变量。 基本变量取非零值并锚定当前解，而非基本变量则为零。

当我们从可行域的一个角移动到另一个角时，非基本变量可以变为基本变量，反之亦然，这取决于它们对目标函数的影响。这种动态交换使算法能够有效地探索和优化解。

3.5. 枢轴操作

枢轴操作是单纯形法的关键步骤，我们通过交换变量来改进解。

在每个步骤中，我们选择一个非基本变量进入基，以增强目标函数，并选择一个基本变量离开，以保持可行性。这使得解保持在可行域内。枢轴操作会更新这些变量，改进解并使我们更接近最优解。

通过系统性的枢轴操作，该算法可以有效地从一个角移动到下一个角。

4. 一个实际例子

4.1. 简的优化问题

简同时兼顾两份兼职工作，工作I和工作II，并希望最大化她的每周收入。在这样做的时候，她面临两个约束

她每周最多可以工作12小时
她每周有16小时用于工作准备。在工作I的每一小时需要2小时的准备时间，而在工作II的每一小时需要1小时。

此外，她在这些工作中的盈利潜力各不相同：她在工作I每小时赚取40美元，在工作II每小时赚取30美元。

那么，简应该如何分配她的工作时间在两份工作之间才能最大化她的收入？她的总收入是多少？

让我们一步一步地使用单纯形法来解决简的问题。

4.2. 第一步：将线性规划转化为标准形式

为了准备单纯形算法，我们确保目标函数处于最大化形式。

设 $x_1$ 是在工作 I 上工作的小时数， $x_2$ 是在工作 II 上工作的小时数。总收入是

$Z = 40x_1 + 30x_2$

我们希望最大化这个值。如果目标是最小化，例如成本，我们将目标函数乘以 -1。

然后，我们将所有 $\leq$ 约束条件转换为等式，通过添加松弛变量。

简总共工作时间不超过 12 小时

$x_1 + x_2 \leq 12$

在工作 I 的每个小时需要 2 小时的准备时间，在工作 II 的每个小时需要 1 小时的准备时间，最多 16 小时

$2x_1 + x_2 \leq 16$

此外， $x_1$ 和 $x_2$ 都必须是非负数

$x_1, x_2 \geq 0$

我们引入松弛变量（除了非负约束），将不等式转换为等式

$x_1 + x_2 + s_1 = 12 \quad \text{where} \quad s_1 \geq 0$

$2x_1 + x_2 + s_2 = 16 \quad \text{where} \quad s_2 \geq 0$

最后，我们将目标函数写成一个等式

$Z - 40x_1 - 30x_2 = 0$

因此，我们将问题转化为标准形式，并设置了初始单纯形表

x1	x2	s1	s2	Z	右侧常数项 (RHS)
1	1	1	0	0	12
2	1	0	1	0	16
-40	-30	0	0	1	0

4.3. 第二步：初始化基本可行解

一旦线性规划处于标准形式，下一步就是确定初始基本可行解。我们指定步骤 1 中的松弛变量作为基本变量，并将所有非基本变量设置为零。 从等式约束中，我们计算基本变量的值，建立起始解。

在我们的例子中，我们选择 $s_1$ 和 $s_2$ 作为基本变量，因此我们将 $x_1$ 和 $x_2$ 设置为零。然后，我们求解所得系统以获得基本变量 $s_1$ 和 $s_2$ 。

从第一个约束条件 $x_1 + x_2 + s_1 = 12$ ，我们代入 $x_1 = 0$ 和 $x_2 = 0$ 来找到

$s_1 = 12$

类似地，从第二个约束条件，我们得到

$s_2 = 16$

因此，初始基本可行解是

$x_1 = 0, x_2 = 0, s_1 = 12, s_2 = 16$

接下来，我们计算目标函数的值

$Z = 40x_1 + 30x_2 = 0 + 0 = 0$

4.4. 第 3 步：确定进入变量（枢轴列）

接下来，我们确定进入变量——移动到基础中以改进解决方案的非基本变量。它引导我们走向更好的目标值——对于最大化问题增加它，或者对于最小化问题减少它。

为了选择进入变量，我们检查单纯形表的目标行。对于最大化问题，我们选择系数“最负”的变量，因为增加它会使 $Z$ 产生最陡峭的上升。由于每个系数代表 $Z$ 的变化率，因此最负的系数确保最快的改进。在最小化问题中，我们选择最大的正系数。此步骤确保我们始终 朝着最佳方向前进。

我们的例子是一个最大化问题。查看我们初始单纯形表中 $x_1$ 和 $x_2$ 的系数，我们看到 -40 是最负的系数。因此， $x_1$ 将会是进入变量，它的列变成枢轴列

x1	x2	s1	s2	Z	右侧常数项 (RHS)
1	1	1	0	0	12
2	1	0	1	0	16
-40	-30	0	0	1	0

4.5. 第 4 步：确定离开变量和枢轴元素

在单纯形算法中，离开变量是在一次迭代期间退出基础的基本变量。

为了确定离变量，我们计算右侧值（RHS）与枢轴列中正系数的比率。我们选择比率最小的正行，因为将进入变量增加到此点之后会违反约束条件。这种选择确保解保持在可行区域内。

枢轴元素是枢轴行与枢轴列的交点，是用于更新单纯形表中的关键值。这一步骤确保平滑过渡到新的顶点。

在简的优化问题中，枢轴列是 $x_1$ ，而RHS与 $x_1$ 列中正系数的比率是

对于第1行： $\frac{12}{1} = 12$
对于第2行： $\frac{16}{2} = 8$

由于第2行具有最小的正比率， $s_2$ 是离变量。这使得枢轴元素成为第2行第一列中的那个。

x1	x2	s1	s2	Z	RHS	比率 = (RHS / x1)
1	1	1	0	0	12	12/1 = 12
2	1	0	1	0	16	16/2 = 8
-40	-30	0	0	1	0

4.6. 第5步：执行枢轴操作

一旦确定枢轴元素，我们执行枢轴操作来更新单纯形表。

我们通过规范化枢轴行（将其除以枢轴元素使其变为1）并调整所有其他行（包括Z行）来实现这一点，以使枢轴列中的每个其他条目变为零。这确保了与枢轴列关联的基本变量正确地整合到解中。

在简的问题中，枢轴元素是第2行第一列中的2。因此，我们通过将其除以2来规范化第2行，使枢轴元素变为1。

x1	x2	s1	s2	Z	RHS	行操作
1	1	1	0	0	12
1	1/2	0	1/2	0	8	新第2行 = 第2行/2
-40	-30	0	0	1	0

接下来，我们调整第1行，使用该操作使枢轴列条目变为零

$\text{New Row1} = \ \text{Row1} - 1 \times \text{New Row2} \quad \rightarrow \quad [0, 0.5, 1, -0.5, 0, 4]$

最后，我们更新Z行（第3行）以消除枢轴列系数，确保与目标函数一致

$\text{New Row3} = Z + 40 \times \text{New Row2} \quad \rightarrow \quad [0, -10, 0, 20, 1, 320]$

这是更新后的单纯形表

x1	x2	s1	s2	Z	RHS	行操作
0	1/2	1	-1/2	0	4	新第1行 = 第1行 – 新第2行
1	1/2	0	1/2	0	8
0	-10	0	20	1	320	新第3行 = Z + 40 新第2行

4.7. 第6步：重复直到达到最优解

我们重复第3到第5步，直到目标行（Z行）中的所有系数均为非负数。这将表明我们找到了最优解。

在当前简化的 Jane 优化问题 tableau 中，Z 行仍然包含一个负值， $-10$ ，因此我们必须返回到步骤 3 以开始下一轮迭代。

底行中最负的数字是 $-10$ ，它确定了主元列。因此，我们计算每一行相对于主元列的 RHS 的比率。

$\frac{4}{\frac{1}{2}} = 4 \div \frac{1}{2} = 4 \times 2 = 8$

$\frac{8}{\frac{1}{2}} = 8 \div \frac{1}{2} = 8 \times 2 = 16$

由于 8 是最小的正商，因此它确定了主元行。

新的 tableau 变为

x1	x2	s1	s2	Z	RHS	比率 = (RHS / x2)
0	1/2	1	-1/2	0	4	4/(1/2) = 8
1	1/2	0	1/2	0	8	8/(1/2) = 16
0	-10	0	20	1	320

因此， $\frac{1}{2}$ 在第 1 行（黄色框）中是主元。我们需要将其转换为 1，并将所有下面的条目转换为 0。为了将主元条目更改为 1，我们将第 1 行乘以 $\frac{2}{1} = 2$ 。

这是更新后的单纯形表

x1	x2	s1	s2	Z	RHS	行运算
0	1	2	-1	0	8	新第 2 行 = 2 * 第 1 行
1	1/2	0	1/2	0	8
0	-10	0	20	1	320

为了使主元条目下方变为零，我们用第 2 行减去 (1/2) * 第 1 行，用第 3 行加上 10 * 第 1 行。

x1	x2	s1	s2	Z	RHS	行运算
0	1	2	-1	0	8
1	0	-1	1	0	4	第 2 行 = 第 2 行 – (1/2) * 第 1 行
0	0	20	10	1	400	新第 3 行 = 第 3 行 + 10 * 第 1 行

我们不再在最后一行中包含负值。所以，我们得到了解决方案！

4.8. 步骤 7：解释解决方案

现在我们有了最终的 tableau，基本变量——那些列包含 1 且所有其他条目为 0 的变量——直接从 RHS 给出它们的值。与此同时，非基本变量为零，这意味着它们不直接构成可行解。

从我们最终的 tableau 中，我们得到

$x_1 = 4, \quad x_2 = 8, \quad \text{and} \quad Z = 400$

这告诉我们 Jane 应该在 Job I 工作 4 小时，在 Job II 工作 8 小时，以最大化她的收入，总收入为 $400。

4.9. 特殊情况

在单纯形算法的步骤 4 中，如果不存在有效的旋转行，则目标函数是无界的。

如果在比率测试期间，多行并列，则会随机选择一行，但需要谨慎，因为这可能导致循环。

如果初始 tableau 具有负 RHS 值且无法执行有效的旋转运算，则问题是不可行的。

5. 单纯形算法的伪代码

这是单纯形算法的伪代码

algorithm SimplexAlgorithm(tableau):
    // INPUT
    //    tableau = the initial simplex tableau
    // OUTPUT
    //    optimal solution (if it exists)

    // Step 1: Repeat until the solution is optimal
    while there exists a negative coefficient in the objective row:
        
        // Step 2: Identify the pivot column (entering variable)
        pivotColumn <- index of the most negative coefficient in the objective row
        
        // Step 3: Identify the pivot row (leaving variable)
        // Calculate the ratio of the right-hand side (RHS) to the pivot column value
        // Consider only rows with positive pivot column values
        smallestRatio <- infinity
        for each row i in the tableau:
            if value in pivotColumn at row i > 0:
                ratio <- RHS[i] / value in pivotColumn at row i
                if ratio < smallestRatio:
                    smallestRatio <- ratio
                    pivotRow <- i

        // Step 4: Perform the pivot operation
        // Normalize the pivot row
        pivotElement <- value at (pivotRow, pivotColumn)
        for each column j in the tableau:
            tableau[pivotRow][j] <- tableau[pivotRow][j] / pivotElement

        // Make all other entries in the pivot column zero
        for each row k in the tableau (k != pivotRow):
            factor <- tableau[k][pivotColumn]
            for each column j in the tableau:
                tableau[k][j] <- tableau[k][j] - factor * tableau[pivotRow][j]

    // Step 5: Extract the solution
    solution <- array of zeros with length equal to number of variables
    for each column corresponding to a basic variable:
        if column has a single 1 and all other entries are 0:
            solution[variableIndex] <- value in RHS of corresponding row
    return solution

6. 实现和替代方案

诸如 Python 中的 SciPy、MATLAB 的 linprog 以及 R 的 lpSolve 包提供了单纯形算法的高效实现。

然而，由于其指数时间复杂度，单纯形算法可能难以处理极其大型的问题。在这种情况下，元启发式算法，如粒子群优化或遗传算法，可以提供更快，但近似的解决方案。

此外，近似算法，如内点法，保证在特定范围内（例如，最优值的 10%）内获得接近最优的结果，并且可以更有效地处理大型数据集。

7. 结论

在本文中，我们探讨了单纯形法如何找到线性问题的最优解。最优解始终位于可行域的角点上，而单纯形法通过迭代的方式找到它。

核心概念

操作系统

神经网络

图论

LaTeX

完整存档

关于 Baeldung