企业官网建设流程全解析

怎样建设小游戏网站,如何优化关键词提升相关度,公司网站建设设计方案,怎么样自己做网站赚钱年入40万原文#xff1a;towardsdatascience.com/linear-programming-optimization-the-simplex-method-b2f912e4c6fd 到目前为止#xff0c;本系列已经涵盖了线性规划的基础知识。在本文中#xff0c;我们将从基本概念转向底层的细节#xff01;本文将介绍单纯形法#xff0c;这是…原文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.pngS_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 行中寻找负值以查看是否找到了最优解或者是否需要移动到下一次迭代。结论在本文中我们深入探讨了单纯形法的细节。我认为理解细节很重要但也不应忽视整体。特别是你永远不会在实际情况中手动解决线性规划问题。本文的几个关键要点如下单纯形法是一种使用代数解决线性规划问题的算法在使用单纯形法之前需要将目标和约束公式重写为带有松弛变量的等式单纯形法通过贪婪搜索找到对目标函数贡献最大的变量进行优化 - 然后将该变量设置为尽可能高单纯形法在找不到任何可以改进目标函数的变量后停止 - 这使得单纯形法可以提前退出问题并得到最优解 - 而无需探索所有角点