Maksymalny przepływ a dualność

W tym podrozdziale okaże się, że twierdzenie o maksymalnym przepływie i minimalnym przekroju jest - w pewien sposób - zasadą dualności dla problemu maksymalnego przepływu.
Zapiszmy problem maksymalnego przepływu () - () w nieco innej postaci. Niech będzie dana sieć $S=(V,A;c)$. Przepływem w $S$ jest funkcja $f:A \rightarrow {\bf R}$ spełniająca następujące warunki:

$$\hspace{0.8cm} \left\{ \begin{array}{lc} \sum_{(x,y)\i... ...f(x,y) \ge 0 \mbox{ dla } (x,y) \in A & \end{array} \right.$$ (8.13)

Wartością przepływu $f$ jest wtedy liczba $w$ którą w naszym problemie maksymalizujemy:

$$w \rightarrow \max$$ (8.14)

Problemem dualnym do problemu () - () jest problem następujący (por. podrozdział ):

$$\hspace{8mm} \left\{ \begin{array}{l} \lambda (y)-\lamb... ...}c(x,y)\gamma (x,y) \rightarrow \max \end{array} \right.$$ (8.15)

Zauważmy, że w problemie dualnym () nie ma ograniczeń na znak zmiennych dualnych $\lambda (v)$ (dla $v\in V$). Zmienne dualne odpowiadają poszczegłnym ograniczeniom w problemie prymalnym. Tak więc

$\lambda (x) \ -$

są zmiennymi odpowiadającymi ograniczeniom

$$\sum_{(x,y)\in A} f(x,y) - \sum_{(z,x) \in A} f(z,x) = \le... ...box{dla } x=s\\ w & \mbox{dla } x=t \end{array} \right.$$ (8.16)

Każdemu wierzchołkowi $x$ sieci $S$ odpowiada zmienna dualna która nie ma ograniczenia na znak gdyż we wzorze () jest równość.

$\gamma (x,y) \ -$

są zmiennymi dualnymi odpowiadającymi ograniczeniu

$$f(x,y) \le c(x,y)$$ (8.17)

stąd w problemie dualnym występuje ograniczenie na znak tej zmiennej^8.7.

Dowolny przekrój $(W,\overline{W})$ rozdzielający $s$ od $t$ w sieci $S$ definiuje pewne rozwiązanie dopuszczalne problemu () w następujący sposób:

$$\lambda (x) = \left\{ \begin{array}{ll} 1 & \mbox{ je... ...n W\\ 0 & \mbox{ jeśli } x \notin W \end{array} \right.$$ (8.18)

$$% latex2html id marker 10275 \gamma (x,y)= \left\{ ... ... 0 & \mbox{ w przeciwnym przypadku} \end{array} \right.$$ (8.19)

Słaba zasada dualności w ogólnej postaci (twierdzenie ) daje nam natychmiast inny dowód twierdzenia . Rzeczywiście, funkcje $\lambda$ i $\gamma$ zdefiniowane wzorami () i () przez dowolny przekrój rozdzielający $s$ od $t$ dają pewne rozwiązanie problemu ().
Z kolei cała reszta dowodu twierdzenia sprowadza się do wykazania, że pewien przekrój określa nam przy pomocy () i () rozwiązanie optymalne () (zrobili to Dantzig i Fulkerson w [6]).