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 :

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 1

Definicja

Zbiór wierzchołków sieci S nazywamy uporządkowanym, jeżeli:

U_ij ε 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 = {k₁, k­₂, … , k_m}

Gdzie k₁=1, k_m=N , K_i< k_i+1 oraz U_k1K2 ε 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 U_ij w Sieci czynności S mogą być charakteryzowane następującymy wielkościami

T_{ij – czsy trwania czynności} U_ij

d_{ij – pracochłonności czynności} U_ij

z_{ij – zasobochłonności czynności} U_ij

k_{ij – koszty realizacji czynności} U_ij

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

• U_ij – czynności składające się na dane przedsięwzięcie

• T_ij – czasy realizacji U_ij

• 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) = $\sum_{i = 1}^{m - 1}{tk1,\ ki + 1}$

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 T_i 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 , T₁=T* , Aby wyznaczyć T* wystarczy wyznaczyć T₁

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 $\overbrace{1 \leq k \leq K}$ 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

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

3 sposób

Wykresy Gantta

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.