Lekcja 9. Elementy programowania sieciowego i dynamicznego.

9.1. Zadania programowania sieciowego i dynamicznego.

9.2. Pojecie grafu. Uporządkowanie grafu metodą Falkersona.

9.3. Elementy analizy sieci przedsięwzięcia wieloczynnościowego. Analiza czasowa.

9.4. Zasady programowania dynamicznego. Funkcjonalne równania Bellmana.

9.5. Przykłady rozwiązania zadania metodami programowania sieciowego i dynamicznego.

9.1. Zadania programowania sieciowego i dynamicznego.

Odrębną grupę zagadnień programowania matematycznego stanowią zagadnienia sieciowe. Są to zagadnienia, których ilustrację graficzną można przedstawić w formie figury płaskiej noszącej nazwę grafu, utworzonej z wyróżnionych punktów — zwanych węzłami grafu i odcinków łączących określone pary węzłów, zwanych łukami grafu.

Dla rozwiązania takich zadań istnieją specjalne matematyczne metodę - teoria grafów, metody planowania dynamicznego, teoria planowania i inne.

Zaznaczymy niektóry zadania programowania sieciowego.

1.1. Zadanie transportowe z optymalnym czasem przewozu.

Niech mamy m punktów (magazynów) z zasobami surowców (towaru, ładunków) odpowiednie a₁, a₂, ... , a_m i n punktów (przedsiębiorstw, sklepów) z zapotrzebowaniami w surowcach b₁, b₂, ... , b_n. Punkty i i j połączony drogami z czasem przewozu t_ij.

Potrzebnie znaleźć taki plan przewozu surowców (towaru, ładunków), żeby wykonać zapotrzebowanie przedsiębiorstw i czas przewozów był najmniejszy.

1.2. Zadanie komiwojażera.

Komiwojażer (menedżer) reklamuje towar w n miastach, połączonych siecią dróg (i-te miasto połączone z j-em drogą odległością a_ij). Komiwojażer wyjeżdża z miasta 1 i musze przejechać przez wszystkie miasta 2, 3, ... n i wrócić z powrotem w miasto 1.

Jaką drogą potrzebnie jemu jechać, żeby ogólna długość kierunku była najmniejsza (czas przejazdu najkrótszy, koszty przejazdu najtańsze) ?

1.3. Zadanie planowania sieciowego (zadanie o rozkładach).

Potrzebnie wykonać niektórą pracą, zaczynając od zdarzenia 1 (początek) do zdarzenia N (koniec). W ciągu pracy mamy zdarzenia 2, 3, ... , i , ..., N-1. Zdarzenia z numerami i i j (i,j = 1,2, ... N) mogą być związany między sobą odcinkom czasu t_ij. Potrzebnie znaleźć plan najkrótszego rozwiązania pracy.

Niektóry zadania programowania dynamicznego.

1.4. Zadanie wymiany sprzętu.

Przedsiębiorstwo ma sprzęt, na którym za rok z numerem t produkuje się towar kosztem r(t). Wydatki na utrzymanie tego sprzętu w ciągu roku t są u(t); p(t) - cena nowego sprzętu, s(t) - cena, za którą można sprzedać ten sprzęt w roku t.

Potrzebnie znaleźć plan takiej wymiany sprzętu w ciągu T lat, że by otrzymać największy zysk ot jego wykorzystania.

1.5. Zadanie o podziale (dystrybucji) środków.

Firma ma sumą X (pieniądz, sprzętu lub inne) dla modernizacji swoich N przedsiębiorstw. Jeżeli i-mu przedsiębiorstwu wydzielić sumą x_i, to firma otrzymuje zysk z_i.

Potrzebnie tak podzielić sumą X, żeby firma otrzymała największy zysk od swoich przedsiębiorstw.

9.2. Pojecie grafu. Uporządkowanie grafu metodą Falkersona.

Jedno z najważniejszych pojęć programowania sieciowego jest pojecie grafu.

Niech mamy W - zbiór elementów, który nazywamy wierzchołkami grafu i L - zbiór relacji między elementami zbioru W, zwanych lukami grafu (rys. 1).

Definicja 1. Zbiór G=<W,L> wierzchołków i luk nazywa się grafem.

Jeżeli luki nie skierowany, to graf nazywa się nie skierowanym. Odpowiednie, jeżeli luki skierowany, to graf nazywa się skierowanym lub grafem orientowanym (rys. 2).

Rys. 1.

Jeżeli luka wychodzi i wchodzi w ten samy wierzchołek, to graf nazywa się grafem z pętlami. Na przykład, na rys. 1 wierzchołek 1 ma dwie pętli, wierzchołek 4 - jedną pętlą.

