《数学模型》——最大流与最小费用流问题

一、最大流问题

许多系统包含了流量问题，如公路系统中有车辆流、物资调配系统中有物资流、金融系统中有现金流等。这些流问题都可归结为网络流问题，且都存在一个如何安排使流量最大的问题，即最大流问题。下面先介绍最大流问题的相关概念。

1.基本概念

若给定一个可行流f={fij}f=\{ f_{ij} \}f={fij​}，把网络中使$f_{ij}=c_{ij}$的弧称为饱和弧，使$f_{ij}<c_{ij}$的弧称为非饱和弧。把$f_{ij}=0$的弧称为零流弧，$f_{ij}>0$的弧称为非零流弧。

若$\mu$是网络中联结发点$v_s$和收点$v_t$的一条路，我们定义路的方向是从$v_s$到$v_t$，则路上的弧被分为两类：一类是弧的方向与路的方向一致，叫做前向弧。前向弧的全体记为${\mu }^{+}$。另一类弧与路的方向相反，称为后向弧。后向弧的全体记为${\mu }^{-}$。

2.寻求最大流的标号法（Ford－Fulkerson）

从$v_s$到$v_t$的一个可行流出发（若网络中没有给定$f$，则可以设$f$是零流），经过标号过程与调整过程，即可求得从$v_s$到$v_t$的最大流。这两个过程的步骤分述如下:

（1）标号过程
在下面的算法中，每个顶点$v_x$的标号值有两个，$v_x$的第一个标号值表示在可能的增广路上，$v_x$的前驱顶点；$v_x$的第二个标号值记为${\sigma }_x$，表示在可能的增广路上可以调整的流量。

（2）增流过程
①令$v_y=v_t$。
②若$v_y$的标号为$(v_x,{\sigma }_t)$，则$f_{xy}=f_{xy}+{\sigma }_t$；若$v_y$的标号为$(-v_x.{\sigma }_t)$，则$f_{yx}=f_{yx}-{\sigma }_t$。
③若$v_y=v_s$,把全部标号去掉，并回到标号过程（1）。否则，令$v_y=v_x$，并回到増流过程的步骤②