图论中几个典型问题的求解.ppt

《图论中几个典型问题的求解.ppt》由会员分享，可在线阅读，更多相关《图论中几个典型问题的求解.ppt（161页珍藏版）》请在三一办公上搜索。

1、图论中几个典型问题的求解,1 图的基本概念,图是一种直观形象地描述已知信息的方式，它使事物之间的关系简洁明了，是分析问题的有用工具，很多实际问题可以用图来描述。,一、图的定义,图论是以图为研究对象的数学分支，在图论中，图由一些点和点之间的连线所组成 称图中的点为顶点（节点），称连接顶点的没有方向的线段为边，称有方向的线段为弧用V=v1,v2,表示全体顶点的集合，用 E=e1,e2,表示全体边的集合，如果对于E中的任一条边ek，在V中都有一对顶点(vi,vj)和它对应，则称由V和E组成的集体为一个图，记为G=V,E，简写为G,二、基本概念,点与边相连接称为关联，与边e关联的顶点称为该边的端点，与

2、同一条边关联的两个顶点称为相邻顶点，与同一个顶点关联的边称为相邻边具有相同顶点的边称为平行边，两个端点重合的边称为环所有线段都没有方向的图称为无向图，所有线段都有方向的图称为有向图，既有边也有弧的图称为混合图在无向图中，没有环和平行边的图称为简单图，任意两个顶点之间都有一条边相连的简单图称为完全图任意两个顶点之间有且只有一条弧相连的有向图称为竞赛图,在无向图中与顶点v关联的边的数目（环算两次）称为该顶点的度（或次数），记为d(v)。度为奇数的顶点叫做奇点，度为偶数的顶点叫做偶点。在有向图中，从顶点v引出的边的数目称为该顶点的出度，记为d+(v)，从顶点v引入的边的数目称为该顶点的入度，记为d-

3、(v)，而d(v)d+(v)+d-(v)称为v的次数。,在图中，两个顶点u和v之间由顶点和边构成的交错序列（使u和v相通）称为链（通道），没有重复边的通道称为迹，起点与终点重合的通道称为闭通道，不重合的称为开通道，没有重复顶点（必然边也不重复）的开通道称为路，起点与终点重合的路称为圈（回路）包含奇数个顶点（或边）的圈称为奇圈，包含偶数个顶点（或边）的圈称为偶圈。如果顶点u和v之间存在一条路，则称u和v是连通的，任意两个顶点都连通的图称为连通图无圈的连通图称为树，如果一棵树T包含了图G的所有顶点，称T为G的生成树,如果图G的每条边e都对应一个实数C(e)，称C(e)为该边e的权，称图G为赋权图通

4、常称赋权的有向图为网络图中边e6和e7是平行边，e9是环，顶点v4是悬挂点，边e4是悬挂边,2 最短路问题,最短路问题是图论应用的基础，很多实际问题，如线路的布设、运输规划、运输网络最小费用流等问题，都可以通过建立最短路模型来求解。有些有深度的图与网络优化问题，如旅行售货商、中国邮递员等问题，需要在首先求出任意两点之间最短路的基础上解决。一、最短路的概念给定一个连通的赋权图G=V,E，设R是连接节点vi和vj的一条路，该路的权定义为路中所有各边权之和，如果路R在所有连接节点vi和vj的路中权最小，则称它为vi和vj间的最短路。,二、任意两点之间的最短路(Floyd算法)Floyd算法利用距离矩

5、阵进行迭代运算，可以一次性地求出任意两点之间的最短路，该方法的思路有创意，计算量小，编程较简单，又称矩阵求解法。1算法原理 设A=aijmn是图的权矩阵（也称带权邻接矩阵），其中aij是图上连接顶点i和j的边的权，如果两顶点之间没有直接相连的边（即两顶点不相邻），则aij=。,令矩阵D(0)=A，作为迭代的初始矩阵，从它出发按照一定规则求D(1)，又由D(1)按照类似的规则求D(2)，依此类推进行迭代直至求出D(n)，设矩阵D(m)的元素为dij(m)，迭代规则为：上式表示dij(1)在dij(0)以及从顶点vi经过顶点v1到vj的权之和di1(0)+d1j(0)两者之中选择最短长度。依此规则