Jeżeli na zbiór W lub na zbiór L nałożony (nie nałożony) warunki, to graf nazywa się obciążonym (nie obciążonym)

Grafy można zaznaczyć w postaci macierzowej. Jeżeli przyjąć za podstawą wierzchołki grafu, to macierz nazywa się macierzą zbieżności wierzchołków. Jeżeli przyjąć za podstawą luki grafu, to macierz nazywa się macierzą zbieżności luk.

W macierze zbieżności wierzchołków w wierszach zaznaczamy wierzchołki, z których wychodzą luki (wyjścia), w kolumnach - wierzchołki, z których wchodzą luki (wejścia).

Na przykład, macierz zbieżności wierzchołków dla grafu z rys. 1. będzie mieć postać:

	W1	W2	W3	W4	W5	P^(-)(wyjścia)
W1	2	1	1	1	1	6
W2	0	0	0	1	0	1
W3	0	1	0	0	1	2
W4	0	0	1	1	1	3
W5	0	0	0	0	0	0
P^(+) (wejścia)	2	2	2	3	3	12 \ 12

Oczywiście, że P⁽⁺⁾ = P^(-).

Na podstawie macierzy zbieżności wierzchołków grafu można narysować graf na wykresie.

W zadaniach programowania sieciowego często graf nie ma pętli i ma jeden wierzchołek, z którego tylko wychodzą luki i tylko jeden wierzchołek, w który tylko wychodzą luki. Taki graf nazywa się sieć.

Definicja 2. Sieć - to jest ograniczony graf bez pętli, skierowany od wierzchołka 1 (wejście) do wierzchołka N (wyjście).

Graf na rys. 2 jest siecią, bo z wierzchołka W₄ tylko wychodzą luki, a w wierzchołek W₂ tylko wchodzą luki.

Sieć można uporządkować na podstawie metody Falkersona:

1) znaleźć wierzchołki, dla których nie istnieję poprzednie (z których tylko wychodzą luki). Taki wierzchołki tworzą poziom 1 uporządkowanego grafu;

2) wykreślić luki z wierzchołków i-go poziomu (i=1,2, ...).

3) znaleźć wierzchołki, dla których ni istnieję poprzednie (z których tylko wychodzą luki). Taki wierzchołki tworzą poziom i uporządkowanego grafu;

Powtórzyć p. 2) - 3) do pełnego uporządkowania grafu.

Rys. 2.

Podstawowy graf i uporządkowany graf nazywa się izomorficznymi.

9.3. Elementy analizy sieci przedsięwzięcia wieloczynnościowego.

W naszych rozważaniach ograniczymy się jedynie do omówienia elementów analizy sieciowej związanej z planowaniem i kierowaniem przedsięwzięciem wieloczynnościowym.

Przez przedsięwzięcie wieloczynnościowe rozumieć będziemy każdy zespół działań, których wykonanie realizuje określone zadanie. Przykładami przedsięwzięć wieloczynnościowych mogą być:

- projektowanie i budowa różnego rodzaju obiektów i urządzeń, jak np. budynku mieszkalnego, zakładu przemysłowego, obiektu sportowego, mostu, drogi, statku, różnego rodzaju maszyn;

- prace remontowe, np. remont kapitalny budynku, statku, maszyny;

- prace naukowo-badawcze,

- prace organizacyjne,

- przejazdy od punktu wejściowego do punktu docelowego, i inni.

Spośród rozmaitych przedsięwzięć wieloczynnościowych tylko te nadają się do ujęcia sieciowego, które mają następujące własności.

WŁASNOŚĆ 1. Całe przedsięwzięcie daje się rozłożyć na elementy prostsze zwane czynnościami. Każda czynność jest procesem wykonywania określonej części zadania stanowiącego wynik realizacji danego przedsięwzięcia.

Przykład 1. Rozpatrzmy budowę garażu dla samochodu osobowego jako przykład przedsięwzięcia wieloczynnościowego. To przedsięwzięcie można podzielić na zespół czynności, których listę podaje następujące zestawienie:

A — zatwierdzenie planu,

B — zakup i dostawa cementu i piasku,

C — zakup i dostawa papy i lepiku,

D — zakup i dostawa cegły,

E — wykonanie i dostawa płyt stropowych,

F — wykonanie i dostawa stolarki,

G — wytyczanie i wyrównywanie terenu,

H — wykopy pod fundamenty,

I — budowa fundamentów,

J — budowa ścian,

K — układanie stropu,

L — pokrycie stropu i roboty blacharskie,

Ł — montaż drzwi,

M — zakładanie instalacji elektrycznej,

