图与网络分析 Graph Theory and Network Analysis 网络流(Flow)与最大流问题 最小费用大流问题 前面讨论的旅行社的计划问题中,旅行社解决了将尽可能多的 游客(86人)送往了目的地—北京,但旅行社计划时没有考虑机 票的成本。现在旅行社考虑的问题是既要送出尽可能多的游客(86 人),又要使机票的总成本最低,应该如何制定新的计划呢?这就 是最小费用大流所研究解决的一类流量问题。 最小费用大流问题还广泛应用于诸如最优匹配,运输问题等一 类问题。 应该注意的是:最小费用大流问题首先要解决网络上的最大流 ,目的是寻找使总费用达到最小的那个最大流