Podstawowe własności zadania programowania liniowego; metoda SIMPLEX



Liniowe zadania optymalizacji



Zadanie programowania liniowego



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



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



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


W przestrzeni zmiennych zadania liniowego optymalizacji



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.


Algorytm Simplex




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.





Programowanie liniowe







Idea działania algorytmu Simplex





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














Faza algorytmu Simplex





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.


Algorytm Simplex - implementacja




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


Lepszy niż Simplex ?





Droga "na skróty"





Algorytmy (metody) punkt wewnętrznego







Algorytm poszukujący rozwiązania






Oprogramowanie dla zadań liniowych