N — tynkowanie wnętrza,

O — betonowanie podłogi,

P — tynkowanie zewnętrzne,

R — suszenie.

WŁASNOŚĆ 2. Każda czynność jako część składowa całego przedsięwzięcia trwa przez pewien czas (i najczęściej zużywa określone środki). W związku z tym z każdą czynnością związana musi być pewna liczba nieujemna t zwana czasem trwania.

WŁASNOŚĆ 3. Dla ułatwienia konstrukcji sieci przedsięwzięcia, oprócz elementów składowych, jakimi są czynności, wprowadza się jeszcze jeden rodzaj elementów składowych przedsięwzięcia, zwanych zdarzeniami. Każde zdarzenie określa moment rozpoczęcia lub zakończenia co najmniej jednej czynności wchodzącej w skład przedsięwzięcia.

Z definicji wynika, że zdarzenie jako ustalony moment czasu nie zużywa ani środków, ani czasu. Zdarzenie opisuje jednak pewien stan realizacji przedsięwzięcia.

W naszych rozważaniach zakładać będziemy, że czas trwania czynności jest ustalony. Może on wynikać z obowiązujących norm pracy lub warunków normatywnych, bądź może być ustalony na podstawie nabytych wcześniej doświadczeń. W przypadku gdy czas trwania czynności nie jest stały, a dysponujemy jednocześnie pewnymi informacjami co do spodziewanej jego wielkości, wtedy jako oczekiwany czas trwania danej czynności przyjmujemy liczbę

albo

gdzie t_opt — optymistyczna ocena czasu trwania (możliwie najkrótszego) czynności , t_pesym — pesymistyczna ocena czasu trwania (możliwie najdłuższego) czynności, t_prawda — najbardziej prawdopodobna ocena czasu trwania czynności.

Z określenia wielkości t_opt , t_prawda , t_pesym wynika, że spełniają one relację:

0 ≤ x_opt ≤ x_prawda ≤ x_pesym

ponieważ ocena optymistyczna mówi o najkrótszym, a pesymistyczna o najdłuższym czasie trwania czynności.

WŁASNOŚĆ 4. Przyjmuje się, że każda czynność rozpoczyna się pewnym zdarzeniem (początek czynności) i kończy się innym zdarzeniem (koniec czynności), a jednocześnie dla dwóch różnych czynności ta sama para zdarzeń nie może spełniać roli początku i końca tych czynności.

Oba rodzaje składowych elementów przedsięwzięcia - zdarzenia i czynności można zilustrować graficznie. Przyjęło się przedstawiać zdarzenia jako punkty (kółka) umieszczone na płaszczyźnie, a czynności jako zorientowane odcinki łączące parę punktów reprezentujących początek i koniec danej czynności; długość tych odcinków jest dowolna i nie zależy od rzeczywistego czasu trwania danej czynności. Graficzne przedstawienie wszystkich zdarzeń i czynności rozpatrywanego przedsięwzięcia nazywać będziemy jego grafem. Postać grafu zależy od kolejności, w jakiej muszą występować czynności, a także od sposobu rozmieszczenia punktów reprezentujących zdarzenia.

WŁASNOŚĆ 5. W przedsięwzięciu musi istnieć jedno tylko zdarzenie, które jest wyłącznie początkiem pewnych czynności (początek przedsięwzięcia) i inne, ale tylko jedno, które jest wyłącznie końcem pewnych czynności (koniec przedsięwzięcia).

Bardzo często po wstępnej konstrukcji grafu nie dysponuje on własnością 5, ponieważ występuje w nim więcej niż jedno zdarzenie końcowe lub początkowe przedsięwzięcia. W takim przypadku przez wprowadzenie czynności fikcyjnych, można bardzo łatwo zapewnić występowanie własności 5.

WŁASNOŚĆ 6. Każda czynność, a więc i każde zdarzenie przedsięwzięcia musi należeć do co najmniej jednej drogi łączącej początek z końcem przedsięwzięcia, natomiast żadne zdarzenie nie może być początkiem i jednocześnie końcem tej samej drogi (brak pętli).

WŁASNOŚĆ 7. Dane zdarzenie występuje w momencie najpóźniej kończonej czynności spośród wszystkich, których końcem jest to zdarzenie.

WŁASNOŚĆ 8. Żadna czynność nie może rozpocząć się przed wystąpieniem zdarzenia, które jest jej początkiem.

Deterministyczne metody sieciowe realizowane są na komputerach, same znane z nich są metody CPM i PERT.

Metoda CPM

