Sieć logistyczna

D M M H

R W

M C

D P W D G

P M

H W

D S

CI

D - dostawca

P - Producent

MWP - Magazyn własny producenta

MR - Magazyn regionalny

H - hurtownia

CD - centrum dystrybucji

MW - magazyn własny

G - gastronomia

S - sklepy

CI - centrum informacji

Problem przepływu produktów w sieciach

Maksymalizacja przesyłu w sieci dystrybucyjnej

Legnica Ostrów wielkopolski

25

15 12

Zgorzelec Kielce

30 18

Wrocław Częstochowa

9

Przykład tras przewozu o ograniczonej przepustowości

Grafy skierowane wartościowane G = <V, E, b> będące sieciami z wyróżnionymi:

• Źródłem reprezentującym miejsca producenta oraz

• Ujściem przyporządkowanym miejscu odbioru produktu.

Liczby b_ij>0 przyporządkowane strzałkom <i, j> określają maksymalną wielkość przewozu na odcinku łączącym węzeł i z węzłem j.

Liczba b_ij będzie określać przepustowość połączenia <i, j>. Wprowadza się niekiedy też dolną granicę przepustowości (np. aby nie przewozić listu tirem).

Typy połączeń

Przejścia z węzła r do węzła k

R k

Gdy strzałki mają ten sam zwrot tworzą drogę.

R k

Gdy strzałki mają różne zwroty tworzą łańcuch połączeń.

x_ij - realne wykorzystanie przepustowości 0 ≤ x_ij ≤ b_ij

Przepływ z węzła r do węzła k

Wektor x wyznacza przepływ z węzła r do węzła k o natężeniu v (v ≥ 0) gdy jego składowe spełniają następujące warunki:

Najważniejsze są wąskie gardła.

1. Źródło opuszcza łącznie v produktu,

2. w każdym węźle nie będącym ani źródłem ani ujściem ilość wpływająca produktów równa się ilości wypływającej,

3. Do węzła będącego ujściem dociera tyle produktu, ile wypłynęło ze źródła

Będziemy poszukiwać takiego przepływu o natężeniu v*, dla którego nie istnieje inny przepływ o większym natężeniu.

Przepływ v*, który ma tę właściwość, będziemy nazywać maksymalnym przepływem w sieci.

Jego wyznaczenie sprowadza się do rozwiązania zadania:

V → max

przy ograniczeniu:

.

.

.

Przekrój sieci

Dokonujemy podziału zbioru węzłów v na dwa niepuste, rozłączne zbiory

Wąskie gardło to minimalny przekrój.

Dolna granica musi być spełniona (wymusza) a górna nie musi być wykorzystana.

Legnica Ostrów wielkopolski

25

15 12

Zgorzelec Kielce

5

30 18

Wrocław Częstochowa

9

A B

W powyższym przypadku przepustowość sieci wynosi 30 (12 + 18).

WWW.DYCHA.PRV.PL - Oficjalna Strona GRUPY 10 AE we Wrocławiu

LOGISTYKA Stanisław Krawczyk Wykład 23 - 2001-04-23

Sukcesory

- to co wpływa

Poprzednicy

- to co wypływa

Przekrój sieci

---