algorithm - 为什么单纯形算法适用于解决线性规划

Question

我们知道单纯形是一种非常著名的用于解决线性规划问题的算法，我也知道如何使用它，但令我困惑的是，为什么单纯形总是假设多面体的一个顶点是最优解？

Answer 1

简而言之，沿着增加利润的方向进入多面体，你最终会到达一个顶点。很像这样的观察：如果你把一个盒子放在它的一个角上，让一个大理石从顶部滚动，它最终会在这个角落里。

有一种情况需要考虑，当你在垂直于利润增长线的一侧停止行走，那么这一侧的所有点都是最优解。因此，您可以选择这一侧的任何顶点。

Answer 2

我觉得你可以参考几何，尤其是解析几何。单纯形算法实际上意味着最优的结果总是停留在顶点而不是在直线或面中，非常直观。

Answer 3

给定一个线性目标函数f和一个多面体P，您可以进行如下推理。

1. P内部的任何点p都不能是严格的局部最大值。取一条线L通过p，并将f限制为L。对于某个点q和t实数，将L参数化为p + t(q - p) 。那么f的限制在t中是线性的，并且存在一个包含 0 的区间 (a, b) ，其中t有效。根据t的系数，朝一个方向或另一个方向前进以增加f。如果t的系数为0，只要朝一个方向尽可能远。
2. P面内部的任何点都具有相同的属性，您可以将线限制在该面上。
3. 逐个维度地遍历边界单纯形。你最终到达一个顶点；局部最大值在顶点。
4. 这并不意味着您选择了正确的路线；单纯形算法的复杂性在于如何走向正确的方向。