Metoda CPM (Critical Path Method) odwzorowuje przyjęte zależności technologiczne i wiąże poszczególne czynności oraz pokazuje wpływ terminów wykonawczych tych czynności na ich koszt i wysokość nakładów na całe przedsięwzięcie. Sprowadza się w istocie do wyznaczania ścieżki krytycznej w skierowanym i obciążonym grafie, czyli najdłuższej (najkrótszej) ścieżki łączącej wierzchołek początkowy z wierzchołkiem końcowym.

Zasady budowy sieci w metodzie CPM są proste:

— numeracja zdarzeń może być dowolna, byleby nie wystąpiły dwa identyczne numery zdarzenia;

— w sieci nie mogą wystąpić czynności równoległe;

— każde przedsięwzięcie musi mieć tylko jedno zdarzenie początkowe i tylko jedno zdarzenie końcowe.

Następnym krokiem w metodzie CPM jest ocena czasów realizacji poszczególnych czynności. Obieramy jednostkę i przystępujemy do umieszczenia na sieci czasów trwania poszczególnych czynności projektu. Poszczególnym czynnościom, a tym samym łukom sieci, odpowiadają liczby, będące ocenami czasu potrzebnego na wykonanie czynności. Ścieżka krytyczna w naszej sieci czynności wyznaczana jest za pomocą komputera, z pomocą którego trzeba zbadać znaczną liczbę wariantów. Według specjalnego programu komputer wyznacza ścieżkę krytyczną.

Metoda PERT

Metoda PERT (Program Evaluation and Review Technique) posługuje się również analizą ścieżki krytycznej w sieci, ale umożliwia ponadto wykorzystanie statystycznego oszacowania czasu trwania poszczególnych czynności, a w związku z tym wyznaczenie prawdopodobieństwa zrealizowania poszczególnych etapów przedsięwzięcia w z góry zadanych terminach.

Analiza czasowa projektu.

Definicja 3. Czasem realizacji projektu określonym przez czas trwania czynności będziemy nazywali czas t^*

t^* = max t_i ,

gdzie t_i , i =1, 2, ... , k - czas trwania możliwej ścieżki pełnej łączącej punkt wejściowy i punkt wyjściowy,
, j=1, 2, ..., r - punkty ze ścieżki pełnej z numerem i.

Dalej wprowadzimy istotne dla naszej analizy pojęcie ścieżki krytycznej. Podstawę analizy stanowi bowiem metoda ścieżki krytycznej (ang. critical path method - CPM).

Definicja 4. Ścieżką krytyczną w sieci czynności nazywamy ścieżkę pełną, dla której czas trwania jest najdłuższy.

Biorąc pod uwagę powyższe definicje, można powiedzieć, że możliwie najkrótszy termin realizacji przedsięwzięcia określony jest przez czas ścieżki krytycznej, tj. ścieżki pełnej, która w przedsięwzięciu ma określony najdłuższy czas. W sensie organizacji działań oznacza to, że nie można zrealizować przedsięwzięcia wcześniej (przy założeniu stałej struktury, jak i czasu wykonania czynności) zanim nie wykona się najdłuższego w sensie czasu ciągu następujących po sobie czynności.

Definicja 5. Najwcześniejszy możliwy termin zaistnienia zdarzenia określony jest wzorem:

,

gdzie
oznacza najwcześniejszy możliwy termin wystąpienia i-tego zdarzenia bezpośrednio poprzedzającego wydarzenie j-te. Przyjmijmy, że
.

Definicja 6. Najpóźniejszy dopuszczalny termin zaistnienia zdarzenia i-tego,
, wyznaczony jest następująco:

gdzie
oznacza najpóźniejszy dopuszczalny termin zaistnienia j-tego zdarzenia, następującego po i-tym zdarzeniu, przy czym
.

Najwcześniejszy i najpóźniejszy termin zdarzenia końcowego są sobie równe, gdyż zdarzenie to nie ma następnika. Definicje 5 oraz 6 umożliwiają wprowadzenie pojęcia luzu czasowego zdarzenia.

Definicja 7. Luz czasowy L_i dowolnego zdarzenia i-tego określamy w następujący sposób:
.

Wskazuje on, o ile może opóźnić się termin zaistnienia zdarzenia bez wpływu na termin zakończenia realizacji projektu.

Obecnie przejdziemy do przedstawienia charakterystyk czasowych rozpoczęcia i zakończenia czynności oraz ich rezerw. Dla każdej czynności (i-j) wyróżnia się cztery terminy.

Definicja 8. Najwcześniejszy możliwy termin rozpoczęcia czynności (i-j) wyznacza najwcześniejszy możliwy termin zajścia zdarzenia początkowego tej czynności.

Definicja 9. Najpóźniejszy dopuszczalny termin rozpoczęcia czynności określony jest przez różnicę
.

