Badania operacyjne
dr Radosław Jadczak
Wydział Ekonomiczno-Socjologiczny
Katedra Badań Operacyjnych
Bud. „T” pok. T409
PN, 11.30-13.00
rjadczak@pai.net.pl
www.kbo.uni.lodz.pl
Badania operacyjne – zakres zagadnień (1) 1.
Elementy teorii podejmowania decyzji
podejmowanie decyzji w warunkach niepewności
podejmowanie decyzji w warunkach ryzyka
podejmowanie decyzji w warunkach dodatkowej informacji
2.
Liniowe modele decyzyjne
budowa modeli decyzyjnych
poszukiwanie i analiza rozwiązań optymalnych
analiza postoptymalizacyjna
3.
Optymalizacja w zagadnieniach przewozowych
klasyczne zadanie transportowe
modyfikacje zadania transportowego
pochodne zadania transportowego – zagadnienie przydziału
Badania operacyjne – zakres zagadnień (2) 4.
Modelowanie złoŜonych przedsięwzięć wieloczynnościowych
(zarządzanie projektami)
deterministyczna analiza przedsięwzięcia
stochastyczna analiza przedsięwzięcia
5.
Modelowanie procesów o charakterze masowym
podstawowe pojęcia i definicje
klasyfikacja systemów masowej obsługi
6.
Wybrane nieliniowe problemy decyzyjne
1
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
Badania operacyjne – zaliczenie
Przedmiot będzie zaliczany na podstawie pracy kolokwialnej obejmującej zakres praktyczny i teoretyczny metod badań operacyjnych oraz indywidualnej oceny za pracę w trakcie laboratoriów komputerowych.
Sprawdzian odbędzie się w jednym terminie dla całego roku (wszystkie grupy). Obecność na sprawdzianie jest obowiązkowa. Zaliczenie nieobecności na sprawdzianie (usprawiedliwionej bądź nieusprawiedliwionej) moŜliwe jest tylko w terminie poprawkowym.
Termin sprawdzianu zaliczeniowego:
28.01-01.02.2008
Termin poprawkowy:
18.02−22.02.2008
(dokładna data, godzina i sala dla obu terminów zostaną podane później) Elementy teorii decyzji
2
Elementy teorii decyzji – gry z naturą (1) warunki pogodowe (stan natury)
decyzja
susza
normalne
deszcze
rolnika
s
s
s
1
2
3
d – zboŜe 1
24
28
36
1
d – zboŜe 2
31
30
28
2
d – zboŜe 3
28
34
29
4
d – zboŜe 4
27
29
33
4
d – zboŜe 5
31
30
29
5
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)
24 28 36
31 30 28
A ×
5 3 = 28
34
29
27 29 33
31 30 29
Elementy teorii decyzji – gry z naturą (3) Analiza gry z naturą oparta jest na:
1. analizie drzewa decyzyjnego
s1
24
s
2
2
28
d
s3
1
36
s1
31
s2
d
3
30
2
s3
28
s1
28
d
s
1
3
4
2
34
s3
29
s1
27
d
s2
4
5
29
s3
33
d
s1
5
31
s
6
2
30
s3
29
3
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 wyznacz maksymalny zysk o i
i
2. WskaŜ decyzję d , dla której maksymalny zysk o jest największy k
i
o
max a
i =
{ ij}
j
o
max o
k =
{ i}
i
24 28 36 o = max{24;28;36} = 36
1
31 30 28 o = max{31;30;28} = 31
2
A ×
5 3 = 28
34
29 o = max{28;34;29} = 34
o = max{36;31;34;33;31} = 36
3
k
27 29 33 o = max{27;29;33} = 33
4
31 30 29
o = max{31;30;29} = 31
5
d1
Podejmowanie decyzji w warunkach niepewności (3) Kryterium MaxiMin:
1. Dla kaŜdej decyzji d wyznacz minimalny zysk p i
i
2. WskaŜ decyzję d , dla której minimalny zysk p jest największy k
i
p
min a
i =
{ ij}
j
p
max p
k =
{ i}
i
24 28 36 p = min{24;28;36} = 24
1
31 30 28 p = min{31;30;28} = 28
2
A ×
5 3 = 28
34
29 p = min{28;34;29} = 28
p = max{24;28;28;27;29} = 29
3
k
27 29 33 p = min{27;29;33} = 27
4
31 30 29
p = min{31;30;29} = 29
5
d5
4
Podejmowanie decyzji w warunkach niepewności (4) Kryterium Hurwicza:
1. α ∈(0,1) – skłonność do ryzyka przy decyzji d
i
i
2. Dla kaŜdej decyzji d wyznacz średni waŜony zysk h z zysków: i
i
maksymalnego ( o ) i minimalnego ( p )
i
i
3. WskaŜ decyzję d , dla której średni waŜony zysk h jest największy k
i
h
α o
1
(
α ) p
i =
i i +
− i i
h max h
k =
{ i}
i
24 28 36 α = 0,1
h = 0,1×36 + (1-0,1)×24 = 25,2
1
1
31 30 28 α = 0,3
h = 0,3×31 + (1-0,3)×28 = 28,9
2
2
A ×
α
5 3 = 28
34
29
= 0,5
h = 0,5×34 + (1-0,5)×28 = 29
3
3
27 29 33 α = 0,7
h = 0,7×33 + (1-0,7)×27 = 31,2
4
4
31 30 29
α = 0,9
h = 0,9×31 + (1-0,9)×29 = 30,8
5
5
h = max{25,2; 28,9; 29; 31,2; 30,8} = 31,2
d
k
4
Podejmowanie decyzji w warunkach niepewności (5) Kryterium Savage’a:
1. Zbuduj macierz „Ŝalu” R
a
max a
j =
{ ij}
i
R
r
a
a
m× n = [ ij =
j −
ij ]
24 28 36
31− 24 = 7 34 − 28 = 6 36 − 36 = 0
31 30 28
31− 31 = 0 34 − 30 = 4 36 − 28 = 8
A
R ×
5 3 = 31 − 28 = 3
34 − 34 = 0 36 − 29 = 7
5×3 = 28
34
29
27 29 33
31 − 27 = 4 34 − 29 = 5 36 − 33 = 3
31 30 29
31− 31= 0 34 − 30 = 4 36 − 29 = 7
Podejmowanie decyzji w warunkach niepewności (6) Kryterium Savage’a (c.d.):
2.
Operując na macierzy „Ŝalu” R wyznacz dla kaŜdej decyzji di maksymalny „Ŝal” ri
3.
WskaŜ decyzję d , dla której Ŝal r jest najmniejszy k
i
r
max r
i =
{ ij}
j
r
min r
k =
{ i}
i
7 6 0
r = max{7;6;0} = 7
1
0 4 8
r = max{0;4;8} = 8
2
R
r = max{3;0;7} = 7
5×3 = 3
0
7
3
r = min{7;8;7;5;7} = 5
k
4 5 3
r = max{4;5;3} = 5
4
0 4 7
r = max{0;4;7} = 7
5
d4
5
Podejmowanie decyzji w warunkach niepewności (7) Kryterium Laplace’a:
1. Prawdopodobieństwo zaistnienia kaŜdego stanu natury jest jednakowe i wynosi: P{ s } = 1/ n
j
2. Dla kaŜdej decyzji d wyznacz oczekiwaną wartość zysku l uŜywając w/w i
i
prawdopodobieństwa stanu natury
3. WskaŜ decyzję d , dla której oczekiwana wartość zysku l jest największa k
i
l
P s
{
a
}
1/ n
a
i = ∑ n
n
j =1
j
ij =
∑ j=1 ij
l max l
k =
{ i}
i
24 28 36
l = 1/3×24 + 1/3×28 + 1/3×36 = 29⅓
1
31 30 28
l = 1/3×31 + 1/3×30 + 1/3×28 = 29⅔
2
A ×
5 3 = 28
34
29
l = 1/3×28 + 1/3×34 + 1/3×29 = 30⅓
3
27 29 33
l = 1/3×27 + 1/3×29 + 1/3×33 = 29⅔
4
31 30 29
l = 1/3×31 + 1/3×30 + 1/3×29 = 30
5
l = max{29⅓; 29⅔; 30⅓; 29⅔; 30} = 30⅓
d
k
3
Podejmowanie decyzji w warunkach ryzyka (1)
warunki pogodowe (stan natury)
decyzja
susza
normalne
deszcze
rolnika
s
s
s
1
2
3
P{s } = 0,15
P{s } = 0,50
P{s } = 0,35
1
2
1
d – zboŜe 1
24
28
36
1
d – zboŜe 2
31
30
28
2
d – zboŜe 3
28
34
29
4
d – zboŜe 4
27
29
33
4
d – zboŜe 5
31
30
29
5
P{ s } – określone z góry prawdopodobieństwo zaistnienia stanu natury s j
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”
6
Podejmowanie decyzji w warunkach ryzyka (3)
Kryterium maksymalnego oczekiwanego zysku (MOW):
1. Dla kaŜdej decyzji d wyznacz oczekiwaną wartość zysku E ( a) uŜywając i
i
określonych prawdopodobieństw stanu natury
2. WskaŜ decyzję d , dla której oczekiwana wartość zysku E ( a) jest k
i
największa
E ( a)
i
= ∑ nj= {
P s }
1
a
j
ij
P{s }=0,15 P{s }=0,50 P{s }=0,35
E ( a)
1
2
3
k
= max{ E ( a
i
}
)
i
24 28 36
E ( a) = 0,15×24 + 0,50×28 + 0,35×36 = 30,20
1
31 30 28
E ( a) = 0,15×31 + 0,50×30 + 0,35×28 = 29,45
2
A ×
5 3 = 28
34
29
E ( a) = 0,15×28 + 0,50×34 + 0,35×29 = 31,35
3
27 29 33
E ( a) = 0,15×27 + 0,50×29 + 0,35×33 = 30,10
4
31 30 29
E ( a) = 0,15×31 + 0,50×30 + 0,35×29 = 29,80
5
E ( a)= max{30,20; 29,45; 31,35; 30,10; 29,80} = 31,35
d
k
3
Podejmowanie decyzji w warunkach ryzyka (4)
Kryterium minimalnego oczekiwanego „Ŝalu” : 1. Dla kaŜdej decyzji d wyznacz oczekiwaną wartość „Ŝalu” E ( r) uŜywając i
i
określonych prawdopodobieństw stanu natury
2. WskaŜ decyzję d , dla której oczekiwana wartość „Ŝalu” E ( r) jest k
i
najmniejsza
E ( r)
i
= ∑ nj= {
P s }
1
r
j
ij
P{s }=0,15 P{s }=0,50 P{s }=0,35
E ( r)
1
2
3
k
= mi {
n E ( r
i
}
)
i
7 6 0
E ( r) = 0,15×7 + 0,50×6 + 0,35×0 = 4,05
1
0 4 8
E ( r) = 0,15×0 + 0,50×4 + 0,35×8 = 4,80
2
A ×
5 3 = 3
0
7
E ( r) = 0,15×3 + 0,50×0 + 0,35×7 = 2,90
3
4 5 3
E ( r) = 0,15×4 + 0,50×5 + 0,35×3 = 4,15
4
0 4 7
E ( r) = 0,15×0 + 0,50×4 + 0,35×7 = 4,45
5
E ( r)= min{4,05; 4,80; 2,90; 4,15; 4,45} = 2,90
d
k
3
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)?
a
max a
j =
{ ij}
j
P{s }=0,15 P{s }=0,50 P{s }=0,35
1
2
3
OKPI = ∑ n P s
{
a
}
j =1
j
j
24 28 36
s : a = max{24; 31; 28; 27; 31} = 31
1
1
31 30 28
s : a = max{28; 30; 34; 29; 30} = 34
2
2
A ×
s : a = max{36; 28; 29; 33; 29} = 36
5 3 = 28
34
29
3
3
27 29 33
31 30 29
OKPI = P{ s }× a + P{ s }× a + P{ s }× a =
1
1
2
2
3
3
= 0,15×31 + 0,50×34 + 0,35×36 = 34,25
7
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 ( r)
k
Podejmowanie decyzji z wykorzystaniem dodatkowej informacji (1) ZałóŜmy, Ŝe dla na zaistnienie stanu natury s ma istotny wpływ K czynników j
(wskaźników): I , I , I ,…, I . Celem analizy jest określenie prawdopodobieństw 1 2 3
K
warunkowych P{ s | I }, tzn. prawdopodobieństw zaistnienia stanu natury s pod j k
j
warunkiem, Ŝe wystąpił czynnik I ( k=1,2,…, K).
k
P{ s | I } – prawdopodobieństwa a posteriori – zrewidowana forma j k
prawdopodobieństw a priori P{ s }
j
Najczęściej w wyniku dodatkowych badań (eksperymentów) szacuje się prawdopodobieństwa warunkowe P{ I | s }
j
k
{
P I | s } {
P s }
{
P s | I }
k
j
j
=
j
k
{
P I }
k
gdzie
{
P I }
n
= ∑
{
P I ∩ s }
n
∑
{
P I | s } {
P s }
k
j 1
=
=
k
j
j 1
=
k
j
j
Podejmowanie decyzji z wykorzystaniem dodatkowej informacji (2)
stan natury
Czynniki
susza
normalne
deszcze
s
s
s
1
2
3
I
10%
30%
50%
1
I
40%
50%
25%
2
I
50%
20%
25%
3
stan natury
Czynniki
susza
normalne
deszcze
s
s
s
1
2
3
I
0,1
0,3
0,5
1
I
0,4
0,5
0,25
2
I
0,5
0,2
0,25
3
8
Podejmowanie decyzji z wykorzystaniem dodatkowej informacji (3)
I :
Określenie prawdopodobieństw warunkowych P{ s | I }:
1
j 1
P{ s }
P{ I | s }
P{ I
j
1
j
∩ s }
P{ s | I }
1
j
j 1
s
0,15
0,10
0,15
1
×0,10=0,0150
0,0150/0,3400=0,0441
s
0,50
0,30
0,50
2
×0,30=0,1500
0,1500/0,3400=0,4412
s
0,35
0,50
0,35
3
×0,50=0,1750
0,1750/0,3400=0,5147
∑
1,00
×
P{ I } = 0,3400
1,0000
1
I :
Określenie prawdopodobieństw warunkowych P{ s | I }:
2
j 2
P{ s }
P{ I | s }
P{ I
j
2
j
∩ s }
P{ s | I }
2
j
j 2
s
0,15
0,40
0,15
1
×0,40=0,0600
0,0600/0,3975=0,1509
s
0,50
0,50
0,50
2
×0,50=0,2500
0,2500/0,3975=0,6289
s
0,35
0,25
0,35
3
×0,25=0,0875
0,0875/0,3975=0,2202
∑
1,00
×
P{ I } = 0,3975
1,0000
2
Podejmowanie decyzji z wykorzystaniem dodatkowej informacji (4)
I :
Określenie prawdopodobieństw warunkowych P{ s | I }:
3
j 3
P{ s }
P{ I | s }
P{ I
j
3
j
∩ s }
P{ s | I }
3
j
j 3
s
0,15
0,50
0,15
1
×0,50=0,0750
0,0750/0,2625=0,2857
s
0,50
0,20
0,50
2
×0,20=0,1000
0,1000/0,2625=0,3810
s
0,35
0,25
0,35
3
×0,25=0,0875
0,0875/0,2625=0,3333
∑
1,00
×
P{ I } = 0,2625
1,0000
3
Podejmowanie decyzji z wykorzystaniem dodatkowej informacji (5) Wyznaczenie optymalnej decyzji przy wykorzystaniu kryterium maksymalnego oczekiwanego zysku (MOW):
1.
Prawdopodobieństwa a priori P{ s } zostają zastąpione j
prawdopodobieństwami a posteriori
2.
Decyzje optymalne podejmowane są dla oddzielnie uwzględnianych czynników Ik
E ( a)
n
P s
I a
i| I
= ∑ j= { | }
1
j
k
ij
k
*
E ( a) max E
a
i| I
=
i I
k
{ (
| k
}
)
i
9
Podejmowanie decyzji z wykorzystaniem dodatkowej informacji (6) Optymalna decyzja jeŜeli wystąpi czynnik I – kryterium MOW:
1
E ( a)
n
P s
I a
i| I
= ∑ j= { | }
1
j
1
ij
1
*
E ( a) max E
a
i| I
=
i| I
1
{ (1 }
)
i
P{ s | I }=0,0441 P{ s | I }=0,4412 P{s | I }=0,5147
1 1
2 1
3 1
24 28 36
E
( a) = 0,0441×24 + 0,4412×28 + 0,5147×36 = 31,9412
1|I1
31 30 28
E
( a) = 0,0441×31 + 0,4412×30 + 0,5147×28 = 29,0147
2|I1
A ×
5 3 = 28
34
29
E
( a) = 0,0441×28 + 0,4412×34 + 0,5147×29 = 31,1619
3|I1
27 29 33
E
( a) = 0,0441×27 + 0,4412×29 + 0,5147×33 = 30,9706
4|I1
31 30 29
E
( a) = 0,0441×31 + 0,4412×30 + 0,5147×29 = 29,5254
5|I1
E*
( a)= max{31,9412; 29,0147; 31,1619; 30,9706; 29,5254} = 31,9412
d
k|I1
1
Podejmowanie decyzji z wykorzystaniem dodatkowej informacji (7) Optymalna decyzja jeŜeli wystąpi czynnik I – kryterium MOW:
2
E ( a)
n
P s
I a
i| I
= ∑ j= { | }
1
j
1
ij
2
*
E ( a) max E
a
i| I
=
i| I
2
{ (2 }
)
i
P{ s | I }=0,1509 P{ s | I }=0,6289 P{s | I }=0,2202
1 2
2 2
3 2
24 28 36
E
( a) = 0,1509×24 + 0,6289×28 + 0,2202×36 = 29,1580
1|I2
31 30 28
E
( a) = 0,1509×31 + 0,6289×30 + 0,2202×28 = 29,7105
2|I2
A ×
5 3 = 28
34
29
E
( a) = 0,1509×28 + 0,6289×34 + 0,2202×29 = 31,9936
3|I2
27 29 33
E
( a) = 0,1509×27 + 0,6289×29 + 0,2202×33 = 29,5790
4|I2
31 30 29
E
( a) = 0,1509×31 + 0,6289×30 + 0,2202×29 = 29,9307
5|I2
E*
( a)= max{29,1580; 29,7105; 31,9936; 29,5790; 29,9307} = 31,9936
d
k|I2
3
Podejmowanie decyzji z wykorzystaniem dodatkowej informacji (8) Optymalna decyzja jeŜeli wystąpi czynnik I – kryterium MOW:
3
E ( a)
n
P s
I a
i| I
= ∑ j= { | }
1
j
1
ij
3
*
E ( a) max E
a
i| I
=
i| I
3
{ (3 }
)
i
P{ s | I }=0,2857 P{ s | I }=0,3810 P{s | I }=0,3333
1 3
2 3
3 3
24 28 36
E
( a) = 0,2857×24 + 0,3810×28 + 0,3333×36 = 29,5236
1|I3
31 30 28
E
( a) = 0,2857×31 + 0,3810×30 + 0,3333×28 = 29,6191
2|I3
A ×
5 3 = 28
34
29
E
( a) = 0,2857×28 + 0,3810×34 + 0,3333×29 = 30,6193
3|I3
27 29 33
E
( a) = 0,2857×27 + 0,3810×29 + 0,3333×33 = 29,7618
4|I3
31 30 29
E
( a) = 0,2857×31 + 0,3810×30 + 0,3333×29 = 29,9524
5|I3
E*
( a)= max{29,5236; 29,6191; 30,6193; 29,7618; 29,9524} = 30,6193
d
k|I3
3
10
Podejmowanie decyzji z wykorzystaniem dodatkowej informacji (9) Oczekiwana korzyść dodatkowej informacji
OKDI = ∑ K
*
k = P I
{
E
}
( a
1
)
k
i| I k
P{I } = 0,3400 E*
( a) = 31,9412
1
k|I1
P{I } = 0,3975 E*
( a) = 31,9936
2
k|I2
P{I } = 0,2625 E*
( a) = 30,6193
3
k|I3
OKDI = P{ I }× E*
( a) + P{ I }× E*
( a) + P{ I }× E*
( a) =
1
k|I1
2
k|I2
3
k|I3
= 0,3400×31,9412 + 0,3975×31,9936 + 0,2625×30,6193 = 31,6150
Podejmowanie decyzji z wykorzystaniem dodatkowej informacji (10) Oczekiwana wartość dodatkowej informacji
Jest to róŜnica pomiędzy oczekiwaną korzyścią przy uwzględnieniu dodatkowej informacji ( OKDI) a oczekiwaną korzyścią bez uwzględnienia dodatkowej informacji, tzn. kwotą uzyskaną z zastosowania kryterium maksymalnej oczekiwanej wartości ( MOW):
OWDI = OKDI – MOW = 31,6150 – 31,35 = 0,265
Podejmowanie decyzji z wykorzystaniem dodatkowej informacji (11) Efektywność dodatkowej informacji
Jest to iloraz oczekiwanej wartości dodatkowej informacji ( OWDI) do ceny granicznej doskonałej informacji ( CGPI):
= OWDI
EDI
×100%
CGPI
,
0 265
EDI =
×10 %
0
= 1
,
9
%
4
9
,
2 0
11