W typowym przypadku zbiór ten jest wielościanem wypukłym.
Przykładowo problem maksymalizacji
przy ograniczeniach
wyznacza pewien wielokąt będący obszarem rozwiązań dopuszczalnych.
Jeżeli problem ma rozwiązanie optymalne i zbiór rozwiązań dopuszczalnych jest niepusty, to w przypadku ograniczonego optimum istnieje co najmniej jeden wierzchołek zbioru dopuszczalnego, w którym funkcja celu osiąga wartość optymalną.
Algorytm sympleksowy rozpoczyna więc od określonego wierzchołka i przechodzi wzdłuż jednej z jego krawędzi do sąsiedniego wierzchołka, w którym funkcja celu ma nie gorszą wartość. Proces jest powtarzany aż do znalezienia wierzchołka optymalnego.
Nie jest konieczne odwiedzanie wszystkich wierzchołków wielościanu. Algorytm wybiera kolejne wierzchołki na podstawie współczynników funkcji celu i ograniczeń.
Sformułowanie zadania
Standardowe zadanie maksymalizacji programowania liniowego można zapisać w postaci
przy ograniczeniach
gdzie: jest macierzą współczynników ograniczeń, jest wektorem zmiennych decyzyjnych, jest wektorem prawej strony ograniczeń, jest wektorem współczynników funkcji celu.
Ograniczenia typu nierówności można przekształcić do tej postaci poprzez wprowadzenie dodatkowych zmiennych, zwanych zmiennymi luzu.
Przykładowo nierówność
może zostać zastąpiona równaniem