Definicja 10. Najwcześniejszy możliwy termin zakończenia czynności (i-j) wyrażony jest przez sumę
.

Definicja 11. Najpóźniejszy dopuszczalny termin zakończenia czynności (i-j) określa najpóźniejszy termin zajścia zdarzenia końcowego tej czynności.

Dla każdej czynności możemy wyznaczyć rezerwy czasu wykonania, zwane zapasami czasu.

Rozróżnia się cztery rodzaje zapasów czasu:

Z_c — zapas całkowity,

Z_s — zapas swobodny,

Z_w — zapas warunkowy,

Z_n — zapas niezależny.

Definicja 12. Zapas całkowity Z_c określony jest za pomocą równania:

Stanowi on rezerwę czasu, który może być wykorzystany dodatkowo na wykonanie danych czynności bez wpływu na termin realizacji projektu.

Definicja 13. Zapas swobodny Z_s określony jest równaniem:

Wykorzystanie tego zapasu nie ma wpływu na zapasy związane z czynnościami należącymi do danej ścieżki.

Definicja 14. Zapas warunkowy Z_w określony jest następująco:

Ta rezerwa czasu może być wykorzystana bez zmniejszania zapasów poprzednich, określonych dla danej ścieżki.

Definicja 15. Zapas niezależny Z_n oblicza się według wzoru:

Wykorzystanie tej rezerwy nie ma wpływu na zapas jakiejkolwiek innej czynności.

Można wykazać, że dla czynności należących do ścieżki krytycznej wszystkie zapasy są równe zeru. Tym samym wydłużenie jakiejkolwiek czynności krytycznej o jednostkę powoduje opóźnienie terminu realizacji projektu o jednostkę. W przypadku występowania jednej ścieżki każde skrócenie czasu trwania jednej z czynności krytycznych o jednostkę powoduje skrócenie o jednostkę czasu realizacji projektu. Warto zaznaczyć, że w sieci istnieje co najmniej jedna ścieżka krytyczna. Może być ich więcej, jednak ich liczba jest skończona. W skrajnym przypadku może się zdarzyć, że wszystkie ścieżki pełne będą krytycznymi. Ta mało realna sytuacja oznacza konieczność natychmiastowego podjęcia realizacji poszczególnych czynności.

Wyznaczone terminy zajścia zdarzeń, terminy rozpoczęcia i zakończenia czynności składają się na plan wykonania zadań w czasie realizacji projektu zwany harmonogramem.

9.4. Potoki w sieciach. Zadanie o maksymalnym potoku.

Zadanie o przepływach w sieci

Zadania przepływu w sieciach powstaję jako zadanie optymalizacji przewozu ładunków. W rozszerzonym podejściu zadanie o potokach jest zadanie optymalizacji (maksymalizacji) przepływu informacji w sieciach telekomunikacyjnych, optymalizacji sieci dróg, sieci komunikacyjnych (energii, ruro-, gazo-, ropo-, wodociągów) i inne.

Rozpatrujemy ograniczony graf bez pętli (sieć) skierowany od wierzchołka I do wierzchołka S. Zaznaczymy jego G(U,W), Dla każdego łuku (i,j) = u_ij łączącej wierzchołki i oraz j odpowiada nieujemna liczba d_ij która nazywa się przepustowością łuku. Jeżeli wierzchołki połączony nie skierowanym łukiem (żebrem) wtedy przepustowość żebra d_ij = d_ji . Dla każdego łuku u_ij można wprowadzić nieujemną liczbę x_ij która nazywa się przepływem (potokiem) względem łuku u_ij . Oczywiście że

0 ≤ x_ij ≤ d_ij

co oznacza że potok przez łuk nie może przekraczać przepustowości luku.

Potokiem w sieci od wierzchołka I do wierzchołka S nazywa się zbiór X nieujemnych liczb x_ij ≥ 0 dla łuków u_ij odpowiadający warunkom

,
,

Ostatnie równanie oznacza że dla dowolnego tranzytowego wierzchołka k ilość wpływającego materiału równa się ilości wypływającego z niego, czyli w wierzchołkach tranzytowych potok nie tworzy się. Pierwsze równanie oznacza że z źródłowego wierzchołka I płynie potok wielkości z, oraz drugie równanie pokazuję że potok wielkości z dopływa do wierzchołka docelowego S.

Sformalizowane zadanie maksymalizacji potoku polega na stworzeniu lokalnych potoków x_ij ≥ 0 maksymalizujący potok w sieci Z → max od I do S nie przekraczając przepustowości łuków sieci d_ij .

Cięcia w sieciach

