MO Moduł 3

From Studia Informatyczne

Enlarge

Enlarge

Enlarge
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 !).

Enlarge
Zamiast „przy ograniczeniach” będziemy pisali \;\;\mathrm {p.o.}

Enlarge
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).

Enlarge
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.

Enlarge
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.

Enlarge
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.


Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge
Dla równania
Ax = b,
gdzie x jest wektorem n wymiarowym, a b wektorem p wymiarowym, macierzą bazową nazywa się każdą kwadratową nieosobliwą macierz B, którą da się utworzyć z p kolumn macierzy A.

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge
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.

Enlarge
Uznane pakiety komercyjne zawierające algorytm Simplex to np. CPLEX, MINOS, NAG, AMPL, MATLAB i Mathematica

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge