摘要交通问题与城市经济发展和居民生活情况息息相关，建立并健全以交通网络为基础的交通运输费用优化模型显得尤为重要。因为这是除了产品的成本，加工，推广以及销售以外，还可以使得经济效益达到最大化的有效途径之一。87195

本文主要叙述了在运筹学的总体思想下，运用图论模型和标号算法在交通运输网络中选取最短路径或者最优路径，从而达到我们所希望的路径最优、费用最优的目的。并且结合该模型和算法针对沃尔玛公司物资运输的一个实例展开分析和解决，从而使得该公司能够在最少费用的情况下取得最大的利益。

目前该研究存在的大部分问题都只是单单从运筹学的角度上建立普通的线性规划方法来解决相关问题，而没有结合图论以及数学建模两个方面的知识来解决更加贴合实际情况的交通运输问题。

考虑到目前该研究存在的问题，所以本文结合了图论以及数学建模等方面的知识和模型来研究交通运输问题在最优化模型上的体现。在此我将该问题分为三个部分来讨论：

第一部分：交通运输网络的图论模型的建立；

第二部分：网络赋值流的在交通运输上的最大化问题；

第三部分：在交通运输最短路基础上的费用最优问题的解决。

毕业论文关键词：网络赋值流；最短路；最优费用

Abstract Traffic problem is closely related to urban economic development and residents' living conditions。 It is particularly important to establish and improve the optimization model of transportation cost based on traffic network。 In addition to the cost of products, processing, marketing and sales, transportation optimization is also one of the effective ways to maximize economic benefits。

This paper mainly describes the use of graph theory and labeling algorithm in transportation network in selecting the shortest path and optimal path to achieve the purpose we want the optimal path, the optimal cost, in the overall thought of operational research。 Using the model and the algorithm to analyze and solve the problem of material transportation of the Wal-Mart Store Inc, which makes the company can get the maximum benefit at the minimum cost。

Most of the problems currently existing in the present study are just only from operations research perspective establish ordinary linear programming method to solve the problem without the combination of knowledge of graph theory and mathematical modeling to solve the transportation problem more fitting the actual situation。

Considering the problems existing in the research, this paper combines the knowledge and model of graph theory and mathematical modeling to study the expression of traffic and transportation problems in optimization model。 In this paper we pided into three parts to discuss:

The first part: The establishment of graph theory model of transportation network;

The second part: The maximization problem of network assignment in transportation;

The third part: The solution of the cost optimization problem based on the shortest path of transportation。

Keywords: Network flow; The shortest path; The optimal cost

目  录

第一章 绪论-1

1。1 研究背景-1

1。1。1 交通运输费用最优问题研究意义-1

1。1。2 交通运输费用最优问题国内外研究现状与发展-1

1。2 本文的主要内容-2

1。3 研究方法-3

  1。4 图与网络流相关知识3

    1。4。1 图的概念3

    1。4。2 网络与流4

    1。4。3 可行流与最大流4

第二章 交通运输网络的图论模型建立与最大流问题8