根据个人经验，我会说单纯形方法比内点方法更容易理解如何实现，这是基于在 MATLAB 中实现原始单纯形法和基本内点法作为参加线性编程课程的一部分的个人经验. 原始单纯形的主要障碍是确保正确实施第一阶段和第二阶段，以及正确实施反循环规则。实现线性规划的内点方法的主要障碍往往更多是关于正确实现迭代方法，并相应地缩放障碍参数。

您可以在线性规划教科书中找到对每种算法优缺点的更完整讨论，例如Bertsimas 和 Tsitsiklis的线性优化简介。（免责声明：我从这本教科书中学习了线性编程，并在麻省理工学院从 Bertsimas 的妻子那里学习了线性编程。）以下是一些基础知识：

单纯形的优点：

• 给定决策变量，通常会在次操作中以个主元收敛。$n$$O(n)$$O(n)$
• 利用问题的几何：访问可行集的顶点并检查每个访问的顶点的最优性。（在原始单纯形中，降低的成本可用于此检查。）
• 适合小问题。

单纯形的缺点：

• 给定决策变量，您总能找到一个问题实例，其中算法需要操作和枢轴才能得出解决方案。$n$$O(2^{n})$
• 对于大问题来说不是很好，因为旋转操作变得昂贵。像 Dantzig-Wolfe 这样的切割平面算法或延迟列生成算法有时可以弥补这个缺点。

内点法的优点：

• 多项式时间渐近复杂度为，其中是算法输入的位数。$O(n^{3.5}L^2\log{L}\log\log{L})$$L$
• 更适合大型稀疏问题，因为算法所需的线性代数更快。

内点法的缺点：

• 它并不那么直观地令人满意，因为你是对的，这些方法不访问顶点。他们在内部区域徘徊，成功时会聚在一个解决方案上。
• 对于小问题，单纯形法可能会更快。（您可以构建病理案例，例如 Klee-Minty 立方体。）

答案很简单。从算法的角度来看，它们（单纯形法和内点法）都是一个成熟的领域。他们都在实践中工作得很好。IPM（内点方法）的良好声誉是由于其在最坏情况下的多项式复杂性。对于具有组合复杂性的单纯形，情况并非如此。然而，组合线性规划在实践中几乎从未发生过。对于非常大规模的问题，IP 似乎要快一些，但不是必须的规则。在我看来，IP 可以很容易理解和实施，但可以肯定的是，其他人可能不同意，这很好。现在，在 LP 中，如果解决方案是唯一的，它肯定是在一个顶点中，（IP 和 Simplex 在这里也做得很好）。在这种情况下，解决方案也可以在多面体的面上或边缘上，相邻顶点是（或顶点是）也是一个解决方案（同样，IP 和单纯形都很好）。所以它们几乎是一样的。