Metoda simpleks

Metoda simpleks
Polecane artykuły
Programowanie liniowe Drzewo decyzyjne 7 narzędzi TQC Analytic Hierarchy Process Typizacja Diagram pokrewieństwa System ekspercki Podejście funkcjonalno-wzorcujące Metoda Blocha-Schmigalli

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):

• Marketing – koszty 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

• Dębski D. (2006), Ekonomika i organizacja przedsiębiorstw Część 2, Wydawnictwo Szkolne i Pedagogiczne Spółka Akcyjna, Warszawa, s. 144
• Glinka M., Badania operacyjne (fragmenty wykładu), Uniwersytet Technologiczno-Humanistyczny w Radomiu, Radom
• Gospodarek T. (2009), Modelowanie w naukach o zarządzaniu oparte na metodzie programów badawczych i formalizmie reprezentatywnym, Wydawnictwo Uniwersytetu Ekonomicznego we Wrocławiu, Wrocław, s. 124-125
• Hillier F.S., Libereman G.J. (2001), Introduction to Operations Research, Uniwersytet Stanforda, Stanford
• Kostrzewska M.D. (2019), Metoda simpleks na przykładzie problemu decyzyjnego przedsiębiorstwa produkującego panele solarne, Instytut Marketingu i Zarządzania Uniwersytetu Szczecińskiego, Szczecin
• Łomotowski G. (2018), Zastosowanie metody simpleksów w badaniach symulacyjnych mikrozaworu hydraulicznego, Wydawnictwo Uczelni Jana Wyżykowskiego, Polkowice
• Wojda A.P. (2013), Wykłady z programowanie liniowego, Wydział Matematyki Stosowanej AGH, Kraków

Autor: Bartosz Karlikowski