Drzewa decyzyjne i macierz wypłat

SPIS TREŚCI
1.Istota pojęcia str. 3
1.1. Drzewo decyzyjne str.3
1.2. Macierz wypłat str.3
1.3. Etapy analizy str. 4
2.Budowa drzewa na przykładzie str.4
3. Przykład drzewa decyzyjnego str.7
4.Przykład macierzy wypłat str.9
5. Wnioski str.13
5.1. Zalety drzewa decyzyjnego str.13
6. Bibliografia str.14


1.Istota pojęcia

1.1.Drzewo decyzyjne
Poszerzają macierz wypłat o kolejność decyzji,
Pozwalają rozważyć ciąg alternatywnych wariantów decyzyjnych.
Nadają się one jednak najlepiej wtedy, gdy trzeba kolejno podjąć szereg różnych decyzji i kiedy procesy są skomplikowane.
Drzewo decyzyjne (diagramy, dendryty) to metoda prezentacji czynników umożliwiających rozwiązanie problemu oraz podjęcie właściwej decyzji.
Podejmowanie decyzji to wybranie alternatyw:
-albo zrobimy X lub nie zrobimy Y;
-albo zrobimy X lub zrobimy Y;
Analiza procesu decyzyjnego za pomocą drzewa nosi nazwę ekstensywnej formy analizy.

1.2.Macierz wypłat
Określa prawdopodobną wartość różnych wariantów decyzyjnych, przy manipulowaniu zmiennymi decyzyjnymi,
Kryterium wyboru wariantu decyzyjnego jest jego najwyższa wartość oczekiwana.
Aby zastosować macierz wypłat musimy mieć kilka wariantów decyzji, przy czym zajść może kilka różnych zdarzeń, a konsekwencje zależą od tego, który wariant zostanie wybrany, które zdarzenie lub zespół zdarzeń faktycznie zajdzie. Ważną kategoria w tym rozumowaniu jest prawdopodobieństwo ? wyrażona w procentach szansa zajścia lub nie zajścia konkretnego zdarzenia.
Większość wartości prawdopodobieństwa wykorzystywanych przez menedżerów opiera się na subiektywnej ocenie, intuicji i danych z przeszłości.
Inne możliwości zastosowania macierzy wypłat dotyczą określenia optymalnych rozmiarów zamówienia, decydowania o naprawie lub wymianie uszkodzonego sprzętu czy też wyboru pomiędzy kilkoma n owymi produktami i wprowadzenia produktu na rynek. Oczywiście menedżerowie muszą trafnie szacować odpowiednie prawdopodobieństwa, gdyż jest to warunek skutecznego użycia macierzy wypłat.

1.3.Etapy analizy
Na ogół określa się cztery etapy analizy zadania podejmowania decyzji w warunkach nieokreśloności; ?
1)Przedstawienie struktury zadania w postaci drzewa decyzyjnego,
2)Ocena użyteczności każdego wyniku na końcu gałęzi tego drzewa,
3)Ocena prawdopodobieństwa na wszystkich losowych rozgałęzieniach,
4)Określenie optymalnej strategii.

2.Budowa drzewa na przykładzie
Każde drzewo decyzyjne składa się z dwóch rodzajów węzłów. Jedne z nich będziemy nazywa węzłami decyzyjnymi i będziemy je oznaczać prostokątami, a drugie ? węzłami losowymi oznaczanymi kółkami. Jeśli podmiot podejmujący decyzję znajduje się w więźle oznaczonym prostokątem, to może wybrać drogę, jaką zechce. Jeśli zaś podmiot znajduje się w węźle oznaczonym kółkiem, a więc w węźle losowym, dalsza droga nie będzie zależna od niego, lecz jest wyznaczona przez czynniki zewnętrzne. Drzewo budujemy zaczynając od węzła przedstawionego za pomocą prostokąta, z którego wychodzą trzy linie, reprezentujące trzy decyzje.

Przykład 2.1.?? Dla lustracji moglibyśmy sobie wyobrazić, że podmiotem podejmujący decyzję jest rolnik, który na danym areale może uprawiać jedną z czterech roślin. Jego wybór równoznaczny jest z podjęciem jednej decyzji
D1, D2, D3, D4, jest całkowicie zależny od niego. Niech Z1, Z2, Z3 oznaczają odpowiednio trzy różne rodzaje warunków atmosferycznych w okresie wegetacji roślin. Ostateczne korzyści będą zależeć od podjętej decyzji przez rolnika oraz od warunków atmosferycznych. Zwróćmy uwagę, że podejmując decyzję, rolnik nie zna przyszłych warunków atmosferycznych, stąd też po podjęciu jakiejkolwiek decyzji trafia do węzła losowego (oznaczonego kółkiem) i dalsza droga przesądzająca o jego korzyściach nie zależy już od niego.

