ZAGADNIENIA DECYZYJNE
Osiągnięcie określonego celu zwykle wymaga zaangażowania pewnych środków pieniężnych, materialnych i czasu.
Te środki są ograniczone i należy nimi dysponować tak, aby w maksymalnym stopniu zrealizować wyznaczony cel.
Trzeba podjąć decyzje, które środki i w jakich ilościach należy zaangażować. Decyzji może być wiele.
Decyzja najlepsza z pkt widzenia przyjętego celu i przy uwzględnieniu istniejących ograniczeń, nazywa się DECYZJĄ OPTYMALNĄ (Dopt)
SYTUACJE DECYZYJNE
1. Ustalić taki plan produkcji uzyskanej z dostępnych czynników produkcji, przy którym przychód uzyskany ze sprzedaży wyrobów, będzie największy. 2. Ustalić taki plan rozwozu produktów, aby przy najniższym koszcie zaspokoić popyt odbiorców i wykorzystać podaż dostawców. 3. Ustalić taki harmonogram prac, aby stałe przedsięwzięcie zakończyć w najkrótszym czasie, przy zachowaniu pewnej kolejności wykonywanych czynności.
DECYZJE OPTYMALNE
Wyznaczanie Dopt ułatwią skonstruowane odpowiednio metody matematyczne. Problemy decyzyjne należy przedstawić w języku matematycznym i w tym modelu matematycznym wyznaczyć Dopt ze względu na przyjęte kryterium optymalizacyjne.
Metody wyznaczania Dopt należą do dziedziny zwanej BADANIAMI OPERACYJNYMI. Metody optymalizacji funkcji przy zadanych ograniczeniach nazywa się PROGRAMOWANIEM MATEMATYCZNYM (PM).
KONSTRUOWANIE MODELI MATEMATYCZNYCH
W typowych problemach decyzyjnych należy postępować wg podanych niżej reguł: 1. Określić zmienne decyzyjne. Będzie to ciąg zmiennych przyjmujących wartości liczbowe. 2. Zdefiniować ograniczenie określające decyzje w danych warunkach. Będzie to układ równań i nierówności. 3. Określić sposób porównania decyzji i wyboru spośród nich takiej, która najlepiej realizuje stawiany cel. Można osiągnąć to poprzez określenie funkcji celu, którą należy maksymalizować lub minimalizować w zależności od przyjętego kryterium optymalizacyjnego.
OGÓLNE SFORMUŁOWANIE ZADAŃ PM PRZY KRYTERIUM MAKSYMALNYM
x=(x1,.., xn1, xn+1,…, xn) – decyzja
f(x1 ,…, xn) – funkcja celu
X – część wspólna dziedziny funkcji f oraz funkcji g1,…, gn
Zadanie PM z kryterium maksymalizacji zapisujemy:
f(x1 ,…, xn) -> max (1)
przy ograniczeniach, gdzie b1 ,…, bm to znane liczby :
gi (x1 ,…, xn) ≤ bi dla i = 1,…, m1 (2)
gi (x1 ,…, xn) ≥ bi dla i = m1+1,…, m2 (3)
gi (x1 ,…, xn) = bi dla i = m2+1,…, m (4)
xi ≥ dla i = 1,…,n (5)
Zadanie PM polega na znalezieniu wśród pkt x=(x1 ,…, xn) є X spełniających warunki (2) – (5) takiego pkt (być może wielu pkt) x0, w którym funkcja celu f osiąga największą wartość. Pkt x0 nazywamy Dopt. Oznaczenia: D – podzbiór zbioru X taki, że dla każdego jego elementu spełnione są warunki ograniczające (2) - (5)
Dopt– podzbiór D taki, że dla każdego jego elementu x0 zachodzi f(x) ≤ f(x0). Zatem mamy relację: Dopt D X
ZADANIE PM Z KRYTERIUM MINIMALIZACJI
Elementy zbioru X nazywamy DECYZJAMI, X – zbiór decyzji. Elementy zbioru D nazywamy DECYZJAMI DOPUSZCZALNYMI, D – zbiór decyzji dopuszczalnych. Elementy zbioru Dopt nazywamy decyzjami optymalnymi, Dopt – zbiór decyzji optymalnych. Jeżeli D=Ø, to zadanie PM nazywamy SPRZECZNYM. Analogicznie określa się postać zadania PM z kryterium min, a mianowicie f(x) -> min przy warunkach ograniczających (2) – (5). Wówczas : Dopt={x0 є D: x∈Dfx≥f(x0)}
ZMIANIA KRYTERIUM Z MIN NA MAX Ten przypadek można sprowadzić do problemu maksymalizacji funkcji g(x) = -f(x). Pkt x0 w którym g(x0) -> max jest również pkt, w którym f(x) -> min i f(x0) = -g(x0).
Zatem zagadnienie minimalizacji funkcji celu przy zadanych ograniczeniach sprowadza się do zagadnienia maksymalizacji funkcji celu. Zwykle bez komputera, Dopt nie da się wyznaczyć. Na szczęście jt duża biblioteka oprogramowania dla zadań PM.
ZWIĄZEK MIĘDZY PM I PROGRAMOWANIEM LINOWYM (PL)
W dalszych wykładach skupimy się na PL tzn. na optymalizacji funkcji przy liniowych ograniczeniach. Najbardziej znaną i pożyteczną metodą wyznaczania optymalnych decyzji w zagadnieniach liniowych jest metoda SYMPLEKS.
SFORMUŁOWANIE ZADANIA PROGRAMOWANIA LINIOWEGO
PM jt programowaniem liniowym, gdy funkcja celu f jt funkcją liniową i funkcje g1, g2,…, gm są liniowe, tzn. :
c1x1+c2x2+…+cnxn→max(min)
przy ograniczeniach:
ai1x1+ai2x2+…+ainxn ≤bi dla i = 1,2, …, m1
ai1x1+ai2x2+…+ainxn≥ bi dla i = m1+1, …, m2
ai1x1+ai2x2+…+ainxn=bi dla i = m2+1, …, n
xi ≥ 0 dla i = 1,2, …, n xi ≤ 0 dla i = n1+1, …., n2
xi є R dla i = n1+1, …., n2
Macierz:
A= [aij]=a11a21…a1na21a22…a2n…am1…am2………amn jt macierzą znaną. Również parametry ci i= 1,2, … ,n oraz bj j=1,2, …, n mają znane wartości liczbowe. Rozwiązanie zadania PL polega na znalezienie Dopt (x1,x2,…,xn) є Dopt, tzn.: c1x1,c2x2,…,cnxn=max(min)
oraz spełnione są warunki ograniczające.
UKŁADANIE ZADAŃ DECYZYJNYCH (ZD)
Polega na „przetłumaczeniu” słownego, czasami dość swobodnego opisu sytuacji decyzyjnych na język matematyczny. Ogólne reguły formułowania ZD: - określenie zmiennych decyzyjnych jakie decydent ma wyznaczyć,
- sformułowanie warunków ograniczających jakie powinna spełniać decyzja dopuszczalna - sformułowanie celu decydenta, tj. ustalenie funkcji celu określonej na zmiennych decyzyjnych
OPTYMALNY WYBÓR ASORTYMENTU PRODUKCJI
Określić które wyroby i w jakich ilościach produkować aby nie przekroczyć posiadanych zasobów produkcji i zmaksymalizować przychód (lub zysk) z ich sprzedaży.
Posiadane dane:
n –lb wyborów produkowanych przez firmę
aij – zużycie i-tego środka produkcji na wytworzenie jednostki j-tego wyrobu i=1,…,r, j=1,…,n
bi - posiadany zasób i-tego środka produkcji
cj – cena lub zysk jednostkowy ze sprzedaży j-tego wyrobu
dj – min ilośc j-tego wyrobu jaką trzeba wyprodukować
ej- max ilośc j-tego wyrobu jaka można sprzedać
ZAPIS MATEMATYCZNY ASORTYMENTU PRODUKCJI
Niech xi –wielkość produkcji wyrobu i, x1=0; x2≥0; xn≥0
Funkcja celu: f(x1 ,…, xn)= c1x1+….+cnxn -> max
Ograniczenia związane ze środkami produkcji:
a11x1+ a12x2+…+ a1nxn≤b1a21x1+ a22x2+…+ a2nxn≤b2…..ar1x1+ar2x2+…+ arnxn≤br
ograniczenia związane z popytem: dj≤xj≤ej dla niektórych j.
PLAN PRODUKCJI
Plan produkcji, czyli decyzja co do wielkości produkcji każdego asortymentu: (x1 ,…, xn) jt rozwiązaniem dopuszczalnym, jeśli spełnia warunki ograniczające. Rozwiązanie optymalne będzie to (Lub będą te) spośród rozwiązań dopuszczalnych, dla którego (lub dla których) f-cja celu przyjmuje wartość max. Dopt wyznacza się metoda sympleks. Która będzie omówiona wkrótce po metodzie graficznej.
WARSTWICE
Graficzną metodę rozwiązywania zadań PL stosuje się wtedy gdy w zadaniu występują dwie zmienne decyzyjne. Wówczas łatwo wyznaczyć zbiór dopuszczalny D na płaszczyźnie. Posługując się warstwicami f-cji celu f można wyznaczyć pkt optymalny x0 w którym f(x0)=max (min) (o ile istnieje). Przypomnijmy pojęcie warstwicy f-cji f(x). Warstwicą f-cji f odpowiadają wartości z R nazywamy zbiór: Wz(f)={x Df: f(x)=z}.
Zbior Wz(f) jt zbiorem agrumentow f-cji f, dla których wartość f-cji f jt równa z.
WŁASNOŚCI PL
1. Jeżeli zbiór D jt niepusty i ograniczony, to zadanie PL posiada co najmniej jedną Dopt. 2. Jeżeli zbiór Dopt nie jt Ø, to przynajmniej jeden wierzchołek zbioru D należy do zbioru Dopt. 3. Jeżeli Dopt ≠ Ø albo funkcja celu jt funkcją nieograniczoną na zbiorze D, to zadanie PL nie posiada rozwiązania (jest zadaniem sprzecznym) 4. Zbiór Dopt decyzji dopuszczalnych jt zbiorem wypukłym, domkniętym, o skończonej lb wierzchołków (niekoniecznie ograniczony) 5. Zbiór Dopt jt również zbiorem wypukłym, domkniętym i o skończonej lb wierzchołków.
STANDARDOWA POSTAĆ ZADANIA PL
Zadanie programowania liniowego:
i=1nci...