Metody rozwiązywania

problemów.

Metody matematyczne.

Dr inż. Eugeniusz Neumann

[e-mail]

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