PROBLEMY TRANSPORTOWE I PRZYDZIAŁU

Zagadnienie transportowe zostało po raz pierwszy sformułowane przez F. L. Hitchcocka w r. 1941, jako sposób zaplanowania przewozu jednorodnego produktu od określonej liczby dostawców do określonej liczby odbiorców. Zagadnienie transportowe jest szczególnym przypadkiem programowania liniowego – można je rozwiązać za pomocą metody simpleks. Jednak dzięki charakterystycznej strukturze warunków ograniczających, w zagadnieniu transportowym opracowano metody pozwalające otrzymać rozwiązanie w sposób bardziej efektywny.

Opracowany w roku 1951 przez G.B. Dantziga schemat metody rozwiązania zagadnienia transportowego nazywany algorytmem transportowym, pozostał w użyciu do dziś[1].

Charakterystyka zagadnienia transportowego:

R dostawców pewnego jednorodnego towaru, z których każdy dysponuje Ai (i=1, 2, ...., R) jednostkami tego towaru, zaopatruje N odbiorców. Zapotrzebowanie każdego z odbiorców wynosi Bj (j=1, 2, ...., N). Każdy z dostawców może zaopatrywać dowolnego odbiorcę i odwrotnie – każdy odbiorca może otrzymać towar od dowolnego dostawcy. Dodatkowo mamy podane koszty jednostkowe transportu od i-tego dostawcy do j-tego odbiorcy Cij (i=1, 2, ..., R  j=1, 2, ..., N). Zamiast kosztów transportu mogą być podane odległości lub czas transportu (zwłaszcza w przypadku towarów szybko psujących się). Wówczas mówimy o zagadnieniach transportowych z kryterium kosztów, odległości lub czasu.

Należy opracować plan przewozu towaru między dostawcami, a odbiorcami tak, aby łączne koszty transportu były możliwie najniższe. Plan taki ma określić, ile towaru powinien dostarczyć i-ty dostawca j-temu odbiorcy.

Zakłada się, że całkowita łączna podaż dostawców powinna być nie mniejsza niż łączne zapotrzebowanie odbiorców: , jeżeli:

1.                   ZZT              zamknięte zagadnienie transportowe,

2.                   OZT              otwarte zagadnienie transportowe.

Zmienne decyzyjne              xij              ilość przewiezionego towaru od i-tego dostawcy do j-tego odbiorcy, Cij koszty przewozu tego towaru.

Funkcja celu                            (minimalizacja łącznych kosztów transportu od wszystkich dostawców do wszystkich odbiorców).

Warunki strukturalne:

a)                  dla dostawców (i-ty dostawca ma dostarczyć wszystkim odbiorcom tyle towaru, ile posiada; warunków tych jest tyle, ilu jest dostawców, czyli N) :

sumuję po wierszach,

b)                 dla odbiorców (j-ty odbiorca ma otrzymać od wszystkich dostawców tyle towaru, ile potrzebuje; warunków tego typu jest tyle ilu odbiorców, czyli R) :

sumuje po kolumnach,

c)                  brzegowe:

OZT można sprowadzić do ZZT poprzez:

a) wprowadzenie fikcyjnego N+1 odbiorcy, którego zapotrzebowanie jest równe nadwyżce podaży nad popytem: ;

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

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 () lub też zakłada się, że koszty magazynowania są pomijalnie małe w porównaniu z kosztami transportu (tj. ). 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 Ai lub Bj 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 zero. 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ą

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 permutacji , przy czym:

               1, gdy i-ty pracownik zostanie przydzielony na j-te stanowisko,

=       0 w pozostałych przypadkach.

Zdefiniowana jw. macierz X nazywana jest macierzą przydziału.

Liniowy zapis zagadnienia przydziału:

   - każde stanowisko może być obsadzone przez jednego pracownika,

  - każdy pracownik może zostać przydzielony do jednego stanowiska.

lub,                             .

Rozwiązanie optymalne można uzyskać za pomocą algorytmu węgierskiego:

1.      Przekształcić macierz współczynników funkcji celu tak, aby w każdym wierszu i w każdej kolumnie występowało co najmniej jedno zero.

2.      W przekształconej macierzy współczynników funkcji celu skreślić wiersze i kolumny zawierające zera za pomocą możliwie najmniejszej liczby linii (poziomych i pionowych). Jeżeli liczba linii potrzebnych do skreślenia wszystkich zer jest równa wymiarowi macierzy czyli N, można wyznaczać rozwiązanie optymalne – przejść do punktu 3. Jeżeli liczba ta jest mniejsza od N – przejść do punktu 4.

3.      Ustalić rozwiązanie optymalne, polegające na takiej konstrukcji macierzy , aby jedynki znalazły się tylko w tych klatkach, w których w przekształconej macierzy współczynników funkcji celu występują zera (w każdym wierszu i w każdej kolumnie może wystąpić tylko jedna jedynka).

4.      Jeżeli liczba linii pokrywających zera jest mniejsza od wymiaru macierzy (N), w przekształconej macierzy należy znaleźć najmniejszy nie skreślony element a następnie:

a)            odjąć go od elementów nie skreślonych,

b)            dodać do elementów podwójnie skreślonych.

Elementy skreślone jedną linią pozostają bez zmian.

Następnie wrócić do punktu 2 i powtórzyć procedurę aż do uzyskania rozwiązania optymalnego.

UWAGI:

1.      Metoda powyższa ma zastosowanie tylko do problemów minimalizacji. Aby rozwiązać problem maksymalizacji, należy macierz współczynników funkcji celu przekształcić tak, aby jej elementy miały przeciwne znaczenie, np. odejmując od największego elementu wszystkie pozostałe.

2.      Powyższy algorytm zakłada, że liczba stanowisk do obsady jest równa liczbie pracowników, czyli że macierz A jest kwadratowa. W przypadku gdy tak nie jest – należy dopisać dodatkowy wiersz lub kolumnę (fikcyjnego wykonawcę lub fikcyjne zadanie), których elementy .

3.      Czasem zdarza się, ze pewne przydziały są niedopuszczalne (tzn. określone elementy macierzy X z założenia są równe 0). Wówczas do macierzy współczynników funkcji celu w klatkach gdzie musi być spełniony warunek , wprowadza się bardzo dużą liczbę, np. M – taką, że odjęcie od niej jakiejkolwiek liczby praktycznie nie zmieni jej wartości.

Twierdzenie.

Jeżeli uda się rozdysponować wszystkie środki, odbiorcy otrzymają tyle ile wynosiło ich zapotrzebowanie, a dostawcy oddadzą cały towar, to takie rozwiązanie dopuszczalne jest zarazem rozwiązaniem optymalnym.

Zadanie 1

Trzy magazyny M1 M2 M3 zaopatrują w mąkę cztery piekarnie P1 P2 P3 P4. Jednostkowe koszty transportu (w złotych za tonę), oferowane miesięczne wielkości dostaw Ai (w tonach) oraz miesięczne zapotrzebowanie piekarń Bj (w tonach) podano w tablicy: