Matlab travel salesman plot: D = [0 36 55 40 55 40 85 100 90 78; 36
Question:
Matlab travel salesman plot:
D = [0 36 55 40 55 40 85 100 90 78;
36 0 27 24 37 42 55 73 72 67;
55 27 0 20 17 40 30 45 47 48;
40 24 20 0 15 21 46 59 52 44;
55 37 17 15 0 27 35 45 35 30;
40 42 40 21 27 0 62 70 55 40;
85 55 30 46 35 62 0 19 34 47;
100 73 45 59 45 70 19 0 26 45;
90 72 47 52 35 55 34 26 0 21;
78 67 48 44 30 40 47 45 21 0];
c = reshape(D, [100,1]);
intcon = linspace(1, 100);
beq = [ones(20, 1); zeros(10, 1)];
Aeq= zeros(30, 100);
for j=1:10
for i=1:10
Aeq(j, i+(j-1)*10)=1;
Aeq(j+10, (i-1)*10+j)=1;
end
Aeq(j+20, j+(j-1)*10)=1;
end
lb = zeros(1, 100);
ub = ones(1, 100);
x = intlinprog(c, intcon, [], [], Aeq, beq, lb, ub);
X = reshape(x, [10, 10])
b = zeros(5, 1);
A = zeros(5, 100);
A(1, 1+(2-1)*10)=1;
A(1, 2+(1-1)*10)=1;
A(2, 3+(5-1)*10)=1;
A(2, 5+(3-1)*10)=1;
A(3, 4+(6-1)*10)=1;
A(3, 6+(4-1)*10)=1;
A(4, 7+(8-1)*10)=1;
A(4, 8+(7-1)*10)=1;
A(5, 9+(10-1)*10)=1;
A(5, 10+(9-1)*10)=1;
x = intlinprog(c, intcon, A, b, Aeq, beq, lb, ub);
X = reshape(x, [10, 10]);
1. How many subtours are in the optimal solutions?
2. Plot the subtours
3. What is the length of the tour in the one tour optimal solution?