3848093740

17

1.2. Problem przydziału

szczególna strukturę warto zastosować prostszy algorytm węgierski. Niech będzie dana macierz kosztów C = [cy]

Algorytm węgierski

Krok 1. Przekształcić macierz kosztów C = [cij] tak, aby w każdym jej wierszu i w każdej kolumnie występowało przynajmniej jedno zero. W tym celu od każdego wiersza macierzy odejmuje się jego najmniejszy element i, jeżeli trzeba, to następnie od każdej kolumny odejmuje się jej najmniejszy element.

Krok 2. W przekształconej macierzy skreślić możliwie najmniejszą liczbą linii wszystkie wiersze i kolumny zawierające zera. Jeżeli najmniejsza liczba linii niezbędnych do pokrycia wszystkich zer jest równa wymiarowi macierzy n, to otrzymane rozwiązanie jest optymalne.

Krok 3. Ustalić rozwiązanie optymalne, polegające na takiej konstrukcji macierzy Xij, aby jedynki znalazły się tylko na tych miejscach, na których w przekształconej macierzy kosztów występują zera (w każdym wierszu i każdej kolumnie może występować tylko jedna jedynka).

Krok 4. Jeżeli liczba skreśleń jest mniejsza od rozmiaru macierzy n, w bieżącej macierzy kosztów należy znaleźć najmniejszy nieskreślony element i ten element:

—    odjąć od elementów nieskreślonych,

—    dodać do elementów podwójnie skreślonych,

—    elementy skreślone jedną linią zostawić bez zmian.

Krok 5. Wrócić do kroku 2.

W celu ułatwienia obliczeń podzielmy wszystkie elementy macierzy [cy] przez 100. Po przekształceniu macierzy kosztów zgodnie ze wskazówkami w kroku 1 otrzymujemy macierz przedstawioną w tablicy 1.11.

Tablica 1.11. Macierz kosztów po kroku 1 algorytmu

0	0	0	0
7	0	6	4
11	0	18	6
10	0	21	4

Jak widać wszystkie zera można w tej macierzy skreślić za pomocą dwóch linii. Zatem rozwiązanie nie jest optymalne. Znajdujemy najmniejszy nieskreślony element macierzy, czyli element (2,4) lub (4,4) o wartości 4. Po przekształceniu otrzymujemy macierz przedstawioną w tablicy 1.12.

Tablica 1.12. Macierz kosztów po pierwszej iteracji algorytmu

0	4	0	0
3	0	2	0
7	0	15	2
6	0	18	0

Nadal nie jest to rozwiązanie optymalne. Po kolejnej iteracji otrzymujemy macierz pokazaną w tablicy 1.13 reprezentującą rozwiązanie optymalne.

Tablica 1.13. Macierz kosztów po drugiej iteracji algorytmu

0	6	0	2
1	0	0	0
5	0	13	2
4	0	16	0