Optymalizacja bazy transportowej

1. Wyznaczanie najkrótszej drogi w sieci

Pierwszym zadaniem, które musi być rozwiązane w bazie transportowej, jest przygotowanie bazy podstawowych parametrów. Należy do nich wyznaczenie najkrótszych dróg przejazdów z uwzględnieniem specyfiki sieci połączeń. Przyjmując, że droga z miejscowości i do miejscowości j może być inna niż z miejscowości j do miejscowości i, potencjalne trasy przejazdu będziemy przedstawiać za pomocą strzałek. Gdy kierunek przejazdu nie będzie odgrywał roli, strzałki będą zastąpione krawędziami.

W pierwszej kolejności rozpatrzymy przypadek, gdy kierunek przejazdu jest istotny. Strukturę grafu 1.1 i określone przy strzałkach odległości zapiszemy teraz w macierzy, w której wiersze i kolumny odpowiadają węzłom grafu. Przyjmiemy, że w wierszach będą reprezentowane węzły jako początki a w kolumnach jako końce strzałek. W ujęciu tabelarycznym nasza macierz jest przedstawiona w tabeli 1.1.

Rys. Graf skierowany z wartościami oznaczającymi odległości.

	1	2	3	4	5	6	7
1	*	30	*	35	*	*	*
2	*	*	13	*	42	*	*
3	*	14	*	15	38	27	46
4	*	*	12	*	*	34	*
5	*	*	*	*	*	*	18
6	*	*	*	*	*	*	20
7	*	*	*	*	*	*	*

Tab. Macierz odległości.

Nasze zadanie będzie polegać na podaniu algorytmu wyznaczającego najkrótsze drogi między określoną miejscowością a wszystkimi pozostałymi. Będziemy oczywiście zakładać, że obowiązuje nas kierunek przemieszczania zgodny ze wskazaniami strzałek.

Najpierw jednak musimy poznać pewne podstawowe pojęcia i oznaczenia, których znajomość przyda nam się dla lepszego zrozumienia prowadzonych w dalszej części obliczeń.

• Drogę w grafie skierowanym określa ciąg węzłów będącymi początkami i końcami następujących po sobie strzałek, przy czym wszystkie strzałki muszą mieć zgodny kierunek. Drogę między węzłami i₀ i i_s będziemy zaznaczać jako F=[i₀,i₁,...,i_s]. W naturalny sposób możemy określić długość tej drogi jako:

c(F)=
_i

• F = [1,...,j] - ciąg węzłów (wskazujących jednoznacznie ciąg strzałek) najkrótszej drogi od węzła 1 do węzła j;

• d_j - odległość od węzła 1 do węzła j;

• S(j) -zbiór następników węzła j (rysunek 1.2);

• P(j) - zbiór poprzedników węzła j (rysunek 1.2);

• 
  (j) - bezpośredni poprzednik węzła j na najkrótszej drodze z a do j.

Rys. Zbiór poprzedników P(j)={1,2,3} i następników S(j)={4,5}.

Rozpatrzymy ogólny przypadek, gdy między obiektami i oraz j mogą występować dwie strzałki: od i do j oraz od j do i, przy czym każda z nich może mieć przypisaną inną liczbę, a więc dopuszcza się, że c_ij =c_ji . Pozwala to rozpatrywać zadania, w których rolę miary odległości może odgrywać czas przejazdu, który wcale nie musi być taki sam dla przejazdu w jedną i drugą stronę.

Rys. Dwie drogi między węzłami i oraz j.

Nasze zadanie ujmiemy następująco: w sieci znany jest pewien wyróżniony węzeł, który dalej będziemy oznaczać symbolem a (np. a=1). Należy wyznaczyć najkrótsze drogi z tego węzła do wszystkich innych węzłów oraz obliczyć odległości od węzła do każdego z węzłów.

Zastosujemy tu algorytm Dijkstry I.

Algorytm Dijkstry I

Założenia startowe:

Znamy węzeł a.

Przyjmujemy: Q:={a} i d_a:=0, a dla pozostałych węzłów i
a przyjmujemy: d_i:=
.

ITERACJE

Krok I

W zbiorze Q wyznaczamy węzeł h, dla którego zachodzi: d_h= min d_i

Krok II

Ze zbioru Q usuwamy węzeł h, w wyniku czego Q:=Q\{h}.

Krok III

Wyznaczamy wszystkie węzły, które są następnikami h, a więc S(h).

Krok IV

Kolejno dla każdego węzła j
S(h) porównujemy wcześniej przyporządkowana odległość d_j z suma odległości d_h powiększonej o długość przemieszczenia c_hj. Sprawdzamy więc, czy spełniona jest nierówność:

d_h+c_hj<d_j

Jeżeli nierówność jest prawdziwa, to:

• Starą odległość zastępujemy nową: d_j:= d_h+c_hj.

• Dla j identyfikujemy poprzednika:
  (j):=h.

• Węzeł j wprowadzamy do zbioru Q:Q:=Q
  {j}.

W przeciwnym przypadku pozostawiamy d_j bez zmiany.

Krok V

Jeżeli Q
0, to przechodzimy do następnej iteracji, a więc powracamy do kroku I.

Jeżeli Q = 0, postępowanie kończy się.

W samym postępowaniu koncentrujemy się na obliczeniach odległości d_j. W celu odczytania ciągu węzłów leżących na najkrótszych drogach wystarczy odczytywać ich numery w trakcie określania odległości. Pomocą będą zapamiętane wskazania bezpośrednich poprzedników
(i).

Przykład

Rozpatrzmy przykład sieci przedstawiony na rysunku 1.1. przyjmijmy, że węzeł 1 odzwierciedla producenta. Należy wyznaczyć najkrótsze drogi od producenta do wszystkich pozostałych oraz odpowiadające im odległości.

Start

Przyjmujemy: a:=1, Q:={1}, d₁:=0, d₂:=
,..., d₇:=
.

ITERACJA I

Ponieważ Q={1}, wybór h jest zdeterminowany i mamy h=1.

Wykreślamy węzeł 1 ze zbioru Q i otrzymujemy Q=0.

Dla h=1 mamy S(1)={2,4}.

Rozpatrujemy kolejno:

j=2, d₂:=
, d₁+c₁₂=30
d₂:=30 i Q:={2}

j=4, d₄:=
, d₁+c₁₄=35
d₄:=35 i Q:={2,4}

Wyniki przejściowe zawiera tabela 1.2.

i	1	2	3	4	5	6	7
dj	0	30		35
(i)	*	1	-	1	-	-	-

Tab. Zapis wyników iteracji 1.

ITERACJA 2

