Lekcja 5. Elementy programowania sieciowego i dynamicznego.

5.1. Zadania programowania sieciowego i dynamicznego.

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

5.3. Metoda programowania dynamicznego.

5.4. Przykład rozwiązania zadania metodami programowania sieciowego i dynamicznego.

5.1. Zadania programowania sieciowego i dynamicznego.

Duża ilość zadań badań operacyjnych może być przedstawiona w postaci sieciowej. W takich zadaniach mamy niektóry punkty (wierzchołki). Oni mogą odpowiadać miastom, zdarzeniom, osobom i inne. Wierzchołki mogą być połączone lukami z innymi wierzchołkami. Wierzchołki i luki razem tworzą obiekt, który nazywa się grafem, a na wykresie to wygląda jak sieć połączonych punktów.

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.

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

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

Rys. 1.

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. 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).

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. Sieć - to jest konieczny graf bez pętli, skierowany od wierzchołka 1 (wejście) do wierzchołka N (wyjście).

Graf na rys. 2 jest sieć, 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.

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.

5.3. 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.

5.4. Przykład rozwiązania zadania metodami programowania sieciowego i dynamicznego.

Zadanie. Dla dziesięciu miast 1,2, ... 9, 10 wiadome odległości a_ij między odpowiednie miastami i i j . Jaka droga z miasta 1 do miasta 10 będzie najkrótsza?

Potrzebnie: 1. Narysować graf sieci dróg. 2. Uporządkować jego metodą Falkersona. 3. Metodami programowania dynamicznego znaleźć minimalną odległość między punktami 1 a 10, i również 2 a 10, 3 a 10, ... , 9 a 10. 4. Zrobić wnioski.

a12	a13	a14	a24	a25	a26	a35	a36	a37	a45	a46	a56	a58	a67	a68	a78	a79	a710	a89	a810	a910
2	5	9	4	1	9	5	9	3	5	5	4	5	3	5	9	8	5	6	5	2

Rozwiązanie. 1. Narysujemy graf sieci dróg, wykorzystując graficzne możliwości Excel'a. Dla tego połączmy lukami (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ą luki. 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 luki, które zaczynają się w wierzchołku 1 (luki 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ą luki. 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 minimalnej odległości między punktami 1 a 10, i również 2 a 10, 3 a 10, ... , 9 a 10.

Zaczynamy z ostatniego etapu. Liczymy, że odległość 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 luka. To oznacza, że minimalna odległość 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 luki. 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 minimalna odległość z 8 do 10 jest 5 jednostek i odpowiada kierunku 8-10.

Analogiczne na VI etapie z wierzchołka 7 wychodzi 3 luki. Jeżeli będziemy jechać kierunkiem 7-10, to odległość 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 minimalna odległość z 7 do 10 jest 5 jednostek i odpowiada kierunku 7-10.

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

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

4.1. Optymalny kierunek z 1 w 10: 1-2-5-8-10 lub 1-3-7-10. Jego długość 13 jednostek.

4.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).

Rys. 3.

9

7

W₃

W₄

W₂

W₁

W₃

W₄

W₂

W₁

W₃

W₄

W₅

W₂

W₁

8

6

5

4

3

2

1

10

9

7

8

6

5

4

3

1

10

2

---