Programowanie liniowe (metoda sympleks)

Zadanie programowania liniowego (LP):

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).

Idea algorytmu symplex:

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.

I etap:

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 I_M -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).

II etap:

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:

1. jeżelito zakończ, bieżące rozwiązanie jest optymalne (minimum funkcji to )

2. znajdź q takie, żejest najmniejsze

3. (podzbiór indeksów wierszy)

4. jeżeli to zakończ, rozwiązanie jest nieograniczone (dowolnie małe)

5. wybierz z W taki numer wiersza p żejest minimalne

6. wyrzuć z bazy zmienną o indeksie q, dodaj do bazy zmienną o indeksie p i doprowadź układ do postaci kanonicznej (metodą eliminacji)

7. przejdź do pkt. 1