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, że
jest
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