Algorytm sympleksowy

Algorytm sympleksowy, inaczej metoda sympleks(ów) – iteracyjna metoda rozwiązywania zadań programowania liniowego za pomocą kolejnego polepszania (optymalizacji) rozwiązania. Nazwa metody pochodzi od sympleksu, figury wypukłej będącej uogólnieniem trójkąta na więcej wymiarów. Terminem „metoda sympleksowa” określa się również algorytm Neldera-Meada, niezwiązany z algorytmem opisywanym w tym artykule.

Opis metody

Wielościan algorytmu sympleksowego w trzech wymiarach

Zadanie programowania liniowego z dowolną liczbą 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 sympleks 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 sympleks dla układu równań $A^{k}x=b_{k}$ w postaci kanonicznej istnieje tablica sympleksowa $Y_{k}$ o wymiarach $(m+1)\times (n+1)$ w postaci:

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

Kroki algorytmu

Dla wykonania algorytmu sympleks należy wykonać kroki:

1. Podstawiamy $k=0$
2. Sprawdzamy kryteria stopu dla $j=1,\dots ,n{:}$

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

   Jeśli kryterium nie jest spełnione, to:

3. Wyznaczamy indeksy $s$ macierzy $A$ dla kolumny wprowadzanej do bazy dla $j$ z przedziału $1,\dots ,n{:}$

   $y_{m+1,s}^{k}=\max[y_{m+1,j}^{k}]$

4. Sprawdzamy kryterium nieograniczoności: dla $i=1,\dots ,m$

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

   Jeśli kryterium nie jest spełnione, to:

5. 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]$

6. Dokonujemy zmiany zastępując $r$-tą współrzędną wektora $x_{B}$ przez współrzędną $x_{s}$ i wyznaczamy nową tablicę sympleksową $Y_{k+1}$
7. 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).

Tabela sympleksowa

Dla zadania maksymalizacji funkcji $\mathbf {c} \cdot \mathbf {x}$ na obszarze dopuszczalnym z $\mathbb {R} ^{n}$ spełniającym $m$ równań:

$\mathbf {A} \mathbf {x} =\mathbf {b} ,\,x_{i}\geqslant 0$

tworzymy tablicę postaci:

${\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\0&\mathbf {A} &\mathbf {b} \end{bmatrix}}.$

Można założyć, że wiersze $\mathbf {A}$ są liniowo niezależne (jeśli by tak nie było, wystarczy rozważać mniejszą liczbę równań eliminując zależne od pozostałych). Wówczas można wybrać z $\mathbf {A}$ podmacierz odwracalną $\mathbf {B}$ i rozważać tablicę

${\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\0&\mathbf {B} ^{-1}\mathbf {A} &\mathbf {B} ^{-1}\mathbf {b} \end{bmatrix}},$

którą poprzez operacje elementarne można sprowadzić do postaci kanonicznej tablicy sympleks:

${\begin{bmatrix}1&0&-{\bar {\mathbf {c} }}_{D}^{T}&z_{B}\\0&I&\mathbf {D} &{\bar {\mathbf {b} }}\end{bmatrix}}.$

Jeśli ${\bar {b_{i}}}\geqslant 0,$ to tablica jest pierwotnie dopuszczalna i opisuje wierzchołek obszaru dopuszczalnego. Zmienne odpowiadające macierzy jednostkowej nazywamy bazowymi, a opisywany przez tablicę wierzchołek ma współrzędne: $({\bar {\mathbf {b} }}^{T},0,\dots ,0)$ i funkcja celu przyjmuje dla niego wartość $z_{B}.$ Kolumny odpowiadające zmiennym niebazowym opisują krawędzie wychodzące z wierzchołka. Współczynnikom ujemnym w pierwszym wierszu odpowiadają krawędzie poprawiające, zerowym – krawędzie neutralne, a dodatnim – pogarszające.

Zobacz też

• programowanie całkowitoliczbowe
• programowanie matematyczne
• programowanie nieliniowe

Linki zewnętrzne

• COIN-OR- Biblioteka Open Source dla programowania liniowego
• FAQ – programowanie liniowe