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.
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 a1, a2, ... , am i n punktów (przedsiębiorstw, sklepów) z zapotrzebowaniami w surowcach b1, b2, ... , bn. Punkty i i j połączony drogami z czasem przewozu tij.
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ą aij). 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 tij. 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ą xi, to firma otrzymuje zysk zi.
Potrzebnie tak podzielić sumą X, żeby firma otrzymała największy zysk od swoich przedsiębiorstw.
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)
2
1
6
0
3
P(+) (wejścia)
Puchaczo_o