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

图论中几个典型问题的求解第一页，共一百六十一页，2022年，8月28日§1图的基本概念第二页，共一百六十一页，2022年，8月28日图是一种直观形象地描述已知信息的方式，它使事物之间的关系简洁明了，是分析问题的有用工具，很多实际问题可以用图来描述。第三页，共一百六十一页，2022年，8月28日一、图的定义

图论是以图为研究对象的数学分支，在图论中，图由一些点和点之间的连线所组成．

称图中的点为顶点（节点），称连接顶点的没有方向的线段为边，称有方向的线段为弧．用V={v1,v2,…}表示全体顶点的集合，用

E={e1,e2,…}表示全体边的集合，如果对于E中的任一条边ek，在V中都有一对顶点(vi,vj)和它对应，则称由V和E组成的集体为一个图，记为G={V,E}，简写为G．第四页，共一百六十一页，2022年，8月28日二、基本概念

点与边相连接称为关联，与边e关联的顶点称为该边的端点，与同一条边关联的两个顶点称为相邻顶点，与同一个顶点关联的边称为相邻边．具有相同顶点的边称为平行边，两个端点重合的边称为环．所有线段都没有方向的图称为无向图，所有线段都有方向的图称为有向图，既有边也有弧的图称为混合图．在无向图中，没有环和平行边的图称为简单图，任意两个顶点之间都有一条边相连的简单图称为完全图．任意两个顶点之间有且只有一条弧相连的有向图称为竞赛图．第五页，共一百六十一页，2022年，8月28日在无向图中与顶点v关联的边的数目（环算两次）称为该顶点的度（或次数），记为d(v)。度为奇数的顶点叫做奇点，度为偶数的顶点叫做偶点。在有向图中，从顶点v引出的边的数目称为该顶点的出度，记为d+(v)，从顶点v引入的边的数目称为该顶点的入度，记为d-(v)，而d(v)＝d+(v)+d-(v)称为v的次数。第六页，共一百六十一页，2022年，8月28日在图中，两个顶点u和v之间由顶点和边构成的交错序列（使u和v相通）称为链（通道），没有重复边的通道称为迹，起点与终点重合的通道称为闭通道，不重合的称为开通道，没有重复顶点（必然边也不重复）的开通道称为路，起点与终点重合的路称为圈（回路）．包含奇数个顶点（或边）的圈称为奇圈，包含偶数个顶点（或边）的圈称为偶圈。如果顶点u和v之间存在一条路，则称u和v是连通的，任意两个顶点都连通的图称为连通图．无圈的连通图称为树，如果一棵树T包含了图G的所有顶点，称T为G的生成树．第七页，共一百六十一页，2022年，8月28日如果图G的每条边e都对应一个实数C(e)，称C(e)为该边e的权，称图G为赋权图．通常称赋权的有向图为网络．图中边e6和e7是平行边，e9是环，顶点v4是悬挂点，边e4是悬挂边．第八页，共一百六十一页，2022年，8月28日§2最短路问题第九页，共一百六十一页，2022年，8月28日最短路问题是图论应用的基础，很多实际问题，如线路的布设、运输规划、运输网络最小费用流等问题，都可以通过建立最短路模型来求解。有些有深度的图与网络优化问题，如旅行售货商、中国邮递员等问题，需要在首先求出任意两点之间最短路的基础上解决。一、最短路的概念给定一个连通的赋权图G={V,E}，设R是连接节点vi和vj的一条路，该路的权定义为路中所有各边权之和，如果路R在所有连接节点vi和vj的路中权最小，则称它为vi和vj间的最短路。第十页，共一百六十一页，2022年，8月28日二、任意两点之间的最短路(Floyd算法)Floyd算法利用距离矩阵进行迭代运算，可以一次性地求出任意两点之间的最短路，该方法的思路有创意，计算量小，编程较简单，又称矩阵求解法。1．算法原理

设A=[aij]m×n是图的权矩阵（也称带权邻接矩阵），其中aij是图上连接顶点i和j的边的权，如果两顶点之间没有直接相连的边（即两顶点不相邻），则aij=∞。第十一页，共一百六十一页，2022年，8月28日令矩阵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)两者之中选择最短长度。依此规则迭代。第十二页，共一百六十一页，2022年，8月28日上式表示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时结束迭代。

第十三页，共一百六十一页，2022年，8月28日2．程序设计

先编写Flody算法的子程序（函数）如下：Function[D,R]=floyd(a)n=size(a,1);D=a;%D是初始矩阵fori=1:n

forj=1:nR(i,j)=j;endend第十四页，共一百六十一页，2022年，8月28日fork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,j)

D(i,j)=D(i,k)+D(k,j);%在循环中进行矩阵迭代

R(i,j)=R(i,k);%R是路径矩阵endendendendD,R%输出最短路矩阵和最短路的路径矩阵。第十五页，共一百六十一页，2022年，8月28日以上程序是通用程序，只需输入初始距离矩阵，就能输出最短路矩阵以及最短路的路径矩阵，将程序以文件名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,inf,inf,inf,21,13,20,inf,inf,inf,inf,9,0];[D,R]=floyd(a);第十六页，共一百六十一页，2022年，8月28日输入数据中的inf表示无穷大（两个顶点之间没有边直接相连）。运行以上程序，求得最短路矩阵D和最短路的路径矩阵。此处省略结果。

