Metoda wyznaczania przepływu maksymalnego. Przykład wyznaczania maksymalnego przepływu metodą Forda-Fulkersona
Cykle Hamiltona
Wykres ma postać macierzy, gdzie komórki określają koszt przemieszczania się pomiędzy punktami. Symbol ∞ jest umieszczony na głównej przekątnej, aby wyeliminować bezsensowną ścieżkę do siebie.
Ponieważ Jeśli otrzymana macierz zawiera kolumnę bez elementów zerowych, to znajdziemy w niej element minimalny i odejmiemy go od wszystkich elementów tej kolumny.
| A | B | C | D | |
| A | ∞ | |||
| B | ∞ | |||
| C | ∞ | |||
| D | ∞ |
Podsumujmy wszystkie odjęte elementy i uzyskajmy dolną granicę cyklu w= 2+2+3+2+1=10
1.2. Oceńmy wszystkie zerowe elementy macierzy.
Wygodnie jest przedstawić oszacowanie zer w tabeli.
| A | B | C | D | |
| A | ||||
| B | ||||
| C | ||||
| D |
θ=maks. γ=γ A C =2
1.3. Podzielmy zbiór ścieżek na dwa podzbiory: Q AC– ścieżki zawierające łuk (AC) i Q AC– ścieżki niezawierające łuku (AC). Dla drugiego podzbioru dolna granica będzie wynosić: w / = w + θ =10+2=12.
Aby obliczyć granicę pierwszego podzbioru, przechodzimy do macierzy o rząd wielkości niżej, przekreślając wiersz A i kolumnę C. W nowej macierzy, aby wyeliminować ścieżkę odwrotną (CA), w odpowiedniej komórce umieszczamy znak ∞.
Obliczmy granicę wynikowej macierzy 2+0=2
i dodaj go do dolnej granicy pętli. Ta ilość w // =10+2=12 i będzie granicą pierwszego podzbioru.
1.4. Porównajmy granice wszystkich wiszących wierzchołków i wybierzmy wierzchołek z najmniejszą granicą. Jeśli są dwa z tych wierzchołków, wybierz dowolny z nich. To jest szczyt Q AC, którego dolna granica =12.
Wybierzmy maksimum z szacunków θ=maks. γ=γ BD =3
w / =12+3=15.
1.6. Wszystkie kolejne punkty wykonujemy analogicznie do poprzednich.
Wybierzmy maksimum z szacunków θ=max γ=γ C B =∞
w / =w+ θ=∞
| A | |
| D |
Wszystkie wiersze i kolumny tej macierzy zawierają zera. Zatem granica pozostaje równa 12.
ZADANIE. Znajdź wartość maksymalnego przepływu w sieci transportowej.
SFORMUŁOWANIE PROBLEMU.
Rozważ problem transportu w sieci ( Ja, D, G) przy danych pojemnościach łuku c(i,j).
Wybierzmy dwa stałe wierzchołki: S- źródło i T- odpływ. Streamuj w sieci s → t nazwijmy funkcję numeryczną F, zdefiniowanych na zbiorze łuków i spełniających następujące równania i nierówności liniowe:
0≤ f(i,j) ≤c(i,j) dla każdego (i, j)
Wymagane do maksymalizacji zmiennej X
Cięcie L w sieci oddzielającej wierzchołki s t
zwany zbiorem łuków 
W każdym razie s → t zawiera co najmniej jeden łuk cięcia.
KRYTERIA OPTYMALNOŚCI: w sieci rzeczywistej wartość dowolnego przepływu nie przekracza przepustowości przekroju, a wartość maksymalnego przepływu jest równa minimalnej przepustowości przekroju.
PRZYKŁAD 3.12.
M 9 K
M 8 K
PRZYKŁAD 3.13.
M 2 K
ROZWIĄZANIE :
Nośność łuku wychodzącego (T,B) przekracza całkowitą pojemność łuków wchodzących do odpowiedniego wierzchołka. Aby sieć stała się rzeczywista, zastępujemy c(T,B)=5.
Znajdźmy i obliczmy wartość przepustowości wszystkich cięć. (K,V) – (T,V) cięcie przy minimalnej przepustowości =6. Dlatego maksymalny przepływ =6.
Sieć z kilkoma źródłami i ujściami można zredukować do sieci z jednym źródłem i ujściem.
PRZYKŁAD. Niech będzie kilka źródeł S i pochłaniaczy T (problem transportu). Rozbudujmy sieć dodając dwa węzły s*, t* i wszystkie łuki (s*, S), (T,t*). Zdefiniujmy funkcję pojemności poprzez ustawienie
SPOSÓB UMIESZCZENIA ZNAKÓW.
1. Przepływ początkowy f(i,j) = 0.
Przypiszmy etykiety wierzchołkom tej sieci, które będą miały postać (i+, ε) Lub
(i - , ε). Zaznaczmy źródło (-, ∞),
te . ε(s)= ∞.
2. Dla dowolnego zaznaczonego wierzchołka I
wybierz wszystkie nieoznaczone wierzchołki J
dla którego f(i,j)
Czynność tę powtarzamy aż do zaznaczenia drenażu. Jeśli przepływ pozostaje nieoznaczony, to znaleziony przepływ jest maksymalny, a zbiór łuków łączących zaznaczone wierzchołki z nieoznaczonymi tworzy minimalne cięcie.
3. Niech towar zostanie oznaczony (j+, ε(t)), Następnie f(j,t) zamienić f(j,t)+ε(t). Jeśli zapasy są oznaczone (j-, ε(t)), To f(j,t) zamienić f(j,t)-ε(t). Chodźmy na górę J. Jeśli J ma znak (i+, ε(j)), następnie zastępujemy f(i,j) NA f(i,j)+ε(t), i jeśli (i-, ε(j)), f(j,i) zamienić f(j,i)-ε(t). Chodźmy na górę I. Czynność tę powtarzamy aż dotrzemy do źródła S. Zmiana przepływu zostanie zatrzymana, wszystkie oznaczenia zostaną usunięte i przejdź do kroku 2
PRZYKŁAD 3.14.
M 4 K
| 1 krok | A → (-, ∞) M → (A+,8) P → (A+,3) K → (P+,3) T → (P+,3) B → (T+,3) | f(T,B)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(A,M)=0 f(M,P)=0 f(M,K)=0 f(M,T)=0 f(K,T)=0 f( K,B)=0 |
| Krok 2 | A → (-, ∞) M → (A+,8) P → (M+,1) K → (M+,4) T → (M+,2) | f(K,B)=3 f(M,K)=3 f(A,M)=3 f(T,B)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(M,T)=0 f(M,P)=0 f(K,T)=0 |
| Krok 3 | A → (-, ∞) M → (A+,5) P → (M+,1) K → (M+,1) T → (M+,2) B → (T+,2) | f(T,B)=5 f(M,T)=2 f(A,M)=5 f(K,B)=3 f(M,K)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(M,P)=0 f(K,T)=0 |
| Krok 4 | A → (-, ∞) M → (A+,3) P → (M+,1) K → (M+,1) T → (P+,1) B → (T+,1) | f(A,M)=6 f(T,B)=6 f(P,T)=4 f(M,P)=1 f(M,T)=2 f(K,B)=3 f(M,K)=3 f(A,P)=3 f(P,K)=0 f(K,T)=0 |
| Krok 5 | A → (-, ∞) M → (A+,2) P → (M-,1) K → (M+,1) T → (K+,1) B → (T+,1) | f(A,M)=7 f(M,K)=4 f(K,T)=1 f(T,B)=7 f(P,T)=4 f(M,P)=1 f( M, T) = 2 f(K,B)=3 f(A,P)=3 f(P,K)=0 |
| Krok 6 | A → (-, ∞) M → (A+,1) | Przepływ jest optymalny f=10 Minimalne cięcie: M→T-M→R-M→DO |
ZADANIE. Znajdź najwyższy przepływ w sieci
ALGORYTM
Oznaczmy wierzchołek s= x 0 . Wszystkie inne to x i.
Scena 1.
1. Wybierz dowolną ścieżkę, której łuki nie są nasycone.
2. Zwiększamy wielkość przepływu wzdłuż tej ścieżki o jeden, aż nie będzie w niej nasyconego łuku.
Kontynuujemy proces zwiększania przepływu, aż do zbudowania pełnego przepływu, tj. każda ścieżka będzie zawierać co najmniej jeden nasycony łuk.
Etap 2.
2. Jeżeli х i jest już zaznaczonym wierzchołkiem, to zaznaczamy (+i) wszystkie nieoznaczone wierzchołki, do których przechodzą nienasycone łuki od х i, a indeksem (–i) wszystkie nieoznaczone wierzchołki, z których wychodzą łuki o niezerowym przepływie do х i.
3. Jeżeli w wyniku tego procesu zostanie zaznaczony wierzchołek T, następnie pomiędzy S I T istnieje ścieżka, której wszystkie wierzchołki są oznaczone numerami wierzchołków poprzednich. Zwiększamy przepływ we wszystkich łukach tej ścieżki o jeden, jeśli podczas poruszania się S Do T orientacja łuku pokrywa się z kierunkiem ruchu i jest zmniejszana o jeden, jeśli łuk ma przeciwną orientację. Przejdźmy do kroku 1.
4. Kiedy na górze T nie można oznaczyć procesu jako zakończonego, a powstały przepływ jest największym przepływem w sieci.
NOTATKA. Do etapu 2 można przejść bez ukończenia pierwszego etapu (patrz przykład 3.16).
PRZYKŁAD 3.15.
9
ROZWIĄZANIE:
W danej sieci transportowej stwierdzono pełny przepływ. Nasycone łuki są podświetlane
W tej sieci możesz również zaznaczyć końcowy wierzchołek, a wynik zaznaczenia będzie taki sam. Zmieniając przepływ, otrzymujemy sieć, w której nie można wyznaczyć końcowego wierzchołka, więc przepływ w niej jest największy i równy 10.
PRZYKŁAD 3.16.
8 2 1
Na danej sieci transportowej stwierdzono niepełny przepływ
Oznaczmy sieć i zwiększmy w niej przepływ zgodnie z algorytmem. Dostajemy
W tej sieci możesz również zaznaczyć końcowy wierzchołek, a wynik zaznaczenia będzie taki sam. Zmieniając przepływ, otrzymujemy sieć, w której nie można wyznaczyć końcowego wierzchołka, więc przepływ w niej jest największy i równy 6.
Sekcja IV. PROGRAMOWANIE DYNAMICZNE.
Programowanie dynamiczne służy do znalezienia optymalnych rozwiązań wieloetapowych. Na przykład długoterminowe planowanie wymiany sprzętu; działalności branży na przestrzeni wielu lat. Wykorzystuje zasadę optymalności, zgodnie z którą każde nowe rozwiązanie cząstkowe musi być optymalne w stosunku do stanu osiągniętego.
Lepiej rozwiązać jeden prosty problem wiele razy, niż raz rozwiązać trudny.
PROBLEM 1. O najkorzystniejszej trasie pomiędzy dwoma punktami.
Wymagane jest zbudowanie ścieżki łączącej dwa punkty A i B, z czego drugi leży na północny wschód od pierwszego. Dla uproszczenia załóżmy, że wytyczenie ścieżki składa się z szeregu kroków, a na każdym kroku możemy poruszać się albo na północ, albo na wschód. Wtedy dowolna ścieżka jest schodkową linią przerywaną, której odcinki są równoległe do jednej z osi współrzędnych. Znane są koszty budowy każdego z tych odcinków.
PRZYKŁAD 4.1. Znajdź minimalną ścieżkę z A do B.
Ostatnim krokiem jest osiągnięcie T.V. Przed ostatnim krokiem mogliśmy dotrzeć do punktów, z których jednym krokiem mogliśmy dotrzeć do telewizji. Istnieją dwa takie punkty (system może znajdować się w jednym z dwóch stanów). Dla każdego z nich istnieje tylko jedna możliwość dotarcia do t.V: w przypadku jednego - ruch na wschód; dla drugiego - na północ. Zapiszmy w każdym przypadku koszty 4 i 3.
4
Teraz zoptymalizujmy przedostatni krok. Po poprzednim kroku moglibyśmy znaleźć się w jednym z trzech punktów: C 1, C 2, C 3.
Dla punktu C 1 jest tylko jedna kontrola (zaznaczmy ją strzałką) - przejdź na wschód, a koszt wyniesie 2 (w tym kroku) + 4 (w następnym kroku) = 6. Podobnie dla pozycji C 3 koszty będą wynosić 2+3=5. Dla t.C 2 są dwie możliwości kontroli: idź na wschód lub na północ. W pierwszym przypadku koszty wyniosą 3+3=6, a w drugim – 1+4=5. Oznacza to, że warunkowa optymalna kontrola ma zmierzać na północ. Zaznaczmy to strzałką i wpiszmy odpowiednie koszty.
| |
| |
| |
| ZADANIE 2. O załadunku samochodu (o plecaku). Jest N elementów. Znana waga ja i wartość φi każda sztuka. Wymagane do wypełnienia plecaka zdolnego utrzymać ≤ ciężaru R , taki zestaw przedmiotów, który miałby największą wartość.
Proces załadunku plecaka można podzielić na N kroków. Na każdym kroku stawiamy sobie pytanie: brać ten przedmiot czy nie? Na każdym kroku są tylko 2 kontrole: kontrola =1, jeśli weźmiemy ten element; i 0 – jeśli tego nie weźmiemy. Stan układu przed kolejnym krokiem charakteryzuje się wagą S, która pozostaje do naszej dyspozycji aż do zakończenia pełnego obciążenia po wykonaniu poprzednich kroków (część elementów została już załadowana), tj. ilość wolnego miejsca w plecaku. ALGORYTM. 1. Zacznijmy od ostatniego kroku. Przyjmijmy różne założenia dotyczące wolnej przestrzeni w plecaku: S=0,1,…R. Ostatnią rzecz włóżmy do plecaka, jeśli ma wystarczająco dużo miejsca do przechowywania. 2. Na każdym poprzednim kroku, dla wszystkich możliwych stanów S, rozważamy 2 możliwości: wziąć lub nie wziąć przedmiotu. Znajdźmy zysk w każdym przypadku jako sumę zysków w bieżącym kroku i w kolejnym, już zoptymalizowanym kroku. Wyniki wpiszemy do tabeli pomocniczej. 3. W pierwszym kroku rozważamy tylko jedyny możliwy stan S=R. 4. Znajdźmy rozwiązanie „cofając się”, tj. Przejmując optymalną kontrolę w pierwszym kroku, w drugim kroku zmieniamy stan systemu: S=R– x 1 do 1 i wybierz optymalną kontrolę x 2 dla tego stanu. Itp. PRZYKŁAD 4.2. Wstępne dane
Główny stół
Stół pomocniczy.
Odpowiedź: x 4 = 0; x 3 = 1; x2 =0; x 1 = 1; W=15 ZADANIE 3. O podziale zasobów. Istnieje N przedsiębiorstw P 1, P 2,… P N, z których każde generuje dochód φ k (x), jeśli przydzielono mu zasób w wysokości x. Wymagane jest rozdzielenie zasobu dostępnego w ilości A pomiędzy obiekty tak, aby całkowity dochód był maksymalny. Niech x k będzie ilością zasobów przydzielonych k-temu przedsiębiorstwu. Następnie rozważany problem sprowadza się do konwencjonalnego problemu programowania nieliniowego.
Sformułujmy problem jako problem programowania dynamicznego. W pierwszym kroku zajmiemy się inwestycją środków w przedsiębiorstwo P 1, w drugim – w P 2 itd. Systemem zarządzanym w tym przypadku są dystrybuowane środki. Stan systemu przed każdym krokiem charakteryzuje jeden parametr – dostępny stan środków, które nie zostały jeszcze zainwestowane. W tym problemie kontrolą krokową są środki przyznane przedsiębiorstwom. Należy znaleźć optymalną kontrolę (x 1, x 2,...x N), przy której całkowity dochód jest maksymalny: | 1,1 0,5 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=3 | 0,1 0,5 | 1,1 1,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=4 | 0,1 0,5 | 2,1 1,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=5 | 0,1 0,5 2,5 | 3,1 2,5 2,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| i=1 S=5 | 0,5 1,5 | 3,1 1,1 | 3,1 3,5 2,1 2,6 |
Odpowiedź: x 1 = 1; x 3 = 0; x 3 = 4; W=3,5
ALGORYTM OGÓLNY
1. Opisz system. Oznacza to, że przed każdym krokiem dowiedz się, jakie parametry charakteryzują stan kontrolowanego układu. Ważne jest, aby móc poprawnie i „skromnie” postawić zadanie, nie obciążając go niepotrzebnymi szczegółami, maksymalnie upraszczając opis sterowanego systemu.
2. Podziel operację na etapy (etapy). Należy tu wziąć pod uwagę wszystkie uzasadnione ograniczenia nałożone na kierownictwo. Krok musi być na tyle mały, aby procedura optymalizacji sterowania krokowego była dość prosta; przy czym krok nie powinien być zbyt mały, aby nie wykonywać zbędnych obliczeń, które komplikują procedurę znalezienia rozwiązania optymalnego, ale nie prowadzą do istotnej zmiany optymalnej funkcji celu.
3. Znajdź zestaw kontroli kroków x i dla każdego kroku i nałożone na nie ograniczenia.
4. Określ, jakie wzmocnienie przynosi sterowanie x i w i-kroku, jeżeli wcześniej układ znajdował się w stanie S, tj. zapisz funkcje wypłaty:
w ja = f ja (S, x i)
5. Określ, jak zmienia się stan układu pod wpływem sterowania x i w pierwszym kroku, tj. napisz funkcje zmiany stanu.
S / =φ i (S, x i)
6. Zapisz główne równanie programowania rekurencyjnego, wyrażające warunkowe optymalne wzmocnienie poprzez znaną już funkcję
W i (S)= max(f i (S, x i)+W i+1 (φ i (S, x i)))
7. Przeprowadź optymalizację warunkową ostatniego kroku, przyjmując różne założenia dotyczące zakończenia przedostatniego kroku i dla każdego z tych założeń znajdź warunkową (wybraną na podstawie warunku, że krok zakończył się czymś) optymalną kontrolę na ostatnim kroku.
W m (S)= max(f m (S, x m))
8. Wykonaj optymalizację warunkową, zaczynając od przedostatniego kroku i kończąc na pierwszym kroku (cofanie się).
9. Przeprowadzić bezwarunkową optymalizację sterowania, „odczytując” odpowiednie zalecenia na każdym kroku: w pierwszym kroku przyjąć znalezione optymalne sterowanie i zmienić stan systemu, znaleźć optymalne sterowanie dla znalezionego stanu w drugim kroku itp. aż do ostatniego kroku.
ZASADA OPTYMALNOŚCI. Niezależnie od stanu systemu przed kolejnym krokiem, należy na tym etapie wybrać sterowanie tak, aby wzmocnienie na tym etapie plus optymalne wzmocnienie na wszystkich kolejnych etapach było maksymalne.
Zasada programowania dynamicznego nie oznacza, że każdy krok jest optymalizowany oddzielnie, niezależnie od pozostałych. Jaki sens ma wybieranie kontroli, której skuteczność jest maksymalna na jednym konkretnym etapie, skoro krok ten pozbawi nas możliwości dobrego zwycięstwa na kolejnych etapach?
W praktyce zdarzają się przypadki, gdy operację trzeba planować na czas nieokreślony. Modelem takiego przypadku jest proces kontrolowany o nieskończonych krokach, w którym wszystkie etapy są równe. Tutaj funkcja wygrywająca i funkcja zmiany stanu nie zależą od numeru kroku.
Rozdział V. MODELOWANIE SYMULACYJNE
Skrajny przypadek: jeśli wszystkie matryce mają ten sam kolor – odpowiedź brzmi 0.Dodajmy fikcyjne źródło i drenażu. Od źródła do wszystkich białych wierzchołków rysujemy krawędzie o wadze B (koszt przemalowania ich na kolor czarny). Od czarnych wierzchołków do odpływu rysujemy krawędzie o wadze W (koszt przemalowania na biało). A pomiędzy wszystkie sąsiednie wierzchołki (niezależnie od tego, czy mają ten sam kolor, czy różne) umieszczamy krawędź o wadze G (szara linia). Odpowiedzią na problem będzie wartość maksymalnego przepływu.
Źródło: Ogólnoukraińska Olimpiada Szkolna z Informatyki, 2007, dzień 1
Rozwiązanie
Wystarczy podzielić każdy wierzchołek na dwa i pomiędzy nimi umieścić krawędź o wadze równej ograniczeniom nośności tego wierzchołkaRozwiązanie
W klasycznym problemie minimalnego cięcia krawędzie muszą zostać usunięte. Bez problemu! Podzielmy wierzchołki na 2 i umieśćmy między nimi krawędź o wadze 1. Wtedy odpowiedzią na problem jest znalezienie w grafie minimalnego przecięcia (czyli przepływu maksymalnego).Źródło: Zimowa szkoła programowania w Charkowie, 2009, dzień 3
Po przejściu automatu od i do j wzdłuż krawędzi k, wszystkie przejścia od i wzdłuż krawędzi k, jak również wszystkie przejścia do j wzdłuż krawędzi k, ulegają skasowaniu. Należy wydrukować liczbę ścieżek od A do B wzdłuż takiego automatu.
Rozwiązanie
Problem sprowadza się do znalezienia maksymalnej liczby ścieżek, w których z jednego wierzchołka nie wychodzi więcej niż jedna krawędź tego samego koloru. Sprowadźmy problem do znalezienia maksymalnego przepływu. Dla każdego wierzchołka w przebudowanej sieci utworzymy k+1 wierzchołków. Pierwszy wierzchołek będzie wejściem, pozostałe wierzchołki będą reprezentować kolory. Z wierzchołka wejściowego rysujemy wzdłuż krawędzi o pojemności 1 do każdego z k wierzchołków odpowiadających kolorowi. Z wierzchołków odpowiadających kolorowi i rysujemy wszystkie krawędzie koloru i do wejść końcówek krawędzi. Po znalezieniu maksymalnego przepływu w takiej sieci uzyskujemy maksymalną liczbę ścieżek spełniających wymaganą właściwość.Rozwiązanie
Zbudujmy sieć. Utwórzmy jeden wierzchołek dla każdego rodzaju monety. Te blaty będą odpowiadać Twoim monetom. Musimy zebrać jak najwięcej unikalnych monet, dlatego z każdego takiego wierzchołka rysujemy krawędź pojemności 1 do zlewu. Na wierzchołkach odpowiadających monetom, które początkowo posiadasz, narysujemy krawędź, której pojemność będzie równa liczbie posiadanych przez Ciebie takich monet.Dla każdego członka klubu (z wyjątkiem 1, czyli Ciebie) utworzymy po jednym wierzchołku. Wierzchołek ten może przyjąć co najwyżej jedną monetę, której nie ma i dać
co najwyżej k-1 monet, z czego ma k (k > 1). Naturalnie członek klubu oddaje jedną monetę w zamian za otrzymaną.
Zatem do każdego takiego wierzchołka należy narysować krawędź pojemności 1 z wierzchołków odpowiadających monetom, których dany członek klubu nie posiada. I z tych wierzchołków należy narysować krawędzie o pojemności k i - 1 do wierzchołka i, odpowiadające monetom, których członek klubu ma więcej niż jedną.
Zbudowana sieć odzwierciedla procesy wymiany zachodzące w klubie. Maksymalny przepływ w takiej sieci będzie równy maksymalnej liczbie monet, które możesz zebrać.
Źródło: Zimowa szkoła programowania w Charkowie, 2009, dzień 4
Podano opis układu chłodzenia. Konieczne jest sprawdzenie, w jaki sposób ciecz może przepływać przez rury, aby spełnione były wszystkie określone warunki.
Rozwiązanie
Jest to problem znalezienia obiegu w sieci przy danych mniejszych ograniczeniach na krawędziach. Jeżeli przepływ musi przebiegać wzdłuż krawędzi (u, v) w segmencie , to przebudowana sieć będzie miała trzy krawędzie (od, do, waga): (u, v, r - l), (S, v, l) , (u, T, l). S, T - dodatkowo wprowadzono odpowiednio dren i źródło. Tak naprawdę przepuszczamy wymagany minimalny przepływ wzdłuż krawędzi, a następnie równoważymy go tak, aby uzyskać cyrkulację.Rozwiąż zadanie znalezienia maksymalnego przepływu w sieci transportowej za pomocą algorytmu Forda-Fulkersona i skonstruuj odcinek sieci S.
Wstępne dane:
Biorąc pod uwagę sieć S(X,U)
- źródło sieci; - odpływ sieciowy, gdzie ∈X; ∈X.
Wartości mocy łuku podawane są w kierunku orientacji łuku: od indeksu i do indeksu j.
r = 39; r = 44; r = 33; r = 53; r = 10;
r = 18; r = 95; r = 16; r = 23; r = 61;
r = 81; r = 71; r = 25; r = 15; r = 20
1. Ustaw zerowy przepływ w sieci (na wszystkich łukach wartość przepływu wynosi 0). Przepływ zerowy to początkowy dozwolony przepływ w sieci. Wartość przepływu na każdym łuku będzie wskazywana poza wydajnością łuku.). Wartość przepływu równa „0” nie jest określona.
2. Wybierz (dowolnie) ścieżkę w sieci prowadzącą od wierzchołka x0 do wierzchołka x7:
X0-X1-X4-X6-X7
3. Znajdź 
i zwiększyć przepływ o tę ilość. Krawędź X1-X4 jest oznaczona jako brana pod uwagę. 
4. Wybierz inną ścieżkę, na przykład: X0-X2-X5-X7, znajdź 
i zwiększyć przepływ o tę ilość. Krawędź X0-X2 jest oznaczona jako brana pod uwagę. 
5. Wybierz inną ścieżkę, np.: X0-X3-X2-X5-X7, znajdź i zwiększ przepływ o tę wartość. Krawędź X3-X2 jest oznaczona jako brana pod uwagę. 
6. Nie ma już ścieżek od X0 do X7, podsumujmy wzrost przepływu: 25+10+20=55.
Wniosek: maksymalny przepływ wynosi 55.
2) Zbuduj odcinek sieci S.
Procedura „oznaczania wierzchołków”.
Stan początkowy: wszystkie wierzchołki są nieoznaczone.
Wierzchołek X0 ma przypisaną etykietę. Wszystkim wierzchołkom, dla których łuk nie jest nasycony, przypisane są znaczniki (czerwone kółka) 
Definiujemy łuki o minimalnym przekroju: są to łuki, których początek znajduje się w oznaczonych wierzchołkach, a końce w nieoznaczonych wierzchołkach.
Oto łuki:
Zatem minimalne cięcie tej sieci 
Obliczanie maksymalnej wartości przepływu
Planując racjonalną dystrybucję produktów w sieci dystrybucyjnej, należy skoordynować przepustowość kanału z potrzebami klientów oraz z wydajnością zakładu produkcyjnego. Problemy tej klasy rozwiązuje się poprzez znalezienie maksymalnego przepływu.
Rozważmy sieć dystrybucyjną (ryc. 4.21), w której punkty 0 (wejście np. do magazynu producenta wyrobów gotowych) i P (wyjście, centra dystrybucyjne, magazyny organizacji hurtowych i detalicznych, konsument) i każdy punkt połączenia łuku (segmentu). I I J, powiązana jest liczba dij > 0, tzw wydajność łuki. Wartość przepustowości charakteryzuje maksymalną dopuszczalną ilość przepływu materiału, który może przejść wzdłuż odpowiedniego łuku w jednostce czasu.
Ryż. 4.21.
Ilość produktów przechodzących po łuku I zanim J , nazwiemy to przepływem po łuku ( I ,J ) i oznaczone przez . To oczywiste
Jeśli weźmiemy pod uwagę, że cały przepływ materiału wchodzący do punktu pośredniego sieci musi go całkowicie opuścić, otrzymamy
Z naturalnego wymogu równości przepływów na wejściu i wyjściu mamy
Wartość Z nazwiemy wartością przepływu w sieci i postawimy problem maksymalizacji Z przy spełnieniu powyższych warunków.
Znalezienie maksymalnego przepływu sprowadza się do znalezienia przepustowości minimalnego cięcia.
Rozważmy uniwersalny algorytm wyszukiwania w postaci macierzowej.
Początkowy etap algorytmu polega na skonstruowaniu macierzy D 0, w którym wprowadzane są wartości przepustowości (dla łuku niezorientowanego przyjmujemy symetryczne wartości elementów macierzy).
Główne kroki algorytmu polegają na znalezieniu określonej ścieżki i skorygowaniu przepływu wzdłuż tej ścieżki.
Szukając ścieżki, stosujemy proces zaznaczania. Symbolem * oznaczamy zerowy wiersz i kolumnę macierzy (wejście sieciowe). W wierszu 0, którego szukamy, zaznacz odpowiednie kolumny indeksami
i przenieś etykiety kolumn do wierszy. Następnie bierzemy i-ty zaznaczony wiersz, szukamy w nim nieoznaczonej kolumny z , do której dopasowujemy etykiety indeksu
Przenosimy etykiety kolumn do wierszy i kontynuujemy ten proces, aż zostanie zaznaczona n-ta kolumna.
Następnie za pomocą indeksów znajdujemy ścieżkę prowadzącą do η-tego wierzchołka za pomocą indeksów i zmniejszamy pojemność łuków ścieżki (elementów macierzy) przez V n i zwiększ elementy symetryczne o tę samą wartość.
Ta procedura jest kontynuowana aż do zaznaczenia N -topy nie staną się niemożliwe.
Maksymalny strumień można znaleźć, odejmując od oryginalnej macierzy D 0, otrzymane po powyższej korekcie macierzy pojemności:
Przykład 4.4
Produkcja zlokalizowana jest w Moskwie. Do dystrybucji produktów firma przyciąga pośredników, którzy współpracują z firmą poprzez centra dystrybucyjne na różnych poziomach. W europejskiej części Rosji istnieje przedsiębiorstwo hurtowe 1, obsługiwane przez centralne centrum dystrybucyjne. Hurtownia 2 działa na terenie bliskiej zagranicy (Ukraina, Białoruś) i obsługiwana jest przez regionalne centrum dystrybucyjne. Firma ma swoich klientów na rynku lokalnym (Moskwa i obwód moskiewski) - sprzedawców detalicznych, którzy otrzymują produkty z miejskiego centrum dystrybucyjnego. Zaopatrzenie regionalnych i miejskich centrów dystrybucyjnych odbywa się z centralnego centrum dystrybucyjnego.
Wyróżnijmy fragment sieci dystrybucji:
- magazyn gotowych produktów przedsiębiorstwa produkcyjnego;
- centralne centrum dystrybucyjne;
- regionalne centrum dystrybucyjne;
- miejskie centrum dystrybucyjne;
- dwa przedsiębiorstwa hurtowe;
- punkt sprzedaży detalicznej będący własnością firmy;
- konsumenci.
Ryż. 4.22.
Oznaczmy każde ogniwo sieci dystrybucyjnej numerem, a nad łukami umieśćmy pojemność. Zdolność przerobową, w zależności od rodzaju połączenia, można wyrazić w kategoriach wielkości zdolności produkcyjnych, planowanego zapotrzebowania (popytu) odbiorców i zdolności rynkowej.
Wykres sieci dystrybucji produktów pokazano na ryc. 4.23. Zbudujmy macierz D 0, w którym wpisujemy wartości przepustowości łączy sieci dystrybucyjnej (rys. 4.24).
Ryż. 4.23.
Ryż. 4.24.
Z wiersza zerowego zaznaczamy wierzchołki (wiersze-kolumny) 1, 2 i 3 indeksami μ = 0 i V, równe 30,10 i 10.
Z zaznaczonej linii 1 zaznacz wierzchołki 4 i 5 o indeksach μ = 1 i V4 = min (30,15) = 15, V5 = min (30,10) = 10.
Z linii 3 zaznaczamy wierzchołek 6 i ostatecznie z linii 4 – wierzchołek 7 (ryc. 4.25).
Ryż. 4,25.
Wracając wzdłuż μ, znajdujemy ścieżkę: do wierzchołka 7 od 4, do wierzchołka 4 od 1, do wierzchołka 1 od 0; elementy regulacyjne D 0 na wartość przepływu V7 = 15.
Następny krok daje ścieżkę z przepływem 5 (ryc. 4.26).
Ryż. 4.26.
W kolejnym kroku uzyskany zostanie efekt pokazany na rys. 4,27.
Ryż. 4,27.
Dalsze oznaczenie nie jest możliwe. Stąd otrzymujemy macierz maksymalnego przepływu (ryc. 4.28).
Ryż. 4,28.
W wyniku zastosowania algorytmu wyznaczania maksymalnego przepływu w sieci uzyskano wyniki przedstawione na rys. 4,29. Pary liczb w nawiasach pokazane na łukach wykresu oznaczają maksymalną przepustowość łuku oraz zalecaną ilość towarów dostarczanych do sieci.
Algorytm obliczania maksymalnego przepływu w sieciach
KROK 1. Wstępne zadania. Aktualna wartość Na Maksymalnemu przepływowi w sieci przypisuje się wartość 0. KROK 2. Wybór niezależnych tras w sieci i określenie przepływów w nich. Z całego zestawu możliwych tras w sieci od źródła do ujścia wybieramy trasy niezależne M 1 , … , M k, nie mający żadnych wspólnych wierzchołków poza początkowym (źródło v i) i końcowy (odpływ v z). Dla każdej wybranej trasy M ja(1£ I£ k) określić maksymalny przepływ A(M ja)KROK 3. Korekta aktualnej wartości maksymalnego przepływu w sieci. Dodajemy te znalezione na KROK 2 wartości maksymalnych przepływów w niezależnych trasach M 1 , … , M k do aktualnego całkowitego maksymalnego przepływu w sieci: Na:= At + A(M 1)+ A(M 2)+…+ A(M k)KROK 4. Korekta sieci. Znalezione na KROK 2 maksymalne przepływy A(M 1), … , A(M k) odjęta od pojemności odpowiednich łuków sieciowych. Łuki o zerowej pojemności resztkowej są usuwane. KROK 5. Sprawdzenie kompletności algorytmu. Jeżeli po korekcie w sieci nie ma żadnych tras ze źródła v i do zapasów v z, wówczas wymagany maksymalny przepływ w sieci jest równy znalezionemu prądowi A:= T, algorytm kończy działanie, ponieważ cała przepustowość sieci została wyczerpana. Jeżeli w dostosowanej sieci znajdują się trasy ze źródła v i do zapasów v z, następnie idź do KROK 2 i kontynuacja wykonywania algorytmu . Przykład 2. Znajdź maksymalny przepływ w sieci na ryc. 1.15, korzystając z tego algorytmu. Rozwiązanie.KROK 1. Zadania wstępne. Na: = 0.I iteracja. KROK 2. Wybór niezależnych tras w sieci i określenie przepływów w nich. Jak M 1 wybierz trasę ( v i = V 1 , V 2 , V 5 , vs =V 7), rozważane w przykładzie 1. Dla niego A(M 1) = 10.
Łatwo jest również wyizolować niezależnie M 1 trasa M 2 = (v i = V 1 , V 3 , V 6 , vs =V 7). Obliczmy dla niego maksymalną przepustowość i dostosujmy przepustowość łuków: A(M 2)=min{D 13 ,D 36 ,D 67 } =min{45, 40, 30} = 30. D 13 ¢ =d 13 - 30 = 15,D 36 centów =d 36 - 30 = 10,D 67 centów =d 67 - 30 = 0.
KROK 3. Korekta aktualnej wartości maksymalnego przepływu w sieci. Na:= At + A(M 1)+ A(M 2) = 0 + 10+ 30 = 40.KROK 4. Korekta sieci. Znalezione na KROK 2 maksymalne przepływy A(M 1), A(M 2) w trasach M 1 , M 2 odejmuje się od pojemności ich łuków. Łuki o zerowej pojemności resztkowej są usuwane. Wynik przedstawiono na ryc. 1.16 a. a) b) Ryc. 1.16. Wynik korekty sieci po iteracjach I I IISTEP 5. Sprawdzenie kompletności algorytmu. W skorygowanej sieci (ryc. 1.16 a) istnieją trasy od źródła v i do zapasów v z, Na przykład M 3 = (v i = V 1 , V 4 , V 2 , V 5 , vs =V 7). Kontynuacja wykonywania algorytmu .II iteracja. KROK 2. Jako jedyna niezależna trasa, którą podążamy M 3 = (v i = V 1 , V 4 , V 2 , V 5 , vs =V 7). Dla niego:
A(M 3)=min{D 14 ,D 42 ,D 25 ,D 57 } =min{15, 10, 10, 15} = 10.
D 14 ¢ =d 14 - 10 = 5,D 42 ¢ =d 42 - 10 = 0,D 25 centów =d 25 - 10 = 0,D 57 centów =d 57 - 10 = 5.
KROK 3. O godz:= At + A(M 3) = 40 + 10= 50.KROK 4. Korekta sieci. Maksymalny przepływ A(M 3) odjąć od łuków trasy M 13 . Wynik przedstawiono na ryc. 1.16 b.
KROK 5. W dostosowanej sieci nie ma już żadnych tras od źródła do ujścia. A:= T:= 50, zakończenie algorytmu. Odpowiedź: maksymalny przepływ w sieci na ryc. 1.15 wynosi 50.Jeżeli w sieci przewidziano kilka źródeł, uzupełnieniem tego jest wprowadzenie nowego wspólnego źródła, które łączy się ze źródłami pierwotnymi łukami o nieograniczonej przepustowości. Następnie problem rozwiązuje się za pomocą zwykłego algorytmu. Wymagane przepływy przez pierwotne źródła będą przepływami wzdłuż nowo dodanych łuków wpływających do nich z nowego wspólnego źródła. Zrób to samo, jeśli w sieci jest kilka odpływów.
Planowanie sieci
Każde zadanie polegające na projektowaniu lub budowie dość złożonego obiektu (np. projekt) można podzielić na kilka mniejszych etapów składowych. Od prawidłowego wyboru kolejności tych kroków zależy czas realizacji całego projektu.
Cały zakres działań mających na celu realizację projektu przedstawiony jest jako zbiór wydarzenia I Pracuje. Zdarzenia nazywane są poszczególnymi etapami projektu. Praca to proces jej dopełniania. Cały kompleks wydarzeń i prac niezbędnych do realizacji projektu można przedstawić w postaci dwubiegunowej sieci G =({v i v z} , V, X), w której:
i wszystkich wydarzenia oznaczone zbiorem wierzchołków V, wśród nich wyróżniony wydarzenie początkowe v i(rozpoczęcie pracy) i wydarzenie końcowe v z(zakończenie całego projektu) definiują wierzchołki wewnętrzne sieci zdarzenia pośrednie- etapy, które należy wykonać w trakcie realizacji projektu,
b) wszystko praca są oznaczone łukami łączącymi pary zdarzeń - wierzchołki.
Graficzna reprezentacja tej sieci nazywa się internetowy diagram. Aby wskazać kolejność działań, wprowadź także schemat sieci dzieła fikcyjne, które nie są związane z wykonaniem jakichkolwiek czynności. Odpowiednie prace są oznaczone przerywanymi łukami.
Jako przykład rozważmy organizację jakiejś produkcji. Projekt wymaga następujących prac:
I) badania marketingowe, II) badania przedprojektowe urządzeń, III) organizacja sieci sprzedaży, IV) prowadzenie kampanii reklamowej, V) opracowanie specyfikacji technicznych urządzeń produkcyjnych, VI) opracowanie dokumentacji technicznej pomieszczeń produkcyjnych i komunikacji, VII) zakup wyposażenia standardowego, VIII) projektowanie i produkcja sprzętu niestandardowego, IX) budowa obiektów produkcyjnych i montaż łączności, X) montaż wyposażenia standardowego, XI) montaż wyposażenia niestandardowego, XII) uruchomienie.
Prace te oznaczymy na schemacie sieci łukami z odpowiednimi liczbami.
Wydarzenia w ramach tego projektu będą następujące:
1) rozpoczęcie prac (zdarzenie początkowe), 2) zakończenie badań marketingowych, 3) zakończenie badań przedprojektowych, 4) organizacja sieci sprzedaży, 5) organizacja kampanii reklamowej, 6) przygotowanie specyfikacji technicznych produkcji urządzeń, 7) zakończenie opracowywania dokumentacji technicznej pomieszczeń produkcyjnych i komunikacji, 8) zakończenie zakupu wyposażenia standardowego, 9) zakończenie projektowania i wykonania urządzeń niestandardowych, 10) zakończenie budowy obiektów produkcyjnych i montaż łączności, 11) zakończenie prac instalacyjnych i uruchomieniowych,
12) zakończenie projektu (impreza końcowa).
Wierzchołki kojarzymy z odpowiednimi liczbami ze zdarzeniami. Harmonogram sieci dla projektu pokazano na ryc. 1.17:
Ryc.1.17. Harmonogram sieci realizacji projektu
