POLITECHNIKA RZESZOWSKA

im. I. Łukasiewicza

Wydział Budowy Maszyn i Lotnictwa

Zakład Pojazdów Samochodowych

EKONOMIKA i ZARZĄDZANIE

w TRANSPORCIE SAMOCHODOWYM

PROJEKT NR 2.

Wykonał:

Arkadiusz Żywiec

V MDE

Konsultant:

dr inż. P. Pawlus

Problem Komiwojażera

Komiwojażer musi objechać „n” miast i wrócić do miasta wyjściowego przy czym całkowity koszt podróży ma być najmniejszy. Koszt podróży z „i+j” wynosi c_ij. Zadanie polega na wyznaczeniu optymalnej trasy podróży, minimalizującej całkowity koszt przejazdu.

Dane:

i\^j	1	2	3	4	5
1	∞	2	5	6	3
2	4	∞	5	7	8
3	2	6	∞	9	2
4	4	5	7	∞	6
5	5	6	9	1	∞

Krok 1. Szacowanie dolnej granicy kosztów przejazdu.

Bazując na twierdzeniu mówiącym, że jeżeli od pewnej kolumny lub wiersza odejmiemy wartość stałą to rozwiązanie optymalne nie ulegnie zmianie. Dokonuje się modyfikacji macierzy kosztów tak aby każda kolumna i każdy wiersz zawierały co najmniej jedno zero, a pozostałe wartości c_ij były nie ujemne. Całkowita odjęta wartość jest równa dolnej granicy kosztów. Od każdego wiersza odejmujemy jego najmniejszy element „p_i” , a następnie od każdej następnej tak powstałej kolumny odejmujemy jej najmniejszy element „q_j”.

i\^j	1	2	3	4	5	pi
1	∞	2	5	6	3	2
2	4	∞	5	7	8	4
3	2	6	∞	9	2	2
4	4	5	7	∞	6	4
5	5	6	9	1	∞	1
qj	0	0	1	0	0

Koszty:

Krok 2. Gałęzienie (podział).

Poszukuje się nowych wartości p_i^* oraz q_j^* które należy odjąć tak aby każda kolumna i każdy wiersz zawierały co najmniej jedno zero, w przypadku wprowadzenia za c_ij = 0 wartości c_ij = ∞ . Spośród liczb p_i^* i q_j^* wybieramy te których suma jest największa w miejscach równych zero. Łuk i^*-j^* wybieramy jako pierwszy w optymalnej sekwencji. Rozbija się korzeń na dwa poddrzewa, zawierający dany łuk i nie zawierający go.

i\^j	1	2	3	4	5	pi^*
1	∞	0	2	4	1	1
2	0	∞	0	3	4	0
3	0	3	∞	7	0	0
4	0	1	2	∞	2	1
5	4	5	7	0	∞	4
qj^*	4	1	2	3	0

i^*+j^*	pi^*+qj^*
1-2	1+1 = 2
2-1	4
2-3	2
3-1	0+4 = 4
3-5	0
4-1	5
5-4	7

Krok 3. Oszacowanie dolnych ograniczeń dla obydwu poddrzew.

W przypadku poddrzewa zawierającego uprzednio wybrany łuk usuwa się określony wiersz i kolumnę oraz modyfikuje się macierz w celu wykluczenia takich rozwiązań, które odpowiadałyby dwukrotnemu przybyciu komiwojażera do tego samego miasta lub pomijaniu pewnych miast. Podaną macierz modyfikuje się jak w kroku pierwszym.

Dla poddrzewa nie zawierającego wybranego łuku modyfikuje się macierz odejmując od wiersza i^* i kolumny j^* wartości p_i^*+q_j^*. Dolna granica kosztów dla tego poddrzewa jest większa od poprzednio wyliczanej o p_i^*+q_j^*. Tak powstałą macierz modyfikuje się gdy zachodzi potrzeba jak w kroku 2.

Poddrzewo zawierające łuk 5-4 c₄₅ = ∞

i\^j	1	2	3	5	pi^*
1	∞	0	2	1	0
2	0	∞	0	4	0
3	0	3	∞	0	0
4	0	1	2	∞	0
qj^*	0	0	0	0

Koszty:

Po odjęciu, macierz zawierająca łuk 5-4 ostatecznie wygląda tak:

i\^j	1	2	3	5
1	∞	0	2	1
2	0	∞	0	4
3	0	3	∞	0
4	0	1	2	∞

Bez łuku 5-4

i\^j	1	2	3	4	5	pi^*
1	∞	0	2	4	1	0
2	0	∞	0	3	4	0
3	0	3	∞	7	0	0
4	0	1	2	∞	∞	0
5	4	5	7	0	∞	0
qj^*	0	0	0	0	0

Koszty:

i\^j	1	2	3	5	pi^*
1	∞	0	2	1	1
2	0	∞	0	4	0
3	0	3	∞	0	0
4	0	1	2	∞	1
qj^*	0	1	0	0

i^*+j^*	pi^*+qj^*
1-2	2
2-1	0
2-3	0
3-1	0
3-5	0
4-1	1

Poddrzewo zawierające łuk 1-2 c₂₁ = ∞

i\^j	1	3	5	pi
2	∞	4	0	0
3	0	∞	0	0
4	3	0	∞	0
qj	0	0	0

Koszty:

Po odjęciu, macierz zawierająca łuk 1-2 ostatecznie wygląda tak:

i\^j	1	3	5
2	∞	0	4
3	0	∞	0
4	0	2	∞

Bez łuku 1-2

i\^j	1	2	3	5	pi^*
1	∞	0	2	1	1
2	∞	∞	0	4	0
3	0	3	∞	0	0
4	0	1	2	∞	0
qj^*	0	1	0	0

Koszty:

i\^j	1	3	5	pi^*
2	∞	0	4	4
3	0	∞	0	0
4	0	2	∞	2
qj^*	0	2	0

i^*+j^*	pi^*+qj^*
2-3	6
3-1	0
3-5	0
4-1	2

Poddrzewo zawierające łuk 2-3 c₃₁ = ∞

i\^j	1	5	pi
3	∞	0	0
4	0	∞	0
qj	0	0

Koszty:

Po modyfikacji:

i\^j	1	5
3	∞	0
4	0	∞

Bez łuku 2-3

i\^j	1	3	5	pi^*
2	∞	0	4	0
3	∞	∞	0	0
4	0	2	∞	0
qj^*	0	0	0

Koszty:

i\^j	1	5	pi^*
3	∞	0	∞
4	0	∞	∞
qj^*	∞	∞

Wybieram drogę 3-1

Poddrzewo zawierające łuk 3-1

i\^j	5
4	0

Koszty:

Bez łuku 3-1

i\^j	1	5	pi^*
3	∞	0	∞
4	0	∞	∞
qj^*	∞	∞

Koszty:

Brak rozwiązania

Pozostały łuk 4-5

i\^j	1
4	0

Koszty:

Bez łuku 4-5

i\^j	1	5	pi^*
3	∞	0	∞
4	0	∞	∞
qj^*	∞	∞

Koszty:

Brak rozwiązania

Drzewo kosztów wygląda zatem następująco:

7

B= 14

B= 14

B= 14

B= 14

B= 14

B= 14

B= 16

B= 14

Brak rozwiąz.

Brak rozwiąz.

B= 14

5-4

4-5

≠4-5

≠3-1

3-1

≠2-3

2-3

≠1-2

1-2

≠5-4

WR

---