求出下图中以v1为起点的一条中国邮路。
后面是我和朋友一起做的一点东西：
1 问题分析
中国邮路问题，可以简要叙述为：一个邮递员送信，要走完他负责投递的全部街道，投完后回到邮局。由此把这样一个多重边的连通图中，从某个顶点出发，经过不同的线路，又回到原出发点的路线问题，转化为欧拉图一笔画问题。观察图2.1，为偶点，而奇点则有，共6个点。在图2.1基础上，增加一些重复边，使新图不含奇点，并且重复边的总权为最小。由此建立一个最短路线的一笔画模型。
2 建立模型及求解
由图2.1写出邻接矩阵，运用算法，在中编写程序（附录2.1）得到7个顶点的两两最短距离。
图2.2
根据欧拉定理3.1：连通的多重图G是欧拉图，当且仅当G中无奇点。考虑这6个奇点，在已知两两最短距离情况下，建立关联的3条重复边，并使总权最小为最佳方案的优化模型。由此，将欧拉图问题转化为优化模型，再对当前问题进行分析。欲将6个奇点调整成偶点，可以简化为基本的匹配问题。由于对称性，将图2.2矩阵只列出严格上三角部分，且可以省略的关系。
图2.3
用表示点（）添加一条重复边 ，而表示（）不关联。 显然,目标函数正好是)对之和。约束条件是每个奇点只能(而且必须在)某一条重复边，即对于任意有：只要属性的某个下标为就加起来，此和应该等于1。
运用软件，编写程序（附录2.2）计算结果如下：
Variable Value Reduced Cost
B( V2, V7) 1.000000 2.000000
B( V3, V4) 1.000000 3.000000
B( V5, V6) 1.000000 3.000000
图2.4
由上图2.4结果得到：使原图2.1中6个奇点全部调整成为偶点，原图调整成欧拉图并要求路线最短所添加的三条重复边为。
图2.5
整理上述模型，增加3条重复边，使得图中所有点均为偶点，符合欧拉定理3.1以完成一笔画模型，且以总权值最小而取得最佳方案。
图2.6
如上图2.6，该邮递员走过的路线：,。因为欧拉图一笔画模型的路线总是不止一条，以上只是众多情况之一，但总权值始终不变，为41。
附录2.1
% 计算两点之间的最短路
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,k)+D(k,j); %在循环中进行矩阵迭代 R(i,j)=R(i,k); % R是路径矩阵 end end end end D,R for i=1:7 for j=i:7 s(i,j)=D(i,j); end end for i=1:7 for j=1:7 if s(i,j)==0 s(i,j)=NaN; end end end 附录2.2 ！用lingo算出V2-V7每两个点组队的最短距离； model: sets: num_i/v2,v3,v4,v5,v6,v7/; link(num_i,num_i)|&2#gt#&1:a,b; endsets data: a= 44742 3662 362 35 4; enddata min=@sum(link(i,j):a(i,j)*b(i,j)); @for(num_i(i):@sum(link(j,k)|j#eq#i #or# k#eq#i:b(j,k))=1); @for(link(i,j):@bin(b(i,j))); end
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024