To tylko jedna z 47 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Wstęp Kilka słów o przedmiocie Tematem zajęć będą Metody Optymalizacji a nie same Badania Operacyjne. Ponieważ większość z tych metod powstała na potrzeby Badań Operacyjnych, pozostaniemy przy tej drugiej nazwie. Zajmować będziemy się metodami optymaliza cji , służącymi do rozwiązywania problemów decyzyjnych . Program zajęć obejmuje zapoznanie się z metodami rozwiązywania następujących problemów
Problemy i modele decyzyjne Każdy system działania rodzi tzw. sytuacje decyzyjne . Sytuacją decyzyjną nazywać będziemy ogół czynników, które wyznaczają postępowanie decyzyjne podmiotu podejmującego decyzję, zwanego na ogół decydentem . Następstwem prawie każdej sytuacji decyzyjnej jest pewien problem decyzyjny, którego rozwiązanie wyznacza racjonalną decyzję. Problem decyzyjny można zdefiniować następująco:
istnieje cel lub zbiór celi które należy osiągnąć
istnieją alternatywne sposoby dojścia do celu optymalny sposób lub kombinacja sposobów nie jest oczywista.
Badania operacyjne (ang. operational research) należą do tych dziedzin wiedzy, które zajmują się metodami rozwiązywania problemów decyzyjnych, wynikających z potrzeb racjonalnej działalności człowieka.
Rozwiązanie problemu decyzyjnego za pomocą badań operacyjnych jest procedurą składającą się z następujących etapów:
rozpoznanie sytuacji decyzyjnej i wynikającego z niej problemu decyzyjnego
budowa modelu decyzyjnego
rozwiązanie problemu decyzyjnego (metodą badań operacyjnych lub programowania matematycznego)
ocena poprawności i realności uzyskanych rozwiązań oraz ewentualna weryfikacja modelu decyzyjnego
przedstawienie rozwiązań decydentowi i ostateczne przygotowanie decyzji.
Nie każdy problem decyzyjny może być rozwiązany za pomocą badań operacyjnych. Rozwiązać można jedynie problemy dobrze ustrukturalizowane, dające się przedstawić w postaci modelu matematycznego. Nie da się rozwiązać metodami badań operacyjnych problemów nieustrukturalizowanych i słabo ustrukturalizowanych.
Budowa modelu decyzyjnego jest jednym z trudniejszych etapów w procedurze podejmowania decyzji. W praktyce najwięcej problemów sprawia:
wyróżnienie istotnych cech sytuacji decyzyjnej i ujęcie ich w modelu
modelowanie - tę samą sytuację często można odwzorować za pomocą kilku modeli.
Od postaci sformułowanego modelu zależą szanse jego efektywnego rozwiązania - stąd przy formułowaniu modelu należy mieć rozeznanie co do metod, którymi można go rozwiązać. Model decyzyjny
(…)
…
Wprowadzenie
Do tej pory zakładaliśmy, że zagadnienie programowania liniowego ma początkowe bazowe rozwiązanie dopuszczalne (jest macierz jednostkową, która może być wykorzystana jako baza początkowa). Istnieje jednak wiele zagadnień, które nie mają początkowego bazowego rozwiązania dopuszczalnego. By je uzyskać należy dodać do wyjściowego problemu zmienne sztuczne (ang. artificial variables), które pozwolą…
… - rozwiązanie jest nieograniczone gdy X nie jest zwarte
jest jedno skończone rozwiązanie
jest wiele skończonych rozwiązań
nie ma żadnego rozwiązania - X jest puste.
Własności zadania programowania liniowego
Kombinacja liniowa wektorów, wektory liniowo niezależne (cel: baza)
Wektor x∈Rn nazywamy kombinacją liniową wektorów x1,x2,...,xk∈Rn jeżeli:
(2.1)
Przykład: wektor jest kombinacją liniową wektorów…
…],...,[0,0,...,1] jest bazą w Rn. !!! Dany jest układ równań liniowych Ax=b. Macierz A jest typu m x n i zakładamy że m<=n. Niech AB jest bazą zbioru kolumn macierzy A, xB niech będzie wektorem zmiennych stojących przy kolumnach bazowych (zmienne bazowe), xR wektorem zmiennych stojących przy kolumnach niebazowych (zmienne niebazowe lub wtórne). Układ równań liniowych możemy przedstawić teraz w postaci ABxB…
… reprezentuje bazowe rozwiązanie dopuszczalne zadania programowania liniowego.
Uogólnienie dotychczasowych 4 własności:
TWIERDZENIE: Punkt x jest punktem wierzchołkowym zbioru X wtedy i tylko wtedy, gdy w kombinacji liniowej wektorów niezależnych Pj (2.5)
współczynniki xj są dodatnie.
WNIOSKI:
Każde bazowe rozwiązanie dopuszczalne jest punktem wierzchołkowym zbioru X
Istnieje punkt wierzchołkowy zbioru X…
... zobacz całą notatkę
Komentarze użytkowników (0)