Zagadnienia

14. Przepływy w sieciach

14.1. Przepływy w sieciach.

Siecią nazywać będziemy skończony graf G=\{ W,S;k,p\} wraz z dwiema funkcjami V\,:W\rightarrow\mathbb{R} przypisującą każdemu wierzchołkowi liczbę rzeczywistą V(w) zwaną potencjałem i C\,:S\rightarrow\mathbb{R} przypisującą każdej krawędzi koszt przepływu. Ponieważ zawiera wierzchołki i krawędzie więc, dla uniknięcia nieporozumień, wierzchołki sieci będziemy nazywać węzłami zaś zorientowane krawędzie strzałkami.

Zagadnienie przepływy w sieciach ( o nieograniczonej przepustowości ) polega na znalezieniu schematu przepływu o minimalnych kosztach, wyrównującego potencjały.

Modelem matematycznym takiego zagadnienia będzie:

Jako zmienne wybieramy zbiór \{ x_{s}\ |\  s\in S\} indeksowany strzałkami grafu.

Min\  x_{0}=\sum _{{s\in S}}\  C(s)x_{s} na obszarze opisanym nierównościami:

\forall _{{w\in W}}\ \sum _{{\{ s\in S\,|p(s)=w\}}}\  x_{s}-\sum _{{\{ s\in S\,|k(s)=w\}}}\  x_{s}=V(w)

\forall _{{s\in S}}\  x_{s}\geq 0.

Zauważmy, macierz opisująca powyższe równania ma wiersze indeksowane węzłami a kolumny, z prawej strony kreski, indeksowane strzałkami s (lub zmiennymi x_{s} ). Ponadto kolumna odpowiadająca strzałce s ma zera, jedną 1 w wierszu o indeksie p(s) i jedną -1 w wierszu o indeksie k(s). W przypadku grafu ukorzenionego strzałką s_{1}, dochodzi kolumna o indeksie s_{1}, która ma zera i jedną 1 w wierszu o indeksie p(s_{1})

Jak zsumujemy wszystkie równania, dla grafu nieukorzenionego, lewa strona zredukuje się do 0 i otrzymamy:

0=\sum _{{w\in W}}\  V(w)

A zatem ten układ równań jest zależny i jeżeli suma potencjałów jest niezerowa to jest sprzeczny. Zagadnienie gdy \sum _{{w\in W}}\  V(w)=0 nazywamy zrównoważonym.

Zajmijmy się teraz zrównoważonym zadaniem przepływu w sieci, która jest grafem spójnym. Okazuje się, że w takim przypadku po ukorzenieniu grafu w dowolnym wierzchołku równania stają się liniowo niezależne a każdy układ bazowy jest wyznaczony przez pewne drzewo spinające. Dokładniej.

Twierdzenie 14.1

Niech G=\{ W,S;k,p\} będzie spójnym grafem ukorzenionym w węźle w_{1} wraz z funkcjami potencjału V\,:W\rightarrow\mathbb{R} i kosztów C\,:S\rightarrow\mathbb{R} takimi, że \sum _{{w\in W}}\  V(w)=0. Wówczas:

a) Zbiór równań \forall _{{w\in W}}\ \sum _{{\{ s\in S\,|p(s)=w\}}}\  x_{s}-\sum _{{\{ s\in S\,|k(s)=w\}}}\  x_{s}=V(w) jest liniowo niezależny.

b) Jeżeli kolumny o indeksach s_{1},s_{2},...,s_{n} są liniowo niezależne i n=|W| to podgraf G=\{ W,S^{{\prime}};k,p\}, gdzie S^{{\prime}}=\{ s_{1},s_{2},...,s_{n}\} jest ukorzenionym drzewem spinającym.

Twierdzenie 14.1 w dalszej części będziemy używać poprzez następujący wniosek.

Wniosek 14.1

Niech TS będzie tablicą sympleks opisującą zagadnienie przepływu w sieci spójnej. Wówczas graf powstały przez odrzucenie strzałki indeksujących zmienne niebazowe jest drzewem spinającym.

Do dowodu części b) twierdzenia 14.1 użyjemy następującego lematu.

Lemat 14.1

Niech c=(s_{1},s_{2},...,s_{n}) przebiegający między wierzchołkami

w_{0},w_{1},w_{2},...,w_{n}=w_{0} będzie cyklem prostym w sieci G. Wówczas kolumny k_{1},k_{2},...,k_{n} tablicy sympleks indeksowane tymi krawędziami są liniowo zależne.

