wyk4-7, BO wyk 4


Metody Sieciowe w Badaniach optymalizacyjnych

Optymalizacja sieciowa(programowanie sieciowe).

Sieci w zagadnieniach optymalizacyjnych

W opt. Siec. Rozpatruje się wiele różnych sieci:

Sieci czynności

S.czynności oznaczoną symbolem S = [ P, U] nazywamy graf spełniający następujące warunki:

Uwagi :

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

  2. 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 10x01 graphic

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, k­2, … , 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:

Definicja

Długością drogi D lub czasem przejścia drogi D nazywamy T(D) = 0x01 graphic

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. T­N=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ąć T­N=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.

  1. Dla dowolnej sieci czynności S istnieje dokładnie jeden czas Krytyczny T*

  2. 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 0x01 graphic
    T(D*k) = T*

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

0x01 graphic

Uwaga w Sieci uzupełnionej powinna być zaznaczona droga krytyczna D*

3 sposób

Wykresy Gantta

0x01 graphic

Uwaga.

  1. Czynności kryt. Powinny być na wykresie Gantta zaznaczone specjalnie.

  2. Wykresy Gantta mogą być traktowane jako harmonogramy realizacji projekty.

  3. Na wykresach można uwzględniać koszty, zasoby, itp.



Wyszukiwarka