Monika Rapacz

Gr lab 8.

Metody Optymalizacji Dyskretnej

Problem Komiwojażera
Sprawozdanie nr 3

n - miast

cij - odległość miedzy i-tym a j-tym miastem

1. Zapis modelu matematycznego w AMPL:

Wariant A

var x{i in N, j in N} binary; `zmienna decyzyjna:

minimize droga: sum{i in N, j in N}c[i,j]*x[i,j]; ` funkcja celu:

`ograniczenia:

subject to OUTPUT{i in N: i>1}: sum {j in N:j<>i}x[i,j]=1;

subject to INPUT {j in N: j>1}: sum{i in N:i<>j}x[i,j]=1;

subject to CICLE{s in SQ}: sum{i in Q[s], j in N diff Q[s]}x[i,j]>=1;

`podcykle miast

set Q[1]:= 1;

set Q[2]:= 2;

set Q[3]:= 3;

set Q[4]:= 4;

set Q[5]:=5;

set Q[6]:= 1,2;

set Q[7]:= 1,3;

set Q[8]:= 1,4;

set Q[9]:= 1,5;

set Q[10]:= 2,3;

set Q[11]:= 2,4;

set Q[12]:= 2,5;

set Q[13]:= 3,4;

set Q[14]:= 3,5;

set Q[15]:= 4,5;

set Q[16]:= 1,2,3;

set Q[17]:= 1,2,4;

set Q[18]:= 1,2,5;

set Q[19]:= 1,3,4;

set Q[20]:= 1,3,5;

set Q[21]:= 1,4,5;

set Q[22]:= 2,3,4;

set Q[23]:= 2,3,5;

set Q[24]:= 2,4,5;

set Q[25]:= 3,4,5;

set Q[26]:= 1,2,3,4;

set Q[27]:= 1,2,3,5;

set Q[28]:= 1,2,4,5;

set Q[29]:= 1,3,4,5;

parametr c_ij - odległość między miastem i a miastem j:

param c:1 2 3 4 5:=

1 0 105 255 655 1005

2 100 0 415 450 540

3 250 410 0 275 486

4 650 420 300 0 25

5 1000 360 481 25 0;

Wariant B

var x{i in N, j in N} binary; `zmienna decyzyjna

minimize droga: sum{i in N, j in N: i>j}c[i,j]*x[i,j]; `funkcja celu

