Rok akademicki	Tytuł ćwiczenia:	Data wykonania:
2006/2007	Zadanie 3. Problem komiwojażera	26.03.2007
Kierunek studiów
ZiIP	Nazwisko i imię:	Ocena:
dzienne	Żymła Agnieszka
Rok III

n - miast

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

Wariant A!

Zapis modelu matematycznego w AMPL-u:

1. zmienna decyzyjna:

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

2. funkcja celu:

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

3. 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;

4. 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;

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 675 675

3 250 410 0 275 495

4 650 630 250 0 20

5 1000 450 490 20 0;

Wariant B!

Zapis modelu matematycznego w AMPL-u:

1. zmienna decyzyjna:

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

2. funkcja celu:

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

3. ograniczenia:

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

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 tasama{i in N}: x[i,i]=0;

4. 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 670 670

3 250 410 0 270 490

4 650 670 270 0 15

5 1000 670 490 15 0;

Interpretacja otrzymanych wyników:

1. W wariancie A komiwojażer pokona następującą drogę:

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, co obrazuje poniższy graf. Długość pokonanej drogi wynosi: 1100.

W wariancie B komiwojażer pokona następującą drogę:

Po jej uporządkowaniu otrzymujemy:

Powtarzanie się par wierzchołków jest spowodowane brakiem ograniczenia porządkującego kolejność. Długość pokonanej drogi wynosi: 1305.

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

• Wartość 1 dla „input” i „output” oznacza, że komiwojażer przejedzie przez to miasto, tzn. wjedzie do niego „input” i wyjedzie z niego „output”.

• Wartość 2 dla „cicle” w podcyklach 8, 9, 10, 11, 14, 17, 20, 21, 22, 23 wskazuje podcykle, które nie wchodzą w skład wybranej drogi. Pojawia się, gdy nie ma określonego kierunku wejścia do danego podcyklu (istnieją dwie możliwości).

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

• Wartość 2 dla „input” i „output” oznacza, że komiwojażer przejedzie przez to miasto, tzn. wjedzie do niego „input” i wyjedzie z niego „output” (zawsze są możliwe 2 wejścia i wyjścia do lub z miasta).

• Ograniczenie „droga” zapewnia symetryczność i działa na zasadzie odejmowania stron, dlatego mamy same zera.

• Ograniczenie „tasama” zapewnia nam, że komiwojażer nie zapętli się w jednym mieście.

3) Ograniczenie na podcykle działa w ten sposób, że komiwojażer będąc w mieście 1 wybiera kolejne miasto do którego ma się udać, a tym samym pozostałe podcykle stają się niemożliwe do zrealizowania, to samo gdy trafi do kolejnego miasta itd.

W przypadku wariantu A z miasta 1 komiwojażer podążył do miasta 3, a tym samym pozostałe kombinacje z 1 stają się niemożliwe do zrealizowania. W następnej kolejności poszedł do miasta 4 i znów podcykle nie zawierające tej kombinacji stają się niemożliwe. Możemy to w prosty sposób zauważyć na wykonanym grafie. Wybór konkretnej drogi przez komiwojażera wyklucza powrót tą samą drogą.

4) W wariancie B w funkcji celu warunek i>j zapewnia, że brane są pod uwagę wartości z dolnej części macierzy odległości. W momencie, gdy zmienimy warunek na i<j pod uwagę będą brane wartości ponad przekątną macierzy. Brak tego warunku spowodowałby dwukrotne policzenie drogi.

5) W momencie zmiany kierunku optymalizacji na maksymalizację funkcji celu otrzymalibyśmy najdłuższą drogę jaką może pokonać komiwojażer odwiedzając miasta.

6) Problem ten odpowiada problemowi przydziału.

W związku z tym, że nie ma ograniczenia na podcykle najlepszym rozwiązaniem okazują się 2 osobne drogi: z 1 do 5 i z powrotem oraz z 2 do 4, z 4 do 3, z 3 do 2. Ten typ rozwiązania nie może być zaakceptowany dla problemu komiwojażera.

Rok akademicki	Tytuł ćwiczenia:	Data wykonania:
2006/2007	Zadanie 4. Zadanie wyboru parku maszynowego	16.04.2007
Kierunek studiów
ZiIP	Nazwisko i imię:	Ocena:
dzienne	Żymła Agnieszka
Rok III

Zapis modelu matematycznego w AMPL-u:

1. zmienne decyzyjne:

var x{i in M, j in N}>=0 integer ;

var y{i in M} >=0 integer;

2. funkcja celu:

minimize koszt: sum{i in M}c[i]*y[i];

3. ograniczenia:

subject to ilosc{i in M}: sum{j in N}x[i,j]=y[i];

subject to zdolnosc{j in N}: sum{i in M}a[i,j]*x[i,j]>=b[j];

4. parametr b_j - liczba produkowanych wyrobów j-tego radzaju:

param b:= 1 18 2 10 3 10 4 10 5 45 6 15 7 10 8 15 9 25;

5. parametr c_i - koszt urządzenia typu i:

param c:= 1 450 2 175 3 195 4 155 5 100;

6. parametr a_ij - zdolność produkcyjna i-tego urządzenia ze względu na j-ty wybór:

param a : 1 2 3 4 5 6 7 8 9 :=

1 350 0 15 10 50 11 40 15 0

2 10 100 0 0 15 150 0 40 40

3 15 25 150 25 20 20 300 10 25

4 0 10 0 150 35 0 50 100 20

5 25 0 15 0 150 15 30 0 150;

Interpretacja otrzymanych wyników:

Koszt minimalny wynosi 1065 (Objective: KOSZT = 1065 (MINimum)).

Został wybrany następujący zestaw urządzeń zapewniający wykonanie planowanych zadań produkcyjnych: 4 i 5, w ilościach odpowiednio: 3 i 6 sztuk. Na urządzeniu typu 4 produkowane są wyroby: 2, 4, 8, natomiast na urządzeniu typu 5 produkowane są pozostałe wyroby, czyli: 1, 3, 5, 6, 7, 9.

Pierwsze ograniczenie dotyczące ilości jest spełnione (subject to ilosc{i in M}: sum{j in N}x[i,j]=y[i];), ponieważ w kolumnie „Activity” występują cyfry 0.

Drugie ograniczenie (subject to zdolnosc{j in N}: sum{i in M}a[i,j]*x[i,j]>=b[j];) mówi o zdolności produkcyjnej urządzeń wytwarzających dany wyrób i zapotrzebowaniu na niego. Dla wyrobu 2 i 6 zdolność produkcyjna urządzeń jest dokładnie równa zapotrzebowaniu na dany wyrób. W pozostałych przypadkach zdolność produkcyjna urządzeń jest większa od zapotrzebowania. Obrazuje to poniższy rysunek.

---