136 137

136 Zadanie transportowe i problem komiwojażera

znacznie większej liczby iteracji. Do drugiej grupy metod wykorzystujących informacje o jednostkowych kosztach transportu należą: metoda minimalnego elementu macierzy kosztów oraz metoda VAM. Jak jednak zobaczymy w dalszej części rozdziału, nie ma możliwości jednoznacznego wskazania, która z tych metod jest najlepsza.

W rozdziale tym zajmiemy się rozwiązywaniem zadania transportowego oraz wybranymi jego zastosowaniami. Zadanie transportowe przedstawimy najpierw jako zadanie programowania liniowego, omówimy jego własności i zbudujemy zadanie dualne do zbilansowanego zadania transportowego, w którym łączna podaż dostawców jest równa łącznemu zapotrzebowaniu odbiorców. Pokażemy, w jaki sposób można skonstruować pierwsze rozwiązanie bazowe. Na początku opiszemy najbardziej rekomendowaną metodę minimalnego elementu, a następnie metodę VAM i metodę kąta północno-zachodniego. Z kolei omówimy metodę potencjałów. Pokażemy związek kryterium optymalności z ograniczeniem zadania dualnego do zadania transportowego, a także opiszemy kryterium wejścia nowej zmiennej do bazy, kryterium wyjścia dla zmiennej opuszczającej bazę oraz przejście do kolejnego rozwiązania bazowego.

Zajmiemy się dokładniej zagadnieniem degeneracji, które występuje wtedy, kiedy w rozwiązaniu bazowym, rozpatrywanym w pewnym etapie postępowania, jedna lub więcej zmiennych bazowych przyjmuje wartość zero¹. W przypadku pojawienia się degeneracji należy pamiętać, które ze zmiennych przyjmujących wartość zero są zmiennymi bazowymi, a które — niebazowymi.

Wśród zadań transportowych występują często niezbilansowane zadania transportowe, w których łączna podaż dostawców nie jest równa łącznemu popytowi odbiorców. Pokażemy, w jaki sposób należy bilansować zadania transportowe zarówno w przypadku przewagi podaży nad popytem, jak również w sytuacji przeciwnej. Jest to istotne, ponieważ metodę potencjałów można stosować również do zadań niezbilansowanych po uprzednim ich zbilansowaniu.

Zajmiemy się również problemem komiwojażera, który można sformułować następująco: mamy n miast, które należy odwiedzić w dowolnej kolejności, rozpoczynając podróż z miasta o numerze 1 i wracając do niego, przy czym każde z miast można odwiedzić dokładnie jeden raz. Znając wszystkie odległości między miastami, należy znaleźć trasę przejazdu o minimalnej długości.

Pokażemy, że odpowiednio sformułowane zadanie transportowe stanowi dolne przybliżenie zagadnienia komiwojażera. Pokażemy również, że można uzyskać dobre przybliżenie rozwiązania optymalnego za pomocą algorytmu genetycznego.

Zagadnienie transportowe, jak i problem komiwojażera, mają wiele zastosowań zarówno w dziedzinie transportu, jak również do rozwiązywania różnorodnych problemów nie związanych z transportem. Pokażemy przykłady zadań transpor-

' Problem degeneracji może pojawić się również, w zadaniu programowania liniowego, ale występuje sporadycznie. W zadaniach transportowych jest to przypadek częstszy i przysparza studiują-cym sporo kłopotu.

towych, omawiając zagadnienie transportowo-produkcyjne, zagadnienie minimalizacji pustych przebiegów oraz zagadnienie przydziału. Do rozwiązywania zadań wykorzystamy program TRANS.EXE.

3.2. Zadanie transportowe i jego własności

3.2.1. Zadanie transportowe

w ujęciu programowania liniowego

Zilustrujemy najpierw możliwość przedstawienia zadania transportowego jako zadania programowania liniowego.

Przykład 3.1

Firma ma zakłady wytwórcze w miejscowościach D,, D₂ i D, oraz ośrodki dystrybucji w miejscowościach O,, 0₂ i O_y Możliwości produkcyjne zakładów wynoszą, odpowiednio, 20, 20 i 30 jednostek, natomiast prognozy popytu w centrach, odpowiednio, 10, 15 i 45 jednostek. Jednostkowe koszty transportu przedstawione są w tablicy 3.1.

Tablica 3.1

Miejscowość	Ośrodek dystrybucji
	o,	02	O,
O,	1	4	1
D2	3	5	11
D,	6	7	9

Należy zapisać zadanie optymalizacyjne, pozwalające na znalezienie takiego planu przewozów, by przy uwzględnieniu możliwości produkcyjnych zakładów oraz przewidywanego popytu w ośrodkach dystrybucji zminimalizować łączne koszty transportu (które są proporcjonalne do ilości przewożonego towaru).

Rozpatrywane zadanie jest przykładem problemu transportowego. Przedstawiono je schematycznie na rys. 3.1.

Mamy trzech dostawców, oznaczonych jako D,, D₂ i D₃; są nimi zakłady produkcyjne firmy. Mamy również trzech odbiorców, oznaczonych jako O,, 0₂ i O i, są to ośrodki dystrybucji. Zadanie jest zbilansowane, gdyż łączna podaż, równa 20 + 20 + 30 = 70, jest równa łącznemu popytowi, którego wielkość wynosi 10+15 + 45 = 70.