Algorytm sympleksowy

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Algorytm sympleksowy, inaczej metoda sympleks(ów) to stosowana w matematyce iteracyjna metoda rozwiązywania zadań programowania liniowego za pomocą kolejnego polepszania (optymalizacji) rozwiązania. Nazwa metody pochodzi od simpleksu, figury wypukłej będącej uogólnieniem trójkąta na więcej wymiarów.

[edytuj] Opis metody

Zadanie programowania liniowego z dowolną ilością zmiennych można rozwiązać wyznaczając wszystkie wierzchołkowe punkty wielościanu, a następnie porównując wartości funkcji w punktach wierzchołkowych. W związku z wielością punktów powstaje problem wyznaczenia wartości funkcji celu i znalezienie optymalnego wierzchołka, który spełniłby warunek zadania programowania liniowego. Istota metody simpleks sprowadza się do tego, że jeżeli jest znany jakikolwiek wierzchołkowy punkt i wartość w tym punkcie funkcji celowej, to wtedy wszystkie wierzchołkowe punkty w których celowa funkcja przyjmuje gorsze wartości są odrzucane. Kolejny krok iteracji polega na tym, że przechodzimy do następnego wierzchołka, znajdującego się na jednej krawędzi z odnalezionym już punktem, w którym celowa funkcja osiąga lepsze wartości. Iteracja kończy się, gdy kolejny przeglądany punkt wierzchołkowy jest najlepszy pod względem odpowiednich wartości funkcji celowej.

W metodzie simpleks dla układu równań A^kx=b_k w postaci kanonicznej istnieje tablica simpleksowa Y^k o wymiarach (m+1)x(n+1) w postaci:

$Y_{k}=\left[ \frac{A_{k} | b^{k}}{-(c^{-k})^{T}) | z_{0}^{k}} \right]$

[edytuj] Kroki algorytmu

Dla wykonania algorytmu simpleks należy wykonać kroki:

Podstawiamy k=0
Sprawdzamy kryteria stopu dla j=1,...,n:

$y_{m+1,j}^{k}=-c_{j}^{-k} \leq 0$

Jeśli kryterium nie jest spełnione, to:
Wyznaczamy indeksy s macierzy A dla kolumny wprowadzanej do bazy dla j z przedziału 1-n:

$y_{m+1,s}^{k}=max [y_{m+1,j}^{k}]$
Sprawdzamy kryterium nieograniczoności: dla i=1,...,m

$y_{i,s}^{k} \leq 0$

Jeśli kryterium nie jest spełnione, to:
Wyznaczamy indeks r dla kolumny macierzy B, która jest usuwana z bazy

$\frac{y_{r,n+1}^{k}}{y_{r,s}^{k}}=min \left[ \frac{y_{r,n+1}^{k}}{y_{r,s}^{k}} : y_{i,s}^{k} >0 \right]$
Dokonujemy zmiany zastępując r-tą współrzędną wektora x_B przez współrzędną x_s i wyznaczamy nową tablicę simpleksową Y_k+1
Podstawiamy k=k+1 i kontynuujemy od kroku (2)

Inaczej, mając układ równań dokonujemy przekształceń:

Jeśli rozwiązanie podstawowe układu jest nieprawidłowe, wybieramy jedną z nieprawidłowych zmiennych.

Wybieramy jedną ze zmiennych po prawej stronie mającą dodatni współczynnik. Jeśli takowej by nie było, np.:

x 5 = - 2 - x 1 - x 3

To układ nie ma żadnego rozwiązania, w którym lewostronna zmienna jest nieujemna.

Rozwiązujemy równania ze względu na wybraną zmienną po prawej stronie.

$x_L = -\alpha + c_R x_R + \sum_{i=1}^n c_{j} x_j$

$x_R = \frac {\alpha} {c_R} + \frac 1 {c_R} x_L - \sum_{i=1}^n \frac {c_{j}}{c_R} x_j$

Podstawiamy za wszystkie wystąpienia x_R w pozostałych równaniach oraz w definicji funkcji bazowej, prawą stronę nowego równania.

Ponieważ $\frac {\alpha} {c_R}$ jest dodatnie, tak przekształcone równanie nie łamie warunku nieujemności. Podstawienie pod c_R prawej strony równania również nie uczyni żadnego z poprawnych równań niepoprawnym.

Jeśli rozwiązanie bazowe jest prawidłowe, sprawdzamy postać funkcji celu. Jeśli wszystkie współczynniki przy zmiennych występujące w niej są niedodatnie, przyjęcie zera za ich wartości da rozwiązanie optymalne.

Jeśli współczynnik a_i przy zmiennej x_i w funkcji celu jest dodatni, wybieramy jedno z równań i rozwiązujemy je ze względu na x_i po czym postępujemy jako wyżej (na wybór zmiennej oraz równania do rozwiązania muszą być nałożone pewne ograniczenia, jeśli chcemy mieć gwarancję, że algorytm kiedyś się skończy).