W zbiorze Q={2,4} wyznaczamy węzeł h, dla którego d_h= min d_i. Korzystając z wyników pierwszej iteracji otrzymujemy h=2. Wykreślamy węzeł 2 ze zbioru Q i otrzymujemy Q={4}. Dla h=2 mamy S(2)={3,5}.

Rozpatrujemy kolejno:

j=3, d₃=
, d₂+c₂₃=30+13=43
d₃:=43 i Q:={3,4}

j=5, d₅=
, d₂+c₂₅=30+30=60
d₅:=60 i Q:={3,4,5}.

Wyniki przejściowe zawiera tabela 1.3.

i	1	2	3	4	5	6	7
dj	0	30	43	35	60
(i)	*	1	2	1	2	-	-

Tab. Zapis wyników iteracji 2.

ITERACJA 3

W zbiorze Q={3,4,5} wyznaczamy węzeł h, dla którego d_h= min d_i.

Korzystając z wyników drugiej iteracji otrzymujemy h=4.

Wykreślamy węzeł 4 ze zbioru Q i otrzymujemy Q={3,5}.

Dla h=4 mamy S(4)={3,6}.

Rozpatrujemy kolejno:

j=3, d₃:=43, d₄+c₄₃=35+12=47
d₃:=43

j=6, d₆:=
, d₄+c₄₆=35+34=69
d₆:=69 i Q:={3,5,6}.

Wyniki przejściowe zawiera tabela 1.4.

i	1	2	3	4	5	6	7
dj	0	30	43	35	60	69
(i)	*	1	2	1	2	4	-

Tab. Zapis wyników iteracji 3.

ITERACJA 4

W zbiorze Q={3,5,6} wyznaczamy węzeł h, dla którego d_h= min d_i.

Korzystając z wyników trzeciej iteracji otrzymujemy h=3.

Wykreślamy węzeł 3 ze zbioru Q i otrzymujemy Q={5,6}.

Dla h=3 mamy S(3)={2,4,5,6,7}.

Rozpatrujemy kolejno:

j=2, d₂:=30, d₃+c₃₂=43+14=57
d₂:=30

j=4, d₄:=35, d₃+c₃₄=43+15=58
d₄:=35

j=5, d₅:=60, d₃+c₃₅=43+38=81
d₅:=60

j=6, d₆:=69, d₃+c₃₆=43+27=70
d₆:=69

j=7, d₇:=
, d₃+c₃₇=43+46=89
d₇:=89 i Q:={5,6,7}.

Wyniki przejściowe przedstawia tabela 1.5.

i	1	2	3	4	5	6	7
dj	0	30	43	35	60	69	89
(i)	*	1	2	1	2	4	3

Tab. Zapis wyników iteracji 4.

ITERACJA 5

W zbiorze Q={5,6,7} wyznaczamy węzeł h, dla którego d_h= min d_i.

Korzystając z wyników czwartej iteracji otrzymujemy h=5.

Wykreślamy węzeł 5 ze zbioru Q i otrzymujemy Q={6,7}.

Dla h=5 mamy S(5)=7.

Dla węzła 7 otrzymujemy:

j=7, d₇:=89, d₅+c₅₇=60+18=78
d₇:=78.

Wyniki przejściowe przedstawia tabela 1.6.

i	1	2	3	4	5	6	7
dj	0	30	43	35	60	69	78
(i)	*	1	2	1	2	4	5

Tab. Zapis wyników iteracji 5.

ITERACJA 6

W zbiorze Q={6,7} wyznaczamy węzeł h, dla którego d_h= min d_i.

Korzystając z wyników czwartej iteracji otrzymujemy h=6.

Wykreślamy węzeł 6 ze zbioru Q i otrzymujemy Q={7}.

Dla h=6 mamy S(6)={7}.

Dla węzła 7 otrzymujemy:

j=7, d₇:=78, d₆+c₆₇=69+20=89
d₇:=78.

Wyniki przejściowe przedstawia tabela 1.7.

i	1	2	3	4	5	6	7
dj	0	30	43	35	60	69	78
(i)	*	1	2	1	2	4	5

Tab. Zapis wyników iteracji 6.

ITERACJA 7

Ponieważ Q={7} otrzymujemy natychmiast h=7 i po wykreśleniu tego węzła, Q=0.

Dla h=7 mamy S(7)=0.

Postępowanie kończy się, a wyniki odczytujemy z ostatniej tabeli.

Odczytajmy drogę od węzła 1 do węzła 7. Jej długość wynosi 78. Bezpośrednim poprzednikiem węzła 7 jest węzeł 5, dla węzła 5 bezpośrednim poprzednikiem jest węzeł 2, dla węzła 2 bezpośrednim poprzednikiem jest węzeł 1.Wobec tego drogę wyznacza ciąg węzłów [1,2,5,7].

Analogicznie odczytujemy wyniki dla pozostałych węzłów:

• Drogę z węzła 1 do węzła 2 o długości 30 wyznacza ciąg [1,2].

• Drogę z węzła 1 do węzła 3 o długości 43 wyznacza ciąg [1,2,3].

• Drogę z węzła 1 do węzła 4 o długości 35 wyznacza ciąg [1,4].

• Drogę z węzła 1 do węzła 5 o długości 60 wyznacza ciąg [1,2,5].

• Drogę z węzła 1 do węzła 6 o długości 69 wyznacza ciąg [1,4,6].
  

Algorytm Dijkstry II

W przypadku, gdy w grafie nie wyróżniamy kierunków przemieszczania, a więc gdy rolę strzałek przejmują krawędzie, algorytm ulega pewnej modyfikacji, która pociąga za sobą zmiany w zapisie postępowania. Ponieważ w rozpatrywanych zadaniach nie pojawiają się pętle typu [i,j,i], nie będziemy rozpatrywać przemieszczeń z i do j i z powrotem. Upraszcza to zapis postępowania, gdyż nie musimy zapamiętywać bezpośrednich poprzedników.

Algorytm

Założenia startowe:

Zadany jest graf nie skierowany, wartościowany z wyróżnionym węzłem startowym w, np. w=1.

Każdemu węzłowi i będziemy przyporządkowywać cechę tymczasową d_it oraz cechę stałą d_is.

Cecha tymczasowa odpowiada wyznaczonej na bieżąco odległości od węzła startowego, cecha stała określa ostateczną odległość, wobec czego po jej wyznaczeniu nie ulega ona zmianie w trakcie dalszego postępowania. Dla węzłów mających cechę stałą, nie rozpatrujemy cechy tymczasowej.

Start

Rozpoczynamy od pewnego określonego węzła, np. w=1. Przypisujemy mu cechę stałą d_1s=0. Pozostałe węzły nie maja cechy stałej. Jako wartości cech tymczasowych przyjmujemy d_it:=
, i
1.

Iteracje

Krok I

