Metody rozwiązywania
problemów.
Metody matematyczne.
Dr inż. Eugeniusz Neumann
eneumann@wp.pl
Metody rozwiązywania
problemów.
Metody matematyczne.
Dr inż. Eugeniusz Neumann
eneumann@wp.pl
2
Literatura
Krawczyk S., Metody ilościowe w
planowaniu, Tom I, C.H. Beck,
Warszawa 2001
3
Metody matematyczne
Prognozowanie (ekstrapolacja trendów)
Metody sieciowe
CPM (CPM COST)
PERT (PERT COST)
MPM
GERT
Programowanie liniowe (optymalizacja)
4
Składowe prognozy
Sprzedaż
Szereg czasowy
Wahania cykliczne
Wahania przypadkowe
Wahania sezonowe
trend
stały poziom
czas
5
Metoda arytmetycznej średniej
ruchomej
y
t
(n) - n-okresowa arytmetyczna średnia
liczona po okresie t.
zaobserwowane wielkości popytu w
okresach
n – ilość okresów średniej
n
y
y
...
y
(n)
y
t
1
-
t
1
n
-
t
t
6
Arytmetyczna średnia ruchoma o
zróżnicowanych wagach
gdzie:
γ
i
- wartość wagi przypisanej i-temu
czynnikowi
β – wartość współczynnika przyjmowana
odpowiednio do liczby okresów
uwzględnianych w uśrednianiu- wartość
współczynnika wynika z tabeli.
y
t
(n) = γ
n
y
t
+ γ
n-1
y
t-1
+ ... + γ
1
y
t-n+1
n
i
i
7
Wartość współczynnika β
8
Model Browna
Jeden z najpopularniejszych modeli w prognozach
krótkoterminowych.
W modelu tym wagi tworzą postęp geometryczny o ilorazie
( 1 - α ). Szereg wartości wag wyrównania wykładniczego
wynosi:
α, α( 1 - α ), α ( 1 - α )
2
, α ( 1 - α )
3
Równoważnym zapisem do sumy ważonych wg powyższych
wag jest prognoza określona poniższym równaniem:
a
t
= α y
t
+ ( 1 - α ) a
t-1
gdzie:
α – parametr wyrównania wykładniczego z przedziału <0;1>,
szacowany metodą przybliżeń
a
t
, a
t-1
– wyrównanie wykładnicze po okresach t i t-1
y
t
– ostatnia wartość sprzedaży
9
Model Browna z sygnałem Trigga
Błędu prognozy:
e
t
=y
t
– ŷ
t
Wyrównanego wykładniczo po okresie t średniego
błędu prognozy:
ē
t
= δ e
t
+ (1 – δ)ē
t-1
Wyrównanego wykładniczo po okresie t średniego
bezwzględnego błędu prognozy:
đ
t
= δ| e
t
|+ (1 – δ)đ
t-1
sygnał Trigga, to zmienny w czasie parametr α
α
t
= |ē
t
/ đ
t
|
10
Model Holta
Stosowany, gdy szereg czasowy wykazuje istotne
zmiany trendu. Model Holta opisany jest układem
równań:
Ocena wartości średniej:
a
t
= α y
t
+ ( 1 - α )(a
t-1
+ b
t-1
)
Ocena przyrostu średniej (trendu):
b
t
= β (a
t
– a
t-1
) +( 1 – β ) b
t-1
Prognoza na okres t+T:
ŷ
t+T
= a
t
+ b
t
x T
11
Metoda wyznaczania
wskaźników sezonowości
Scentralizowana średnia ruchoma:
Y(7śr) =[0,5y(1)
+y(2)+y(3)+y(4)+y(5)+y(6)+y(7)+y(8)+y(9)+y(10)+y(11)+y(12)+0,5y
(13)]/12
Średnia dla miesiąca:
Wskaźnik sezonowości (7)= y(7) /
Y(7śr)
Wskaźniki sezonowości należy uśrednić
12
Metoda Wintersa
T
K
t
t
t
T
t
K
t
t
t
t
t
t
t
t
t
t
K
t
t
t
c
T
b
a
y
c
a
y
c
b
a
a
b
b
a
c
y
a
)
(
)
1
(
)
1
(
)
(
)
)(
1
(
1
1
1
1
13
Metoda Wintersa
i
sezonowo
śe
cykl
K
wyrównania
parametry
T
t
okres
na
prognoza
y
i
sezonowo
śe
wska
źskaź
ocena
c
trendu
przyrostu
ocena
b
trendu
ocena
a
T
t
t
t
t
,
,
14
Modele przyczynowo - skutkowe
Liniowy model przyczynowo skutkowy.
ŷ = a + bx
a = y
śr
–b x
śr
gdzie:
ŷ – zmienna prognozowana (objaśniana)
a, b – parametry strukturalne
x – zmienna objaśniająca
2
2
x
x
n
y
x
xy
n
b
15
Regresja wieloraka
ŷ = a + b
1
x
1
+b
2
x
2
2
2
2
2
1
1
2
2
2
1
2
2
1
1
1
1
2
2
1
1
x
b
x
x
b
x
a
y
x
x
x
b
x
b
x
a
y
x
x
b
x
b
na
y
16
Techniki sieciowe
Technika CPM (Critical Path Method) –
metoda ścieżki krytycznej
Technika PERT (Program Evaluation and
Review Technique)
Technika CPM-COST
Technika PERT-COST
Technika GERT
Technika MPM (Metra Potential Methode)
Technika GERTS (Graphical Evaluation and
Review Technique Simulation)
17
Metoda CPM –
wyznaczanie ścieżki
krytycznej
Termin zdarzenia rozpoczynającego
przedsięwzięcie jest równy zeru: T
(w)
= T
(p)
=0
(Najwcześniejszy Możliwy Termin=
Najpóźniejszemu Dopuszczalnemu Terminowi=0)
Wyznaczanie najwcześniejszych terminów zdarzeń
T
j(w)
rozpoczyna się od zdarzenia początkowego.
Najwcześniejszy termin wystąpienia zdarzenia j-
tego jest związany z warunkiem zakończenia
wszystkich czynności poprzedzających zdarzenie j.
T
j(w)
=max (T
i(w)
+ t
ij
)
18
Metoda CPM
Przyjmuje się, że najpóźniejszy termin
wystąpienia zdarzenia końcowego, jest
równy najwcześniejszemu terminowi
wystąpienia tego zdarzenia (T
n(p)
=T
n(w)
)
Wyznaczenie najpóźniejszego terminu
zdarzeń T
i(p)
rozpoczyna się od zdarzenia
końcowego. Obliczenia najpóźniejszych
dopuszczalnych terminów zdarzeń
przeprowadza się przesuwając się w lewo,
wzdłuż sieci: T
j(p)
=min (T
i(p)
- t
ij
)
Wyznaczenie ścieżki krytycznej: to droga
przechodząca przez węzły, o zerowym luzie
czasowym
19
Metoda CPM-COST -
algorytm
Zestawienie czynności krytycznych z
podaniem ich gradientów kosztów S i czasów
granicznych
Wyeliminowanie czynności krytycznych o
zerowym gradiencie kosztów
Proces skracania rozpoczyna się od czynności
krytycznej o najniższym gradiencie kosztów S
tg
t
t
K
K
S
gr
n
n
gr
20
CPM-COST
Przy skróceniu czasu o maksymalny
czas występują dwa ograniczenia: czas
graniczny danej czynności oraz
pojawienie się nowej ścieżki krytycznej
Przy istnieniu dwóch lub więcej ścieżek
krytycznych, czas należy skracać o tę
samą wartość na wszystkich
równoległych ścieżkach krytycznych
21
CPM-COST
Najkrótszy termin wykonania programu
sieciowego uzyskuje się, gdy wszystkie
czynności leżące na jakiejkolwiek
ścieżce krytycznej osiągną wartości
krytyczne. Dalsze skracanie czasu jest
wówczas niemożliwe.
Koszty przyspieszenia oblicza się
mnożąc skrócony czas danej czynności
krytycznej przez jej gradient kosztów.
22
Metoda PERT
Budowanie sieci czynności
Wyznaczenie wartości oczekiwanej
czasu trwania każdej czynności T
e
Wyznacza się wariancje czasu trwania
każdej czynności (W
e
)
6
4
b
m
a
T
e
36
)
(
2
a
b
W
e
23
PERT- algorytm
Obliczamy w każdym węźle czasy T
j(w)
oraz
T
j(p)
Wyznaczamy ścieżkę krytyczną
Obliczamy ze ścieżki krytycznej
najwcześniejszy prawdopodobny termin
zdarzenia końcowego (t
w
)
Ustalamy termin dyrektywny (t
d
)
)
min(
)
max(
)
(
)
(
)
(
)
(
ij
p
j
p
i
ij
w
i
w
j
t
T
T
t
T
T
24
PERT – algorytm
Oblicza się sumę wariancji w węzłach
krytycznych wyznaczających ścieżkę
krytyczną (W
tw
)
Obliczamy zmienną standaryzowaną ze
wzoru:
Obliczamy prawdopodobieństwo
dotrzymania terminu dyrektywnego:
tw
w
d
W
t
t
x
0
)
(
5
,
0
)
(
0
)
(
5
,
0
)
(
x
dla
x
x
F
x
dla
x
x
F
25
Metoda PERT-COST
Zakłada się liniowy przebieg zależności
kosztów od czasu. Zakłada się stałe
relacje, odpowiednio dla wartości a i b:
2
1
r
t
b
t
b
t
b
r
t
a
t
a
t
a
gr
gr
es
s
en
n
gr
gr
es
s
en
n
26
PERT-COST
Określenie czasu modalnego, wariancji,
odchylenia standardowego, gradient
kosztów:
egr
en
n
gr
es
ij
es
ij
es
t
t
K
K
S
t
r
r
t
r
r
t
r
r
m
6
36
)
(
4
)
(
6
1
2
2
2
1
2
2
2
1
27
Technika MPM
W technice MPM (Metra Potential Methode)
projekt przedstawiany jest w postaci wykresu
sieciowego
Dokonywana jest analiza czynności krytycznych
w sieci o sztywnej, deterministycznej strukturze
Dla odróżnienia sieci jednopunktowych (MPM) od
dwupunktowych (CPM, PERT) w technice MPM
czynności przedstawiane są jako prostokąty z
zaznaczonymi wewnątrz numerami i opisami.
Łuki grafu oznaczone są strzałkami pionowymi,
poziomymi lub ukośnymi
28
Technika MPM - algorytm
Określenie projektu i przygotowanie analizy jego
struktury
Określenie zależności pomiędzy poszczególnymi
czynnościami wchodzącymi w skład projektu
Sporządzenie wykresu sieciowego łączącego
wszystkie czynności
Przypisanie poszczególnym czynnościom
zakładanego czasu realizacji oraz wskazanie
momentu rozpoczęcia czynności w stosunku do
terminu rozpoczęcia czynności poprzedzającej
29
Technika MPM - algorytm
Obliczenie najwcześniejszych terminów
rozpoczęcia i zakończenia czynności
Obliczenie terminu zakończenia całego
projektu, najpóźniejszych terminów
rozpoczęcia i zakończenia czynności
Obliczenie zapasów czasu i wskazanie
czynności krytycznych
30
Metoda GERT
Odmiana sieci GAN dająca możliwość
wielowariantowego ustalenia zależności
między zdarzeniami oraz twórczego
dobierania w trakcie realizacji innych dróg
niż pierwotnie ustalono.
Sieci o strukturze logicznej stochastycznej
są charakteryzowane przez wierzchołki
logiczne oraz parametry addytywne i
multiplikatywne opisujące łuki sieci.
Określono trzy logiczne relacje wejścia
(alternatywa rozłączna, łączna i koniunkcja)
oraz dwa typy relacji wyjścia
(deterministyczne i probabilistyczne)
31
Metoda GERT - algorytm
Zmiana jakościowego opisu problemu na
model w postaci stochastycznej
Zebranie informacji niezbędnych do opisania
wszystkich gałęzi sieci
Określenie funkcji ekwiwalentnej opisującej
jednoznacznie sieć pierwotną
Zmiana funkcji ekwiwalentnej na dwie miary
sieci:
Prawdopodobieństwo tego, że określone zdarzenie
jest zrealizowane
Funkcję generującą moment (FGM) czasu
korespondującą z siecią ekwiwalentną
Konkluzja dotycząca systemu
32
GERTS(Graphical Evaluation
and Review Technique
Simulation)
Wykorzystuje się generatory liczb
pseudolosowych:
Dla węzłów o alternatywnych wyjściach, liczby losowe
z rozkładów prawdopodobieństwa określonych na tych
wyjściach – wyznaczenie podsieci wariantowych
Dla każdej czynności tak uzyskanych sieci generuje się
liczbę losową z rozkładu prawdopodobieństwa
opisującą czas realizacji tej czynności
Powyższe dane traktuje się jako
deterministyczne i dokonuje się dalszych
obliczeń np. wykorzystując metodę CPM
Powyższe kroki powtarza się wielokrotnie do
momentu uzyskania zadowalających wielkości,
np. czasu zakończenia projektu