第五节 最小费用最大流流问题 在在实实际际的的网网络络系系统统中中，当当涉涉及及到到有有关关流流的的问问题题的的时时候候，我我们们往往往往不不仅仅仅仅考考虑虑的的是是流流量量，还还经经常常要要考考虑虑费费用用的的问问题题。比比如如一一个个铁铁路路系系统统的的运运输输网网络络流流，即即要要考考虑虑网网络络流流的的货货运运量量最最大大，又又要要考考虑虑总总费费用用最最小小。最最小小费费用用最最大大流流问问题题就就是是要要解解决决这一类问题。这一类问题。最小费用最大流问题提法最小费用最大流问题提法:设 设一 一个 个网 网络 络G G= =（ （V V， ，E E， ，C C） ）， ，对 对于 于每 每一 一个 个弧 弧( (v vi i ,v ,vj j ) ) E E , ,给 给定 定容 容量 量c cij ij外 外， ，还 还给 给出 出单 单位 位流 流量 量的 的费 费用 用d dij ij 0 0 ， ，网 网络 络记 记为 为G G= =（ （V V， ，E E， ，C C， ，d d） ）。 。网 网络 络系 系统 统的 的最 最小 小费 费用 用最 最大 大流 流问
