Przepływy w sieciach

Def.

Graf: suma = [P,U], zorientowany, spójny, acykliczny, mający dokładnie jeden wierzchołek początkowy oraz dokładnie jeden wierzchołek końcowy nazywamy siecią przepływów jeżeli jego łuki uij scharakteryzowane są wielkościami fij >= 0 nazywamy ich przepustowościami.

Uwaga

Sieci przepływów mogą być modelami matematycznymi:

- sieci drogowych

- sieci transportowych

- lub sieci przepływu różnych substancji w różnych obiektach

Dla sieci przepływu przyjmuje się następujące oznaczenia:

P1 = 0 żródło sieci przepływu (węzeł początkowy )

Pm = M – ujście sieci przepływu ( węzeł końcowy)

Xij – przepływ przez łuk uij, przy czym : fij >= xij >= 0 (zapis ten oznacza, że przepływ jest nieujemny i nie przekracza przepustowości).

F – przepływ w sieci SUMA = [P,U] od żródła Uścia.

Problem decyzyjny polega na wyznaczeniu maksymalnego przepływu F* od źródła do Uścia oraz dodatkowo na wyznaczeniu jak ten przepływ się odbywa.

W związku z powyższym, łuki w sieci przepływu oznaczać będziemy następująco

Wniosek

Łuki w sieci przepływu charakteryzowane są przepływem i przepustowością.

Zbadanie wyznaczenia maksymalnego przepływu F* od żródła do ujścia w sieci przepływu SUMA = [P,U] można sformułować w postaci następującego zadania optymalizacji liniowej

F-> max przy spełnieniu warunków ograniczających:

$$\left\{ \begin{matrix} \frac{\sum_{j}^{}{X0j = F\ dla\ takich,\ ze\ X0j \in U}}{\sum_{i}^{}{Xim = F\ dla\ takich,\ ze\ Xim \in U}} \\ \frac{\sum_{i}^{}{Xik - \ \sum_{j}^{}{\text{Xjk\ dla\ }\ k = 1,2,\ldots,\ m - 1}}}{0 \leq xij \leq fij\ \ \ dla\ xij \in U} \\ \end{matrix} \right.\ $$

Uwagi

1. Pierwszy warunek oznacza że z węzła „0” wypływ wynosi F.

2. Drugi warunek oznacza że do węzła końcowego „M” przepływ wynosi „F”

3. Trzeci warunek oznacza, że przepływ do każdego węzła jest równy odpływowi z tego węzła,

4. Czwarty warunek oznacza,że przepływy są nieujemne i nie przekraczają przepustowości łuków.

Dokończenie...

Przekroje w Sieci Przepływów

Niech A i B – dwa podzbiory zbioru wszystkich węzłów sieci ∑ = [P, U], które spełniają warunki:

1. 0eA źródło należy do podzbioru A

2. MeB ujście należy do podzbioru B

3. A suma B = P ( suma podzbiorów A i B jest zbiorem wszystkich węzłów)

4. A różnica B = zbiór zamknięty ( podzbiory A oraz B są wzajemnie rozłączne).

DEFINICJA

Przekrojem sieci przepływów nazywamy zbiór oznaczony (A, B) wszystkich łuków łączących punkty albo węzły zbiorów A i B, czyli przekrojem jest zbir.

DEFINICJA

Przepustowością przekroju nazywamy su ę przepustowości wszystkich łuków przekroju czyli f(A,B)= $\sum_{\frac{i \in A}{j \in B}}^{}\text{fij}$

TWIERDZENIE

Maksymalny przepływ w sieci przepływu ∑ = [P, U] jest równy przepustowości minimalnego przekrojuw sieci, czyli F*= $\frac{\min}{A,B}$ f(A,B)

Wnioski:

1. Aby wyznaczyć maksymalny przepływ wystarczy wyznaczyć minimalny przekrój.