Optymalizacja przewozów


Charakterystyka

Optymalizacja przewozów służy do takiego rozplanowania przewozów aby koszty transportu były jak najniższe. Dotyczy to głównie przedsiębiorstw, których działalność wymaga dokonywania transportu dużej ilości produktów np: zboża, węgla, piasku czy cementu. Optymalizacja przewozów znana jest również pod pojęciem zagadnienia transportowe.

Etapy klasycznego algorytmu transportowego

  1. wyznaczenie wstępnego rozwiązania bazowego przy wykorzystaniu wybranej metody np:
    • metoda kąta północno-zachodniego,
    • metoda minimalnego elementu wiersza lub kolumny macierzy kosztów,
    • metoda minimalnego elementu macierzy kosztów.
  2. przy użyciu metody potencjałów należy sprawdzić, które rozwiązanie jest optymalne w tym celu należy zastosować wskaźnik optymalności o= (ui + vj) - cij=0 gdzie cij= ui + vj
  3. w wypadku, gdy rozwiązanie jakie otrzymaliśmy nie jest optymalne wówczas należy wyznaczyć kolejne rozwiązanie. (D. Witkowska 2000 s. 66)

Elementy zagadnienia transportowego

  • Podaż dostawców - przez podaż dostawców należy rozumieć liczbę dostawców m posiadających am produktów.
  • Zapotrzebowanie odbiorców- przez zapotrzebowanie odbiorców należy rozumieć ilość odbiorców n, którym przedsiębiorstwo ma dostarczyć bn produktów.
  • Macierz kosztów przewozu- jest to macierz kij gdzie i = (1,...,m) oraz j = (1,...,n) tj. koszt przewozu produktu od i-tego dostawcy do j-tego odbiorcy.
  • Macierz przewozów- jest to macierz xij gdzie i = (1,...,m) oraz j = (1,..,n) tj. Ilość produktów

przewieziona od i-tego dostawcy do j-tego odbiorcy. (E. Nowak 2003 s. 129-130)

Rodzaje zagadnień transportowych

  • zamknięte zagadnienie transportowe- występuje wówczas, gdy podaż dostawców jest równa zapotrzebowaniu odbiorców tj. wówczas gdy występuje następująca zależność ai = bj
  • otwarte zagadnienie transportowe- występuje wówczas, gdy podaż dostawców nie jest równa zapotrzebowaniu odbiorców tj. Wówczas gdy występuje następująca zależność
    • ai > aj oznacza to, iż podaż dostawców jest większa od zapotrzebowania odbiorców.
    • ai < aj oznacza to, iż dostawców jest mniejsza od zapotrzebowania.

Postać klasycznego algorytmu transportowanego dla zamkniętych zagadnień transportowych.

Warunki ograniczające dla dostawców:

xij=ai gdzie xij elementy macierzy przewozów

Warunki ograniczające dla odbiorców

xij=bj

ai = bj

cijxij - min

Przykład

Na podstawie danych zawartych w poniższej tabelce zbudowany zostanie model zagadnienia transportowego, w którym występuje czterech odbiorców i trzech dostawców.


Odbiorcy/Dostawcy O1 O2 O3 O4 Zasoby dostawców ai
D1 2 1 3 1 20
D2 4 2 1 2 10
D3 1 3 1 4 20
Zapotrzebowanie odbiorców bj 20 15 5 10 50


Etap I określenie rodzaju zagadnienia (otwarte lub zamknięte)

ai = bj, 50=50 więc jest to zagadnienie transportowe zamknięte

Etap II wyznaczenie warunków ograniczających dla dostawców i odbiorców.

Warunki ograniczające dla dostawców:

X11 + X12 +X13 + X14 = 20

X21 + X22 + X23 + X24 =10

X31 + X32 + X33 + X34 =20

Warunki ograniczające dla odbiorców

X11 + X21 + X31= 20

X12 + X22 + X32 = 15

X13 + X23 + X33 = 5

X14 + X24 + X34= 10

Etap III wyznaczenie funkcji celu

2x11 + x12 + 3x13 + x14 +4x21+2x22 + x23 + 2x24 +x31+ 3x32 +x33 + 4x34 - min

Funkcja celu wyznaczana jest z wartości znajdujących się w tabelce odzwierciedlającej macierz.

Etap IV wyznaczamy optymalne rozwiązanie przy wykorzystaniu metody kąta północno - zachodniego

Odbiorcy/Dostawcy O1 O2 O3 O4 Zasoby dostawców ai
D1 20 20
D2 10 10
D3 5 5 10 20
Zapotrzebowanie odbiorców bj 20 15 5 10 50


W metodzie kąta północno - zachodniego wielkość przewozu x11 wyznaczamy jako min(20,20) czyli x11=20 popyt pierwszego dostawcy został w pełni zaspokojony, następnie x22 wyznaczamy jako min (10,5) odbiorca drugi nie zaspokoił zgłaszanego popytu pozostało jeszcze 5 jednostek towaru, natomiast dostawca trzeci posiada jeszcze 5 jednostek towaru co sprawia, iż popyt zostaje w pełni zaspokojony. Taki tryb postępowania prowadzony jest, aż zostaną wyczerpane wszystkie możliwości.

Wyznaczone za pomocą metody kąta północno - zachodniego rozwiązanie jest optymalne i jest następujące:

x11 = 20, x22= 10, x32=5, x33=5, x34=10,

x12=x13=x21=x23=x31=0

Etap V wyznaczenie wartości funkcji celu.

2x20+2x10+3x5+5+4x10= 40+20+15+5+40=120

tak więc wartość funkcji celu wynosi 120 i jest to najniższy koszt transportu.

Bibliografia

Autor: Krzysztof, Iwona Bonarska