Algorytm sympleksowy

Algorytm sympleksowy, znany również jako metoda sympleks, to iteracyjna technika rozwiązywania problemów programowania liniowego poprzez optymalizację rozwiązań. Jego nazwa pochodzi od pojęcia sympleksu, który jest uogólnieniem trójkąta w wielowymiarowej przestrzeni.

Opis metody

Metoda sympleksowa polega na wyznaczaniu wierzchołków wielościanu, które są punktami rozwiązania zadania programowania liniowego. Rozpoczyna się od wybranego wierzchołka, a następnie iteracyjnie przemieszcza się do sąsiednich wierzchołków, eliminując te, które nie spełniają warunków optymalności. Proces kończy się, gdy osiągnięty zostaje najlepszy wierzchołek.

Kroki algorytmu

Podstawowe kroki algorytmu sympleksowego obejmują:

Inicjalizacja: ustawienie $k=0$ .
Sprawdzenie kryteriów stopu dla $j=1,dots,n$ .
Jeśli kryterium nie jest spełnione, wyznacz indeksy $s$ dla kolumny wprowadzanej do bazy.
Sprawdzenie kryterium nieograniczoności.
Wyznaczanie indeksu $r$ dla kolumny usuwanej z bazy.
Zmiana współrzędnej $x_B$ oraz wyznaczenie nowej tablicy sympleksowej $Y_{k+1}$ .
Inkrementacja $k$ i powrót do kroku 2.

Tabela sympleksowa

Dla maksymalizacji funkcji $mathbf{c} cdot mathbf{x}$ przy spełnieniu równań $mathbf{A}mathbf{x} = mathbf{b},, x_i geqslant 0$ , tworzy się tablicę w postaci:

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

Zakłada się, że wiersze $mathbf{A}$ są liniowo niezależne, co pozwala na wybranie podmacierzy $mathbf{B}$ . Tablica ta może zostać przekształcona do postaci kanonicznej:

$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} geqslant 0$ , tablica jest dopuszczalna i opisuje wierzchołek obszaru dopuszczalnego. Zmienne odpowiadające macierzy jednostkowej są bazowe, a ich współrzędne oraz wartości funkcji celu są kluczowe dla wyznaczenia optymalnego rozwiązania.

Najnowsze aktualności:

Algorytm sympleksowy