1 Decyzja: pojęcie popularne w naszym języku zdecydowałem się – będę studiował automatykę zarząd przyjął plan strategicznego rozwoju firmy Decyzja: pojęcie kluczowe w wielu naukach teoria decyzji optymalizacja decyzji decyzje wielokryterialne decyzje w warunkach ryzyka i niepewności
2 Oblicza decyzji? * decyzja sędziego na boisku – był faul? rzut wolny? żółta kartka? czerwona kartka? * decyzja Trybunału Konstytucyjnego – akt prawny zgodny z Konstytucją? częściowo zgodny? * decyzja zakochanego? – wziąć ślub? * decyzja szefa firmy – dobry projekt marketingowy? sfinansować w całości? dobry projekt nowego wyrobu? dobry program produkcji? * decyzja rady miasta – dobry projekt budżetu? o ile zmniejszyć wydatki? co usunąć?
3 Oblicza decyzji? c.d. * decyzja dowódcy na polu walki – atakować? wycofać się? bronić się? którędy atakować, aby zaskoczyć wroga? * decyzja kierowcy w samochodzie – którędy jechać, aby najszybciej dotrzeć do celu? * decyzja robota domowego? sprzątać? włączyć ogrzewanie? * decyzja zespołu robotów – jak poruszać się w terenie, aby razem najszybciej dotrzeć do celu? * decyzja regulatora – ile gazu do pieca, aby osiągnąć pożądaną temperaturę?
4 Czy zawsze będziemy mówić o wspomaganiu decyzji - kto podejmuje decyzje?Decydent jednostka, która podejmuje decyzję Decydentem może być: pojedyncza osoba – człowiek grupa osób urządzenie grupa urządzeń
5 Fakty z przytoczonych przykładów: decydent chce coś osiągnąć – istnieje jakiś cel lub cele jego, które chciałby osiągnąć lub które mają być osiągnięte decydent jest człowiekiem lub zespołem ludzi jego działanie jest skierowane na niego samego lub na obiekty z otoczenia
6 Decyzja jest wyborem sterowaniaOdrzucenie urządzeń i grupy urządzeń jako decydentów - odwołanie do dwóch pojęć – sterowanie, automatyka Sterowanie to celowe oddziaływanie czegoś/kogoś na coś/kogoś Decyzja jest wyborem sterowania Automatyka jest dziedziną wiedzy, która zajmuje się możliwościami ograniczania udziału lub eliminowania udziału człowieka w sterowaniu różnorodnymi obiektami bądź środowiskiem
7 Wspomaganie decyzji jest dziedziną wiedzy, która zajmuje się możliwościami pomagania człowiekowi w sterowaniu różnorodnymi obiektami bądź środowiskiem, w sterowaniu w którym jest on istotnie zaangażowany, a pomaganie skupione jest na procesie podejmowania decyzji Można powiedzieć:
8 Czy zawsze będziemy mówić o wspomaganiu decyzji – charakter decyzji?Czy powinienem kupić nowy komputer? Czy powinienem tej jesieni podróżować samolotami? Jaki jest najbardziej odpowiedni profil produkcji fabryki? Który rynek powinien być najbardziej dochodowy? Jaką terapię zastosować? Jak przeciwdziałać skutkom ataku terrorystycznego? Jak monitorować środowisko przeciw skażeniom?
9 Rozróżnienie: decyzje indywidualne (osobnicze) decyzje instytucjonalne
10 proces podejmowania decyzjiKiedy pojawia się decyzja? Decyzja pojawia się jako wynik procesu nazywanego procesem decyzyjnym proces decyzyjny proces podejmowania decyzji podejmowanie decyzji Terminy tożsame:
11 Po podjęciu decyzji mówimy – rozwiązaliśmy problem decyzyjnyPodejmowanie decyzji to każdy ciąg operacji o charakterze mentalnym i obliczeniowym tworzących proces przetwarzania, w który włączone są informacja, wiedza, preferencje, a którego celem jest podjęcie decyzji Czym jest proces podejmowania decyzji instytucjonalnej? Po podjęciu decyzji mówimy – rozwiązaliśmy problem decyzyjny
12 Czy tylko decydent uczestniczy w procesie decyzyjnym?- w procesie decyzyjnym występują różni jego uczestnicy; na dwóch zwracamy uwagę – decydent i analityk - decydent - D (Decision Maker – DM) jest tym uczestnikiem procesu podejmowania decyzji – PPD (Decision Making Prosess – DMP), do którego adresowane jest wspomaganie decyzji (osoba, ciało kolegialne, zbiorowość); krótko, ten, któremu pomagamy - analityk A jest tym uczestnikiem procesu podejmowania decyzji, który zajmuje się wspomaganiem decyzji; krótko, ten, który pomaga
13 W procesie decyzyjnym można wyróżnić umownie kilka kolejnych faz1. identyfikacja sytuacji decyzyjnej 2. sformułowanie problemu decyzyjnego 3. zbudowanie modelu decyzyjnego 4. wyznaczenie różnych podzbiorów zbioru opcji (dopuszczalnych, zadowalających, optymalnych, .....) 5. podjęcie/wybór decyzji
14 Jak można określić poszczególne z tych faz?Sytuacja decyzyjna określana jest przez zestaw wszystkich czynników, które mają wpływ na decyzję, jakiej dokona decydent Sformułowanie problemu decyzyjnego powinno definiować: 1. decydenta, 2. opcje decyzyjne, 3. czynniki ograniczające przestrzeń decyzyjną, 4. czynniki kształtujące ocenę opcji decyzyjnych
15 Dwie poprzednie fazy procesu decyzyjnego (podejmowania decyzji) mają na ogół charakter opisowy. Charakteru takiego nie ma kolejna faza tego procesu – budowanie modelu decyzyjnego Model decyzyjny to wyrażona najczęściej w języku matematyki reprezentacja rozważanego problemu decyzyjnego. Z pomocą modelu powinno być możliwe określenie elementów zbioru dopuszczalnych opcji decyzyjnych a także wskazanie opcji optymalnych
16 Ze względu na posiadane informacje formułowane problemy decyzyjne dzieli się na trzy grupydecyzja podejmowana w warunkach pewności – z każdą decyzją związane są określone, znane skutki decyzja podejmowana w warunkach ryzyka – każda decyzja może pociągać za sobą więcej niż jeden skutek, z powodu działania natury (otoczenia, zakłóceń), znany jest zbiór skutków i prawdopodobieństwa ich wystąpienia decyzja podejmowana w warunkach niepewności – nie znamy prawdopodobieństw wystąpienia skutków danej decyzji
17 Wyznaczenie różnych podzbiorów zbioru opcji opiera się na stosowaniu różnorodnych metod metod optymalizacji jednokryterialnych metod optymalizacji wielokryterialnych metod klasyfikacji metod porządkowania
18 W przypadku decyzji instytucjonalnych pojawiają się:Systemy wspomagania decyzji - SWD (Decision Support System - DSS) są klasą skomputeryzowanych systemów informacyjnych, które wspomagają działalność podejmowania decyzji Dwa obszary: podejmowanie decyzji, systemy informacyjne Płaszczyzna spotkania: technika komputerowa
19 Wielokryterialne problemy decyzyjne
20 Problemy podejmowania decyzji wielokryterialnych mogą być ogólnie zakwalifikowane do dwóch kategorii: problemy decyzji wieloatrybutowych (Multiple Attribute Decision Problem - MADP) problemy decyzji wielocelowych (Multiple Objective Decision Problem - MODP)
21 Problemy decyzji wieloatrybutowychCechą wyróżniającą problemy decyzji wieloatrybutowych MADP jest to, że istnieje ograniczona (i przeliczalnie mała) liczba ustalonych wcześniej opcji decyzyjnych. Każda opcja posiada określony, związany z nią, poziom osiągnięcia uznanych za istotne przez decydenta atrybutów/cech (które niekoniecznie muszą być kwantyfikowalne) i na których podstawie podejmowana jest decyzja
22 Atrybut Myśliwiec Zagadnienie wieloatrybutowe – przykład(Problem wyboru samolotów myśliwskich) Pewne państwo zdecydowało się zakupić flotę odrzutowych myśliwców w USA. Urzędnicy Pentagonu przedstawili informację o właściwościach czterech modeli, które mogą być sprzedane do tego kraju. Zespół analityków Sił Powietrznych zainteresowanego kraju zgodził się, że należy rozważać sześć charakterystyk (atrybutów). Są to: maksymalna prędkość (A1), zasięg latania (A2), maksymalny ładunek użyteczny (A3), koszt zakupu (A4), niezawodność (A5), manewrowalność (A6). Wartości tych atrybutów zostały przedstawione w tablicy Myśliwiec Atrybut A1 A2 A3 A4 A5 A6 M1 2.0 1500 20000 5.5 średnia b. wysoka M2 2.5 2700 18000 6.5 niska M3 1.8 2000 21000 4.5 wysoka M4 2.2 1800 5.0 Który z samolotów powinien wybrać zainteresowany kraj, jeżeli chciałby mieć samolot jak najszybszy, o jak największym zasięgu, jak największej ładowności, jak najtańszy, jak najbardziej niezawodny i jak najwyższych zdolnościach manewrowych?
23 Problemy decyzji wielocelowychW przypadku problemów decyzji wielocelowych MODP nie określana jest wcześniej liczba opcji z wartościami właściwych dla problemu atrybutów. Zamiast tego problemy te posiadają: (1) zbiór kwantyfikowalnych celów na podstawie których podejmowana jest decyzja o wyborze określonej opcji decyzyjnej; (2) zbiór dobrze określonych ograniczeń na wartości różnorakich czynników kształtujących możliwości wyboru możliwych opcji (zmiennych decyzyjnych)
24 Zadanie, które posłuży do ilustrowania różnych podejść optymalizacji wielocelowejFirma produkuje dwa produkty. Zarząd wyraził życzenie, aby znaleźć program produkcji, który: maksymalizuje całkowity zysk, maksymalizuje spodziewaną ,,przechwytywaną” część rynku (udziały na rynku), spełnia ograniczenia procesu produkcji (tzn. dostępności surowców), nie doprowadza do nasycenia rynku (tzn. mamy możliwość sprzedania całej wytworzonej produkcji). Ponadto wiadomo: jedna jednostka produktu 1. zapewnia dochód w wysokości 3 jednostek pieniężnych (jp.), a jedna jednostka produktu jp.; oszacowano, że każda sprzedana jednostka produktu 1. powiększy rynek o dwie jednostki udziału na rynku, a jedna jednostka produktu 2. - o 3 jednostki; wytworzenie jednostki produktu 1. wymaga zużycia 2 jednostek surowca, a jednostki produktu jednostki; tylko 50 jednostek surowca jest dostępnych w rozważanym okresie czasu; badania rynku wskazują, że nie więcej niż 20 jednostek produktu pierwszego i nie więcej niż 30 jednostek produktu drugiego.
25 Analityczne sformułowanie zagadnienia:Oznaczmy: - liczba wyprodukowanych jednostek produktu 1 - liczba wyprodukowanych jednostek produktu 2 Znaleźć wartości i takie, które: (czyli całkowity zysk w rozważanym okresie czasu) maksymalizują spełniając: (czyli przechwycone w rozważanym okresie czasu udziały w rynku) (ograniczenie dostępności surowca) (ograniczenie nasycenia rynku produktu 1.) (ograniczenie nasycenia rynku produktu 2.) (warunki nieujemności)
26 Graficzne rozwiązanie zagadnieniaPunkty wierzchołkowe:
27 Ogólne sformułowanie wielocelowego zagadnienia programowania liniowego; k - funkcji celu, m - ograniczeń gdzie
28 Wielość funkcji celu Nie będą nas interesowały przypadki, kiedy możliwe jest znalezienie całkowicie optymalnego rozwiązania Np. jeżeli dla przykładowego zagadnienia
29 Wielość funkcji celu Rozwiązanie całkowicie optymalne (przypadek minimalizacji) Mówi się, że jest rozwiązaniem całkowicie optymalnym, wtedy i tylko wtedy, jeżeli istnieje takie, że
30 Optymalizacja z jedną funkcją celu (jednocelowa) Funkcja celu z odwzorowuje punkty przestrzeni decyzyjnej w Rn w wartość skalarną w R W R istnieje naturalny kanoniczny porządek Zdefiniowanie optymalnego rozwiązania np. minimalizacji jest proste Konsekwencja:
31 Optymalizacja z wieloma funkcjami celu (wielocelowa) Funkcja celu z=[z1, z2, , zK] odwzorowuje punkty przestrzeni decyzyjnej w Rn w wartość wektorową w RK, K>1 Problem: W RK nie istnieje naturalny kanoniczny porządek Istnieją różne pojęcia optymalności, które zależą od wybranego w RK porządku Konsekwencja:
32 Weźmy przykład – dwucelowe zagadnienie programowania liniowegoWielość funkcji celu Weźmy przykład – dwucelowe zagadnienie programowania liniowego
33 Przedstawienie w przestrzeni opcji decyzyjnych (w przestrzeni decyzji)
34 Transformacja
35 Przedstawienie w przestrzeni kryteriów (w przestrzeni celów)
36 Optymalizacja z wieloma funkcjami celu (wielocelowa)Wybór porządku zależy od problemu decyzyjnego Jeżeli można podać ranking funkcji celu – np. z1 jest ważniejsza niż z2 , wybrany zostanie porządek leksykograficzny
37 Optymalizacja z wieloma funkcjami celu (wielocelowa) Jeżeli interesują nas rozwiązania dla których poprawienie wartości jednej funkcji np. z1 nie może się odbyć bez pogorszenia co najmniej jednej z pozostałych, wybrany zostanie porządek Pareto
38 Optymalizacja z wieloma funkcjami celu (wielocelowa)Ilustracja nierówności Pareto Stożki nierówności Pareto
39 Rozwiązanie optymalne w sensie Pareto (rozwiązanie Pareto optymalne)Rozwiązanie jest nazywane Pareto optymalnym (zagadnienie minimalizacji), jeżeli nie istnieje Określenia: Jeżeli jest rozwiązaniem Pareto optymalnym, to o jest nazywany punktem efektywnym Jeżeli oraz i mówimy, że dominuje nad oraz, że dominuje nad
40 Graficzne wyznaczenie zbioru Pareto dla rozważanego przykładua) w przestrzeni decyzji
41 b) w przestrzeni celów
42 Wykorzystanie stożków Pareto (przypadek minimalizacji)Lepsze Gorsze Nieporównywalne Wykorzystanie stożków Pareto (przypadek minimalizacji)
43 Alternatywy postępowania – porządek ParetoI. Wykorzystanie klasycznych metod optymalizacji jednocelowej operujących na pojedynczych punktach przestrzeni decyzyjnej – poszukiwany jest jeden punkt zbioru Pareto – wyrażenie preferencji decydenta odbywa się przed optymalizacją II. Wykorzystanie metod optymalizacji operujących na populacjach punktów przestrzeni decyzyjnej (np. algorytmy genetyczne) – poszukiwanie zbioru punktów Pareto – wyrażenie preferencji decydenta odbywa się po optymalizacji
44 Wybrane metody poszukiwania rozwiązań wielocelowych zagadnień liniowych1. Sprowadzenie do jedno-celowego zagadnienia liniowego poprzez zamianę wszystkich funkcji celu poza jedną w ograniczenia
45 (czyli całkowity zysk w rozważanym okresie czasu)Przykład Przyjmiemy całkowity zysk jako pojedynczy cel i będziemy traktować powiększenie udziału na rynku jako ograniczenie. To ostatnie przekształcenie możemy zrealizować przez przyjęcie pewnego akceptowalnego lub pożądanego powiększenia udziału na rynku. Przykładowo przyjmijmy, że takim pożądanym powiększeniem udziału na rynku jest 100. Model naszego przykładowego problemu będzie miał wówczas postać Znaleźć wartości i taki, które: maksymalizują (czyli całkowity zysk w rozważanym okresie czasu) spełniając: (pożądane powiększenie udziału na rynku) (ograniczenie dostępności surowca) (ograniczenie nasycenia rynku produktu 1.) (ograniczenie nasycenia rynku produktu 2.) (warunki nieujemności)
46 Graficzne rozwiązaniePunkty wierzchołkowe Rozwiązanie optymalne
47 Zalety Możemy bezpośrednio zastosować istniejące algorytmy lub oprogramowanie PL do rozwiązania zaproponowanego modelu. Wady Jeżeli nie jesteśmy ostrożni (i/lub szczęśliwi), konwersja celu w (twarde) ograniczenie może prowadzić do modelu, który jest matematycznie niedopuszczalny (np. w naszym przykładzie, jeżeli użylibyśmy wartości 120 zamiast 100 dla PS ograniczenia powiększenia udziałów na rynku, nasz model byłby matematycznie niedopuszczalny)
48 Wady Przetworzony cel, lub cele, są traktowane jako twarde ograniczenia przez algorytmy PL. Zatem jeżeli nawet bylibyśmy skłonni pogodzić się z udziałem mniejszym niż 100 w rozważanym okresie, rozwiązanie takie nie zostanie wygenerowane przez algorytmy PL Ma miejsce duża subiektywność w wyborze pojedynczego celu, który będzie wykorzystany w przetransformowanym modelu - wynik może różnić się istotnie w zależności od wyboru
49 Graficzna ilustracja Znalezione rozwiązanie
50 Czy ten wynik ma cechy ogólności?Pokazaliśmy graficznie na jednym przykładzie, że metoda sprowadzenia do jedno-celowego zagadnienia liniowego poprzez transformację części funkcji celu prowadzi do znalezienia/wybrania jednego z rozwiązań Pareto optymalnych Czy ten wynik ma cechy ogólności? Będziemy rozważaną metodę skalaryzacji nazywali metodą ograniczenia (MO) (ang. constraint method) lub metodą
51 Sformułowanie oryginalne (WCPL)Sformułowanie metody ograniczenia Niech będzie optymalnym rozwiązaniem zagadnienia metody ograniczenia (MO)
52 Twierdzenie MO1 Jeżeli jest unikatowym rozwiązaniem optymalnym zagadnienia MO, dla pewnych wartości to jest rozwiązaniem Pareto optymalnym zagadnienia WCPL Jeżeli unikatowość rozwiązania zagadnienia MO nie jest gwarantowana, wówczas jedynie słabe rozwiązanie Pareto optymalne jest gwarantowane
53 Twierdzenie MO2 Jeżeli jest jest rozwiązaniem Pareto optymalnym zagadnienia WCPL, to jest optymalnym rozwiązaniem zagadniena MO, dla pewnych wartości
54 Przykład:
55 Wybrane metody poszukiwania rozwiązań wielocelowych zagadnień liniowych2. Sprowadzenie do jedno-celowego zagadnienia liniowego poprzez agregację funkcji celu (metoda ważenia (ang. weighting method))
56 Przykład Jeden cel mierzony jest w dolarach (zysk) a drugi w uzyskiwanym udziale na rynku (np. pewna miara ,,lojalności" kupujących dany produkt przejawiająca się w większym prawdopodobieństwie powtórzenia zakupu danego towaru). Jeżeli można przetworzyć jeden z nich, powiedzmy pozyskane udziały na rynku, w dolary zysku (lub alternatywnie, dolary zysku w jednostki udziału na rynku), to będziemy mogli złożyć obydwa cele w jeden, który będzie mierzony w jednakowych jednostkach
57 Załóżmy, że jesteśmy w stanie, dla naszego przykładu, wybrać wagi: dla pierwszego celu 0.6, a dla drugiego, 0.4. Uzyskamy wówczas następujący model naszego zagadnienia: Znaleźć wartości i takie, które: maksymalizują (zagregowane funkcje celu w wybranych jednostkach użyteczności) spełniając: (ograniczenie dostępności surowca) (ograniczenie nasycenia rynku produktu 1.) (ograniczenie nasycenia rynku produktu 2.) (warunki nieujemności)
58 Graficzne rozwiązanieRozwiązanie optymalne
59 Zalety Możemy bezpośrednio zastosować istniejące algorytmy lub oprogramowanie PL do rozwiązania zaproponowanego modelu. Wady Istotny czas i ostrożność są potrzebne dla określenia odpowiednich wag
60 Graficzna ilustracja Znalezione rozwiązanie
61 Czy ten wynik ma cechy ogólności?Podobnie jak poprzednio, pokazaliśmy graficznie na jednym przykładzie, że metoda sprowadzenia do jedno-celowego zagadnienia liniowego poprzez zaproponowanie zagregowanej – ważonej funkcji celu prowadzi do znalezienia/wybrania jednego z rozwiązań Pareto optymalnych Czy ten wynik ma cechy ogólności?
62 Sformułowanie oryginalne (WCPL)Sformułowanie metody ważenia (MW) Niech będzie optymalnym rozwiązaniem zagadnienia metody ważenia gdzie
63 Twierdzenie MW1 Jeżeli jest rozwiązaniem optymalnym zagadnienia MW, dla pewnych wartości to jest rozwiązaniem Pareto optymalnym zagadnienia WCPL Warunek twierdzenia może być zamieniony innym brzmiącym: unikatowym rozwiązaniem optymalnym zagadnienia MW, dla pewnych wartości
64 jest jest rozwiązaniem Pareto optymalnym zagadnienia WCPL, toTwierdzenie MW2 Jeżeli jest jest rozwiązaniem Pareto optymalnym zagadnienia WCPL, to jest optymalnym rozwiązaniem zagadnienia MW, dla pewnych wartości Geometrycznie dla przypadku ogólnego k funkcji celu, czyli w przestrzeni celów jest hiperpłaszczyzną z normalnym do niej wektorem
65 Zapraszam na kolejny wykładDziękuję za uwagę Zapraszam na kolejny wykład