Wykład 4

Jednym z najbardziej interesujących szczególnych przypadków zagadnień optymalizacji liniowej jest tzw. zadanie transportowe ZT. 

ZT zostało sformułowane i rozwiązane w roku 1934 przez L. Kantorowicza i było jednym z pierwszych rozwiązanych problemów programowania liniowego. W roku 1941 angielski badacz Hitchcock opublikował wersję zadania i algorytmu, znanego dziś pod nazwą „klasycznego zadania transportowego”. W ostatnich latach opublikowano wiele uogólnień tego problemu, a także efektywnych algorytmów obliczeniowych.

Sformułowanie zadania transportowego

Mamy m dostawców  

i  n  odbiorców     tego samego produktu.

- podaż  i-tego dostawcy, czyli liczba jednostek produktu, jaką dysponuje i-ty dostawca, przy czym i=1,2,....,m,

- popyt j-tego odbiorcy, czyli liczba jednostek produktu, jaką chce otrzymać j-ty odbiorca, przy czy j=1,2,....,n.

jednostkowe koszty transportu   , i=1,2,....,m,   j=1,2,....,n, tzn. koszty transportu jednostki produktu od i-tego dostawcy do j-tego odbiorcy. 

Jeżeli łączna (całkowita) podaż wszystkich dostawców jest równa łącznemu (całkowitemu popytowi) zapotrzebowaniu wszystkich odbiorców czyli spełniony jest warunek

to zagadnienie transportowe nazywamy zadaniem zbilansowanym.

Poszukiwany jest taki plan przewozów, który zapewnia każdemu odbiorcy otrzymanie żądanej ilości produktu oraz każdemu dostawcy całkowity zbyt produktu i dla którego łączny koszt transportu będzie minimalny.

Informacje dotyczące zadania wygodnie jest umieścić w tabeli:

Model matematyczny

    -  liczba jednostek produktu przewieziona od i-tego dostawcy do  j-tego odbiorcy,  koszt transportu na tej trasie wynosi         ,

łączny koszt transportu tworzy funkcję celu, którą należy zminimalizować:

Ograniczenia:

  i-ty dostawca, który dysponuje  jednostkami produktu, może dostarczyć   jednostek produktu pierwszemu odbiorcy,  jednostki drugiemu odbiorcy itd., czyli:

...