Dowód lematu. Wprowadźmy orientację na cyklu c zgodną z kolejnością węzłów s_{1}. To znaczy: Niech strzałka przebiega między węzłami w_{{i-1}} i w_{i}, definiujemy \varepsilon _{i}=\left\{\begin{array}[]{rl}1&,p(s_{i})=w_{{i-1}}\\
-1&,p(s_{i})=w_{i}\end{array}\right.

Badamy kolumnę K=\sum _{{i=1}}^{n}\ \varepsilon _{i}k_{i}.

W j - tym wierszu kolumny k_{i} (w wierszu indeksowanym węzłem w_{j}) występuje element

e_{{i,j}}=\left\{\begin{array}[]{rl}1&,p(s_{i})=w_{j}\\
-1&,k(s_{i})=w_{j}\\
0&,p(s_{i})\neq w_{j}\neq k(s_{i})\end{array}\right.=\left\{\begin{array}[]{rl}1&,p(s_{i})=w_{j}\\
-1&,p(s_{i})=w_{{j-1}}\\
0&,p(s_{i})\neq w_{j}\neq k(s_{i})\end{array}\right.

e_{{i,j}}=\left\{\begin{array}[]{rl}-\varepsilon _{i}&,i=j\\
\varepsilon _{i}&,i=j+1\\
0&,j\neq i\neq j+1\end{array}\right.

Zatem w j - tym wierszu kolumny K występuje 0 lub \varepsilon _{{i-1}}^{2}-\varepsilon _{i}^{2}=0.

Dowód twierdzenia.

a) Wybieramy dowolne drzewo spinające T, ukorzenione. Macierz układu równań opisujących obszar dopuszczalny zadany drzewem jest podmacierzą wyjściowego układu więc do wykazania liniowej niezależności możemy przyjąć, że graf jest drzewem spinającym. Dowód przeprowadzimy przez indukcję względem liczby węzłów.

1^{0} Sieć ma 1 wierzchołek i 1 krawędź wychodzącą z niego. Zatem macierzą układu jest M=[1] o maksymalnym rzędzie.

2^{0} Jeżeli sieć ma co najmniej dwa węzły to ma liść w_{j}, który nie jest korzeniem. Usuwamy liść w_{j} i strzałkę s z nim związaną. Zobaczmy jak zmienia się macierz M układu równań. Wiersz indeksowany liściem w_{j} ma tylko jedno miejsce różne od 0 -\pm w kolumnie o indeksie s. Zatem po usunięciu tego wiersza i kolumny rząd macierzy maleje o 1.

ad b) Po odrzuceniu korzenia otrzymujemy podsieć T o n węzłach i n-1 strzałkach, nie mający cykli. A taka sieć jest drzewem.

Algorytm sympleks w sieciach.

Algorytm ten będziemy ilustrować przykładem.

Dane zadanie opisane grafem

opis
Rys. 14.1. sieć.

Liczby w węzłach opisują potencjały zaś na strzałkach koszty.

Jak widać suma potencjałów jest zerowa więc zadanie jest zbilansowane.

Ukorzeniamy graf w węźle w_{1}.

\par
Rys. 14.2. Graf ukorzeniony.

Do rozpoczęcia algorytmu potrzebujemy wierzchołek startowy. Niech będzie nim następujące drzewo spinające:

\par
Rys. 14.3. Schemat przepływu 1.

Czerwone liczby oznaczają wartości zmiennych czyli liczba towaru przepływająca przez strzałkę.

Krok 1 TEST OPTYMALNOŚCI

Budujemy pomocnicze drzewo kosztów. Koszty podróży po strzałkach są te same a liczby w węzłach obrazują koszt spływu jednostki towaru przez korzeń. W przypadku podróży pod prąd koszt strzałki liczymy ze znakiem minus.

\par
Rys. 14.4. Drzewo kosztów 1.

Teraz wyliczamy koszty zredukowane.

\par
Rys. 14.5. Koszty zredukowane 1.

Liczymy koszty zredukowane zgodnie z zasadą: Na węźle w_{i} umieszczamy liczbę d_{i} z drzewa kosztów. Następnie koszt każdej strzałki wychodzącej z w_{i} zmniejszamy o d_{i} zaś koszt każdej strzałki przychodzącej do w_{i} zwiększamy o d_{i}. Wartość funkcji celu zmieni się przy tej ope4racji o stałą d_{i}\cdot V(w_{i}). Metoda obliczania wartości węzłów w drzewie kosztów wymusza zerowe koszty strzałek użytych w schemacie przepływu ( zerowe koszty zmiennych bazowych ).

Koszt zredukowany strzałki s_{{i,j}} między węzłami w_{i} aw_{j} wynosi c_{{i,j}}^{{\prime}}=c_{{i,j}}-d_{i}+d_{j}.

Jeżeli wszystkie strzałki mają koszt nieujemny to STOP badany schemat jest optymalny.

Krok 2. WYBÓR KOLUMNY POPRAWIAJĄCEJ

Wybieramy teraz strzałkę o ujemnym koszcie i dołączamy ją do drzewa. W naszym przykładzie jest to strzałka zaznaczona linią przerywaną z w_{2} do w_{5}.

Krok 3. WYBÓR ELEMENTU CENTRALNEGO

\par
Rys. 14.6. Schemat przepływu 1 uzupełniony.

Pojawia się cykl po którym staramy się przepchnąć jak najwięcej towaru. Dołączoną strzałką podróżuje \Delta jednostek a pozostałymi strzałkami o \Delta mniej lub więcej w zależności od ich zwrotu. Ponieważ zmienne są nieujemne jako \Delta wybieramy minimum z kosztów strzałek przeciwnie zorientowanych niż dodana. W naszym przykładzie \Delta=min\{ 6,7\}=6.

Teraz z grafu wyrzucamy jedną ze strzałek po której nie płynie towar. W naszym przykładzie jest to strzałka z w_{1} do w_{3}. W ten sposób otrzymaliśmy nowy schemat przewozu, który jest drzewem a więc wierzchołkiem obszaru dopuszczalnego. Funkcję celu poprawiliśmy o \Delta pomnożone przez koszt dołączonej strzałki. W naszym przykładzie wyrzucamy strzałkę z w_{1} do w_{3}.

\par
Rys. 14.7. Schemat przepływu 2.

GO TO krok 1

Budujemy drugie drzewo kosztów.

\par
Rys. 14.8. Drzewo kosztów 2.

i wyliczamy koszty zredukowane drugiego schematu przepływu.

\par
Rys. 14.9. Koszty zredukowane 2.

Tym razem ujemny koszt ma strzałka z w_{4} do w_{1}. Dołączamy ją i otrzymujemy cykl:

\par
Rys. 14.10. Schemat przepływu 2 uzupełniony.

W naszym przykładzie \Delta=min\{ 1,2\}=1 więc wyrzucamy strzałkę z w_{2} do w_{1}. Otrzymujemy trzeci schemat przepływu.

\par
Rys. 14.11. Schemat przepływu 3.

Znowu liczymy koszty zredukowane.

\begin{figure}[!ht] \ffig[]{}{}{} \caption{.}  \end{figure}
Rys. 14.12. Drzewo kosztów 3.

[0.5]KZ3Koszty zredukowane 3

Są one nieujemne więc schemat trzeci jest optymalny.

Dwufazowa metod sympleks.

Dana jest sieć G=\{ W,S;k,p\} wraz z potencjałem V. Wprowadzamy dodatkowy (sztuczny ) węzeł o potencjale 0 i strzałki łączące sztuczny węzeł ze wszystkimi pozostałymi tak skierowane by potencjały mogły się wyrównać. Następnie wprowadzamy sztuczną funkcję celu nadając starym strzałkom koszt 0 a sztucznym koszt 1. Dalej stosujemy prosty algorytm sympleks. Jeżeli nie uda się uzyskać przepływu o koszcie 0 to znaczy, że wyjściowe zadanie jest sprzeczne. W przeciwnym przypadku uzyskamy przepływ będący wierzchołkiem obszaru dopuszczalnego.

Przypadek niezbilansowany.

Przypadek niezbilansowany sprowadzamy do zbilansowanego wprowadzając sztuczny węzeł o potencjale przeciwnym do sumy pozostałych potencjałów i strzałki łączące sztuczny węzeł ze wszystkimi pozostałymi. Jeżeli sztuczny węzeł ma potencjał dodatni to wszystkie sztuczne strzałki z niego wychodzą. Jeżeli ujemny to wszystkie sztuczne strzałki mają w nim swój koniec. Dalej stosujemy prosty algorytm sympleks.

Ćwiczenie 14.1

W sieci o strzałkach z nieograniczonymi przepustowościami aktualnie realizowany jest następujący schemat przepływów:

\begin{figure}[!ht] \ffig[]{}{}{} \caption{.}  \end{figure}
Rys. 14.14. Sieć.

[0.5]ZadPSchemat przepływu

Wyznacz przepływ o minimalnym koszcie za pomocą algorytmu sympleks.

Przykład i zadanie w tym wykładzie pochodzą z egzaminów prof. W. Ogryczaka.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.