Zmienna jest wtedy zmienną luzu.
Rozwiązanie bazowe
Niech zadanie ma postać
gdzie macierz ma wierszy i kolumn.
Jeżeli można wybrać spośród kolumn macierzy podzbiór liniowo niezależnych kolumn, tworzących odwracalną macierz , to macierz tę nazywa się macierzą bazową.
Zmienne odpowiadające kolumnom macierzy nazywa się zmiennymi bazowymi, natomiast pozostałe zmienne są zmiennymi niebazowymi.
Przyjmując wszystkie zmienne niebazowe za równe zeru, otrzymujemy układ
Stąd
Jeżeli
otrzymane rozwiązanie jest bazowym rozwiązaniem dopuszczalnym.
Każde bazowe rozwiązanie dopuszczalne odpowiada wierzchołkowi obszaru rozwiązań dopuszczalnych, choć w przypadku degeneracji kilka baz może odpowiadać temu samemu wierzchołkowi.
Tabela sympleksowa
W klasycznej wersji algorytmu stosuje się tablicę sympleksową. Dla zadania
przy ograniczeniach
można rozpocząć od tablicy
Jeżeli wybrano bazę odpowiadającą macierzy , poprzez odpowiednie operacje na wierszach można otrzymać postać kanoniczną
Macierz jest macierzą jednostkową odpowiadającą zmiennym bazowym. Wektor zawiera wartości zmiennych bazowych dla aktualnego rozwiązania.
Jeżeli
aktualna baza opisuje rozwiązanie dopuszczalne.