Metoda simpleks

Metoda simpleks
Polecane artykuły

Metoda simpleks, inaczej algorytm simpleksowy – matematyczna metoda programowania liniowego mająca na celu rozwiązanie zadania przez kolejne optymalizacje rozwiązań. Nazwa pochodzi od simpleksu, czyli otoczki wypukłej n+1 elementowego zbioru w przestrzeni n wymiarowej. W tej metodzie poruszamy się po krawędziach tego wielościanu, w celu sprawdzenia kolejnych wierzchołków (A. Paweł Wojda, 2013). Została opracowana w 1947 roku przez amerykańskiego matematyka George’a Dantzig’a. Okazała się niezwykle wydajną metodą, która rozwiązywała wiele problemów w programowaniu liniowym. Poza małymi zadaniami, metoda ta jest używana w specjalnych szeroko dostępnych oprogramowaniach (F.S. Hillier, G.J. Lieberman, 2001).

Algorytm Simpleksu

Składa się z dwóch podstawowych elementów:

  • Pierwszy, który osiągniemy dodając dodatkowe zmienne decyzyjne. W ten sposób dojdziemy do rozwiązania bazowego dopuszczalnego.
  • Drugim elementem jest korekta przeprowadzonych już wcześniej iteracji rozwiązania bazowego dopuszczalnego do momentu, kiedy osiągniemy rozwiązanie optymalne, jeśli ono w ogóle istnieje.

Istotą algorytmu simpleks jest badanie rozwiązań bazowych w postaci kanonicznej tak, aby znaleźć dowolne rozwiązanie programu, równocześnie sprawdzając czy jest ono optymalne. Jeżeli rozwiązanie nie jest optymalne, zaczynamy ponownie od znalezienia rozwiązania bazowego lepszego od poprzedniego. Kiedy stwierdzimy, że nie jesteśmy w stanie poprawić rozwiązania oznacza to, że rozwiązanie bazowe jest optymalne (M.D. Kostrzewska,2019).

Algorytm simpleks jest operacją pracochłonną, szczególnie dla modeli o dużych rozmiarach. W takim przypadku stosuje się aplikacje komputerowe, które umożliwiają tworzenie procedur obliczeniowych metody simpleks lub są wyposażone w gotowe moduły simpleksowe. Do takich programów należą: Mathematica, MathCAD, Excel, Quantitative Systems for Business (M. Glinka).

Zalety metody simpleks

Metoda simpleksów posiada wiele zalet, ale do najważniejszych z nich należą (G. Łomotowski, 2018):

  • efektywność – możliwość ustalenia optimum,
  • wydajność – osiągnięcie celu na podstawie małej liczby doświadczeń,
  • celowość – obszary, w których wyniki są niezadowalające zostają pomijane.

Zastosowania praktyczne

Rozwiązanie problemu maksymalizacji funkcji celu przy użyciu metody simpleksu, znalazło zastosowania w różnych dziedzinach ekonomii (T. Gospodarek, 2009):

  • Marketingkoszty oraz efektywność to dwa najbardziej istotne elementy, w których programowanie liniowe spełnia swoją rolę, ze względu na proste funkcje ograniczające.
  • Analiza finansowa – zastosowanie programowania liniowego w analizie finansowej najlepiej widać na przykładzie optymalnego portfolio oraz strategii mieszanych w finansowaniu organizacji.
  • Zarządzanie produkcjąplanowanie pracy oraz ustalenie obciążenia zasobów, czyli tzw. eliminacja wąskich gardeł, w tych aspektach metoda simpleksu jest dobrym narzędziem, dzięki której powstały specjalnie dedykowane programy komputerowe.
  • Analiza wielokryterialna – najbardziej odpowiadające modelowo zastosowanie programowania liniowego.

Na przykładzie produkcji, dzięki metodzie simpleks możemy uzyskać takie rozwiązanie optymalne dla określonych wielkości, które da przedsiębiorstwu największy zysk lub najniższe zużycie czynników produkcji. Obliczamy kolejne rozwiązania do momentu znalezienia najlepszego w danych warunkach. Ta operacja poszukiwania kolejnych rozwiązań zwana jest metodą kolejnych przybliżeń lub iteracją (D. Dębski, 2006).

Bibliografia

Autor: Bartosz Karlikowski