LINGO在图论中的应用

《LINGO在图论中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章LINGO在图论和网络模型中的应用图是一种直观形象地描述已知信息的方式，它使事物之间的关系简洁明了，是分析问题的有用工具，很多实际问题可以用图来描述。一、图的基本概念图论是以图为研究对象的数学分支，在图论中，图由一些点和点之间的连线所组成．称图中的点为顶点（节点），称连接顶点的没有方向的线段为边，称有方向的线段为弧．所有线段都没有方向的图称为无向图，所有线段都有方向的图称为有向图，既有边也有弧的图称为混合图．点与边相连接称为关联，与边e关联的顶点称为该边的端点，与同一条边关联的两个顶点称为相邻顶点，与同一个顶点关联的边称为相邻边．具有相同顶点的边称为平行边，两个端点重合的边称为

2、环．在无向图中，没有环和平行边的图称为简单图，任意一对顶点都有一条边相连的简单图称为完全图．任意两个顶点之间有且只有一条弧相连的有向图称为竞赛图．在图中，两个顶点u和v之间由顶点和边构成的交错序列（使u和v相通）称为链（通道），没有重复边的通道称为迹，起点与终点重合的通道称为闭通道，不重合的称为开通道，没有重复顶点（必然边也不重复）的开通道称为路，起点与终点重合的路称为圈（回路）．如果顶点u和v之间存在通道，称u和v是连通的，任意两个顶点都连通的图称为连通图．无圈的连通图称为树，如果一棵树T包含了图G的所有顶点，称T为G的生成树．如果图G的每条边e都对应一个实数C(e)，称C(e)为该

3、边e的权，称图G为赋权图．通常称赋权的有向图为网络．二、最短路问题1.动态规划法(1)问题的描述给定N个点Pi(i=1,2,...,n)组成集合{Pi}，集合中任一点Pi到另一点Pj的距离用Wij表示，如果Pi到Pj没有弧联结(无通路)，则规定Wij=+∞，又规定，Wii=0(i=1,2,...,n)，指定一个终点PN，要求从Pi点出发到PN的最短路线。可以用动态规划的方法来求最短路问题，下面举例说明其算法原理。2.算法原理举例：图中A,B,...,G表示7个城市，连线表示城市之间有道路相通，连线旁的数字表示道路的长度Wij，现要从城市A到G找出一条最短路线。该问题有三个阶段，第一阶段

4、从A到B或C，第二阶段到D,E或F，第三阶段到终点G，我们从终点向前倒过来找。AGFEDCB24123133134第三阶段，从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=4WBE+f(E)=3+3=6WBF+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

5、WCE+f(E)=3+3=6WCF+f(F)=1+4=5故F(C)=3；第一阶段，出发点只有一个A，从A出发分别经过B,C,至终点G的里程分别为：WAB+f(B)=2+4=6WAC+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个城市;road

6、s(cities,cities)/A,BA,CB,DB,EB,FC,DC,EC,FD,GE,GF,G/:W,P;!定义哪些城市之间有路相联，W为里程，P用来存放最短路的路径;endsetsdata:W=24331231134;enddataN=@SIZE(CITIES);FL(N)=0;!终点的F值为0;@for(cities(i)

7、i#lt#N:FL(i)=@min(roads(i,j):W(i,j)+FL(j)));!递推计算各城市F值;!显然，如果P(i,j)=1,则点i到点n的最短路径的第一步是i-->j，否则就不是。由此，我们就可方便的确定出最短路径;@for(roads(i

8、,j):P(i,j)=@if(FL(i)#eq#W(i,j)+FL(j),1,0));end部分计算结果：FL(A)6FL(B)4FL(C)3FL(D)1FL(E)3FL(F)4FL(G)0最短路线为ABDG以上计算程序是通用程序，对其它图，只需在此程序基础上对数据作一些修改即可。程序中的语句roads(cities,cities)/A,BA,CB,DB,EB,FC,DC,EC,FD,GE,GF,G/:W,P;定义的集合称为稀疏集合，本例中ci