线性规划优化：单纯形法-开发者社区

原文：towardsdatascience.com/linear-programming-optimization-the-simplex-method-b2f912e4c6fd

到目前为止，本系列已经涵盖了线性规划的基础知识。在本文中，我们将从基本概念转向底层的细节！本文将介绍单纯形法，这是解决线性规划问题常用的算法。虽然我们将通过单纯形法手动解决一个简单的线性规划例子，但我们的重点是算法的直觉，而不是记住算法步骤（我们有计算机来处理这类事情！）。

下面是我们将要涵盖的内容：

为什么需要单纯形法
从图形解法转向代数解法
通过一个简单的例子演示单纯形法的工作原理

这是包含我迄今为止为这个系列所写所有文章的列表链接：

线性规划

为什么需要单纯形法

在本系列的第一篇文章中，我们讨论了线性规划的特性，使其仅考虑约束的角点作为潜在的解。这是一个非常强大的特性，将无限解空间缩小到有限解空间。在我们回顾的例子中，我们只有几个约束和变量——我们甚至手动解决了一些！在查看了一些简单例子之后，人们可能会认为，一种彻底的、暴力的（查看每一个角点）方法来寻找最优解是足够的。

对于较小的线性规划问题，暴力法是可行的，但随着问题变得更加复杂，角点的数量可能会急剧增加。总角点数（包括可行和不可行的）是问题中变量数量和约束数量的函数。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/2ea8b10649870276a26b720abcdc9ef2.png

总角点数公式的图像 - 图片由作者提供

下面是一些多变量和约束组合的角点数量增长示例：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/ef01d6d9e3376f4ce6f3fa875998f49c.png

角点数量快速增加 - 图片由作者提供

角点数量的快速增长需要一种更智能的方法来寻找最优解——这就是单纯形法！单纯形法是一种巧妙的方法，只查看所有可能解的小子集，同时仍然保证全局最优结果——我们将在下面进一步探讨细节。

从图形解法转向代数解法

在学习线性规划的基础知识时，查看具有两个决策变量的优化问题的图形表示是非常有用的。我们在第一部分中讨论了这一点。虽然这对理解基础知识大有裨益，但它并不能很好地推广到更复杂的问题。它的实用性基本上限于教学目的。

为了进一步理解 LP，并准备好开始讨论单纯形法的细节，我们需要了解如何将 LP 问题转换成代数格式。

获得代数设置的主要组成部分之一是将约束不等式转换为等式。在 LP（线性规划）的语境之外，没有很好的数学方法来做这件事。但记住，对于 LP，我们实际上只对角点感兴趣？而且所有角点都在线上？因为我们实际上只关心解空间边界，所以我们基本上忽略了不等式！再次强调，这是因为我们本来就不会担心空间边界线之外的区域。

很好，我们只需将所有不等号换成等号，就可以继续了，对吧？但等等！当我们考虑角点时，我们通常不会同时位于所有这些直线上。正因为如此，我们需要添加一种方法来“跳跃”到特定的约束线上。这用语言解释起来有点困难——讽刺的是，我将以图形的方式来解释这个概念…图形化。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/d9d3ac6ab25163c067e2a553d8cb61b5.png

从不等式切换到等式 - 作者图片

好吧，现在看看为什么我们可以将不等式移除为等式——但我们有一个大问题。让我们通过查看特定角点的数学来探讨这个问题：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/6bdbf0c26e5dfa2f01b08761e8e20513.png

作者图片

让我们把所有线性约束的 X₁和 X₂值代入：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/28d6ba4e2594cb887d15bc17906983d2.png

作者图片

我们可以看到，更严格的等式导致 X₁和 X₂的这些值对于第三个约束来说不可行。我们需要一种方法，使我们能够在角点处，同时变量值在所有约束公式中都能工作。

上述问题的解决方案是创建松弛变量。松弛变量被添加到每个等式中，使我们能够一次只考虑一个角点涉及的约束。

我们可以通过将涉及约束的松弛变量设为 0 来“跳跃”到角点。对于不涉及的额外约束，我们可以将松弛变量设为方程的决策变量侧与常数侧之间的差值（或松弛）。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/afcdfbaaa5941f3ac744adebb64f27b1.png

添加松弛变量使我们能够“跳跃”到角点——作者图片

如果松弛变量设为 0，那么约束条件就是我们在考虑的角点中的一个约束条件。如果它不是零，我们知道特定的约束条件不涉及我们正在考虑的角点。

好的，当我们将不等式设为等式并创建松弛变量后，我们就准备好用代数方法解决线性规划问题了。现在让我们深入了解单纯形法如何利用这个设置来高效优化！