Rozpatrujemy wszystkie węzły połączone bezpośrednio z węzłem w, któremu nadaliśmy cechę stałą. Wykorzystamy tutaj symbol zbioru następników i powiemy, że wyznaczamy zbiór S(w).

Krok II

Sprawdzamy, czy w zbiorze S(w) wszystkie węzły mają cechę stałą.

• Jeżeli tak, przechodzimy do kroku 4.

• Jeżeli istnieje przynajmniej jeden węzeł nie mający cechy stałej przechodzimy do kroku 3.

Krok III

Rozpatrujemy kolejno wszystkie węzły zbioru S(w), które nie maja cechy stałej. Dla każdego z nich obliczamy sumę cechy stałej węzła w i odległości danego węzła od węzła w i sprawdzamy, czy jest spełniona nierówność:

d_ws+c_wi<d_it.

Jeżeli nierówność jest prawdziwa, starą cechę tymczasową zastępujemy nową: d_it:=d_ws+c_wi.

W przeciwnym wypadku pozostawiamy d_it bez zmiany.

Krok IV

Sprawdzamy, czy istnieją węzły, które maja cechę tymczasową.

Jeżeli taki węzeł nie istnieje - postępowanie kończy się.
W przeciwnym przypadku, spośród węzłów mających cechę tymczasową wyznaczamy węzeł o najniższej jej wartości. Przyporządkowana cechę tymczasową tego węzła uznajemy za jego cechę stałą, a jednocześnie węzeł ten przejmuje rolę węzła w.

Przykład

Zmodyfikowane postępowanie przedstawimy na przykładzie, w którym graf przedstawiony na rysunku 1.4 odzwierciedla rzeczywiste połączenia między miejscowościami wokół Wrocławia. Korzystając z algorytmu Dijkstry II, wyznaczymy najkrótsze drogi z Wrocławia do każdej z wymienionych miejscowości.

Odległości zaznaczone na grafie 1.4 przedstawia tabela 1.8.

W tabeli wymieniamy jedynie odległości odzwierciedlające bezpośrednie połączenia między miastami. Dla połączeń oznaczonych gwiazdkami najkrótsze drogi wymagają przejazdu przez inną miejscowość.

Rys. Graf połączeń.

Miejscowość		1	2	3	4	5	6	7	8	9	10	11
Wrocław	1		34	31	62	56	*	27	*	58	*	*
Brzeg Dolny	2	34		58	43	62	*	*	*	*	*	*
Oleśnica	3	31	58		64	51	68	44	*	*	*	*
Rawicz	4	62	43	64		41	*	*	*	*	*	*
Milicz	5	56	62	51	41		71	*	*	*	*	*
Ostrów Wlkp.	6	*	*	68	*	71		*	*	*	*	*
Oława	7	27	*	44	*	*	*		15	60	*	*
Brzeg	8	*	*	*	*	*	*	15		73	96	40
Dzierżoniów	9	58	*	*	*	*	*	60	73		41	109
Kłodzko	10	*	*	*	*	*	*	*	96	41		109
Opole	11	*	*	*	*	*	*	*	40	109	109

Tab. Tabela odległości między miastami wokół Wrocławia.

ITERACJA 1

Mamy w=1 i d_1s=0, d_it=
, i
1.

Identyfikujemy S(1)={2,3,4,5,7,9}. Żaden z nich nie ma cechy stałej. Dla każdego z nich określamy cechę tymczasową.

d_2t:=
, d_1s+c₁₂=0+34=34,
d_2t:=34,

d_3t:=
, d_1s+c₁₃=0+31=31,
d_3t:=31,

d_4t:=
, d_1s+c₁₄=0+62=62,
d_4t:=62,

d_5t:=
, d_1s+c₁₅=0+56=56,
d_5t:=56,

d_7t:=
, d_1s+c₁₇=0+27=27,
d_7t:=27,

d_9t:=
, d_1s+c₁₉=0+58=58
d_9t:=58.

Wyniki pierwszej iteracji zapisane są w tabeli 1.9.

Iteracja		1	2	3	4	5	6	7	8	9	10	11	min
1	ds dt	0 -	- 34	- 31	- 62	- 56	- -	- 27	- -	- 58	- -	- -	27

Tab. Cechy stałe i tymczasowe po pierwszej iteracji.

Wskazujemy węzeł mający najmniejszą cechę tymczasową. Jest nim 7. Przyporządkowana mu cechę tymczasową zamieniamy na cechę stałą d_7s=27. Węzeł 7 przejmuje rolę węzła w.

ITERACJA 2

Mamy w=7 i d_7s=27.

Identyfikujemy S(7)={1,3,8,9}. Cechy stałej nie mają węzły 3,8,9. Dla każdego z nich określamy cechę tymczasową po sprawdzeniu z wcześniej przyporządkowaną.

d_3t:=31, d_7s+c₇₃=27+44=71
d_3t:=31,

d_8t:=
, d_7s+c₇₈=27+15=42
d_8t:=42,

d_9t:=58, d_7s+c₇₉=27+60=87
d_9t:=58.

Wyniki drugiej iteracji zapisane są w tabeli 1.10.

Iteracja		1	2	3	4	5	6	7	8	9	10	11	min
2	ds dt	0 -	- 34	- 31	- 62	- 56	- -	27 -	- 42	- 58	- -	- -	31

Tab. Cechy stałe i tymczasowe po drugiej iteracji.

Wskazujemy węzeł mający najmniejszą cechę tymczasową. Jest nim 3. Przyporządkowana mu cechę tymczasową zamieniamy na cechę stałą d_3s=31. Węzeł 3 przejmuje rolę węzła w.

ITERACJA 3

Mamy w=3 i d_3s=31.

Identyfikujemy S(3)={1,2,4,6,7}. Cechy stałej nie maja węzły 2,4,6. Dla każdego z nich określamy cechę tymczasową po sprawdzeniu z wcześniej przyporządkowaną.

d_2t:=34, d_3s+c₃₂=31+58=89
d_2t:=34,

d_4t:=62, d_3s+c₃₄=31+64=95
d_4t:=62,

d_6t:=
, d_3s+c₃₆=31+68=99
d_6t:=99.

Wyniki trzeciej iteracji przedstawione są w tabeli 1.11.

Iteracja		1	2	3	4	5	6	7	8	9	10	11	min
3	ds dt	0 -	- 34	31 -	- 62	- 56	- 99	27 -	- 42	- 58	- -	- -	34

Tab. Cechy stałe i tymczasowe po trzeciej iteracji.

Wskazujemy węzeł mający najmniejszą cechę tymczasową. Jest nim 2. Przyporządkowana mu cechę tymczasową zamieniamy na cechę stałą d_2s=24. Węzeł 2 przejmuje rolę węzła w.

