Klasyczne zagadnienie transportowe

Dane:

• m punktów dostawy i=1,2,...,m

• n punktów odbioru j=1,2,...,n

• zasoby produktu i-tego dostawcy S_i

• zapotrzebowanie j-tego odbiorcy D_j

• koszt przewozu każdej jednostki produktu od i-tego dostawcy do j-tego odbiorcy c_ij.

Cel:

Wybór takiego planu przewozów, który minimalizowałby łączny koszt transportu w ustalonym horyzoncie czasowym.

Model:

przy warunkach:

Tablica transportowa

Odbiorca	1	2	...	n	Podaż
Dostawca
1	c11	c12	...	c1n	S1
2	c21	c22	...	c2n	S2
...	...	...	...	...	...
m	cm1	cm2	...	cmn	Sm
Popyt	D1	D2	...	Dn

Rozwiązanie dopuszczalne modelu, gdy spełniony warunek:

W standardowym modelu transportowym wygodnie jest przyjąć, że łączna podaż równa jest łącznemu popytowi:

W tym celu tworzymy fikcyjny kierunek przewozu (fikcyjnego odbiorcę), którego zapotrzebowanie równe jest
i oznaczając go numerem n przyjmujemy
, natomiast
oznaczać będzie tę część produkcji, która pozostanie u i-tego dostawcy.

Algorytm transportowy

Wykorzystuje metodę simpleks.

Początkowe rozwiązanie wpływa na efektywność algorytmu iteracyjnego.

Metoda kąta północno-zachodniego

Wypełnianie macierzy przewozów
rozpoczyna się od klatki w lewym górnym rogu. Wpisujemy do niej mniejszą z liczb
odpowiadających tej klatce, a następnie przesuwamy się w prawo lub w dół: w prawo, gdy produkt pierwszego dostawcy nie został jeszcze całkowicie rozdysponowany, a w dół, gdy całą podaż tego dostawcy rozdzielono odbiorcom.

Metoda minimalnego elementu macierzy

Polega na rozmieszczeniu przewozów przede wszystkim na tych trasach, na których koszty są najniższe. Punktem wyjścia jest przekształcenie macierzy kosztów do takiej postaci, by w każdym wierszu i w każdej kolumnie występowało co najmniej jedno zero. Można to uzyskać odejmując 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 odejmując element najmniejszy znajdujący się w danej kolumnie. Rozmieszczenie przewozów od dowolnej klatki, w której wartość równa 0.

Jeśli uda się rozmieścić przewozy wyłącznie w klatkach, w których występują zera, to otrzymane rozwiązanie jest już optymalnym planem przewozów. Jeżeli nie, to należy je poprawiać stosując algorytm transportowy.

---