如果您是工科学生或工程师，您就会知道优化系统以获得最佳结果意味着什么。
优化解决方案是从构建桥梁到制作软件的一切成功的关键。
基本可行解的想法就在此时产生了。
这是线性规划中的一个基本思想，可以让您找出一组可能的解决方案中的哪一个是最好的。
但为什么它如此重要？在本文中，我将讨论基本可行的解决方案以及如何使用它们来解决现实世界中的工程问题。
我将讨论如何找到它们、它们由什么制成以及它们为何重要。
因此，无论您是经验丰富的工程师还是刚起步的学生，都请与我们一起深入了解基本可行解的世界，并向您展示如何使用线性规划的强大功能。
了解基本可行的解决方案
正式定义：
所有变量均为非负的线性规划模型的基本解。
基本可行解 (BFS) 是线性规划中的一个关键思想，可帮助找到最佳解。
BFS 是具有尽可能少的非零变量的解决方案。
它是可行解多面体的一个角。
换句话说，BFS 是满足非负约束并且在可行域或问题域中的基本解。
寻找最优的基本可行解
为了找到最好的 BFS，我们需要做以下事情：
- 以标准形式为线性序列编写程序。
- 将不等式系统变成增广矩阵。
- 弄清楚哪些变量是基本的，哪些不是。
- 根据其他变量找出基本变量是什么。
- 将这些表达式放入目标函数中以获得仅包含非基本变量的函数。
- 找到一个可以在不破坏任何约束的情况下增加的非基本变量，这将使目标函数更好。
该变量现在是基本变量，其他基本变量之一不再是基本变量。
如果存在最佳解决方案，则它必须位于可能存在解决方案的区域的末端或顶点之一。
因此，如果 LP 有最优解，则它在可行集的极值点处有最优解。
此外，如果存在最优解，则始终存在最优 BFS。
使用单纯形法寻找最佳 BFS
单纯形法是一种用于解决线性规划问题的算法。
它通过使用枢轴过程从一个 BFS 移动到“相邻”BFS。
在主元过程中，选择一个非基本变量成为基本变量，然后使用当前 BFS 求解新的基本变量。
当不能改变非基本变量以使目标函数更好时，算法就完成了。
为什么基本可行的解决方案对于解决复杂的工程问题至关重要
还是很难理解？让我稍微改变一下观点：
无论如何，谁需要简单、可行的答案？把一切都放在一起，希望最好的。
毕竟，当混乱如此有趣时，谁还需要优化呢？欢迎来到非负变量的世界，这里的一切都只是建议，几乎可以肯定会失败。
或者是吗？
让我们探讨为什么基本可行解决方案看似基本的概念根本不是基本概念，以及为什么它们可能只是解决最复杂工程问题的关键。
好吧，那只是一个看起来像电视广告的笑话。
现在让我们回到解释。
寻找基本可行的解决方案
基本可行解 (BFS) 是线性优化问题的解，它满足所有约束并且具有最少数量的非零变量。
从几何角度看，每个 BFS 都是可行解多面体的一个角。
如果有最佳解决方案，则还必须有最佳第一步。
在本文中，我们将讨论如何找到初始基本可行解、如何找到所有基本可行解以及如何找到没有松弛变量的基本可行解。
寻找初步的基本可行方案
我们可以根据问题的设置方式使用不同的方法来找到适用于线性优化问题的初始基本解决方案。
一种方法是将松弛变量添加到不等式的约束中，并将所有其他变量设置为零。
松弛变量成为基本变量，其余为非基本变量。
两相单纯形法是解决该问题的另一种方法。
该方法涉及解决额外的线性规划问题以找到可行的初始基本解决方案。
一旦找到初始的基本可行解，就可以使用单纯形法从一个基本可行解移动到下一个，然后移动到最佳解决方案。
寻找所有基本可行的解决方案
可以有不止一种适用于线性程序的基本解决方案。
我们可以通过添加松弛变量来改变系统，然后使用新系统来寻找线性规划的所有基本可行解。
然后，利用这些基本可行解来寻找原问题的基本可行解。
寻找没有松弛变量的基本可行解
我们需要使用松弛变量来摆脱小于约束，这样我们就可以找到一个没有松弛变量的基本解决方案。
松弛变量只是约束右侧和左侧之间的差异。
例如，对于第一个约束，我们定义一个松弛变量 x4 = 14 - 2x1 - x2 - x3。就这个新变量而言，第一个约束简单地等同于 x4 ≥ 0，这是 x4 的正约束。
当我们添加这些松弛变量时，我们得到一个与原始程序相同的线性程序，除了所有约束都是方程式或表示某些内容为正的约束。
在基本解中具有非零值的基本变量集称为基础。
在基本解中值为零的变量不是基本变量。
为了找到最佳解决方案，我们需要找到满足所有规则并获得目标的最大或最小值的向量 x。
但是找到最佳解决方案比仅仅找到一个有效且没有松弛变量的解决方案需要更多的步骤。
并非总能找到没有松弛变量的基本解决方案，尤其是对于小于约束的问题。
要找到基本可行解，需要使用单纯形法或其他线性规划算法来寻找满足所有约束且具有最少非零变量的解。
基本可行解的性质及意义
基本可行解的性质
一个基本可行解最多有 m 个非零变量，至少有 nm 个变量为零，其中 n 是决策变量的数量，m 是约束的数量。
BFS 是可能解多面体的一个角，每个 BFS 都有 n 个线性独立的活动约束。
如果有最佳解决方案，则还必须有最佳第一步。
基本可行解最重要的是它们是线性规划问题凸解集的末端。
为了找到最佳答案，单纯形算法会经过一系列 BFS。
Simplex Algorithm 以有组织的方式搜索所有基本可能的解决方案，以找到最佳解决方案。
基本可行解的意义
找到可能的基本解决方案很重要，因为它有助于找到线性规划问题的最佳答案。
它还为复杂算法提供了一个起点，并可用于确定线性程序是否可能。
要找到线性规划的所有基本可行解，您可以通过添加松弛变量来更改系统，然后使用更改后的系统找到所有基本可行解。
然后，利用这些基本可行解来寻找原问题的基本可行解。
视频：基本可行的解决方案
提示：如果需要，请打开字幕按钮。如果您不熟悉口语，请在设置按钮中选择“自动翻译”。在您最喜欢的语言可供翻译之前，您可能需要先点击视频的语言。
用例
| 用于： | 描述： |
|---|---|
| 资源分配： | BFS可以用来将有限的资源分配到几个项目中，做到事半功倍。这种方法可以用于许多不同的领域，如交通、农业和金融。 |
| 网络优化： | BFS 可用于使通信、运输和物流网络更好地工作。BFS 可以帮助找到货物和服务的最佳路线，减少运输时间和金钱，并加快和更准确地交付。 |
| 生产计划： | BFS 可用于计划生产，以便以最佳方式使用劳动力、原材料和设备等资源，以充分利用它们。BFS 可以帮助降低生产成本、减少浪费并提高效率。 |
| 金融计划： | 在财务规划中，BFS 可用于优化投资组合、降低风险并获得最大的回报。BFS 可以帮助找到最好的资产分配方式，降低交易成本，赚更多的钱。 |
| 供应链管理： | 作为供应链管理的一部分，BFS 可用于改善从供应商到客户的商品和服务流。BFS 可以帮助确定手头的最佳库存量、缩短交货时间并改善客户服务。 |
结论
随着对基本可行解决方案的了解接近尾声，很明显它们是任何工程师或工程专业学生的重要工具。
从找出构建复杂系统的最佳方法到充分利用可用资源，基本可行的解决方案为获得最佳结果提供了一个框架。
但不仅仅是有用，它们还展示了数学是多么优雅和美丽。
令人惊奇的是，您可以将复杂的问题归结为一组简单的方程式，然后使用这些方程式来解决现实世界中的问题。
这是一个很好的提醒，工程就是解决问题，并且通过使用数学的力量，我们可以找到曾经被认为不可能的答案。
因此，随着您对工程学的了解越来越多，请牢记您所学到的有关有效的简单解决方案的知识，并使用它们使世界变得更美好、更高效。
链接和参考
图书：
- 线性规划：基础和扩展
- 线性规划：理论与应用
分享…
