Zagadnienie transportowe (zwane też problemem transportowym bądź zadaniem transportowym) za zadanie obliczenie najkorzystniejszego rozplanowania wielkości łańcucha dostaw między dostawców i odbiorców. Jego celem jest zazwyczaj minimalizacja kosztów transportu, a zastosowanie znalazło przy projektowaniu bądź optymalizacji sieci dystrybucji w przedsiębiorstwie [1]. Z zagadnieniem transportowym wiąże się pojęcia rozwiązania dopuszczalnego- jest to rozwiązanie które w wyniku daje niski koszt ale jest możliwość w prosty sposób uzyskania kosztu niższego [4]. Jak widać więc, jest ono doraźne, pośrednie w uzyskaniu rozwiązania optymalnego.
By znaleźć rozwiązanie zadania transportowego, należy kierować się następującym schematem [2]:
Korzystając z jednej z metod (metoda kąta pn.- zach., najmniejszego elementu macierzy bądź VAM) należy znaleźć rozwiązanie dopuszczalne.
Obliczyć koszt całkowity.
Sprawdzić, czy rozwiązanie posiada odpowiednią ilość baz (jest zdegenerowane).
Jeżeli nie, należy zastosować metodę e-perturbacji.
Przy pomocy metody potencjałów należy sprawdzić, czy rozwiązanie jest optymalne.
Jeżeli rozwiązanie nie jest dopuszczalne, należy stworzyć cykl i zbudować nowe rozwiązanie dopuszczalne.
Powtarzać kroki 5 i 6 aż do momentu znalezienia dopuszczalnego rozwiązania.
2. Metody minimalizacji kosztów transportu
W rozwiązywaniu zagadnień transportowych, można się spotkać z różnymi metodami rozdziału ładunku. Przy zastosowaniu każdej z metod zupełnie inny będzie rozkład ładunku oraz koszty- co powoduje, że nie każda z tych metod powoli na optymalizację kosztów transportu. W dalszej części projektu, do rozwiązania zadania zostały użyte trzy metody minimalizacji kosztów transportu: metoda kąta północno-zachodniego, metoda minimalnego kosztu macierzy oraz, jako metoda gwarantująca najlepsze rozwiązanie, optymalizacja kosztów przy pomocy programu MS Excel- Solver.
Jest najprostszą i najszybszą metodą minimalizacji kosztów transportu. Niestety, nie przekłada się to na uzyskiwane koszty- są znacznie wyższe, niż przy zastosowaniu innych metod [4]. Zakłada ona rozdział ładunku w macierzy przewozów rozpoczynając od lewego górnego rogu (północny- zachód), a następnie- zależnie czy rozdzielono cały ładunek dostawcy- należy przesuwać się w dół bądź w prawo (jeśli nie wykorzystaliśmy całego ładunku od dostawcy) [3].
Rozpatrzmy przypadek, w którym ładunek od trzech odbiorców musimy rozdzielić między czterech odbiorców. Macierz początkowa została przedstawiona w tabeli 2.1.
Tab. 2.1. Macierz początkowa
Odbiorcy Dostawcy |
O1 | O2 | O3 | O4 | ai |
|---|---|---|---|---|---|
| D1 | 3 | 3 | 8 | 9 | 100 |
| D2 | 2 | 4 | 10 | 5 | 200 |
| D3 | 5 | 1 | 2 | 7 | 150 |
| bj | 50 | 100 | 150 | 150 | 450 |
Zgodnie z założeniami, rozpoczynamy rozdział ładunku od lewego górnego rogu- w tym przypadku, będzie to Odbiorca 1 i Dostawca 1 (tabela 2.2.).
Tab. 2.2. Początek rozkładu ładunku
Odbiorcy Dostawcy |
O1 | O2 | O3 | O4 | ai |
|---|---|---|---|---|---|
| D1 | 50 | 100 | |||
| D2 | 200 | ||||
| D3 | 150 | ||||
| bj | 50 | 100 | 150 | 150 | 450 |
Popyt odbiorcy pierwszego został w pełni zapełniony, podaż pierwszego dostawcy nie została w pełni wykorzystana. Dlatego w kolejnym kroku ładunek przydzielamy kolejnemu odbiorcy (wykonujemy krok w lewo). Następnie by zaspokoić w pełni popyt tego odbiorcy, przydzielamy mu ładunek od drugiego dostawcy (wykonujemy krok o jedno pole niżej). Według tego schematu przydzielamy ładunek reszcie odbiorców (tabela 2.3.).
Tab. 2.3. Przyporządkowanie ładunku kolejnym odbiorcom
Odbiorcy Dostawcy |
O1 | O2 | O3 | O4 | ai |
|---|---|---|---|---|---|
| D1 | 50 | 50 | 100 | ||
| D2 | 50 | 150 | 200 | ||
| D3 | 150 | 150 | |||
| bj | 50 | 100 | 150 | 150 | 450 |
Drugą metodą według której można dokonać optymalizacji kosztów jest metoda najmniejszego elementu macierzy. Wymaga większej ilości czasu niż zastosowanie metody kąta północno-zachodniego, jednak wiąże się to z redukcją kosztów (choć nie zawsze koszty uzyskane tą metodą są najmniejsze). Polega ona na rozdziale ładunku począwszy od najmniejszego elementu macierzy kosztów [4].
Ponownie rozpatrzmy przypadek, w którym ładunek od trzech odbiorców musimy rozdzielić między czterech odbiorców. Macierz początkowa pozostaje bez zmian w stosunku do poprzedniego przypadku (tabela 2.1.). Jak widać, najmniejszy element macierzy znajduje się przy drugim odbiorcy i trzecim dostawcy (element macierzy równy jeden). Rozkład ładunku rozpoczynamy od tego miejsca (tabela 2.4.) [3].
Tab. 2.4. Rozkład ładunku w najmniejszym elemencie macierzy
Odbiorcy Dostawcy |
O1 | O2 | O3 | O4 | ai |
|---|---|---|---|---|---|
| D1 | 100 | ||||
| D2 | 200 | ||||
| D3 | 100 | 150 | |||
| bj | 50 | 100 | 150 | 150 | 450 |
Zapotrzebowanie dostawcy wynosiło 100, podaż dostawcy 150. Dlatego drugiego odbiorcy przy dalszym rozkładzie nie uwzględniamy. Szukamy natomiast wśród pozostałych odbiorców najmniejszego elementu macierzy. Znajdujemy go w dwóch różnych miejscach- u dostawcy drugiego i odbiorcy pierwszego, oraz u trzeciego dostawcy i trzeciego odbiorcy. W tych dwóch miejscach przydzielamy ładunek (tabela 2.5.).
Tab. 2.5. Dalszy etap rozkładu ładunku
Odbiorcy Dostawcy |
O1 | O2 | O3 | O4 | ai |
|---|---|---|---|---|---|
| D1 | -- | 100 | |||
| D2 | 50 | -- | 200 | ||
| D3 | 100 | 50 | 150 | ||
| bj | 50 | 100 | 150 | 150 | 450 |
W kolejnych etapach szukamy ponownie najmniejszych elementów macierzy, wykreślając uprzednio kolumny bądź wiersze w których popyt lub podaż jest w pełni wykorzystana. Pełny rozkład ładunku według tej metody został przedstawiony w tabeli 2.6.
Tab. 2.6. Rozkład ładunku metodą najmniejszego elementu macierzy
Odbiorcy Dostawcy |
O1 | O2 | O3 | O4 | ai |
|---|---|---|---|---|---|
| D1 | -- | -- | 100 | -- | 100 |
| D2 | 50 | -- | -- | 150 | 200 |
| D3 | -- | 100 | 50 | -- | 150 |
| bj | 50 | 100 | 150 | 150 | 450 |
Dodatek Solver programu MS Excel jest narzędziem umożliwiającym znalezienie optymalnego rozwiązania dla wszelakiego rodzaju problemów decyzyjnych. Wykorzystuje on w tym celu metody znane z badań operacyjnych. By rozwiązać zagadnienie transportowe, musimy najpierw w programie MS Excel stworzyć macierz kosztów. Następnym krokiem, jest sformułowanie odpowiednich założeń ograniczających- bez nich program może nieprawidłowo rozdzielić ładunek (np. rozdzielając więcej niż wynosi podaż dostawcy). Dlatego określamy następujące ograniczenia:
Suma dostaw każdego magazynu do każdego sklepu musi wyczerpać zapas,
Suma dostaw towarów otrzymanych przez każdego odbiorcę musi być równa całkowitemu zapotrzebowaniu,
Całkowite koszty transportu muszą być jak najmniejsze (funkcja celu).
Po sformułowaniu założeń, należy stworzyć macierz, w której ładunek zostanie rozdzielony przy pomocy programu. Wstawiamy następnie dowolne wartości dostaw (i tak ulegną później zmianie) i obliczamy sumy wierszy (dostaw z magazynów) i sumy kolumn (towar otrzymany przez sklepy). Następnie ilustrujemy wcześniej sformułowane warunki ograniczające oraz przy pomocy funkcji sumy iloczynów, zapisujemy formułę będącą funkcją celu . Ostatnim krokiem jest uruchomienie dodatku Solver, a następnie wprowadzenie wcześniej zilustrowanych warunków ograniczających, adresów komórek funkcji celu oraz komórek zmienianych. Po przyciśnięciu przycisku „Rozwiąż” w arkuszu pojawiają się zoptymalizowane wartości zmiennych decyzyjnych- ustalony zostaje optymalny rozkład ładunku, gwarantujący najniższe koszty jednostkowe.
3. Zagadnienie transportowe
Rozpatrujemy następujące zagadnienie. Od ośmiu (D1-D8) dostawców należy przewieźć towar do dziewięciu (O1-O9) odbiorców. Podaż w danym okresie, np. w ciągu tygodnia wynosi łącznie 7850 ton, zapotrzebowanie na towar odbiorców wynosi również 7850 ton. Wszystkie parametry zadania zawiera tab. 3.1., która przedstawia informacje dotyczące zarówno jednostkowych kosztów transportu, jak i ilości ton, jakie mają być wywiezione od poszczególnych dostawców, a także ilości, jakie mają być przewiezione od poszczególnych odbiorców.
Zagadnienie polega na znalezieniu takiego dopuszczalnego planu przewozów, który zapewni łączny koszt transportu 7850 ton towaru z punktu nadania do punktu odbioru będzie najmniejszy.
Rozwiązać zbilansowane zadanie transportowe z wykorzystaniem trzech metod poszukiwania rozwiązania optymalnego:
metodą kąta północno-zachodniego,
metodą minimalnego elementu macierzy,
za pomocą optymalizacji w programie MS Excel- Solver
Jednostkowe koszty transportu cij [zł/tona] pomiędzy podmiotami podane są w macierzy.
Potencjał dostawców [tona] podano w kolumnie ai.
Zapotrzebowanie odbiorców [tona] podano w wierszu bj.
Tab.3.1. Macierz początkowa
Odbiorcy Dostawcy |
O1 | O2 | O3 | O4 | O5 | O6 | O7 | O8 | O9 | Ai |
|---|---|---|---|---|---|---|---|---|---|---|
| D1 | 15 | 100 | 50 | 40 | 70 | 5 | 95 | 70 | 90 | 850 |
| D2 | 20 | 5 | 60 | 35 | 45 | 40 | 70 | 90 | 45 | 900 |
| D3 | 10 | 45 | 35 | 10 | 35 | 50 | 85 | 55 | 70 | 950 |
| D4 | 5 | 60 | 45 | 65 | 60 | 35 | 75 | 75 | 60 | 900 |
| D5 | 50 | 30 | 60 | 85 | 25 | 75 | 60 | 35 | 55 | 1090 |
| D6 | 60 | 45 | 5 | 40 | 60 | 60 | 80 | 20 | 40 | 1400 |
| D7 | 45 | 80 | 20 | 80 | 70 | 30 | 55 | 60 | 75 | 960 |
| D8 | 70 | 45 | 15 | 65 | 40 | 90 | 50 | 25 | 85 | 800 |
| Bj | 900 | 750 | 850 | 850 | 750 | 800 | 850 | 900 | 1200 | 7850 |
Metoda kąta północno-zachodniego
Tab.4.1. Optymalizacja metodą kąta północno-zachodniego
Odbiorcy Dostawcy |
O1 | O2 | O3 | O4 | O5 | O6 | O7 | O8 | O9 | Ai |
|---|---|---|---|---|---|---|---|---|---|---|
| D1 | 850 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 850 |
| D2 | 50 | 750 | 100 | 0 | 0 | 0 | 0 | 0 | 0 | 900 |
| D3 | 0 | 0 | 750 | 200 | 0 | 0 | 0 | 0 | 0 | 950 |
| D4 | 0 | 0 | 0 | 650 | 250 | 0 | 0 | 0 | 0 | 900 |
| D5 | 0 | 0 | 0 | 0 | 500 | 590 | 0 | 0 | 0 | 1090 |
| D6 | 0 | 0 | 0 | 0 | 0 | 210 | 850 | 340 | 0 | 1400 |
| D7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 560 | 400 | 960 |
| D8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 800 | 800 | |
| Bj | 900 | 750 | 850 | 850 | 750 | 800 | 850 | 900 | 1200 | 7850 |
Koszty całkowite: 384750 zł/tona
Metoda najmniejszych kosztów jednostkowych
Tab.4.2. Optymalizacja metodą najmniejszych kosztów jednostkowych
Odbiorcy Dostawcy |
O1 | O2 | O3 | O4 | O5 | O6 | O7 | O8 | O9 | Ai |
|---|---|---|---|---|---|---|---|---|---|---|
| D1 | 0 | 0 | 0 | 0 | 0 | 800 | 0 | 0 | 50 | 850 |
| D2 | 0 | 750 | 0 | 0 | 0 | 0 | 0 | 0 | 150 | 900 |
| D3 | 0 | 0 | 0 | 850 | 0 | 0 | 0 | 0 | 100 | 950 |
| D4 | 900 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 900 |
| D5 | 0 | 0 | 0 | 0 | 750 | 0 | 0 | 0 | 340 | 1090 |
| D6 | 0 | 0 | 850 | 0 | 0 | 0 | 0 | 550 | 0 | 1400 |
| D7 | 0 | 0 | 0 | 0 | 0 | 0 | 400 | 0 | 560 | 960 |
| D8 | 0 | 0 | 0 | 0 | 0 | 0 | 450 | 350 | 0 | 800 |
| Bj | 900 | 750 | 850 | 850 | 750 | 800 | 850 | 900 | 1200 | 7850 |
Koszty całkowite: 186950 zł/tona
Optymalizacja w programie MS Excel- Solver
Tab.4.3. Optymalizacja programem MS Excel- Solver
Odbiorcy Dostawcy |
O1 | O2 | O3 | O4 | O5 | O6 | O7 | O8 | O9 | Ai |
|---|---|---|---|---|---|---|---|---|---|---|
| D1 | 50 | 0 | 0 | 0 | 0 | 800 | 0 | 0 | 0 | 850 |
| D2 | 0 | 750 | 0 | 0 | 0 | 0 | 0 | 0 | 150 | 900 |
| D3 | 0 | 0 | 0 | 850 | 100 | 0 | 0 | 0 | 0 | 950 |
| D4 | 850 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 50 | 900 |
| D5 | 0 | 0 | 0 | 0 | 650 | 0 | 0 | 100 | 340 | 1090 |
| D6 | 0 | 0 | 740 | 0 | 0 | 0 | 0 | 0 | 660 | 1400 |
| D7 | 0 | 0 | 110 | 0 | 0 | 0 | 850 | 0 | 0 | 960 |
| D8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 800 | 0 | 800 |
| Bj | 900 | 750 | 850 | 850 | 750 | 800 | 850 | 900 | 1200 | 7850 |
Koszty całkowite: 172000 zł/tona
Zagadnienie transportowe jest przykładem problemu decyzyjnego o wielu rozwiązaniach. Jak przedstawiono w projekcie- istnieje kilka metod jego rozwiązania (w projekcie zastosowano jedynie trzy), w każdej z nich otrzymujemy inne koszty jednostkowe. Największe koszty uzyskano przy rozkładzie ładunku metodą kąta północnego- wynosiły one 384750 zł/tona. Jednocześnie, jest to metoda najprostsza i najszybsza- rozdziału tą metodą można dokonać od razu, bez wcześniejszego rozpisywania macierzy kosztów jednostkowych. Niższy koszt, choć nie najniższy, wynoszący 186950 zł/tona, uzyskano przy pomocy metody najmniejszego elementu macierzy. Metoda ta jednak była bardziej pracochłonna od metody kąta północno-zachodniego, a wynik uzyskany przy jej pomocy nie zawsze będzie najniższy. Najlepszy efekt osiągnięto przy pomocy dodatku programu MS Excel- Solver, koszty całkowite powstałe przez rozkład ładunku tą metodą wynosiły 172000 zł/tona. Jednak należy podkreślić, iż metoda ta jest najbardziej pracochłonna, i wiąże się ze znajomością podstaw programu MS Excel. Źle sformułowane warunki ograniczające mogą wiązać się z uzyskaniem nieprawidłowego rozkładu (nie uzyskanie najniższych kosztów, nie wykorzystanie w pełni podaży dostawców lub nie zaspokojenie popytu wszystkich odbiorców).
Jak wynika z powyższych przykładów rozwiązań, każda z metod ma swoja osobne zastosowanie. W przypadku potrzeby dokonania szybkiego rozkładu ładunku, dla okolicznościowego przewozu, w którym generowane koszty całkowite nie będą grały najistotniejszej roli, świetnie sprawdzi się metoda kąta północno-zachodniego. Nie wymaga ona wielkiego nakładu pracy ani zastosowania żadnego z programów komputerowych (można go dokonać nawet ręcznie, po rozpisaniu macierzy na kartce). Metoda najmniejszego elementu macierzy świetnie nadaje się gdy dysponujemy nieco większą ilością czasu, i zależy nam na obniżeniu kosztów całkowitych. Jednak należy pamiętać że rozkład przy jej pomocy nie zawsze będzie wiązał się uzyskaniem najmniejszych kosztów całkowitych. Taką gwarancję daje nam zastosowanie programu MS Excel z dodatkiem Solver, który można traktować jako sprawdzenie metody najmniejszego elementu macierzy, bądź gdy dysponujemy większą ilością czasu na opracowanie warunków ograniczających oraz jesteśmy zaznajomieni z programem MS Excel.
[1] Guzik B., Ekonometria i badania operacyjne. Badania operacyjne, Poznań 1993 r.
[2] Nowak E., Zaawansowana rachunkowość zarządcza, PWE ,Warszawa 2003 r.
[3] Tomkowska A., Badania operacyjne- programowanie liniowe, Koszalin 2006 r.
[4] Witkowska D., Metody wspomagające podejmowanie decyzji w zarządzaniu, "Menadżer", Łódź 2000 r.