Algorytm sympleksowy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 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-Mead'a, niezwiązany z algorytmem opisywanym w tym artykule.

Opis metody[edytuj | edytuj kod]

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ń Akx=bk w postaci kanonicznej istnieje tablica sympleksowa Yk o wymiarach (m+1)x(n+1) w postaci:


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

Kroki algorytmu[edytuj | edytuj kod]

Dla wykonania algorytmu sympleks należy wykonać kroki:

  1. Podstawiamy k=0
  2. Sprawdzamy kryteria stopu dla j=1,...,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-n:
    y_{m+1,s}^{k}=\max [y_{m+1,j}^{k}]
  4. Sprawdzamy kryterium nieograniczoności: dla i=1,...,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 xB przez współrzędną xs i wyznaczamy nową tablicę sympleksową Yk+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 xR 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 cR 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 ai przy zmiennej xi w funkcji celu jest dodatni, wybieramy jedno z równań i rozwiązujemy je ze względu na xi 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[edytuj | edytuj kod]

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 \ge 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}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}}^T_D & z_B \\
    0 & I & \mathbf{D} & \bar{\mathbf{b}}
  \end{bmatrix}

Jeśli \bar{b_i} \ge 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,\ldots,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.

Ta sekcja jest niekompletna. Jeśli możesz, rozbuduj ją.

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]