Dokumentacja klasy Simplex

#include <Simplex.h>

Diagram dziedziczenia dla Simplex

LinearMethod Method Observable Lista wszystkich składowych.

Opis szczegółowy

Algorytm programowania liniowego "simplex".

Metoda programowania liniowego służąca do rozwiązywania problemów w postaci standardowej:

\[ \min \: \lbrace c^T x \; : \; Ax = b, \; x \ge 0 \rbrace, \]

gdzie:
$A$ - macierz współczynników funkcji ograniczeń,
$b$ - wektor ograniczeń,
$c$ - wektor kosztów.

Metoda simplex oparta jest na spostrzeżeniu, że punkt, w którym znajduje się minimum, jest jednym z punktów wierzchołkowych obszaru dopuszczalnego i że da się go osiągnąć w skończonej liczbie kroków, przechodząc między punktami wierzchołkowymi w taki sposób, aby przy każdym przejściu wartość funkcji celu zmniejszała się.

Aby znajdować punkty wierzchołkowe, algorytm w kolejnych iteracjach wyróżnia w macierzy $A$ część bazową i niebazową oraz rozwiązuje układy równań $A x = b $ względem bazowych współczynników punktu $x$ (niebazowe współczynniki traktuje się jako zerowe).
W ten sposób w każdym etapie wyznaczany jest jeden punkt znajdujący się na przecięciu ograniczeń związanych z aktualną bazą. Na końcu każdego etapu w bazie wymienia się jedną zmienną: wprowadza się tą ze zmiennych niebazowych, której wzrost prowadzi do najszybszego spadku funkcji celu, a wyprowadza tą ze zmiennych bazowych, która po wprowadzeniu nowej zmiennej najszybciej osiąga wartość 0 (pamiętajmy, że standardowe sformułowanie problemu narzuca ograniczenie $x \ge 0$).

Algorytm kończy się, gdy wprowadzenie żadnej ze zmiennych niebazowych do bazy nie będzie mogło prowadzić do spadku wartości funkcji celu.

Zaimplementowano dwufazową wersję algorytmu - jeśli wyznaczenie pierwszej bazy nie jest trywialne (macierz $A$ nie jest w postaci kanonicznej), metoda w celu znalezienia bazy tworzy problem rozszerzony (macierze $\hat{A}, \: \hat{b}, \: \hat{c}$) i rozwiązuje go przy pomocy algorytmu simplex.


Informacje wejściowe:
$A_0$ - macierz współczynników funkcji ograniczeń [$m \times n$],
$b_0$ - wektor ograniczeń [$m$],
$c_0$ - wektor kosztów (współczynników funkcji celu) [$n$].


Oznaczenia:
$m$ - liczba ograniczeń (liczba wierszy macierzy $A_0$),
$n$ - liczba zmiennych (uwzględnia zmienne dopełniające, nie uwzględnia zmiennych rozszerzających, liczba kolumn macierzy $A_0$),
$\hat{A}$ - macierz wsp. f. ograniczeń problemu rozszerzonego [$m \times (n + m)$],
$\hat{b}$ - wektor ograniczeń problemu rozszerzonego [$m$],
$\hat{c}$ - wektor kosztów problemu rozszerzonego [$n + m$],
$A, \: b, \: c$ - macierze aktualnie rozwiązywanego problemu,
$x_B$ - wektor bazowych współrzędnych aktualnego punktu [$m$],
$i_B$ - wektor indeksów bazowych (indeksów kolumn macierzy $A$, które tworzą aktualną bazę),
$i_N$ - wektor indeksów niebazowych,
$B$ - aktualna baza (macierz zbudowana z kolumn macierzy $A$ o indeksach z $i_B$) [$m \times m$],
$N$ - macierz zbudowana z pozostałych, niebazowych kolumn $A$ [$m \times (n - m) \mbox{ gdy } A = A_0; \; m \times n \mbox{ gdy } A = \hat{A}$],
$d$ - wektor kosztów zredukowanych (zawiera informację o wpływie ewentualnego wprowadzenia danej zmiennej niebazowej na wartość funkcji celu) [$(n - m) \mbox{ gdy } A = A_0; \; n \mbox{ gdy } A = \hat{A}$],
$h$ - wektor przesunięcia (zawiera informację o tym, jak proporcjonalnie zmienią się poszczególne zmienne bazowe po wprowadzeniu nowej zmiennej do bazy) [$m$],
$s$ - indeks zmiennej wprowadzanej do bazy,
$q$ - indeks zmiennej wyprowadzanej z bazy,
$\alpha$ - długość kroku przy przejściu do nowego punktu wierzchołkowego,
$p$ - informacja o aktualnie przeprowadzanej fazie algorytmu ($p = 1$ - faza wstępna: rozwiązywanie problemu rozszerzonego w celu znalezienia pierwszej bazy; $p = 2$ - rozwiązywanie problemu właściwego) .


Procedura.


Krok 1:
Sprawdzamy, czy ostatnich $m$ kolumn macierzy $A_0$ tworzy macierz identycznościową. Jeśli tak, przechodzimy do kroku 2. Jeśli nie, przechodzimy do kroku 3.


Krok 2:
Macierz bazowa będzie utworzona z ostatnich $m$ kolumn macierzy $A_0$.
Podstawiamy:

\[ i_B = \lbrack n - m + 1, \: n - m + 2, \: \ldots, \: n \rbrack , \]

