Algorytm sympleksowy
Algorytm sympleksowy, inaczej metoda sympleks(ów) – 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-Meada, niezwiązany z algorytmem opisywanym w tym artykule.
Opis metody
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d4/Simplex-method-3-dimensions.png/220px-Simplex-method-3-dimensions.png)
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ń w postaci kanonicznej istnieje tablica sympleksowa o wymiarach w postaci:
Kroki algorytmu
Dla wykonania algorytmu sympleks należy wykonać kroki:
- Podstawiamy
- Sprawdzamy kryteria stopu dla
- Jeśli kryterium nie jest spełnione, to:
- Wyznaczamy indeksy macierzy dla kolumny wprowadzanej do bazy dla z przedziału
- Sprawdzamy kryterium nieograniczoności: dla
- Jeśli kryterium nie jest spełnione, to:
- Wyznaczamy indeks dla kolumny macierzy która jest usuwana z bazy
- Dokonujemy zmiany zastępując -tą współrzędną wektora przez współrzędną i wyznaczamy nową tablicę sympleksową
- Podstawiamy 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.:
- 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.
- Podstawiamy za wszystkie wystąpienia w pozostałych równaniach oraz w definicji funkcji bazowej, prawą stronę nowego równania.
- Ponieważ jest dodatnie, tak przekształcone równanie nie łamie warunku nieujemności. Podstawienie pod prawej strony równania również nie uczyni żadnego z poprawnych równań niepoprawnym.
- Wybieramy jedną ze zmiennych po prawej stronie mającą dodatni współczynnik. Jeśli takowej by nie było, np.:
- 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 przy zmiennej w funkcji celu jest dodatni, wybieramy jedno z równań i rozwiązujemy je ze względu na 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
Dla zadania maksymalizacji funkcji na obszarze dopuszczalnym z spełniającym równań:
tworzymy tablicę postaci:
Można założyć, że wiersze są 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 podmacierz odwracalną i rozważać tablicę
którą poprzez operacje elementarne można sprowadzić do postaci kanonicznej tablicy sympleks:
Jeśli 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: i funkcja celu przyjmuje dla niego wartość 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ż
- programowanie całkowitoliczbowe
- programowanie matematyczne
- programowanie nieliniowe
Linki zewnętrzne
- COIN-OR- Biblioteka Open Source dla programowania liniowego
- FAQ – programowanie liniowe
- LCCN: sh85122745
- GND: 4181488-5
- J9U: 987007546249105171
- Britannica: topic/simplex-method