Badania operacyjne w pigułce

Wstęp notatki wygenerowany automatycznie

...Wyznaczanie rozwiązania: - metody dokładne - metody przybliżone - metody symulacyjne (nie będziemy ich omawiad na tym przedmiocie, będą na 3cim roku) 1. Metody dokładne: - znajdują rozwiązanie optymalne - bardzo kosztowne obliczeniowo, zarówno w zakresie czasu działania jak i wymaganej pamięci Przykłady: - metoda podziału i ograniczeo (B&B) - metoda oparta o schemat programowania dynamicznego (PD) - metody oparte na programowaniu całkowitoliczbowym (PLC) - metody oparte na programowaniu binarnym (PLB) - metody subgradientowe 2. Metody przybliżone: - znajdują rozwiązanie przybliżone - zwykle zorientowane na konkretny problem - jakośd metod przybliżonych można oceniad pod względem złożoności obliczeniowej algorytmu lub dokładności przybliżenia Algorytmy można podzielid na dwie klasy: 1. Algorytmy konstrukcyjne: - generują pojedyncze rozwiązanie lub ustalony z góry podzbiór rozwiązao o niewielkiej liczności, z którego następnie wybierane jest najlepsze rozwiązanie w sensie postawionej funkcji celu - konstrukcja rozwiązania polega na dołączaniu kolejnych elementów rozwiązania, nie mając początkowych ustaleo 2. Algorytmy poprawy: - rozpoczynają swoje działanie dla pewnego rozwiązania, uzyskanego losowo lub przy użyciu algorytmu konstrukcyjnego - w kolejnych iteracjach następuje poprawianie tego rozwiązania Dualnośd Rozw. optymalne zadania pierwotnego można odtworzyd w oparciu o twierdzenie Dantzing-Ordena Twierdzenie (Dantzing – Orden): Jeżeli dla rozwiązao optymalnych zadania pierwotnego i dualnego jte ograniczenie zadania dualnego jest spełnione jako nierównośd to j-ta zmienna w zadaniu pierwotnym jest równa zeru (xj = 0). Jeżeli ita zmienna dualna yi jest dodatnia, to i-te ograniczenie w zadaniu pierwotnym jest równością. METODA SIMPLEX Twierdzenie Funkcja celu f(x) = cx zagadnienia programowania liniowego osiąga wartośd minimalną w punkcie wierzchołkowym zbioru rozwiązao dopuszczalnych 1. Utworze...

Podobne notatki