注意：当我们讨论上一节中可能角点的数量时，n包括松弛变量，而不仅仅是原始决策变量。

通过简单示例演示单纯形法的工作原理

首先且最重要的是，单纯形法是一种高效地在角点之间移动的算法，它计算角点的目标值，直到找到全局最优解。单纯形法是一种贪婪算法，它会移动到使目标函数增加（对于最大化）或减少（对于最小化）最多的角点。贪婪算法通常因找到次优解而臭名昭著——但是，由于线性规划的特性，单纯形法保证能够找到最优解。

我想花些时间来建立对为什么贪婪算法，如单纯形法，可以找到线性规划的全局最优解的直觉。贪婪算法的定义属性是，它只根据即时信息做出最优决策。通常，一系列局部最优决策不会导致全局最优解——但是，正如我提到的，这并不适用于线性规划。它之所以成立，是因为约束条件的线性要求。让我们看看使用线性函数做出最优决策的例子。

想象我们处于两个函数的交点——我们想要选择一个函数，它将为下一个 x 值提供最高的 y 值。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/5f514086976043a0de1953430bdf165d.png

线性函数中局部最优决策也是全局最优的证明——作者图片

单纯形法使用一个非常类似的方法以贪婪的方式移动到不同的角点。单纯形法的一个关键点是，当找不到更好的相邻角点时，它就会终止。由于解空间的凸性，这个角点既是局部最优也是全局最优。

直观示例

在对单纯形方法的设置有一个一般了解，并对它所做的工作（贪婪地遍历顶点以找到全局最优解）有一个基本了解后——我认为我们准备好开始通过一个例子来工作了。

到目前为止，我们讨论了三个约束条件，但我们还没有建立一个目标函数。为了做到这一点，我们将给出一些系数来赋予 X₁和 X₂，并将所有松弛变量添加上系数 0（这使得优化表完整）。

因此，这是我们将会解决的问题：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/10999551651ad029a057cb2035f99367.png

作者图片

让我们使这组线性方程准备好单纯形。我们将从上面已经讨论过的约束条件开始。它们看起来是这样的：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/70c6df62da99143633c8fd6a06141070.png

作者图片

我们还没有讨论如何修改目标函数以适应单纯形方法。这非常简单，我们将目标值设为Z，并通过代数变换将 0 放在等式右边。它看起来是这样的：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/8bdc25f522b597c5fabf7c72fcb5ee6b.png

作者图片

注意，我们为松弛变量添加了 0，它们对目标函数没有贡献，但这个公式设置将有助于我们开始构建单纯形表。

单纯形表是一个数据表，用于单纯形法遍历顶点并计算它们的自标函数值。它还实现了在找到最优值后停止探索的功能。

单纯形表有一行用于目标函数，一行用于每个约束条件。在算法执行的任何时刻，都有基本和非基本变量。变量在算法进展过程中在这些类别之间切换。基本变量是未设置为 0 的变量，你可以把它们看作是活跃的变量。非基本变量是值为 0 的变量，你可以把它们看作是非活跃的。单纯形法总是从原点开始。在原点，所有决策变量都设置为 0，这意味着只有松弛变量是基本的，即非零或“活跃”的。起始表将显示松弛变量在开始时为非基本。

下面是我们示例的起始表：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/01141d97c71464a8e6a6976845ecd170.png

作者图片

好的，现在我们已经完成了初始设置，我们可以开始单纯形法的第一次迭代了。我们需要开始远离原点——我们通过将一个松弛变量移到非基本变量并拉入一个决策变量到基本解集中来实现这一点。但我们应该移除哪个松弛变量，以及我们应该引入哪个X？

让我们首先确定我们想要使哪个变量成为基本变量。记得我们说过单纯形算法是贪婪的吗？这就是它的用武之地！我们查看 z 行的系数，并选择具有最大负系数的变量。这是一个最大化问题，但记住，我们改变了系数的符号，以在右侧得到 0，所以负号=好，正号=坏。最负的系数与现在可以最大程度增加目标函数的变量相关联。我们的选择是 X₁ 的 -5 和 X₂ 的 -3，所以我们选择 X₁。这被称为进入变量- 幸运的是，这个名字相当直观！

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/3feee6d953849f78ac0867ffdd30f409.png

图片由作者提供

现在，让我们谈谈寻找松弛变量以使非基本或非活动/移除。在单纯形术语中，正在被移除的变量（也是直观地）被称为离开变量。我们想要找到可以设置进入变量的最大值，而不违反任何约束。这意味着我们需要找到与 X₁ 上最紧/最限制性约束相关的松弛变量。我们可以通过计算“解”列和约束的 X₁ 系数的比率来完成此操作。X₁ 的约束系数是 -2、1 和 1，相应的“解”列值是 5、7 和 10。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/af6c46fa10e7787d924a82269d339777.png

