数学建模课件-中国邮路问题

数学建模课件-中国邮路问题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，在命令窗口中输入对应的矩阵a（实际上可以在excel中输入

0D0中非零数，但置为0，所得数据再拷入matlab命令窗口中）：

>> a

a =

0 2 8 1 0 0 0 0 0 2 0 6 0 1 0 0 0 0 8 6 0 7 5 1 2 0 0 1 0 7 0 0 0 9 0 0 0 1 5 0 0 3 0 2 9 0 0 1 0 3 0 4 0 6 0 0 2 9 0 4 0 0 3 0 0 0 0 2 0 0 0 7 0 0

0 0

0 0

0 0

0 0

0 0

1 0

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 4 5 0 7 8 0 10 11

c中非零数及对应奇点

>> [D,path]=floyd1(a)

D =

0 2 2 0 7 5 1 3 3 1 6 4 9 7 5 3 11 9 7 1 5 3 0 7 7 0 4 4 1 7 2 9 6 6 4 11 3 6 1 4 4 1 4 7 0 3 3 0 6 3 2 5 8 5 9 5 7 3 2 6 9 6 6 2 3 5 0 8 8 0 2 7 10 9 8 4 3 10 8 7 5 4 2 1 7 8 0 1 13

6

13

7

4

9

2

11 11

11 10

10 8 3 10 7 4 1 8 1 0 3

13 11 6 13 10 7 4 9 2 3 0

path =

1 2 1 2 6 6 1 1 2 2 5 5 3 3 5 5 10 10 7 7 2 4 5 1 3 4 3 4 6 2 3 5 3 4 5 5 10 7 7 2 2 5 5 6 6 1 1 5 6 5 6 3 3 5 5 10 10 7 7 2 2 5 5 7 6 7 1 6 8 3 5 7 3 5 8 10 8 7 9 2 2 5 5 7 7 7 7 6 6 3 3 10 9 9 9 10 9 10 2

5

7

7

6

3

10

11

9

10 11

10

9 9 9 9 9 9 9 8 9 9 11

其中D为最短距离矩阵

然后，在D中找到奇点对应的距离矩阵e，可以如下取得

>> r=c(c>0)

r =

1 2 >> e=D(r,r)

e =

0 2 2 0 1 3 3 1 9 7 4 5 1 3 3 1 0 4 4 0 9 6 7 8 9 5 7 3 9 6 6 2 0 8 11

13

8 11

13

7 10

1 4

10 10 10

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:

v/1..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: Variable X( 1, 3) X( 2, 4) X( 5, 7) X( 6, 8) Value 0

Reduced Cost

1.000000

1.000000

1.000000

9.000000

1.000000 1.000000 1.000000 1.000000