当前位置： >>
图论中几个典型问题的求解
图论中几个典型 问题的求解§1 图的基本概念图是一种直观形象地描述已知信息的方 式，它使事物之间的关系简洁明了，是分 析问题的有用工具，很多实际问题可以用 图来描述。一、图的定义图论是以图为研究对象的数学分支，在图论 中，图由一些点和点之间的连线所组成． 称图中的点为顶点（节点）
，称连接顶点的 没有方向的线段为边，称有方向的线段为弧． 用 V={v1,v2,?} 表 示 全 体 顶 点 的 集 合 ， 用 E={e1,e2,?} 表示全体边的集合，如果对于E中的 任一条边ek，在V中都有一对顶点(vi,vj)和它对应， 则称由V和E组成的集体为一个图，记为G={V,E}， 简写为G．二、基本概念点与边相连接称为关联，与边e关联的顶点称为 该边的端点，与同一条边关联的两个顶点称为相 邻顶点，与同一个顶点关联的边称为相邻边．具 有相同顶点的边称为平行边，两个端点重合的边 称为环．所有线段都没有方向的图称为无向图， 所有线段都有方向的图称为有向图，既有边也有 弧的图称为混合图．在无向图中，没有环和平行 边的图称为简单图，任意两个顶点之间都有一条 边相连的简单图称为完全图．任意两个顶点之间 有且只有一条弧相连的有向图称为竞赛图．在无向图中与顶点v关联的边的数目（环算两 次）称为该顶点的度（或次数），记为d(v)。度 为奇数的顶点叫做奇点，度为偶数的顶点叫做偶 点。在有向图中，从顶点v引出的边的数目称为 该顶点的出度，记为d+(v)，从顶点v引入的边的 数目称为该顶点的 入度 ， 记为 d-(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为赋权图．通常称赋权 的有向图为网络．v4e4e9v2e1v1 e2e5e3 e6v5e8e10e11v7v3e7v6图中边e6 和e7 是平行边，e9 是环，顶点v4 是悬 挂点，边e4是悬挂边．§2 最短路问题最短路问题是图论应用的基础，很多实际问 题，如线路的布设、运输规划、运输网络最小费 用流等问题，都可以通过建立最短路模型来求解。 有些有深度的图与网络优化问题，如旅行售货商、 中国邮递员等问题，需要在首先求出任意两点之 间最短路的基础上解决。 一、最短路的概念给定一个连通的赋权图G={V,E}，设R是连接 节点vi 和vj 的一条路，该路的权定义为路中所有 各边权之和，如果路R在所有连接节点vi和vj的路 中权最小，则称它为vi和vj间的最短路。二、任意两点之间的最短路(Floyd算法) Floyd算法利用距离矩阵进行迭代运算，可以 一次性地求出任意两点之间的最短路，该方法的 思路有创意，计算量小，编程较简单，又称矩阵 求解法。 1．算法原理设A=[aij]m×n 是图的权矩阵（也称带权邻接矩 阵），其中aij是图上连接顶点i和j的边的权，如 果两顶点之间没有直接相连的边（即两顶点不相 邻），则aij=Q。令矩阵D(0)=A，作为迭代的初始矩阵，从它出 发按照一定规则求D(1)，又由D(1)按照类似的规则 求D(2)，依此类推进行迭代直至求出D(n)，设矩阵 D(m)的元素为dij(m)，迭代规则为：d(1) ij? min {d , d( 0) ij( 0) i1? d }, i ? j( 0) 1j上式表示dij(1)在dij(0)以及从顶点vi经过顶点v1到 vj的权之和di1(0)+d1j(0)两者之中选择最短长度。依 此规则迭代。d( 2) ij? min {d , d(1) ij(1) i2? d }, i ? j(1) 2j上式表示dij(2)在dij(1)以及从顶点vi经过顶点v2到 vj的权之和di2(1)+d2j(1)两者之中选择最短长度。依 此类推，迭代公式为 ：d( m) ij? min {d( m?1) ij,d( m?1) im?d( m?11) mj}, i ? j上式表示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; end endfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)&D(i,j) D(i,j)=D(i,k)+D(k,j); %在循环中进 行矩阵迭代 R(i,j)=R(i,k); % R是路径矩阵 end end end end D,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,30,inf,inf,inf,21,13,20,inf,inf,inf,in f,9,0]; [D,R]=floyd(a);输入数据中的inf表示无穷大（两个顶点之间 没有边直接相连）。 运行以上程序，求得最短路矩阵D和最短路的 路径矩阵。此处省略结果。§3 最小生成树一、 最小生成树的概念树是图论中的一种简单而重要的图，连通并 且无圈的无向图称为树，常用T表示。树有以下 性质： (1) 树中任意两点之间有唯一路径； (2) 树的边数等于顶点数减1； (3) 在树中删去任意一条边就不连通； (4) 在树中任意两个不相邻的顶点间添加一条 边，则恰好产生一个圈。具有n个顶点的无向连通图是树的充分必要条 件是它有n-1条边．连通图G的子图T，如果它的 顶点集与G的顶点集相同，且T为树，则称T是图 G的生成树，又称支撑树。如果图的边有权（对 应于边的实数），则生成树上各边权的总和称为 生成树的权，生成树并不唯一，权达到最小的生 成树称为最小生成树(Minimal Spanning Tree， 简称MST)，最小生成树不一定唯一．最小生成树是网络优化中的一个重要问题， 在网络设计中有广泛的应用，例如如何修筑一些 公路把若干个城镇连接起来且总里程最短；如何 架设通讯网络将若干个地区连接起来且总费用最 省；如何修筑水渠将水源和若干块待灌溉的土地 连接起来且总距离最短等等．这些应用问题通称 为最优连线问题，其实质是寻找图的最小生成 树．二、Prim（普里姆）算法 求图的最小生成树最常用的算法有两种： Prim（普里姆）算法和Kruskal（克罗斯克尔） 算法，这两种方法都由贪婪法的思想发展而来。 贪婪法又称贪心法，该法总是做出在当前看 来最好的选择，也就是说该算法并不从整体最优 考虑，它所做出的选择只是在某种意义上的局部 最优选择。虽然贪婪算法不能对所有问题都得到 整体最优解，但是它对某些问题能够得到整体最 优解，例如图的固定起点的最短路问题，最小生 成树问题。有时候，即使贪婪算法不能得到整体 最优解，但其结果却是整体最优解的很好近似。Prim 算 法 的 思 路 是 ： 把 所 有 顶 点 分 成 部 分 （两个集合），一个用S表示（该集合中的顶点 都涂成红色），另一个用V-S表示（该集合中的 顶点都涂成白色），开始时S中只有一个顶点v1， 其余顶点都是白色，在一个端点为红色，另一个 端点为白色的边中选取权最小的边，将该边涂红 （表示入选最小生成树）并且把该边的白色端点 也涂红（表示移入S中）这个过程一直进行下去， S中的端点越来越多，直到所有顶点都涂成红色 为止，或者说红色边达到n-1条为止。从Prim算法的思路中可以看出，该算法的关 键是如何找出连接红点和白点的所有边中找出权 最小的边。若G为完全图，当前有k个红点，则 有n-k个白点，有k(n-k)条连接红、白点的边，为 了在如此众多的边中找到权最小的边，可以分两 步走，对每一个白点，先从连接该点至k个红点 的k条中找出权最小的边作为候选边，然后对n-k 个白点，从n-k条候选边中找出权最小的边。实现Prim算法的Matlab编程思路如下： (1) 设第一个红点是节点v1。构建初始候选边 的权矩阵B。该矩阵有3行，第一行表示当前红 点，开始时第一个红点是v1 ，故第一行都是1， 第二行表示白点，开始时白点的序号是2,3,…,n， 第三行表示连接红点和白点的边的权值。当前入 选最小生成树的最短边将从该矩阵中产生。初始 最小生成树T是空集。 (2) 对B矩阵的第3行排序，即对候选边的权值 进行排序，选取最短边（权值最小的边），把该 边涂红（选入最小生成树的边集T），该边的白 色端点也涂成红色。(3) 将(2)选出的边移出B（不参与下一轮竞 选），即将它从B矩阵中删除。当前有n-2个白点 （两个红点），对每个白点都有到两个红点的两 条边，通过比较这两者的大小，选出权值小的边， 放入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,…,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,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 d&b(3,j) b(1,j)=v; b(3,j)=d; end end%以上循环调整候选边集合，入选该集合的 边数等于当前白点数，对每一个白点入选一条边， 该边通过比较连接该白点到红点的边的权值大小 确定，小者入选。该循环是程序的关键和核心部 分。 end T,e 以上程序以文件名prim.m存盘。例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,30,inf,inf,inf,21,13,20,inf,inf,inf,in f,9,0]; [T,e]=prim(a);计算结果为： T=1 5 6 7 5 5 11 16 11 10 16 16 4 1 1 14 5 6 7 8 4 11 16 17 10 9 15 12 3 13 14 2 11 13 9 13 14 15 9 9 10 11 11 14 19 21 21 21e = 221 T中每一列代表入选最小生成树的一条边，每 一列有3个元素，前两个代表顶点的编号，第3个 是边的权值。e是最小生成树的总长。三、Kruskal（克罗斯克尔）算法 Kruskal（克罗斯克尔）算法又称“避圈法”， 也是一种贪婪算法。 给定加权连通图G={V,E}，Kruskal算法的基 本思路如下： (1) 把所有边按照权值的大小由小到大排序， 将最小边入选最小生成树T。 (2) 从剩下的边中选取权值最小的边，并且该 边与T中已经存在的边不形成圈，将它也取进T 中（若某边权值虽然小，但形成圈则舍去此边， 并且另选。 重复步骤(2), 直至入选T的边达到n-1条为止。由以上思路可知，Kruskal算法的关键是如何 判断一条候选边是否会与T中已有边形成圈，下 面介绍一种判断方法。 设所有顶点都是红色，选入最小生成树T的边 为红色，没有选入的边为白色。则红点和红边会 形成一个或者一个以上的连通分支，它们都是G 的子树，当一条待选边的两个端点属于同一棵子 树时候就会形成圈，否则不构成圈，且该边入选 后会使原来两个不连通的红色子树合并成为一棵 红色连通子树。因此判断一条边是否会与现有红 边形成圈，只需要判断该边的两个端点是否属于 同一棵子树。可以用下面的方法来实现以上判断：给每棵 子树一个不同的编号，对每一个顶点引入一个标 记t，表示该顶点所在子树的编号。当加入一条 红色边时，就该边两个端点所在的子树连接起来 成为一棵子树，从而两棵子树中的顶点标记要改 成一样。按照以上思路编写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 & a(i,j)&inf m=m+1; b(1,k)=i; b(2,k)=j; b(3,k)=a(i,j); end end end% 以上循环生成图的边权矩阵，该矩阵有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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)));% 入选边的两个端点分别属于不同的子树，t 标号不同，对这两个t标号排序 for j=1:n if t(j)==tmax t(j)= end end % 将入选边所属两个t标号合并成一个（大标 号改为小标号） endif k==n-1 % 如果入选最小生成树的边数达 到n-1，则结束计算 end end T,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 2 7 16 17 11 5 10 16 6 8 5 16 11 4 13 14 14 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(且i≠j)表示从i 到j的边在树中，xij＝0则表示该边不在树中。目标函数min z ? ? ? cij xiji j ?1nn约束条件： (1)除树根外每个点都有线路通到(且只需要一次) 表示为?xi ?1nij?1,j ? 2 ,3,?, n , i ? j(2)至少有一条线路从1出来?xj ?2n1j?1以上约束条件是必要条件，但不充分，类似于 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≤n j≠k；最优连线(最小生成树) 转化为整数规划：min z ? ? ? cij xiji ?1 j ?1nn? n ?? xi j ? 1 , j ? 2 ,?, n , i ? j i ?1 ? n ? x ?1, ?? 1 j j ?2 ? ?u1 ? 0 , 1 ? ui ? n ? 1 , i ? 2 , 3 ,?, n ?u ? u ? x ? ( n ? 2)(1 ? x ) ? ( n ? 3) x , k kj kj jk ? j ? k ? 1,?, n, j ? 2,?, n, j ? k ? ? ?例3 假设某电力公司计划在七个村庄之间架 设电线，各村庄之间的距离如图所示．试求出 使电线总长度最小的架线方案．4 7 6 2 4 2 3 4 5 5 4 723 11237 62. LINGO程序 编写LINGO程序如下： MODEL: sets: city / 1..7/:! 定义7个城市; link( city, city): dist, !距离矩阵和决策变量; 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 2 100 100 100 6 4 2 0; !这里可改为你要解决的问题的数据; enddata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))+(N3)*X(J,K); ); ); @sum( city( J)| J #GT# 1: x( 1, J)) &= 1; @for(city(K) | K #gt# 1:U(K)&=1; U(K)&=N1-(N-2)*X(1,K);); end计算结果：目标函数值(最优连线的长度)为13， 最优连线的构成如图所示42 23312517236§4 旅行商问题一、 旅行商问题的基本概念旅 行 商 问 题 （ 又 称 货 郎 担 问 题 ， traveling salesman problem，简称TSP问题）是典型的组 合优化问题，并且是一个NP完全难题，其提法 为：有n个城市，相互之间的旅行费用（或距离） 为已知，有一个旅行推销商，从某个基点城市 出发，要遍访其余n-1个城市至少一次，最后回 到出发点，试找出总费用最小（或总路程最短） 的旅行路线。 称能够到每个城市至少一次的回路为旅行商 回路，其中费用最少者为最优旅行商回路.在图论中，经过所有顶点恰好一次的圈（路） 称为哈密顿圈（路），简称H圈（H路），存在 H圈的图称为哈密顿图，简称H图。 旅行商问题是指在赋权图上经过每个顶点至 少一次，且总长度（路径上权的总和）达到最小 的闭通路。在加权的连通无向图中，权最小的H 圈简称最优H圈；经过每个顶点至少一次且权最 小的闭通路称为最优旅行商回路。注意：最优H 圈与最优旅行商回路两者是有区别的，最优H圈 只允许经过每个顶点恰好一次，而最优旅行商回 路允许经过某些顶点一次以上。定理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’中寻 求最优哈密顿圈的问题。寻找最优哈密顿圈和最优旅行商回路是图论 中的典型问题，而且是一个NP完全难题。问题 的求解没有多项式时间算法，除了穷举法，目前 还没有寻找最优解的算法，随着顶点数的增加， 运算所需时间呈指数级增长，当顶点数较大时， 求出最优解所需时间可能是难以忍受的。可行的 方法是用近似算法，力争在较短时间寻找接近最 优解的近似最优解。 旅行商问题得到了许多学者的关注和长期研 究，提出了多种近似算法，例如分支定界法、遗 传算法、模拟退火法、蚁群算法、神经网络方法、 粒子群优化算法、重绕最小生成树法、二次逐边 修正法等。二、用LINGO求解TSP问题的方法一1. 把最优哈密顿圈问题转化为0-1线性规划 将任意两点之间的最短路作为两点之间边的 权构造完全图G’。引入0-1整数变量xij(且i≠j)： 若xij=1则边i-j在回路中，而xij＝0则表示否。目标函数 min z ? ?? cij xiji ?1 j ?1nn首先必须满足约束条件：对每个城市访问一 次且仅一次。从城市i出发一次(到其它城市去), 表示为 n? xi j ? 1 ,j ?1i ? 1, 2 ,?, n , j ? i从某个城市到达j一次且仅一次，表示为：? xi j ? 1 ,i ?1nj ? 1, 2 ,?, n , i ? j以上建立的模型类似于指派问题的模型，对 TSP问题只是必要条件，并不充分。例如，用图示路线连接六个城市，满足以上 两个约束条件，但这样的路线出现了两个子回 路，两者之间不通，不构成整体巡回路线。31 2 465为此需要考虑增加充分的约束条件以避免产 生子巡回。下面介绍一种方法： 增加变量ui,i=2,3,…,n，（它的大小可以取 正整数：例如从起点出发所达到的城市u=2,依 此类推）。附加约束条件： 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，故不会发生矛盾。对于整体巡回路线，只要ui取适当值，都可以满 足该约束条件： ()对于总巡回上的边，xij=1, ui可取访问城市i 的 顺 序 数 ， 则 必 有 ui-uj ＝ -1 ， 约 束 条 件 uiuj+nxij≤n-1变成： -1+n ≤n-1，必然成立。 ()对于非总巡回上的边，因为xij=0 ，约束条 件ui-uj+nxij≤n-1变成-1≤n-1，肯定成立。 综上所述，该约束条件只限止子巡回，不影响 其它，于是TSP问题转化成了一个整数线性规划问 题。求最优哈密顿圈可以表示为规划：min z ? ? ? cij xiji ?1 j ?1nn?n ? ? xi j ? 1 , j ? 1 , 2 , ? , n , i ? j ? i ?1 n ? x ? 1 , i ? 1 , 2 ,? , n , j ? i ?? i j ? j ?1 ?ui ? u j ? nxi j ? n ? 1 , i ? 1,?, n , j ? 2 ,?, n , i ? j ? xij ? 0 , 1 , i , j ? 1, 2 ,?, n , ui ? 0 , i ? 1, 2 ,?, n ?2. LINGO程序 !旅行售货员问题; model: sets: city / 1..17/:! 定义17个城市; link( city, city): dist, ! 距离矩阵; !决策变量; 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 36 16.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.7 11.9 12.2 0 22 36.1 21 5.9 32.5 40.3 34.1 28.9 43.8 26.9 35 19.6 17.6 25.8 10.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.1 28 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.9 12.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.5 6 10.3 5.9 16.1 34 18.9 0 26.6 34.4 28.2 26.8 41.7 25 33.1 17.7 21.8 30 20.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.6 28.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.1 22.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.2 20.8 16.7 28.9 15.2 7.2 7.9 26.8 25.7 23.4 15.5 0 14.9 17.1 25.2 24.1 28.2 36.4 35.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.2 22.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 23 30.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.9 23.7 7.4 19.6 33.8 31.3 16.2 17.7 44.3 47.5 39.6 24.1 25.7 7.3 15.4 0 18.9 20.3 27.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.2 36 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)) = 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为0\1变量; end计算结果： 目标函数值：159.3 路线：1→7→3→16→17→14→13→15 →2→6→11→12→5→10→9→8→4→1 因为以上规划是线性规划，所以求解不费时， 当顶点数为20－30个时，一般几分钟就可以得 到最优解。 利用LINGO软件的强大优化能力，不必研究 旅行商问题的算法，通过编写不太复杂的 LINGO程序，能够较快地解决实际问题，达到 事半功倍的效果。三、用LINGO求解TSP问题的方法二1. 对城市排序，找出最优排序在现实中的城市交通图中，有些城市之间有 直接道路，有些则没有，如果两点之间没有直 接的通路，则两点之间的距离取最短路（经过 其它点），即用任意两点之间的最短路Cij 作为 图的距离矩阵，构成一个完全图G'，其任意一 对顶点都有一条边相连。图G的最优旅行商回 路等价于图G'的最优哈密顿圈，此时形式上的 环形巡回路线实际上个别点有可能不止经过一 次。设某个城市为旅行的出发地和终点（相当于 总部所在地），旅行者从该城市出发到其它n个 城市各一次且仅一次，最后回到出发地。我们 把行进路线分成n步，每一步到一个城市（第 n+1步返回出发地），于是一条旅行路线就相当 于n个城市的一种排列，n个城市共有n!种排列 方式。排序不同则总里程（或费用）可能不同， 总里程（或总费用）最小的排序就是我们要寻 找的最优路线。引入0-1型决策变量Xkj，下标k表示旅行的步 数，下标j表示到达哪一个城市，Xkj=1表示旅行 者第k个目的地（到达点）是城市j，Xkj=0则表 示否。用lj表示总部到各城市的距离，用Cij表示 城市i与城市j之间的最短路。 n 从出发地到第1个点的路程为 ? l j ? X 1 jj ?1从最后一个点返回出发地的里程为 ? l j ? X njj ?1n假设在第k步到达城市i，在第k+1步达到城市 j，即Xki=Xk+1,j=1，则走过的里程为： Cij? ki? k+1,j X X 从第1点到第n点走过的总里程为??? Cij ? X k i ? X k ?1, jk ?1 i ?1 j ?1n ?1 nn目标函数为min Z ? ? l j ( X 1 j ? X nj ) ? ??? Cij ? X k i ? X k ?1, jj ?1 k ?1 i ?1 j ?1nn ?1 nn约束条件有以下2条： (1) 每一步到达一个城市，即?Xj ?1nkj? 1 , k ? 1,2,?, n(2) 每一个城市必须到一次且只需一次，即?Xk ?1nkj? 1 , j ? 1,2,?, n综上所述，可以把最优哈密顿圈问题转化成 如下非线性0-1 规划min L ? ? l j ( X 1 j ? X nj ) ? ??? Ci j ? X k i ? X k ?1, jj ?1 k ?1 i ?1 j ?1 n n ?1 n n?n ?? X kj ? 1 , k ? 1, 2 ,?, n ? j ?1 ?n ? X ? 1 , j ? 1 , 2 , ?, n s.t. ?? kj ? k ?1 ? X kj ? 0 或 1 ? ?其 它 约 束 条 件 ?以上规划中允许包含其它约束条件。 用LINGO可以求解该规划，举例如下。 某县邮局和10个乡镇支局组成该县的邮政运 输网络，已知县局到各支局的距离和支局之间 的距离矩阵（数据在程序中）。用一辆邮车完 成邮件运输任务，邮车从县局出发到各支局去 一次且只需一次，最后回到县局，求总路程最 短的行驶路线。 解：本题是“旅行商”问题。可以用上面介 绍的方法求解。编写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,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(LIN KS(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”选项，可以选或不选“Global Solver”， 当选择多起点算法“Multistart Solver”时，需要设置 起点数，若选择“Solver Decides”表示由LINGO决定。对以上程序，我们选择“Global Solver”，点击菜单 “Options”，在全局优化求解器“Global Solver”选项 框内打“√”，再点击“确定”。 运行以上程序，费时4分多钟，得到最优解： 目标函数值（总路程）260公里 邮车的行驶路线为： 县局→8→9→10→7→6→5→4→1→2→3→县局四、 多旅行商（MTSP）问题1. 多旅行商问题的概念 在现实中问题中，有时候不是由一人走遍所 有点，而是由几个人分工合作，每个人只到其 中部分城市，每个点都有人来过一次且只需一 次，事先不指定谁到哪些点，求出使总路程最 小的旅行规划（每个人的行走路线）。 例如邮路规划中，为了在允许的时间内完成 邮件运输任务，县局的邮车往往不止1辆，而是 用若干辆邮车分工运输，只要保证每个支局有 邮车来过即可，为了节省行驶费用，需要规划 几辆邮车的最佳路线。这就是多旅行商问题。多旅行商问题的提法如下：有n+1个城市， 相互间的路程（或旅行费用）为已知，有k个旅 行商都从总部所在城市出发，赴其它城市旅行 推销，分工遍历其余n个城市，即每个城市各有 任意一名旅行商来过一次且仅一次，最后都回 到出发地，目标是总路程最短或总费用最省。 多旅行商问题在物流配送、邮路优化等方面 具有较高的实用价值，而在现实问题中，研究 对象往往不是单纯的旅行商问题，而要考虑各 种约束条件，例如时间约束、载重量约束等等。 研究这一类带约束条件的多旅行商问题具有很 强的现实意义。在现实的多旅行商问题中，往往带有约束条 件，例如时间约束、载重量约束等等。 带约束条件的多旅行商问题具有广泛现实意 义，且是极具挑战性的难题，我们仍然把它转 化为0-1非线性规划并编成LINGO程序来求解。 实例 某县邮政局管辖16个支局，已知县局到各支 局的距离以及16个支局之间的距离矩阵。寄达 各支局和各支局收寄的邮件(袋)如下表所示：县邮局和各支局分布图每一辆邮车最多装载65袋邮件，邮车的运行 成本为3元/公里。试用最少邮车，并规划邮车 的行驶路线使总费用最省。 分析： 首先考虑最少邮车数量，由题目所给表中数 据，寄达16个支局的邮件总数为176袋，从各支 局收寄的邮件总数为170袋，每一辆邮车最多容 纳65袋邮件，至少需要176/65≈2.7辆邮车，由于 邮车数量为整数，故最少需要3辆邮车。如果3 辆邮车能够完成邮件运输任务，则3辆车就是邮 车数量的最优解。运输费用与行驶里程成正比，总里程最短对 应总费用最省。把16个支局放在一起作为一个 整体考虑，找出3条邮路，每条邮路都从县局出 发，到若干支局进行卸装，最后回到县局。各 邮车路过的支局数量未知，合理安排各邮车的 行驶路线，由3辆邮车分别承包运输，在满足运 载量约束前提下，把3条巡回路线的总里程最小 作为优化的目标。该问题相当于附带约束条件 的多旅行商模型。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) 任何一辆车在任何一步到达一个支局 ，即? X kj ? 1 , k ? 1,2,?, m1j ?11616?Ykj ? 1 , k ? 1,2,?, m2j ?116? Z kj ? 1 , k ? 1,2,?, m3j ?1(2) 任何一个支局必须有一辆邮车到达一次且 只需要一次，即? X k j ? ?Yk j ? ? Z k j ? 1 ,k ?1 k ?1 k ?1m1m2m3j ? 1, 2 ,?,16(3) 在邮车行进的任何路段上，装载的邮件不 超过65袋。 设寄达各支局的邮件量为Pj ，各支局收寄的 邮件量为Qj。 装载量是动态变化的，以第1辆邮 车为例，出发时的装载量为Wx 0 ? ? ( Pj ? ? X k j )j ?1 k ?116m1到第1个支局卸装以后，装载量变为Wx1 ? Wx 0 ? ? ( Pj ? Q j ) ? X 1 jj ?116在行驶过程中，装载量的递推公式为Wx k ? Wx ,k ?1 ? ? ( Pj ? Q j ) ? X kj , k ? 2 , 3 ,?, m1约束条件为j ?116Wx i ? 65 , i ? 0 ,1, 2 ,?, m1综上所述，建立多旅行商问题的0-1规划模型 如下：min S ? L1 ? L2 ? L3 ? Lx ? Ly ? Lz16 16 ? 16 ?? X k j ? 1 , ? Yk j ? 1 , ? Z k j ? 1 , k ? 1, 2 ,?, mi j ?1 j ?1 j ?1 ? m3 m2 ? m1 ?? X k j ? ? Yk j ? ? Z k j ? 1 , j ? 1, 2 ,?,16 k ?1 ? k ?1 16 k ?1 ? L ? l ? ( X ? X ) , L ? 16 l ? (Y ? Y ) , L ? 16 l ? ( Z ? Z ) ? ? j 1 j m2 j 3 ? j 1 j m3 j m1 j 2 s.t. ? 1 ? j 1 j j ?1 j ?1 j ?1 ? m3 ?1 16 16 m1 ?1 16 16 m2 ?1 16 16 ? ? Lx ? ??? Cij ? X k i ? X k ?1, j , Ly ? ??? Cij ? Yk i ? Yk ?1, j , Lz ? ??? Cij ? Z k i ? Z k ?1, j k ?1 i ?1 j ?1 k ?1 i ?1 j ?1 k ?1 i ?1 j ?1 ? ?Wx k ? 65 , Wy k ? 65 , Wz k ? 65 , k ? 0 ,1, 2 ,?, mi ? ? X k j , Yk j , Z k j ? 0 或 1 ?装载量的计算公式为：m3 m1 m2 16 16 16 ? ?Wx 0 ? ? ( Pj ? ? X k j ) , Wy 0 ? ? ( Pj ? ? Yk j ) , Wz 0 ? ? ( Pj ? ? Z k j ) j ?1 k ?1 j ?1 k ?1 j ?1 k ?1 ? 16 16 ? ?Wx 1 ? Wx 0 ? ? ( Pj ? Q j ) ? X 1 j , Wy 1 ? Wy 0 ? ? ( Pj ? Q j ) ? Y1 j j ?1 j ?1 ? 16 ? ?Wz 1 ? Wz 0 ? ? ( Pj ? Q j ) ? Z1 j j ?1 ? ? 16 ?W ? W xk x ,k ?1 ? ? ( Pj ? Q j ) ? X k j , k ? 2 , 3 , ? , m1 ? j ?1 ? 16 ?W ? W y ,k ?1 ? ? ( Pj ? Q j ) ? Yk j , k ? 2 , 3 , ? , m2 ? yk j ?1 ? 16 ? ?Wz k ? Wz ,k ?1 ? ? ( Pj ? Q j ) ? Z n j , k ? 2 , 3 ,?, m3 j ?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 11 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 32 32 15 24 30 51 27 27 13 0 9 21 37 26 26 43 45 45 28 29 38 58 32 34 20 9 0 13 32 32 35 47 52 52 35 33 42 71 45 47 33 21 13 0 19 30 39 50 65 65 48 44 40 67 64 49 35 37 32 19 0 11 20 31 54 61 34 25 21 57 53 39 25 26 32 30 11 0 10 20 43 51 24 14 13 47 47 29 15 26 35 39 20 10 0 18 36 41 14 9 1852 61 42 33 48 57 38 32 21 52 38 32 41 48 29 15 52 56 38 24 61 63 44 30 ENDDATA43 45 45 28 29 3847 52 52 35 33 4250 65 65 48 44 4031 54 61 34 25 2120 43 51 24 14 1318 0 23 46 25 14 23 36 23 0 27 22 33 42 41 46 27 0 39 48 57 14 25 22 39 0 11 20 9 14 33 48 11 0 9 18 23 42 57 20 9 0;@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);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);@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三辆邮车各自负责的支局数量有若干种分配方 法，例如有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是因为避免超载的原因，被迫绕路， 整体上仍然保持最优。第二条邮路：县局→14→15→16→11→12→ 县局，总里程105km，沿途各段邮件的装载量 为61,55,52,54,49,54袋。 第三条邮路：县局→13→1→2→3→4→县局， 总 里 程 117km ， 沿 途 各 段 邮 件 的 装 载 量 为 51,53,52,51,50,51袋。三条邮路的图形如图所示§5 中国邮递员问题一、欧拉（Euler）图定义：设图G={V,E}是连通无向图，则经过 G的每边正好一次的道路称为欧拉道路（欧拉 迹）；经过G的每边至少一次的闭通路称为巡回； 经过G的每边正好一次的巡回称为欧拉巡回；存 在欧拉巡回的图称为欧拉图； 定理：一个非空连通图是欧拉图的充分必要 条件是它没有奇点。 推论：连通图G能够一笔画出（存在欧拉迹） 的充要条件是所有顶点是偶点或者仅有两个顶 点是奇点。二、中国邮递员问题1. 概念 邮递员从邮局出发，经过他所投递范围内的 每一条街道至少一次，然后返回邮局，如何安 排投递路线使总路程最短，这个问题由中国学 者管梅谷于1962年首先提出并给出了一种解法， 被国际上称为中国邮递员问题。 用图来描述投递区域，用边表示街道，用点 表示路口和邮局，则投递区构成一个非负的赋 权连通图。中国邮递员问题就是在一个非负的 赋权连通图中寻找一条总权最小的巡回，这种 巡回称为最优巡回。2．欧拉图中的最优巡回若图G是欧拉图，则G的任何一个欧拉巡回都是 最优巡回，因为欧拉巡回是一条通过G的每一条 边恰好一次的巡回。此时可用Fleury算法来确定 一个欧拉巡回。定义：设G是连通图，边，若从G中删除边e后， 图不连通，则称边e为图G的割边。 定理：e是G的割边的充要条件是e不含在G的圈 中。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}的割边。 ③ 当第②步不能进行时就停止。3．非欧拉图中的最优巡回 如果G不是欧拉图（图中有奇点），则G的任何 一个巡回经过某些（与奇点相关联的）边必定多 于一次。解决这一类问题的一般方法是，引入重 复边，使原图成为欧拉图，并且添加的重复边的 权的总和为最小。 情形1 G只有两个奇点u和v，求最优巡回的算 法如下： (1) 用Dijkstra算法或Floyd算法求出奇点u和v之 间的最短路径P。 (2) 令G * =G∪P，则G *为欧拉图。 (3) 用Fleury算法来确定一个G *的欧拉巡回，这 就是G的最优巡回。情形2 G有2n个奇点（n&1），可以用Edmonds 算法解决，其基本思路为：首先将奇点配对，使 配对以后各对之间距离的总和（两点之间的距离 按照最短路计算）达到最小（称为最佳配对）,求 最佳配对的方法可以用匈牙利法或0-1规划法等方 法（可以用Lingo实现）。然后把每一对点之间的 最短路作为边添加到原图中,使之成为欧拉图G *， 找出G *的欧拉巡回就是原图的最佳巡回。算法步骤如下： (1) 用Floyd算法求出所有奇点之间的最短路径 和距离矩阵。 (2) 用匈牙利法或0-1规划法求出所有奇点之间 的最佳配对。 (3) 在原图上添加最佳配对所包含的两两顶点之 间的最短路得到欧拉图G *。 (4) 用Fleury算法确定一个G *的欧拉巡回，这就 是G的最优巡回。三、Fleury算法的Matlab程序设图是连通无向图，如果所有顶点都是偶点， 则该图是欧拉图，必然存在欧拉巡回，如果恰好 有两个奇次顶点，则称该图为半欧拉图，必然存 在起点在奇点（两个奇点中的一个）且终点在另 一个奇点的欧拉道路。这两种情况下都可用 fleury算法确定一条欧拉巡回或者欧拉道路。按照fleury算法的思路编写Matlab程序。主要程 序arEuler根据图的边集确定是否为欧拉图、半欧 拉图或非欧拉图，如果是欧拉图则用fleury算法找 到一条欧拉巡回路线（欧拉图的欧拉巡回不止一 条，输出的是其中的一条），如果是半欧拉图则 返回一条欧拉道路，其起点在两个奇点之一，终 点是另一个奇点。function [eu,cEu]=arEuler(E) %输入参数E是图的边集（m行2列矩阵，每一 行的两个数字代表一条边的两个顶点，共有m条 边），输出参数eu有三种结果：若为欧拉图则 eu=1；半欧拉图则eu=0.5；否则eu=0。输出参数 cEu是m行1列矩阵，表示欧拉巡回或欧拉道路中 边的序列。 eu = 0; % eu的初始值为0 cEu=[]; % cEu开始时为空集 ncV=arComp(E); % 调用函数arComp确定图的 分枝构成，判断是否连通if max(ncV)&1, % 表示有2个或以上互不连通的 部分 return % 不是连通图就返回endn=max(max(E(:,1:2))); % n是图的顶点总数m=size(E,1); % m是边的总数for i=1:nb(i)=0;for j=1:mif E(j,1)==i|E(j,2)==ib(i)=b(i)+1;endendend% b表示各顶点的度数rp=rem(b,2); % 各顶点的度数除2取余数，偶点 的余数为0，奇点的余数为1 srp=sum(rp); % srp是rp的总和 switch srp case 0, % 若余数的总和为0，则所有顶点为偶 点，原图是欧拉图 eu=1; case 2, % 恰好有两个奇点，原图是半欧拉图 eu=0.5; otherwise, % 否则是非欧拉图 returnend % 以下程序寻找一条欧拉巡回或欧拉道路 if srp==0, % 对于欧拉图 v1=1; % 把第一个顶点作为欧拉巡回的起点 else % 对于半欧拉图 v1=find(rp); %先找出奇点 v1=v1(1); % 把第一个奇点作为欧拉道路的起 点endvc=v1; % vc是当前顶点 m=size(E,1); % m是边的总数 E1=[E(:,1:2), [1:m]']; % E1代表候选边集，开 始时它的前两列与E相同，第三列表示边的顺序号 % 以下是Fleury算法 while ~isempty(E1), %若E1非空则循环 evc=find((E1(:,1)==vc)|(E1(:,2)==vc)); % 找 出与当前顶点vc关联的边 levc=length(evc); % 统计与当前顶点vc关联的 边的总数if levc==1, % 只有一条路 cEu=[cEu;E1(evc,3)]; % 把新的边加入欧拉 巡回或欧拉道路中 vcold= vc=sum(E1(evc,1:2))- % vc为新的当前点 E1=E1(setdiff([1:size(E1,1)],evc),:); % 删除 孤立顶点 E2=E1(:,1:2); E2gv=E2& E2(E2gv)=E2(E2gv)-1;E1(:,1:2)=E2; if vc&vcold, vc=vc-1; end if v1&vcold, v1=v1-1; end else % 从顶点vc出发有若干条路可供选择for k=1:levc, E2=E1(setdiff([1:size(E1,1)],evc(k)),:); ncv=arComp(E2); % 确定E2的互不相连的 分枝数目 nco=max(ncv); if (max(ncv)==1), % 此时E2为连通图，即 选中的边不是割边（桥） cEu=[cEu;E1(evc(k),3)]; % 把该边加入欧 拉巡回或欧拉道路中vc=sum(E1(evc(k),1:2))- % vc为新的当前点 E1=E2; end end end end return在fleury算法过程中，每次预选一条边，需要判 断它是否为当前子图的割边，为此先假定把该边 从当前边集中删去，然后判断余下的子图是否连 通，若不连通，则选中的边是当前子图的割边， 若仍然连通，则不是割边，可以把该边加入巡回 中。 在程序arEuler中，通过调用函数arComp来确 定图的互不连通的分枝数，根据它的返回结果判 定图的连通性。function ncV=arComp(E,n) %功能是确定图的互不连通的分枝数目。输入 参数E是图的边集，它使m行2列矩阵，每一行的 两个数字代表一条边的两个顶点，共有m条边，n 是图的顶点数，该参数不是必须的，可以省略， 此时默认n=max(max(E))，但是，假如最末尾的 顶点是孤立的点，则该参数不能省略。 %输出参数ncV是n行1列向量，每个数字代表 相应顶点的互不连通的分枝数目，由ncV可以判断 图的连通性，若max(ncV)&1，则图有2个以上互 不连通的分枝。[m,n1,E1] = arValidation(E); % 验证数据的有 效性 E2=[E1(:,1:2);E1(:,[2 1])]; % E2的行数是E1的 两倍，新增加的行由原来各边的两个顶点交换次 序得到 [Dec,Ord]=arDecOrd(E2); % 对有向图E2进行 分解 ncV=sum(Dec*diag([1:size(Dec,2)]),2); % 互不 相连的分枝数 if (nargin&1)&(n&n1), % 最后的孤立顶点 ncV=[ncV;[1:n-n1]'+max(ncV)]; end return在 程 序 arComp 中 ， 通 过 调 用 函 数 arValidation(E)来确任数组E的有效性。 function [m,n,newE] = arValidation(E); %输入参数E与前面相同，输出参数m是图的边 数，n1是图的顶点数，数组newE的第一和第二列 等同于输入数据E，第三列是各边的权重。 se=size(E); % se是数组E的大小（行数和列数） m=se(1);if se(2)&3, % 没有设置权重 E(:,3)=1; % 各边的权重相等且都等于1 end newE=E(:,1:3); %数组newE的第三列是各边的 权重 n=max(max(newE(:,1:2))); % n是顶点数 return 在程序arComp中，通过调用函数arDecOrd(E) 把图中相互连通的顶点进行分组（如果整个图连 通，则所有顶点都归入一组）。function [Dec,Ord]=arDecOrd(E) %输入参数E是图的边集，它是m行2列矩阵， 每一行的两个数字代表一条边的两个顶点，共有 m条边。 %输出参数Dec是n行ns列逻辑（布尔）数组 （所有元素非0即1），n是顶点数，ns是相互连通 的顶点的分组数，Dec的每一列所包含的真值（数 字1）的数量等于对应组内相互连通的顶点数。各 列包含的数字1的数目由小到大排列。 %输出参数Ord是ns行ns列逻辑（布尔）方阵 （所有元素非0即1），ns是相互连通的顶点的分 组数，若Ord(i,j)=True，则表示从图的i部分（对 应Dec的i列）到图的j部分（对应Dec的j列）有通 路。[m,n,E] = arValidation(E); % 验证数据的有 效性 A=zeros(n); A((E(:,2)-1)*n+E(:,1))=1; Ak=eye(n); As=(Ak&0); for k=1:n, Ak=(Ak*A&0); As=As|Ak; endA=As; [T,ir,jc]=unique(A.*A','rows'); Dec=T'; Ord=A(ir,ir); ns=size(Ord,1); for it=1:ns*(ns-1)/2 Mlow=tril(Ord,-1); [is,js,Mw]=find(Mlow); if isempty(is) endnum=[1:ns]; num(is(1))=js(1); num(js(1))=is(1); Ord=Ord(num,num); Dec=Dec(:,num); end return例1 求下图中的一条欧拉巡回。123456798解：该图有9个顶点、14条边，各顶点的度数 均为偶数，是一个欧拉图。在Matlab中输入 E=[1,2;2,3;1,4;2,4;2,5;3,6;4,5;4,7;5,8;5,6;6,9;6 ,8;7,8;8,9]; %E代表图的边集，它有14行2列，每一行是 连接一条边的两个顶点，各边的编号从1到14依 次排列。 运行[eu,cEu]=arEuler(E); 结果为eu=1（说明该图是欧拉图）。cEu = 1 2 6 10 5 4 7 9 12 11 14 13 8 3 它代表一条欧拉巡回依次经过的边的序列， 它 所 经 过 的 顶 点 序 列 依 次 为 1→2→3→6→5→2→4→5→8→6→9→8→7→4 →1。 注：一般说来，一个欧拉图中的欧拉巡回不 止一条（各条巡回的总路程相等），本程序的 结果给出其中的一条三、中国邮递员问题的求解实例前面已经讲过，对于欧拉图，可以直接用 Fleury算法找出一条欧拉巡回路线；对于半欧 拉图，可以先求出奇点u和v之间的最短路径P， 令G*=G∪P，则G *为欧拉图，然后用Fleury算 法来确定一个G *的欧拉巡回，它就是原图G的 最优巡回。当G有2n个奇点（n&1），可以用Edmonds算 法解决，步骤如下： (1) 用Floyd算法求出所有奇点之间的最短路 径和距离矩阵。 (2) 用匈牙利法或0-1规划法求出所有奇点之 间的最佳配对。 (3) 在原图上添加最佳配对所包含的两两顶点 之间的最短路得到欧拉图G *。 (4) 用Fleury算法确定一个G *的欧拉巡回，这 就是G的最优巡回。 以上步骤的关键是找出2n个奇点的最佳配对， 举例如下。例2 下图是某区街道示意图，各边的长度数 据见下表。现在需要对每条街道都巡视到（至 少走一次），求一条总路程最短的巡回路线。123546789101112131415161718 19 2021 222423 28 292526 30 352731 3233 3436373839404142边长数据解：该图有42个顶点和62条边，有26个顶点 为奇点，因而它不是欧拉图，为了寻找最优巡 回，需要先求26个奇点的最佳配对。 先用Floyd算法求出所有42个顶点之间的最短 路距离和路径。程序如下： E=[1 2
402 …………… 注：每一行代表一条边（两个顶 点和边长），此处省略59行 40 39 198];for i=1:42 for j=1:42 if j==i a(i,j)=0; else a(i,j)= end end endfor k=1:62 i=E(k,1);j=E(k,2);a(i,j)=E(k,3);a(j,i)=E(k,3); end [D,R]=floyd(a);然后求26个奇点的最优配对，这可以用Lingo 求解，编写程序如下： MODEL: SETS: dot/2,4,5,6,8,9,10,11,12,13,14,15,17,18,19,20,22 ,24,25,26,28,29,30,36,40,41/; LINKS(dot,dot)| &2 # GT # &1:C,X; ENDSETSDATA: C=1 650 939 00
77 52 18 51 4 668 51 198 181 402 13 453 601 945 84 597 8 04 414 919 32 435 148 886 9 347 691 30 823 94 50 505 794 9 562 472 750 6 382 967 02 73 41 289 578 813 1 245 940 7 462 07 768 05 9 524 0 534 651 76 504 828 886 8 25 2 3 362 65 793 706 597
14 80 3 00
1 86 1 2 505 849 20 416 7 08 07 531 199 543 14 675 6 02 360 1 527 577 47 883 34 01 7 217 757 866
47 144 5 24 344 15 476 7 03 722 0 91 59 540 649
57 2 598 184 79 7 293 88 62 271 866 901 1 39 95
792; ENDDATAMIN=@SUM(LINKS:C*X); @FOR(LINKS:@BIN(X)); @FOR(dot(I):@SUM(LINKS(J,K)| J #EQ# I #OR# K #EQ# I:X(J,K))=1); END 运行以上程序，得到最优配对结果为：2与6、 4与12、5与13、8与9、10与11、14与15、17与 25、18与26、19与20、22与28、24与29、30与 36、40与41。在原图62条边的基础上增加13条边，得到如 图所示的图形，它有42个顶点和75条边，是欧 拉图。 1 3 24567891011121314 21151623 24172518192022263027 31 35362829 3432 374133 38394042对该图运行运行[eu,cEu]=arEuler(E)，其中输入参数E是75 行2列矩阵（代表75条边），得到一条欧拉巡回如图所示，总里 程为25983123546789101112131415161718241926 3020 2731212223 28 29253233 343536 37 3839404142该巡回路线所经过的顶点序列为： 1→2→3→11→10→9→8→7→2→ （ 经 过 7 ） → 6→5→4→12→13→5→13→19→20→6→7→1 4→15→8→9→23→24→25→17→11→10→16→ 17→25→42→41→37→32→21→14→15→22→2 3→28→29→24→29→34→33→28→( 经 过 23)→22→21→20→19→18→26→27→31→30→ 39→40→41→40→35→36→31→32→33→38→3 7→36→（经过31）→30→26→18→12→4→1。§6 最大流问题一、问题的描述设有一批物资，要从A市通过公路网络（内 含一些中转站）运往B市，已知每段公路的运输 能力有限制（流量限制），问应如何安排运输 方案，才能使总运量最大？这就是网络最大流 问题． 假设有一个有向网络，对应每一条弧(vi,vj)有 一 个 非 负 的 权 Cij ， 表 示 该 弧 的 容 量 （ 流 量限 制）．图中有两个特殊顶点：一个称为发点,又 称源，记为s，它只有出弧而没有入弧，即只有 流出而没有流进；另一个称为收点,又称汇，记 为t，它只有入弧而没有出弧，即只有流进而没 有流出．定义实值函数f，该函数对应各弧的取值为f(i,j)， 表示流过弧i→ j的流量，假设f满足以下三个条件： (1) 对每条弧，流量不超过弧的容量，即0? 称为流量限制； f (i , j ) ? Cij (2) 发点 s 流出的总量等于收点 t 流进的总量； (3) 对于除了发点和收点之外的其他任意中间点， 流入该点的总量等于流出该点的总量，称为流量 守恒规则． 称函数f为流函数，简称流（可行流）。令f v ? ? f ( s ,i )i?V如果fv达到了最大，则称它是运输网络的最 大流． 实例：下图是从发货地①到目的地⑥的有 向运输网络，称点①为发点（源），点⑥为收 点（汇），有向边（弧）旁边的数字是该弧的 流量（运输能力）限制，求①－⑥的最大流．一个运输网络图1021641010120616 6635二、数学模型对每一条弧(顶点i到j)，定义f(i,j)为该弧上从 顶点i到顶点j的流量，用Cij表示其上的流量限 制．则对任意一个中转点，流进与流出相等， 但顶点①只有流出，顶点⑥只有流进，并且两 者大小相等(方向相反)，如果我们在图上虚拟 一条从⑥－①的弧，其流量不受限制，并假设 从①流到⑥的总量又从该虚拟弧上返回①，整 个网络系统构成一个封闭的不停流动的回路， 则对任意顶点都满足流进等于流出．目标函数是max f(n,1)，n是收点，1是发点. 约束条件有两条： (1)对每个顶点，流进等于流出，即? f (k, i) ? ? f (i, j) i ? 1,2, ? , n k j等式左边的求和是对所有以顶点i为终点的边 进行，右边的求和是对所有以顶点i为起点的边 进行． (2)对每条弧，流量不超过其限制值，即f (i, j ) ? Cij完整的模型为：maxf (n,1)? ? f (k , i ) ? ? f (i, j ) , i ? 1,2,?, n , ?k ?V j ?V s.t ? ? f (i, j ) ? Cij , 顶点 (vi , v j ) ?V . ?编写LINGO程序如下： MODEL: SETS: CHSH/1..6/; LINKS(CHSH,CHSH)/1,2 1,3 2,4 2,5 3,4 3,5 4,6 5,6 6,1/:C,F; !该集合列出有弧相连的顶点对，与每一条弧一 一对应，6,1是虚拟弧; ENDSETS DATA: C=16,20,10,10,6,6,10,16,1000; !虚拟弧上的流量不受限制(很大的数); ENDDATAMAX=F(6,1); !目标函数; @FOR(LINKS(I,J):F(I,J)&=C(I,J));!流量限制; @FOR(CHSH(I):@SUM(LINKS(J,I):F(J,I))= @SUM(LINKS(I,J):F(I,J))); !每个顶点的流进等于流出; END 求解得到结果，最大流为26，运输方案:弧 1-2 1-3 2-4 2-5 3-4 3-5 4-6 5-6 虚拟弧6-1 6 10 16 26 流量 14 12 4 10 6三、最小费用最大流前面介绍了网络最大流问题及其求解 方法，它不涉及费用问题，有时在实际 问题中，网络中各条弧(边)上的运输费 用(单价)不相同，因而在满足最大流的 情况下(运输方案不唯一)，要求费用最 小的最大流，称为最小费用最大流问 题．下面看一个具体实例例：图示网络的每一条弧上括号内有两个 数字，前一个数字代表该弧上的最大流量， 后一个数字是单位运费．用uij表示弧(i,j)上的 最大流量，用cij表示运输单价。(9,2) (8,2)2(5,5)4( 2,1)(5,6)1(7,8)(6,4)63( 9,3)5(10,7 )先用求最大流的方法求出该网络从顶点1到 顶点6的最大流为14，运输方案如下表所示：弧 流量 1-2 1-3 2-3 2-4 3-5 4-3 4-6 5-4 5-6 6-1 7 7 2 5 9 0 5 0 9 14最小费用是在满足最大流情况下找出费用最 小的运输方案，故下一步是把求出的最大流作 为约束条件，即把f(6,1)=14作为约束条件，目 标函数改成min z ?( i , j )?E?cij f ij , i ? 6 .编写LINGO程序如下： MODEL: SETS: CHSH/1..6/; LINKS(CHSH,CHSH)/1,2 1,3 2,3 2,4 3,5 4,3 4,6 5,4 5,6 6,1/:C,U,F; !6,1 是虚拟弧，U为流量限制，C为费用，F为 实际流量; ENDSETS DATA: U=8,7,5,9,9,2,5,6,10,15; C=2,8,5,2,3,1,6,4,7,8 ;ENDDATA N=@SIZE(CHSH); F(6,1)=14; !把上一步求出的最大流作为约束条件;MIN=@SUM(LINKS(I,J)|I#LT#N:C(I,J)*F(I,J)); @FOR(LINKS(I,J):F(I,J)&=U(I,J));@FOR(CHSH(I):@SUM(LINKS(J,I):F(J,I))=@SU M(LINKS(I,J):F(I,J))); END运行该程序，得到最小费用为205，最小费用 下的最大流运输方案如下表所示弧 流量 1-2 8 1-3 6 2-3 1 2-4 7 3-5 9 4-3 2 4-6 5 5-4 0 5-6 9 虚拟弧6-1 14注：满足最大流时的运输方案可以有多种， 表中所列方案是费用最小的方案。
常见问题: 1、图论的历史图论以图为研究对象的数学分支。 图论中的图指的是...因此在设计和制造印刷电路板时, 首先要解决的问题是判定一个给定的电路图是 否...图论中的常用经典算法_IT/计算机_专业资料。Jsoi2006...路径毫无关系的问题也可以归结为最短路径问题来求解...至于它经过了哪几个点大家可在上述过程中加以记录...图论最短路径问题 在消防选址中的应用 【摘 要】 最短路径问题是图论解决的典型实际问题之一,可用来解决管路铺设、线路 安装、厂区布局和设备更新等实际问题。介绍...图论在实际生活中的应用_数学_自然科学_专业资料。...本文就通过 找重庆邮电大学几个代表性地点之间寻找最...在1736年欧拉神奇般的解决了这个问题,他用抽像分析...用图论解决四人过桥问题_其它_计划/解决方案_实用文档。经典的四人过桥问题。...作为一个测试人员,首先得对问题中的许多未知因素提出疑问,下面 一些问题也许是...图论解决渡河问题农夫,狼,羊,草渡河问题,是一道很经典的问题。讲述的是农夫,...用图论解决几个特殊的禁... 暂无评价 3页 ¥3.00
图论中独立支配集的求解...数据结构课后习题详解(超完整,超经典)_工学_高等教育...试按图论中图的画法惯例画出其逻辑结构图。 解: ...试问在此条件下,这两个算法可解问题的规模(即 n...图论及其应用课程论文―― 解决城市道路最短路问题_...2 (2){dist(i)|Vi∈(V-S)}中最小值对应的...7总结 Dijkstra算法是求最短路的一个经典算法,其...马踏棋盘问题, 实际上是图论中的哈密顿通路问题, 典型的是 NP 问题,求解的...{ }P 定义把个方向试探的增量位置数组 7 8 7 1 ...图论建模;接着从现实例子出发,给出各 种典型图论...整个求解过程如下: 原问题――&图论建模――&运用...例 1.宴会定理:任何一宴会中,一定存在两个人有...
All rights reserved Powered by
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。