Badania operacyjne

dr Radosław Jadczak

Katedra Bada

ń

Operacyjnych

Bud. „E” pok. E136

WT, 9.45-11.00

[e-mail]

Badania operacyjne – zakres zagadnie

ń

(1)

1.

Elementy teorii podejmowania decyzji

podejmowanie decyzji w warunkach niepewno

ś

ci

podejmowanie decyzji w warunkach ryzyka

2.

Liniowe modele decyzyjne

budowa modeli decyzyjnych

poszukiwanie i analiza rozwi

ą

za

ń

optymalnych

analiza postoptymalizacyjna

3.

Modelowanie zło

ż

onych przedsi

ę

wzi

ęć

wieloczynno

ś

ciowych

(zarz

ą

dzanie projektami)

deterministyczna analiza przedsi

ę

wzi

ę

cia

probabilistyczna analiza przedsi

ę

wzi

ę

cia

kosztowo-czasowa analiza przedsi

ę

wzi

ę

cia

Badania operacyjne – literatura i oprogramowanie

1. Krawczyk S., Badania operacyjne dla mened

ż

erów, Wyd. AE we

Wrocławiu, Wrocław, 1997

2. Kukuła K. (red.), Badania operacyjne w przykładach i zadaniach, PWN,

Warszawa, 1999

3. Miszczy

ń

ska D., Miszczy

ń

ski M., Wybrane metody bada

ń

operacyjnych,

WSzEH, Skierniewice, 2002

4. Trzaskalik T. , Wprowadzenie do bada

ń

operacyjnych z komputerem,

PWE, Warszawa, 2003

1. BAD_OP - pakiet programów zał

ą

czony do podr

ę

cznika [6]

2. SOLVER (narz

ę

dzie Excel’a w MS Office)

3. WinQSB
4. WinSTORM

Elementy teorii decyzji

Elementy teorii decyzji – gry z natur

ą

(1)

decyzja

rolnika

warunki pogodowe (stan natury)

susza

s

1

normalne

s

2

deszcze

s

3

d

1

– zbo

ż

e 1

24

28

36

d

2

– zbo

ż

e 2

31

30

28

d

4

– zbo

ż

e 3

28

34

29

d

4

– zbo

ż

e 4

27

29

33

d

5

– zbo

ż

e 5

31

30

29

Dwóch graczy:

1. decydent (rolnik) maj

ą

cy pi

ęć

mo

ż

liwo

ś

ci;

2. natura (warunki pogodowe) maj

ą

ca trzy mo

ż

liwo

ś

ci

Elementy teorii decyzji – gry z natur

ą

(2)

Analiza gry z natur

ą

oparta jest na:

1. macierzy wypłat (macierz korzy

ś

ci lub macierz strat)

































=

×

29

30

31

33

29

27

29

34

28

28

30

31

36

28

24

3

5

A

Elementy teorii decyzji – gry z natur

ą

(3)

Analiza gry z natur

ą

oparta jest na:

1. analizie drzewa decyzyjnego

2

1

3

4

5

6

d

1

d

2

d

3

d

4

d

5

s

2

s

3

s

1

s

2

s

3

s

1

s

2

s

3

s

1

s

2

s

3

s

1

s

2

s

3

24
28
36

31
30
28

28
34
29

27
29
33

31
30
29

s

1

Podejmowanie decyzji w warunkach niepewno

ś

ci (1)

Kryteria wyboru decyzji:

1. kryterium MaxiMax (kryterium ryzykanta, optymisty)

2. kryterium MaxiMin (kryterium asekuranta, pesymisty)

3. kryterium Hurwicza (kompromis pomi

ę

dzy MaxiMax a MaxiMin)

4. kryterium Savage’a (kryterium MiniMax „

ż

alu”)

5. kryterium Laplace’a (maksymalizacja oczekiwanego zysku)

Podejmowanie decyzji w warunkach niepewno

ś

ci (2)

Kryterium MaxiMax:

1. Dla ka

ż

dej decyzji d

i

wyznacz maksymalny zysk o

i

2. Wska

ż

decyzj

ę

d

k

