harmonogram1.pdf

PROGRAMOWANIE SIECIOWE.

METODA

SCIE ZKI KRYTYCZNEJ

Maciej Patan

Instytut Sterowania i Systemów Informatycznych

Uniwersytet Zielonogórski

Badania operacyjne

Programowanie sieciowe. Metoda CPM

WPROWADZENIE

Metody programowania sieciowego wprowadzono pod koniec lat

pi ecdziesi atych

Ze wzgl edu na struktur e logiczn a metody sieciowe dzieli si e na:

1. sieci o strukturze zdeterminowanej DAN (ang. Deterministic Analysis

Network )

2. sieci o strukturze stochastycznej GAN (ang. Generalized Analysis

Network )

Przy tak zdeﬁniowanym podziale b edziemy rozwazac modele sieciowe

przedsi ewzi ec

Instytut Sterowania i Systemów Informatycznych

Uniwersytet Zielonogórski

Badania operacyjne

Programowanie sieciowe. Metoda CPM

Deﬁnicje

• Przedsi ewzi ecie – zorganizowane działanie ludzkie zmierzaj ace do osi agni ecia

okreslonego celu, zawarte w sko nczonym przedziale czasu, z wyróznionym

pocz atkiem i ko ncem oraz zrealizowane przez sko nczon a liczb e osób, srodków

technicznych, energii, materiałów, srodków ﬁnansowych i informacji

• Podstawowych elementów przedsi ewzi ecia: zdarzenia i czynnosci

• Zdarzenie – w modelu sieciowym oznacza osi agni ecie stanu zaawansowania prac

przy realizacji przedsi ewzi ecia

• Zdarzenia przedstawia si e graﬁcznie za pomoc a kółek lub innnych ﬁgur

geometrycznych

• Czynno s c – dowolnie wyodr ebniona cz esc przedsi ewzi ecia charakteryzuj aca si e

trwaniem, terminem rozpocz ecia, zako nczenia oraz ilosci a zaangazowanych do jej

wykonania srodków

• Obrazem graﬁcznym czynnosci s a strzałki. Kierunek strzałki wskazuje kierunek

przebiegu czynnosci w czasie

Instytut Sterowania i Systemów Informatycznych

Uniwersytet Zielonogórski

Badania operacyjne

Programowanie sieciowe. Metoda CPM

• Zaleznosci pomi edzy zdarzeniami i czynnosciami okreslaj a struktur e logiczn a

modelu sieciowego

• Struktura sieciowa moze byc:

⋄ zdeterminowana, jesli w trakcie realizacji przedsi ewzi ecia wszystkie czynnosci

przedstawione w sieci s a zrealizowane

⋄ stochastyczna, jesli w trakcie realizacji przedsi ewzi ecia bierze udział tylko cz esc

czynnosci przedstawiona w sieci, z okreslonym, wi ekszym od zera

prawdopodobie nstwem

• Modele sieciowe o zdeterminowanej strukturze logicznej:

⋄ CPM (ang. Critical Path Method )

⋄ CPM-COST

⋄ PERT (ang. Program Evaluation and Review Technique )

⋄ PERT-COST

Instytut Sterowania i Systemów Informatycznych

Uniwersytet Zielonogórski

Badania operacyjne

Programowanie sieciowe. Metoda CPM

Optymalizacja przedsi ewzi ecia polega na:

• wyodr ebnieniu i zestawieniu wchodz acych w jego skład czynnosci

• ocenie parametrów poszczególnych czynnosci i zdarze n

• konstrukcji sieci zaleznosci technologicznych

• wyznaczeniu podstawowych charakterystyk sieci dotycz acych

poszczególnych czynnosci, zdarze n i całego projektu

• wyznaczeniu sciezki krytycznej

Instytut Sterowania i Systemów Informatycznych

Uniwersytet Zielonogórski

Badania operacyjne

Programowanie sieciowe. Metoda CPM

Reguły obowi azuj ace przy konstrukcji sieci:

• nalezy tak rozplanowac czynnosci przedsi ewzi ecia, aby graf nie zawierał