6、迭代。,上式表示dij(2)在dij(1)以及从顶点vi经过顶点v2到vj的权之和di2(1)+d2j(1)两者之中选择最短长度。依此类推，迭代公式为：上式表示dij(m)在dij(m-1)以及从顶点vi经过顶点vm到vj的权之和dim(m-1)+dmj(m-1)两者之中选择最短长度。当m=n时结束迭代。,2程序设计 先编写Flody算法的子程序（函数）如下：Function D,R=floyd(a)n=size(a,1);D=a;%D是初始矩阵for i=1:n for j=1:n R(i,j)=j;endend,for k=1:n for i=1:n for j=1:n if D(i,k)

7、+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);%在循环中进行矩阵迭代 R(i,j)=R(i,k);%R是路径矩阵 end end endendD,R%输出最短路矩阵和最短路的路径矩阵。,以上程序是通用程序，只需输入初始距离矩阵，就能输出最短路矩阵以及最短路的路径矩阵，将程序以文件名floyd.m存盘。例1 以2007年研究生数学建模竞赛C题为例，已知16个邮政支局的初始距离矩阵，求任意两个节点之间的最短路。解：编写主程序如下：a=0,27,44,17,11,27,42,inf,inf,inf,20,25,21,21,18,27,inf;inf,inf,inf,inf,30

8、,inf,inf,inf,21,13,20,inf,inf,inf,inf,9,0;D,R=floyd(a);,输入数据中的inf表示无穷大（两个顶点之间没有边直接相连）。运行以上程序，求得最短路矩阵D和最短路的路径矩阵。此处省略结果。,3 最小生成树,一、最小生成树的概念树是图论中的一种简单而重要的图，连通并且无圈的无向图称为树，常用T表示。树有以下性质：(1)树中任意两点之间有唯一路径；(2)树的边数等于顶点数减1；(3)在树中删去任意一条边就不连通；(4)在树中任意两个不相邻的顶点间添加一条边，则恰好产生一个圈。,具有n个顶点的无向连通图是树的充分必要条件是它有n-1条边连通图G的子图T

9、，如果它的顶点集与G的顶点集相同，且T为树，则称T是图G的生成树，又称支撑树。如果图的边有权（对应于边的实数），则生成树上各边权的总和称为生成树的权，生成树并不唯一，权达到最小的生成树称为最小生成树(Minimal Spanning Tree，简称MST)，最小生成树不一定唯一,最小生成树是网络优化中的一个重要问题，在网络设计中有广泛的应用，例如如何修筑一些公路把若干个城镇连接起来且总里程最短；如何架设通讯网络将若干个地区连接起来且总费用最省；如何修筑水渠将水源和若干块待灌溉的土地连接起来且总距离最短等等这些应用问题通称为最优连线问题，其实质是寻找图的最小生成树,二、Prim（普里姆）算法求图

10、的最小生成树最常用的算法有两种：Prim（普里姆）算法和Kruskal（克罗斯克尔）算法，这两种方法都由贪婪法的思想发展而来。贪婪法又称贪心法，该法总是做出在当前看来最好的选择，也就是说该算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。虽然贪婪算法不能对所有问题都得到整体最优解，但是它对某些问题能够得到整体最优解，例如图的固定起点的最短路问题，最小生成树问题。有时候，即使贪婪算法不能得到整体最优解，但其结果却是整体最优解的很好近似。,Prim算法的思路是：把所有顶点分成部分（两个集合），一个用S表示（该集合中的顶点都涂成红色），另一个用V-S表示（该集合中的顶点都涂成白色

11、），开始时S中只有一个顶点v1，其余顶点都是白色，在一个端点为红色，另一个端点为白色的边中选取权最小的边，将该边涂红（表示入选最小生成树）并且把该边的白色端点也涂红（表示移入S中）这个过程一直进行下去，S中的端点越来越多，直到所有顶点都涂成红色为止，或者说红色边达到n-1条为止。,从Prim算法的思路中可以看出，该算法的关键是如何找出连接红点和白点的所有边中找出权最小的边。若G为完全图，当前有k个红点，则有n-k个白点，有k(n-k)条连接红、白点的边，为了在如此众多的边中找到权最小的边，可以分两步走，对每一个白点，先从连接该点至k个红点的k条中找出权最小的边作为候选边，然后对n-k个白点，从

12、n-k条候选边中找出权最小的边。,实现Prim算法的Matlab编程思路如下：(1)设第一个红点是节点v1。构建初始候选边的权矩阵B。该矩阵有3行，第一行表示当前红点，开始时第一个红点是v1，故第一行都是1，第二行表示白点，开始时白点的序号是2,3,n，第三行表示连接红点和白点的边的权值。当前入选最小生成树的最短边将从该矩阵中产生。初始最小生成树T是空集。(2)对B矩阵的第3行排序，即对候选边的权值进行排序，选取最短边（权值最小的边），把该边涂红（选入最小生成树的边集T），该边的白色端点也涂成红色。,(3)将(2)选出的边移出B（不参与下一轮竞选），即将它从B矩阵中删除。当前有n-2个白点（两