, dla której maksymalny zysk o

i

jest najwi

ę

kszy

{ }

{ }









=

=

i

i

k

ij

j

i

o

max

o

a

max

o

































=

×

29

30

31

33

29

27

29

34

28

28

30

31

36

28

24

3

5

A

o

1

= max{24;28;36} = 36

o

2

= max{31;30;28} = 31

o

3

= max{28;34;29} = 34

o

4

= max{27;29;33} = 33

o

5

= max{31;30;29} = 31

o

k

= max{36;31;34;33;31} = 36

d

1

Podejmowanie decyzji w warunkach niepewno

ś

ci (3)

Kryterium MaxiMin:

1. Dla ka

ż

dej decyzji d

i

wyznacz minimalny zysk p

i

2. Wska

ż

decyzj

ę

d

k

, dla której minimalny zysk p

i

jest najwi

ę

kszy

{ }

{ }









=

=

i

i

k

ij

j

i

p

max

p

a

min

p

































=

×

29

30

31

33

29

27

29

34

28

28

30

31

36

28

24

3

5

A

p

1

= min{24;28;36} = 24

p

2

= min{31;30;28} = 28

p

3

= min{28;34;29} = 28

p

4

= min{27;29;33} = 27

p

5

= min{31;30;29} = 29

p

k

= max{24;28;28;27;29} = 29

d

5

Podejmowanie decyzji w warunkach niepewno

ś

ci (4)

Kryterium Hurwicza:

1.

α

i

∈

(0,1) – skłonno

ść

do ryzyka przy decyzji d

i

2. Dla ka

ż

dej decyzji d

i

wyznacz

ś

redni wa

ż

ony zysk h

i

z zysków:

maksymalnego (o

i

) i minimalnego (p

i

)

3. Wska

ż

decyzj

ę

d

k

, dla której

ś

redni wa

ż

ony zysk h

i

jest najwi

ę

kszy

{ }









=

−

+

=

i

i

k

i

i

i

i

i

h

max

h

p

o

h

)

1

(

α

α

































=

×

29

30

31

33

29

27

29

34

28

28

30

31

36

28

24

3

5

A

h

1

= 0,1

×

36 + (1-0,1)

×

24 = 25,2

h

2

= 0,3

×

31 + (1-0,3)

×

28 = 28,9

h

3

= 0,5

×

34 + (1-0,5)

×

28 = 29

h

4

= 0,7

×

33 + (1-0,7)

×

27 = 31,2

h

5

= 0,9

×

31 + (1-0,9)

×

29 = 30,8

h

k

= max{25,2; 28,9; 29; 31,2; 30,8} = 31,2

d

4

α

1

= 0,1

α

2

= 0,3

α

3

= 0,5

α

4

= 0,7

α

5

= 0,9

Podejmowanie decyzji w warunkach niepewno

ś

ci (5)

Kryterium Savage’a:

1. Zbuduj macierz „

ż

alu” R

































=

×

29

30

31

33

29

27

29

34

28

28

30

31

36

28

24

3

5

A

{ }

[

]







−

=

=

=

×

ij

j

ij

n

m

ij

i

j

a

a

r

a

max

a

R

































=

−

=

−

=

−

=

−

=

−

=

−

=

−

=

−

=

−

=

−

=

−

=

−

=

−

=

−

=

−

=

×

7

29

36

4

30

34

0

31

31

3

33

36

5

29

34

4

27

31

7

29

36

0

34

34

3

28

31

8

28

36

4

30

34

0

31

31

0

36

36

6

28

34

7

24

31

3

5

R

Podejmowanie decyzji w warunkach niepewno

ś

ci (6)

Kryterium Savage’a (c.d.):

2.

Operuj

ą

c na macierzy „

ż

alu” R wyznacz dla ka

ż

dej decyzji d

i

maksymalny „

ż

al” r

i

3.

Wska

ż

decyzj

ę

d

k

, dla której

ż

al r

i

jest najmniejszy

{ }

{ }









=

=

i

i

k

ij

j

i

r

min

r

r

max

r

































=

×

7

4

0

3

5

4

7

0

3

8

4

0

0

6

7

3

5

R

r

1

= max{7;6;0} = 7

r

2

= max{0;4;8} = 8

r

3

= max{3;0;7} = 7

r

4

= max{4;5;3} = 5

r

5

= max{0;4;7} = 7

r

k

= min{7;8;7;5;7} = 5

d

4

Podejmowanie decyzji w warunkach niepewno

ś

ci (7)

Kryterium Laplace’a:

1. Prawdopodobie

ń

stwo zaistnienia ka

ż

dego stanu natury jest jednakowe i

wynosi: P{s

j

} = 1/n

2. Dla ka

ż

dej decyzji d

i

wyznacz oczekiwan

ą

warto

ść

zysku l

i

u

ż

ywaj

ą

c w/w

prawdopodobie

ń

stwa stanu natury

3. Wska

ż

decyzj

ę

d

k

, dla której oczekiwana warto

ść

zysku l

i

jest najwi

ę

ksza

{ }









=

=

=

∑

∑

=

=

i

i

k

n

j

ij

n

j

ij

j

i

l

max

l

a

n

a

s

P

l

1

1

/

1

}

