Optymalizacja przewozów: Różnice pomiędzy wersjami

m
 
m
Linia 1: Linia 1:
 +
 +
 
==Charakterystyka==
 
==Charakterystyka==
 
Optymalizacja przewozów służy do takiego rozplanowania przewozów aby koszty [[transport]]u 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.
 
Optymalizacja przewozów służy do takiego rozplanowania przewozów aby koszty [[transport]]u 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.
Linia 8: Linia 10:
 
#* metoda minimalnego elementu macierzy kosztów.
 
#* metoda minimalnego elementu macierzy kosztów.
 
# 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''
 
# 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''
# w wypadku, gdy rozwiązanie jakie otrzymaliśmy nie jest optymalne wówczas należy wyznaczyć kolejne rozwiązanie. (D. Witkowska 2000 s. 66)
+
# 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==
 
==Elementy zagadnienia transportowego==
 
* [[Podaż]] dostawców - przez podaż dostawców należy rozumieć liczbę dostawców ''m'' posiadających ''am'' produktów.
 
* [[Podaż]] dostawców - przez podaż dostawców należy rozumieć liczbę dostawców ''m'' posiadających ''am'' produktów.
 
* [[popyt|Zapotrzebowanie]] odbiorców- przez zapotrzebowanie odbiorców należy rozumieć ilość odbiorców ''n'', którym przedsiębiorstwo ma dostarczyć ''bn'' produktów.
 
* [[popyt|Zapotrzebowanie]] odbiorców- przez zapotrzebowanie odbiorców należy rozumieć ilość odbiorców ''n'', którym przedsiębiorstwo ma dostarczyć ''bn'' produktów.
 +
<google>ban728t</google>
 +
 
* 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 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  
 
* Macierz przewozów- jest to macierz ''xij'' gdzie ''i = (''1'',...,m)'' oraz ''j = (''1'',..,n)'' tj. Ilość produktów  
Linia 174: Linia 177:
 
[[en:Optimization of transport]]
 
[[en:Optimization of transport]]
  
 
fr. Optimisation de transports, niem. Optimierung des transportes
 

Wersja z 17:31, 13 gru 2009


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

  • Nowak E., Zaawansowana rachunkowość zarządcza, PWE ,Warszawa 2003 str. 129-131
  • Witkowska D., Metody wspomagające podejmowanie decyzji w zarządzaniu, "Menadżer" , Łódź 2000 str. 66-70

Autor: Krzysztof, Iwona Bonarska