Zagadnienie przydziału i algorytm węgierski — model, zapis liniowy i rozwiązanie krok po kroku.
Zagadnienie przydziału polega na optymalnym przypisaniu wykonawców do zadań. Każdy wykonawca ma otrzymać jedno zadanie, a każde zadanie ma zostać wykonane przez dokładnie jednego wykonawcę. Celem może być minimalizacja łącznego kosztu lub czasu albo maksymalizacja łącznego zysku, efektu czy korzyści. Jedną z najpopularniejszych metod rozwiązywania takich problemów minimalizacyjnych jest algorytm węgierski.
Spis treści
Na czym polega zagadnienie przydziału?
Zagadnienie przydziału jest jednym z podstawowych modeli badań operacyjnych. W najprostszym wariancie mamy taką samą liczbę wykonawców i zadań. Każdemu wykonawcy można przypisać każde zadanie, ale koszt, czas lub korzyść zależą od konkretnej pary.
Przykładowo można przydzielać:
- pracowników do stanowisk pracy,
- kierowców do tras,
- maszyny do zleceń produkcyjnych,
- techników do zgłoszeń serwisowych,
- wykładowców do grup zajęciowych,
- programistów do modułów projektu,
- pojazdy do rejonów dostaw.
W każdej z tych sytuacji obowiązuje zasadnicza reguła: jeden wykonawca otrzymuje jedno zadanie, a jedno zadanie zostaje powierzone jednemu wykonawcy. Nie chodzi więc o podział pracy w dowolnych proporcjach, lecz o wybór najlepszego pełnego skojarzenia dwóch zbiorów.
Ważne rozróżnienie
W zagadnieniu transportowym jeden dostawca może obsługiwać wielu odbiorców, a wielkości przewozów mogą być dowolne. W zagadnieniu przydziału decyzja ma charakter binarny: dany przydział jest realizowany albo nie jest realizowany.
Macierz kosztów i zadanie niezrównoważone
Dane do zadania przydziału zapisuje się zwykle w postaci macierzy. Wiersze reprezentują wykonawców, kolumny reprezentują zadania, a liczba w komórce oznacza koszt wykonania określonego zadania przez określonego wykonawcę.
Symbol \(c_{ij}\) oznacza koszt przydzielenia wykonawcy \(i\) do zadania \(j\). Zamiast kosztu można w ten sam sposób zapisać czas realizacji, zużycie materiału, emisję, liczbę przejechanych kilometrów albo inną wielkość, którą chcemy minimalizować.
Zadanie zrównoważone
Klasyczna postać algorytmu węgierskiego dotyczy macierzy kwadratowej, czyli sytuacji, w której liczba wykonawców jest równa liczbie zadań. Jeśli mamy czterech wykonawców i cztery zadania, otrzymujemy macierz \(4\times4\).
Zadanie niezrównoważone
W praktyce liczba wykonawców i zadań często nie jest taka sama. Gdy wykonawców jest mniej niż zadań, dodajemy fikcyjnych wykonawców. Gdy wykonawców jest więcej, dodajemy fikcyjne zadania. W ten sposób uzupełniamy macierz do postaci kwadratowej.
Jeżeli brak realizacji zadania nie powoduje dodatkowego kosztu, w komórkach związanych z fikcyjnym wykonawcą lub fikcyjnym zadaniem można wpisać zero. Gdy jednak pominięcie zadania oznacza stratę, karę umowną lub koszt alternatywny, należy wpisać wartość odzwierciedlającą tę konsekwencję.
Fikcyjny wykonawca nie zawsze oznacza koszt równy zero
Wartość zero jest poprawna tylko wtedy, gdy pozostawienie zadania bez realizacji nie wiąże się z żadnym kosztem. Jeżeli niewykonanie zlecenia oznacza stratę, do odpowiedniej komórki należy wpisać tę stratę lub przyjętą karę.
Model programowania liniowego ze zmiennymi binarnymi
Zagadnienie przydziału można zapisać jako model programowania liniowego. Wprowadzamy zmienne decyzyjne:
Jeżeli minimalizujemy łączny koszt, funkcja celu ma postać:
Każdy wykonawca ma otrzymać dokładnie jedno zadanie:
Każde zadanie ma zostać przydzielone dokładnie jednemu wykonawcy:
Ostatecznie określamy dziedzinę zmiennych:
Model można rozwiązać metodą programowania całkowitoliczbowego, na przykład w Excel Solverze lub w specjalistycznym oprogramowaniu optymalizacyjnym. Dla klasycznego problemu przydziału bardzo wygodny jest jednak algorytm węgierski, ponieważ wykorzystuje specyficzną strukturę tego zadania.
Minimalizacja a maksymalizacja
Algorytm węgierski najczęściej przedstawia się dla zagadnień minimalizacyjnych. Jeżeli w macierzy znajdują się zyski, efekty lub korzyści, które chcemy maksymalizować, można najpierw przekształcić zadanie maksymalizacyjne do równoważnego zadania minimalizacyjnego.
Niech \(p_{ij}\) oznacza korzyść uzyskaną przy przypisaniu wykonawcy \(i\) do zadania \(j\). Najpierw wyznaczamy największy element całej macierzy:
Następnie dla każdej komórki tworzymy koszt przekształcony:
Największe korzyści zmieniają się wtedy w najmniejsze koszty. Minimalizacja sumy wartości \(c_{ij}\) prowadzi do tego samego przydziału, który wcześniej maksymalizował sumę korzyści \(p_{ij}\).
Dlaczego to działa?
W pełnym przydziale zawsze wybieramy dokładnie \(n\) komórek. Suma przekształconych kosztów jest więc równa \(n\cdot p_{\max}\) pomniejszonemu o sumę pierwotnych korzyści. Im większa jest suma korzyści, tym mniejsza będzie suma kosztów przekształconych.
Algorytm węgierski
Algorytm węgierski prowadzi do rozwiązania przez kolejne przekształcanie macierzy kosztów. Kluczowe jest to, że po redukcjach nadal otrzymujemy przydział optymalny dla pierwotnego problemu.
Krok 1. Redukcja wierszy
W każdym wierszu odnajdujemy najmniejszy element i odejmujemy go od wszystkich wartości w tym wierszu. W każdym wierszu pojawi się wtedy przynajmniej jedno zero.
Krok 2. Redukcja kolumn
W każdej kolumnie z macierzy otrzymanej po redukcji wierszy odnajdujemy najmniejszy element i odejmujemy go od wszystkich wartości w tej kolumnie. Po tej operacji w każdej kolumnie występuje co najmniej jedno zero.
Krok 3. Pokrycie zer minimalną liczbą linii
Wszystkie zera w macierzy pokrywamy minimalną liczbą linii poziomych i pionowych. Jeżeli liczba użytych linii jest równa wymiarowi macierzy, można przejść do wyboru niezależnych zer. Jeżeli liczba linii jest mniejsza, potrzebna jest korekta macierzy.
Krok 4. Korekta macierzy
Gdy liczba linii pokrywających zera jest mniejsza niż liczba wierszy, znajdujemy najmniejszy element niepokryty liniami. Następnie:
- odejmujemy tę wartość od wszystkich elementów niepokrytych,
- dodajemy ją do elementów leżących na przecięciu dwóch linii,
- nie zmieniamy elementów pokrytych dokładnie jedną linią.
Po korekcie ponownie pokrywamy wszystkie zera minimalną liczbą linii. Czynność powtarzamy aż do momentu, gdy liczba linii będzie równa wymiarowi macierzy.
Krok 5. Wybór niezależnych zer
Niezależne zera to takie zera, z których żadne dwa nie leżą w tym samym wierszu ani w tej samej kolumnie. Wybieramy po jednym zerze dla każdego wykonawcy i dla każdego zadania. Wybrane zera określają ostateczny przydział.
Co oznacza zero w macierzy zredukowanej?
Zero nie oznacza, że rzeczywisty koszt wykonania zadania jest równy zero. Oznacza jedynie, że po wykonanych redukcjach dana para wykonawca – zadanie jest kandydatem do przydziału optymalnego. Wartość funkcji celu zawsze odczytujemy z pierwotnej macierzy kosztów.
Przykład rozwiązany krok po kroku
Załóżmy, że czterech pracowników \(A\), \(B\), \(C\) i \(D\) ma zostać przydzielonych do czterech zadań \(Z_1\), \(Z_2\), \(Z_3\) i \(Z_4\). Liczby w tabeli oznaczają koszt wykonania danego zadania przez danego pracownika.
| Wykonawca / zadanie | \(Z_1\) | \(Z_2\) | \(Z_3\) | \(Z_4\) | Minimum wiersza |
|---|---|---|---|---|---|
| \(A\) | 82 | 83 | 69 | 92 | 69 |
| \(B\) | 77 | 37 | 49 | 92 | 37 |
| \(C\) | 11 | 69 | 5 | 86 | 5 |
| \(D\) | 8 | 9 | 98 | 23 | 8 |
Krok 1. Redukcja wierszy
Od każdego elementu wiersza \(A\) odejmujemy 69, od każdego elementu wiersza \(B\) odejmujemy 37, od każdego elementu wiersza \(C\) odejmujemy 5, a od każdego elementu wiersza \(D\) odejmujemy 8.
| Wykonawca / zadanie | \(Z_1\) | \(Z_2\) | \(Z_3\) | \(Z_4\) |
|---|---|---|---|---|
| \(A\) | 13 | 14 | 0 | 23 |
| \(B\) | 40 | 0 | 12 | 55 |
| \(C\) | 6 | 64 | 0 | 81 |
| \(D\) | 0 | 1 | 90 | 15 |
Krok 2. Redukcja kolumn
Po redukcji wierszy minima kolumn wynoszą kolejno: \(0\), \(0\), \(0\) oraz \(15\). Tylko w czwartej kolumnie trzeba więc odjąć wartość 15 od wszystkich elementów.
| Wykonawca / zadanie | \(Z_1\) | \(Z_2\) | \(Z_3\) | \(Z_4\) |
|---|---|---|---|---|
| \(A\) | 13 | 14 | 0 | 8 |
| \(B\) | 40 | 0 | 12 | 40 |
| \(C\) | 6 | 64 | 0 | 66 |
| \(D\) | 0 | 1 | 90 | 0 |
Krok 3. Pokrycie zer liniami
Wszystkie zera można pokryć trzema liniami: linią poziomą wiersza \(D\) oraz liniami pionowymi kolumn \(Z_2\) i \(Z_3\). Ponieważ macierz ma wymiar \(4\times4\), a liczba linii jest równa 3, nie można jeszcze wybrać czterech niezależnych zer. Trzeba wykonać korektę macierzy.
| Wykonawca / zadanie | \(Z_1\) | \(Z_2\) | \(Z_3\) | \(Z_4\) |
|---|---|---|---|---|
| \(A\) | 13 | 14 | 0 | 8 |
| \(B\) | 40 | 0 | 12 | 40 |
| \(C\) | 6 | 64 | 0 | 66 |
| \(D\) | 0 | 1 | 90 | 0 |
Najmniejszym elementem niepokrytym liniami jest liczba \(6\). Odejmujemy ją od wszystkich elementów niepokrytych, dodajemy ją do elementów leżących na przecięciu dwóch linii, a pozostałe elementy pozostawiamy bez zmian.
Krok 4. Korekta macierzy
| Wykonawca / zadanie | \(Z_1\) | \(Z_2\) | \(Z_3\) | \(Z_4\) |
|---|---|---|---|---|
| \(A\) | 7 | 14 | 0 | 2 |
| \(B\) | 34 | 0 | 12 | 34 |
| \(C\) | 0 | 64 | 0 | 60 |
| \(D\) | 0 | 7 | 96 | 0 |
Możemy teraz wybrać cztery niezależne zera:
- wykonawca \(A\) otrzymuje zadanie \(Z_3\),
- wykonawca \(B\) otrzymuje zadanie \(Z_2\),
- wykonawca \(C\) otrzymuje zadanie \(Z_1\),
- wykonawca \(D\) otrzymuje zadanie \(Z_4\).
Rozwiązanie optymalne
Optymalny przydział to: \(A\rightarrow Z_3\), \(B\rightarrow Z_2\), \(C\rightarrow Z_1\), \(D\rightarrow Z_4\).
Minimalny łączny koszt wynosi zatem 140 jednostek kosztu.
Obliczając wartość funkcji celu, wracamy do macierzy pierwotnej. Zera z macierzy zredukowanej służą wyłącznie do wskazania optymalnego układu przydziałów.
Najczęstsze błędy
- Odczytywanie kosztu z macierzy zredukowanej. Wartość funkcji celu liczymy zawsze na podstawie pierwotnej macierzy kosztów.
- Wybieranie dwóch zer z jednego wiersza lub jednej kolumny. Każdy wykonawca i każde zadanie muszą wystąpić dokładnie raz.
- Pomijanie elementu fikcyjnego w zadaniu niezrównoważonym. Algorytm klasyczny wymaga macierzy kwadratowej.
- Uznawanie, że każde zero powinno zostać wybrane. Wybieramy tylko niezależne zera, czyli takie, które nie kolidują ze sobą w wierszach i kolumnach.
- Niepoprawna korekta macierzy. Najmniejszą wartość niepokrytą odejmujemy od elementów niepokrytych, ale dodajemy ją wyłącznie na przecięciach dwóch linii.
- Niewłaściwe przekształcenie maksymalizacji. Przed uruchomieniem algorytmu trzeba zamienić macierz korzyści na macierz kosztów przekształconych.
Podsumowanie
Zagadnienie przydziału służy do wyboru najlepszego pełnego przypisania wykonawców do zadań. Można je formalnie zapisać jako problem programowania liniowego ze zmiennymi binarnymi, a w klasycznej wersji minimalizacyjnej wygodnie rozwiązać algorytmem węgierskim.
Najważniejsze etapy algorytmu to redukcja wierszy, redukcja kolumn, pokrywanie zer minimalną liczbą linii, ewentualna korekta macierzy oraz wybór niezależnych zer. Warto pamiętać, że zredukowana macierz pomaga odnaleźć optymalny przydział, ale całkowity koszt lub zysk obliczamy zawsze na podstawie danych początkowych.
Powiązane artykuły
- Programowanie matematyczne i programowanie liniowe — modele, metody i zastosowania
- Metoda simpleks — algorytm rozwiązywania zadań programowania liniowego
- Zagadnienie transportowe i metoda potencjałów
- Programowanie liniowe – metoda graficzna
Masz problem z tym tematem?
Wszechwiedza.pl pomaga zrozumieć matematykę, statystykę, ekonometrię, badania operacyjne, analizę danych, mechanikę, rachunkowość i wiele innych przedmiotów — spokojnie, konkretnie i krok po kroku.
Zapytaj o pomoc