{

































=

×

29

30

31

33

29

27

29

34

28

28

30

31

36

28

24

3

5

A

l

1

= 1/3

×

24 + 1/3

×

28 + 1/3

×

36 = 29⅓

l

2

= 1/3

×

31 + 1/3

×

30 + 1/3

×

28 = 29⅔

l

3

= 1/3

×

28 + 1/3

×

34 + 1/3

×

29 = 30⅓

l

4

= 1/3

×

27 + 1/3

×

29 + 1/3

×

33 = 29⅔

l

5

= 1/3

×

31 + 1/3

×

30 + 1/3

×

29 = 30

l

k

= max{29⅓; 29⅔; 30⅓; 29⅔; 30} = 30⅓

d

3

Podejmowanie decyzji w warunkach ryzyka (1)

decyzja

rolnika

warunki pogodowe (stan natury)

susza

s

1

normalne

s

2

deszcze

s

3

P{s

1

} = 0,15

P{s

2

} = 0,50

P{s

1

} = 0,35

d

1

– zbo

ż

e 1

24

28

36

d

2

– zbo

ż

e 2

31

30

28

d

3

– zbo

ż

e 3

28

34

29

d

4

– zbo

ż

e 4

27

29

33

d

5

– zbo

ż

e 5

31

30

29

P{s

j

} – okre

ś

lone z góry prawdopodobie

ń

stwo zaistnienia stanu natury s

j

– prawdopodobie

ń

stwo a priori

Podejmowanie decyzji w warunkach ryzyka (2)

Kryteria wyboru decyzji:

1. kryterium maksymalnej oczekiwanej warto

ś

ci (MOW)

2. kryterium minimalnego oczekiwanego „

ż

alu”

Podejmowanie decyzji w warunkach ryzyka (3)

Kryterium maksymalnego oczekiwanego zysku (MOW):

1. Dla ka

ż

dej decyzji d

i

wyznacz oczekiwan

ą

warto

ść

zysku E

i

(a) u

ż

ywaj

ą

c

okre

ś

lonych prawdopodobie

ń

stw stanu natury

2. Wska

ż

decyzj

ę

d

k

, dla której oczekiwana warto

ść

zysku E

i

(a) jest

najwi

ę

ksza

{

}









=

=

∑

=

)

(

)

(

}

{

)

