40688

*»» +	*21 ■*" •** ■*■*«!
*12 +	*22 + - +*R2
*1N +	X2N + ... ■+‘*RJV
C)	brzegowe:
x, ^0	/ —dostawcy R: J -

OZT można sprowadzić do ZZT poprzez:

a)    wprowadzenie fikcyjnego N+l odbiorcy, którego zapotrzebowanie B_N+_t jest równe nadwyżce podaży nad

R    ,Y

popytem: B_v+, = £A “J^B, ;

i=i    )=\

b)    wprowadzenie fikcyjnego R+l dostawcy, dysponującego podażą    która jest równa nadwyżce popytu nad

N    R

podażą: Aui =    ~ ŁA :

W rzeczywistości najczęściej zakłada się, że nadwyżka towaru pozostanie w magazynach dostawców.

Mogą być dodatkowo podane jednostkowe koszty magazynowania u poszczególnych dostawców (^ci,y₊₁) lub też zakłada się, że koszty magazynowania są pomijalnie małe w porównaniu z kosztami transportu (tj. c,_<JV+1 =0). W funkcji celu minimalizuje się łączne koszty transportu i magazynowania.

Metody stosowane do rozwiązania:

1. Kąta północno zachodniego.

Polega na wypełnieniu macierzy przewozów, rozpoczynając od lewego górnego pola (stąd nazwa). Wpisujemy w nią mniejszą z wartości A, lub B, odpowiadającej tej kratce. Następnie przesuwamy się w prawo, gdy towar od pierwszego dostawcy nie został w pełni rozdysponowany, lub w dół, gdy cała podaż tego dostawcy została rozdzielona odbiorcom.

2.    Minimalnego elementu.

Polega na rozmieszczeniu przewozów przede wszystkim na tych trasach, gdzie koszty są jak najmniejsze. Przekształcamy macierz tak aby w każdym wierszu i kolumnie było przynajmniej jedno zera Odejmujemy od elementów poszczególnych wierszy macierzy kosztów najmniejszy element znajdujący się w danym wierszu, a następnie od poszczególnych kolumn otrzymanej macierzy odejmujemy element najmniejszy w danej kolumnie. W klatki zerowe rozdysponowujemy towar.

3.    Aproksymacji Vogla (VAM):

W każdym wierszu/kolumnie szukamy najmniejszego elementu. Odejmujemy go od kolejnego najmniejszego elementu w każdym wierszu kolumnie Spośród nich wybieramy wartość maksymalną, która wskazuje, gdzie należy przesunąć środki.

Charakterystyka zagadnienia przydziału;

Istnieje możliwość obsadzenia N stanowisk roboczych przez N osób. Znane są efekty pracy i-tego pracownika na j-tym stanowisku. Efekty te mogą być oceniane pozytywnie (wydajność, wartość produkcji na jednostkę czasu) lub negatywnie (liczba braków, czas wykonywania pracy, koszty pracy). Efekty dane są macierzą A = |a_(J j Należy przydzielić pracowników do poszczególnych stanowisk tak, aby zmaksymalizować pozytywne lub zminimalizować negatywne efekty pracy całego zespołu.

Zakłada się, że każde stanowisko może być obsadzone przez jednego pracownika (tym samym każdy pracownik może pracować na jednym stanowisku).

Rozwiązaniem problemu jest kwadratowa macierz peimutacji X = [x_1; ] (i, j =1,2,..., N) , przy czym:

] 1, gdy i-ty pracownik zostame przydzielony na j-te stanowisko, xy = ^ 0 w pozostałych przypadkach

10