49509 Transport14

Przykład 23. Przedsiębiorstwo Exbud ma możliwość wysiania 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 / 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

■0

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ć:

Z *ij = !> '

j= i

I ^X2j = 1>

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

7

Z ^X3J —

J- 1

4

Z ^XAJ ^m 1 •    t

J- I

X*n I.

/- |

1^2-1.

na każdy kontrakt może być przydzielony tylko jeden pracownik.

i= 1

4

Z *i3 = 1,

1=1

Z *i4 = l

i= 1 x_tJ> 0 dla i= 1,2, 3,4; j = 1, 2, 3,4,

= 7x₁₁ + 10x₁₂ + llx₁₃ + 9x₁₄ +

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

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

+ 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:

"l 0 0 0~

0 0 0 1

V* —

0 0 10’

0 10 0

czyli pracownika A należy wysłać na pierwszy kontrakt, pracownika B na czwarty i pracownika (' na trzeci. Natomiast na drugi kontrakt powinien pojechać pracownik spoza liabudu. Łączny zysk przedsiębiorstwa wyniesie miesięcznie (10 I I / ( H) 100    15' 100 - 3 500 dolarów.

IJI