Zadanie programowania liniowego w postaci standardowej polega na minimalizacji funkcji:
Przy zadanych ograniczeniach (*):
(i)
(ii);;;;;;
W praktyce występują też ograniczenia w postaci nierówności które można jednak sprowadzić do równości wprowadzając dodatkowe zmienne (tzw. zmienne dopełniające), z odpowiednim współczynnikiem (-1 lub 1).
Ograniczenia (*) wyznaczają w wielościan, tzw. sympleks, zaś wartość minimalna funkcji F może być osiągnięta jedynie w wierzchołkach tego sympleksu (jeżeli w więcej niż jednym wierzchołku funkcja F ma wartość minimalną, to na odcinku łączącym te wierzchołki też przyjmuje wartość minimalną). Współrzędne wierzchołków sympleksu można uzyskać rozwiązując układ równań (ii) dla M współrzędnych różnych od 0 (tzw. współrzędnych bazowych) i pozostałych N-M współrzędnych równych 0.
Algorytm sympleksu można podzielić na dwie fazy: w pierwszej znajdywane jest dowolne rozwiązanie dopuszczalne (tzn. takie w którym wartości M niezerowych zmiennych są nieujemne). W kolejnej fazie rozwiązanie to jest konsekwentnie poprawiane poprzez odpowiednią podmianę wektorów tworzących bazę (inny wybór współrzędnych bazowych) - sprawdzanie kolejnych wierzchołków sympleksu. Do osiągnięcia punktu optymalnego potrzeba co najwyżej N takich podmian.
Jedną z metod znalezienia rozwiązania dopuszczalnego jest rozwiązanie następującego problemu pomocniczego który też jest zadaniem programowania liniowego (jednak z danym rozwiązaniem dopuszczalnym) z funkcją celu postaci:
gdzie - wektor zmiennych sztucznych (i równocześnie początkowy wektor zmiennych bazowych generujący dopuszczalne rozwiązanie problemu pomocniczego).
i ograniczeniami:
,
, gdzie IM -macierz jednostkowa.
Oczywiście wartość minimalna funkcji G wynosi 0 (wystarczy że pozbędziemy się z bazy wszystkich zmiennych sztucznych) gdy istnieje rozwiązanie oryginalnego problemu LP. Rozwiązanie problemu pomocniczego jest równocześnie początkowym rozwiązaniem problemu oryginalnego (wymaganym w II etapie).
Oznaczenia:
Po fazie I (i dalej w każdej iteracji) otrzymujemy nasze zadanie w postaci kanonicznej:
gdzie , wektor - to wektor zmiennych bazowych
która wyznacza następujące rozwiązanie dopuszczalne:
i
Algorytm:
jeżelito zakończ, bieżące rozwiązanie jest optymalne (minimum funkcji to )
znajdź q takie, żejest najmniejsze
(podzbiór indeksów wierszy)
jeżeli to zakończ, rozwiązanie jest nieograniczone (dowolnie małe)
wybierz z W taki numer wiersza p żejest minimalne
wyrzuć z bazy zmienną o indeksie q, dodaj do bazy zmienną o indeksie p i doprowadź układ do postaci kanonicznej (metodą eliminacji)
przejdź do pkt. 1