Algorytm sympleksowy, inaczej metoda sympleks – iteracyjna metoda rozwiązywania zadań programowania liniowego. Polega na przechodzeniu pomiędzy kolejnymi wierzchołkami wielościanu rozwiązań dopuszczalnych w taki sposób, aby w kolejnych iteracjach poprawiać wartość funkcji celu. Metoda została opracowana przez George'a Dantziga w 1947 roku i należy do podstawowych metod rozwiązywania problemów programowania liniowego.
Nazwa metody pochodzi od sympleksu, czyli uogólnienia trójkąta i czworościanu na dowolny wymiar. W kontekście programowania liniowego termin „metoda sympleks” odnosi się jednak do algorytmu działającego na wierzchołkach wielościanu rozwiązań dopuszczalnych, który nie musi być sympleksem.
Algorytm sympleksowy jest szczególnie użyteczny w problemach, w których należy znaleźć największą lub najmniejszą wartość funkcji liniowej przy zadanych ograniczeniach liniowych. Stosowany jest między innymi w badaniach operacyjnych, ekonomii, logistyce, planowaniu produkcji i alokacji zasobów.
Termin „metoda sympleksowa” bywa również używany w odniesieniu do metody Neldera-Meada. Jest to jednak inny algorytm optymalizacyjny, przeznaczony do problemów optymalizacji bez ograniczeń lub z ograniczeniami obsługiwanymi w inny sposób, i nie jest związany z algorytmem sympleksowym programowania liniowego.
Historia
Algorytm sympleksowy został opracowany przez George'a Dant ziga w 1947 roku. Pierwsze zastosowania metody były związane między innymi z problemami planowania gospodarczego i wojskowego.
W kolejnych latach metoda stała się jednym z najważniejszych algorytmów programowania liniowego. Jej rozwój doprowadził między innymi do powstania różnych reguł wyboru zmiennej wchodzącej i wychodzącej z bazy oraz metod radzenia sobie z degeneracją i cyklami.
Współczesne implementacje wykorzystują zwykle zmodyfikowane wersje metody, takie jak metoda sympleksowa w postaci tablicowej lub metoda oparta na faktoryzacji macierzy bazowej. W praktycznych zastosowaniach stosuje się również metodę dwufazową i metodę wielkiej M do znajdowania rozwiązania bazowego dopuszczalnego.
Idea geometryczna
Zadanie programowania liniowego można przedstawić jako optymalizację funkcji liniowej na zbiorze określonym przez liniowe ograniczenia. W typowym przypadku zbiór ten jest wielościanem wypukłym.
Przykładowo problem maksymalizacji
przy ograniczeniach
wyznacza pewien wielokąt będący obszarem rozwiązań dopuszczalnych.
Jeżeli problem ma rozwiązanie optymalne i zbiór rozwiązań dopuszczalnych jest niepusty, to w przypadku ograniczonego optimum istnieje co najmniej jeden wierzchołek zbioru dopuszczalnego, w którym funkcja celu osiąga wartość optymalną.
Algorytm sympleksowy rozpoczyna więc od określonego wierzchołka i przechodzi wzdłuż jednej z jego krawędzi do sąsiedniego wierzchołka, w którym funkcja celu ma nie gorszą wartość. Proces jest powtarzany aż do znalezienia wierzchołka optymalnego.
Nie jest konieczne odwiedzanie wszystkich wierzchołków wielościanu. Algorytm wybiera kolejne wierzchołki na podstawie współczynników funkcji celu i ograniczeń.
Sformułowanie zadania
Standardowe zadanie maksymalizacji programowania liniowego można zapisać w postaci
przy ograniczeniach
gdzie: jest macierzą współczynników ograniczeń, jest wektorem zmiennych decyzyjnych, jest wektorem prawej strony ograniczeń, jest wektorem współczynników funkcji celu.
Ograniczenia typu nierówności można przekształcić do tej postaci poprzez wprowadzenie dodatkowych zmiennych, zwanych zmiennymi luzu.
Przykładowo nierówność
może zostać zastąpiona równaniem
Zmienna jest wtedy zmienną luzu.
Rozwiązanie bazowe
Niech zadanie ma postać
gdzie macierz ma wierszy i kolumn.
Jeżeli można wybrać spośród kolumn macierzy podzbiór liniowo niezależnych kolumn, tworzących odwracalną macierz , to macierz tę nazywa się macierzą bazową.
Zmienne odpowiadające kolumnom macierzy nazywa się zmiennymi bazowymi, natomiast pozostałe zmienne są zmiennymi niebazowymi.
Przyjmując wszystkie zmienne niebazowe za równe zeru, otrzymujemy układ
Stąd
Jeżeli
otrzymane rozwiązanie jest bazowym rozwiązaniem dopuszczalnym.
Każde bazowe rozwiązanie dopuszczalne odpowiada wierzchołkowi obszaru rozwiązań dopuszczalnych, choć w przypadku degeneracji kilka baz może odpowiadać temu samemu wierzchołkowi.
Tabela sympleksowa
W klasycznej wersji algorytmu stosuje się tablicę sympleksową. Dla zadania
przy ograniczeniach
można rozpocząć od tablicy
Jeżeli wybrano bazę odpowiadającą macierzy , poprzez odpowiednie operacje na wierszach można otrzymać postać kanoniczną
Macierz jest macierzą jednostkową odpowiadającą zmiennym bazowym. Wektor zawiera wartości zmiennych bazowych dla aktualnego rozwiązania.
Jeżeli
aktualna baza opisuje rozwiązanie dopuszczalne.
Współczynniki w wierszu funkcji celu wskazują, które zmienne niebazowe mogą poprawić wartość funkcji celu. W przypadku konwencji maksymalizacyjnej, w której wiersz funkcji celu zawiera przeciwne znaki współczynników kosztów zredukowanych, dodatni współczynnik może wskazywać możliwość poprawy wartości funkcji celu.
Przebieg algorytmu
Podstawowa wersja algorytmu może zostać przedstawiona następująco.
Wyznaczane jest początkowe bazowe rozwiązanie dopuszczalne. Tworzona jest tabela sympleksowa odpowiadająca aktualnej bazie. Sprawdzany jest wiersz funkcji celu. Jeżeli żadna ze zmiennych niebazowych nie może poprawić wartości funkcji celu, aktualne rozwiązanie jest optymalne. W przeciwnym razie wybierana jest zmienna wchodząca do bazy. Za pomocą testu ilorazów wybierana jest zmienna wychodząca z bazy. Wykonywany jest krok pivotowy, który zmienia bazę. Otrzymana tabela opisuje nowe rozwiązanie bazowe. Kroki są powtarzane do momentu spełnienia kryterium optymalności, wykrycia nieograniczoności albo innego warunku zakończenia.
Zmienna wchodząca do bazy
Jeżeli aktualne rozwiązanie nie jest optymalne, należy wybrać zmienną niebazową, która zostanie wprowadzona do bazy.
Wybór może być dokonywany za pomocą różnych reguł. Jedną z prostszych jest wybór zmiennej o największym dodatnim współczynniku w odpowiednim wierszu tablicy sympleksowej.
Stosuje się również inne reguły, między innymi regułę najmniejszego indeksu oraz regułę największego kosztu zredukowanego.
Wybór reguły może mieć wpływ na liczbę iteracji potrzebnych do znalezienia rozwiązania.
Zmienna wychodząca z bazy
Po wybraniu zmiennej wchodzącej należy ustalić, jak daleko można poruszać się w wybranym kierunku bez opuszczenia obszaru rozwiązań dopuszczalnych.
Służy do tego test ilorazów. Dla odpowiednich dodatnich współczynników wyznacza się ilorazy
Wybierany jest najmniejszy nieujemny iloraz. Odpowiadający mu wiersz wyznacza zmienną wychodzącą z bazy.
Jeżeli dla wybranej zmiennej wchodzącej wszystkie odpowiednie współczynniki są niedodatnie, oznacza to, że funkcję celu można poprawiać bez ograniczenia. W takim przypadku zadanie maksymalizacyjne jest nieograniczone.
Operacja pivotowa
Po wybraniu zmiennej wchodzącej i wychodzącej wykonuje się operację pivotową.
Element znajdujący się na przecięciu wybranego wiersza i wybranej kolumny nazywa się elementem głównym (pivotem).
Operacja polega na przekształceniu tablicy za pomocą operacji elementarnych na wierszach tak, aby: element główny otrzymał wartość 1, pozostałe elementy w jego kolumnie otrzymały wartość 0.
W rezultacie zmienna wchodząca staje się zmienną bazową, a zmienna wychodząca przestaje być zmienną bazową.
Nowa tablica opisuje inne bazowe rozwiązanie dopuszczalne.
Kryterium optymalności
Dla zadania maksymalizacji, przy odpowiedniej konwencji zapisu tablicy sympleksowej, rozwiązanie jest optymalne, jeżeli wiersz funkcji celu nie zawiera współczynników umożliwiających dalszą poprawę wartości funkcji celu.
W szczególności, przy zapisie wykorzystującym koszty zredukowane, warunek optymalności można wyrazić jako
Wtedy żadna ze zmiennych niebazowych nie może zostać zwiększona w sposób prowadzący do poprawy funkcji celu.
Jeżeli pewne koszty zredukowane są równe zeru, może istnieć więcej niż jedno rozwiązanie optymalne.
Przykład
Rozważmy zadanie
przy ograniczeniach
Wprowadzamy zmienne luzu i :
Funkcja celu ma postać
Początkowym rozwiązaniem bazowym jest
Wartość funkcji celu wynosi wówczas
Ponieważ zwiększenie lub może poprawić wartość funkcji celu, wykonuje się kolejną iterację. Po wykonaniu kolejnych operacji pivotowych algorytm przechodzi pomiędzy sąsiednimi wierzchołkami obszaru dopuszczalnego.
Dla tego zadania rozwiązaniem optymalnym jest
a maksymalna wartość funkcji celu wynosi
Inicjalizacja algorytmu
Jednym z warunków rozpoczęcia klasycznego algorytmu sympleksowego jest posiadanie bazowego rozwiązania dopuszczalnego.
W prostych zadaniach, w których wszystkie ograniczenia mają postać
można często uzyskać takie rozwiązanie bezpośrednio po dodaniu zmiennych luzu.
W ogólnym przypadku znalezienie początkowego rozwiązania dopuszczalnego może wymagać zastosowania dodatkowej procedury. Stosuje się między innymi metodę dwufazową.
W pierwszej fazie konstruuje się pomocnicze zadanie programowania liniowego, którego rozwiązanie pozwala ustalić, czy pierwotny problem ma rozwiązanie dopuszczalne. Jeżeli tak, otrzymaną bazę wykorzystuje się jako punkt początkowy drugiej fazy.
Alternatywnym podejściem jest metoda wielkiej M, w której do funkcji celu wprowadza się odpowiednio duże kary związane ze zmiennymi sztucznymi.
Degeneracja
Rozwiązanie bazowe nazywa się degenerowanym, jeżeli co najmniej jedna zmienna bazowa ma wartość równą zero.
Degeneracja może powodować, że algorytm wykona pivot, nie zmieniając geometrycznie aktualnego wierzchołka. W konsekwencji wartość funkcji celu może pozostać niezmieniona przez jedną lub więcej iteracji.
W szczególnych przypadkach może wystąpić cykl, czyli powrót do wcześniej odwiedzanej bazy. Aby temu zapobiec, można stosować odpowiednie reguły wyboru zmiennej wchodzącej i wychodzącej.
Jedną z klasycznych metod zapobiegania cyklom jest reguła najmniejszego indeksu (reguła Bland'a).
Wielokrotność rozwiązania optymalnego
Zadanie programowania liniowego może mieć więcej niż jedno rozwiązanie optymalne.
Jeżeli funkcja celu jest stała wzdłuż pewnej krawędzi obszaru rozwiązań dopuszczalnych, wszystkie punkty tej krawędzi mogą być rozwiązaniami optymalnymi.
W tablicy sympleksowej sytuację taką można rozpoznać między innymi po występowaniu zerowych kosztów zredukowanych dla odpowiednich zmiennych niebazowych.
Nieograniczoność
Jeżeli podczas wyboru zmiennej wchodzącej nie istnieje odpowiedni wiersz spełniający warunek testu ilorazów, oznacza to, że wybrany kierunek poprawy funkcji celu nie prowadzi do ograniczenia wynikającego z warunków zadania.
W przypadku maksymalizacji oznacza to, że funkcja celu może rosnąć bez ograniczenia. Zadanie nie posiada wtedy skończonego optimum.
Brak rozwiązania dopuszczalnego
Algorytm może również wykazać, że zbiór rozwiązań dopuszczalnych jest pusty.
W praktycznych implementacjach problem ten jest rozpoznawany podczas procedury inicjalizacji, na przykład w pierwszej fazie metody dwufazowej. Jeżeli wartość funkcji pomocniczej wskazuje na konieczność pozostawienia zmiennej sztucznej w rozwiązaniu, oznacza to brak rozwiązania dopuszczalnego dla zadania pierwotnego.
Złożoność obliczeniowa
Algorytm sympleksowy jest bardzo skuteczny w wielu praktycznych zastosowaniach, jednak jego klasyczna wersja nie ma wielomianowego ograniczenia liczby iteracji w najgorszym przypadku.
Istnieją rodziny problemów, dla których określone reguły wyboru pivotów prowadzą do wykładniczej liczby iteracji względem rozmiaru problemu.
Nie oznacza to jednak, że metoda jest niepraktyczna. W zastosowaniach praktycznych algorytm sympleksowy często wykonuje znacznie mniej iteracji, niż wynikałoby to z najgorszego przypadku teoretycznego.