Każdy łuk jest obciążony parą liczb (d_ij ,x_ij) pokazującym przepustowość i potok w łuku. Jest oczywistym że maksymalny potok nie może przekroczyć przepustowości łuków. Można zrobić w sieci cięcie i wyznaczyć cięcie z minimalną przepustowością która równa się maksymalnemu potoku w sieci.

Niech zbiór wierzchołków W jest podzielony na dwa zbiory A i B tak że A ∪ B = W.

Cięciem (A,B) w sieci G(W,U) nazywa się zbiór C(A,B) łuków u_ij dla których wierzchołki W_i ∈ A i W_j ∈ B.

Jeżeli I ∈ A oraz S ∈ B, wtedy cięcie (A,B) rozdziela źródło potoku od punktu docelowego.

Przepustowością cięcia (A,B) nazywa się liczba P(A,B) = Σd_ij ze zbioru przecinanych łuków.

W ogólnym przypadku C(A,B) ≠ C(B,A) oraz P(A,B) ≠ P(B,A).

Przykład. Dla podanego niżej grafu są zrobione dwa cięcia (A1,B1) oraz (A2,B2).

Do zbioru A1 należy wierzchołek 2, do zbioru B1 - wierzchołki 1,3,4,5. Wtedy C(A1,B1) = {d₂₃, d₂₄, d₂₅}. Przepustowość cięcia P(A1,B1) = 4+5+9=18.

Łatwo sprawdzić że dla cięcia C(B1,A1) przepustowość P(B1,A1)=12

Dla cięcia C(A2,B2) otrzymujemy: A2={1,2,3}, B2={4,5}. P(A2,B2)=9+5+7=21.

Cięcie C(A2,B2) rozdziela źródło potoku I i punkt docelowy S.

Cięcie rozdzielające I oraz S które ma minimalną przepustowość P nazywa się cięciem minimalnym.

Algorytm Forda-Fulkersona maksymalizacji potoku

Podstawą tworzenia maksymalnego potoku w sieci jest twierdzenie Forda-Fulkercona.

Twierdzenie (Forda-Fulkersona). Wielkość maksymalnego potoku w sieci od I do S równa się minimalnej z przepustowości cięć rozdzielających wierzchołki I i S.

Jeżeli potok x_ij < d_ij wtedy łuk (lub żebro) (i,j) nazywa się nienasyconym. Jeżeli potok x_ij = d_ij wtedy łuk (lub żebro) (i,j) nazywa się nasyconym.

Algorytm Forda-Fulkersona podajemy w następującej interpretacji:

1. Tworzymy macierz przepustowości żeber pamiętając o kierunku przepływu.

2. Tworzymy pierwotne potoki od I do S, biorąc pod uwagę przepustowość żeber.

3. Obliczamy macierz potoków i macierz nasyconych żeber. Dla nienasyconych wierzchołków budujemy listę od I do S.

4. Jeżeli listę zbudować nie jest możliwe, wtedy potok jest zmaksymalizowany i zadanie rozwiązane. Jeżeli istnieję lista wierzchołków z nienasyconymi żebrami od I do S wtedy zwiększamy moc potoku wybierając najniższą wartość potoków pomiędzy żebrami z listy przechodzimy do p.3.

Algorytm Forda-Fulkersona jest wielokrokowym (iteracyjnym).

Przykład. Dla grafu narysowanego wyżej obliczyć maksymalny potok i znaleźć minimalne cięcie.

	1	2	3	4	5
1	0	7	8	0	0
2	0	0	4	5	9
3	0	0	0	7	0
4	0	5	0	0	7
5	0	0	0	0	0

1. Stworzymy macierz przepustowości żeber.

2. Stworzymy dowolne potoki: 1-2-4-5 (wielkość przepływu czyli moc potoku wynosi min(7, 5, 7) = 5) oraz 1-3-4-5 (moc potoku min(8,7,7-5)=2).

Pierwotny potok w sieci wynosi 5+2=7.

3. Obliczamy macierz potoków i macierz nasyconych żeber.

Macierz potoków Macierz nasyconych żeber

	1		2		3		4		5
1			5		2
2							5
3							2
4									2+5=7
5
		1		2		3		4		5
1				2		6
2						4				9
3								5
4				5
5

Zbudujemy listy nienasyconych żeber.

1 → 2,3 ; 2 → 3, 5; 3 → 4; 4 → 2

Widać że z 1=I do 5=S można trafić ścieżką 1 - 2 - 5. Moc potoku min(2, 9)=2.

Potok w sieci jest zwiększony o 2 jednostki i wynosi 7+2 = 9 jednostek.

