Zagadnienie transportowe na sieci

ZT na sieci – rozważamy na grafie niekierowanym (bez strzałek, np. mapa
drogowa z odległościami pomiędzy połączonymi drogami miastami).
Def. Graf nieskierowany to para (V,L), gdzie V - skończony zbiór
wierzchołków (węzłów - miast), L – skończony zbiór nieuporządkowanych
par (różnych parami) elementów zbioru V (tzw. łuków).
W takim grafie zbiór V dzielimy na trzy rodzaje węzłów:

1.

węzły zwane źródłami (dostawcy, producenci towaru, miasta);

2.

węzły pośrednie albo tranzytowe (punkty, poprzez które przepływa
towar, miasta na trasie),

3.

węzły odpływowe (odbiorcy, konsumenci towaru, miasta docelowe).

Założenia: ZT w wersji sieciowej:

a)

suma ilości towaru w źródłach jest równa sumie ilości towaru w
odpływach;

b)

na każdym łuku grafu nieskierowanego – sieci transportowej –
dane są koszty przesłania towaru po łuku. Oznaczamy je c

ij

;

CEL: zaplanować przepływ towaru po zadanej sieci transportowej, by koszt
przesłania towarów ze wszystkich źródeł do wszystkich odpływów był jak
najmniejszy.
I BUDOWA PLANU POCZĄTKOWEGO PRZEPŁYWU TOWARÓW

Wyznaczamy

na

grafie

nieskierowanym

drzewo

rozpinające

(szkieletowe) transportu. Dla grafu złożonego z n węzłów drzewo
szkieletowe składa się z n-1 krawędzi. Ustalamy kierunek przesyłania
towaru nadając strzałki na łukach drzewa szkieletowego od źródeł do ujść.
II

WŁAŚCIWA

NUMERACJA

WIERZCHOŁKÓW

I

PLAN

POCZĄTKOWY TRANSPORTU PO SIECI
III OBLICZENIE KOSZTU TRANSPORTU PO SIECI
IV NADANIE POTENCJAŁÓW WIERZCHOŁKOM

Na przykład: v

1

=0 i v

j

= v

i

+c

ij

, gdy poruszamy się w kierunku odpływu,

v

j

= v

i

-c

ij

, gdy poruszamy się w przeciwnym kierunku.

V

OBLICZENIE

DELT

DLA

ŁUKÓW

BEZ

STRZAŁEK

(NIEBAZOWYCH)

Obliczamy

)

(

j

i

ij

ij

v

v

c

−

−

=

∆

liczone od większego potencjału i do

mniejszego j. Jeśli wszystkie obliczone delty są nieujemne, to plan
przesyłania towarów po sieci jest optymalny.
VI JEŚLI NIE - POPRAWIANIE PLANU TRANSPORTU

Do nowej sieci transportowej dodajemy łuk, który wyznacza

najmniejsza delta. W sieci wyznaczonej przez drzewo szkieletowe tworzy się
cykl. Na dodanym łuku kierunek przepływu towarów od v

i

mniejszego do v

j

większego. W ramach cyklu przesuwamy towar w ilości minimum po
łukach przeciwnie skierowanych do kierunku cyklu.