Metody Sieciowe w Badaniach optymalizacyjnych
Optymalizacja sieciowa(programowanie sieciowe).
Sieci w zagadnieniach optymalizacyjnych
W opt. Siec. Rozpatruje się wiele różnych sieci:
Czynności
Przepływu
Transportowe
I inne.
Sieci czynności
S.czynności oznaczoną symbolem S = [ P, U] nazywamy graf spełniający następujące warunki:
Jest grafem zorientowanym
Jest grafem spójnym
Acyklicznym
Ma dokładnie jeden wierzchołek początkowy
I końcowy
Uwagi :
Zbiór P nazywamy zbiorem wierzchołków, a zbiór U nazywamy zbiorem łuków sieci S. Sieć jest Grafem zorientowanym Jeżeli wszystkie łuki mają nadany bądź określony zwrot. Jest grafem spójnym jeżeli składa się z jednej części. Jest grafem acyklicznym jeżeli wychodząc z dowolnego wierzchołka i poruszając się do innych wierzch. Zgodnie ze zwrotem łuków nie można wrócić do tego wierzchołka.
Dla sieci czynności przyjmujemy, że zbiór jego wierzchołków ma nast. Postać. P = {1,2,3, … , N} (każdy inny zbiór wierzchołków można przemianować i przenumerować tak żeby osiągnąć ustaloną postać).
Przykład rys 1
Definicja
Zbiór wierzchołków sieci S nazywamy uporządkowanym, jeżeli:
Uij ε U -> i < j
Wniosek 1. W sieci uporządkowanej łuki zaczynają się w wierzchołkach o numerach mniejszych
Wniosek 2. W siesieci uporządkowanej wierzch. Początkowy zawsze ma numer 1. Wierzch. Końcowy numer N
Wniosek 3. Zbiór wierzchołków dowolnej sieci można uporządkować dokonując odpowiedniego przenumerowania wierzchołków.
Wniosek 4. Można zatem przyjąć, że rozpatrywanie dalej będą wyłącznie sieci z uporządkowanym zbiorem wierzch.
Definicja
Droga w sieci czynności nazywamy dowolną ścieżkę łączącą wierzchołek początkowy z wierzch. końcowym
Ścieżką w sieci czynności nazywamy zbiór dowolny łuków sieci, ale takich, że koniec takiego łuku jest zarazem początkiem następnego łuku.
Wniosek.
Drogą w sieci czynności będzie następujący zbiór punktów
D = {k1, k2, … , km}
Gdzie k1=1, km=N , Ki< ki+1 oraz Uk1K2 ε U dla i=
Uwaga w sieci na ogół istnieje wiele różnych dróg
Ogólne sformułowania
Zastosowania sieci czynności w BO
Projekt - Zespół czynności pewnego przedsięwzięcia, które są powiązane następstwem wykonania.
Sieć czynności - będzie rozumiana, w tym konteksie, jako matematyczny opis struktury przedsięwzięcia lub rewalizacji przedsięwzięcia, oraz wierzchołki czynności będziemy nazywać zdarzeniami, a łuki - czynnościami.
Czynności Uij w Sieci czynności S mogą być charakteryzowane następującymy wielkościami
Tij - czsy trwania czynności Uij
dij - pracochłonności czynności Uij
zij - zasobochłonności czynności Uij
kij - koszty realizacji czynności Uij
Ogólne sformułowanie zad. Opt. Siec.
Wyznaczyć optymalny harmonogram realizacji projektu
Wniosek. Zagadnienia opt. Siec. Można określić jako zagadnienia optymalizacji realizacji projektu ( ze wzgl. Na różne kryteria).
Analiza Czasu w sieciach czynności
Podstawowym instrumentem analizy czasu w sieciach czynności jest METODA ŚCIEŻKI KRYTYCZNEJ ( CPM)
Podstawy CPM
Przyjmujemy następujące założenia i oznaczenia:
S= [ P, U] - jest siecią czynności będącą modelem matematycznym pewnego przedsięwzięcia
Uij - czynności składające się na dane przedsięwzięcie
Tij - czasy realizacji Uij
D = {k1, k2, … , km} - droga w rozpatrywanej sieci czynności sieci czynności S = [P, U]
Definicja
Długością drogi D lub czasem przejścia drogi D nazywamy T(D) =
Uwaga. Przedsięwzięcia, którego modelem jest Sieć S będzie zrealizowane wtedy, gdy zrealizowane będą wszystkie czynności Uij E U
Wniosek. Najkrótszy możliwy czas realizacji rozpatrywanego przedsięwzięcia jest równy długości najdłuższej drogi sieci S
Definicja
Najdłuższą drogą w sieci czynności nazywamy drogą krytyczną i oznaczamy D*
Czynności składające się na drogę Krytyczną D* nazywamy czynnościami Krytycznymi w sieci czynności.
Zdarzenia należące do drogi krytycznej D* nazywamy zdarzeniami krytycznymi
Czas przejścia drogi krytycznej lub długości drogi krytycznej D* wynosząca
T* = T( D*) nazywamy czasem krytycznym dla sieci czynności S
WYZNACZANIE CZASU KRYTYCZNEGO D* ORAZ DROGI KRYTYCZNEJ D* DLA SIECI CZYNNOŚCI
Def. Czasem Krytycznym Ti zdarzenia i-tego nazywamy czas przejścia najdłuższej drogi z wierzchołka i-tego do ostatniego wierzchołka N-tego, sieci S = [P, U]
Wnioski. TN=0 , T1=T* , Aby wyznaczyć T* wystarczy wyznaczyć T1
Algorytm wyznaczania czasy krytycznego T* w sieci czynności S.
Uwaga. Idea tego algorytmu wynikac będzie z definicji czasów krytycznych zdarzeń.
KROK1. Przyjąć TN=0
KROK2. Dla i=2, .. , N-2, N-1 wyznaczyć następujące wielkości
Ti = max {Tj+tij} dla takich j, że Uij E U
Będące czasami krytycznymi poszczególnych wierzchołków sieci czynności S= [ P, U]
KROK N. Wyznaczyć T1:
Ti = max {Tj+t1j} dla takich j, że U1j E U
Oraz zgodnie z def. Czasu krytycznego zdarzeń i czasu krytycznego dla sieci S= [ P, U] , przyjąć że T*=T1
Algorytm wyznaczania Drogi krytycznej D* w sieci czynności S.
KROK 0: Z def. Drogi krytycznej przyjmujemy że 1 E D* oraz D* = {1, ….
KROK 1: Jeżeli Tp = max {Tj+t1j} = Tp+t1p
To stwierdzamy że pED* oraz że D* = {1, p, …
KROK 2: : Jeżeli Tp = max {Tj+t1j} = Tq+tpq
To stwierdzamy że qED* oraz że D* = {1, p, q, …
Uogólnienie postępowania algorytmicznego
Postępowanie algor. Kontynuujemy do chwili stwierdzenia, że zdarzenie końcowe będzie należało do drogi krytycznej czyli, że NED*, wtedy stwierdzamy, że poszukiwana droga krytyczna D* jest następująca D*= {1, p, q, … , N}
UWAGI.
Dla dowolnej sieci czynności S istnieje dokładnie jeden czas Krytyczny T*
Mogą natomiast istnieć różne drogi krytyczne D*k dla (k=1,2, .. , K) prz czym czas przejścia każdej drogi krytycznej jest jednakowy i wynosci T* czyli
T(D*k) = T*
Czas krytyczny wyznacza się rozpoczynając od końca, a drogę od początku
Uzupełniające charakterystyki czasowe w sieci czynności
Na analizę czasu w sieciach czynności składa się również wyznaczanie dodatkowo następujących wielkości:
Wi - najwcześniejszy możliwy moment zajścia zdarzenia i
pj - najpóźniejszy możliwy moment zajścia zdarzenia j
t wp/ij - najwcześniejszy możliwy moment rozpoczęcia zdarzenia Uij
t pp/ij- najpóźniejszy możliwy moment rozpoczęcia zdarzenia Uij
t wk/ij- najwcześniejszy możliwy moment zakończenia zdarzenia Uij
t pk/ij - najpóźniejszy możliwy moment zakończenia zdarzenia Uij Uij
Lij - Całkowity zapas czasowy ( luzy czasowe) czynności Uij
DODATKOWE charakterystyki czasowe
^Lij - Swobodny zapas luz czasowy czynności Uij
Tylda Lij - warunkowy zapas luz czasowy czynności Uij
Wyznaczanie uzupełniających charakt. Czasowych sieci czynności
Przyjmując że W1 = 0 pN = wN = T*
Pozostałe z powyższych wielkości można wyznaczyć
Wi = max {pk+tij} = dla takich j, że Uij E U
pj= min {pk-tjk} = dla takich k, że Uij E U
t wp/ij = wi
t pp/ij = pj -tij
twk/ij = wi + tij
t pk/ij = wi + tij
t pk/ij = pj
Lij = t pp/ij - t wp/ij = t pk/ij - t wk/ij = pj - wi - tij
^Lij = wj - wi -tij
Tylda Lij = pj - pi -tij
Sposoby prezentacji wyników metody analizy ścieżki krytycznej
1 sposób
Tablica wyników analizy czasu w sieci czynności.
Uij |
tij |
wi |
pj |
T wp/ij |
T wk/ij |
T pp/ij |
T pk/ij |
Lij |
^Lij |
Tyl.Lij |
|
|
|
|
|
|
|
|
|
|
|
2 sposód
Sieć uzupełniona
Uwaga w Sieci uzupełnionej powinna być zaznaczona droga krytyczna D*
3 sposób
Wykresy Gantta
Uwaga.
Czynności kryt. Powinny być na wykresie Gantta zaznaczone specjalnie.
Wykresy Gantta mogą być traktowane jako harmonogramy realizacji projekty.
Na wykresach można uwzględniać koszty, zasoby, itp.