摘要：在各种网络流量的相关问题中结合了最大流和最小费用流这两种问题的情况是在研究中非常重要的问题之一。它不仅包含网络流中的最小费用问题，而且还涉及最大流问题。它可以说是网络流量中的一个难题。人们之所以对最小费用最大流问题的有着极其浓厚的研究兴趣是因为这类问题是和人们的日常生活结合的非常深的，因为它在很多方面上都有到过运用。日常生活中，宅男宅女们喜欢网上购物，就伴随着，物流量等信息。节假日，拼命工作了很久的上班族们终于有了休息的时间，可以到处旅游。各大景区就有了庞大的人流量。日常出行，会遇到早高峰，晚高峰的道路拥堵问题，也就是涉及到了车流量问题。这些都是现实生活中可以处处见到的一些相关的问题。以及一些需要通过数字表达的类似问题，在计算机网络中，工程项目中，等其他较为前沿领域的应用问题，随着越来越多的人投入到对最小费用最大流的相关问题的研究，逐渐的积累了众多的理论基础，及实际应用。得到了众多的理论模型。并且不仅仅是在理论上研究问题，也在实际生活的得以运用。本文的研究的是建立在一些已有的理论基础上进行研究。也就是借助前辈的力量。对最小费用最大流的问题有更深一步的理解，对于一些算法的理解，并且得出新的解决问题的算法。在现实生活中寻找到了一些及其有意义的例子，可以说是一些最经典、最困难的最小费用最大流问题，在一些相关的算法把为题的最优方案找到。在本文中，我们提出了一个最小费用最大流问题的标签算法。并通过一个工厂运输货物的实例，对算法进行了一次测试。最后，通过编程，利用计算机实现了最小费用最大流问题的号算法。

关键词:容量—费用网络图;最短路;最大流;最小费用;最小费用最大流量。

abstract：It is one of the most important problems in the research that the most current and the least cost flow are combined in various network traffic related problems. It involves not only minimal cost in network flows, but also maximum flow. It can be said that network traffic in a difficult problem. The reason why people have a very strong on minimum cost maximum flow problem of research interest because of this kind of problem is combined with People's Daily lives is very deep, because it has been used in many ways. In daily life, women who stay indoors for a long time like shopping on the Internet. During the holiday season, those who have been working hard for a long time finally have time to rest and travel. Every major scenic area has a huge flow of people. When I travel daily, I will encounter the problem of traffic congestion in the morning peak and the evening peak, that is, the problem of traffic flow. These are all related problems that can be seen everywhere in real life. And need some similar problems, through digital expression in computer network, the engineering project, and other frontier issues in the field of application, as more and more people into the minimum cost maximum flow problems related to research, gradually accumulated many theoretical basis, and practical application. Many theoretical models are obtained. And not only in theory, but also in real life.

The key point of this paper is to use graph theory to solve the minimum cost and maximum flow network flow problems. Finally, the application of minimum cost and maximum traffic in network coding is given.

Keywords:Capacity  -  cost  network  diagram;  The  short  circuit;  Maximum     flow;Minimum cost; Minimum cost maximum flow

目录

一绪论 6

1.1课题的目的和意义 6

1.2国内外研究状况及发展趋势