『运筹OR帷幄』转载
文章作者：休语
编者按：本文整理自休语的知乎文章，文章主要围绕最小流问题进行阐述，结构主要为问题描述，模型建立，解的性质，特殊案例及网络单纯形法的求解。
问题描述
（1）网络：有向且连通。
（2）边：根据边上的流量，我们可以分为
- 最大流问题：容量限制
- 最短路径问题：费用作为边的权重
（3）节点：至少有一个（可以有多个）节点是供应点（supply node）或者需求点（demand node）
（4）其他：
- 弧的容量充分，支持供应点到需求点的所有流
- 每条弧上的费用与流量成正比。
（5）目标：给定需求，通过网络发送的总成本最小。
输入整个网络的流量是不变的，但是中间节点可以看成是处理设施，处理的费用累加在边的运输费用上。
模型建立
解的性质
因为cost
不在约束里面，所以所有BF解都是整数解只要求约束中出现的两类量为整数，即
和
为整数。
特殊案例
以下四个问题是特殊的最小费用流问题
- 运输问题：没有中间节点，边的流量没有上界约束。
- 指派问题：每个节点的 为 1或-1
- 转运问题（Transshipment Problem）：没有上界约束
- 最短路径问题：
- 除了起点（source）出发和汇入目的地（target）的边，其它边变成双向边
- 距离是cost ，没有容量（capacity）限制
- 最大流问题
- 不考虑费用，
- 选一个网络最大流量的上界 ，设Supply node为 ，demand node为
- 从supply node到demand node画一条“分流线”，分走多出来的流量 。“分流线”的 ，容量无穷大。
具体案例
前面我们已经对最小流费用问题做了简单的叙述，对于这类问题到底如何解，下面我们对一种经典解法进行描述，即网络单纯性法。
基础：上界法（Upper Bound Technique）
在运筹学建模中，我们经常有约束
。通常地，把该约束当做非负约束（nonnegative constraints）处理，会比当成函数式约束（functional constraints）处理节省计算量。我们可以做如下替换：
经过上述处理后，单纯形法中出基条件则变为了超出上界或者下界。当入基变量不断增大以至于某个
达到上界
时，用
替换。
那么上界法和最小费用流问题有什么联系呢？最小费用流问题中的约束通常分有两种：节点约束和边约束。节点约束是函数式约束，通常可以表示为
，边约束表示为
。我们可以用上界法对约束进行转换，提高计算效率。
网络单纯形法——上界法转换
网络单纯形状法和上界法的思路类似。对于
这样的增补决策变量（complementary decision variables）有一个很好的解释，如下图所示。
如下公式所示，
和
的变化其实就是上界法中把
代入到
，导致等式右侧
的变化。
最终网络流如下图所示：
是从i到j能够减少的流量，
是表示每减少单位流量，就能节省
的成本，
的上界
，是因为最多只能减少10（
流量分配了10）。
如上所述，只适用于有上界约束的情况，对于边上的流量没有上界约束的情况来说没有必要。
网络单纯形法——求解
对一个网络图来说，找到一个生成树就是找到了一组基解。
将非基变量置为0，可以解出每条弧上的流量，满足
和
的生成树就是可行生成树，对应基可行解。
网络单纯形法计算示例：
入基变量的选择
那么在求解中，哪个非基变量从0开始增加，会使得目标函数Z增加得最快？且在网络单纯形法中，每增加一个非基变量（一个arc），会形成一个环。环中同向arc增大，反向arc减小。如下图所示：
对这个变化，求一个整体的变化量
。对于每个可以加入的arc，找到这样的一个环，假设入基arc增加的流量为
，看整体的
是多少。其中能够增加单位流量，
下降最大的非基变量（arc）是我们需要选择的。
迭代选择出基变量和下一个可行解。注意，根据上界法，当某一条arc达到上界时，通过
代换得到反向arc，这样
，正常出基。
原文链接
https://zhuanlan.zhihu.com/p/73401547
https://zhuanlan.zhihu.com/p/73527137
,