\[ i_N = \lbrack 1, \: 2, \: \ldots, \: n - m \rbrack . \]

Przechodzimy do kroku 5.


Krok 3:
W celu znalezienia pierwszej bazy rozwiązujemy problem rozszerzony.
Tworzymy macierze problemu rozszerzonego:

\[ A = \lbrack A_0 \; | \; I(m) \rbrack = \hat{A} , \]

\[ b = b_0 = \hat{b} , \]

\[ c = \lbrack 0(n) \; | \; 1(m) \rbrack = \hat{c} , \]

gdzie:
$I(m)$ - macierz jednostkowa $m \times m$,
$0(n)$ - wektor zerowy o $n$ wersach,
$1(m)$ - wektor jednostkowy o $m$ wersach.
Podstawiamy:

\[ i_B = \lbrack n + 1, \: n + 2, \: \ldots, \: n + m \rbrack , \]

\[ i_N = \lbrack 1, \: 2, \: \ldots, \: n \rbrack . \]

Na podstawie $i_B$ i $i_N$ oraz $A$ tworzymy macierze $B$ i $N$.
Podstawiamy $p = 1$ i przechodzimy do kroku 6.


Krok 4:
Sprawdzamy, czy otrzymane po rozwiązaniu problemu rozszerzonego indeksy bazowe są poprawne (nie dotyczą kolumn rozszerzających):
Jeśli $ \exists \: i \in \overline{1,\ldots,m} \: . \: (i_B^{(i)} > n) $, to STOP - zmiennych rozszerzających nie udało się wyeliminować, problemu nie da się rozwiązać.
W przeciwnym wypadku usuwamy niebazowe indeksy zmiennych rozszerzających :
dla $i = 1, \: \ldots, n$ jeśli $i_N^{(i)} > n$, element ten jest usuwany z wektora.
Przechodzimy do kroku 5.


Krok 5:
Podstawiamy:

\[ A = A_0, \]

\[ b = b_0, \]

\[ c = c_0, \]

\[ p = 2 . \]

Na podstawie $i_B$ i $i_N$ oraz $A$ tworzymy macierze $B$ i $N$.
Przechodzimy do kroku 6.


Krok 6:
Obliczamy macierz odwrotną do bazowej $B^{-1}$.
Wyznaczamy pierwszy punkt wierzchołkowy:

\[ x_B = B^{-1} b .\]

Przechodzimy do kroku 7.


Krok 7:
Obliczamy wektor kosztów zredukowanych:

\[ d = c_N - N^T B^{-T} c_B . \]

Sprawdzamy warunek stopu:
Jeśli $d \ge 0$, to: jeśli $p = 2$ to STOP - wynikiem jest $x_B$ uzupełniony o pozostałe, niebazowe zmienne; jeśli $p = 1$, to przechodzimy do kroku 4.
Jeśli $d < 0$, to zapamiętujemy indeks najmniejszej składowej tego wektora - będzie to indeks zmiennej wprowadzanej do bazy:

\[ s = \arg \min_{i \in \overline{1,\ldots,dim(d)}} d^{(i)} . \]

Przechodzimy do kroku 8.


Krok 8:
Obliczamy wektor przesunięcia:

\[ h = B^{-1} N^{(s)} , \]

gdzie:
$N^{(s)}$ - s-ta kolumna macierzy $N$.
Sprawdzamy, czy $h \le 0$. Jeśli tak, to STOP - problem jest nieograniczony.
W przeciwnym wypadku szukamy zmiennej, którą należy wyprowadzić z bazy:

\[ \mbox{Dla } i = 1, \: \ldots, \: m \mbox{: } \; \sigma^{(i)} = \left\{ \begin{array}{ll} \frac{x_B^{(i)}}{h^{(i)}} & \mbox{ dla $h^{(i)} > 0$} \\ +\infty & \mbox{ dla $h^{(i)} \le 0$} \end{array} \right. \]

\[ q = \arg \min_{i \in \overline{1,\ldots,m}} \sigma^{(i)} , \]

\[ \alpha = \sigma^{(q)} . \]

Przechodzimy do kroku 9.


Krok 9:
Zamieniamy indeksy zmiennej wychodzącej i wchodzącej do bazy:

\[ i_B^{(q)} \leftrightarrow i_N^{(s)}. \]

Na podstawie nowych indeksów tworzymy macierze $B$ i $N$.
Obliczamy nową macierz $B^{-1}$.
Wyznaczamy nowy punkt wierzchołkowy:

\[ x_B = x_B - \alpha h, \]

\[ x_B^{(q)} = \alpha. \]

Przechodzimy do kroku 7.


Uwagi.
Zaimplementowano metodę niezmodyfikowaną, bez algorytmu zapobiegającego zapętleniu przy występowaniu punktów zdegenerowanych.

Metoda zaimplementowana na podstawie opisu zamieszczonego w:
Bruun H. N.: Algorithms for Linear Optimization - an Introduction. Lyngby, Technical University of Denmark 1999.
(http://www2.imm.dtu.dk/courses/02611/ALO.pdf).

Zobacz również:
AugmentedForm

Niniejszy dokument został półautomatycznie wycięty z dokumentacji kodu źródłowego programu Eduoptim 2. Pełna dokumentacja dostępna jest wraz ze źródłami bądź osobno w dziale pliki.
Hierarchia klas w programie nie odpowiada klasyfikacji metod optymalizacji.