第4章 物流运输路径规划.ppt

第4章 物流运输路径规划 4.1 图与网络的基本概念 4.2 最短路径问题 4.3 运输流量问题 4.4 单回路运输路线问题 4.5 多回路运输路线 第4章 物流运输路径规划 本章重点： 图论是运筹学的一个分支，是建立和处理离散数学模型的一个重要工具。本章中学生要了解图论的基本概念，掌握最短路径问题的狄克斯屈标号法和运输流量问题的福特—富尔克逊标号法，了解单回路运输路线问题和多回路运输路径。 4.1 图与网络的基本概念 图论（Theory of Graphs或Graph Theory）是应用非常广泛的运筹学分支，是建立和处理离散数学模型的一个重要工具。图论的起源最早可追溯到1736年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文。直到20世纪中叶，随着离散数学和计算机技术的发展，图和网络的研究更是得到了飞速发展。目前，网络分析的理论已经在工程设计、管理科学、交通规划、通信网络规划等众多领域中得到广泛应用，并取得了丰富的成果。 4.1 图与网络的基本概念 4.1.1 图和图解 1. 图的基本结构 首先看一个图的实例。图4-1是某地7个村镇之间的道路交通示意图，点①、②、③、④、⑤、⑥、⑦分别表示7个村镇，各村镇之间的连线称为道路。 （1）结点用来表示物理实体或事物，一般用vi来表示。例如，图4-1中的结点就是各村镇。 （2）边是结点间的连线，表示两结点之间的关系，一般表示为e =（vi，vj）。 4.1 图与网络的基本概念 2. 无向图和有向图 若某一图中所有边之间都没有方向，则称该图为无向图。无向图一般用G=（V，E）表示，其中，V = {v1，v2，…，vn}表示点的集合，E = { eij } 表示边的集合。 若某一图中所有边都有方向，则称该图为有向图。在有向图中，有方向的边又称为弧。有向图用D=（V，A）表示，A = { aij } 表示弧的集合，其中a = （vi，vj）。 4.1 图与网络的基本概念 3. 图解 若用平面上的点表示图G的结点，用连接相应的结点而不经过其他结点的线表示图G的边，所画出的图形称为图G的平面图解，简称图解。由于对结点的位置和边的形状的选取具有随意性，因此一个图可以有几种形状迥异的图解。图4-2（a）和（b）为同一个无向图的图解，图4-2（c）和（d）为同一个有向图的图解。 4.1 图与网络的基本概念 4.1.2 几个基本概念 1. 端点，关联边，相邻。若有e = （vi，vj），则称vi，vj是e的端点，称e是vi，vj的关联边。若点vi与vj跟同一条边相关联，则称点vi与vj相邻，若边ei与ej有一个公共端点，则称边ei与ej相邻。 2. 环，多重边，简单图。若一条边的两个端点是同一结点，则称该边为环；若两个端点之间不止一条边，称为具有多重边；无环也无多重边的图称为简单图。以下讨论的图多指简单图。 4.1 图与网络的基本概念 3. 次，奇点，偶点。点v的关联边的数目称为点v的次。次为奇数的点称为奇点，次为偶数的点称为偶点。图4-2（a）中v1的次为3，所以是奇点；图4-2（c）中v1的次为2，所以是偶点。 4. 链，圈，路。一个图中相邻结点与相邻边的序列{v1，e1，v2，e2，…，en-1，vn}称为一条从v1到vn的链μ。若v1与vn重合，则该链为闭链，在一个闭链μ中，若任意两点均不同，且所有的边也均不相同，则称μ为一个圈。若交替序列是有向图D =（V，A）的一条链，则称μ是图D的一条从v1到vn的路。 4.1 图与网络的基本概念 5. 连通图。在一个图种，若任意两点之间至少存在一条链，则称该图为连通图，否则称为不连通图。图4-1和图4-2都是连通图，而图4-3不是连通图。 6. 网络，权。一个图连同定义在其边集上的实函数w（vi，vj）一起称为一个网络。网络一般是连通图。记wij=w （vi，vj），称为边（vi，vj）的权数。 4.2 最短路径问题 4.2.1 狄克斯屈标号法 该法是Dijkstra在1959年提出的，适用于所有权数均为非负（即一切wij≥0）的网络（对于负权网络，该法有时失效），能够求出网络的任一点到其他各点的最短路，使目前求这类网络最短路的最好算法。 该法直接在网络上对每一个点标号，标号分为两种：临时标号T（vj）和固定标号P（vj）。在网络中，固定标号以带括号的数字表示，临时标号不带括号。网络中一个点的临时标号表示从始点到该点的最短路长的上界，固定标号表示最短路长。在标号过程中，临时标号不断被新的更小的临时标号所替代，直到不能再减小为止，就得到该点的固定标号。计算步骤如下： 4.2 最短路径问题 （1）给始点标固定标号（0）； （2）给与（0）点相邻的各点标上临时标号，标号数值为始点固定标号值加上始点到该点间边的权数； （