单纯形法和网络单纯形法有什么区别？

Question

我正在使用网络单纯形来解决有向图中的最大流问题。 为了比较几种路由算法的执行时间，我需要使用 Dantzig 单纯形法 George 的实现。

我的问题是：单纯形法能否解决给定有向图中的最大流问题？

有没有很好的文档解释图论中的单纯形法？

Answer 1

网络单纯形法是一般单纯形法的高度专业化形式：它只能解决网络问题。

当然，线性规划的标准单纯形法也可以解决网络问题，只需将网络问题表述为LP问题即可。

为了比较，您可能想看看 Cplex：它都有用于线性规划的（原始和对偶）单纯形法和网络单纯形法的实现。

有趣的是，Gurobi 没有网络单纯形法。这背后的想法是，LP 求解器变得如此之快，以至于专用网络求解器失去了一些速度优势。

一个很好的参考是：Ahuja、Magnanti 和 Orlin，网络流。