数学建模课件-中国邮路问题
原来你什么都不想要-从你的全世界路过影评
数学建模课件-中国邮路问题0-1规划法
首先建立matlab函数文件：
function [D,path]=floyd1(a)
a(find(a==0))=inf;
n=size(a,1);
%¼ÆËã³öaµÄ¹æÄ£µÄ´óС.
D=a;path=zeros(n,n);%ÉèÖÃDºÍpathµÄ³õÖµ.
for i=1:n
for j=1:n
if D(i,j)~=inf
path(i,j)=j;
end
end
end
%×ön´Îµü´ú£¬Ã¿´Îµü´ú¾ù¸üÐÂ
D(i,j)ºÍpath(i,j)
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);
path(i,j)=path(i,k);
end
end
end
end
for i=1:n
D(i,i)=0;
path(i,i)=0;
end
根据文献中距离矩阵
D
0
，在命令窗口中输入对应的矩阵a（实际上可以在excel
中输入
D
0
中非零数，但
置为0，所得数据再拷入
matlab命令窗口中）：
>> a
a =
0 2 8 1 0 0 0 0 0
0 0
2 0 6 0 1 0
0 0 0 0 0
8 6 0
7 5 1 2 0 0 0 0
1 0 7 0 0 0 9 0 0
0 0
0 1 5 0 0 3
0 2 9 0 0
0 0 1
0 3 0 4 0 6 0 0
0 0 2 9 0 4 0 0 3
1 0
0 0 0 0 2 0
0 0 7 0 9
0 0
0 0 9 6 3 7 0 1 2
0 0 0 0 0 0 1
0 1 0 4
0 0 0 0
0 0 0 9 2 4 0
根据a求出奇点：
b=a>0;
n=length(b);
for
i=1:n
if mod(sum(b(i,:)),2)==1
c(i)=i;
end
end
c
c =
1
2 0
c中非零数及对应奇点
>> [D,path]=floyd1(a)
D =
0 2 7
2 0 5
7 5 0
1 3 7
3 1 4
6 4 1
9 7 2
5 3 6
11 9 4
10 8 3
13 11 6
path =
1 2 2
1 2 5
6 6 3
1 1 3
2 2 6
5 5 3
3 3 3
5 5 5
4 5
1 3
3
1
7 4
0 4
4 0
7 3
9 6
6 2
8
7
10
4 2
1
5
4 6
4 1
2 5
5 5
4 3
5 5
0
7
6 9
4 7
1 2
7 9
3 6
0 3
3
0
5 8
5 2
4 1
7 4
2 2
5 5
6
7
1 7
6 6
6 3
3 7
5 5
8 0
5
11
3 9
6 4
6 11
2
8
5 5
8 2
0 7
7
0
8 1
9 2
2 2
5
5
6 7
1 7
8 6
5
3
3 10
8 9
10 11
10
13
8 11
3 6
10 13
7
10
4 7
1 4
8 9
1
2
0 3
3 0
2 2
5
5
7 7
7 7
6 6
3
3
10 10
9 11
11
10
13
10 10
10 10 10 10 10 8 9 10 11
7 7 7 7 7 7 7
9 9 10 9
9 9 9 9
9 9 9 8 9 9 11
其中D为最短距离矩阵
然后，在D中找到奇点对应的距离矩阵e，可以如下取得
>> r=c(c>0)
r =
1 2
4 5 7 8 10 11
>> e=D(r,r)
e =
0 2 1 3
9 5 10 13
2 0 3 1
7 3 8 11
1 3 0 4
9 6 10 13
3 1 4 0
6 2 7 10
9 7 9 6
0 8 1 4
5 3 6 2
8 0 8 9
10 8 10 7
1 8 0 3
13 11 13 10
4 9 3 0
最后将数据e写入如下lingo程序：
sets:
v1..8;
vv(v,v):e,x;
endsets
data:
e=
0 2 1 3 9 5 10 13
0 0 3 1
7 3 8 11
0 0 0 4 9 6 10 13
0 0 0 0 6 2 7
10
0 0 0 0 0 8 1 4
0 0 0 0 0 0 8 9
0
0 0 0 0 0 0 3
0 0 0 0 0 0 0 0;
enddata
min=@sum(vv:e*x);
@for(vv(i,j)|i#ge#j:x(i,j)=0);
@for(v(i):@
sum(v(k):x(k,i))+@sum(v(j):x(i,j))=1);
@for(vv:@bin(x));
部分结果显示：
Global
optimal solution found.
Objective
value: 12.00000
Objective bound:
12.00000
Infeasibilities:
0.000000
Extended solver steps:
0
Total solver iterations:
0
Variable
Value Reduced Cost
X( 1, 3) 1.000000 1.000000
X( 2, 4) 1.000000 1.000000
X( 5, 7) 1.000000 1.000000
X( 6, 8) 1.000000 9.000000