【管理运筹学】背诵手册（六）| 图与网络分析（最大流问题，最小费用最大流问题）

本文主要是介绍【管理运筹学】背诵手册（六）| 图与网络分析（最大流问题，最小费用最大流问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

六、图与网络分析

最大流问题

最大流问题的数学规划模型为： $\max v=f_{12}+f_{13}\\ \begin{cases} f_{12}+f_{13}-f_{57}-f_{67}=0 \\ f_{13}+f_{23}=f_{34}+f_{35} \\ ...\\ 0\leq f_{ij}\leq c_{ij} \end{cases}$ 第一个约束表示从起点流出的流量等于流入终点的流量；最后一个为容量限制条件；中间的约束为中间点的平衡条件。

满足容量限制条件和平衡条件（起点、终点和中间点）的网络流称为可行流，可行流总是存在的，如零流。

定义网络 $G$ 中的一条初等链 $\mu$ （所有顶点均不相同），方向为从起点到终点，若链上有弧与 $\mu$ 方向一致，称为前向弧；若有弧与 $\mu$ 的方向相反，称为后向弧。网络中 $f_{ij}=c_{ij}$ 的弧称为饱和弧， $f_{ij}<c_{ij}$ 的弧称为非饱和弧， $f_{ij}=0$ 的弧称为零流弧。

若某条链中所有前向弧非饱和，后向弧非零，称其为一条增广链。

可行流为最大流的充要条件是不存在增广链。

从起点 $v_s$ 到终点 $v_t$ 的最大流的流量，等于分离 $v_s,v_t$ 的最小截集的容量。

寻找最大流的标号法，称为 2F 算法。可分为两个过程，一是标号过程，二是调整过程。

标号过程先给起点标上 $(0,+\infty)$ ，若在前向弧 $v_i,v_j)$ 上， $f_{ij}<c_{ij}$ ，则给 $v_j$ 标号 $v_s,l(v_j))$ ，其中 $l(v_j)=\min\{l(v_i),c_{ij}-f_{ij}\}$ ；若在后向弧 $v_j,v_i)$ 上， $f_{ij}>0$ ，则给 $v_j$ 标号 $v_i,l(v_j))$ ，其中 $l((v_j)=\min\{l(v_i),f_{ij}\}$ 。

调整过程的调整量为终点的标号，令前向弧加上这个调整量，后向弧减去这个调整量。

当出现有多个收发点时，可以虚拟一个总发点和总收点或把所有收发点看成一个整体，先解决外部的流量分配，再解决整体内部的流量分配。当网络为无向图时，可以考虑用枚举法用最小截求最大流。标准的最大流问题应只有弧有容量限制，当出现某个节点也有容量限制时，应进行转换，将其分为两个节点 $\lambda,\mu$ 。原来流入的弧全部连接到 $\lambda$ ，原来流出的点全部从 $\mu$ 节点流出。

最小费用流

链的费用为链中前向弧的费用减去后向弧的费用。所有增广链中费用最小的链称为最小费用增广链。

定理：若 $f$ 是流量为 $V (f)$ 的最小费用流， $\mu$ 是关于 $f$ 的从 $v_s$ 到 $v_t$ 的一条最小费用增广链，则 $f$ 经过 $\mu$ 调整流量后得到新的可行流 $f^{'}$ ， $f^{'}$ 一定是流量为 $V(f)+\theta$ 的可行流中的最小费用流。