Podręcznik

W sieciach przepływowych formułuje się problemy typowe dla sieci przepływowych, w szczególności problem maksymalnego przepływu i problem przepływu minimalnokosztowego. Cała sztuka modelowania polega na „zakodowaniu” problemu, który chcemy rozwiązać w pojęciach ze świata sieci przepływowych. Najpierw dokonujemy więc pewnego mapowania problemu do problemu w sieci przepływowej. Następnie rozwiązujemy odpowiedni problem w sieci przepływowej. Uzyskany w ten sposób wynik dekodujemy z przestrzeni pojęć sieci przepływowej do domeny wyjściowego problemu. Dlatego istotne jest jednoznaczne i poprawne określenie parametrów sieci przepływowej, zazwyczaj przepustowości i kosztów łuków, oraz wskazanie problemu do rozwiązania na sieci. Przedstawimy teraz dwa kluczowe problemy rozwiązywane w sieciach przepływowych.

Problem maksymalnego przepływu

Problem polega na znalezieniu maksymalnego przepływu od wierzchołka źródłowego $s$ do wierzchołka ujściowego $t$. W problemie tym muszą zostać zdefiniowane przepustowości krawędzi, natomiast nie są wykorzystywane koszty. 

Poniżej znajduje się przykładowa sieć przesyłowa dla problemu maksymalnego przepływu.

Rozwiązanie problemu maksymalnego przepływu zostało zaznaczone poniżej w postaci przepływów podanych w nawiasach kwadratowych.

Problem maksymalnego przepływu można rozwiązywać np. algorytmem Forda-Fulkersona. Dla całkowitoliczbowych przepustowości algorytm ten znajduje rozwiązanie całkowitoliczbowe w skończonej liczbie iteracji. Ponieważ w niniejszym materiale skupiamy się na modelowaniu, czytelnika chcącego poznać szczegóły algorytmu odsyłamy do pozycji bibliograficznych.

Model programowania liniowego dla problemu maksymalnego przepływu jest następujący:

$\max F$

$\sum_{v \in V} f_{sv} -F =0$

$\sum_{u\in V} f_{vu} - \sum_{u\in V} f_{uv} = 0 \quad v \in V, v \ne s, v \ne t$

$0 \leq f_{uv} \leq c_{uv} \quad (u,v) \in E$

Z maksymalnym przepływem wiąże się pojęcie minimalnego przekroju.

Przekrojem grafu $G=(V,E)$ nazywamy podział łuków na dwa rozłączne podzbiory $S$ oraz $T= V \setminus S$. Przepustowość przekroju $(S,T)$ to suma przepustowości wszystkich łuków łączących wierzchołki $s \in S$ z wierzchołkami $t \in T$.

Wartość dowolnego przepływu w sieci nie może być większa niż przepustowość dowolnego przekroju. W szczególności wartość maksymalnego przepływu w sieci $G$ jest równa przepustowości minimalnego przekroju w sieci $G$.

Minimalny przekrój może być wyznaczony np. w ramach ostatniej iteracji algorytmu Forda-Fulkersona, w której finalne znakowanie wierzchołków wyznacza ich podział na podzbiory $S$ i  $T$.

Problem najtańszego przepływu

Problem najtańszego przepływu wymaga zdefiniowania jednostkowych kosztów przepływ na łukach. Należy znaleźć przepływ o zadanej wielkości z węzła źródłowego $s$ do ujścia $t$ przy minimalnym sumarycznym koszcie przepływu.

Poniżej znajduje się przykładowa sieć przesyłowa dla problemu najtańszego przepływu, gdzie pierwsza liczba z pary x/y oznacza przepustowość, a druga koszt.

Rozwiązanie problemu najtańszego przepływu zostało zaznaczone poniżej w postaci przepływów podanych w nawiasach kwadratowych.

Problem najtańszego przepływu może być rozwiązywany uproszczoną metodą sympleks lub dedykowanymi algorytmami sieciowymi.

Model programowania liniowego dla problemu minimalnokosztowego przepływu $F$ jest następujący:

$\min \sum_{(u,v) \in E} \theta_{uv} f_{uv}$

$\sum_{v \in V} f_{sv} = F$

$\sum_{u\in V} f_{vu} - \sum_{u\in V} f_{uv} = 0 \quad v \in V, v \ne s, v \ne t$

$0 \leq f_{uv} \leq c_{uv} \quad (u,v) \in E$