BADANIA OPERACYJNE - ĆWICZENIA
1 Wstęp Zaliczenie zajęć na podstawie zdobytej ilości punktów:
w ciągu semestru odbędą się dwa kolokwia (zapowiedziane z conajmniej 2 tygodniowym wyprzedzeniem). Zaliczenie pozytywne - uzyskanie powyżej 50% punktów. W przypadku niezaliczenia kolokwium, w terminie do dwóch tygodni od ogłoszenia wyników odbędzie się kolokwium poprawkowe. By zaliczyć kolokwium poprawkowe trzeba zdobyć co najmniej 60% punktów (przy niezmienionym poziomie trudności). Otrzymuje się wtedy (potrzebne do końcowej oceny) dokładnie 50% punktów właściwego kolokwium. dodatkowe punkty za aktywność na zajęciach
punkty karne za nieusprawiedliwiona nieobecność
na końcu semestru istnieje możliwość podwyższenia oceny (maksymalnie o 1 stopień w górę) po rozmowie ustnej (zaliczenie całego materiału); w wyniku rozmowy ocena może też zostać obniżona
Egzamin - wymagane wiadomości z ćwiczeń i wykładów Problem programowania liniowego
programowanie dynamiczne
Definicja problemu
TAK
WPD z własnością markowa
TAK
Metoda sympleks + przykład
TAK
zasada optymalności
TAK
Odmiany metody sympleks
NIE
Algorytm
TAK
Unikanie degeneracji
NIE
zastosowanie dla problemów ciągłych i dyskretnych
Oprogramowanie
TAK
Dualność i interpretacja
TAK
Niesimpleksowe podejścia
TAK
Problem programowania dyskretnego
problem programowania nieliniowego
Metoda płaszczyzn odcinajacych
TAK
TW. Kuhna-Tuckera
TAK
Metoda podziału i ograniczeń
TAK
TW. Lagrange'a
TAK
Metaheurystyki
TAK
przegląd i klasyfikacja metod
TAK
Znalezione błędy (zaznaczono na czerwono)
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 optymalizacji, służącymi do rozwiązywania problemów decyzyjnych. Program zajęć obejmuje zapoznanie się z metodami rozwiązywania następujących problemów
(…)
… 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+ARxR=b.
Zbiory wypukłe, sympleks
Wypukłą…
… 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 optymalizacji, 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 (Siudak)
Każdy system działania rodzi tzw. sytuacje…
…:
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…
… 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 ponieważ: Wektor x∈Rn nazywamy wypukłą kombinacją…
….
Baza, rozwiązanie bazowe (cel: zadanie PL a baza)
Bazą zbioru S ⊂ Rn jest zbiór liniowo niezależnych wektorów, takich że wszystkie inne wektory należące do S da się przedstawić jako kombinację liniową wektorów bazy.
Dowolny zbiór n liniowo niezależnych wektorów należących do Rn jest bazą w przestrzeni Rn .
Zbiór n wektorów jednostkowych [1,0,...,0],[0,1,...,0],...,[0,0,...,1] jest bazą w Rn. !!! Dany…
…
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ą…
... zobacz całą notatkę
Komentarze użytkowników (0)