LINGO在图论中的应用.ppt

第2章 LINGO 在图论和网络模型中的应用 1 图是一种直观形象地描述已知信息的方式,它使事物之间的关系简洁明了,是分析问题的有用工具,很多实际问题可以用图来描述。 2一、图的基本概念图论是以图为研究对象的数学分支,在图论中, 图由一些点和点之间的连线所组成. 称图中的点为顶点(节点),称连接顶点的没有方向的线段为边,,所有线段都有方向的图称为有向图,既有边也有弧的图称为混合图. 点与边相连接称为关联,与边 e 关联的顶点称为该边的端点,与同一条边关联的两个顶点称为相邻顶点,与同一个顶点关联的边称为相邻边. 3 具有相同顶点的边称为平行边,,没有环和平行边的图称为简单图,. 在图中,两个顶点 u和v 之间由顶点和边构成的交错序列(使 u和v 相通)称为链(通道),没有重复边的通道称为迹,起点与终点重合的通道称为闭通道,不重合的称为开通道,没有重复顶点(必然边也不重复)的开通道称为路,起点与终点重合的路称为圈(回路).如果顶点 u和v 之间存在通道,称 u和v 是连通的,任意两个顶点都连通的图称为连通图. 4 无圈的连通图称为树,如果一棵树 T包含了图 G 的所有顶点,称 T为G的生成树. 如果图 G的每条边 e都对应一个实数 C(e) ,称 C(e) 为该边 e的权,称图 . 5二、最短路问题 (1) 问题的描述给定 N 个点 P i(i =1,2,..., n) 组成集合{P i} ,集合中任一点 P i 到另一点 P j 的距离用 W ij 表示,如果 P i到P j没有弧联结( 无通路) ,则规定 W ij =+ ∞,又规定, W ii =0 (i=1,2,..., n), 指定一个终点 P N ,要求从 P i 点出发到 P N的最短路线。可以用动态规划的方法来求最短路问题,下面举例说明其算法原理。 6 : 图中 A,B,...,G 表示 7 个城市,连线表示城市之间有道路相通,连线旁的数字表示道路的长度 W ij, 现要从城市 A到G找出一条最短路线。该问题有三个阶段,第一阶段从 A到B或C ,第二阶段到 D,E 或F,第三阶段到终点 G ,我们从终点向前倒过来找。 A G F E D C B 24 1231 3 31347 第三阶段,从 D,E,F 到G 的最短路分别为 1,3,4 ,记为 f (D)=1, f (E)=3, f (F)=4 ; 第二阶段,与 D,E,F 有连线的出发点为 B和C ,从 B 出发分别经过 D,E,F ,至终点 G的里程分别为: W BD + f (D)=3+1=4 W BE + f (E)=3+3=6 W BF + f (F)=1+4=5 故B到G的最短路是上述三者的最小值(4) ,可以写成 f (B)=min{W Bj +f(j)}=4 ,j是上一步考察过的三个点 D,E,F ; 同理 f(C)=min{W Cj+f (j)} ,而 W CD + f (D)=2+1=3 W CE + f (E)=3+3=6 W CF + f (F)=1+4=5 故 F(C)=3 ; 8 第一阶段,出发点只有一个 A ,从 A 出发分别经过 B,C, 至终点 G的里程分别为: W AB + f (B)=2+4=6 W AC + f (C)=4+3=7 故A到G的最短路是上述两者的最小值 6,可以写成 f (A)=min{W Aj+f (j)}=6 ,j是上一步考察过的两个点 B,C ,现在已经到了起点,结束运算,从 A到 G的最短路为 6。上述算法可以简写成 N是终点, 1是起点, j是与 i相联,上一步考察过, 且与终点相通、 f (j)为已知的点。??????????0)( 1,2,,1, )}({ min )(Nf NijfW if ijj?9 编写 LINGO 程序如下: model: sets: cities/A,B,C,D,E,F,G/: FL; ! 定义 7个城市; roads(cities,cities)/ A,B A,C B,D B,E B,F C,D C,E C,F D,G E,G F,G/: W, P; ! 定义哪些城市之间有路相联, W 为里程, P用来存放最短路的路径; endsets 10