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

m
Linia 2: Linia 2:
  
 
==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.
  
 
==Etapy klasycznego algorytmu transportowego==
 
==Etapy klasycznego algorytmu transportowego==
 
# wyznaczenie wstępnego rozwiązania bazowego przy wykorzystaniu wybranej metody np:
 
# wyznaczenie wstępnego rozwiązania bazowego przy wykorzystaniu wybranej metody np:
#* metoda kąta północno-zachodniego,
+
#* [[metoda]] kąta północno-zachodniego,
#* metoda minimalnego elementu wiersza lub kolumny macierzy kosztów,
+
#* metoda minimalnego elementu wiersza lub kolumny macierzy [[koszt]]ów,
 
#* 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>
 
<google>ban728t</google>
  
Linia 22: Linia 22:
  
 
==Rodzaje zagadnień transportowych==
 
==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''
+
* 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ść
 
* 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ż podaż dostawców jest większa od zapotrzebowania odbiorców.
Linia 42: Linia 42:
  
 
==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 52: Linia 52:
 
!O3
 
!O3
 
!O4
 
!O4
!Zasoby dostawców ''ai''
+
![[Zasoby]] dostawców ''ai''
 
|-
 
|-
 
|D1
 
|D1
Linia 112: Linia 112:
 
''2x11 + x12 + 3x13 + x14 +4x21+2x22 + x23 + 2x24 +x31+ 3x32 +x33 + 4x34'' - min
 
''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.
+
[[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'''
 
'''Etap IV wyznaczamy optymalne rozwiązanie przy wykorzystaniu metody kąta północno - zachodniego'''
Linia 154: Linia 154:
  
  
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 169:
  
 
==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>
 
<p align=right>'''Autor:''' Krzysztof, Iwona Bonarska</p>
Linia 176: Linia 176:
 
[[Kategoria:Statystyka i Ekonometria]]
 
[[Kategoria:Statystyka i Ekonometria]]
 
[[en:Optimization of transport]]
 
[[en:Optimization of transport]]
 

Wersja z 10:55, 1 lut 2014


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