ITERACJA 4

Mamy w=2 i d_2s=34.

Identyfikujemy S(2)={1,3,4,5}. Cechy stałej nie mają węzły 4,5. Dla każdego z nich określamy cechę tymczasową po sprawdzeniu z wcześniej przyporządkowana.

d_4t:=62, d_2s+c₂₄=34+43=77
d_4t:=62,

d_5t:=56, d_2s+c₂₅=34+62=96
d_5t:=56.

Wyniki czwartej iteracji przedstawia tabela 1.12.

Iteracja		1	2	3	4	5	6	7	8	9	10	11	min
4	ds dt	0 -	34 -	31 -	- 62	- 56	- 99	27 -	- 42	- 58	- -	- -	42

Tab. Cechy stałe i tymczasowe po czwartej iteracji.

Wskazujemy węzeł mający najmniejszą cechę tymczasową. Jest nim 8. Przyporządkowaną mu cechę tymczasową zamieniamy na cechę stałą d_8s=42. Węzeł 8 przejmuje rolę węzła w.

ITERACJA 5

Mamy w=8 i d_8s=42.

Identyfikujemy S(8)={7,9,10,11}. Cechy stałej nie mają węzły 9,10,11. Dla każdego z nich określamy cechę tymczasową po sprawdzeniu z wcześniej przyporządkowaną.

d_9t:=58, d_8s+c₈₉=42+73=115
d_9t:=58,

d_10,t:=
, d_8s+c_8,10=42+96=138
d_10t:=138,

d_11,t:=
, d_8s+c_8,11=42+40=82
d_11,t:=82.

Wyniki piątej iteracji przedstawia tabela 1.13.

Iteracja		1	2	3	4	5	6	7	8	9	10	11	min
5	ds dt	0 -	34 -	31 -	- 62	- 56	- 99	27 -	42 -	- 58	- 138	- 82	56

Tab. Cechy stałe i tymczasowe po piątej iteracji.

Wskazujemy węzeł mający najmniejszą cechę tymczasową. Jest nim 5. Przyporządkowaną mu cechę tymczasową zamieniamy na cechę stałą d_5s=56. Węzeł 5 przejmuje rolę węzła w.

ITERACJA 6

Mamy w=5 i d_5s=56.

Identyfikujemy S(5)={1,2,4,6}. Cechy stałej nie mają węzły 4,6. Dla każdego z nich określamy cechę tymczasową po sprawdzeniu z wcześniej przyporządkowaną.

d_4t:=62, d_5s+c₅₄=56+41=97
d_4t:=62,

d_6t:=99, d_5s+c₅₆=56+71=127
d_4t:=99.

Wyniki szóstej iteracji przedstawia tabela 1.14.

Iteracja		1	2	3	4	5	6	7	8	9	10	11	min
6	ds dt	0 -	34 -	31 -	- 62	56 -	- 99	27 -	42 -	- 58	- 138	- 82	58

Tab. Cechy stałe i tymczasowe po szóstej iteracji.

Wskazujemy węzeł mający najmniejszą cechę tymczasową. Jest nim 9. Przyporządkowaną mu cechę tymczasową zamieniamy na cechę stałą d_9s=58. Węzeł 9 przejmuje rolę węzła w.

ITERACJA 7

Mamy w=9 i d_9s=58.

Identyfikujemy S(9)={1,7,8,10,11}. Cechy stałej nie mają węzły 10,11. Dla każdego z nich określamy cechę tymczasową po sprawdzeniu z wcześniej przyporządkowaną.

d_10,t:=138, d_9s+c_9,10=58+41=99
d_10,t:=99,

d_11,t:=82, d_9s+c_9,11=58+109=167
d_4t:=82.

Wyniki siódmej iteracji przedstawia tabela 1.15.

Iteracja		1	2	3	4	5	6	7	8	9	10	11	min
7	ds dt	0 -	34 -	31 -	- 62	56 -	- 99	27 -	42 -	58 -	- 99	- 82	62

Tab. Cechy stałe i tymczasowe po siódmej iteracji.

Wskazujemy węzeł mający najmniejszą cechę tymczasową. Jest nim 4. Przyporządkowaną mu cechę tymczasową zamieniamy na cechę stałą d_4s=62. Węzeł 4 przejmuje rolę węzła w.

ITERACJA 8

Mamy w=4 i d_4s=62.

Identyfikujemy S(4)={1,2,3,5}. Wszystkie węzły mają cechę stałą. Przechodzimy więc do analizy tabeli po zmianie cechy dla węzła 4.

Wyniki przedstawia tabela 1.16.

Iteracja		1	2	3	4	5	6	7	8	9	10	11	min
8	ds dt	0 -	34 -	31 -	62 -	56 -	- 99	27 -	42 -	58 -	- 99	- 82	82

Tab. Cechy stałe i tymczasowe po ósmej iteracji.

Wskazujemy węzeł mający najmniejszą cechę tymczasową. Jest nim 11. Przyporządkowaną mu cechę tymczasową zamieniamy na cechę stałą d_11,s=82. Węzeł 11 przejmuje rolę węzła w.

ITERACJA 9

Mamy w=11 i d_11,s=82.

Identyfikujemy S(11)={8,9,10}. Cechy stałej nie ma węzeł 10. Określamy dla niego cechę tymczasową po sprawdzeniu z wcześniej przyporządkowaną.

d_10,t:=99, d_11,s+c_11,10=82+109=191
d_10,t:=99.

Wyniki dziewiątej iteracji przedstawia tabela 1.17.

Iteracja		1	2	3	4	5	6	7	8	9	10	11	min
9	ds dt	0 -	34 -	31 -	62 -	56 -	- 99	27 -	42 -	58 -	- 99	82 -	99

Tab. Cechy stałe i tymczasowe po dziewiątej iteracji.

Wskazujemy węzeł mający najmniejszą cechę tymczasową. Z dwóch mających identyczne wartości wybieramy 6. Przyporządkowaną mu cechę tymczasową zamieniamy na cechę stałą d_6s=99. Węzeł 6 przejmuje rolę węzła w.

ITERACJA 10

Mamy w=6 i d_6s=99.

Identyfikujemy S(6)={3,5}. Wszystkie węzły mają cechę stałą. Przechodzimy więc do analizy tabeli po zmianie cechy dla węzła 6.

Wyniki przedstawia tabela 1.18.

Iteracja		1	2	3	4	5	6	7	8	9	10	11	min
10	ds dt	0 -	34 -	31 -	62 -	56 -	99 -	27 -	42 -	58 -	- 99	82 -	99

Tab. Cechy stałe i tymczasowe po dziesiątej iteracji.

