Mamy n punktów wysyłających towar i t punktów odbierających. Istnieje droga od każdego dostawcy do każdego odbiorcy i znany jest koszt transportu jednostki towaru.

Jak zorganizować transport, żeby koszt był minimalny?

Zapiszmy dane w postaci tabeli:

O1O2⋯⋯OtpodażD1a1,1a1,2⋯⋯a1,tb1D2a2,1a2,2⋯⋯a2,tb2⋮⋮⋮⋱⋮⋮Dnan,1an,2⋯⋯an,tbnpopytc1c2⋯⋯ct

Wprowadźmy zmienne xi,j opisujące ilość towaru przewożonego od i - tego dostawcy do j - tego odbiorcy.

Niech ai⁢j oznacza koszt przewiezienia jednostki towaru.

Jako funkcję celu przyjmijmy: m⁢i⁢n⁢⁢x0⁢=∑i=1n∑j=1tai,j⁢xi,j

Zadanie transportowe nazywamy zbilansowanym gdy podaż = popyt,

czyli ∑i=1n⁢bi⁢=⁢∑j=1t⁢cj.

W przypadku zbilansowanym obszar dopuszczalny opisany jest następującym układem równań i nierówności:

∑j=1tx1,j=b1, - pierwszy dostawca wysyła cały towar,

∑j=1tx2,j=b2, - drugi dostawca wysyła cały towar,

⋮

∑j=1tx1,j=bn, - n-ty dostawca wysyła cały towar,

∑i=ntx1,j=c1, - pierwszy odbiorca dostaje cały towar,

∑i=ntx2,j=c2, - drugi odbiorca dostaje cały towar,

⋮

∑i=ntx1,j=ct, - t-ty odbiorca dostaje cały towar,

Ponadto nie można przewozić ujemnej liczby towarów - a więc:

.

Czasami towary są podzielne jak prąd czy woda, ale zwykle dodajemy warunki:

∀i,j⁢xi,j∈Z

Jeśli dodamy do siebie równania opisujące popyt otrzymamy

∑i=1n∑j=1txi,j=∑i=1nbi

Analogicznie jeśli dodamy do siebie równania opisujące podaż otrzymamy

∑j=1t∑i=1nxi,j=∑j=1tci.

Zatem dla zadania niezbilansowanego układ równań opisujący obszar dopuszczalny jest sprzeczny zaś dla zadania zbilansowanego układ równań opisujący obszar dopuszczalny jest zależny. Można pokazać, że rząd macierzy układu jest równy n+t-1 a więc tyle musi być zmiennych bazowych.

Zakładamy, że zagadnienie jest zbilansowane.

Zadanie opisują dwie tablice mające tyle wierszy ilu jest dostawców i tyle kolumn ilu jest odbiorców plus wiersze i kolumny nagłówków.

W pierwszej zapisujemy koszty lub koszty zredukowane - czyli to co jest nad kreską w tablicy sympleks.

Druga tablica opisuje przewozy - dla zmiennej bazowej xi,j wstawiamy ilość towaru przewożonego od i - tego dostawcy do j - tego odbiorcy zaś dla zmiennych niebazowych krzyżyk x. Ta tablica opisuje to co jest w tablicy sympleks z prawej strony kreski i umiejscowienie zmiennych bazowych jak w zrewidowanej metodzie sympleks.

b) Metoda minimalnych kosztów.

Ta metoda różni się od poprzedniej tym, że zamiast wierzchołka północno - zachodniego wybieramy miejsce tabeli o minimalnym koszcie.

3) Wędrowanie między wierzchołkami.

3a) Wybieramy drogę o ujemnym koszcie - w przykładzie drogę wyznaczoną zmienną x4,2 i w tablicy przewozy do X dopisujemy +Δ.

3b) Wpisując przy odpowiednich zmiennych bazowych ±Δ budujemy cykl tak by popyt i podaż z uwzględnieniem Δ nie zmieniła się.

3c) Wybieramy maksymalną Δ=m⁢i⁢n⁢xi,j⁢|Δ⁢ występuje ze znakiem -

4) Podstawiamy wyliczoną wartość Δ i usuwamy z bazy jedną ze zmiennych na której ilość przewożonego towaru zmniejszyliśmy do 0.

Transport niezbilansowany

W przypadku gdy podaż przewyższa popyt zadanie można doprowadzić do zbilansowanego wprowadzając sztucznego odbiorcę o popycie równoważącym różnicę i kosztach przewozów 0. Po wyliczeniu optymalnego przewozu mówimy, że towary wysłane do sztucznego odbiorcy zostają u dostawców.

W przypadku gdy popyt przewyższa podaż, analogicznie, zadanie można doprowadzić do zbilansowanego wprowadzając sztucznego dostawcę o podaży równoważącym różnicę i kosztach przewozów 0.

Jako literaturę uzupełniającą do tego tematu polecamy książki [10] i [6].