Praca pochodzi z serwisu www.e-sciagi.pl <<<>>> Zacznij zarabiać http://partner.e-sciagi.pl
Badania Operacyjne Wykład 02 2004-10-18
BADANIA OPERACYJNE zajmują się teorią podejmowania decyzji i rozwiązywania problemów
Ogólne sformułowanie zagadnienia programowania matematycznego:
Z problemem wyboru decyzji optymalnej ze względu na wybrany cel działania mamy do czynienia, gdy:
Ø istnieje ograniczona swoboda w podejmowaniu decyzji, dlatego też każda decyzja, która uwzględnia przyjęte ograniczenia będzie nazwana DECYZJĄ DOPUSZCZALNĄ
Ø istnieje możliwość podjęcia więcej niż jednej decyzji dopuszczalnej
Ø istnieje kryterium pozwalające ocenić stopień realizacji celu przez dowolną decyzję dopuszczalną. Decyzja dopuszczalna najlepiej realizująca przyjęty cel działania nazywa się DECYZJĄ OPTYMALNĄ
Podstawowe elementy modelu matematycznego dotyczącego problemu wyboru decyzji optymalnej i odzwierciedlających wybraną sytuację decyzyjną to:
a) zespół k – zmiennych x1,x2,…,xk – zmienne decyzyjne
Każdy zestaw wartości x1,x2,…,xk jest opisem ilościowym dowolnej decyzji, a zatem dla dowolnej decyzji wyznaczamy X = (x1,x2,…,xk), a w interpretacji geometrycznej jest to pewien punkt w przestrzeni k – wymiarowej
(x1,x2,…,xk) Є Rk
b) Dany jest zbiór D decyzji dopuszczalnych ograniczających swobodę podejmowania decyzji. Oznacza to, że nie każdy punkt przestrzeni k – wymiarowej reprezentuje decyzję dopuszczalną. Zbiór D jest podzbiorem zbioru Rk. D nie jest zbiorem pustym.
c) Dana jest funkcja f(x1,x2,…,xk) = f(x)
Wartość funkcji wyznaczona dla dowolnej decyzji dopuszczalnej mierzy stopień realizacji celu przez tą decyzję. Dla dwóch różnych decyzji dopuszczalnych x1,x2 , x1≠x2, ta z nich lepiej realizuje przyjęty cel działania, dla której wartość funkcji jest taka sama, będziemy je traktować równorzędnie. Funkcja f ze względu na rolę jaką pełni w modelu matematycznym nazywa się funkcją celu albo funkcją kryterium.
Przyjmując powyższe założenia, za decyzją optymalną tzn. najlepiej realizującą przyjęty cel działania, uznamy tą spośród decyzji dopuszczalnych, dla której wartość funkcji celu jest max w zbiorze D.
dla
Jeżeli zbiór decyzji dopuszczalnych D zapiszemy w formie układu nierówności, jaki powinny spełniać wartości zmiennych decyzyjnych:
h1 (x1,x2,…,xk) ≤ b1
h2 (x1,x2,…,xk) ≤ b2
hm (x1,x2,…,xk) ≤ bm
To wtedy problem wyboru decyzji optymalnej będziemy nazywać ZAGADNIENIEM PROGRAMOWANIA MATEMATYCZNEGO. A zatem zagadnienie programowania matematycznego, to każdy problem wyboru decyzji optymalnej, którego model matematyczny można zapisać, wyznaczyć wektor X=( x1,x2,…,xk)
f(x1,x2,…,xk) » max
Maksymalizujemy funkcję celu przy warunkach ograniczających
hi (x1,x2,…,xn) ≤ bi i = (1,…,m)
Badania Operacyjne Wykład 03 2004-10-25
PROGRAM LINIOWY:
X = (x1, x2,…, xk)
f(X) = c1x1 +c2x2 +…+ ckxk » max
przy warunkach ograniczających:
a11x1 + a12x2 + … + a1kxk ≤ b1 (i=1,…,m)
a21x1 + a22x2 + … + a2kxk ≤ b2 xj ≥ 0 (j=1,…,n)
……………………………………………….
am1x1 + am2x2 + … + amkxk ≤ bm
xj ≥ 0 (j=1,…,n)
CT » max
Ax ≤ b
x ≥ 0
Jest to postać kanoniczna. Komplementarną formą jest postać standardowa.
POSTAĆ STANDARDOWA charakteryzuje się tym, że:
Ø warunki graficzne zapisane są w postaci równań
Ø wyrazy wolne poszczególnych warunków ograniczających są nieujemne
Ø warunki nieujemności są pełne tzn. dotyczą wszystkich zmiennych decyzyjnych
f(X) = c1x1 +c2x2 +…+ cnxn » max
a11x1 + a12x2 + … + a1nxn = b1 b1 ≥ 0 (i=1,…,m)
a21x1 + a22x2 + … + a2kxk = b2 b2 ≥ 0 bi ≥ 0
…………………………………………. xj ≥ 0 (j=1,…,n)
am1x1 + am2x2 + … + amnxn = bm bm ≥ 0
CT » max Ax ≤ b x ≥ 0 b ≥ 0 C,X Є Rn Amxn b Є Rm
METODY WYZNACZANIA ROZWIĄZANIA ZADANIA PROGRAMOWANIA LINIOWEGO:
1) metoda graficzna (geometryczna)
2) program dualny
3) metoda Simplex
Warunki stosowalności:
Metodę 1) można stosować tylko wtedy, jeśli w modelu znajdują się 2 zmienne decyzyjne (co najwyżej 3 zmienne). Jeśli w modelu programowania liniowego znajduję się więcej zmiennych decyzyjnych niż 2 (lub 3), natomiast liczba warunków ograniczających wynosi 2 (lub 3), to można wyznaczyć rozwiązanie takiego zadania programowania liniowego korzystając z zapisu programu dualnego w stosunku do programowania pierwotnego.
Metoda Simplex, która jest metodą uniwersalną, polegającą najogólniej biorąc na wyznaczeniu wstępnego rozwiązania bazowego, a następnie poprawianiu tego rozwiązania w kolejnych krokach iteracyjnych aż do uzyskania rozwiązania optymalnego, można stosować do wyznaczenia rozwiązania praktycznie rzecz biorąc każdego modelu PL (za wyjątkiem przypadków degenerowanych)
PROGRAM DUALNY:
Program pierwotny Program dualny
zmaksymalizować zminimalizować
przy warunkach ograniczających: przy warunkach ograniczających:
(i=1,…,m) (j=1,…,n)
(j=1,…,n) (i=1,…,m)
Program dualny jest w pewnym sensie transpozycją programu pierwotnego, a charakter tej transpozycji jest następujący:
a) j – ta kolumna współczynników stojących przy zmiennych decyzyjnych w warunkach ograniczających PP staję się i – tym wierszem współczynników w warunkach ograniczających PD
b) wektor ograniczeń zagadnienia pierwotnego przejmuje rolę współczynników funkcji celu w PD
c) współczynniki funkcji celu PP stają się wektorem wyrazów wolnych w PD
d) rodzaj optymalizacji oraz kierunki nierówności w warunkach ograniczających są przeciwne względem siebie w obu zagadnieniach
TWIERDZENIE 1
Jeżeli zagadnienie pierwotne i dualne mają rozwiązania dopuszczalne a stanowi rozwiązanie optymalne zagadnienia pierwotnego, natomiast stanowi rozwiązanie optymalne zagadnienia dualnego, to , co oznacza, że wartość funkcji celu zagadnienia pierwotnego i dualnego jest taka sama.
TWIERDZENIE 2
Jeżeli program pierwotny (dualny) ma skończone rozwiązanie optymalne to adekwatnie do niego program dualny (pierwotny) ma również rozwiązanie optymalne o tej samej wartości funkcji celu.
Badania Operacyjne
Wykład 04 2004-11-08
PROGRAM DUALNY – ZADANIE
Program Pierwotny:
x1,…,x4 ≥ 0
warunki ograniczające:
x1+2x2+1,5x3+6x4 ≤ 90000
2x1...
stary_hipis