Prawdopodobieństwa
p1=0,1 p2=0,7 p3=0,2
Z1
D
Z1 Z2 Z3
D1
D2
D3
D4
10 4 5
8 6 6
12 5 2
3 7 10
Tabela 2.1. Funkcja korzyści dla przykładu 2.1

Na wykres drzewa decyzyjnego przenosimy wszystkie dane z tabl..2.1 w następujący sposób:

Rysunek 2.1 Drzewo decyzyjne dla przykładu 2.1

Po naniesieniu wszystkich danych przystępujemy do wyznaczania optymalnej decyzji. Ogólną zasadą jest zawsze analiza drzewa decyzyjnego od strony prawej do lewej, od korony do pnia drzewa.
W tym przypadku najdalej na prawo są położone węzły losowe, które dla ułatwienia ponumerowaliśmy. Od tych właśnie węzłów zaczynamy analizę. I tak dla 1 korzyść wynosi ;
10 ? 0,1 4 ? 0,7 5 ? 0,2 = 4,8
Analogiczny sposób liczymy pozostałe węzły.
Następnie cofamy się do węzła leżącego dalej na lewo. Jest to węzeł decyzyjny, a więc od podmiotu zależy decyzja, którą z czterech dróg wybierze. Kierując się zasadą maksymalizacji spodziewanych korzyści, za optymalną musimy uzna drogę odpowiadająca decyzji D4, gdyż gwarantuje nam ona największą spodziewaną korzyść. Dla oznaczenia tego, drogi odpowiadające pozostałym decyzjom blokujemy, gdyż nie są to drogi korzystne. Jaką konkretną korzyść w tym przypadku odniesiemy, tego już przewidzieć się nie da, gdyż dalsza doga nie zależy już od podmiotu podejmującego decyzję. Może to być korzyść 3 albo 7, albo 10.

3.Przykład drzewa decyzyjnego
Przykład 3.1???. Załóżmy, że organizacja powinna wybrać jedną z dwóch maszyn wykonujących tę samą operację. Obie maszyny mają jednakową wydajność i wytwarzają wyroby o tej samej jakości. Wybór maszyny określa się za pomocą średniorocznych kosztów eksploatacji, zależnych od czasu zamiany maszyny.

Rysunek 3.1. Drzewo decyzyjne problemu zamiany maszyny
Ile kosztuje organizację określenie informacji o roku zamiany maszyny? W celu odpowiedzi na to pytanie są konstruowane dwa drzewa decyzyjne, przy czym w jednym są porównywane średnioroczne kosztu eksploatacji maszyn (rys. 3.1),a w drugim jest podejmowana decyzja losowa (rys. 3.2).
Po rozważeniu drzewa decyzyjnego z rys. 3.1, można zauważyć, że po 6 roku koszty eksploatacji obu maszyn zaczynają wzrastać, przy czym koszty eksploatacyjne maszyny B są mniejsze w 6 roku, tj. zamiana maszyny B po 6 roku eksploatacji będzie decyzją optymalną.
Aby określić koszty tej informacji, za pomocą drzewa (rys 3.1) sprawdza się, do czego prowadzi decyzja losowa. Drzewo decyzyjne z rys. 3.2 przedstawia, że przy losowej zamianie średnioroczne koszty eksploatacji maszyny są równe 2571,17 jp;
- średnioroczne koszty eksploatacji maszyny A:
(0,14? 3300) ( 0,14 ?2750) (0,14?2517) (0,14?2333) (0,14?2164) (0,14?2137) (0,14?2174)=2432,5 jp.
-średnioroczne koszty eksploatacji maszyny B:
(0,14? 5250) ( 0,14 ?3200) (0,14?2610) (0,14?2298) (0,14?2054) (0,14?1970) (0,14?1974)=2709,84 jp.
Tak, więc, średnioroczne koszty eksploatacji maszyny wynoszą
(0,5?12432,5) (0,5?2709,84)=2571,17 jp.

Rysunek 2.2. Drzewo decyzyjne losowej decyzji zamiany maszyny
Skorzystanie z informacji przedstawionej na rys 3.1 umożliwiłoby zmniejszenie średniorocznych kosztów eksploatacji maszyny z 2571,17 do 1970 jp. Różnica między tymi dwiema wartościami pomnożona przez liczbę lat eksploatacji maszyny daje koszty informacji dla organizacji:
(2571,17- 1970)?6=653,64?6=3607,02 jp.
Te średnie koszty wahają się od 0 do 19680 jp. Będą one równe 0, kiedy losowa decyzja będzie pokrywała się z optymalną, a równe 19 680 jp., Jeżeli ilustruje możliwość określenia kosztów informacji za pomocą pomiaru skutków nie przeprowadzenia jej zbierania. To podejście tylko po zebraniu informacji.

To drzewo przekonuje, że w sytuacjach nieco bardziej skomplikowanych jest narzędziem, które bardzo ułatwia i uplastycznia analizę procesów decyzyjnych.

