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

m (clean up, replaced: → , <p align=right>'''Autor:''' Krzysztof, Iwona Bonarska</p> → {{a|Krzysztof, Iwona Bonarska}}, , → , (2), → (4), → (2), ,m) → , m) (4), → , n( → n (, * → *, removed: ==Charakterystyka==)
Linia 1: Linia 1:
 
+
'''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.
 
 
==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.
 
  
 
==Etapy klasycznego algorytmu transportowego==
 
==Etapy klasycznego algorytmu transportowego==
Linia 10: Linia 7:
 
#* 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==
Linia 16: Linia 13:
 
* [[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>
 
<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  
 
 
przewieziona od ''i''-tego dostawcy do ''j''-tego odbiorcy. (E. Nowak 2003 s. 129-130)
 
przewieziona od ''i''-tego dostawcy do ''j''-tego odbiorcy. (E. Nowak 2003 s. 129-130)
  
Linia 43: Linia 39:
 
==Przykład==
 
==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.
 
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.
 
  
  
Linia 83: Linia 78:
 
|}
 
|}
  
+
 
'''Etap I określenie rodzaju zagadnienia (otwarte lub zamknięte)'''
 
'''Etap I określenie rodzaju zagadnienia (otwarte lub zamknięte)'''
  
Linia 153: Linia 148:
 
|}
 
|}
  
 
+
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.
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:
 
Wyznaczone za pomocą metody kąta północno - zachodniego rozwiązanie jest optymalne i jest następujące:
Linia 169: Linia 163:
  
 
==Bibliografia==
 
==Bibliografia==
* Nowak E., Zaawansowana [[rachunkowość zarządcza]], PWE ,Warszawa 2003 str. 129-131
+
* 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
+
* Witkowska D., Metody wspomagające [[podejmowanie decyzji]] w zarządzaniu, "[[Menadżer]]", Łódź 2000 str. 66-70
  
<p align=right>'''Autor:''' Krzysztof, Iwona Bonarska</p>
+
{{a|Krzysztof, Iwona Bonarska}}
 
[[Kategoria:Transport]]
 
[[Kategoria:Transport]]
 
[[Kategoria:Statystyka i Ekonometria]]
 
[[Kategoria:Statystyka i Ekonometria]]
 
[[en:Optimization of transport]]
 
[[en:Optimization of transport]]

Wersja z 08:58, 21 cze 2015

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