3848093749

9

1.1. Zagadnienie transportowe

całkowitymi, to każde rozwiązanie (a więc również optymalne) jest utworzone z liczb całkowitych.

Pozostaje nam zatem zająć się metodą wyznaczania tego rozwiązania. Pamiętamy, że zadanie transportowe jest szczególną postacią zadania programowania liniowego, z zatem można je rozwiązać metodą sympleks, ale w kolejnym punkcie poznamy znacznie sprawniejszy algorytm transportowy.

1.1.4. Wyznaczanie rozwiązań początkowych

Znalezienie rozwiązania początkowego zbilansowanego zadania transportowego jest łatwe. Pokażemy trzy sposoby wyznaczania rozwiązań początkowych zadania transportowego: metodę północno-zachodniego narożnika, metodę najmniejszego elementu macierzy oraz metodę Vogel’a zwaną też metodą VAM (Vogel Approximation Method). W każdej z tych metod wybieramy element macierzy i na trasie wskazanej przez ten element przesyłamy maksymalną dopuszczalną ilość towaru. Następnie usuwamy wiersz lub kolumnę w której popyt lub podaż zostały wyzerowane i wybieramy następny element. Postępujemy w ten sposób aż do wykreślenia wszystkich wierszy i kolumn. Metody różnią się jedynie regułą wyboru kolejnych elementów macierzy.

Metoda północno-zachodniego narożnika

W metodzie północno-zachodniego narożnika jako następny wybieramy element znajdujący się w pierwszym wierszu i pierwszej kolumnie zredukowanej macierzy.

Przebieg obliczeń dla danych z tablicy 1.1 jest następujący. Wybieramy element a\\ macierzy kosztów i określamy maksymalną ilość nawozu, którą można przesłać tą trasą. Jest to minimum z wartości a\ i b\ (ogólnie ai i bj), a więc 5000. Przyjmujemy zatem x\\ — 5000 oraz x\2 — #13 = #14 = 0, zmniejszamy ilość pozostałą do wysłania do pierwszego odbiorcy (6000-5000) i wykreślamy pierwszy wiersz z macierzy kosztów. Jako kolejny wybieramy element znajdujący się w pierwszym wierszu i pierwszej kolumnie tak zredukowanej macierzy, czyli 021- Na tej trasie pozostaje do przesłania 1000 kg nawozu, przyjmujemy zatem X2i = 1000, #31 = 0, zmniejszamy zapas u drugiego dostawcy (6000-1000) i wykreślamy pierwszą kolumnę. Następnym elementem jest a22- Na tej trasie przesyłamy 4000 kg nawozu, X22 = 4000,^32 = 0. Kolejne kroki podsumowano w tablicy 1.2.