Wybór węzła, który przejmuje rolę w jest jednoznaczny. Jest nim 10. Przyporządkowaną mu cechę tymczasową zamieniamy na cechę stałą d_10,s=99.

Otrzymujemy tabelę 1.19.

Iteracja		1	2	3	4	5	6	7	8	9	10	11	min
	ds dt	0 -	34 -	31 -	62 -	56 -	99 -	27 -	42 -	58 -	99 -	82 -

Tab. Cechy stałe i tymczasowe po zakończeniu postępowania.

Ponieważ wyczerpaliśmy tym samym zbiór węzłów nie mających cechy stałej, postępowanie kończy się. Cechy stałe ostatniej tabeli określają poszukiwane odległości.

Zestawienie, które pozwala szybko odczytywać każda drogę zaczynającą się w węźle 1, przedstawia tabela 1.20., w której podajemy numer węzła końcowego, długość drogi do niego i węzeł bezpośrednio go poprzedzający.

Odczytujemy teraz przykładowo: dla węzła 11 poprzednikiem jest 8, dla 8 poprzednikiem jest 7, a dla 7 poprzednikiem jest 1. Mamy więc drogę 1-7-8-11 o długości 82.

Węzeł końcowy	1	2	3	4	5	6	7	8	9	10	11
Długość drogi	0	34	31	62	56	99	27	42	58	99	82
Węzeł poprzedzający	-	1	1	1	1	3	1	7	1	9	8

Tab. Zestawienie odległości i dróg z Wrocławia do pozostałych miast.

2. Planowanie tras dostaw dla wielu pojazdów

2.1 Zasady tworzenia tras

Rozpatrzymy zadanie dostaw produktów do klientów. Przyjmujemy, że są spełnione następujące założenia:

• Wspólna miara ładowności ze względu na jednorodność produktów

• Symbolem Lo oznaczamy magazyn produktów producenta, z którego pobieramy produkty i dostarczamy do na odbiorców

• Symbolami Bi,….Bn oznaczamy potencjalnych odbiorców

• Małe bi to zamówienie odbiorcy

• Q - ładowność środków transportowych

• Ładowność środków transportowych musi być większa niż zamówienie odbiorcy, czyli Q>bi, i=1,2…n

• Dopuszczalny czas trwania przewozu przez jeden środek transportu ( od producenta do klienta i z powrotem ) nie może przekroczyć T jednostki czasu

• Czas wyładowania ładunku jest równy zero

Nasze zadnie sformułujemy następująco: należy wyznaczyć ilość środków transportowych od trasy ich przejazdów pozwalające obsłużyć wszystkie zamówienia klientów przy zachowaniu warunków przewozu tak, aby łączny czas obsługi wszystkich klientów był minimalny. Sformułowanie zadania składa się z dwóch zadań częściowych:

• Przydziału klientów do określonego środka transportu

• Wyznaczenia tras dla każdego z nich

Jako H oznaczamy dowolną trasę rozpoczynającą się w punkcie Lo, czyli od magazynu producenta, przebiegającą przez punkty i1, i2….ir i kończąca się ponownie w punkcie Lo. Niech ty ozncza czas przejazdu z punktu i do punktu j. na mocy przyjętego założenia o dopuszczalnym czasie trwania przejazdu musimy mieć spełnioną nierówność:

t +t T

reprezentujemy trasę H=[0,i1,i2,....ir,o]

• Czas przejazdu tej trasy wynosi: t(H)=toi1+ti1i2+….=tiro

• Łączna wielkość zamówień odbiorców tej trasy: b(H)=bi1+…bir

Trasę H nazwiemy dopuszczalna gdy

B(H) Q i t(H) T

Na początku załóżmy, że każdy klient jest obsłużony indywidualnie. Oznacza to, że dla obsługi wszystkich n klientów potrzebujemy n pojazdów i każdy z nich ma prosta trasę z punktu Lo do swojego klienta i z powrotem. Łączny czas trwania dosta wynosi wtedy:

Z= (t + t )

Teraz rozpatrzmy dwóch odbiorców i i produktów, których mógłby obsłużyć jeden pojazd w ramach całej trasy, wtedy łączny czas trwania dostaw przy indywidualnej ich obsłudze wynosi:

To=(toi+tio)+(toj+tjo)

Rys. indywidualna obsługa dwóch odbiorców

Gdyby jednak w miejsce dwóch odrębnych tras zaproponowalibyśmy jedna wspólną od 0 do i potem do j i z powrotem do 0. Wtedy czas obsługi wyniósłby:

t1=toi+tij+tjo

Rys. Połączenie obsługi dwóch odbiorców

Obliczając różnice otrzymujemy:

sij=to-ti=tio+toj-tij

Jeśli sij>0, to sumaryczny czas indywidualnej obsługi trwa dłużej niż czas obsługi w ramach połączonej trasy. Wartość ta określa wielkość zaoszczędzonego czasu sij<0 oznacza ujemna oszczędność, tzn. że indywidualny tras nie powinno się łączyć we wspólną trasę.

Rozważamy przypadek dwóch tras:

H=[0,h,…i,0]

H=[0,j,….k,0]

W każdej z tych tras wyróżniliśmy dwóch klientów, którzy są obsługiwani jako pierwsi (h,j) i jako ostatni (i,k). Będziemy ich nazywać odbiorcami krańcowymi w swoich trasach. Pozostali to odbiorcy pośredni. Dokonujemy połączenia tych dwóch tras w jedną. Po odwiedzeniu klienta z pierwszej trasy powinien nastąpić powrót do punktu startu. Zamiast tego następuje wizyta u pierwszego klienta drugiej trasy i dalej kontynuacja odwiedzin zgodnie z wytyczona druga trasą. Wyróżnienie która z tras jest pierwsza a która druga odgrywa jedynie rolę ilustracyjną podobnie jak wyróżnienie strzałek na rysunku.

Rys. Połączenie dwóch tras

Nowa trasa H = [0,h,…i,j….k,0] wymaga realizacji dostaw o łącznej ładowności:

b(h )=b(H1)+b(H2),

a czas jej przejazdu wynosi:

t(H)=t(H1)+t(H2)-toi-toj+tij=t(H1)+t(H2)-sij

Gdy nastąpi skrócenie łącznego czasu przejazdu i będą zachowane warunki dopuszczalności przejazdu, czyli b(H )< Q oraz t(H ) < T to trasę H uznamy za oszczędną. Wraz z oszczędnością czasu przejazdu uzyskujemy zmniejszenie liczby środków transportu, gdyż w miejsce dwóch wysyłamy na trasę tylko jeden pojazd. Liczba tras będzie równoznaczna z liczbą pojazdów potrzebnych do obsługi klientów.

Są przypadki w których nie ma sensu rozpatrywanie łączenia tras. Są to:

• Odbiorcy, którzy już zostali uwzględnieni w tej samej trasie

• Nowi odbiorcy - dołączenie do trasy może nastąpić albo do jej początku albo na jej koniec, czyli nie ma sensu rozpatrywanie oszczędności czasu między nowym a jakimkolwiek pośrednim odbiorcą grupy uwzględnionej już w trasie.

2.2 Oszczędnościowe łączenie tras

Założenia startowe:

• Rozpatrujemy zadanie w którym znamy czasy przejazdów tij, i, j=0,1…n. Na podstawie czasów tij obliczamy potencjalne oszczędności czasów przejazdu sij. Wartości sij porządkujemy malejąco, odrzucając wcześniej wszystkie sij<0

• Przyjmujemy początkowo, że każdy odbiorca jest obsługiwany indywidualnie, co oznacza że do obsługi kierujemy n pojazdów, co oznacza, że wstępnie dopuszczamy

Przykład:

Producent ma swój magazyn we Wrocławiu. Odbiorcy maja swe lokalizacje w różnych miejscach rejonu dystrybucji. Rysunek przedstawia mapę połączeń komunikacyjnych między miejscowościami rejonu dystrybucji. W tabeli mamy przedstawione czasy przejazdu między miejscowościami w minutach oraz wielkość dostawy do danej miejscowości z magazynu producenta. Jednostką dostawy jest paleta. Podstawową jednostką transportową jest samochód mogący przewieźć Q=32 palety produktów, a czas przebywania kierowcy w trasie nie może przekroczyć T=16 godzin, czyli 960 minut.

Rys. Mapa połączeń komunikacyjnych dystrybutora z Wrocławia

		0	1	2	3	4	5	6	7	8	9
Wrocław	0	0	83	78	198	156	212	309	361	216	131	0
Wałbrzych	1	83	0	81	273	228	282	380	439	291	63	8
Legnica	2	78	81	0	277	211	292	396	450	307	66	7
Poznań	3	198	273	227	0	156	345	466	427	90	288	14
Kalisz	4	156	228	211	156	0	200	338	271	268	274	6
Częstochowa	5	212	282	292	345	200	0	139	157	81	336	5
Kraków	6	309	380	396	466	338	139	0	158	93	451	15
Kielce	7	361	439	450	427	271	157	158	0	207	512	12
Katowice	8	216	291	307	390	268	81	93	207	0	346	11
Jelenia Góra	9	131	63	66	288	274	336	451	512	346	0	9

Tab. Czasy przejazdów między miejscowościami rejonu dystrybucji

W tym przykładzie zakładamy, że mamy określone czasy przejazdu między każdymi dwoma miejscowościami, nawet gdy nie ma między nimi bezpośredniego połączenia. Z mapy połączeń można odczytać, że z Wrocławia do Krakowa można dojechać przez Katowice, albo przez Częstochowę. Pierwsza trasa ma czas przejazdu 216+93=309 min , natomiast druga 212+139=351 min. W tabeli czasów przejazdu uwzględniana jest krótsza, pierwsza trasa.

Wyznaczamy teraz macierz S, której elementy sij=tio+tjo-tij, dla i, j=1,…n,i>j oraz sij=0 dla i=j. bierzemy największą wartość sij i odczytujemy wskazania numerów odbiorców. Jeżeli zbiór tych wartości jest pusty - postępowanie się kończy.

	0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0	0
1	0	0	80	8	11	13	12	5	8	151
2	0	80	0	-1	23	-2	-9	-11	-13	143
3	0	8	-1	0	198	65	41	132	24	41
4	0	11	23	198	0	168	127	246	104	13
5	0	13	-2	65	168	0	382	416	347	7
6	0	12	-9	41	127	382	0	512	432	-11
7	0	5	-11	132	246	416	512	0	370	-20
8	0	8	-13	24	104	347	432	370	0	1
9	0	151	143	41	13	7	-11	-20	1	0

Tab. Planowanie tras dostaw dla wielu pojazdów

Macierz S dla przewozów w rejonie dystrybucji

Tworzymy teraz ciąg malejących wartości z dodatnich elementów macierzy S. Jest on następujący:

S67> S68> S57> S56> S78> S58> S47> S34> S45> S19>

512. 432> 416> 382> 370> 347> 246> 198> 168> 151>

S29> S37> S46> S48> S12> S35> S39= S36> S38> S24>

143> 132> 127> 104> 80> 65> 41= 41> 24> 23>

S49= S15> S16> S14> S18= S13> S59> S17> S89

13= 13> 12> 11> 8= 8> 7> 5> 1

Rozwiązaniem startowym jest indywidualna obsługa każdego z klientów, co oznacza, że powinniśmy dysponować 9 samochodami. W kolejnych interakcjach będziemy sprawdzać, czy można trasy i tym samym zmniejszać liczbę samochodów.

INTERAKCJA 1

S67=512. Zarówno 6 jak i 7 są obsługiwani indywidualnie, a więc tworzymy grupę {i,j} i sprawdzamy, czy trasa H=[0,6,7,0] spełnia warunki dopuszczalności przewozu. Gdy warunki są spełnione - tworzymy trasę [0,6,7,0]. W przeciwnym wypadku skreślamy s z listy i przechodzimy do następnego wskaźnika oszczędności.

Mamy zatem:

T=309+158+361=828<960 - dopuszczalny czas przewozu

b=15+12=27<32 - ładowność

trasa spełnia warunki dopuszczalności. Przyjmujemy zatem:

H=[0,6,7,0]

INTERAKCJA 2

S62=432. 6 należy do trasy H i jest odbiorcą krańcowym, a konkretnie - pierwszym. Natomiast 8 jest obsługiwany indywidualnie. Odbiorca i jest więc odbiorcą krańcowym, sprawdzamy zatem, czy dołączenie odbiorcy j do trasy nie naruszy warunków dopuszczalności przewozu. Jeśli warunki przewozu są spełnione to odbiorcę j dołączamy do trasy zawierającej i przy czym j będzie obsługiwany:

• Przed i, gdy i występował w trasie jako pierwszy

Rys. Dołączenie j do trasy przed i

Trasa wygląda następująco [0,j,i….0]

• Po i, gdy i występuje jako ostatni z obsługiwanych

Rys. Dołączenie j do trasy po i

Trasa wygląda następująco [0,….,i,j,0]

Możemy w tej interacji rozpatrywać trasę H=[0,8,6,7,0]. Dopuszczalny czas przejazdu wynosi:

T=216+93+158+361=828<960

B=11+15+12=38>32

Jeden warunek przewozu dotyczący dopuszczalności nie został spełniony i dlatego nie możemy odbiorcy 8 dołączyć do trasy.

INTERACJA 3

S67=416. 7 należy do trasy H1 i jest odbiorca krańcowym, a konkretnie ostatnim. Natomiast 5 jest obsługiwany indywidualnie. Możemy rozpatrywać trasę H=[0,6,7,5,0].

Mamy:

T=309+158+157+212=830<960

b=15+!2+5=32=32

5 dołączamy do trasy H11 i obsługujemy po i, czyli7, gdyż i występował jako ostatni z obsługiwanych. Otrzymujemy trasę:

H1=[0,6,7,5,0]

Zauważamy, że pojemność samochodu trasy H1 jest w pełni wykorzystana, zatem w następnych interacjach możemy z góry odrzucać możliwości połączenia tej trasy z innymi.

INTERACJA 9

S45=168. 4 należy do trasy H2, natomiast 5 do trasy H1. połączenie tras ma sens, gdy zarówno i jak i j są odbiorcami krańcowymi swych tras oraz gdy po połączeniu tras są spełnione warunki przewozu. Zatem połączenie tych tras jest niemożliwe.

INTERACJA 11

S29=143. 2 jest obsługiwana indywidualnie, natomiast 9 należy do trasy H3, gdzie jest odbiorcą krańcowym - konkretnie ostatnim. Możemy wieć rozpatrywać trasę:

H=[0,1,9,2,0]

Mamy:

T=83+63+66+78=290<960

b=8+9+7=24<32

Modyfikujemy trasę H3, gdyż warunki przewozu zostały spełnione:

H3=[0,1,9,2,0]

INTERACJA 14

S48=104. 4 należy do trasy h2 jako ostatni odbiorca, natomiast 8 jest odbiorca indywidualnym. Tworzymy trasę:

H=[0,3,4,8,0]

Mamy:

T=198+156+268+216=838<960

b=14+6+11=31<32

Modyfikujemy więc trasę H2=[0,3,4,8,0]

Po wyczerpaniu listy możliwych stwierdzimy, że zasadnicze są trasy:

H1=[0,6,7,5,0], dla której T=830 min. i b =32 palety

H2=[0,3,4,8,0], dla której T=838 min. i b = 31 palety

H2=[0,1,9,2,0], dla której T=290 min. i b = 24 palety

Wyznaczone trasy są przedstawione na rysunku.

Rys. Trasy przewozu w rejonie dystrybucji

Wprowadzając nazwy miejscowości mamy:

H1: Wrocław-Kraków-Kielce-Częstochowa-Wrocław

H2: Wrocław-Poznań-Kalisz-Katowice-Wrocław

H3: Wrocław-Wałbrzych-Jelenia Góra-Legnica-Wrocław

3. Rozdział zadań przewozowych

3.1 Zadania przyporządkowania

Określenie tras przewozu i ilości pojazdów nie gwarantuje, że są to trasy o podobnej skali przewozów. Także ładunki różnią się składem produktów, również pojazdy nie zawsze są dostosowane do przewozu danego typu ładunku. Powstaje wtedy problem odpowiedniego przyporządkowania pojazdów do tras przewozów. Jest to zadanie ogólniejsze, znane w literaturze, jako zadanie przyporządkowania.

Uściślijmy najpierw założenia problemu:

1. mamy n jednostek wykonawczych R_i , i = ,....,n (osób, maszyn, samochodów) oraz n zadań Z_j , j = ,....,n do wykonania

2. przyjmijmy, że każda jednostka R_i może właściwie wykonać dowolne zadanie Z_j, ale efektywność wykonania każdego z nich jest różna

3. efektywność wykonania zadania Z_j przez R_i może być wyrażona albo przez miarę korzyści - oznaczamy ją d_ij albo przez miarę nakładu - oznaczamy ją k_ij

Cel zadania sformułujemy następująco: należy jednostkom R_i tak przyporządkować zadania Z_j, aby efekt sumaryczny był jak najkorzystniejszy.

Należy wprowadzić zmienne x, i = ,....,n; j = 1,....,n, które będą odzwierciedlać czy jednostce wykonawczej R_i zostało przyporządkowane zadanie Z_j czy też nie.

1, gdy R_i otrzymuje zadanie Z_j

x_ij =

0, w przeciwnym przypadku

Gdy efektywność jest wyrażana poprzez miary korzyści, najkorzystniej efekt wyraża funkcja kryterium:

Z_L = d_ij * x_ij max

Gdy efektywność jest wyrażona przez miary nakładów, najkorzystniejszy efekt wyraża funkcja kryterium:

Z_k = k_ij * x_ij min

Algorytmy rozwiązywania zadań tej klasy są na ogół formułowane przy założeniu poszukiwania minimum. Zadanie, w którym poszukiwane jest maksimum efektywności można zastąpić zadaniem poszukiwania minimum w następujący sposób:

Z_L max

Możemy teraz wprowadzić standardowe oznaczenia współczynników funkcji kryterium, mianowicie c_ij. Zadanie przyporządkowania możemy zatem sformułować następująco:

(Jest to tzw. Zadanie prymalne)

Wprowadzone zmienne x_ij są zmiennymi binarnymi, czyli x_ij = 1 lub x_ij = 0. Praktycznie zapis zadania sprowadza się do macierzowego ujęcia zmiennych x_ij oraz współczynników c_ij

c₁₁ c_1j c_1n

C = c_il c_ij c_in

c_n1 c_nj c_nn

Wskazane przyporządkowanie jest, w tej konwencji równoznaczne ze wskazaniem elementu macierzy C. Jeżeli zostanie wskazany np. element c₂₃ to odczytujemy, że jednostka wykonawcza R₂ otrzymała zadanie Z₃.

Gdy zadanie (minimalizacja) nie jest symetryczne tzn. gdy liczba wykonawców nie jest równa liczbie zadań, sprowadzamy go do symetrycznego wprowadzając pomocnicze kolumny lub wiersze z elementami będącymi liczbami „dużymi” zwanymi „big - M”. W zadaniu z maksymalizacją wprowadzane współczynniki muszą być równe 0. Gdy chcemy zablokować pewien przedział, przyjmujemy, że wartość współczynnika c jest równa „big - M”.

3.2 Własności zadań przyporządkowań

Zadania przyporządkowania należą do klasy zadań liniowych o specjalnej strukturze. Ponieważ w omawianym dalej postępowaniu będziemy korzystać z zapisu macierzy C, w pierwszej kolejności musimy odpowiednio przeformułować interpretację bazowego rozwiązania dopuszczalnego. Podobnie jak w klasycznych zadaniach transportowych wprowadzamy macierz przyporządkowań X, której elementami są poszukiwane zmienne x_ij;
i = 1,....,n; j = 1,...., n. Ma ona postać zgodną z zapisem macierzy C (zwany wektorem przyporządkowań).