Macierz potoków Macierz nasyconych żeber

	1		2				3		4		5
1			5+2=7				2
2									5		2
3									2
4											2+5=7
5
		1		2	3	4		5
1					6
2					4			7
3						5
4				5
5

Zbudujemy listy nienasyconych żeber.

1 → 3 ; 3 → 4; 4 → 2; 2 → 3,5

Widać że z 1=I do 5=S można trafić ścieżką 1 - 3 - 4 - 2 -- 5. Moc potoku min(6,5,5,7)=5

Potok w sieci jest zwiększony o 5 jednostki i wynosi 9+5 = 14 jednostek.

Macierz potoków Macierz nasyconych żeber

	1		2				3		4		5
1			5+2=7				2
2									5		2
3									2
4											2+5=7
5
		1		2	3	4		5
1					1
2					4			2
3
4
5

Zbudujemy listy nienasyconych żeber.

1 → 3.

Ścieżki prowadzącej od 1 do 5 nie istnieję. Zwiększyć moc potoku nie jest możliwe. Maksymalna moc potoku w sieci wynosi 14 jednostek.

Cięcie minimalne zawiera zbiory wierzchołków A = {1,3} i B {2,4,5}. Obliczymy przepustowość cięcia P(A,B)=d₁₂ + d₃₄ = 7+7=14.

Na podstawie twierdzenia Forda-Fulkersona zadanie jest rozwiązane.

9.5. Metoda programowania dynamicznego.

Programowanie (planowanie) dynamiczne jest zbiór matematycznych metod dla optymalnego planowania procesami sterowanymi.

Sterowany proces jest proces, na który można mieć ukierunkowany wpływ.

W programowanie dynamicznym proces optymalizacji zadania jest podzielony na kroki 0, 1, 2, ... N.

W programowaniu dynamicznym funkcja celu Z ma charakter rekurencyjny i może być zapisana w postaci równań Bellmana:

F_i(x_i-1; u_i) = extr {Z_i(x_i-1; u_i) + F_i+1(x_i)}

u_i

gdzie extr - typ extremumu (maksimum lub minimum) funkcji celu ;

x_i-1 - zbiór stanów, w których sterowany system będzie przed i-em krokiem;

u_i - zbiór sterowań, które mogą być wybrane na i-em kroku i system zmieni swój stan;

F_i+1 - względnie-optymalna wartość funkcji celu Z na odcinku od i-go kroku do ostatniego (N-go) pod warunkiem, że system przyjdzie z stanu x_i-1 w stan x_i, jeżeli na system wpływa sterowanie, które wybrane z zbioru u_i.

i = N-1, N-2, .... , 2.

Z = F₁(x₀, u₁)

Optymalizacja w zadaniach programowania dynamicznego zwykle zaczyna się od ostatniego N-go kroku.

Wykorzystywanie metody programowania dynamicznego podane niżej na przykładzie optymalnego rozwiązania zadania sieciowego.

Stan x_i - to będzie punkt, w którym znajduje się pasażer;

Sterowanie u_i - to będzie możliwość przejazdu z punktu w odpowiednim kierunku.

9.6. Przykłady rozwiązania zadania metodami programowania sieciowego i dynamicznego.

Przykład 1.

Zadanie. Dla dziesięciu miast 1,2, ... 9, 10 wiadome czasy przejazdu t_ij między odpowiednie miastami i i j . Jaka droga z miasta 1 do miasta 10 będzie najkrótsza?

Oblicz oczekiwany czas przejazdu od miasta 1 do miast 10 i od miasta 2 do miasta 10.

Potrzebnie: 1. Narysować graf sieci dróg. 2. Uporządkować jego metodą Falkersona. 3. Metodami programowania dynamicznego znaleźć minimalny czas przejazdu między punktami 1 a 10, i również 2 a 10, 3 a 10, ... , 9 a 10 dla prawdopodobnego czasu zdażeń.

4. Oblicz oczekiwany czas przejazdu od miasta 1 do miast 10 i od miasta 2 do miasta 10.

5. Zrobić wnioski.

	t12	t13	t14	t24	t25	t26	t35	t36	t37	t45	t46	t56	t58	t67	t68	t78	t79	t710	t89	t810	t910
prawdopodobne	2	5	9	4	1	9	5	9	3	5	5	4	5	3	5	9	8	5	6	5	2
optymistyczne	1	4	7	2	1	8	5	8	3	3	2	3	3	3	4	7	7	5	5	5	1
pesymistyczne	4	7	11	8	5	9	5	11	4	8	8	5	7	6	6	13	15	8	8	8	6

