img332 (4)

Przykład 23. Przedsiębiorstwo Exbud ma możliwość wysłania pracowników w charakterze kierowników na cztery budowy eksportowe. Przedsiębiorstwo to zatrudnia aktualnie trzech odpowiednich specjalistów: A, B i C, a ponieważ dysponują oni różnym doświadczeniem zawodowym, zyski dla firmy są zróżnicowane w zależności od przydziału pracowników na poszczególne kontrakty, co ilustruje tabl. 110 (zyski podano w setkach dolarów miesięcznie).

Tablica 110

Pracownicy	Kontrakty
	1	2	3	4
A	10	7	6	8
B	12	14	10	17
C	3	5	8	4

Zakładając, że na jeden z kontraktów trzeba będzie zatrudnić pracownika z zewnątrz (zyski z tego dla Exbudu będą równe zeru), należy optymalnie przydzielić pracowników na poszczególne kontrakty z punktu widzenia maksymalizacji zysku przedsiębiorstwa.

Rozwiązanie. Przed przystąpieniem do budowy modelu należy dopisać czwarty wiersz z elementami równymi zeru, a następnie macierz zysków przekształcić do takiej postaci, która będzie minimalizowana. Przekształcenia dokonano przez odjęcie od największego elementu macierzy (a₂₄ = 17) wszystkich pozostałych jej elementów. W rezultacie otrzymano macierz:

7	10	11	9
5	3	7	0
14	12	9	13
17	17	17	17

Nietrudno zauważyć, że elementy tej macierzy można interpretować jako „straty” firmy związane z przydziałem pracowników na poszczególne kontrakty w stosunku do największego zysku, jaki jest możliwy do osiągnięcia.

Model zagadnienia będzie miał postać:

4

każdy pracownik może być przydzielony tylko na jeden z kontraktów;

7=1

4

X-,!

7=1

I *3j

1,    '

1,

1,

4

1*4;

7=1

X *n = 1.    '

4

Z *i2 = 1,

i = 1

4

i = 1

4

Z *i4 = 1.

i= 1

na każdy kontrakt może być przydzielony

tylko jeden pracownik.

x_tj ^ 0 dla i = 1,2, 3,4; y = 1, 2, 3, 4, Ąx_ij) = 7x₁₁ + 10x₁₂ + llx₁₃ + 9x₁₄ +

+ 5x₂₁ + 3x₂₂+ 7x₂₃+ 0x₂₄ +

+ 14x₃₁ + 12x₃₂+ 9x₃₃ + 13x₃₄ +

4- 17x₄₁ + 17x₄₂ + 17x₄₃ + 17x₄₄ -*■ min.

Do rozwiązania tak sformułowanego zadania można już bezpośrednio zastosować algorytm węgierski. Po odjęciu najmniejszych elementów w poszczególnych wierszach otrzymujemy macierz:

0 3 4 2 5 3 7 0 5 3 0 4 0 0 0 0

w której zera występują już także we wszystkich kolumnach i, jak łatwo zauważyć, od razu możliwe jest rozmieszczenie jedynek w klatkach z zerami (najmniejsza liczba linii pokrywających wszystkie zera jest równa 4). Rozwiązanie optymalne jest następujące:

X* =

10 0 0 0 0 0 1 0 0 10 0 10 0

czyli pracownika A należy wysłać na pierwszy kontrakt, pracownika B - na czwarty i pracownika C-na trzeci. Natomiast na drugi kontrakt powinien pojechać pracownik spoza Exbudu. Łączny zysk przedsiębiorstwa wyniesie miesięcznie (10 -I-17 + 8) • 100 = 35 • 100 = 3 500 dolarów.

121