S_2 具有最低的非负比率 - 因此它将被选为离开变量 - 图片由作者提供

这里是这种选择的直觉。我们试图找到 X₁ 可以取的最大值，同时与它所属的线性方程组保持一致。对于第一个约束，实际上任何值都可以，因为 X₁ 的系数是负的 - 其他变量可以在任何水平上补偿，以使整体方程等于 5。显然，“任何值都可以”不是一个非常限制性的约束 😄！

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/4e0be9636a16911ffca2561239a0a036.png

图片由作者提供

对于第二个约束，当 S₁ 和 X₂ 都设置为 0 时，X₁ 的最大值将被实现，这个最大值是 7。我们看到，存在其他变量的值可以使线性方程组生效。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/d9e6e2cfb4384cc5553bbc06defd7759.png

存在着一些值，使得线性方程组不会崩溃 - 图片由作者提供

现在，让我们看看我们的最后一个选项，即将 X₁ 设置为 10。这会导致大问题；记住，所有变量都必须 ≥ 0。正如您下面可以看到的，给定 X₁ 的值为 10，无法使第二个约束条件生效。因此，在不违反线性方程组中的任何函数的情况下，我们可以将 X₁ 设置的最高值是 7。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/f4d6f725dbdb7d65a574616e44d0d0fb.png

没有办法使系统在 x1 = 10 的情况下工作 – 作者图片

哇，我感觉我们已经做了很多工作了！我们已经确定了将要引入单纯形表中的变量以及将要离开的变量。现在我们必须更新表来反映这些变化。

在我们深入讨论更新进入和离开变量的表的具体细节之前，让我们快速记录一些关键术语。属于离开变量的行称为主行。属于进入变量的列称为主列。主行和主列的交点称为主元。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/110fc0decba57b2b92edf617657eb204.png

单纯形进入/离开变量术语 – 作者图片

好的，让我们更新这个表以反映我们需要做的更改！第一步是更新 S₂行（因为它是我们为 X₁交换的行，所以需要特殊处理），然后我们需要更新所有其他行。

我们通过将整个行除以主元来更新主行。这样设置行，使得“解”列的值等于 X₁的值。不幸的是，对于这个例子，因为主元是 1，所以看起来没有什么变化（我想我应该选择一个更好的例子……）。但我们将更新“基本”列以显示 X₁现在在基本解中，而 S₂不在。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/975bc63af0ef08399e9470e3c42c5c7a.png

作者图片

所有其他行都会通过这个函数进行修改：

新行 = (当前行) – (其主列系数) X (新主列)

这个函数更新了解列，使得基本变量的值构成一组连贯的线性方程。我们现在就来讨论这个问题。我们将从松弛变量 S₁的行开始。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/b58270dc055369c58d4fcc36064ce918.png

因为引入了 X1 到基本解而修改 S1 – 作者图片

S₁行的数学计算现在“加起来”了。记住，X₁现在等于 7。对应于第一行的约束是 -2X₁ + X₂ + S₁ = 5。在我们的第一次移动之后，这个等式变为 -14 + 0 + S₁ = 5。根据这个公式，S₁必须等于 19，这正是我们现在“解”列中的值。我们将对其他两行执行相同的步骤。这个表是单纯形算法第一次迭代的输出。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/91e21252dd73c9df93fd08c6d69385b4.png

第一次迭代后更新的单纯形表 – 作者图片

现在我们已经完成了第一次迭代，我们开始新的迭代，并遵循与第一次完全相同的步骤。记住，第一步是找到 z 行中最负的数。有趣的是……所有数字都是正的。当 z 行中的所有数字都是 0 或正数时，你目前处于最优点 - 这是单纯形法的停止条件。对于这个例子，我们的最优解是 X₁ = 7 和 X₂ = 0，目标函数值为 35。松弛变量仅具有代数目的，并在找到最优解后丢弃。

为了说明，让我们假设 z 行中有一个负值。类似于这样：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/e6b1fa9a2680717f30ce2dcacd923674.png

假设场景中我们在 z 行中有一个负值 - 作者图片

如果是这样的话，我们会选择 X₂作为进入变量，然后进行以下步骤：(1)选择离开变量，(2)重新计算离开变量的行并将其与 X₂交换，(3)重新计算所有其他行，(4)最后在 z 行中寻找负值，以查看是否找到了最优解，或者是否需要移动到下一次迭代。