MO_3_podstawowe

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.

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 $b$ wektorem $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.