Badania operacyjne- należą do nauk o zarządzaniu
Def: Badanie operacyjne jest dziedzina nauki zajmująca się analiza celowych działalności (czyli operacji) , generowaniem i ocena ilościową różnych decyzji posługując się metodami matematycznymi, heurystycznymi i symulacja komputerową.
Zadania decyzyjne: w wielu różnych sytuacjach podejmujemy decyzję -sytuacje te nazywamy sytuacjami decyzyjnymi, a osobę podejmująca te decyzje decydentem. Często decydent działa w określonych warunkach, które maja istotny wpływ na podejmowane decyzje i nie pozwalają na wybór decyzji dowolnej.Warunki te nazywamy warunkami ograniczającymi, które określają decyzje dopuszczalne ze względu na cele jakie stawia sobie decydent, jedne z decyzji (spośród dopuszczalnych) mogą być lepsze lub gorsze , stad wynika problem wyboru decyzji najlepszej zwanej decyzją optymalną.
Wybór decyzji optymalnej wymaga przyjęcia określenia „lepszy” lub „gorszy”. Kryterium te nazywamy funkcją celu. Zazwyczaj decyzje dotyczą pewnych zmiennych x 1,x2,…….xk zwane zmienne decyzyjne.
Decyzją jest konkretna wartość zmiennych decyzyjnych.
Decyzja x=( x 1,x2,…….xk ) x 1↔wartości decyzyjne zmiennej X i dla porównania dwóch decyzji
x = (x 1,x2,…….xk) i y=(y1,y2,…….yk) wprowadzamy funkcje celu F(x 1,x2,…….xk) i mówimy , że
x lepsze od y F(x) > F(y) maxymalizacja funkcji celu
x lepsze od y F(x) < F(y) minimalizacja funkcji celu
warunki ograniczające
f1 ( x 1,x2,…….xk ) =0
f2 ( x 1,x2,…….xk ) =0 (1)
-----------------------------
fm ( x 1,x2,…….xk ) =0
ogólna postać zagadnienia decyzyjnego :
x*= x* 1,x*2,…….x*k F(x) = max /(min) F(x) i spełniałoby ograniczenia (1)
Zagadnienia programowania liniowego:
jeżeli w zadaniu decyzyjnym funkcja celu jest funkcja liniową
wszystkie ograniczenia sa równościami lub nierównościami liniowymi
zmienne decyzyjne sa funkcją ciągła i nieujemną x1≥0 to takie funkcje nazywamy funkcjami programowania liniowego
ogólna postać zadania programowania liniowego
X = (x 1,x2,…….xn)-wektor zmiennych decyzyjnych
F(x)= c1x 1+ c2x2,……. cnxn → max (min) - funkcja celu
Zagadnienia decyzyjne oraz zadania decyzyjne
Def: Problem czyli zagadnienie operacyjne nazywamy opis słowny konkretnej sytuacji decyzyjnej . Matematycznym sformalizowaniem problemu decyzyjnego czyli inaczej budowaniem modelu matematycznego nazywamy zapis zagadnienia decyzyjnego w języku matematycznym
budując model matematyczny dla konkretnej sytuacji ustalić jakie wielkości powinny być wyznaczone czyli zbiór (x 1,x2,…….xn)- zmiennych decyzyjnych
jakie wielkości są dane czyli określić parametry modelu
3) jakie ograniczenia musi spełniać decyzja dopuszczalna (sformułować warunki ograniczające)
4) ustalić cel jaki chce osiągnąć decydent
Model matematyczny zagadnienia decyzyjnego nazywamy zadaniem decyzyjnym
Ogólna postać zadania decyzyjnego F(x) → max (min) x↔D D- przestrzeń rozwiązań dopuszczalnych
F-funkcja celu , x-zbiór zmiennych decyzyjnych
Ogólna postać zadania programowania liniowego
1)postać standardowa
c∙x→ max c∙x→ max
Ax<= b Ax>=b
x>=0 x<=0
2) Zadanie dualne
Załóżmy, że mamy zadanie w postaci standardowej nazywamy zadaniem pierwotnym z każdym zadaniem pierwotnym związane jest drugie zadanie nazywane dualnym y=(y1,y2,…….ym )
Funkcja celu L(y)= b1y1+ b2y2+ bmym→ min
Warunki ograniczające
a11y1+ a21y2+……+ am1ym>=c1
y1>=0, y2>=0, ym>=0,
miedzy zadaniem pierwotnym a dualnym zachodzi relacja :
1) w zadaniu dualnym tyle zmiennych ile w zadaniu pierwotnym
2)w zadaniu dualnym tyle warunków ograniczających „n” ile zmiennych decyzyjnych w pierwotnym
3) jeżeli zadanie pierwotne jest(max) to zadanie dualne (min) i na odwrót
4) jeżeli w pierwotnym warunki ograniczające są<= to w dualnym>=
5) współczynniki celu (c1,c2, cn ),funkcja celu zadania pierwotnego są wyrazami wolnymi w zadaniu dualnym
6)wyrazy wolne w zadaniu pierotnym (b1,b2,…….bm ) sa współczynnikami funkcji celu zadania dualnego
7) macierz współczynników lewych stron w zadaniu dualnym jest transpozycją odpowiednich macierzy zadania pierwotnego
Algorytm SIMPLUS 17-03-2006
Zbiory wypukłe w przestrzeni Rn
Def: mówimy , ze podzbiór x<= Rn jest wypukłym jeżeli dla dowolnych x należy doX. Y do Y oraz L>=0 B>= 0 L+B=1 L(x) +B)y) należą do X
Def: mówimy , ze punkt W=(w1,w2, wn) podzbiór Ex jest wierzchołkiem jeżeli nie istnieje dodatnie L>0, B>0 L+B=1 oraz w x nie istnieje dwóch różnych punktów x,y takich aby wektor w=Lx +By nie istnieje W będzie wierzchołkiem wtedy gdy nie należy do wnętrza , żadnego odcinka łączącego dwa różne punkty zbioru. Zbiór wypukły ma skończona liczbę wierzchołków nazywa się wielomianem wypukłym oznaczanym przez Π1={x=(x 1,x2,…….xn }
Liczba wierzchołków wielościanów D jest skończona , zatem na podstawie twierdzenia (funkcja celu osiąga wartość optymalna w wierzchołku zbioru D , wierzchołkiem wielościanu wypukłego D) można zaproponować następująca procedurę określenia rozwiązania optymalnego : przeglądając wszystkie wierzchołki oraz obliczając wartość funkcji celu w tych wierzchołkach można określić wierzchołki w których wartość jest optymalna . Realizacja tego algorytmu potrzebuje ustalenia postaci rozwiania dopuszczalnego , które będzie wierzchołkiem D.
Gry dwuosobowe (macierzowe) 31-03-2006
Matematyczna dyscyplina , która zajmuje się badaniami optymalnych decyzji w sytuacjach gdy nie wiadomo jaki będzie stan naszego otoczenia lub jaką decyzje podejmie konkurent ma nazwe „teoria gier” Gra dwóch graczy niezależnie od siebie (jednocześnie) podejmując decyzję Gracz A ma do wyboru „m decyzji” Gracz B ma do wyboru „n decyzji” A→B płaci kwotę Cij
Wygrana gracza B jest jednocześnie przegrana gracz A i odwrotnie i oznaczamy
Cij> 0 to płaci A Cij<0 to płaci B
Macierz złozona z elementów Cij wypłat
Def: każda decyzję i Należy do I i j należy do J Gra macierzowa to trójka G={I,J,C}
„O” O→A
„R” R→A O -1 1 1
„O” R→B R 1 -1 1
„R” O→B -1 -1
Optymalne strategie czyste z punktu widzenia B decyzje j
Wybierając czyste strategie j gracz B zapewnia sobie minimum wygranej Cij
Ponieważ B ma możliwość wyboru j z J to wybierze taka strategię , aby ta minimalna wygrana była jak najwieksza to gwarantuje graczowi B wygrana w wielkości V=max min Cij j należy J
V=min-dolna cena gry
W sposób podobny ocenia gracz A minimalna gwarantowana przegrana dla gracza A
Max Cij j należy J to trzeba wybrać V min(max) Cij górna granica gry
Def: Jeżeli gra ma punkt równowagi natomiast i* należy do I i j* należy do J tak , ze
i*-czysta strategia gracza A
j*-czysta strategia gracza B,
mówimy wówczas , ze gra ma rozwiązania w czystych strategiach , a znaczy to , ze A musi zawsze wybierać decyzje z i* , a B z j* wybór innej strategii to wynik gorszy
Def; Punkt ( i*,j*) nazywamy punktem siodłowym macierzy C jeżeli Ci*, j<=Ci*j*<=Ci,j* dla dowolnych i=1,2, m ; j=1,2,..n
Twierdzenie Gra macierzowa G ma rozwiązanie w czystych strategiach wtedy i tylko wtedy , gdy macierz wypłat C ma punkt siodłowy. Jeżeli (i*,j*) -punkt siodłowy będzie punktem równowagi .
Optymalne strategie mieszane
Punkt równowagi nie koniecznie musi istnieć , a to oznacza , ze nie zawsze gracze mogą wybrać strategie czyste , wtedy stosujemy pojęcie strategii mieszanych
Strategie mieszane gracza A nazywamy wektor x=(x 1,x2,…….xn) x1>=0; x2>=0; xn>=0;
x 1+x2,…….xn=1
x 1,-traktujemy jako prawdopodobieństwo wyboru przez gracza
analogicznie dla gracza B y=(y 1,y2,…….yn) y1>=0; y2>=0; yn>=0;
y 1+y2,…….yn=1
Zadanie programowania liniowego - zadania dualne dla gracza A min dla gracza B max
Optymalizacja nieliniowa 21-04-2006
Def: zadanie decyzyjne nazywamy nieliniowym jeżeli funkcja celu lub chociaż jeden z warunków ograniczających jest funkcja nieliniowa.
Typy zadań nieliniowych :
to zadanie programowania wypukłego spełniające warunki:
- minimalizujemy wypukła funkcję
Lub
-maxymalizujemy punkcje wklęsłą
2) gdzie zbiór rozwiązań dopuszczalnych jest zbiorem wypukłym -programowanie wypukłe
Zadania programowania nie wypukłego:
Wśród zadań programowania wypukłego wyróżniamy zadania programowania kwadratowego gdzie:
-funkcja celu to funkcja kwadratowa
-wszystkie ograniczenia sa liniowe
Zbiór rozwiązań będzie wypukłym wielościanem
Metoda mnożników Lagrag`a
Realizacje tej metody można podzielić na dwa etapy :
1) sprawdzamy czy funkcja celu X ma extremum bezwarunkowe , sprawdzenie to polega na tym , ze obliczamy pierwsze pochodne funkcji celu (punkty krytyczne) względem poszczególnych zmiennych decyzyjnych i przyrównujemy te pochodne do zera , w ten sposób uzyskuje się punkty krytyczne , następnie dokonuje się analizy czy w punktach krytycznych występuje extremum czy nie .
2) Jeżeli w punkcie krytycznym występuje extremum i spełnia warunki ograniczające i warunki brzegowe to mamy rozwianie zadania programowania nieliniowego (ZPN).
3) jeżeli extremum bezwarunkowe nie spełnia warunków ograniczających to wprowadzamy mnożniki Lagrangea f(x)↔L(x,λ) ; x=(x 1,x2,….xn) ; λ=(λ 1,λ 2,….λ m )
3) L(x,λ)=f(x)+λ1 g1(x)+ λ2 g2(x)…….. λm gm(x)
W ten sposób zastepujemy określenie extremum warunków funkcji f(x)↔określeniem extremum bezwarunkowego funkcji Li(x,λ) w tym celu obliczamy pochodne cząstkowe funkcji Li(x,λ) względem poszczególnych zmiennych decyzyjnych x 1,x2 oraz względem mnożników Lagrangea .
Następnie przyrównujemy te pochodne do zera