4. Przykład macierzy wypłat
Przykład 4.1.? Dwa koncerny samochodowe konkurują ze sobą na rynku pewnego kraju. Koncern A rozważa uruchomienie w lokalnej fabryce jednego z czterech modeli samochodów. Koncern B natomiast jednego z pięciu modeli samochodów.
W macierzy wypłat przedstawiono zyski koncernu A (straty koncernu B) przy produkcji samochodów, zależnie od podjętych decyzji. Należy podjąć decyzję o rodzaju produkcji, będąc dyrektorem koncernu A.
Tabela 4. Zestawienie wiadomości dla przykładu 4.1.

Poszukiwanie strategii zdominowanych
a ij ? element macierzy wypłat

i = 1?m m- ilość strategii koncernu A (ilość wierszy)
j = 1?n n - ilość strategii koncernu B (ilość kolumn)

Porównanie parami strategie koncernu A.
Jeżeli dla danej pary strategii jest spełniony warunek:

a zj ? a dj j=1?n

To strategia z jest zdominowana przez strategie d.

Strategie 2 i 4:
2
70
80
100
80
110
4
70
70
90
20
60
Tabela 4. 1 Strategia zdominowania dla przykładu 4.1.

Warunek dominacji jest spełniony:
strategia 4. ? zdominowana strategia 2. ? dominująca

Z macierzy wypłat usunięto strategię 4. Koncernu A.

Koncern B
strategie
1
2
3
4
5
Koncern A
1
200
70
10
30
120
2
70
80
100
80
110
3
80
150
0
80
30
Tabela 4. 2. Macierz wypłat z usuniętą strategią 4. dla przykładu 4.1.

Poszukiwanie strategii zdominowanych dla koncernu B.

Musi być spełniony warunek:
aiz ? aid i= 1?m

Strategia d jest zdominowana przez strategię z.

2
4
70
30
80
80
150
80
Tabela 4. 3. Strategie 2 i 4 dla przykładu 4.1.
Strategia 2. ? zdominowana
Strategia 4. ? dominująca

Z macierzy usunięto strategię 2. koncernu B.

Te same działania dla strategii 3 i 5:

3
5
10
120
100
110
0
30
Tabela 4. 4. Macierz z zdominowaną strategią 3 i 5 dla przykładu 4.1.

Strategia 5. ? zdominowana
Strategia 3.- dominująca

Z macierzy wypłat usunięto strategię 5. koncernu B.

Porównane zostały wszystkie możliwe pary strategii koncernu B.

Poszukiwanie punktu siodłowego
- dla każdego wiersza znajdujemy wartość minimalną
- dla każdej kolumny znajdujemy wartość maksymalną

Koncern B

Strategie
1
3
4
Min aij
j
Koncern A
1
200
10
30
10
2
70
100
80
70
3
80
0
80
0
Max aij
i
200
100
80

Tabela 4. 5. Macierz z wyznaczonymi minimalnymi i maksymalnymi wartościami dla przykładu 4.1.


- dla wyznaczonych minimalnych wartości z wierszy
określamy wartość maksymalną:
Max(min aij) max(10,70,0) =70
i j
- dla wyznaczonych maksymalnych wartości z kolumn
określamy wartość minimalną:
Min(max aij) min(200,100,80) = 80
j i
Punkt siodłowy istniej, gdy zostaje spełniony warunek
max(min aij ) min(max aij)

W tym przykładzie powyższy warunek nie jest spełniony. Stwierdzono brak rozwiązania w zbiorze strategii czystych i szukano rozwiązań w zbiorze strategii mieszanych.

5.Wnioski
Drzewa decyzyjne są często dogodniejsze niż podejście polegające na ocenie ryzyka, związanego z każdą regułą decyzyjną. Ilość niezbędnych działań matematycznych jest przy nich mniejsza i łatwo je sformułować.?
5.1.Zalety drzewa decyzyjnego
Drzewa decyzyjne to jedna z najczęściej wykorzystywanych technik analizy danych. Przyczyny ich popularności są następujące:
Mogą być budowane przy wykorzystaniu algorytmicznych technik ?dziel i rządź? . Metoda ta jest znana ze swej szybkości. Wykorzystują ją niemal wszystkie algorytmy drzew decyzyjnych.
Doskonale bronią się przed szumem w danych.
Mogą by wykorzystywane do selekcji i ekstrakcji cech.
Modele drzew są względnie łatwe do zrozumienia przez ludzi.
Są łatwe do wizualizacji.



Bibliografia
1.Mitchell G.H. ?Badania operacyjne. Metody i przykłady?, z ang. Tłumaczył dr Jacek Kochanowski,
Wydawnictwa Naukowo-Techniczne, Warszawa 1977 r.
2.Sadowski W. ?Decyzje i prognozy?, Państwowe Wydawnictwo Ekonomiczne, Warszawa 1981r.
3.Witkowski T. ?Decyzje w zarządzaniu przedsiębiorstwem?,
Wydawnictwa Naukowo-Techniczne, Warszawa 2000 r.