运筹学第六章-网络规划与网络分析.pptVIP

“运筹学 ”编写组 2008年12月 第六章 网络规划与网络分析 内 容 概 述 图论是目前运用十分广泛的运筹学分支之一。自1736年著名数学家欧拉(Euler)解决了有名的哥尼斯堡七桥问题以来，图论取得了十分迅速的发展。 如今，图论已广泛应用于计算机、物理学、化学、控制论、信息论、管理科学、经济科学等各领域，用以解决各种各样的决策问题。 概 述 生产、科研、工程项目以及实际生活中的许多问题都可以运用图论的理论与方法来解决。例如， 在生产的组织与管理中，为了完成某项生产任务，各工序之间如何衔接，才能使任务完成得既快又好？ 在城市水、电、煤气供应问题中，管道与供电线路如何铺设，才能做到既满足要求，又使总费用最省？ 像球队循环比赛问题、通讯网络、交通运输网络等问题也都可以运用图论的方法来解决。 概 述 随着科学技术的进步，特别是电子计算机的出现与发展，图论得到更迅速的发展和广泛应用。它把一个庞大而复杂的工程系统和管理问题用图来描述，可以解决许多工程设计和管理决策的最优化问题。诸如上述求完成工程任务的时间最少，距离最短，费用最省等。 可以这样说，在任何一个研究对象中，凡是可以把其中的物件抽象地用一组点来表示，把各个物件之间的联系用点间的连线来表示的问题，图论几乎总是一个很有用的工具。 6.1 图与网络 自然界和人类社会中许多事物以及事物之间的关系，都可以用点和线连接起来的图形来描述。例如用点表示城市，点间联线表示城市间的道路，就可描述城市间的交通，如果联线旁标注城市间的距离——网络图中称为权，形成加权图，就称为网络图，就可进一步研究从一个城市到另一个城市的最短路径；或者标上单位运价，就可分析运费最小的运输方案。 例6-1 图a) 表示5个球队之间的赛事关系。其中点a,b,c,d,e,f 分别表示5个球队，两点的连接表示两球队之间的赛事关系。 因此，从图中可反映出a球队分别与b，c，d 球队有赛事；球 队还与 c球队，d球队还与e球队有赛事。 图6-1是由点及不带箭头的连线所组成的图形。 为区别起见，把两点间不带箭头的连线称为边，带箭头的连线称为弧。 由此看出，用图来描述事物间的联系，不仅直观清晰，便于统观全局，而且网络图的画法简便，不必拘泥于比例和曲直。总之，这里所讲的图是反映对象之间关系的一种工具。这样的例子也很多，电路网络、城市规划、信息传递、物质结构、物资调配等也都可以用点和线连接起来的图进行模拟。 一、无向图 定义6-1 无向图是一个有序二元组（V，E），记为G=（V,E），其中V=(v1， v2，…，vp)是p个点的集合，简称定点集；E=（e1， e2，…，eq）是条边的集合，简称边集合，并且是一个无序二元组，记为 。 边数 ：边集 E中元素的个数，记为 （2）简单图 环（自回路）：一条边的两个端点如果相同，称此边为环。如 图6-3中的e1。 多重边 ：两个点之间多于一条边的，如图6-3中的e4， e5. 次为 1 的点称为悬挂点，连接悬挂点的边称为悬挂边。次为 0的点称为孤立点。次为奇数的点称为奇点，次为偶数的点称为偶点。 定理 6-1 任何图G =（V,E）中，所有点的次数之和等于边数的2倍。即 证：由于每条边必有两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数之和等于边数的2倍。 定理 6-2 任何图G =（V,E）中，奇点的个数必为偶数。 证：设图 中奇点与偶点的集合分别为V1和V2， （4）链 链：对于无向图G =（V,E）, 称顶点和边交替的序列 二、有向图 （1）有向图 有向图是一个有序二元组（V,A），记为D（V,A），其中 （2）简单有向图 两个端点重合的弧称环。如图 6-4 中的a1 . 两个端点之间的同向弧数大于等于2，称为多重弧。 无环也无多重弧的有向图称为简单有向图。 （3）点的出次和入次 以点v为起点的弧数叫做点v的出次，记作 以点v为终点的弧数叫做点v的入次，记作 三、网络 实际问题中，往往只用图来描述所研究对象之间的关系还不够，如果在图中赋予边一定的数量指标，我们常称之为“权”。依据研究问题的需要，权可以代表距离，也可以代表时间、费用