Algorytm sympleksowy

Z Wikipedii

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.

[edytuj] 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^kx=b_k w postaci kanonicznej istnieje tablica sympleksowa Y^k o wymiarach (m+1)x(n+1) w postaci:

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

[edytuj] Kroki algorytmu

Dla wykonania algorytmu sympleks należy wykonać kroki:

Podstawiamy k=0
Sprawdzamy kryteria stopu dla j=1,...,n:

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

Jeśli kryterium nie jest spełnione, to:
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}]$
Sprawdzamy kryterium nieograniczoności: dla i=1,...,m

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

Jeśli kryterium nie jest spełnione, to:
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]$
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
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).

[edytuj] Tabela sympleksowa

Tworzymy tablicę sympleksową w postaci:

**tabela sympleks**
	x₀	...	x_j	...	x_k
x₀	z₀₀	...	y_0j	...	y_0k
x_B1	z₁₀	...	y_1j	...	y_0k
...	...	...	...	...	...
x_Br	z_r0	...	y_rj	...	y_rk
...	...	...	...	...	...
x_Bm	z_m0	...	y_mj	...	y_mk

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

[edytuj] Zobacz też

[edytuj] Linki zewnętrzne

COIN-OR- Biblioteka Open Source dla programowania liniowego
GLPK dla win32 – program i biblioteka dla programowania liniowego
GLPK dla Linuksa – program i biblioteka dla programowania liniowego
Cplex – Komercyjna biblioteka dla programowania liniowego
FAQ – programowanie liniowe
Simplex Algorithm by Elmer G. Wiens. Demonstrates algorithm in detail, using the simplex tableau.

We provide Linux to the World

Algorytm sympleksowy

Z Wikipedii

Spis treści

[edytuj] Opis metody

[edytuj] Kroki algorytmu

[edytuj] Tabela sympleksowa

[edytuj] Zobacz też

[edytuj] Linki zewnętrzne

Views

nawigacja

zmiany

dla edytorów

Szukaj

W innych językach