Rozwiązanie. (Wykorzystujemy arkusz Excel'a z zadaniem)

1. Narysujemy graf sieci dróg, wykorzystując graficzne możliwości Excel'a. Dla tego połączmy łukami (strzałkami) wierzchołki (miasta), między którymi istnieję drogi.

2. Uporządkujemy jego metodą Falkersona. Dla tego wyznaczymy wierzchołki, z których tylko wychodzą łuki. Z wykresu widać, że to będzie wierzchołek 1. On odnosi się do I-ej grupy. Dalej wyłączmy z grafu wierzchołek 1 i łuki, które zaczynają się w wierzchołku 1 (łuki 1-2, 1-3, 1-4, oni zaznaczony na wykresie grubymi liniami). W pozostałym grafie z wierzchołków 2 i 3 również tylko wychodzą łuki. Wierzchołki 2 i 3 odniosą się do II-ej grupy. Jeżeli kontynuować ten proces przekształcenia grafu, to będziemy mieć 9 grup wierzchołków, który narysowany na wykresie w p.2.

3. Wykorzystamy metody programowania dynamicznego dla znalezienia minimalnego czasu między punktami 1 a 10, i również 2 a 10, 3 a 10, ... , 9 a 10.

Zaczynamy z ostatniego etapu. Liczymy, że czas przejazdu z miasta 10 do miasta 10 równa się 0 (wpisujemy 0 w komórką N23). Na przedostatnim etapie VIII (wierzchołek 9) z wierzchołka 9 wychodzi tylko jedna łuka. To oznacza, że minimalny czas między miastami 9 i 10 równa się 2 jednostki (0+2=2 lub formuła =N23+B22). Komórkę z optymalnym marszrutom ruchu zaznaczamy kolorem.

Na VII etapie z wierzchołka 8 wychodzi 2 łuki. Jeżeli będziemy jechać kierunkiem 8-10, to odległość będzie 0+5=5 jednostek (=N23+B21), jeżeli marszrutom 8-9-10 - 0+2+6=8 jednostek (=M23+B20). Wtedy minimalny czas z 8 do 10 jest 5 jednostek i odpowiada kierunku 8-10.

Analogiczne na VI etapie z wierzchołka 7 wychodzi 3 łuki. Jeżeli będziemy jechać kierunkiem 7-10, to czas będzie 0+5=5 jednostek, jeżeli kierunkiem 7-10 (7-8, a dalej optymalny jest 8-10) - 0+5+9=14 jednostek, jeżeli 7-9-10, to 0+2+8=10 jednostek. Wtedy minimalny czas z 7 do 10 jest 5 jednostek i odpowiada kierunku 7-10.

Dalej potrzebnie zrobić optymalizację dla pozostałych etapów.

4. Obliczmy czas optymistyczny dla ścieżki 1-2-5-8-10: t_opt=10 i ścieżki 1-3-7-10: t_opt=12. Dla ścieżki 2-5-8-10: t_opt=9

Obliczmy czas pesymistyczny dla ścieżki 1-2-5-8-10: t_pes=24 i ścieżki 1-3-7-10: t_pes=19.

Dla ścieżki 2-5-8-10: t_pes=20

Czas oczekiwany dla ścieżki 1-2-5-8-10: t_oczekiwane = 14,33

dla ścieżki 1-3-7-10 : t_oczekiwane = 13,83

dla ścieżki 2-5-8-10: t_oczekiwane = 12,17.

5. Na podstawie optymalizacji można zrobić następujące wnioski:

5.1. Optymalny kierunek z 1 w 10: 1-2-5-8-10 lub 1-3-7-10. Jego czas 13 jednostek.

5.2. Optymalne kierunki: z 2 w 10: 2-5-8-10 (11); z 3 w 10: 3-7-10 (8); z 4 w 10: 4-6-7-10 (13); z 5 w 10: 5-8-10 (10); z 6 w 10: 6-7-10 (8); z 7 w 10: 7-10 (5); z 8 w 10: 8-10 (5); z 9 w 10: 9-10 (2).

5.3. Oczekiwany czas przejazdu od 1 do 10 wynosi 13,83 jednostek czasowych, od 2 do 10 - 12,17 jednostek.

Rys. 3.

14

Lekcja 9. Elementy programowania sieciowego i dynamicznego.

W₁

W₂

W₅

W₄

W₃

W₁

W₂

W₄

W₃

W₁

W₂

W₄

W₃

10

1

2

3

4

5

6

8

7

9

2

10

1

3

4

5

6

8

7

9

7

9

5

7

4

8

7

5=S

2

4

3

1=I

A1

B1

A2

B2

7

5

9

7

A1

B1

B2

A2

4

8

7

5=S

2

4

3

1=I

---