为什么simplex算法可以解决线性规划问题

Question

我们知道simplex是一个非常有名的算法，用于解决线性规划问题，我知道如何使用它，但是让我困惑的是为什么simplex总是假定其中一个顶点多面体是最佳解决方案？

Answer 1

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

Answer 2

简而言之，在增加利润的方向上走多面体内部，最终会出现在顶点。非常类似这样的观察：如果你在其中一个角落放置一个盒子，并从上面放一个大理石滚子，它会在这个角落里结束。

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

Answer 3

给出的线性目标函数˚F和多面体P，你可以推理如下。

1. 任何点p在内部P严格的局部最大值不能。取一行L到p，并限制f到L。参数化L作为p + t（q-p）对于某点q和t实数。然后˚F的限制是在吨线性的，并且有一个间隔（A，B）含有0表示吨是有效的。根据的吨系数，去在一个方向或另一个增加f。如果t的系数为0，则尽可能在一个方向上走。
2. P的内部任何点都具有相同的属性，您将行限制在该面上。
3. 走下来的边界simplices，按维度。你最终在一个顶点;局部最大值在顶点。
4. 这并不意味着你选择了正确的路线;单纯形算法的复杂性是如何去正确的方向。