2012-03-27
Pochodzenie metod sieciowych
Badania operacyjne
 Badania operacyjne to budowanie modeli, a ściślej mówiąc, modeli
użytecznych. Mogą to być modele dowolnego rodzaju i dowolnie złożone.
Użyteczne będą wówczas, gdy ich zachowanie się będzie analogiczne do
zachowania się systemu rzeczywistego w takim stopniu, iż będzie można
Metody sieciowe w
przewidywać zachowanie się tego systemu i zmieniać je w pożądany
sposób
budownictwie  Celem badań operacyjnych jest opracowanie systematycznego i
racjonalnego podejścia do rozwiązywania głównych zadań sterowania
systemami
 Badania operacyjne to zastosowanie metod nauki do złożonych
problemów powstających w kierowaniu i zarządzaniu złożonymi systemami
ludzi, maszyn, materiałów i pieniędzy w przemyśle, biznesie, administracji i
obronie
Podejmowanie decyzji
" Znane nazwiska: Kantorowicz, Erlang, Bellman, Neumann
GENEZA ZAKRES B.O.
II WOJNA ÅšWIATOWA  zarzÄ…dzanie, planowanie, logistyka
" Programowanie liniowe
Decydujące znaczenie dla wyodrębnienia się tej dyscypliny
" Programowanie dynamiczne
wiedzy miała działalność zespołu w ramach U.K. Naval
Operational Research, nazwanego  cyrkiem Blacketta , od
" Programowanie nieliniowe
nazwiska Patricka Blacketta (1897- 1974), laureata Nagrody
Nobla w dziedzinie fizyki w 1948r, który pełnił w nim " Programowanie całkowitoliczbowe
czołową rolę. Sukcesy tego zespołu, dotyczące m.in.
" Metody sieciowe
organizacji konwojów morskich i obrony powietrznej,
doprowadziły do spostrzeżenia, że zastosowany przezeń
" Problematyka kolejek
sposób podejścia ma charakter znacznie ogólniejszy.
Równocześnie powstały podobne zespoły w armii
" Zagadnienia transportowe i przydziału
amerykańskiej (U.S. Navy Antisabmarine Warfare
Operations Research Group oraz U.S. Air Force Operations " Teoria gier
Research)
Metody sieciowe Metody sieciowe - klasyfikacja
W 1958 roku opracowano w USA dwie ważne metody " Metody programowania sieciowego to techniki
sieciowego planowania projektów: planowania przedsięwzięć zapewniające sprawny przebieg
ich wykonania. Obecnie istnieje wiele takich metod, często
" DuPont Inc. - metoda ścieżki krytycznej (CPM - Critical Path
znacznie się od siebie różniących. Ze względu na strukturę
Method) stosowana do harmonogramowania projektów o
logiczną metody sieciowe można podzielić na: sieci o
zdeterminowanym czasie realizacji zadań składowych,
strukturze logicznej zdeterminowanej (sieci typu DAN 
" Lockheed Corporation - metoda PERT (Programm
Deterministic Analysis Network) i stochastycznej (sieci typu
Evaluation and Review Technique), stosowana do
GAN  Generalized Analysis Network).
harmonogramowania projektów z uwzględnieniem
" Do typowych zastosowań planowania sieciowego
losowości czasu realizacji zadań składowych, stosowana
przedsięwzięć zalicza się projektowanie zamierzeń na
początkowo do projektów badawczo-rozwojowych w
wielkÄ… skalÄ™ (programy kosmiczne, zbrojeniowe,
sektorze militarnym (projekt rakiet balistycznych POLARIS).
uprzemysłowienia kraju itd.), oraz na mniejszą skalę 
planowanie i kontrola prac budowlanych, remontowych,
prac badawczych itp.
1
2012-03-27
Metody sieciowe  podstawowe
Metody sieciowe - klasyfikacja
pojęcia
a. według znaczenia przypisywanego elementom sieci
- o notacji strzałkowej (strzałka, graf  czynność) - DWUPUNKTOWE " Zdarzenie  w modelu sieciowym oznacza osiągnięcie stanu
zaawansowania pracy przy realizacji projektu. Jest to moment
- o notacji węzłowej (węzeł  czynność) - JEDNOPUNKTOWE
rozpoczęcia lub zakończenia jednej lub kilku czynności. Zdarzenia
b. według sposobów traktowania rzeczywistości poprzez strukturę i
przedstawiamy przy pomocy okręgów, prostokątów lub innych figur
parametry sieci
geometrycznych.
- struktura deterministyczna i parametry deterministyczne
i
i
- struktura deterministyczna i parametry probabilistyczne (zmienne
t i L i T i
t i T i
losowe) L i
- struktura probabilistyczna i parametry deterministyczne
- struktura probabilistyczna i parametry probabilistyczne
i  numer zdarzenia, i = 1, 2, 3, ...
c. zależności sieciowe
t i  najwcześniejszy możliwy moment zaistnienia zdarzenia i
- funkcje czasowe
Ti  najpóz
niejszy dopuszczalny moment zaistnienia zdarzenia i
- zależności zasobowe i środków produkcji
L i - zapas czasu dla zdarzenia i
Metody sieciowe  podstawowe Metody sieciowe  podstawowe
pojęcia pojęcia
" Czynność  dowolnie wyodrębniona część projektu
charakteryzująca się czasem trwania i zużywaniem środków.
Czynności przedstawiamy przy pomocy strzałek (wektorów)
łączących zdarzenia. Kierunek strzałki przedstawia zależności między
czynnościami. Czynność charakteryzuje para wskaz
ników i-j, gdzie i
jest numerem zdarzenia, w którym czynność się rozpoczyna, a j 
numerem zdarzenia w którym czynność się kończy.
" Czynność pozorna  szczególny typ czynności, które nie zużywają
czasu (jej czas trwania jest równy zeru) ani środków. Służą jedynie
Czas najkrótszy(najwcześniejszy moment zaistnienia zdarzenia o numerze 'i') , jest to
do przedstawienia zależności między czynnościami. Czynności
najdłuższy czas przejścia od zdarzenia pierwszego do zdarzenia 'i'-tego. pozorne przedstawiamy przy pomocy strzałek (wektorów)
Czas najdłuższy(najpóz
niejszy moment zaistnienia zdarzenia), jest to różnica przerywanych.
pomiędzy czasem krytycznym a najdłuższym czasem przejścia od tego zdarzenia do
zdarzenia końcowego.
Metody sieciowe - zasady Metody sieciowe - zasady
" Wykres sieciowy może mieć kilka początkowych i kilka
" Zdarzenia początkowe nie mają czynności
końcowych zdarzeń i wówczas łączy się je czynnościami
poprzedzajÄ…cych.
pozornymi w jedno zdarzenie poczÄ…tkowe i jedno
zdarzenie końcowe.
" Zdarzenia końcowe nie mają czynności
następujących po nich
" Dane zdarzenie nie może nastąpić, dopóki nie zakończą
się wszystkie czynności prowadzące do niego i
warunkujące zajście tego zdarzenia.
2
2012-03-27
Metody sieciowe - zasady Metody sieciowe - zasady
" Żadna kolejna czynność nie może się rozpocząć, dopóki nie
" Dwa zdarzenia mogą być połączone tylko jedną
zaistnieje zdarzenie kończące czynności poprzedzające.
czynnością. Jeżeli kilka czynności wykonywanych
" Wektory czynności powinny być skierowane z lewej strony
jest równolegle pomiędzy dwoma zdarzeniami to
do prawej
należy wprowadzić czynności pozorne.
" Wykres sieciowy nie powinien mieć obiegów zamkniętych,
tj. pętli łączących dwukrotnie te same zdarzenia.
Metody sieciowe - zasady Metoda ścieżki krytycznej
" Zdarzenia i czynności powinny być odpowiednio uporządkowane,
" Metoda CPM (Critical Path Method), zwana po polsku
tzn. każdy poprzednik ma mieć mniejszy numer lub wcześniejszą
metodą drogi lub ścieżki krytycznej, pozwala na
literę od następnika (zatem numerując zdarzenia należy zwracać
przeprowadzanie analiz czasów trwania oraz kosztów
uwagę na to, by zdarzenie wcześniejsze miało mniejszy numer i < j).
poszczególnych czynności wchodzących w skład danego
Wymóg ten wyklucza wystąpienie cyklu (tzn. sytuacji, gdy
wychodząc z jednego wierzchołka i poruszając się po krawędziach, projektu.
można do tego samego wierzchołka wrócić.
" Typowy problem rozwiÄ…zywany metodÄ… CPM polega na
tym, że całe przedsięwzięcie należy wykonać po
ustalonych kosztach w jak najkrótszym czasie. Jeżeli
zachodzi potrzeba ukończenia projektu wcześniej,
można tego dokonać ponosząc dodatkowe koszty.
Problemy tego typu można rozwiązywać ręcznie lub
dowolnym programem komputerowym szukania
najdłuższej drogi.
i i
Metoda ścieżki krytycznej
t i T i t i L i T i
L i
i i
i  numer zdarzenia, i = 1, 2, 3, ...
t i T i t i L i T i
L i Ti  najpóz
niejszy dopuszczalny moment zaistnienia zdarzenia i
Po wyznaczeniu najwcześniejszych możliwych momentów zaistnienia
i  numer zdarzenia, i = 1, 2, 3, ...
poszczególnych zdarzeń obliczamy najpóz
niejsze dopuszczalne momenty
t i  najwcześniejszy możliwy moment zaistnienia zdarzenia i
zaistnienia poszczególnych zdarzeń, zaczynając od zdarzenia końcowego i
poruszając się w kierunku przeciwnym ze zwrotem strzałek. Aby
przedsięwzięcie zrealizować w najkrótszym możliwym czasie przyjmuje się, że
Ponieważ zdarzenie można uznać za zrealizowane dopiero najpóz
niejszy dopuszczalny moment zaistnienia zdarzenia końcowego jest
równy najwcześniejszemu możliwemu terminowi jego zaistnienia . Wielkość tę
wówczas, gdy zostaną zakończone wszystkie prowadzące do
wpisujemy arbitralnie w prawej ćwiartce zdarzenia końcowego, a następnie
niego czynności, dlatego w przypadku gdy do zdarzenia
wyznaczamy najpóz
niejsze dopuszczalne terminy dla wszystkich pozostałych
dochodzi więcej niż jedna czynność, najwcześniejszy
zdarzeń. Najpóz
niejszy dopuszczalny moment zaistnienia zdarzenia
możliwy moment zaistnienia tego zdarzenia jest równy poprzedniego (i) obliczamy odejmując od najpóz
niejszego dopuszczalnego
terminu zdarzenia następnego (j) czas trwania czynności i-j. Jeżeli do zdarzenia
maksymalnej z tak obliczonych wielkości, czyli:
dochodzi więcej niż jedna czynność, wybieramy wielkość najmniejszą, czyli:
t =ð max {ðti +ð ti-ð j}ð
j i
Ti =ð min {ðTj -ð ti-ð j}ð
j
3
2012-03-27
Metoda ścieżki krytycznej
Ścieżka krytyczna
" L i - zapas czasu dla zdarzenia i
Po wyznaczeniu najwcześniejszych możliwych i " Ścieżka krytyczna jest najdłuższą drogą w sieci (wszystkie
dopuszczalnych momentów zaistnienia zdarzeń (t oraz T), czynności muszą być zakończone), a jej czas trwania (suma
obliczamy zapasy czasu dla poszczególnych zdarzeń: czasów kolejnych czynności leżących na ścieżce krytycznej)
jest równa terminowi końcowemu. Należy zaznaczyć, iż w
Li =ð Ti -ð ti
sieciach może występować więcej niż jedna ścieżka
krytyczna.
Zapas czasu zdarzenia jest różnicą między najpóz
niejszym
" Układ czynności na drodze krytycznej wskazuje, w jakiej
dopuszczalnym a najwcześniejszym możliwym terminem
kolejności powinny następować czynności krytyczne, aby
jego zaistnienia.
czas wykonania całego przedsięwzięcia był najkrótszy.
Znajomość czynności krytycznych ułatwia planowanie,
W celu wyznaczenia ścieżki krytycznej, należy znać także kierowanie i koordynację realizacji przedsięwzięcia,
zapasy czasu dla czynności, które wyznacza się według ponieważ przekroczenie terminu zakończenia którejkolwiek
wzoru: czynności krytycznej powoduje opóz
nienie wykonania
Zi-ð j =ð (ðT -ð ti -ð j )ð-ð ti caÅ‚ego projektu.
j
Metoda PERT
" Metoda PERT (Program Evaluation and Review Technique) jest stochastycznÄ…
wersją metody CPM. Oznacza to, że czasy wykonywania poszczególnych czynności
oraz czas realizacji całego przedsięwzięcia są zmiennymi losowymi. Przyjmuje się,
że czasy te mają rozkład normalny. Ponieważ uzyskanie informacji ile wynoszą
parametry rozkładu normalnego dla każdej czynności byłoby trudne, parametry te
oblicza statystyk (lub komputer) przy użyciu następujących wzorów i na postawie
następujących danych dostarczonych przez technologów
" - średni (oczekiwany) czas wykonania czynności:
a +ð 4m +ð b
t =ð
e
6
" - wariancja czasu trwania czynności:
2
2 éðb -ð a Å‚ð
sð =ð
Ä™ð Å›ð
6
ëð ûð
gdzie:
a  czas optymistyczny trwania czynności (najkrótszy możliwy czas wykonania
czynności),
b  czas pesymistycznytrwania czynności (najdłuższy przewidywalny czas
wykonania czynności),
m  czas modalny, najbardziej prawdopodobny.
4