Zagadnienie przydziału

Szczególnym przypadkiem zadania programowania liniowego jest przypadek kiedy przydziela się jedną osobę do jednej czynności, firmę do kontraktu lub przewoźnikowi trasę przejazdu, a zmienne przyjmują wartości 0 lub 1. Zagadnienie takie nazywa się zagadnieniem przydziału.

Charakterystyczna dla zagadnienia przydziału jest wzajemna jednoznaczność przydziału osób do czynności i czynności do osób. Każda czynność jest wykonywana przez dokładnie jedną osobę, każda osoba wykonuje dokładnie jedną czynność. Konsekwencja tego jest że macierz zawierająca cel zadania (zyski, koszty, czas) musi być macierzą kwadratową. Istnieją zadania które nie są zadaniami przydziału, które łatwo da się do takich sprowadzić. Kilka takich zadań opisano w dalszej części tego tekstu.

Zagadnienie takie można, jak wszystkie zagadnienia programowania liniowego rozwiązać metodą SIMPLEX. Wygodniejszą i szybszą jest jednak metoda węgierska.

Zagadnienie przydziału może w funkcji celu być minimalizowane lub maksymalizowane. W przypadku rozwiązywania zadania metodą węgierską, zadanie musi być przekształcone do zadania na minimum.

Przykład 1

Miasto chce zlecić modernizację czterech budynków. Każdy z nich jest inny i wymaga od firmy budowlanej innych umiejętności, wiedzy i doświadczenia. Ogłoszono przetarg do którego stanęły cztery firmy budowlane. Proponowany koszt każdej modernizacji zaproponowany przez poszczególne firmy pokazano w tabeli (liczby w tys. zł):

		Modernizowane budynki
				Budynek 1	Budynek 2	Budynek 3	Budynek 4
Firmy	Firma 1	150	180	130	220
		Firma 2	160	200	150	190
		Firma 3	140	220	180	200
		Firma 4	140	210	140	200

Należy przydzielić firmom kontrakty tak aby każda firma dostała dokładnie jeden kontrakt i aby całkowity koszt modernizacji budynków był minimalny.

Ważne:

Macierz współczynników w zadaniu przydziału musi być kwadratowa. Jeżeli z treści zadania wynika że nie jest, należy doprowadzić do sytuacji gdy będzie kwadratowa. (patrz przykład niżej).

Model matematyczny:

W modelu będzie 16 zmiennych reprezentujących każdy możliwy kontrakt. Każda zmienna odpowiada na pytanie: czy dana firma dostanie kontrakt na wykonanie modernizacji określonego budynku ? W związku z tym zmienne przyjmują tylko dwie wartości: 0 i 1.

Zmienne:

x₁₁, x₁₂, x₁₃, x₁₄

x₂₁, x₂₂, x₂₃, x₂₄

x₃₁, x₃₂, x₃₃, x₃₄

x₄₁, x₄₂, x₄₃, x₄₄

gdzie

Ograniczenia dla firm:

x₁₁+x₁₂+x₁₃+x₁₄ = 1

x₂₁+x₂₂+x₂₃+x₂₄ = 1

x₃₁+x₃₂+x₃₃+x₃₄ = 1

x₄₁+x₄₂+x₄₃+x₄₄ = 1

Ograniczenia dla budów:

x₁₁+x₂₁+x₃₁+x₄₁ = 1

x₁₂+x₂₂+x₃₂+x₄₂ = 1

x₁₃+x₂₃+x₃₃+x₄₃ = 1

x₁₄+x₂₄+x₃₄+x₄₄ = 1

Funkcja celu:

F = 150x₁₁+180x₁₂+130x₁₃+220x₁₄+160x₂₁+200x₂₂+150x₂₃+190x₂₄+
+140x₃₁+220x₃₂+180x₃₃+200x₃₄+140x₄₁+210x₄₂+140x₄₃+200x₄₄ → min

Ze względu na konstrukcję zmiennych warunki nieujemności są zbędne.

Metoda węgierska

Metoda węgierska służy do rozwiązywania zagadnienia przydziału. Służy wyłącznie do rozwiązywania zadań „na minimum”. W przypadku zadania „na maksimum” niezbędne będzie wykonanie zabiegu zmieniającego „kierunek zadania” opisanego w następnym przykładzie.

150	180	130	220
160	200	150	190
140	220	180	200
140	210	140	200

1. W każdej kolumnie należy znaleźć najmniejszą liczbę i odjąć ją od wszystkich wyrazów w kolumnie.

10	0	0	30
20	20	20	0
0	40	50	10
0	30	10	10

2. Następnie w każdym wierszu powtarzamy tę czynność tzn. dla każdego wiersza szukamy wartości najmniejszej i odejmujemy od wszystkich elementów wiersza. W tym wypadku najmniejszymi elementami każdego wiersza jest 0 więc nic się nie zmieni.

10	0	0	30
20	20	20	0
0	40	50	10
0	30	10	10

Powyższe dwie operacje można odwrócić tzn. najpierw odejmować w wierszach a później w kolumnach. Na ostateczny wynik nie będzie miało wpływu, chociaż wartości w powstałych tabelach będą różne.

Rząd macierzy można utożsamiać z ilością kolumn lub wierszy w macierzy. Nie jest to do końca prawdą ale dla potrzeb metody węgierskiej jest wystarczające.

3. Jak najmniejszą ilością cięć (jednocześnie poziomych i pionowych) należy wyciąć wszystkie zera. Jeżeli minimalna ilość cięć będzie równa rzędowi macierzy, to można szukać rozwiązania optymalnego, jeżeli będzie mniejsza, należy rozwiązanie poprawiać (postępowanie analogiczne do sprawdzania, czy w wierszu 0 tablicy SIMPLEX są liczby ujemne).

10	0	0	30
20	20	20	0
0	40	50	10
0	30	10	10

W tym wypadku minimalna ilość cięć wynosi 3, rząd macierzy wynosi 4, więc nie można jeszcze odczytać rozwiązania optymalnego.

4. Poprawianie rozwiązania.

Spośród liczb nieskreślonych (40, 50, 10, 30, 10, 10) należy wybrać najmniejszą. Tę liczbę:

• odejmujemy od liczb nieskreślonych (40, 50, 10, 30, 10, 10),

• dodajemy do podwójnie skreślonych (10, 20),

• raz skreślone przepisujemy (0, 0, 30, 20, 20, 0, 0, 0).

20	0	0	30
30	20	20	0
0	30	40	0
0	20	0	0

Aby sprawdzić, czy można odszukać rozwiązanie optymalne, należy powtórzyć pkt. 3. W tym wypadku minimalna ilość cięć jest równa 4. W związku z tym można szukać rozwiązania optymalnego.

W tym celu wybieramy 0 tak, aby w każdej kolumnie i każdym wierszu było wybrane tylko jedno 0.

20	0	0	30
30	20	20	0
0	30	40	0
0	20	0	0

Wartość funkcji celu dla rozwiązania optymalnego:

F = 140 + 180 + 140 + 190 = 650

Odpowiedz.

Najmniejszy koszt modernizacji budynków wyniesie 650 tys. zł i osiągnie się go gdy: firma 1 wyremontuje budynek 2, firma 2 - budynek 4, firma 3 - budynek 1 i firma 4 - budynek 3.

Przykład 2

Pięciu pracowników chcemy przydzielić do pięciu czynności. Dzienny zysk z pracy tych osób przy wykonywaniu poszczególnych czynności pokazano w tabeli:

	czynność 1	czynność 2	czynność 3	czynność 4	czynność 5
prac.1	100	120	90	80	100
prac.2	80	70	90	100	110
prac.3	140	150	130	110	120
prac.4	110	80	70	80	100
prac.5	90	100	80	70	110