x₁₁ x_1j x_1n

X = x_i1 x_ij x_in

X_n1 x_nj x_nn

W trakcie wyznaczania rozwiązania będziemy dokonywać przekształceń macierzy C. Będą to przekształcenia nie mające wpływu na wyznaczanie wektora przyporządkowań x.

1 własność przekształceń macierzy C - jeżeli w macierzy C do każdego elementu pewnego wiersza dodamy liczbę α lub do każdego elementu pewnej kolumny dodamy liczbę β nie ma to żadnego wpływu na wektor przyporządkowań x. Zmienia się jedynie wartość funkcji kryterium.

Istotne warunki komplementarności wiążące rozwiązania obu zadań. Są one określane przez równanie:

(u_i + v_j - c_ij) * x_ij = 0, i = 1,....,n; j = 1,....,n.

Wykorzystamy zależności między zadaniami dualnymi, aby poprzez zadanie dualne uzyskać rozwiązanie zadania prymalnego. W tym celu przeprowadzimy redukcję elementów macierzy C.

• najpierw w kolejnych wierszach od każdego elementu odejmujemy liczbę równą wartości minimalnej w tym wierszu i otrzymujemy:

• w następnej kolejności w kolejnych kolumnach od każdego elementu zmodyfikowanej macierzy odejmujemy liczbę równą wartości minimalnej w tej kolumnie i otrzymujemy:

Po redukcji macierzy C w każdej kolumnie i w każdym wierszu otrzymujemy co najmniej jedno 0. Przekształcenia macierzy C sprawiają, że otrzymujemy w niej elementy równe 0, które mają różne znaczenie. Wyróżniamy więc pewne kategorie zer:

• zera niezależne - dwa zera nazywamy zerami niezależnymi jeżeli w zredukowanej macierzy C¹ nie mają wspólnej kolumny ani wiersza.

Macierz, w której występują elementy zerowe ma własność, którą przedstawia twierdzenie Königa i Egerváry'ego. Jeżeli macierz zawiera elementy zerowe, to maksymalna liczba możliwych do wybrania zer niezależnych jest równa minimalnej liczbie linii, którymi można pokryć te wszystkie zera.

Linie tworzą minimalne pokrycie zer w macierzy. Wykorzystujemy je do sprawdzenia czy wyznaczyliśmy optymalne przyporządkowanie. Jeżeli bowiem liczba linii będzie mniejsza od n, będzie to oznaczało, że poszukiwanie rozwiązania należy kontynuować.

Przyjmijmy, że mamy zmodyfikowaną macierz C^k i wprowadzone linie pokrycia.

Wyróżniamy teraz:

• I_p - zbiór pokrytych wierszy

• I_np - zbiór nie pokrytych wierszy

• J_p - zbiór pokrytych kolumn

• J_np - zbiór nie pokrytych kolumn

W macierzy C^k rozpatrujemy elementy c^k_cj, które znajdują się w nie pokrytych wierszach, a więc i należące do I_np i nie pokrytych kolumnach czyli j należące do J_np.

Mamy następujące proste reguły modyfikacji elementów macierzy C^k:

• jeżeli element jest pokryty przez dwie linie (poziomą i pionową) - dodajmy

• jeżeli element nie jest pokryty przez żadną linię - odejmujemy

• pozostałe elementy pozostają bez zmian

3.3 Algorytm węgierski

Założenia startowe:

Znamy macierz kwadratową C, której elementy są nie ujemne. W zadaniu poszukujemy minimum funkcji kryterium

Start

Wyznaczamy zredukowaną macierz C¹ dokonując operacji:

• dla i = 1, ...., n wyznaczamy kolejno

u_i = min c_ij i = 1,....,n

i tworzymy macierz C o elementach

c_ij = c_ij - u_i i = 1,....,n j = 1,....,n;

• dla j = 1,....,n określamy kolejno:

v_j = min c_ij i = 1,....,n j = 1,....,n

i tworzymy macierz C¹ o elementach:

c^k_ij = c_ij - v_j i = 1,....,n j = 1,....,n.

W macierzy C¹ a w następnych interacjach w macierzach C^k, otrzymujemy zera, które podzielimy na różne kategorie. Wyróżniamy zera, które podzielimy na różne kategorie. Wyróżniamy zera:

• „wskazujące przyporządkowanie” a więc te, które w ramach danej iteracji wskazują przyporządkowanie x_ij = 1.

• „wykluczone”, które ze względu na dokonane już przyporządkowania nie mogą być brane pod uwagę,

• „swobodne”, które nie są ani wskazującymi przyporządkowanie ani wykluczonymi.

Interacje

Krok 1

Wskazujemy wiersz lub kolumnę o najmniejszej liczbie zer „swobodnych”. Jedno z tych zer uznajemy za „wskazujące przyporządkowanie” wszystkie inne zera zamieniamy na „wykluczone”

Powtarzamy ten krok aż do uzyskania sytuacji, gdy w macierzy nie będzie zer „swobodnych.

Krok 2

Sprawdzamy liczbę zer „wskazujących przyporządkowanie”

• jeżeli liczba tych zer jest równa n - mamy optymalne przyporządkowanie i następuje koniec postępowania,

• w przeciwnym przypadku przechodzimy do kroku 3.

Krok 3

Oznaczamy wszystkie wiersze, które nie zawierają żadnego zera „wskazującego przyporządkowanie”

Krok 4

Wykonujemy na przemian następujące operacje:

1. oznaczamy wszystkie kolumny, które w już oznaczonych wierszach mają przynajmniej jedno zero „wykluczone”

2. oznaczamy wszystkie wiersze, które w kolumnach oznaczonych w 1 podpunkcie mają przynajmniej jedno zero „wskazujące przyporządkowanie”

Operacje 1) i 2) powtarzamy na przemian dopóki nie wyczerpiemy możliwości oznaczania

Krok 5

Pokrywamy liniami oznaczone wiersze oraz oznaczone kolumny

Krok 6

Wśród nie pokrytych elementów wierszy i kolumn wyznaczamy

Krok 7

Dokonujemy modyfikacji macierzy C^k

• do elementów pokrytych przez dwie linie dodajemy

• od elementów nie pokrytych żadną linią odejmujemy

• pozostałe elementy pozostawiamy bez zmian

Jako wynik otrzymujemy macierz C^k+1 dla której powtarzamy interację.

2

3

4

1

7

6

5

1

2

3

j

4

5

i

j

4

5

6

2

3

1

9

7

8

1111111

10

0

j

i

0

j

i

0

h

k

j

i

3

4

7

6

8

5

1

9

2

0

0

j

i

i

j

0

9

2

3

4

0

1

8

6

7

5

---