运筹学chap-6网络优化模型.ppt

本章主要讨论图论基本概念、理论和方法以及最短路问题、最大流问题和最小费用流问题等网络优化模型及其基本算法。 ;第一节 图与网络 运筹学的重要分支 主要应用领域：物理学、化学、控制论、信息论、科学管理、电子计算机等 图论理论和方法应用实例： 在组织生产中，为完成某项生产任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。 一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。 各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便。;图论的起源与发展 七桥问题：哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座桥。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。图8-1(a);一、 图的基本概念;例2 有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况用图表示出来。 已知甲队和其他各队都比赛过一次，乙队和甲、丙队比赛过，丙队和甲、乙、丁队比赛过，丁队和甲、丙、戊队比赛过，戊队和甲、丁队比赛过。为了反映这个情况，可以用点分别代表这五个队，某两个队之间比赛过，就在这两个队所相应的点之间联一条线，这条线不过其他的点，如图6-3所示。;关系的对称性和非对称性： 几个例子中涉及到的对象之间的“关系”具有“对称性”，就是说，如果甲与乙有这种关系，那么同时乙与甲也有这种关系。 实际生活中，有许多关系不具有这种对称性。 如例2，如果人们关心的是五个球队比赛的胜负情况，那么从图5-3中就看不出来了。为了反映这一类关系，可以用一条带箭头的连线表示。 例如，如果球队v1胜了球队v2，可以从v1引一条带箭头的连线到v2 类似胜负这种非对称性的关系，在生产和生活中是常见的，如交通运输中的“单行线”，部门之间的领导与被领导的关系，一项工程中各工序之间的先后关系等。 ;术语顶点（结点）、弧、边（取消弧的方向）、有向图、无向图、链、道路、环、连通图、连通子图、次;例： 设V = {v1 , v2 , v3 , v4}, E = { v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4}, 画出G = (V, E ) 的图。;二、网络;第二节 树; 树的性质： 任意两顶点之间必有一条且仅有一条链。 去掉任一条边，则树成为不连通图。 不相邻的两个顶点间添上一条边，恰好得到一个环。;部分图、生成子图、部分树 ;部分图、生成子图、部分树 ;部分图、生成子图、部分树 ;1; 例：某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,…,v7 表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。;方法一：破圈法 步骤： 1、在给定的赋权的连通图上任找一个圈。 2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。 3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。;v1; 方法二：(加边)避圈法（Kruskal） 开始选一条最小权的边，以后每一步中，总从未被选中的边中选一条最小权的边，使之与已选的边不构成圈，直到所有的边都检验完，即可得最小树。（每步中，若有两条或两条以上的边都是权最小的边，则从中任选一条）。 ;例：右图,用避圈法求其最小生成树。 ;练习：房屋开发商正规划设计某居住新区的下水管道，图中各数字表示各栋楼房之间铺设管道的工程费用。房屋开发商应怎样设计最佳的管道铺设方案，使总工程费用最少。 ;;算法（Dijkstra(迪杰斯特拉) 1959年提出的）;Dijkstra方法的基本思想： 从vs出发，逐步向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为P标号)，或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，这样，至多经过p?1步，就可以求出从vs到各点的最短路。;例：用Dijkstra方法求图8-4所示的赋权图中，从v1到所有点的最短路。;解： 计算的最后结果为 P(v1)=0，P(v4)=1，P(v3)=3，P(v2)=5，P(v5)=6，P(v9)=8，P(v7)=9，P(v6)=10，P(v8)=11。 这样从v1到v8的最短链为(v1，v3，v2，v5，v9，v8)，总权为11。;练习： 设备更新问题。某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用