第十七页，共一百六十一页，2022年，8月28日§3最小生成树第十八页，共一百六十一页，2022年，8月28日一、最小生成树的概念树是图论中的一种简单而重要的图，连通并且无圈的无向图称为树，常用T表示。树有以下性质：(1)树中任意两点之间有唯一路径；(2)树的边数等于顶点数减1；(3)在树中删去任意一条边就不连通；(4)在树中任意两个不相邻的顶点间添加一条边，则恰好产生一个圈。第十九页，共一百六十一页，2022年，8月28日具有n个顶点的无向连通图是树的充分必要条件是它有n-1条边．连通图G的子图T，如果它的顶点集与G的顶点集相同，且T为树，则称T是图G的生成树，又称支撑树。如果图的边有权（对应于边的实数），则生成树上各边权的总和称为生成树的权，生成树并不唯一，权达到最小的生成树称为最小生成树(MinimalSpanningTree，简称MST)，最小生成树不一定唯一．第二十页，共一百六十一页，2022年，8月28日最小生成树是网络优化中的一个重要问题，在网络设计中有广泛的应用，例如如何修筑一些公路把若干个城镇连接起来且总里程最短；如何架设通讯网络将若干个地区连接起来且总费用最省；如何修筑水渠将水源和若干块待灌溉的土地连接起来且总距离最短等等．这些应用问题通称为最优连线问题，其实质是寻找图的最小生成树．第二十一页，共一百六十一页，2022年，8月28日二、Prim（普里姆）算法求图的最小生成树最常用的算法有两种：Prim（普里姆）算法和Kruskal（克罗斯克尔）算法，这两种方法都由贪婪法的思想发展而来。贪婪法又称贪心法，该法总是做出在当前看来最好的选择，也就是说该算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。虽然贪婪算法不能对所有问题都得到整体最优解，但是它对某些问题能够得到整体最优解，例如图的固定起点的最短路问题，最小生成树问题。有时候，即使贪婪算法不能得到整体最优解，但其结果却是整体最优解的很好近似。第二十二页，共一百六十一页，2022年，8月28日Prim算法的思路是：把所有顶点分成部分（两个集合），一个用S表示（该集合中的顶点都涂成红色），另一个用V-S表示（该集合中的顶点都涂成白色），开始时S中只有一个顶点v1，其余顶点都是白色，在一个端点为红色，另一个端点为白色的边中选取权最小的边，将该边涂红（表示入选最小生成树）并且把该边的白色端点也涂红（表示移入S中）这个过程一直进行下去，S中的端点越来越多，直到所有顶点都涂成红色为止，或者说红色边达到n-1条为止。第二十三页，共一百六十一页，2022年，8月28日从Prim算法的思路中可以看出，该算法的关键是如何找出连接红点和白点的所有边中找出权最小的边。若G为完全图，当前有k个红点，则有n-k个白点，有k(n-k)条连接红、白点的边，为了在如此众多的边中找到权最小的边，可以分两步走，对每一个白点，先从连接该点至k个红点的k条中找出权最小的边作为候选边，然后对n-k个白点，从n-k条候选边中找出权最小的边。第二十四页，共一百六十一页，2022年，8月28日实现Prim算法的Matlab编程思路如下：(1)设第一个红点是节点v1。构建初始候选边的权矩阵B。该矩阵有3行，第一行表示当前红点，开始时第一个红点是v1，故第一行都是1，第二行表示白点，开始时白点的序号是2,3,…,n，第三行表示连接红点和白点的边的权值。当前入选最小生成树的最短边将从该矩阵中产生。初始最小生成树T是空集。(2)对B矩阵的第3行排序，即对候选边的权值进行排序，选取最短边（权值最小的边），把该边涂红（选入最小生成树的边集T），该边的白色端点也涂成红色。第二十五页，共一百六十一页，2022年，8月28日(3)将(2)选出的边移出B（不参与下一轮竞选），即将它从B矩阵中删除。当前有n-2个白点（两个红点），对每个白点都有到两个红点的两条边，通过比较这两者的大小，选出权值小的边，放入B矩阵的相应位置上，由此构建新的候选边矩阵B，此时B矩阵的有n-2列。(4)对新的B矩阵重复(2)和(3)，T中的边将越来越多，B矩阵的列数越来越少，当选入T中的红色边达到n-1条时结束运算，输出T。第二十六页，共一百六十一页，2022年，8月28日按照以上思路编写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,…,n。第二十七页，共一百六十一页，2022年，8月28日forj=2:nb(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，第三行表示所有连接红点和白点的边的权值第二十八页，共一百六十一页，2022年，8月28日whilesize(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,i);%累计最小生成树的长度

v=b(2,i);%把新入选最小生成树的边的白色端点变成当前红点第二十九页，共一百六十一页，2022年，8月28日t=find(c==b(2,i));c(t)=[];%把该点从白点集合中移出去b(:,i)=[];%把该边从候选边中删除

forj=1:length(c)d=a(v,b(2,j));ifd<b(3,j)b(1,j)=v;b(3,j)=d;endend第三十页，共一百六十一页，2022年，8月28日%以上循环调整候选边集合，入选该集合的边数等于当前白点数，对每一个白点入选一条边，该边通过比较连接该白点到红点的边的权值大小确定，小者入选。该循环是程序的关键和核心部分。endT,e以上程序以文件名prim.m存盘。第三十一页，共一百六十一页，2022年，8月28日例2以2007年研究生数学建模竞赛C题为例，已知县邮政局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);第三十二页，共一百六十一页，2022年，8月28日计算结果为：T=1567551116111016164111456784111617109151231314211139131415991011111419212121e=221T中每一列代表入选最小生成树的一条边，每一列有3个元素，前两个代表顶点的编号，第3个是边的权值。e是最小生成树的总长。第三十三页，共一百六十一页，2022年，8月28日三、Kruskal（克罗斯克尔）算法Kruskal（克罗斯克尔）算法又称“避圈法”，也是一种贪婪算法。给定加权连通图G={V,E}，Kruskal算法的基本思路如下：(1)把所有边按照权值的大小由小到大排序，将最小边入选最小生成树T。(2)从剩下的边中选取权值最小的边，并且该边与T中已经存在的边不形成圈，将它也取进T中（若某边权值虽然小，但形成圈则舍去此边，并且另选。重复步骤(2),直至入选T的边达到n-1条为止。第三十四页，共一百六十一页，2022年，8月28日由以上思路可知，Kruskal算法的关键是如何判断一条候选边是否会与T中已有边形成圈，下面介绍一种判断方法。设所有顶点都是红色，选入最小生成树T的边为红色，没有选入的边为白色。则红点和红边会形成一个或者一个以上的连通分支，它们都是G的子树，当一条待选边的两个端点属于同一棵子树时候就会形成圈，否则不构成圈，且该边入选后会使原来两个不连通的红色子树合并成为一棵红色连通子树。因此判断一条边是否会与现有红边形成圈，只需要判断该边的两个端点是否属于同一棵子树。第三十五页，共一百六十一页，2022年，8月28日可以用下面的方法来实现以上判断：给每棵子树一个不同的编号，对每一个顶点引入一个标记t，表示该顶点所在子树的编号。当加入一条红色边时，就该边两个端点所在的子树连接起来成为一棵子树，从而两棵子树中的顶点标记要改成一样。第三十六页，共一百六十一页，2022年，8月28日按照以上思路编写Matlab程序如下：function[T,c]=kruskal(a)n=size(a,1);%n是总顶点数m=0;fori=1:n-1forj=i+1:nifa(i,j)>0&a(i,j)<infm=m+1;b(1,k)=i;b(2,k)=j;b(3,k)=a(i,j);endendend第三十七页，共一百六十一页，2022年，8月28日%以上循环生成图的边权矩阵，该矩阵有3行，第1行和第2行是顶点的编号，第3行是边的权值，矩阵的列数对于图的边数，每一列代表一条边。程序运行以后，该矩阵的列数（即图的总边数记录在变量m中）。[B,i]=sortrows(b',3);B=B';%实现对边权矩阵按照权值大小由小到大排序，B是排序以后的边权矩阵。k=0;%k表示已经被选入最小生成树的边数t=1:n;%开始每个顶点各自为一棵独立的子树，子树的编号分别1,2,…,n。T=[];c=0;%开始时最小生成树为空集，权值之和为0第三十八页，共一百六十一页，2022年，8月28日fori=1:m%对排序以后的边权矩阵，按顺序考察每一条边ift(B(1,i))~=t(B(2,i))%当第i条边的两个端点所在子树的编号不相等时，该边与已经选入最小生成树的边不形成圈，于是运行以下语句

k=k+1;%入选最小生成树的边数k增加1T(:,k)=B(:,i);%把该边选入最小生成树的集合Tc=c+B(3,i);%把该边的权值加到最小生成树的总权值之中

tmin=min(t(B(1,i)),t(B(2,i)));tmax=max(t(B(1,i)),t(B(2,i)));第三十九页，共一百六十一页，2022年，8月28日%入选边的两个端点分别属于不同的子树，t标号不同，对这两个t标号排序forj=1:n

ift(j)==tmaxt(j)=tmin;

endend%将入选边所属两个t标号合并成一个（大标号改为小标号）end第四十页，共一百六十一页，2022年，8月28日

ifk==n-1%如果入选最小生成树的边数达到n-1，则结束计算

break;endendT,c以上程序以文件名kruskal.m存盘。第四十一页，共一百六十一页，2022年，8月28日仍然以例2的数据为例，先输入数据矩阵a，然后运行[T,e]=kruskal(a)得到计算结果。T=6111610191557412531127161711510166851611413141499910111111131314141519212121e=221该结果与Prim算法求出的结果相同。虽然Prim和kruskal两种算法的思路都由贪婪法发展而来，但它们用来求最小生成树时，最终输出结果必定是最优解。第四十二页，共一百六十一页，2022年，8月28日最小生成树

的图形第四十三页，共一百六十一页，2022年，8月28日四、用LINGO求最小生成树1.把最小生成树问题转化为整数规划采用一定的方法可以把最小生成树问题转化为整数规划，然后用LINGO求解。节点1表示树根，点i到点j的距离用Cij表示，当两个节点之间没有线路相通时，两点之间距离用M(很大的实数)表示。引入0-1整数变量xij：若xij=1(且i≠j)表示从i到j的边在树中，xij＝0则表示该边不在树中。第四十四页，共一百六十一页，2022年，8月28日目标函数约束条件：(1)除树根外每个点都有线路通到(且只需要一次)表示为(2)至少有一条线路从1出来第四十五页，共一百六十一页，2022年，8月28日以上约束条件是必要条件，但不充分，类似于TSP问题，增加一个变量u，再附加约束条件：(1)限制uj的取值范围为：u1=0，1≤uj≤n-1，j=2,3,...,n；用以下不等式可以达到目的：uj≥1且uj≤

n-1-(n-2)x1j，j>1，(2)如果线路从j到k，则uk=uj+1，且避免来回重复和圈，约束条件为:uj≥uk+xkj-(n-2)(1-xkj)+(n-3)xjk，1≤k≤n，2≤j≤nj≠k；第四十六页，共一百六十一页，2022年，8月28日最优连线(最小生成树)转化为整数规划：第四十七页，共一百六十一页，2022年，8月28日例3假设某电力公司计划在七个村庄之间架设电线，各村庄之间的距离如图所示．试求出使电线总长度最小的架线方案．第四十八页，共一百六十一页，2022年，8月28日2.LINGO程序编写LINGO程序如下：MODEL:sets:city/1..7/:u;!定义7个城市;link(city,city):dist,x;!距离矩阵和决策变量;endsetsn=@size(city);data:!dist是距离矩阵;第四十九页，共一百六十一页，2022年，8月28日dist=034710010010030324100100430100571007210002100610045201410010071001021001001006420;!这里可改为你要解决的问题的数据;enddata第五十页，共一百六十一页，2022年，8月28日

min=@sum(link:dist*x);!目标函数;U(1)=0;@for(link:@bin(x));!定义X为0\1变量;@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第五十一页，共一百六十一页，2022年，8月28日计算结果：目标函数值(最优连线的长度)为13，最优连线的构成如图所示4123567第五十二页，共一百六十一页，2022年，8月28日§4旅行商问题第五十三页，共一百六十一页，2022年，8月28日一、旅行商问题的基本概念旅行商问题（又称货郎担问题，travelingsalesmanproblem，简称TSP问题）是典型的组合优化问题，并且是一个NP完全难题，其提法为：有n个城市，相互之间的旅行费用（或距离）为已知，有一个旅行推销商，从某个基点城市出发，要遍访其余n-1个城市至少一次，最后回到出发点，试找出总费用最小（或总路程最短）的旅行路线。称能够到每个城市至少一次的回路为旅行商回路，其中费用最少者为最优旅行商回路.

第五十四页，共一百六十一页，2022年，8月28日在图论中，经过所有顶点恰好一次的圈（路）称为哈密顿圈（路），简称H圈（H路），存在H圈的图称为哈密顿图，简称H图。旅行商问题是指在赋权图上经过每个顶点至少一次，且总长度（路径上权的总和）达到最小的闭通路。在加权的连通无向图中，权最小的H圈简称最优H圈；经过每个顶点至少一次且权最小的闭通路称为最优旅行商回路。注意：最优H圈与最优旅行商回路两者是有区别的，最优H圈只允许经过每个顶点恰好一次，而最优旅行商回路允许经过某些顶点一次以上。第五十五页，共一百六十一页，2022年，8月28日定理1在加权图G=（V，E）中，若对任意顶点x,y,z（z≠x,z≠y），都满足w(x,y)≤w(x,z)+w(y,z)（三角形的两边之和大于等于第三边，称为三角不等式），则该图的最优哈密顿圈也是最优旅行商回路。对于连通的非完全赋权图G，先求出任意两点之间的最短路，然后用最短路作为每一条边的权，构造一个以V为顶点集的完全图G’=（V，E’），容易证明，在如此构造出来的图G’中，各边的权自然满足三角不等式，故在加权图G中寻求最优旅行商回路的问题就可以转化为在图G’中寻求最优哈密顿圈的问题。第五十六页，共一百六十一页，2022年，8月28日寻找最优哈密顿圈和最优旅行商回路是图论中的典型问题，而且是一个NP完全难题。问题的求解没有多项式时间算法，除了穷举法，目前还没有寻找最优解的算法，随着顶点数的增加，运算所需时间呈指数级增长，当顶点数较大时，求出最优解所需时间可能是难以忍受的。可行的方法是用近似算法，力争在较短时间寻找接近最优解的近似最优解。旅行商问题得到了许多学者的关注和长期研究，提出了多种近似算法，例如分支定界法、遗传算法、模拟退火法、蚁群算法、神经网络方法、粒子群优化算法、重绕最小生成树法、二次逐边修正法等。第五十七页，共一百六十一页，2022年，8月28日二、用LINGO求解TSP问题的方法一1.把最优哈密顿圈问题转化为0-1线性规划

将任意两点之间的最短路作为两点之间边的权构造完全图G’。引入0-1整数变量xij(且i≠j)：若xij=1则边i-j在回路中，而xij＝0则表示否。目标函数首先必须满足约束条件：对每个城市访问一次且仅一次。从城市i出发一次(到其它城市去),表示为第五十八页，共一百六十一页，2022年，8月28日从某个城市到达j一次且仅一次，表示为：以上建立的模型类似于指派问题的模型，对TSP问题只是必要条件，并不充分。第五十九页，共一百六十一页，2022年，8月28日例如，用图示路线连接六个城市，满足以上两个约束条件，但这样的路线出现了两个子回路，两者之间不通，不构成整体巡回路线。为此需要考虑增加充分的约束条件以避免产生子巡回。下面介绍一种方法：增加变量ui,i=2,3,…,n，（它的大小可以取正整数：例如从起点出发所达到的城市u=2,依此类推）。312456第六十页，共一百六十一页，2022年，8月28日附加约束条件：ui-uj+nxij≤n-1,i=1,…,n，j=2,…,n，且i≠j

。下面证明：(1)任何含子巡回的路线都必然不满足该约束条件（不管ui如何取值）；(2)全部不含子巡回的整体巡回路线都可以满足该约束条件（只要ui取适当值）。用反证法证明(1),假设存在子巡回，则至少有两个子巡回。那么（必然）至少有一个子巡回中不含起点城市1，如上图中的4－5－6－4，则必有

u4-u5+n≤n-1，u5-u6+n≤n-1，u6-u4+n≤n-1，把这三个不等式加起来得到n≤n-1，不可能，故假设不能成立。而对整体巡回，因为附加约束中j≥2,不包含起点城市1，故不会发生矛盾。第六十一页，共一百六十一页，2022年，8月28日对于整体巡回路线，只要ui取适当值，都可以满足该约束条件：(ⅰ)对于总巡回上的边，xij=1,ui可取访问城市i的顺序数，则必有ui-uj＝-1，约束条件ui-uj+nxij≤n-1变成：-1+n≤n-1，必然成立。(ⅱ)对于非总巡回上的边，因为xij=0，约束条件ui-uj+nxij≤n-1变成-1≤n-1，肯定成立。综上所述，该约束条件只限止子巡回，不影响其它，于是TSP问题转化成了一个整数线性规划问题。第六十二页，共一百六十一页，2022年，8月28日求最优哈密顿圈可以表示为规划：第六十三页，共一百六十一页，2022年，8月28日2.LINGO程序!旅行售货员问题;model:sets:city/1..17/:u;!定义17个城市;link(city,city):dist,!距离矩阵;x;!决策变量;endsetsn=@size(city);data:!距离矩阵;第六十四页，共一百六十一页，2022年，8月28日C=016.311.910.12812.9620.628.422.220.835.722.130.223.727.83616.3012.226.423.98.810.336.940.132.216.731.614.722.87.411.519.711.912.202236.1215.932.540.334.128.943.826.93519.617.625.810.126.422020.42316.110.518.312.115.228.132.238.433.837.946.12823.936.120.4015.1342416.28.37.27.724.31831.335.432.912.98.8212315.1018.933.531.323.47.922.89.217.316.220.328.5610.35.916.13418.9026.634.428.226.841.72533.117.721.83020.636.932.510.52433.526.607.815.725.731.742.74244.348.456.628.440.140.318.316.231.334.47.807.923.423.940.534.247.551.649.122.232.234.112.18.323.428.215.77.9015.51632.626.339.643.741.220.816.728.915.27.27.926.825.723.415.5014.917.125.224.128.236.435.731.643.828.17.722.841.731.723.91614.9018.410.325.733.425.222.114.726.932.224.39.22542.740.532.617.118.408.17.326.22330.222.83538.41817.333.14234.226.325.210.38.1015.423.114.923.77.419.633.831.316.217.744.347.539.624.125.77.315.4018.920.327.811.517.637.935.420.321.848.451.643.728.233.426.223.118.908.23619.725.846.132.928.53056.649.141.236.425.22314.920.38.20;第六十五页，共一百六十一页，2022年，8月28日!这里可改为你要解决的问题的数据;enddata!目标函数;min=@sum(link:dist*x);@FOR(city(K):

!进入城市K;

@sum(city(I)|I#ne#K:x(I,K))=1;

!离开城市K;

@sum(city(J)|J#ne#K:x(K,J))=1;);

!保证不出现子圈;第六十六页，共一百六十一页，2022年，8月28日

@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为0\1变量;end第六十七页，共一百六十一页，2022年，8月28日计算结果：目标函数值：159.3路线：1→7→3→16→17→14→13→15→2→6→11→12→5→10→9→8→4→1因为以上规划是线性规划，所以求解不费时，当顶点数为20－30个时，一般几分钟就可以得到最优解。利用LINGO软件的强大优化能力，不必研究旅行商问题的算法，通过编写不太复杂的LINGO程序，能够较快地解决实际问题，达到事半功倍的效果。

第六十八页，共一百六十一页，2022年，8月28日三、用LINGO求解TSP问题的方法二1.对城市排序，找出最优排序在现实中的城市交通图中，有些城市之间有直接道路，有些则没有，如果两点之间没有直接的通路，则两点之间的距离取最短路（经过其它点），即用任意两点之间的最短路Cij作为图的距离矩阵，构成一个完全图G'，其任意一对顶点都有一条边相连。图G的最优旅行商回路等价于图G'的最优哈密顿圈，此时形式上的环形巡回路线实际上个别点有可能不止经过一次。第六十九页，共一百六十一页，2022年，8月28日设某个城市为旅行的出发地和终点（相当于总部所在地），旅行者从该城市出发到其它n个城市各一次且仅一次，最后回到出发地。我们把行进路线分成n步，每一步到一个城市（第n+1步返回出发地），于是一条旅行路线就相当于n个城市的一种排列，n个城市共有n!种排列方式。排序不同则总里程（或费用）可能不同，总里程（或总费用）最小的排序就是我们要寻找的最优路线。第七十页，共一百六十一页，2022年，8月28日引入0-1型决策变量Xkj，下标k表示旅行的步数，下标j表示到达哪一个城市，Xkj=1表示旅行者第k个目的地（到达点）是城市j，Xkj=0则表示否。用lj表示总部到各城市的距离，用Cij表示城市i与城市j之间的最短路。从出发地到第1个点的路程为从最后一个点返回出发地的里程为

第七十一页，共一百六十一页，2022年，8月28日假设在第k步到达城市i，在第k+1步达到城市j，即Xki=Xk+1,j=1，则走过的里程为：

Cij·Xki·Xk+1,j从第1点到第n点走过的总里程为目标函数为第七十二页，共一百六十一页，2022年，8月28日约束条件有以下2条：(1)每一步到达一个城市，即(2)每一个城市必须到一次且只需一次，即第七十三页，共一百六十一页，2022年，8月28日综上所述，可以把最优哈密顿圈问题转化成如下非线性0-1

规划第七十四页，共一百六十一页，2022年，8月28日以上规划中允许包含其它约束条件。用LINGO可以求解该规划，举例如下。某县邮局和10个乡镇支局组成该县的邮政运输网络，已知县局到各支局的距离和支局之间的距离矩阵（数据在程序中）。用一辆邮车完成邮件运输任务，邮车从县局出发到各支局去一次且只需一次，最后回到县局，求总路程最短的行驶路线。解：本题是“旅行商”问题。可以用上面介绍的方法求解。第七十五页，共一百六十一页，2022年，8月28日编写LINGO程序如下：MODEL:SETS:CITY/1..10/:JL;STEP/1..10/;LINE(STEP,CITY):X;LINKS(CITY,CITY):C;ENDSETS第七十六页，共一百六十一页，2022年，8月28日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,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第七十七页，共一百六十一页，2022年，8月28日@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(LINKS(I,J):C(I,J)*X(N,I)*X(N+1,J)));MIN=L1+LX;END第七十八页，共一百六十一页，2022年，8月28日在程序运行前需要对LINGO的参数作必要的设置。对于非线性规划，LINGO提供两种求解方法，一种是“GlobalSolver”（称为全局优化求解器），另一种是“MultistartSolver”（称为多起点算法），全局优化求解器优点是确保找到全局最优解，缺点是有时需要较长运行时间。多起点算法的优点是节省运行时间，但不能保证找到的解就是全局最优解，设置起点数多一些往往找到的解就是全局最优解。点击菜单“Options”，再打开全局优化求解器“GlobalSolver”选项，可以选或不选“GlobalSolver”，当选择多起点算法“MultistartSolver”时，需要设置起点数，若选择“SolverDecides”表示由LINGO决定。第七十九页，共一百六十一页，2022年，8月28日对以上程序，我们选择“GlobalSolver”，点击菜单“Options”，在全局优化求解器“GlobalSolver”选项框内打“√”，再点击“确定”。运行以上程序，费时4分多钟，得到最优解：目标函数值（总路程）260公里邮车的行驶路线为：县局→8→9→10→7→6→5→4→1→2→3→县局第八十页，共一百六十一页，2022年，8月28日四、多旅行商（MTSP）问题1.

多旅行商问题的概念在现实中问题中，有时候不是由一人走遍所有点，而是由几个人分工合作，每个人只到其中部分城市，每个点都有人来过一次且只需一次，事先不指定谁到哪些点，求出使总路程最小的旅行规划（每个人的行走路线）。例如邮路规划中，为了在允许的时间内完成邮件运输任务，县局的邮车往往不止1辆，而是用若干辆邮车分工运输，只要保证每个支局有邮车来过即可，为了节省行驶费用，需要规划几辆邮车的最佳路线。这就是多旅行商问题。第八十一页，共一百六十一页，2022年，8月28日多旅行商问题的提法如下：有n+1个城市，相互间的路程（或旅行费用）为已知，有k个旅行商都从总部所在城市出发，赴其它城市旅行推销，分工遍历其余n个城市，即每个城市各有任意一名旅行商来过一次且仅一次，最后都回到出发地，目标是总路程最短或总费用最省。多旅行商问题在物流配送、邮路优化等方面具有较高的实用价值，而在现实问题中，研究对象往往不是单纯的旅行商问题，而要考虑各种约束条件，例如时间约束、载重量约束等等。研究这一类带约束条件的多旅行商问题具有很强的现实意义。

第八十二页，共一百六十一页，2022年，8月28日在现实的多旅行商问题中，往往带有约束条件，例如时间约束、载重量约束等等。带约束条件的多旅行商问题具有广泛现实意义，且是极具挑战性的难题，我们仍然把它转化为0-1非线性规划并编成LINGO程序来求解。实例某县邮政局管辖16个支局，已知县局到各支局的距离以及16个支局之间的距离矩阵。寄达各支局和各支局收寄的邮件(袋)如下表所示：第八十三页，共一百六十一页，2022年，8月28日县邮局和各支局分布图第八十四页，共一百六十一页，2022年，8月28日每一辆邮车最多装载65袋邮件，邮车的运行成本为3元/公里。试用最少邮车，并规划邮车的行驶路线使总费用最省。分析：首先考虑最少邮车数量，由题目所给表中数据，寄达16个支局的邮件总数为176袋，从各支局收寄的邮件总数为170袋，每一辆邮车最多容纳65袋邮件，至少需要176/65≈2.7辆邮车，由于邮车数量为整数，故最少需要3辆邮车。如果3辆邮车能够完成邮件运输任务，则3辆车就是邮车数量的最优解。

第八十五页，共一百六十一页，2022年，8月28日运输费用与行驶里程成正比，总里程最短对应总费用最省。把16个支局放在一起作为一个整体考虑，找出3条邮路，每条邮路都从县局出发，到若干支局进行卸装，最后回到县局。各邮车路过的支局数量未知，合理安排各邮车的行驶路线，由3辆邮车分别承包运输，在满足运载量约束前提下，把3条巡回路线的总里程最小作为优化的目标。该问题相当于附带约束条件的多旅行商模型。第八十六页，共一百六十一页，2022年，8月28日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)任何一辆车在任何一步到达一个支局

，即第八十七页，共一百六十一页，2022年，8月28日(2)任何一个支局必须有一辆邮车到达一次且只需要一次，即

(3)在邮车行进的任何路段上，装载的邮件不超过65袋。

设寄达各支局的邮件量为Pj，各支局收寄的邮件量为Qj。

装载量是动态变化的，以第1辆邮车为例，出发时的装载量为第八十八页，共一百六十一页，2022年，8月28日到第1个支局卸装以后，装载量变为在行驶过程中，装载量的递推公式为约束条件为第八十九页，共一百六十一页，2022年，8月28日综上所述，建立多旅行商问题的0-1规划模型如下：第九十页，共一百六十一页，2022年，8月28日装载量的计算公式为：第九十一页，共一百六十一页，2022年，8月28日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第九十二页，共一百六十一页，2022年，8月28日DATA:JL=27361711243144403020252121182736;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=031273851587167574752482141526131019332732456453476157524856632719014273447493929423838293844

3833140132033352515333232152430512727130921372626434545282938583234209013323235475252353342714547332113019303950656548444067644935373219011203154613425215753392526323011010204351241413474729152635392010018364114918

第九十三页，共一百六十一页，2022年，8月28日

526142334347503120180234625142348573832455265544336230272233422152383245526561514146270394857414829152835483424142522390112052563824293344251491433481109616344303842402113182342572090;ENDDATA第九十四页，共一百六十一页，2022年，8月28日@FOR(LINEX:@BIN(X));@FOR(LINEY:@BIN(Y));@FOR(LINEZ:@BIN(Z));M1=@SIZE(STEPX);M2=@SIZE(STEPY);M3=@SIZE(STEPZ);@FOR(STATION(I):@SUM(STEPX(N):X(N,I))+@SUM(STEPY(N):Y(N,I))+@SUM(STEPZ(N):Z(N,I))=1);@FOR(STEPX(N):@SUM(STATION(I):X(N,I))=1);@FOR(STEPY(N):@SUM(STATION(I):Y(N,I))=1);@FOR(STEPZ(N):@SUM(STATION(I):Z(N,I))=1);第九十五页，共一百六十一页，2022年，8月28日WX0=@SUM(STATION(I):P*@SUM(STEPX(N):X(N,I)));WY0=@SUM(STATION(I):P*@SUM(STEPY(N):Y(N,I)));WZ0=@SUM(STATION(I):P*@SUM(STEPZ(N):Z(N,I)));WX(1)=WX0-@SUM(STATION(J):(P(J)-Q(J))*X(1,J));WY(1)=WY0-@SUM(STATION(J):(P(J)-Q(J))*Y(1,J));WZ(1)=WZ0-@SUM(STATION(J):(P(J)-Q(J))*Z(1,J));@FOR(STEPX(N)|N#GE#2:WX(N)=WX(N-1)-@SUM(STATION(J):(P(J)-Q(J))*X(N,J)));@FOR(STEPY(N)|N#GE#2:WY(N)=WY(N-1)-@SUM(STATION(J):(P(J)-Q(J))*Y(N,J)));@FOR(STEPZ(N)|N#GE#2:WZ(N)=WZ(N-1)-@SUM(STATION(J):(P(J)-Q(J))*Z(N,J)));WX0<=65;WY0<=65;WZ0<=65;@FOR(STEPX(N):WX(N)<=65);@FOR(STEPY(N):WY(N)<=65);第九十六页，共一百六十一页，2022年，8月28日@FOR(STEPZ(N):WZ(N)<=65);L1=@SUM(STATION(I):(X(1,I)+X(M1,I))*JL(I));L2=@SUM(STATION(I):(Y(1,I)+Y(M2,I))*JL(I));L3=@SUM(STATION(I):(Z(1,I)+Z(M3,I))*JL(I));LX=@SUM(STEPX(N)|N#LT#M1:@SUM(LINKS(I,J):C(I,J)*X(N,I)*X(N+1,J)));LY=@SUM(STEPY(N)|N#LT#M2:@SUM(LINKS(I,J):C(I,J)*Y(N,I)*Y(N+1,J)));LZ=@SUM(STEPZ(N)|N#LT#M3:@SUM(LINKS(I,J):C(I,J)*Z(N,I)*Z(N+1,J)));MIN=L1+L2+L3+LX+LY+LZ;END第九十七页，共一百六十一页，2022年，8月28日三辆邮车各自负责的支局数量有若干种分配方法，例如有6,5,5、6,6,4、7,5,4等不同分组法。经过试验，以6,5,5方案最优。目标函数值（3条邮路的总里程）为343km。第一条邮路：县局→10→9→8→7→5→6→县局，总里程121km，沿途各段邮件的装载量为64,56,58,63,65,61,65袋。注意：如果支局5和6的先后次序倒过来，即走7→6→5→县局，则里程为106km，减少15km，但是在支局6卸装以后，邮件达69袋，超过了装载量约束，看来先到支局5，后到支局6是因为避免超载的原因，被迫绕路，整体上仍然保持最优。第九十八页，共一百六十一页，2022年，8月28日第二条邮路：县局→14→15→16→11→12→县局，总里程105km，沿途各段邮件的装载量为61,55,52,54,49,54袋。第三条邮路：县局→13→1→2→3→4→县局，总里程117km，沿途各段邮件的装载量为51,53,52,51,50,51袋。第九十九页，共一百六十一页，2022年，8月28日三条邮路的图形如图所示

第一百页，共一百六十一页，2022年，8月28日§5中国邮递员问题第一百零一页，共一百六十一页，2022年，8月28日一、欧拉（Euler）图

定义：设图G={V,E}是连通无向图，则经过G的每边正好一次的道路称为欧拉道路（欧拉迹）；经过G的每边至少一次的闭通路称为巡回；经过G的每边正好一次的巡回称为欧拉巡回；存在欧拉巡回的图称为欧拉图；定理：一个非空连通图是欧拉图的充分必要条件是它没有奇点。推论：连通图G能够一笔画出（存在欧拉迹）的充要条件是所有顶点是偶点或者仅有两个顶点是奇点。第一百零二页，共一百六十一页，2022年，8月28日二、中国邮递员问题

1.概念邮递员从邮局出发，经过他所投递范围内的每一条街道至少一次，然后返回邮局，如何安排投递路线使总路程最短，这个问题由中国学者管梅谷于1962年首先提出并给出了一种解法，被国际上称为中国邮递员问题。用图来描述投递区域，用边表示街道，用点表示路口和邮局，则投递区构成一个非负的赋权连通图。中国邮递员问题就是在一个非负的赋权连通图中寻找一条总权最小的巡回，这种巡回称为最优巡回。

第一百零三页，共一百六十一页，2022年，8月28日2．欧拉图中的最优巡回若图G是欧拉图，则G的任何一个欧拉巡回都是最优巡回，因为欧拉巡回是一条通过G的每一条边恰好一次的巡回。此时可用Fleury算法来确定一个欧拉巡回。定义：设G是连通图，边，若从G中删除边e后，图不连通，则称边e为图G的割边。定理：e是G的割边的充要条件是e不含在G的圈中。第一百零四页，共一百六十一页，2022年，8月28日Fleury算法的基本思想：从任一点出发，每当访问一条边时，先进行检查，如果可供访问的边不止一条，则应选不是未访问边集构成的子图的割边作为访问边直到没有边可供选择为止。Fleury算法的步骤：(1)任意选取一个顶点v0，令W0=v0（作为起点）；(2)假设道路Wi=v0e1v1e2…eivi已经选定，则按以下方法从E\{e1,e2,…,ei}中选取一条边ei+1：①ei+1和vi相关联；②除非没有别的边可选择，否则ei+1不是Gi=G\{e1,e2,…,ei}的割边。③当第②步不能进行时就停止。

第一百零五页，共一百六十一页，2022年，8月28日3．非欧拉图中的最优巡回如果G不是欧拉图（图中有奇点），则G的任何一个巡回经过某些（与奇点相关联的）边必定多于一次。解决这一类问题的一般方法是，引入重复边，使原图成为欧拉图，并且添加的重复边的权的总和为最小。情形1G只有两个奇点u和v，求最优巡回的算法如下：(1)用Dijkstra算法或Floyd算法求出奇点u和v之间的最短路径P。(2)令G*=G∪P，则G*为欧拉图。(3)用Fleury算法来确定一个G*的欧拉巡回，这就是G的最优巡回。第一百零六页，共一百六十一页，2022年，8月28日情形2

G有2n个奇点（n>1），可以用Edmonds算法解决，其基本思路为：首先将奇点配对，使配对以后各对之间距离的总和（两点之间的距离按照最短路计算）达到最小（称为最佳配对）,求最佳配对的方法可以用匈牙利法或0-1规划法等方法（可以用Lingo实现）。然后把每一对点之间的最短路作为边添加到原图中,使之成为欧拉图G*，找出G*的欧拉巡回就是原图的最佳巡回。第一百零七页，共一百六十一页，2022年，8月28日算法步骤如下：(1)用Floyd算法求出所有奇点之间的最短路径和距离矩阵。(2)用匈牙利法或0-1规划法求出所有奇点之间的最佳配对。(3)在原图上添加最佳配对所包含的两两顶点之间的最短路得到欧拉图G*。(4)用Fleury算法确定一个G*的欧拉巡回，这就是G的最优巡回。

第一百零八页，共一百六十一页，2022年，8月28日三、Fleury算法的Matlab程序

设图是连通无向图，如果所有顶点都是偶点，则该图是欧拉图，必然存在欧拉巡回，如果恰好有两个奇次顶点，则称该图为半欧拉图，必然存在起点在奇点（两个奇点中的一个）且终点在另一个奇点的欧拉道路。这两种情况下都可用fleury算法确定一条欧拉巡回或者欧拉道路。第一百零九页，共一百六十一页，2022年，8月28日按照fleury算法的思路编写Matlab程序。主要程序arEuler根据图的边集确定是否为欧拉图、半欧拉图或非欧拉图，如果是欧拉图则用fleury算法找到一条欧拉巡回路线（欧拉图的欧拉巡回不止一条，输出的是其中的一条），如果是半欧拉图则返回一条欧拉道路，其起点在两个奇点之一，终点是另一个奇点。第一百一十页，共一百六十一页，2022年，8月28日function[eu,cEu]=arEuler(E)%输入参数E是图的边集（m行2列矩阵，每一行的两个数字代表一条边的两个顶点，共有m条边），输出参数eu有三种结果：若为欧拉图则eu=1；半欧拉图则eu=0.5；否则eu=0。输出参数cEu是m行1列矩阵，表示欧拉巡回或欧拉道路中边的序列。eu=0;%eu的初始值为0cEu=[];%cEu开始时为空集ncV=arComp(E);%调用函数arComp确定图的分枝构成，判断是否连通

第一百一十一页，共一百六十一页，2022年，8月28日ifmax(ncV)>1,%表示有2个或以上互不连通的部分

return%不是连通图就返回endn=max(max(E(:,1:2)));%n是图的顶点总数m=size(E,1);%m是边的总数第一百一十二页，共一百六十一页，2022年，8月28日fori=1:n

b(i)=0;forj=1:mifE(j,1)==i|E(j,2)==ib(i)=b(i)+1;endendend%b表示各顶点的度数第一百一十三页，共一百六十一页，2022年，8月28日rp=rem(b,2);%各顶点的度数除2取余数，偶点的余数为0，奇点的余数为1srp=sum(rp);%srp是rp的总和switchsrpcase0,%若余数的总和为0，则所有顶点为偶点，原图是欧拉图

eu=1;case2,%恰好有两个奇点，原图是半欧拉图

eu=0.5;otherwise,%否则是非欧拉图

return第一百一十四页，共一百六十一页，2022年，8月28日end%以下程序寻找一条欧拉巡回或欧拉道路

ifsrp==0,%对于欧拉图

v1=1;%把第一个顶点作为欧拉巡回的起点

else%对于半欧拉图

v1=find(rp);%先找出奇点

v1=v1(1);%把第一个奇点作为欧拉道路的起点

end第一百一十五页，共一百六十一页，2022年，8月28日

vc=v1;%vc是当前顶点

m=size(E,1);%m是边的总数

E1=[E(:,1:2),[1:m]'];%E1代表候选边集，开始时它的前两列与E相同，第三列表示边的顺序号%以下是Fleury算法wh