 | Pobierz cały dokument zagadnienia.transportowe.z.zadaniami.doc Rozmiar 188 KB |
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ś.
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:
ZZT zamknięte zagadnienie transportowe,
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:
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,
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,
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: 
;
 | Pobierz cały dokument zagadnienia.transportowe.z.zadaniami.doc rozmiar 188 KB |