Proszę dobrać pracowników do czynności, tak aby łączny zysk był jak największy i aby każdy pracownik wykonywał dokładnie jedna czynność.

Model matematyczny

Jest 25 zmiennych zdefiniowanych podobnie jak w przykładzie 1.

Ograniczenia dla pracowników:

x₁₁+x₁₂+x₁₃+x₁₄+x₁₅ = 1

x₂₁+x₂₂+x₂₃+x₂₄+x₂₅ = 1

x₃₁+x₃₂+x₃₃+x₃₄+x₃₅ = 1

x₄₁+x₄₂+x₄₃+x₄₄+x₄₅ = 1

x₅₁+x₅₂+x₅₃+x₅₄+x₅₅ = 1

Ograniczenia dla czynności:

x₁₁+x₂₁+x₃₁+x₄₁+x₅₁ = 1

x₁₂+x₂₂+x₃₂+x₄₂+x₅₂ = 1

x₁₃+x₂₃+x₃₃+x₄₃+x₅₃ = 1

x₁₄+x₂₄+x₃₄+x₄₄+x₅₄ = 1

x₁₅+x₂₅+x₃₅+x₄₅+x₅₅ = 1

Funkcja celu:

F = 100x₁₁+120x₁₂+90x₁₃+80x₁₄+100x₁₅+80x₂₁+70x₂₂+90x₂₃+100x₂₄+110x₂₅+ +140x₃₁+150x₃₂+130x₃₃+110x₃₄+120x₃₅+110x₄₁+80x₄₂+70x₄₃+80x₄₄+100x₄₅+ +90x₅₁+100x₅₂+80x₅₃+70x₅₄+110x₅₅ → max

Rozwiązanie.

Metoda węgierska jest skuteczna wyłącznie dla zadań na minimum. Niezbędna jest „zmiana kierunku” zadania.

W tym celu należy znaleźć największą liczbę w tabeli i od niej odjęć wszystkie liczby:

50	30	60	70	50
70	80	60	50	40
10	0	20	40	30
40	70	80	70	50
60	50	70	80	40

Dalej postępujemy tak jak w zadaniu poprzednim.

W kolumnach:

40	30	40	30	20
60	80	40	10	10
0	0	0	0	0
30	70	60	30	20
50	50	50	40	10


W wierszach:

20	10	20	10	0
50	70	30	0	0
0	0	0	0	0
10	50	40	10	0
40	40	40	30	0

Minimalna ilość cięć wycinających wszystkie 0 to 3. Należy szukać dalej.

10	0	10	0	0
50	70	30	0	10
0	0	0	0	10
0	40	30	0	0
30	30	30	20	0

Minimalna ilość cięć wynosi 5, czyli tyle ile rząd macierzy. Spośród zer można wybrać rozwiązanie optymalne.

10	0	10	0	0
50	70	30	0	10
0	0	0	0	10
0	40	30	0	0
30	30	30	20	0

Funkcja celu:

F = 110 + 120 + 130 + 100 + 110 = 570

Odpowiedz

Maksymalny zysk w wysokości 570 zł uzyskamy gdy pracownik 1 wykona czynność 2, pracownik 2 - czynność 4, pracownik 3 - czynność 3, pracownik 4 - czynność 1 i pracownik 5 - czynność 5.

Przykład 3

Co zrobić, jeżeli z treści zadania wynika, że macierz współczynników nie jest kwadratowa?

Należy dołożyć odpowiednią ilość kolumn lub wierszy tak aby macierz współczynników była kwadratowa. Współczynniki w tych dodanych kolumnach (wierszach) wpisujemy tak aby były najgorszymi w tabelce. W zadaniu na maksimum wpisujemy 0, w zadaniu na minimum wpisujemy liczby większe od wszystkich pozostałych.

Przykład 4

Jeżeli w tabelce brakuje wartości np. pracownik nie umie wykonać określonej czynności to uzupełniamy ją analogicznie jak w przykładzie 3.

Tomasz Owczarek Strona 1 Zagadnienie przydziału.doc

---