p etel, sciezek cyklicznych, itp.

• zaleca si e, aby nie wyst epowały skrzyzowania łuków (przejrzystosc)

• powinien istniec dokładnie jeden wierzchołek pocz atkowy i jeden ko ncowy

• wierzchołki i łuki powinny byc odpowiednio uporz adkowane

• kazda czynnosc moze byc zrealizowana tylko raz z prawdopodobie nstwem

równym jeden podczas wykonywania przedsi ewzi ecia

Instytut Sterowania i Systemów Informatycznych

Uniwersytet Zielonogórski

Badania operacyjne

Programowanie sieciowe. Metoda CPM

METODA SCIE ZKI KRYTYCZNEJ – CPM

Mozna przedstawic przedsi ewzi ecia w postaci spójnego, acyklicznego digrafu

G =( S,E ), E ⊂ S × S takiego, ze istnieje jeden wierzchołek S i =0 (tzn. liczba

łuków wychodz acych =0) i jeden wierzchołek S i =0 (tzn. liczba łuków

wchodz acych =0). W graﬁe takim wierzchołki oznaczaj a zdarzenia, zas łuki –

czynnosci

Graf taki modeluje list e czynnosci uwzgl edniaj ac ograniczenia technologiczne i

nast epstwo czasowe

Zdarzenia powinny byc tak uporz adkowane, aby przyporz adkowane im numery

okreslały nast epstwo zdarze n w czasie

Nalezy ponumerowac wierzchołki sieci zgodnie z warunkiem

jeżeli( i,j ) ∈ E, to i<j

Instytut Sterowania i Systemów Informatycznych

Uniwersytet Zielonogórski

Badania operacyjne

Programowanie sieciowe. Metoda CPM

Algorytm przenumerowania wierzchołków grafu

Krok 1. Dla danej sieci wyznacz odpowiadaj ac a jej macierz binarn a

Krok 2. Do warstwy w 0 zalicz te zdarzenia, które odpowiadaj a zerowym

kolumnom macierzy B

Krok 3. Z macierzy B wykresl zerowe kolumny oraz wiersze o tych samych

numerach co wykreslone kolumny

Krok 4. Do warstwy kolejnej zalicz wierzchołki odpowiadaj ace zerowym

kolumnom zredukowanej macierzy B

Krok 5. Powtórz czynnosci 3 i 4

Instytut Sterowania i Systemów Informatycznych

Uniwersytet Zielonogórski

Badania operacyjne

Programowanie sieciowe. Metoda CPM

Przykład 6.1. Dana jest macierz B . Narysowac graf oraz przenumerowac wierzchołki

1 2 3 4 5 6

1 2 3 4 5

0 0 0 1 0 0

1 0 1 0 1 0

1 0 0 0 0 0

0 0 0 0 0 0

0 0 0 1 0 0

0 1 1 0 0 0

1 3 4 5

4 0 0 1 0

0 0 0 1 0

1 0 1 0 1

1 0 0 0 0

0 0 0 0 0

0 0 0 1 0

1 4

B =

1 0 0 0

0 0 0 0

0 0 1 0

B =

0 1

0 0

1. Wykreslamy 6 kolumn e i 6 wiersz (warstwa w 0 )

2. Wykreslamy 2 kolumn e i 2 wiersz (warstwa w 1 )

3. Wykreslamy 3 i 5 kolumn e, 3 i 5 wiersz (warstwa w 2 )

4. Wykreslamy 1 kolumn e i 1 wiersz (warstwa w 3 )

5. Pozostaje 4 kolumna (warstwa w 4 )

Instytut Sterowania i Systemów Informatycznych

Uniwersytet Zielonogórski

Badania operacyjne

Programowanie sieciowe. Metoda CPM

Wynikowy graf z now a numeracj a wierzchołków

2 (2)

5 (4)

6 (1)

4 (6)

1 (5)

3 (3)

W 0

W 1

W 2

W 3

W 4

Instytut Sterowania i Systemów Informatycznych

Uniwersytet Zielonogórski

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: