Jest to jednak inny algorytm optymalizacyjny, przeznaczony do problemów optymalizacji bez ograniczeń lub z ograniczeniami obsługiwanymi w inny sposób, i nie jest związany z algorytmem sympleksowym programowania liniowego.
Historia
Algorytm sympleksowy został opracowany przez George'a Dant ziga w 1947 roku. Pierwsze zastosowania metody były związane między innymi z problemami planowania gospodarczego i wojskowego.
W kolejnych latach metoda stała się jednym z najważniejszych algorytmów programowania liniowego. Jej rozwój doprowadził między innymi do powstania różnych reguł wyboru zmiennej wchodzącej i wychodzącej z bazy oraz metod radzenia sobie z degeneracją i cyklami.
Współczesne implementacje wykorzystują zwykle zmodyfikowane wersje metody, takie jak metoda sympleksowa w postaci tablicowej lub metoda oparta na faktoryzacji macierzy bazowej. W praktycznych zastosowaniach stosuje się również metodę dwufazową i metodę wielkiej M do znajdowania rozwiązania bazowego dopuszczalnego.
Idea geometryczna
Zadanie programowania liniowego można przedstawić jako optymalizację funkcji liniowej na zbiorze określonym przez liniowe ograniczenia.