LINGO在图论中的应用.ppt

第2章 LINGO在图论和网络模型中的应用
图是一种直观形象地描述已知信息的方式,它使事物之间的关系简洁明了,是分析问题的有用工具,很多实际问题可以用图来描述。
一、图的基本概念
图论是以图为研究对象的数学分支,在图论中,图由一些点和点之间的连线所组成.
称图中的点为顶点(节点),称连接顶点的没有方向的线段为边,,所有线段都有方向的图称为有向图,既有边也有弧的图称为混合图.
点与边相连接称为关联,与边e关联的顶点称为该边的端点,与同一条边关联的两个顶点称为相邻顶点,与同一个顶点关联的边称为相邻边.
具有相同顶点的边称为平行边,,没有环和平行边的图称为简单图,.
在图中,两个顶点u和v之间由顶点和边构成的交错序列(使u和v相通)称为链(通道),没有重复边的通道称为迹,起点与终点重合的通道称为闭通道,不重合的称为开通道,没有重复顶点(必然边也不重复)的开通道称为路,起点与终点重合的路称为圈(回路).如果顶点u和v之间存在通道,称u和v是连通的,任意两个顶点都连通的图称为连通图.
无圈的连通图称为树,如果一棵树T包含了图G的所有顶点,称T为G的生成树.
如果图G的每条边e都对应一个实数C(e),称C(e)为该边e的权,.
二、最短路问题

(1)问题的描述
给定N个点Pi(i=1,2,...,n)组成集合{Pi},集合中任一点Pi到另一点Pj的距离用Wij表示,如果Pi到Pj没有弧联结(无通路),则规定Wij=+∞,又规定,Wii=0 (i=1,2,...,n),指定一个终点PN,要求从Pi点出发到PN的最短路线。
可以用动态规划的方法来求最短路问题,下面举例说明其算法原理。

举例:
图中A,B,...,G表示7个城市,连线表示城市之间有道路相通,连线旁的数字表示道路的长度Wij,现要从城市A到G找出一条最短路线。
该问题有三个阶段,第一阶段从A到B或C,第二阶段到D,E或F,第三阶段到终点G,我们从终点向前倒过来找。
A
G
F
E
D
C
B
2
4
1
2
3
1
3
3
1
3
4
第三阶段,从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的里程分别为:
WBD+ f(D)=3+1=4
WBE+ f(E)=3+3=6
WBF+ f(F)=1+4=5
故B到G的最短路是上述三者的最小值(4),可以写成f(B)=min{WBj+f(j)}=4,j是上一步考察过的三个点D,E,F;同理f(C)=min{WCj+f(j)},而
WCD+ f(D)=2+1=3
WCE+ f(E)=3+3=6
WCF+ f(F)=1+4=5
故F(C)=3;
第一阶段,出发点只有一个A,从A出发分别经过B,C,至终点G的里程分别为:
WAB+ f(B)=2+4=6
WAC+ f(C)=4+3=7
故A到G的最短路是上述两者的最小值6,可以写成f(A)=min{WAj+f(j)}=6,j是上一步考察过的两个点B,C,现在已经到了起点,结束运算,从A到G的最短路为6。
上述算法可以简写成
N是终点,1是起点, j是与i相联,上一步考察过,且与终点相通、f(j)为已知的点。
编写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