algorithm - 单纯形算法 - 为什么这么复杂？

Question

最近有人介绍了用于优化线性问题的单纯形算法。我想我明白它是如何工作的，但我不知道为什么这么复杂。

1. 为什么我们必须使用数据透视表行/列/元素。如果我没看错的话，这只是高斯消元法，它按特定顺序消元。为什么顺序很重要？是由于数字噪声吗？如果一切都经过精确计算，那么顺序应该不重要，对吧？

2. 在我目前遇到的所有示例中(为了公平起见，数量不多)所有松弛变量最终都设置为零。为什么我们首先引入它们而不是直接将所有不等式重写为方程式？

Answer 1

1. 旋转不是高斯消元法。画面在枢轴之后的零可能与枢轴之前的零一样多。选择旋转顺序是为了保持单纯形约束(始终从可行空间的一个顶点移动到另一个顶点)，并高效地这样做(通过在每次移动时沿着目标取得最大进展)。
2. 对于约束解决方案的约束，松弛变量为零。听起来您查看的问题没有任何非约束性约束。