2.1. Etapy rozwiązywania problemu decyzyjnego (podejmowania decyzji)
1. Formułowanie (identyfikacja) problemu decyzyjnego (rozpoznanie i analiza sytuacji decyzyjnej, kryterium wyboru dobrej decyzji, warunki ograniczające)
2. Budowa matematycznego modelu problemu decyzyjnego (sformalizowanie zadania decyzyjnego, znalezienie zależności powiązań)
3. rozwiązanie modelu
4. Ocena poprawności i realności uzyskanych rozwiązań modelu oraz ewentualna weryfikacja
5. Przedstawienie rozwiązań decydentom i ostateczne przygotowanie decyzji
2.2 Izokwanty lub linie izocelowe (definicja lini modelowej i rozwiązania dopuszczalnego)
Proste wynikające z funkcji celu nazywamy Izokwantami albo Liniami Izocelowymi
Każda izokwanta charakteryzuje się tym, że dowolna para współrzędnych danej izokwanty daje identyczną wartość funkcji celu.
Zbiór rozwiązań dopuszczalnych może być zbiorem ograniczonym, nieograniczonym lub zbiorem pustym (oznacza to, że źle postawiliśmy problem decyzyjny).
Twierdzenie I mówi, że zbiór rozwiązań dopuszczalnych modelu programowania liniowego jest zbiorem (wielobokiem) wypukłym
Twierdzenie II Funkcja celu modelu programowania liniowego osiąga wielkość optymalną na wierzchołku zbioru rozwiązań dopuszczalnych modelu
Twierdzenie III Jeżeli w modelu programowania liniowego istnieją co najmniej 2 rozwiązania optymalne, o różnych wartościach wektorów zmiennych decyzyjnych, to każda wypukła kombinacja tych rozwiązań jest również optymalnym rozwiązaniem tego modelu.
Wniosek: rozwiązań maksymalnych jest nieskończenie wiele, i znajdują się one na odcinku łączącym 2 wierzchołki zbiorów rozwiązań optymalnych.
Jeżeli zbiór rozwiązań dopuszczalnych jest ograniczony i niepusty, to możliwe jest:
jedno rozwiązanie optymalne (na wierzchołku)
nieskończenie wiele rozwiązań optymalnych (na odcinku)
Jeżeli zbiór rozwiązań dopuszczalnych jest nieograniczony, to poza wyznaczonymi wyżej przypadkami rozwiązań optymalnych może wystąpić również rozwiązanie, dla którego wartość funkcji celu jest nieograniczona.
Rozwiązanie optymalne nie istnieje, jeżeli zbiór rozwiązań dopuszczalnych jest zbiorem pustym, albo rozwiązania dają nieograniczoną funkcję celu.
2.3. Omów metodę CPM
CPM - metoda ścieżki krytycznej (critical path method) Istotne jest aby znać czasy realizacji poszczególnych czynności.
Celem jest wyznaczenie najkrótszego czasu zakończenia przedsięwzięcia oraz ustalenie harmonogramu wykorzystywania poszczególnych czynności. Spośród wszystkich czynności szczeólnego znaczenia nabierają czynności tworzące pewną ścieżkę nazywaną krytyczną, która łączy początek sieci z jej wierzchołkiem końcowym.
Przedsięwzięcie jest wykonane jeśli zostaną zakończone wszystkie czynności wszystkich ścieżek łączących początek i koniec sieci.
Jeżeli sumujemy czasy przyjścia na danej ścieżce to mamy sumę czasu przejścia ścieżki. Najdłuższy czas przejścia ścieżki nazywamy czasem krytycznym. Ścieżki sieci którym odpowiada czas krytyczny nazywane są ścieżkami krytycznymi, a czynności składowe tych ścieżek nazywane są czynnościami krytycznymi. Najkrótszy możliwy czas zakończenia przedsięwzięcia równy jest czasowi krytycznemu.
W celu wyznaczenia ścieżki krytycznej i czasu krytycznego należy obliczyć powstałe granice czasowe dla czynności i zdarzeń.
2.4. Funkcją Lagrange'a nazywamy funkcję:
gdzie
i - mnożnik Lagrange'a związany z i-tym warunkiem zadania
Przy rozwiązywaniu modeli nieliniowych należy zwrócić uwagę na to, czy jest w postaci kanonicznej czy standardowej.
Przy rozwiązywaniu modeli w postaci kanonicznej najczęściej znajduje zastosowanie tzw. metoda mnożników Lagrange'a. Tok postępowania można podzielić na dwa etapy:
Etap I: Sprawdzamy czy funkcja celu f(x) ma ekstremum bezwarunkowe, jeśli tak to jest to rozwiązaniem zadania
Jeśli nie są spełnione warunki ograniczające dla ekstremum przechodzimy do etapu II
Etap II: funkcję celu przekształcamy w funkcję Lagrange'a i szukamy ekstremum funkcji Lagrange'a
2.5 Twierdzenie dualności
1) Zadanie pierwotne jest zadaniem dualnym do swojego zadania dualnego (i jest to wtedy model pierwotny)
2) Jeżeli zadanie pierwotne i zadania dualne mają rozwiązanie dopuszczalne to obydwa mają rozwiązanie optymalne. Jeżeli natomiast jedno z nich nie ma rozwiązania dopuszczalnego to obydwa nie mają rozwiązania optymalnego.
3) Jeżeli x1,x2…xn jest rozwiązaniem dopuszczalnym zadania pierwotnego, a y1, y2,… yn jest rozwiązaniem dopuszczalnym zadania dualnego to pomiędzy wartościami funkcji celu zachodzi nierówność
L(x)
L(y) jeżeli L(x) max i odwrotnie.
4) Jeżeli istnieją dwa takie rozwiązania dopuszczalne x1,x2…xn oraz y1, y2,… yn ze funkcje celu są sobie równe L(x)=L(y) to obydwa rozwiązania są rozwiązaniami optymalnymi.
5) Jeżeli x1,x2…xn jest rozwiązaniem dopuszczalnym zadania prymarnego oraz y1, y2,… yn jest rozwiązaniem dopuszczalnym zadania dualnego to aby rozwiązania te były rozwiązaniami optymalnymi wystarczy że są spełnione następujące warunki:
|
|
yi>0 |
xi>0
|