Siecią nazywać będziemy skończony graf wraz z dwiema funkcjami przypisującą każdemu wierzchołkowi liczbę rzeczywistą zwaną potencjałem i 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 indeksowany strzałkami grafu.
na obszarze opisanym nierównościami:
.
Zauważmy, macierz opisująca powyższe równania ma wiersze indeksowane węzłami a kolumny, z prawej strony kreski, indeksowane strzałkami (lub zmiennymi ). Ponadto kolumna odpowiadająca strzałce ma zera, jedną 1 w wierszu o indeksie i jedną -1 w wierszu o indeksie . W przypadku grafu ukorzenionego strzałką , dochodzi kolumna o indeksie , która ma zera i jedną 1 w wierszu o indeksie
Jak zsumujemy wszystkie równania, dla grafu nieukorzenionego, lewa strona zredukuje się do 0 i otrzymamy:
A zatem ten układ równań jest zależny i jeżeli suma potencjałów jest niezerowa to jest sprzeczny. Zagadnienie gdy 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.
Niech będzie spójnym grafem ukorzenionym w węźle wraz z funkcjami potencjału i kosztów takimi, że . Wówczas:
a) Zbiór równań jest liniowo niezależny.
b) Jeżeli kolumny o indeksach są liniowo niezależne i to podgraf , gdzie jest ukorzenionym drzewem spinającym.
Twierdzenie 14.1 w dalszej części będziemy używać poprzez następujący wniosek.
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.
Niech przebiegający między wierzchołkami
będzie cyklem prostym w sieci . Wówczas kolumny tablicy sympleks indeksowane tymi krawędziami są liniowo zależne.
Dowód lematu. Wprowadźmy orientację na cyklu zgodną z kolejnością węzłów . To znaczy: Niech strzałka przebiega między węzłami i , definiujemy
Badamy kolumnę .
W j - tym wierszu kolumny (w wierszu indeksowanym węzłem ) występuje element
Zatem w j - tym wierszu kolumny występuje lub .
∎Dowód twierdzenia.
a) Wybieramy dowolne drzewo spinające , 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.
Sieć ma 1 wierzchołek i 1 krawędź wychodzącą z niego. Zatem macierzą układu jest o maksymalnym rzędzie.
Jeżeli sieć ma co najmniej dwa węzły to ma liść , który nie jest korzeniem. Usuwamy liść i strzałkę z nim związaną. Zobaczmy jak zmienia się macierz M układu równań. Wiersz indeksowany liściem ma tylko jedno miejsce różne od 0 - w kolumnie o indeksie . Zatem po usunięciu tego wiersza i kolumny rząd macierzy maleje o 1.
ad b) Po odrzuceniu korzenia otrzymujemy podsieć o węzłach i 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
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 .
Do rozpoczęcia algorytmu potrzebujemy wierzchołek startowy. Niech będzie nim następujące drzewo spinające:
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.
Teraz wyliczamy koszty zredukowane.
Liczymy koszty zredukowane zgodnie z zasadą: Na węźle umieszczamy liczbę z drzewa kosztów. Następnie koszt każdej strzałki wychodzącej z zmniejszamy o zaś koszt każdej strzałki przychodzącej do zwiększamy o . Wartość funkcji celu zmieni się przy tej ope4racji o stałą . 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 między węzłami a wynosi .
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 do .
Krok 3. WYBÓR ELEMENTU CENTRALNEGO
Pojawia się cykl po którym staramy się przepchnąć jak najwięcej towaru. Dołączoną strzałką podróżuje jednostek a pozostałymi strzałkami o mniej lub więcej w zależności od ich zwrotu. Ponieważ zmienne są nieujemne jako wybieramy minimum z kosztów strzałek przeciwnie zorientowanych niż dodana. W naszym przykładzie .
Teraz z grafu wyrzucamy jedną ze strzałek po której nie płynie towar. W naszym przykładzie jest to strzałka z do . 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 pomnożone przez koszt dołączonej strzałki. W naszym przykładzie wyrzucamy strzałkę z do .
GO TO krok 1
Budujemy drugie drzewo kosztów.
i wyliczamy koszty zredukowane drugiego schematu przepływu.
Tym razem ujemny koszt ma strzałka z do . Dołączamy ją i otrzymujemy cykl:
W naszym przykładzie więc wyrzucamy strzałkę z do . Otrzymujemy trzeci schemat przepływu.
Znowu liczymy koszty zredukowane.
[0.5]KZ3Koszty zredukowane 3
Są one nieujemne więc schemat trzeci jest optymalny.
Dwufazowa metod sympleks.
Dana jest sieć wraz z potencjałem . 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.
W sieci o strzałkach z nieograniczonymi przepustowościami aktualnie realizowany jest następujący schemat przepływów:
[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.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
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.