(

1

a

E

max

a

E

a

s

P

a

E

i

i

k

n

j

ij

j

i

































=

×

29

30

31

33

29

27

29

34

28

28

30

31

36

28

24

3

5

A

E

1

(a) = 0,15

×

24 + 0,50

×

28 + 0,35

×

36 = 30,20

E

2

(a) = 0,15

×

31 + 0,50

×

30 + 0,35

×

28 = 29,45

E

3

(a) = 0,15

×

28 + 0,50

×

34 + 0,35

×

29 = 31,35

E

4

(a) = 0,15

×

27 + 0,50

×

29 + 0,35

×

33 = 30,10

E

5

(a) = 0,15

×

31 + 0,50

×

30 + 0,35

×

29 = 29,80

E

k

(a)= max{30,20; 29,45; 31,35; 30,10; 29,80} = 31,35

d

3

P{s

1

}=0,15 P{s

2

}=0,50 P{s

3

}=0,35

Podejmowanie decyzji w warunkach ryzyka (4)

Kryterium minimalnego oczekiwanego „

ż

alu”:

1. Dla ka

ż

dej decyzji d

i

wyznacz oczekiwan

ą

warto

ść

„

ż

alu” E

i

(r) u

ż

ywaj

ą

c

okre

ś

lonych prawdopodobie

ń

stw stanu natury

2. Wska

ż

decyzj

ę

d

k

, dla której oczekiwana warto

ść

„

ż

alu” E

i

(r) jest

najmniejsza

{

}









=

=

∑

=

)

(

)

(

}

{

)

(

1

r

E

min

r

E

r

s

P

r

E

i

i

k

n

j

ij

j

i

































=

×

7

4

0

3

5

4

7

0

3

8

4

0

0

6

7

3

5

A

E

1

(r) = 0,15

×

7 + 0,50

×

6 + 0,35

×

0 = 4,05

E

2

(r) = 0,15

×

0 + 0,50

×

4 + 0,35

×

8 = 4,80

E

3

(r) = 0,15

×

3 + 0,50

×

0 + 0,35

×

7 = 2,90

E

4

(r) = 0,15

×

4 + 0,50

×

5 + 0,35

×

3 = 4,15

E

5

(r) = 0,15

×

0 + 0,50

×

4 + 0,35

×

7 = 4,45

E

k

(r)= min{4,05; 4,80; 2,90; 4,15; 4,45} = 2,90

d

3

P{s

1

}=0,15 P{s

2

}=0,50 P{s

3

}=0,35

Podejmowanie decyzji w warunkach ryzyka (5)

Cena graniczna doskonałej informacji

Cena graniczna doskonałej (perfekcyjnej) informacji to maksymalna kwota,
jak

ą

warto zainwestowa

ć

w dodatkowe badanie zwi

ą

zane z poznaniem

przyszłego zachowania si

ę

natury. Doskonała informacja to wiedza o przyszłym

stanie natury przed podj

ę

ciem decyzji.

Jaka b

ę

dzie korzy

ść

w warunkach doskonałej (perfekcyjnej) informacji (OKPI)?

{ }









=

=

∑

=

n

j

j

j

ij

j

j

a

s

P

OKPI

a

max

a

1

}

{

































=

×

29

30

31

33

29

27

29

34

28

28

30

31

36

28

24

3

5

A

s

1

: a

1

= max{24; 31; 28; 27; 31} = 31

s

2

: a

2

= max{28; 30; 34; 29; 30} = 34

s

3

: a

3

= max{36; 28; 29; 33; 29} = 36

P{s

1

}=0,15 P{s

2

}=0,50 P{s

3

}=0,35

OKPI = P{s

1

}

×

a

1

+ P{s

2

}

×

a

2

+ P{s

3

}

×

a

3

=

= 0,15

×

31 + 0,50

×

34 + 0,35

×

36 = 34,25

Podejmowanie decyzji w warunkach ryzyka (6)

Cena graniczna doskonałej informacji (c.d.)

Cena graniczna doskonałej (perfekcyjnej) informacji (CGPI) wynika z
porównania korzy

ś

ci osi

ą

ganej w warunkach doskonałej informacji z

korzy

ś

ci

ą

osi

ą

gan

ą

w warunkach zwykłych, tzn. w warunkach kiedy decyzja

musi by

ć

podj

ę

ta przed zarejestrowaniem stanu natury.

Jest to ró

ż

nica pomi

ę

dzy OKPI a kwot

ą

uzyskan

ą

z zastosowania kryterium

maksymalnej oczekiwanej warto

ś

ci (MOW):

CGPI = OKPI – MOW = 34,25 – 31,35 = 2,90

Uzyskana kwota CGPI jest równa minimalnemu oczekiwanemu „

ż

alowi”:

CGPI = E

k

(r)