Slajd35 4

Metoda simpleks

Uniwersalną metodą rozwiązywania programów liniowych jest algorytm simpleks. Istota algorytmu simpleks polega na badaniu kolejnych rozwiązań bazowych (rozwiązań dopuszczalnych) programu liniowego w postaci kanonicznej w taki sposób, że:

>    znajdujemy (dowolne) rozwiązanie bazowe programu,

>    sprawdzamy czy jest ono optymalne,

>    jeżeli dane rozwiązanie nie jest optymalne, konstruujemy następne rozwiązanie bazowe lepsze (lub przynajmniej nie gorsze od poprzedniego).

Postępowanie kończy się w momencie stwierdzenia, że aktualne rozwiązanie bazowe jest optymalne, tzn. nie można już go poprawić. Algorytm simpleks jest więc procedurą iteracyjną (etapową), a wyniki poszczególnych etapów (iteracji) zestawia się w kolejnych tablicach simpleks.