Zaliczenie Wykładu - Metody Optymalizacji Decyzji PDF

ZALICZENIE WYKŁADU – METODY OPTYMALIZACJI DECYZJI ZASADY ROZWIĄZAŃ DOPUSZCZALNYCH: Jeśli przynajmniej jedna zmienna przyjmuje wartość ujemną, to nie jest to rozwiązanie dopuszczalne Jeśli wszystkie zmienne przyjmują wartości dodatnie lub są równe zeru, to jest to rozwiązanie dopuszczalne Je...

ZALICZENIE WYKŁADU – METODY OPTYMALIZACJI DECYZJI ZASADY ROZWIĄZAŃ DOPUSZCZALNYCH: Jeśli przynajmniej jedna zmienna przyjmuje wartość ujemną, to nie jest to rozwiązanie dopuszczalne Jeśli wszystkie zmienne przyjmują wartości dodatnie lub są równe zeru, to jest to rozwiązanie dopuszczalne Jeśli wszystkie zmienne przyjmują wartości dodatnie to rozwiązanie jest punktem wewnętrznym zbioru rozwiązań dopuszczalnych Jeśli k < n - r oraz dokładnie k zmiennych spośród n przyjmuje wartość zero, to rozwiązanie znajduje się na krawędzi zbioru rozwiązań dopuszczalnych, ale nie jest jego wierzchołkiem, Jeśli k = n - r i tylko k zmiennych ma wartość zero, to rozwiązanie jest wierzchołkiem i może być rozwiązaniem optymalnym, Jeśli k > n - r oraz k zmiennych przyjmuje wartość zero, to mówimy, że rozwiązanie jest zdegenerowane. Metoda graficzna służy do rozwiązywania problemów programowania liniowego, w których jeden z wymiarów układu równań nie jest większy od 2. W przypadku gdy mamy do czynienia z dwoma zmiennymi, układ rozwiązujemy graficznie zakładając, że osie układu współrzędnych odpowiadają poszczególnym zmiennym. W przypadku gdy mamy do czynienia z dwoma warunkami ograniczającymi przy kilku zmiennych, skorzystać możemy z rozwiązania polegającego na transformacji posiadanego układu równań – programu pierwotnego (PP) do programu dualnego (PD). Związki pomiędzy tymi programami są następujące: 1. W programie dualnym jest tyle zmiennych, ile warunków ograniczających w programie pierwotnym (i odwrotnie). 2. Współczynniki funkcji celu programu pierwotnego są wyrazami wolnymi układu nierówności programu dualnego (i odwrotnie). 3. Macierz współczynników układu nierówności [aji] w programie dualnym jest transpozycją macierzy współczynników układu nierówności w programie pierwotnym [aij] (i odwrotnie). 4. Programem dualnym względem programu dualnego jest program pierwotny. W PD tworzymy nowe zmienne : yi (i = 1,...,r) oraz nową funkcję celu G(y). Rozwiązując problem PL z wykorzystaniem PP i PD należy pamiętać, że: jeżeli w PP funkcja celu jest maksymalizowana, to w programie dualnym jest minimalizowana (i odwrotnie), konstruując PD, należy zmienić kierunki nierówności na przeciwne w porównaniu z PP, w rozwiązaniach optymalnych obu programów x* = (x1*,x2*,...,xn *) i y* = (y1*,y2*,...,yr *) wartości funkcji celu są sobie równe, czyli: F(x1*,x2*,...,xn*) = G(y1*,y2*,...,yr*), jeżeli j-y warunek PD jest (chociaż w jednym) optymalnym rozwiązaniu tego programu spełniony z nierównością (ostro), to odpowiadająca mu j-a zmienna xj w (dowolnym) optymalnym rozwiązaniu PP przyjmuje wartość zero. Strategia gier uwzględnia różne kombinacje czynników niepewnych, co wspomaga podejmowanie decyzji w ujęciu optymalizacyjnym. Strategię gier wykorzystuje się w sytuacjach, gdy w badanych projektach nie ma możliwości ustalenia prawdopodobieństw osiągania danego efektu. Wynika to głównie z faktu, że na ogół podejmowane decyzje o charakterze ekonomicznym mają charakter niepowtarzalny. Zastosowanie zasad i metod strategii gier polega na: obliczeniu wskaźników efektywności dla wszystkich rozpatrywanych wariantów decyzji przy założeniu, że wariantom tym można przypisać scenariusze decyzyjne różniące się wszystkimi możliwymi kombinacjami czynników niepewnych; każdy wariant decyzji ma dwa lub więcej scenariuszy, każdy ze scenariuszy utożsamiany jest z inną kombinacją czynników niepewnych i charakteryzuje się określoną efektywnością ekonomiczną; zakłada się, że istnieją trudności w jednoznacznym ustaleniu, które ze scenariuszy decyzyjnych są optymistyczne lub pesymistyczne, ponieważ dany scenariusz może być optymistyczny w aspekcie danego wariantu, a w aspekcie innego może być scenariuszem pesymistycznym; opracowywaniu decyzji według formuły maksyminu i minimaksu Wyróżniamy następujące rodzaje zagadnień rozwiązanych z wykorzystaniem teorii gier:  gry o sumie zerowej - suma wygranych równa jest sumie przegranych, a łączny zysk netto graczy jest zerowy. Obaj gracze postępują ostrożnie, niezależnie i racjonalnie. sytuacje kooperacyjne i niekooperacyjne niekooperacyjna sytuacja strategiczna - brak możliwości komunikowania się graczy i koordynacji działań sytuacje kooperacyjne – negocjacje konkurencja jednorazowa i powtarzalna Sytuacja jednorazowa - np. kupno/sprzedaż nieruchomości Sytuacja powtarzalna - np. negocjacje ze związkami zawodowymi, ustalanie cen na produkty lub usługi konkurencja sekwencyjna - gry o charakterze sekwencyjnym - drzewa gier gry z naturą - gry dwuosobowe, w których przeciwnikiem jest natura (sytuacja rynkowa, wieloscenariuszowe uwarunkowania). Rodzaje strategii: Strategia optymalna - strategia maksymalizująca wartość oczekiwaną wypłaty Strategia dominująca - strategia optymalna, niezależnie od tego, jakie posunięcie wybiorą inni gracze (strategia, która stanowi najlepszą odpowiedź na dowolny ruch przeciwników). Równowaga Nasha - każdy gracz wybiera optymalną strategię, przy założeniu danych strategii wybranych przez innych graczy (strategia, która stanowi najlepszą odpowiedź na określone postępowanie innych graczy). W sytuacjach, gdy niemożliwe jest porozumienie, gracze powinni stosować strategie zapewniające osiągnięcie równowagi. Gdy w grze zostanie osiągnięta równowaga Nasha, żaden z graczy nie może poprawić swojego wyniku poprzez jednostronną zmianę wybranej strategii. W jednej grze może być kilka równowag Nasha. Zarówno równowaga strategii dominującej, jak i równowaga Nasha mają charakter stabilny. Nie zawsze istnieje strategia dominująca. W rzeczywistości w teorii gier można przyjąć różne scenariusze działania: kryterium A. Walda (pesymistyczne), polegające na dążeniu do osiągnięcia najlepszego z najgorszych rozwiązań (zasada maksyminu), dla każdej decyzji j ustal minimalny zysk wj = min (aij) i wybierz jako optymalną taką decyzje k, dla której: wk = max{wj } kryterium Hurwicza, polegająca na wybraniu średniej najlepszej kombinacji pod względem minimalizacji strat i jednocześnie maksymalizacji zysku, przyjmij pewną liczbę α (0 ≤ α ≤ 1) zwaną współczynnikiem ostrożności i dla każdej decyzji oblicz: hj (α) = α min{αij} + (1 - α)max{αij} jako optymalną strategię wybierz decyzję k, dla której: hk (α) = max{hj (αij)} kryterium L.J. Savage’a (minimalnego żalu), polegające na przyjęciu rozwiązania powodującego najmniejszą z największych strat (zasada minimaksu), a) Dla każdego stanu natury ustal maksymalny zysk zi = max(aij} b) Utwórz macierz względnych strat s = [sij], gdzie sij = zi – aij (i = 1,…,m; j = 1,…,n) c) Dla każdej decyzji ustal maksymalną względną stratę sj = max{sij} d) Wybierz jako optymalną decyzję, dla której: sk = min{sj } Kryterium Bayesa, które zakłada równość nieznanych prawdopodobieństw zaistnienia różnych stanów natury. Decyzje podejmuje się w oparciu o maksymalną z wyznaczonych wartości oczekiwanych (średnie arytmetyczne) oszacowanych dla różnych założonych decyzji. Dla każdej decyzji ustal średni zysk I jako optymalną wybierz taką decyzję k, dla której: bk = max{bj } Strategia dominująca to najlepsza ze wszystkich możliwych strategii, niezależnie od decyzji, jaką podejmie drugi gracz. Strategia zdominowana to taka strategia, względem której istnieje(ą) strategia(e), która(e) jest(są) zawsze lepsza(e), niezależnie od decyzji, jaką podejmie drugi gracz. Strategia słabo dominująca to taka strategia, dla której nie istnieje strategia lepsza przy dowolnej decyzji, jaką podjąłby drugi gracz. Strategia słabo zdominowana to taka strategia, dla której istnieje(ą) strategia(e), która(e) jest(są) zawsze niegorsza (e), niezależnie od decyzji, jaką podejmie drugi gracz. Przedsięwzięcie To zorganizowane działanie ludzkie zmierzające do osiągnięcia określonego celu, zawarte w skończonym przedziale czasu – z wyróżnionym początkiem i końcem – oraz zrealizowane przez skończoną liczbę osób, środków technicznych, energii i materiałów, środków finansowych i informacji. Czynność Polega na wykonaniu pewnego zadania, na realizację którego potrzebny jest pewien okres (czas), a także (najczęściej) określone środki materialne, stanowiące koszty realizacji danej czynności. Czynności pozorne (fikcyjne), które nie wymagają nakładów czasu ani środków. Są one wprowadzane do sieci w celu zaznaczenia kolejności występowania innych czynności. Ciągiem czynności Nazywa się kolejne, następujące po sobie czynności takie, że zdarzenia końcowe pewnej czynności jest jednocześnie zdarzeniem początkowym dla czynności następnej. Przy czym każde zdarzeniem początkowym i końcowym tylko dla jednej czynności. Pod pojęciem sieci zależności rozumie się graficzne przedstawienie planu przedsięwzięcia, uwzględniające wzajemne logiczne zależności między czynnościami Zdarzeniem początkowym w sieci nazywamy zdarzenie, które nie jest końcem żadnej czynności, a zdarzeniem końcowym – zdarzenie, które nie jest początkiem żadnej czynności. Problem komiwojażera Komiwojażer ma do odwiedzenia pewną liczbę miast. Chciałby dotrzeć do każdego z nich i wrócić do miast, z którego wyruszył. Dane są również odległości miedzy miastami. Jak powinien zaplanować trasę podróży, aby w sumie przebył możliwie najkrótszą drogę? Przez odległość między miastami możemy rozumieć odległość w kilometrach, czas trwania podróży między tymi miastami albo koszt takiej podróży (na przykład cenę biletu lotniczego). W tym ostatnim przypadku, poszukiwanie optymalnej trasy polega na zminimalizowaniu całkowitych kosztów podróży. Zakładamy przy tym, że odległość między dowolnymi dwoma miastami jest nie większa niż długość jakiejkolwiek drogi łączącej te miasta, która wiedzie przez inne miasta. Sformułowanie problemu Budujemy graf ważony, którego wierzchołki są miastami. Każdą parę miast połączmy krawędziami. Każdej krawędzi nadajemy wagę równa 'odległości między miastami odpowiadającymi wierzchołkom, które są końcami tej krawędzi. Otrzymujemy w ten sposób graf pełny, który ma tyle wierzchołków ile miast musi odwiedzić komiwojażer (wliczając w to miasto, z którego wyrusza). Odwiedzenie wszystkich miast odpowiada cyklowi, który przechodzi przez każdy wierzchołek danego grafu dokładnie raz. Cykl taki nazywamy cyklem Hamiltona. Poszukujemy w grafie pełnym cyklu Hamiltona o minimalnej sumie wag krawędzi. Problem komiwojażera nie jest znany żaden wielomianowy optymalny algorytm dla tego problemu i jest mało prawdopodobne, że taki algorytm w ogóle istnieje. Podejścia spotykane w rozwiazywaniu problemu komiwojażera:  Heurystyka Algorytmy aproksymacyjne Metody inteligentne Znalezienie najkrótszej drogi Heurystyka polega na znalezieniu rozwiązania jak najbardziej zbliżonego do optymalnego. Stosowana jest najczęściej, gdy algorytm dokładny jest nieznany lub nieopłacalny (ze względu na koszt, czas). Korzystamy z niej, gdy chcemy skrócić czas działania programu, a rozwiązanie odbiegające od optymalnego o kilka procent jest dla nas satysfakcjonujące. Zaliczamy tu: Algorytmy zachłanne – polegające na składaniu lokalnie optymalnych wyborów ścieżki z nadzieją na znalezienie globalnego optimum. W przypadku problemu komiwojażera metoda polega na wybraniu nieodwiedzonego jeszcze miasta znajdującego się w najbliższej odległości od naszej aktualnej pozycji. Przykłady: algorytm Kruskala, algorytm Prima. Wymiana parami – głównym założeniem jest znaleźć dwie przecinające się krawędzie w drzewie rozpinającym i zamienić je w taki sposób, aby się nie przecinały. Metoda ta modyfikuje już istniejące rozwiązanie, na przykład algorytm zachłanny zmniejszając jego koszt. Zaletą tej metody jest znaczna poprawa jakości rozwiązania w stosunku do czasu obliczeniowego. Symulowane wyżarzanie – (nazwa od wyżarzania w metalurgii, czyli kontrolowanego ogrzewania i chłodzenia materiału, aby zwiększyć rozmiar i jakość kryształów). Metoda ta jest techniką przybliżania globalnego optimum funkcji zwłaszcza w dużej przestrzeni wyszukiwania. Przeszukiwanie tabu - algorytm wykorzystujący lokalne metody wyszukiwania lub najbliższe sąsiedztwo, po to, aby przenieść iteracje z jednego potencjalnego rozwiązania do ulepszonego. Algorytmy aproksymacyjne – algorytmy, dla których nie są znane szybkie metody znajdowania rozwiązania optymalnego. Różnicą między algorytmem aproksymacyjnym a heurystycznym jest informacja o jakości otrzymanego rozwiązania w stosunku do rozwiązania optymalnego. Zaliczamy tu np. Algorytm Christofidesa – metoda znalezienia rozwiązania przybliżonego dla problemu komiwojażera, w przypadku w których odstępy tworzą przestrzeń metryczną. W przypadku metody Christofidesa rozwiązanie jest 1,5 razy gorsze od rozwiązania optymalnego. Metody inteligentne – powstały w wyniku obserwacji świata naturalnego. Sieci neuronowe inspirowanie działaniem układu nerwowego, algorytm genetyczny na podstawie ludzkiej ewolucji i genetyki, a algorytm mrówkowy, jak sama nazwa wskazuje, wzięty z obserwacji tych zwierząt. Zaliczamy do nich: Algorytm mrówkowy – zaczerpnięty z zachowania mrówek szukających najkrótszej drogi pomiędzy ich kolonią, a źródłem pożywienia. W świecie naturalnym mrówki wędrują losowo i po znalezieniu pożywienia wracają do swojej kolonii wydzielając feromony. W ten sposób powstają drogi feromonowe, a inne mrówki czując zapach podążają tą ścieżką wzmacniając tym samym gęstość feromonu. Algorytm genetyczny – należy do klasy algorytmów ewolucyjnych. Metoda ta jest powszechnie używana do generowania wysokiej jakości rozwiązań wykorzystując operatory mutacji, krzyżowania i selekcji. Ewolucja rozpoczyna się zazwyczaj od losowo generowanych jednostek i jest procesem iteracyjnym, a populacje w każdej iteracji nazywamy pokoleniem. Analiza przepływów międzygałęziowych (PM) to typ rachunku makroekonomicznego, który dotyczy badania stanu i struktury złożonych systemów ekonomicznych. Analizę PM nazywa się również analizą nakładów i wyników lub, według terminologii angielskiej, analizą input-output. Twórcą tej metody opisu i pomiaru działalności gospodarczej jest Wassily Leontief, amerykański uczony pochodzenia rosyjskiego. Za teoretyczne i empiryczne prace związane z analizą PM Leontief uzyskał w 1973 r. nagrodę Nobla w dziedzinie ekonomii. Analiza input-output jest stosowana również do analiz międzyregionalnych, do badań nad ochroną środowiska, nad energochłonnością oraz pracochłonnością. Tablica przepływów międzygałęziowych (TPM) zawiera dane liczbowe charakteryzujące działalność gospodarczą w pewnym okresie (zwykle w ciągu roku) zestawione według określonego porządku.