pytania.pdf

(732 KB) Pobierz
1. Co obejmuje proces decyzyjny.
•
Identyfikacja sytuacji decyzyjnej
Sytuacja decyzyjna to zbiór wszystkich czynników, mających wpływ na podjęcie decyzji przez
decydenta w procesie decyzyjnym.
Czynniki można podzielić na: niezależne od decydenta i zależne od decydenta.
•
Sformułowanie problemu decyzyjnego
Problem decyzyjny oznacza sytuację problemową, w której podmiot (decydent) staje przed
koniecznością wyboru jednego z przynajmniej dwóch możliwych wariantów działania.
Dobrze sformułowany problem powinien szczegółowo definiować:
decydenta lub decydentów
warunki ograniczające decyzję
zbiór decyzji dopuszczalnych
kryteria oceny decyzji
•
Zbudowanie modelu decyzyjnego
Model decyzyjny oznacza teoretyczne odwzorowanie wycinka rzeczywistości, które w sposób
syntetyczny opisuje problem decyzyjny. Model taki powinien umożliwiać określenie zbioru decyzji
dopuszczalnych i zbioru decyzji optymalnych, jeśli tylko takie zbiory istnieją.
W większości przypadków modele budowane na potrzeby problemu decyzyjnego to modele
matematyczne, ale również ekonomiczne, informatyczne(systemy informatyczne), a nawet
psychologiczne, czy filozoficzne.
•
Wyznaczenie decyzji dopuszczalnych i decyzji wystarczających lub decyzji optymalnych
Decyzja dopuszczalna oznacza taką decyzję, która spełnia wszystkie warunki ograniczające decyzję.
Zbiór wszystkich takich decyzji nazywamy zbiorem decyzji dopuszczalnych.
•
Podjęcie ostatecznej decyzji
Decyzją może być działanie/akt lub opinia/sąd w jakiejś sprawie. Aby proces decyzyjny miał sens,
potrzebne są co najmniej dwie różne możliwości wyboru (kandydaci na decyzje), a więc istnienie
alternatywy.
2. Postać standardowa, kanoniczna i macierzowa zadania
programowania liniowego.
Na przykładzie z mojego projektu
Postać standardowa modelu
FC:
WO:
1)
2)
WB:
Postać kanoniczna
Postać kanoniczna modelu to taka, gdzie wszystkie warunki ograniczające sprowadzone są do
równości. W przypadku nierówności typu jest to możliwe dzięki dodaniu do lewej strony równania
warunku ograniczającego zmiennej swobodnej ze współczynnikiem 1. Do funkcji celu zmienne
swobodne wchodzą ze współczynnikiem 0.
WO: 1)
2)
FC:
WB:
Postać macierzowa
Model programowania liniowego można zapisać w postaci macierzowej:
FC:
WO:
WB:
gdzie:
,
,
,
.
3. Opisać przypadki szczególne rozwiązania zadania programowania
liniowego.
SPRZECZNOŚĆ
– gdy nie ma rozwiązań dopuszczalnych.
Przykład: gdy w metodzie graficznej zbiór rozwiązań jest zbiorem nieograniczonym w kierunku
wzrostu wartości funkcji celu dla zadania na maksimum bądź spadku dla zadania na minimum.
Metoda Simplex: gdy w rozwiązaniu optymalnym zmienna sztuczna będzie miała wartość niezerową
(czyli będzie w bazie).
ROZWIĄZANIA ALTERNATYWNE
– gdy więcej niż jedno rozwiązanie. Możliwe jest też istnienie
nieskończenie wielu rozwiązań.
Przykład: w metodzie graficznej rozwiązaniem jest odcinek AB, czyli każdy punkt leżący na tym
odcinku. Metoda Simplex: gdy w rozwiązaniu optymalnym dla zmiennych niebazowych zerowe
wartości wskaźników optymalności.
NIEOGRANICZONY ZBIÓR ROZWIĄZAŃ
– gdy zbiór rozwiązań jest nieograniczony z góry (z dołu musi
być ograniczony ze względu na warunki nieujemności. Metoda Simplex: gdy w tablicy Simple kolumna
zmiennej wchodzącej do bazy ma wszystkie elementy niedodatnie. (istnieje możliwość występowania
rozwiązania optymalnego gdy FC jest minimalizowana).
4. Na czym polega rozwiązanie zadania programowania liniowego
metodą graficzną.
Metoda wykreślna pozwala na wyznaczenie zbioru rozwiązań dopuszczalnych (ZRD), dzięki
wykreśleniu na płaszczyźnie dwuwymiarowej (
) prostych z warunków ograniczających oraz
brzegowych oraz oznaczeniu zbiorów rozwiązań poszczególnych nierówności.
Punkty przecięcia prostych z warunków ograniczających z osiami
uzyskuje się poprzez
przyrównanie w każdym warunku ograniczającym najpierw pierwszej decyzyjnej do zera
i obliczenie drugiej, a następnie w kolejności odwrotnej przyrównanie drugiej zmiennej
do zera i obliczenie pierwszej. Proste z warunków brzegowych pokrywają się z osiami
.
Zbiory rozwiązań poszczególnych warunków ograniczających i brzegowych przedstawia się za pomocą
strzałek wskazujących te zbiory.
W celu wyznaczenia punktu, w którym funkcja celu osiąga wartość maksymalną (minimalną)
konieczne jest obliczenie wartości funkcji celu w punktach przecięcia się prostych z WB i WO
(należących do zbioru rozwiązań dopuszczalnych) oraz określenie, w którym z tych punktów funkcja
ta ma najwyższą (najniższą) wartość – współrzędne tego punktu stanowią rozwiązanie optymalne.
5. Metoda budowy zadania dualnego.
Gdy w funkcji celu występują więcej niż dwie zmienne oraz istnieje 2 lub mniej warunków
ograniczających zadanie programowania liniowego można zamienić na dualne i rozwiązać metodą
graficzną. Zadanie dualne buduje się na podstawie poniższych zasad:
Zadanie pierwotne
Zadanie dualne
Przejście do postaci pierwotnej: gdy podstawi się wartości zmiennych y do warunków
ograniczających z zadania dualnego i np. w pierwszym WO lewa strona równa się prawej to warunki
zadania dualnego są spełnione słabo (tj. z równością) i
. Jeśli np. w warunku 2 po
podstawieniu lewa i prawa strona się różnią to warunki ZD są spełnione ostro i x2=0. Otrzymane
wartości podstawia się do WO (równości) z zadania pierwotnego i otrzymuje się rozwiązanie
optymalne.
Związki pomiędzy zadaniem pierwotnym, a zadaniem dualnym:
a) W zadaniu dualnym jest tyle zmiennych ile warunków ograniczających w zadaniu
pierwotnym (i odwrotnie).
b) Współczynniki FC w zadaniu pierwotnym są wyrazami wolnymi układu nierówności
zadania dualnego (i odwrotnie).
c) Macierz współczynników układu nierówności aij w zadaniu dualnym jest transpozycją
macierzy współczynników układu nierówności w zadaniu pierwotnym (i odwrotnie).
d) Zadanie dualne względem zadania dualnego jest zadaniem pierwotnym.
e) Jeżeli w zadaniu pierwotnym mamy maksymalizację, to w zadaniu dualnym
minimalizację (i odwrotnie) oraz zmieniamy znak nierówności
Twierdzenie o dualności – zadanie pierwotne ma rozwiązanie wtedy i tylko wtedy, gdy
zadanie dualne ma rozwiązanie oraz:
pierwotne
Z(MAX)=�½(MIN)
dualne
Rozwiązując jedno z zadań, automatycznie rozwiązujemy też drugie. Twierdzenie ma duże
znaczenie praktyczne, ponieważ czasami łatwiej jest rozwiązać zadanie dualne (mniej
zmiennych).
6. Zbiór rozwiązań dopuszczalnych, a rozwiązanie optymalne. Gdzie
znajdujemy rozwiązanie optymalne.
Zbiór rozwiązań dopuszczalnych
otrzymuje się w metodzie graficznej z wykresu nierówności z
warunków ograniczających i brzegowych (część wspólna wszystkich warunków na wykresie tworzy
zbiór rozwiązań dopuszczalnych).
Rozwiązanie optymalne
jest rozwiązaniem należącym do zbioru rozwiązań dopuszczalnych, które
jednocześnie spełnia założenie funkcji celu (maksymalizacja lub minimalizacja), czyli jest to
rozwiązanie spośród ZRD, dla którego wartość funkcji celu jest najwyższa/najniższa. Rozwiązania
dopuszczalnego szuka się w punktach przecięcia prostych ograniczających ZRD – współrzędne
punktu, w którym wartość FC jest najwyższa/najniższa są rozwiązaniem optymalnym.
a) Jeżeli model posiada ZRD, to można dla modelu wyznaczyć RO:
•
Istnieje jedno RO
•
Istnieje nieskończenie wiele RO, dla których FC przyjmuje taką samą wartość
b) RO nie istnieje gdy nie istnieje ZRD (układ WO jest sprzeczny)
c) Skończone RO nie istnieje gdy:
•
ZRD jest nieograniczony w kierunku wzrostu FC w przypadku, gdy jest ona
maksymalizowana
•
ZRD jest nieograniczony w kierunku zmniejszania się FC gdy jest ona
minimalizowana
Poszukując RO należy pamiętać, że leży ono na jednym z wierzchołków lub na krawędzi boku
ZRD.
7. Kiedy rozwiązanie jest optymalne w zadaniu simpleks.
Maksymalizacja FC
– Wszystkie wskaźniki optymalności (c
j
-z
j
) muszą być niedodatnie.
(cj-zj)≤0
Minimalizacja FC
– Wszystkie wskaźniki optymalności muszą być nieujemne.
(cj-zj)≥0
8. Kryterium wejścia i wyjścia z bazy w metodzie simpleks.
kryterium
Wejścia
Wyjścia
Maksymalizacja FC
*
Minimalizacja FC
Min(c
j
-z
j
)
*iloraz macierzy wyrazów wolnych i macierzy wyrazów przy zmiennej wchodzącej do bazy.
Kryterium wejścia do bazy:
•
Maksymalizacja: zmienna z najwyższą wartością wskaźnika optymalności;
•
Minimalizacja: zmienna z najniższą wartością wskaźnika optymalności.
Kryterium wyjścia z bazy:
•
Minimalizacja i maksymalizacja: zmienna, dla której iloraz elementu z kolumny wyrazów
wolnych przez współczynnik z kolumny zmiennej wchodzącej do bazy ma najmniejszą
wartość.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin