Poprzednia

ⓘ Algorytm sympleksowy




                                     

ⓘ Algorytm sympleksowy

Algorytm sympleksowy, inaczej metoda sympleks – iteracyjna metoda rozwiązywania zadań programowania liniowego za pomocą kolejnego polepszania 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.

                                     

1. Opis metody

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 {\displaystyle A^{k}x=b_{k}} w postaci kanonicznej istnieje tablica sympleksowa Y k {\displaystyle Y_{k}} o wymiarach m + 1 × n + 1 {\displaystyle m+1\times n+1} w postaci:

Y k =.}
                                     

2. Kroki algorytmu

Dla wykonania algorytmu sympleks należy wykonać kroki:

  • Podstawiamy k = k + 1 {\displaystyle k=k+1} i kontynuujemy od kroku 2
  • Dokonujemy zmiany zastępując r {\displaystyle r} -tą współrzędną wektora x B {\displaystyle x_{B}} przez współrzędną x s {\displaystyle x_{s}} i wyznaczamy nową tablicę sympleksową Y k + 1 {\displaystyle Y_{k+1}}
  • Sprawdzamy kryteria stopu dla j = 1, …, n: {\displaystyle j=1,\dots,n{:}} y m + 1, j k = − c j − k ⩽ 0 {\displaystyle y_{m+1,j}^{k}=-c_{j}^{-k}\leqslant 0} Jeśli kryterium nie jest spełnione, to
  • Podstawiamy k = 0 {\displaystyle k=0}
  • Wyznaczamy indeksy s {\displaystyle s} macierzy A {\displaystyle A} dla kolumny wprowadzanej do bazy dla j {\displaystyle j} z przedziału 1, …, n: {\displaystyle 1,\dots,n{:}} y m + 1, s k = max }

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 {\displaystyle 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 = − α + c R x R + ∑ i = 1 n c j x j {\displaystyle x_{L}=-\alpha +c_{R}x_{R}+\sum _{i=1}^{n}c_{j}x_{j}} x R = α c R + 1 c R x L − ∑ i = 1 n c j c R x j {\displaystyle 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 {\displaystyle x_{R}} w pozostałych równaniach oraz w definicji funkcji bazowej, prawą stronę nowego równania. Ponieważ α c R {\displaystyle {\frac {\alpha }{c_{R}}}} jest dodatnie, tak przekształcone równanie nie łamie warunku nieujemności. Podstawienie pod c R {\displaystyle 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 {\displaystyle a_{i}} przy zmiennej x i {\displaystyle x_{i}} w funkcji celu jest dodatni, wybieramy jedno z równań i rozwiązujemy je ze względu na x i {\displaystyle x_{i}} po czym postępujemy jako wyżej.
                                     

3. Tabela sympleksowa

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

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

tworzymy tablicę postaci:

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

Jeśli b i ¯ ⩾ 0, {\displaystyle {\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: b ¯ T, 0, …, 0 {\displaystyle {\bar {\mathbf {b} }}^{T},0,\dots,0} i funkcja celu przyjmuje dla niego wartość z B. {\displaystyle 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.