3848093740

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

Wyszukiwarka

Podobne podstrony:
• Problemów controllingu, w szczególności zastosowania instrumentów controllingu finansowego,
Jeśli zdarzy nam się dostać sadzonkę czegoś ładnego warto zastosować szczególną sztuczkę by
kapitałowym, a zatem problemów szeroko rozumianej analizy jego kondycji finansowej (szczególnie stru
Slajd4 ^Problem wzajemnego wykluczania -struktura procesu sekwencyjnego Dziedziny zastosowań ...Wzaj
kapitałowym, a zatem problemów szeroko rozumianej analizy jego kondycji finansowej (szczególnie stru
• Problemów controllingu, w szczególności zastosowania instrumentów controllingu finansowego,
image 063 Twierdzenie o dualności 63 Rys. 3.3. Antena szczelinowa: a) struktura anteny, b) struktura
img160 100 -    Co by było, gdyby dało się problem, rzecz odwrócić? Co warto przegrup
596.    Systemowe i strukturalne uwarunkowania zastosowania bojowego sil powietrznych
I Struktura badanych szkół. Szczegółową strukturę badanych szkół przedstawia tabela 1 oraz
15 1.2. Problem przydziału Tablica 1.7. Zmiana bazy w grafie rozwiązania Tablica 1.8. Macierz zerowa
Osobisty Trener8 FOKA INTERNETOWE Zbyt dużo, za wcześnie i Jeden z najczęstszych problemów. Wiele (
P1080020 Przemyśla II i jego żony Rychezy. Problem omawiamy szczegółowiej nieco niżej, tutaj chcieli
Laboratorium problemowe. Model Helikoptera, Sprawozdanie. Warto zwrócić uwagę na problem doboru waru
Problemy wynikające z rozproszenia struktury sterowania •    Konieczność precyzyjnej

więcej podobnych podstron