subject to OUTPUT{i in N}: sum{j in N}x[i,j]=2; `ograniczenia

subject to INPUT{j in N}: sum{i in N}x[i,j]=2;

subject to droga{i in N, j in N}: x[i,j]=x[j,i];

subject to ogr4{i in N}: x[i,i]=0;

parametr c_ij - odległość między miastem i a miastem j:

param c:1 2 3 4 5:=

1 0 100 250 650 1000

2 100 0 410 420 360

3 250 410 0 300 481

4 650 420 300 0 25

5 1000 360 481 25 0;

2. Interpretacja otrzymanych wyników:

Wariant A

Wyznaczenie drogi, jaką pokonuje komiwojażer:

x[1,3] * 1

x[2,1] * 1

x[3,4] * 1

x[4,5] * 1

x[5,2] * 1

graficznie:

Po jej uporządkowaniu otrzymujemy:

z miasta 1 do miasta 3,

z miasta 3 do miasta 4,

z miasta 4 do miasta 5,

z miasta 5 do miasta 2

i z miasta 2 do miasta 1.

Długość tej trasy to 1015.

W wariancie A w kolumnie Activity poszczególne ograniczenia oznaczają:

• Wartość 1 dla INPUT i OUTPUT oznacza, że komiwojażer przejeżdża przez dane miasto (tylko raz) , ponieważ wjeżdża do miasta (input) i wyjeżdża z niego (output) .

• Wartość 2 dla CICLE w danych podcyklach, występują gdy nie ma określonego kierunku wejścia do danego podcyklu , istnieją dwie możliwości.

Podcykle, które nie wchodzą w skład wyznaczonej drogi:

CICLE3[8] 2

CICLE3[9] 2

CICLE3[10] 2

CICLE3[11] 2

CICLE3[14] 2

CICLE3[17] 2

CICLE3[20] 2

CICLE3[21] 2

CICLE3[22] 2

CICLE3[23] 2

• Na przykładzie liczbowym działania ograniczenia na podcykle można stwierdzić, że w przypadku wariantu A, komiwojażer zaczynając od miasta 1 zmierza do miasta 3 , a tym samym kombinacje z 1 stają się niemożliwe do realizowania, w tym momencie każdy inny podcykl staje się niemożliwy do wybrania, taka sama sytuacja zachodzi w każdym kolejnym mieście do którego się udaje. Graficzną interpretacje tego stwierdzenia można zauważyć na grafie - wybór konkretnej drogi przez komiwojażera wyklucza powrót tą samą drogą.

Wariant B

Wyznaczenie drogi, jaką pokonuje komiwojażer:

x[2,1] * 1 0 1

x[3,1] * 1 0 1

x[4,3] * 1 0 1

x[5,2] * 1 0 1

x[5,4] * 1 0 1

x[1,2] * 1 0 1

x[1,3] * 1 0 1

x[3,4] * 1 0 1

x[2,5] * 1 0 1

x[4,5] * 1 0 1

Długość drogi jaką przebywa komiwojażer to 1035

Powtarzanie się par wierzchołków jest spowodowane brakiem ograniczenia porządkującego kolejność.

W wariancie B poszczególne ograniczenia oznaczają (interpretacja kolumny Activity):

• Wartość 2 dla INPUT i OUTPUT analogicznie do wariantu A oznaczają, że komiwojażer przejeżdża przez dane miasto , ponieważ wjeżdża do niego i wyjeżdża,w tym wariancie możliwe dwa wejścia do miasta i dwa wyjścia.

• W ograniczeniu „droga” mamy same zera ponieważ macierz odległości jest symetryczna.(Np. odległość z miasta 1 do miasta 2 jest taka sama, jak odległość kiedy się jedzie z powrotem z miasta 2 do miasta 1).

Np. :

droga[1,2] 0

droga[2,1] 0

droga[3,4] 0

droga[4,3] 0

• Ograniczenie 4 gwarantuję, to żeby komiwojażer nie zapętlił się w jednym mieście.

• W wariancie B w funkcji celu („droga”) warunek i > j zapewnia branie pod uwagę wartości spod przekątnej macierzy odległości, gdybyśmy zmienili ten warunek na i < j byłyby brane pod uwagę wartości z górnej części, natomiast gdyby tego warunku nie było, to droga byłaby liczona dwukrotnie.

Minimize droga: sum{i in N, j in N:i>j}c[i,j]*x[i,j];

• Gdybyśmy zmienili „Minimize” w funkcji celu na „Maximize” , czyli zmienili kierunek optymalizacji, znajdowana by była droga najdłuższa, nie najkrótszajaką komiwojażer musi przebyć.

• Problem w tym przypadku, dla wariantu A odpowiadał będzie problemowi przydziału.

Zapis modelu:

param n:=5;

set N := 1..n;

param t;

param c{i in N, j in N};

var x{i in N,j in N}binary;

minimize droga: sum{i in N, j in N}(c[i,j]*x[i,j]);

subject to INPUT {j in N}:sum{i in N:i<>j}x[i,j]=1;

subject to OUTPUT {i in N}:sum{j in N:i<>j}x[i,j]=1;

Wyznaczenie drogi:

x[1,3] * 1

x[2,1] * 1

x[3,2] * 1

x[4,5] * 1

x[5,4] * 1

Rozwiązanie tego typu nie jest akceptowane dla problemu komiwojażera, ponieważ zostały wybrane dwie drogi : a miasta 4 do miasta 5 i z powrotem, oraz z miasta 1 do miasta 3, następnie do miasta 2 i z miasta 2 do miasta 1. Związane jest to z brakiem ograniczenia na podcykle.

3

---