img330 (4)

Przykład 22. W pewnym dużym przedsiębiorstwie 4 sekretarki należy przydzielić do prowadzenia 4 różnych prac biurowych. Z ostatnich zapisów znany jest czas (w min) zajmujący tym sekretarkom wykonywanie poszczególnych prac, który podano w tabl. 109.

Tablica 109

Sekretarki	Czas niezbędny przy wykonywaniu pracy
	1	2	3	4
1	420	480	240	360
2	480	420	300	360
3	420	540	300	420
4	360	480	360	480

Zakładając specjalizację sekretarek, tzn. że każda z nich będzie wykonywać tylko jedną pracę, określić optymalny przydział z punktu widzenia minimalizacji łącznego czasu wykonywania prac.

Rozwiązanie. Ogólnie model powyższego zagadnienia można zapisać następująco:

4

*11+*12+*13+ *14 ~ ^ X₁j = 1,

1=1

4

*21 +*22+ *23 +*24 ⁼ X *2j ⁼

1=1

4

■*31 + *32 +-*33 + •*34 ⁼ X -*31 ⁼ 1=1

4

*41 +*42 + *43 + *44 ⁼ X *4j = h 1=1

4

*11 +*21 + *31 + *41 = X *il ⁼

> = 1

4

*12 + *22 + *32 + *42 ⁼ X *i2 ⁼

i= 1

4

*13 +*23 + *33 +*43 ⁼ X *i3 ⁼ 1> i=l

4

*14+ *24+ *34 +*44 ⁼ X *i4 ⁼

i= 1

) każda sekretarka może wykonywać tylko jedną pracę;

4

’

> każda praca może być wykonywana tylko przez jedną sekretarkę.

W funkcji celu należy zminimalizować łączny czas pracy sekretarek, czyli: Ąx_tJ) — 420x    480x j ₂ + 240x j ₃ 4- 360x j ₄ 4-

4-480x₂₁ 4-420x₂₂ 4~300x₂₃ + 360x₂₄4-4- 420x₃₁ 4- 540x₃₂ + 300x₃₃ + 420x₃₄ 4-+ 360x₄₁ +480x₄₂ 4- 360x₄₃ 4- 480x₄₄ -> min.

Model powyższy jest szczególnym przypadkiem zadań PL - szczególnym, gdyż zmienne decyzyjne przyjmują tylko dwie wartości: jeden lub zero. x_ij = 1 oznacza przydzielenie j-ej pracy i-tej sekretarce, x_y = 0 oznacza, że i-ta sekretarka nie będzie wykonywać j-ej pracy.

Również ten typ zagadnień może być rozwiązywany za pomocą algorytmu simpleks. Obliczenia są jednak bardzo pracochłonne, gdyż należałoby rozważyć wszystkie możliwe kombinacje wartości x_u, spełniające warunki ograniczające. Liczba tych kombinacji jest równa N\ (przy założeniu, że macierz A jest macierzą kwadratową, a więc P = N).

Istnieje jednak bardzo prosty algorytm (zwany często algorytmem węgierskim, oparty jest bowiem na twierdzeniu węgierskiego matematyka Denesa Ko-niga), który pozwala na stosunkowo szybkie uzyskanie rozwiązania optymalnego.

Punkt wyjścia (krok 1) omawianego algorytmu stanowi takie przekształcenie macierzy kosztów A = [a_y], aby w każdym wierszu i w każdej kolumnie występowało przynajmniej jedno zero. W tym celu postępuje się tak jak w metodzie minimalnego elementu macierzy, tzn. od każdego wiersza macierzy współczynników funkcji celu odejmujemy jego najmniejszy element i - jeżeli trzeba¹ - od każdej kolumny tak przekształconej macierzy odejmujemy jej najmniejszy element.

Kolejne, dalsze kroki składające się na algorytm węgierski, to:

2.    Skreślenie w przekształconej macierzy współczynników funkcji celu wierszy i kolumn zawierających zera możliwie najmniejszą liczbą linii. Jeżeli najmniejsza liczba linii niezbędnych do pokrycia wszystkich zer jest równa wymiarowi macierzy (N), to otrzymane rozwiązanie jest rozwiązaniem optymalnym.

3.    Ustalenie rozwiązania optymalnego, polegającego na takiej konstrukcji macierzy [x_y], aby jedynki znalazły się tylko na tych polach (w tych klatkach), na których w przekształconej macierzy współczynników funkcji celu występują zera (przy tym trzeba pamiętać, aby w każdym wierszu i w każdej kolumnie wystąpiła tylko jedna jedynka).

4.    Jeżeli liczba skreśleń jest mniejsza od wymiaru macierzy (N), w bieżącej (przekształconej) macierzy kosztów należy znaleźć najmniejszy nie skreślony element i ten element:

117

1

Może się zdarzyć, iż po odjęciu najmniejszych elementów wierszy również w każdej kolumnie występuje już zero.