MO Moduł 3

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
MO M3 Slajd1.png

MO M3 Slajd2.png

MO M3 Slajd3.png
Funkcja oceny jest tu liniowa, bo jest oczywiste, że dodanie do niej dowolnej liczby nie zmienia rozważań (zmienia wartość funkcji wyboru w punkcie minimalizującym, która jest oczywiście od tej liczby zależna, ale rozwiązaniem zadania jest punkt minimalizujący, który jest taki sam !).

MO M3 Slajd4.png
Zamiast „przy ograniczeniach” będziemy pisali

MO M3 Slajd5.png
Z rysunku wynika, że ograniczenie (c) nie jest potrzebne, oraz że zbiór dopuszczalny jest wielokątem. Linie poziomicowe funkcji liniowej to proste, zatem rozwiązanie leży w wierzchołku wielokąta (albo rozwiązań jest wiele i leżą na brzegu wielokąta, gdy poziomice są równoległe do stosownego ograniczenia).

MO M3 Slajd6.png
W przestrzeni zmiennych zadania liniowego optymalizacji
  • zbiór dopuszczalny to (hiper)wielościan,
  • miejscem geometrycznym stałej wartości funkcji celu jest (hiper)-płaszczyzna, a
  • rozwiązanie zadania (o ile istnieje) leży w jego wierzchołku albo rozwiązań jest wiele i leżą na brzegu wielościanu albo na jego ścianie.

MO M3 Slajd7.png
Na płaszczyźnie taki algorytm będzie działać, bo każdy wierzchołek ma tylko dwu sąsiadów, ale przy większej liczbie wymiarów będzie to bardzo powolne i nie wiadomo, czy algorytm się nie zapętli.

MO M3 Slajd8.png
W Polsce, nie bardzo wiadomo dlaczego, algorytm Dantziga nazywa się metodą sympleks, simpleksową, a nawet metodą sympleksów.

Używane w matematyce pojęcie sympleksu nie ma nic wspólnego z metodą Simplex.


MO M3 Slajd9.png

MO M3 Slajd10.png

MO M3 Slajd11.png

MO M3 Slajd12.png

MO M3 Slajd13.png

MO M3 Slajd14.png

MO M3 Slajd15.png
Dla równania
gdzie jest wektorem wymiarowym, a wektorem wymiarowym, macierzą bazową nazywa się każdą kwadratową nieosobliwą macierz , którą da się utworzyć z kolumn macierzy .

MO M3 Slajd16.png

MO M3 Slajd17.png

MO M3 Slajd18.png

MO M3 Slajd19.png

MO M3 Slajd20.png

MO M3 Slajd21.png

MO M3 Slajd22.png

MO M3 Slajd23.png

MO M3 Slajd24.png

MO M3 Slajd25.png
Główne problemy implementacyjne związane są z szybkością i dokładnością tego algorytmu. Najwięcej kłopotów jest w nim z odwracaniem kolejnych macierzy bazowych. Przypominamy, że numerycznie macierz odwraca się drogą faktoryzacji.

MO M3 Slajd26.png
Uznane pakiety komercyjne zawierające algorytm Simplex to np. CPLEX, MINOS, NAG, AMPL, MATLAB i Mathematica

MO M3 Slajd27.png

MO M3 Slajd28.png

MO M3 Slajd29.png

MO M3 Slajd30.png

MO M3 Slajd31.png

MO M3 Slajd32.png

MO M3 Slajd33.png