13、个红点），对每个白点都有到两个红点的两条边，通过比较这两者的大小，选出权值小的边，放入B矩阵的相应位置上，由此构建新的候选边矩阵B，此时B矩阵的有n-2列。(4)对新的B矩阵重复(2)和(3)，T中的边将越来越多，B矩阵的列数越来越少，当选入T中的红色边达到n-1条时结束运算，输出T。,按照以上思路编写Matlab程序如下：function T,e=prim(a)T=;%T为最小生成树的边集，开始为空集。e=0;%e是最小生成树的长度，开始为0。v=1;%v表示第一个红点是1号顶点。n=size(a,1);%n是总顶点数，它等于初始距离矩阵a的列数。c=2:n;%c代表所有白点，开始是2,3,

14、n。,for j=2:n b(1,j-1)=1;b(2,j-1)=j;b(3,j-1)=a(1,j);end%以上一段程序生成3行n-1列的矩阵，存储初始候选边及其权值信息，该矩阵的第一行都是1，表示第一个红色点是1号顶点，第二行表示白色点依次为2,3,n，第三行表示所有连接红点和白点的边的权值,while size(T,2)n-1%只要最小生成树的边数小于n-1就循环m,i=min(b(3,:);%从候选边中找出权值最小的边（其值存入变量m，序号为i）T(:,size(T,2)+1)=b(:,i);%当前最短边（含起点、终点和权值3个树中）存入T中当前列，表示入选最小生成树 e=e+b(3,

15、i);%累计最小生成树的长度 v=b(2,i);%把新入选最小生成树的边的白色端点变成当前红点,t=find(c=b(2,i);c(t)=;%把该点从白点集合中移出去b(:,i)=;%把该边从候选边中删除 for j=1:length(c)d=a(v,b(2,j);if db(3,j)b(1,j)=v;b(3,j)=d;endend,%以上循环调整候选边集合，入选该集合的边数等于当前白点数，对每一个白点入选一条边，该边通过比较连接该白点到红点的边的权值大小确定，小者入选。该循环是程序的关键和核心部分。endT,e以上程序以文件名prim.m存盘。,例2 以2007年研究生数学建模竞赛C题为例，

16、已知县邮政局X1和16个邮政支局的初始距离矩阵，求该运输图的最小生成树。解：在Matlab中输入a=0,27,44,17,11,27,42,inf,inf,inf,20,25,21,21,18,27,inf;inf,inf,inf,inf,30,inf,inf,inf,21,13,20,inf,inf,inf,inf,9,0;T,e=prim(a);,计算结果为：T=1 5 6 7 5 5 11 16 11 10 16 16 4 1 1 145 6 7 8 4 11 16 17 10 9 15 12 3 13 14 211 13 9 13 14 15 9 9 10 11 11 14 19 21

17、 21 21e=221T中每一列代表入选最小生成树的一条边，每一列有3个元素，前两个代表顶点的编号，第3个是边的权值。e是最小生成树的总长。,三、Kruskal（克罗斯克尔）算法Kruskal（克罗斯克尔）算法又称“避圈法”，也是一种贪婪算法。给定加权连通图G=V,E，Kruskal算法的基本思路如下：(1)把所有边按照权值的大小由小到大排序，将最小边入选最小生成树T。(2)从剩下的边中选取权值最小的边，并且该边与T中已经存在的边不形成圈，将它也取进T中（若某边权值虽然小，但形成圈则舍去此边，并且另选。重复步骤(2),直至入选T的边达到n-1条为止。,由以上思路可知，Kruskal算法的关键是

18、如何判断一条候选边是否会与T中已有边形成圈，下面介绍一种判断方法。设所有顶点都是红色，选入最小生成树T的边为红色，没有选入的边为白色。则红点和红边会形成一个或者一个以上的连通分支，它们都是G的子树，当一条待选边的两个端点属于同一棵子树时候就会形成圈，否则不构成圈，且该边入选后会使原来两个不连通的红色子树合并成为一棵红色连通子树。因此判断一条边是否会与现有红边形成圈，只需要判断该边的两个端点是否属于同一棵子树。,可以用下面的方法来实现以上判断：给每棵子树一个不同的编号，对每一个顶点引入一个标记t，表示该顶点所在子树的编号。当加入一条红色边时，就该边两个端点所在的子树连接起来成为一棵子树，从而两棵

19、子树中的顶点标记要改成一样。,按照以上思路编写Matlab程序如下：function T,c=kruskal(a)n=size(a,1);%n 是总顶点数m=0;for i=1:n-1 for j=i+1:n if a(i,j)0 end endend,%以上循环生成图的边权矩阵，该矩阵有3行，第1行和第2行是顶点的编号，第3行是边的权值，矩阵的列数对于图的边数，每一列代表一条边。程序运行以后，该矩阵的列数（即图的总边数记录在变量m中）。B,i=sortrows(b,3);B=B;%实现对边权矩阵按照权值大小由小到大排序，B是排序以后的边权矩阵。k=0;%k表示已经被选入最小生成树的边数t=1

20、:n;%开始每个顶点各自为一棵独立的子树，子树的编号分别1,2,n。T=;c=0;%开始时最小生成树为空集，权值之和为0,for i=1:m%对排序以后的边权矩阵，按顺序考察每一条边if t(B(1,i)=t(B(2,i)%当第i条边的两个端点所在子树的编号不相等时，该边与已经选入最小生成树的边不形成圈，于是运行以下语句 k=k+1;%入选最小生成树的边数k增加1 T(:,k)=B(:,i);%把该边选入最小生成树的集合T c=c+B(3,i);%把该边的权值加到最小生成树的总权值之中 tmin=min(t(B(1,i),t(B(2,i);tmax=max(t(B(1,i),t(B(2,i);

21、,%入选边的两个端点分别属于不同的子树，t标号不同，对这两个t标号排序 for j=1:n if t(j)=tmax t(j)=tmin;end end%将入选边所属两个t标号合并成一个（大标号改为小标号）end,if k=n-1%如果入选最小生成树的边数达到n-1，则结束计算 break;endendT,c以上程序以文件名kruskal.m存盘。,仍然以例2的数据为例，先输入数据矩阵a，然后运行T,e=kruskal(a)得到计算结果。T=6 11 16 10 1 9 15 5 7 4 12 5 3 1 1 27 16 17 11 5 10 16 6 8 5 16 11 4 13 14 14

22、9 9 9 10 11 11 11 13 13 14 14 15 19 21 21 21e=221该结果与Prim算法求出的结果相同。虽然Prim和kruskal两种算法的思路都由贪婪法发展而来，但它们用来求最小生成树时，最终输出结果必定是最优解。,最小生成树 的图形,四、用LINGO求最小生成树1.把最小生成树问题转化为整数规划采用一定的方法可以把最小生成树问题转化为整数规划，然后用LINGO求解。节点1表示树根，点i到点j的距离用Cij表示，当两个节点之间没有线路相通时，两点之间距离用M(很大的实数)表示。引入0-1整数变量xij：若xij=1(且ij)表示从i到j的边在树中，xij0则表

23、示该边不在树中。,目标函数约束条件：(1)除树根外每个点都有线路通到(且只需要一次)表示为(2)至少有一条线路从1出来,以上约束条件是必要条件，但不充分，类似于TSP问题，增加一个变量u，再附加约束条件：(1)限制uj的取值范围为：u1=0，1ujn-1，j=2,3,.,n；用以下不等式可以达到目的：uj1且uj n-1-(n-2)x1j，j1，(2)如果线路从j到k，则uk=uj+1，且避免来回重复和圈，约束条件为:ujuk+xkj-(n-2)(1-xkj)+(n-3)xjk，1kn，2jn jk；,最优连线(最小生成树)转化为整数规划：,例3 假设某电力公司计划在七个村庄之间架设电线，各村

24、庄之间的距离如图所示试求出使电线总长度最小的架线方案,2.LINGO程序编写LINGO程序如下：MODEL:sets:city/1.7/:u;!定义7个城市;link(city,city):dist,x;!距离矩阵和决策变量;endsets n=size(city);data:!dist是距离矩阵;,dist=0 3 4 7 100 100 100 3 0 3 2 4 100 100 4 3 0 100 5 7 100 7 2 100 0 2 100 6 100 4 5 2 0 1 4 100 100 7 100 1 0 2100 100 100 6 4 2 0;!这里可改为你要解决的问题的数

25、据;enddata,min=sum(link:dist*x);!目标函数;U(1)=0;for(link:bin(x);!定义X为01变量;FOR(city(K)|K#GT#1:sum(city(I)|I#ne#K:x(I,K)=1;for(city(J)|J#gt#1#and#J#ne#K:u(J)=u(K)+X(K,J)-(N-2)*(1-X(K,J)+(N-3)*X(J,K);););sum(city(J)|J#GT#1:x(1,J)=1;for(city(K)|K#gt#1:U(K)=1;U(K)=N-1-(N-2)*X(1,K););end,计算结果：目标函数值(最优连线的长度)为1

26、3，最优连线的构成如图所示,4 旅行商问题,一、旅行商问题的基本概念,旅行商问题（又称货郎担问题，traveling salesman problem，简称TSP问题）是典型的组合优化问题，并且是一个NP完全难题，其提法为：有n个城市，相互之间的旅行费用（或距离）为已知，有一个旅行推销商，从某个基点城市出发，要遍访其余n-1个城市至少一次，最后回到出发点，试找出总费用最小（或总路程最短）的旅行路线。称能够到每个城市至少一次的回路为旅行商回路，其中费用最少者为最优旅行商回路.,在图论中，经过所有顶点恰好一次的圈（路）称为哈密顿圈（路），简称H圈（H路），存在H圈的图称为哈密顿图，简称H图。旅行商

27、问题是指在赋权图上经过每个顶点至少一次，且总长度（路径上权的总和）达到最小的闭通路。在加权的连通无向图中，权最小的H圈简称最优H圈；经过每个顶点至少一次且权最小的闭通路称为最优旅行商回路。注意：最优H圈与最优旅行商回路两者是有区别的，最优H圈只允许经过每个顶点恰好一次，而最优旅行商回路允许经过某些顶点一次以上。,定理1 在加权图G=（V，E）中，若对任意顶点x,y,z（zx,zy），都满足w(x,y)w(x,z)+w(y,z)（三角形的两边之和大于等于第三边，称为三角不等式），则该图的最优哈密顿圈也是最优旅行商回路。对于连通的非完全赋权图G，先求出任意两点之间的最短路，然后用最短路作为每一条边

28、的权，构造一个以V为顶点集的完全图G=（V，E），容易证明，在如此构造出来的图G中，各边的权自然满足三角不等式，故在加权图G中寻求最优旅行商回路的问题就可以转化为在图G中寻求最优哈密顿圈的问题。,寻找最优哈密顿圈和最优旅行商回路是图论中的典型问题，而且是一个NP完全难题。问题的求解没有多项式时间算法，除了穷举法，目前还没有寻找最优解的算法，随着顶点数的增加，运算所需时间呈指数级增长，当顶点数较大时，求出最优解所需时间可能是难以忍受的。可行的方法是用近似算法，力争在较短时间寻找接近最优解的近似最优解。旅行商问题得到了许多学者的关注和长期研究，提出了多种近似算法，例如分支定界法、遗传算法、模拟退火

29、法、蚁群算法、神经网络方法、粒子群优化算法、重绕最小生成树法、二次逐边修正法等。,二、用LINGO求解TSP问题的方法一1.把最优哈密顿圈问题转化为0-1线性规划 将任意两点之间的最短路作为两点之间边的权构造完全图G。引入0-1整数变量xij(且ij)：若xij=1则边i-j在回路中，而xij0则表示否。目标函数首先必须满足约束条件：对每个城市访问一次且仅一次。从城市i出发一次(到其它城市去),表示为,从某个城市到达j一次且仅一次，表示为：以上建立的模型类似于指派问题的模型，对TSP问题只是必要条件，并不充分。,例如，用图示路线连接六个城市，满足以上两个约束条件，但这样的路线出现了两个子回路，

30、两者之间不通，不构成整体巡回路线。为此需要考虑增加充分的约束条件以避免产生子巡回。下面介绍一种方法：增加变量ui,i=2,3,n，（它的大小可以取正整数：例如从起点出发所达到的城市u=2,依此类推）。,附加约束条件：ui-uj+nxijn-1,i=1,n，j=2,n，且ij。下面证明：(1)任何含子巡回的路线都必然不满足该约束条件（不管ui如何取值）；(2)全部不含子巡回的整体巡回路线都可以满足该约束条件（只要ui取适当值）。用反证法证明(1),假设存在子巡回，则至少有两个子巡回。那么（必然）至少有一个子巡回中不含起点城市1，如上图中的4564，则必有 u4-u5+nn-1，u5-u6+nn-

31、1，u6-u4+nn-1，把这三个不等式加起来得到nn-1，不可能，故假设不能成立。而对整体巡回，因为附加约束中j2,不包含起点城市1，故不会发生矛盾。,对于整体巡回路线，只要ui取适当值，都可以满足该约束条件：()对于总巡回上的边，xij=1,ui可取访问城市i的顺序数，则必有ui-uj-1，约束条件ui-uj+nxijn-1变成：-1+n n-1，必然成立。()对于非总巡回上的边，因为xij=0，约束条件ui-uj+nxijn-1变成-1n-1，肯定成立。综上所述，该约束条件只限止子巡回，不影响其它，于是TSP问题转化成了一个整数线性规划问题。,求最优哈密顿圈可以表示为规划：,2.LING

32、O程序!旅行售货员问题;model:sets:city/1.17/:u;!定义17个城市;link(city,city):dist,!距离矩阵;x;!决策变量;endsets n=size(city);data:!距离矩阵;,C=0 16.3 11.9 10.1 28 12.9 6 20.6 28.4 22.2 20.8 35.7 22.1 30.2 23.7 27.8 3616.3 0 12.2 26.4 23.9 8.8 10.3 36.9 40.1 32.2 16.7 31.6 14.7 22.8 7.4 11.5 19.711.9 12.2 0 22 36.1 21 5.9 32.5

33、40.3 34.1 28.9 43.8 26.9 35 19.6 17.6 25.810.1 26.4 22 0 20.4 23 16.1 10.5 18.3 12.1 15.2 28.1 32.2 38.4 33.8 37.9 46.128 23.9 36.1 20.4 0 15.1 34 24 16.2 8.3 7.2 7.7 24.3 18 31.3 35.4 32.912.9 8.8 21 23 15.1 0 18.9 33.5 31.3 23.4 7.9 22.8 9.2 17.3 16.2 20.3 28.56 10.3 5.9 16.1 34 18.9 0 26.6 34.4 2

34、8.2 26.8 41.7 25 33.1 17.7 21.8 3020.6 36.9 32.5 10.5 24 33.5 26.6 0 7.8 15.7 25.7 31.7 42.7 42 44.3 48.4 56.628.4 40.1 40.3 18.3 16.2 31.3 34.4 7.8 0 7.9 23.4 23.9 40.5 34.2 47.5 51.6 49.122.2 32.2 34.1 12.1 8.3 23.4 28.2 15.7 7.9 0 15.5 16 32.6 26.3 39.6 43.7 41.220.8 16.7 28.9 15.2 7.2 7.9 26.8 2

35、5.7 23.4 15.5 0 14.9 17.1 25.2 24.1 28.2 36.435.7 31.6 43.8 28.1 7.7 22.8 41.7 31.7 23.9 16 14.9 0 18.4 10.3 25.7 33.4 25.222.1 14.7 26.9 32.2 24.3 9.2 25 42.7 40.5 32.6 17.1 18.4 0 8.1 7.3 26.2 2330.2 22.8 35 38.4 18 17.3 33.1 42 34.2 26.3 25.2 10.3 8.1 0 15.4 23.1 14.923.7 7.4 19.6 33.8 31.3 16.2

36、17.7 44.3 47.5 39.6 24.1 25.7 7.3 15.4 0 18.9 20.327.8 11.5 17.6 37.9 35.4 20.3 21.8 48.4 51.6 43.7 28.2 33.4 26.2 23.1 18.9 0 8.236 19.7 25.8 46.1 32.9 28.5 30 56.6 49.1 41.2 36.4 25.2 23 14.9 20.3 8.2 0;,!这里可改为你要解决的问题的数据;enddata!目标函数;min=sum(link:dist*x);FOR(city(K):!进入城市K;sum(city(I)|I#ne#K:x(I,K

37、)=1;!离开城市K;sum(city(J)|J#ne#K:x(K,J)=1;);!保证不出现子圈;,for(city(I)|I#gt#1:for(city(J)|J#gt#1#and#I#ne#J:u(I)-u(J)+n*x(I,J)=n-1););!限制u的范围以加速模型的求解，保证所加限制并不排除掉TSP问题的最优解;for(city(I):u(I)=n-1);for(link:bin(x);!定义X为01变量;end,计算结果：目标函数值：159.3路线：17316171413152611125109841因为以上规划是线性规划，所以求解不费时，当顶点数为2030个时，一般几分钟就可以

38、得到最优解。利用LINGO软件的强大优化能力，不必研究旅行商问题的算法，通过编写不太复杂的LINGO程序，能够较快地解决实际问题，达到事半功倍的效果。,三、用LINGO求解TSP问题的方法二1.对城市排序，找出最优排序在现实中的城市交通图中，有些城市之间有直接道路，有些则没有，如果两点之间没有直接的通路，则两点之间的距离取最短路（经过其它点），即用任意两点之间的最短路Cij作为图的距离矩阵，构成一个完全图G，其任意一对顶点都有一条边相连。图G的最优旅行商回路等价于图G的最优哈密顿圈，此时形式上的环形巡回路线实际上个别点有可能不止经过一次。,设某个城市为旅行的出发地和终点（相当于总部所在地），旅

39、行者从该城市出发到其它n个城市各一次且仅一次，最后回到出发地。我们把行进路线分成n步，每一步到一个城市（第n+1步返回出发地），于是一条旅行路线就相当于n个城市的一种排列，n个城市共有n!种排列方式。排序不同则总里程（或费用）可能不同，总里程（或总费用）最小的排序就是我们要寻找的最优路线。,引入0-1型决策变量Xkj，下标k表示旅行的步数，下标j表示到达哪一个城市，Xkj=1表示旅行者第k个目的地（到达点）是城市j，Xkj=0则表示否。用lj表示总部到各城市的距离，用Cij表示城市i与城市j之间的最短路。从出发地到第1个点的路程为从最后一个点返回出发地的里程为,假设在第k步到达城市i，在第k+

40、1步达到城市j，即Xki=Xk+1,j=1，则走过的里程为：CijXkiXk+1,j从第1点到第n点走过的总里程为目标函数为,约束条件有以下2条：(1)每一步到达一个城市，即(2)每一个城市必须到一次且只需一次，即,综上所述，可以把最优哈密顿圈问题转化成如下非线性0-1 规划,以上规划中允许包含其它约束条件。用LINGO可以求解该规划，举例如下。某县邮局和10个乡镇支局组成该县的邮政运输网络，已知县局到各支局的距离和支局之间的距离矩阵（数据在程序中）。用一辆邮车完成邮件运输任务，邮车从县局出发到各支局去一次且只需一次，最后回到县局，求总路程最短的行驶路线。解：本题是“旅行商”问题。可以用上面介

41、绍的方法求解。,编写LINGO程序如下：MODEL:SETS:CITY/1.10/:JL;STEP/1.10/;LINE(STEP,CITY):X;LINKS(CITY,CITY):C;ENDSETS,DATA:JL=71,56,27,30,28,26,15,9,30,27;C=0,15,44,47,64,83,86,75,93,98 15,0,29,32,49,68,71,60,78,83 44,29,0,20,37,53,42,31,49,54 47,32,20,0,17,36,42,39,60,57 64,49,37,17,0,19,37,37,58,55 83,68,53,36,19,

42、0,18,35,56,47 86,71,42,42,37,18,0,24,38,29 75,60,31,39,37,35,24,0,21,26 93,78,49,60,58,56,38,21,0,29 98,83,54,57,55,47,29,26,29,0;ENDDATA,FOR(LINE:BIN(X);M1=SIZE(STEP);FOR(CITY(I):SUM(STEP(N):X(N,I)=1);FOR(STEP(N):SUM(CITY(I):X(N,I)=1);L1=SUM(CITY(I):(X(1,I)+X(M1,I)*JL(I);LX=SUM(STEP(N)|N#LT#M1:SUM(

43、LINKS(I,J):C(I,J)*X(N,I)*X(N+1,J);MIN=L1+LX;END,在程序运行前需要对LINGO的参数作必要的设置。对于非线性规划，LINGO提供两种求解方法，一种是“Global Solver”（称为全局优化求解器），另一种是“Multistart Solver”（称为多起点算法），全局优化求解器优点是确保找到全局最优解，缺点是有时需要较长运行时间。多起点算法的优点是节省运行时间，但不能保证找到的解就是全局最优解，设置起点数多一些往往找到的解就是全局最优解。点击菜单“Options”，再打开全局优化求解器“Global Solver”选项，可以选或不选“Globa

44、l Solver”，当选择多起点算法“Multistart Solver”时，需要设置起点数，若选择“Solver Decides”表示由LINGO决定。,对以上程序，我们选择“Global Solver”，点击菜单“Options”，在全局优化求解器“Global Solver”选项框内打“”，再点击“确定”。运行以上程序，费时4分多钟，得到最优解：目标函数值（总路程）260公里邮车的行驶路线为：县局89107654123县局,四、多旅行商（MTSP）问题1.多旅行商问题的概念在现实中问题中，有时候不是由一人走遍所有点，而是由几个人分工合作，每个人只到其中部分城市，每个点都有人来过一次且只需

45、一次，事先不指定谁到哪些点，求出使总路程最小的旅行规划（每个人的行走路线）。例如邮路规划中，为了在允许的时间内完成邮件运输任务，县局的邮车往往不止1辆，而是用若干辆邮车分工运输，只要保证每个支局有邮车来过即可，为了节省行驶费用，需要规划几辆邮车的最佳路线。这就是多旅行商问题。,多旅行商问题的提法如下：有n+1个城市，相互间的路程（或旅行费用）为已知，有k个旅行商都从总部所在城市出发，赴其它城市旅行推销，分工遍历其余n个城市，即每个城市各有任意一名旅行商来过一次且仅一次，最后都回到出发地，目标是总路程最短或总费用最省。多旅行商问题在物流配送、邮路优化等方面具有较高的实用价值，而在现实问题中，研究

46、对象往往不是单纯的旅行商问题，而要考虑各种约束条件，例如时间约束、载重量约束等等。研究这一类带约束条件的多旅行商问题具有很强的现实意义。,在现实的多旅行商问题中，往往带有约束条件，例如时间约束、载重量约束等等。带约束条件的多旅行商问题具有广泛现实意义，且是极具挑战性的难题，我们仍然把它转化为0-1非线性规划并编成LINGO程序来求解。实例某县邮政局管辖16个支局，已知县局到各支局的距离以及16个支局之间的距离矩阵。寄达各支局和各支局收寄的邮件(袋)如下表所示：,县邮局和各支局分布图,每一辆邮车最多装载65袋邮件，邮车的运行成本为3元/公里。试用最少邮车，并规划邮车的行驶路线使总费用最省。分析：

47、首先考虑最少邮车数量，由题目所给表中数据，寄达16个支局的邮件总数为176袋，从各支局收寄的邮件总数为170袋，每一辆邮车最多容纳65袋邮件，至少需要176/652.7辆邮车，由于邮车数量为整数，故最少需要3辆邮车。如果3辆邮车能够完成邮件运输任务，则3辆车就是邮车数量的最优解。,运输费用与行驶里程成正比，总里程最短对应总费用最省。把16个支局放在一起作为一个整体考虑，找出3条邮路，每条邮路都从县局出发，到若干支局进行卸装，最后回到县局。各邮车路过的支局数量未知，合理安排各邮车的行驶路线，由3辆邮车分别承包运输，在满足运载量约束前提下，把3条巡回路线的总里程最小作为优化的目标。该问题相当于附带

48、约束条件的多旅行商模型。,2.0-1规划模型引入0-1型决策变量Xkj,Ykj,Zkj，分别表示3辆邮车第k步到达支局j，下标k表示邮车行走的步数，下标j表示到达哪一个支局，当决策变量Xkj,Ykj,Zkj等于1时分别表示某邮车第k个装卸点是支局j，等于0时表示否。设各邮车管辖的支局数量分别为m1,m2,m3，则m1+m2+m3=16。约束条件有以下3条：(1)任何一辆车在任何一步到达一个支局，即,(2)任何一个支局必须有一辆邮车到达一次且只需要一次，即(3)在邮车行进的任何路段上，装载的邮件不超过65袋。设寄达各支局的邮件量为Pj，各支局收寄的邮件量为Qj。装载量是动态变化的，以第1辆邮车为

49、例，出发时的装载量为,到第1个支局卸装以后，装载量变为在行驶过程中，装载量的递推公式为约束条件为,综上所述，建立多旅行商问题的0-1规划模型如下：,装载量的计算公式为：,3.LINGO程序编写LINGO程序如下：MODEL:SETS:STATION/1.16/:JL,P,Q;STEPX/1.6/:WX;STEPY/1.5/:WY;STEPZ/1.5/:WZ;LINEX(STEPX,STATION):X;LINEY(STEPY,STATION):Y;LINEZ(STEPZ,STATION):Z;LINKS(STATION,STATION):C;ENDSETS,DATA:JL=27 36 17 1

50、1 24 31 44 40 30 20 25 21 21 18 27 36;P=10,15,6,9,13,6,11,4,13,17,11,2,11,21,13,14;Q=9,14,5,10,9,10,13,9,15,9,6,7,13,15,10,16;C=0 31 27 38 51 58 71 67 57 47 52 48 21 41 52 61 31 0 19 33 27 32 45 64 53 47 61 57 52 48 56 63 27 19 0 14 27 34 47 49 39 29 42 38 38 29 38 44 38 33 14 0 13 20 33 35 25 15 33