Metoda simpleks

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.

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

Składniki algorytmu simpleksu i ich działanie

Algorytm simpleksu składa się z kilku kluczowych składników, które współdziałają, aby znaleźć optymalne rozwiązanie. Oto najważniejsze z nich:

• Tablica simplex: Jest to podstawowy narzędzie algorytmu simpleksu. Tablica ta zawiera informacje dotyczące aktualnego rozwiązania oraz kierunku, w którym należy się poruszać, aby poprawić wartość funkcji celu. Tablica simplex jest aktualizowana w każdym kroku algorytmu, aż do znalezienia optymalnego rozwiązania.
• Pivoting: Pivoting to operacja, która wybiera element bazowy w tablicy simplex. Element ten jest odpowiedzialny za zmianę aktualnego rozwiązania na lepsze. Pivoting polega na zamianie elementów w tablicy w celu poprawienia wartości funkcji celu. Operacja ta jest wykonywana w każdym kroku algorytmu simpleksu.
• Kryterium optymalności: Kryterium optymalności to reguła, która określa, kiedy algorytm simpleksu powinien zakończyć działanie. W przypadku problemów maksymalizacyjnych algorytm simpleksu kończy działanie, gdy wszystkie koszty redukcji w tablicy simplex są nieujemne. Natomiast w przypadku problemów minimalizacyjnych algorytm simpleksu kończy działanie, gdy wszystkie koszty redukcji są nieujemne lub gdy nie ma już żadnego elementu bazowego.

Algorytm simpleks jest iteracyjny, co oznacza, że wykonuje serię kroków, aż do znalezienia optymalnego rozwiązania. W każdym kroku algorytmu następuje aktualizacja tablicy simplex, wybór elementu bazowego za pomocą operacji pivoting oraz sprawdzenie kryterium optymalności. Procedura ta jest powtarzana aż do spełnienia warunku zakończenia, co prowadzi do znalezienia optymalnego rozwiązania.

Wybór punktu startowego

Pierwszym krokiem w procesie rozwiązywania problemu programowania liniowego za pomocą metody simpleks jest wybór punktu startowego. Punkt ten musi spełniać dwa warunki: być dopuszczalny, czyli spełniać wszystkie ograniczenia problemu, oraz mieć wartość funkcji celu większą lub równą niż wszystkie inne dopuszczalne punkty. Jeśli istnieje wiele takich punktów, można wybrać dowolny z nich jako punkt startowy.

Aby wybrać punkt startowy, można skorzystać z różnych metod. Jedną z nich jest metoda największej różnicy, która polega na porównaniu wartości funkcji celu dla różnych punktów dopuszczalnych i wybraniu punktu o największej wartości. Inną metodą jest metoda najmniejszej różnicy, w której wybiera się punkt o najmniejszej wartości funkcji celu spośród punktów dopuszczalnych.

Poruszanie się po krawędziach otoczki wypukłej

Po wyborze punktu startowego, należy poruszać się po krawędziach otoczki wypukłej w poszukiwaniu optymalnego rozwiązania. Otoczka wypukła to zbiór wszystkich dopuszczalnych punktów rozwiązania, które spełniają wszystkie ograniczenia problemu.

Aby poruszać się po krawędziach otoczki wypukłej, metoda simpleks korzysta z tzw. tablic simpleksowych. Tablica simpleksowa jest narzędziem, które pozwala na przekształcenie problemu programowania liniowego do postaci standardowej. W tablicy simpleksowej znajdują się współczynniki funkcji celu oraz ograniczeń, a także zmienne dodatkowe, które reprezentują krawędzie otoczki wypukłej.

Proces poruszania się po krawędziach otoczki wypukłej polega na wyborze zmiennej, która wejdzie do rozwiązania, oraz zmiennej, która opuści rozwiązanie. Wybór tych zmiennych odbywa się na podstawie kryterium optymalności, które polega na znalezieniu zmiennej, która poprawi wartość funkcji celu. Następnie, za pomocą operacji elementarnych na tablicy simpleksowej, można przesuwać się po krawędziach otoczki wypukłej w kierunku optymalnego rozwiązania.

Korekta iteracji do osiągnięcia rozwiązania optymalnego

Proces poruszania się po krawędziach otoczki wypukłej jest powtarzany, aż do osiągnięcia rozwiązania optymalnego. Iteracje mogą być przerywane na podstawie różnych kryteriów, takich jak osiągnięcie maksymalnej liczby iteracji lub brak poprawy wartości funkcji celu przez pewną liczbę iteracji.

Podczas iteracji mogą wystąpić różne sytuacje, które wymagają korekty. Jedną z takich sytuacji jest sytuacja degeneracyjna, która polega na zatrzymaniu się na jednym z punktów w procesie iteracyjnym. W takim przypadku, konieczne jest zastosowanie dodatkowych technik, takich jak technika sztucznej zmiennej, aby znaleźć kolejne dopuszczalne rozwiązanie.

Korekta iteracji polega na analizie aktualnego rozwiązania i zastosowaniu odpowiednich operacji na tablicy simpleksowej w celu poprawy wartości funkcji celu. Operacje te mogą polegać na wyborze nowych zmiennych, przesuwaniu się po krawędziach otoczki wypukłej lub zmianie wartości współczynników w tablicy simpleksowej.

W efekcie wielu iteracji i korekt, metoda simpleks jest w stanie znaleźć optymalne rozwiązanie problemu programowania liniowego. Optymalne rozwiązanie jest tym, które spełnia wszystkie ograniczenia problemu i ma największą wartość funkcji celu.

Zastosowanie metody simpleks w praktyce

Marketing

Metoda simpleks znajduje szerokie zastosowanie w obszarze marketingu. Jej głównym celem jest optymalizacja działań marketingowych oraz efektywne wykorzystanie zasobów, takich jak budżet reklamowy czy zespół sprzedażowy. Dzięki tej metodzie można dokładnie określić, jakie działania marketingowe przyniosą najlepsze rezultaty i jakie powinny być ich proporcje.

Przykładem zastosowania metody simpleks w marketingu może być optymalizacja strategii promocyjnej. Dział marketingu może zdefiniować różne działania promocyjne, takie jak reklama telewizyjna, kampanie w mediach społecznościowych, promocje w sklepach itp. Następnie, korzystając z metody simpleks, można przeprowadzić analizę, aby ustalić, jakie proporcje tych działań przyniosą największy zwrot z inwestycji. Na podstawie wyników analizy można dostosować strategię promocyjną, aby osiągnąć maksymalne efekty przy minimalnych nakładach.

Metoda simpleks może również być wykorzystywana do analizy rynku i segmentacji klientów. Dzięki niej można określić, jakie grupy klientów są najbardziej opłacalne i jakie strategie marketingowe można zastosować, aby przyciągnąć ich uwagę. Dzięki zastosowaniu tej metody można również zoptymalizować alokację zasobów marketingowych, takich jak czas, pieniądze i personel, aby osiągnąć maksymalne wyniki.

Analiza finansowa

Metoda simpleks jest również użyteczna w analizie finansowej. Pozwala na optymalizację alokacji kapitału oraz wybór optymalnych inwestycji. Dzięki tej metodzie można dokładnie określić, jakie projekty inwestycyjne przyniosą największe zyski przy minimalnym ryzyku.

Przykładem zastosowania metody simpleks w analizie finansowej może być wybór portfela inwestycyjnego. Inwestor może mieć do wyboru różne aktywa, takie jak akcje, obligacje, nieruchomości itp. Korzystając z metody simpleks, można przeprowadzić analizę, aby ustalić optymalne proporcje alokacji kapitału do tych aktywów. Na podstawie wyników analizy inwestor może podjąć decyzję, które aktywa kupić lub sprzedać, aby maksymalizować swoje zyski przy minimalnym ryzyku.

Metoda simpleks może również być stosowana do analizy zdolności kredytowej przedsiębiorstw. Dzięki niej można określić, jakie projekty lub inwestycje przedsiębiorstwo może sobie pozwolić na podstawie swojej zdolności finansowej. Analiza simpleks pozwala na znalezienie optymalnej kombinacji działań, która zapewni przedsiębiorstwu stabilność finansową i wzrost.

Zarządzanie produkcją

W dziedzinie zarządzania produkcją metoda simpleks znajduje zastosowanie w optymalizacji procesów produkcyjnych oraz planowania produkcji. Jej celem jest zminimalizowanie kosztów produkcji przy jednoczesnym zwiększeniu wydajności.

Przykładem zastosowania metody simpleks w zarządzaniu produkcją może być optymalizacja planu produkcji. Przedsiębiorstwo może mieć do wykonania różne zadania produkcyjne, takie jak produkcja różnych produktów lub seryjna produkcja danego produktu. Korzystając z metody simpleks, można przeprowadzić analizę, aby określić optymalny plan produkcji, który minimalizuje koszty produkcji i maksymalizuje wydajność. Na podstawie wyników analizy można dostosować harmonogram produkcji, dostosować liczbę pracowników i zasobów, aby osiągnąć optymalne rezultaty.

Metoda simpleks może również być wykorzystywana do optymalizacji procesów produkcyjnych. Dzięki niej można znaleźć optymalne parametry procesu, takie jak prędkość produkcji, ilość surowców czy rozmiar partii produkcyjnych. Analiza simpleks pozwala na znalezienie optymalnej kombinacji tych parametrów, która zapewni maksymalną wydajność przy minimalnych kosztach.

Analiza wielokryterialna

Metoda simpleks jest również użyteczna w analizie wielokryterialnej. Pozwala na uwzględnienie różnych kryteriów i znalezienie optymalnych rozwiązań, które uwzględniają wszystkie te kryteria. Dzięki tej metodzie można dokładnie określić, jakie rozwiązania są najbardziej preferowane przy uwzględnieniu różnych aspektów.

Przykładem zastosowania metody simpleks w analizie wielokryterialnej może być wybór dostawcy. Przedsiębiorstwo może mieć do wyboru różnych dostawców, którzy oferują różne ceny, jakość, terminy dostaw itp. Korzystając z metody simpleks, można przeprowadzić analizę, aby określić optymalnego dostawcę, który spełnia wszystkie kryteria. Na podstawie wyników analizy przedsiębiorstwo może podjąć decyzję, który dostawca jest najlepszy dla jego potrzeb.

Metoda simpleks może również być stosowana do analizy projektów inwestycyjnych, gdzie istnieje wiele kryteriów do uwzględnienia, takich jak koszty, zyski, ryzyko itp. Dzięki niej można znaleźć optymalne rozwiązania, które uwzględniają wszystkie te kryteria i zapewniają maksymalne korzyści przy minimalnym ryzyku.

Inne dziedziny, w których metoda simpleks znajduje zastosowanie

Metoda simpleks ma szerokie zastosowanie nie tylko w powyższych dziedzinach, ale także w wielu innych obszarach. Może być wykorzystywana do optymalizacji logistyki, zarządzania łańcuchem dostaw, planowania transportu, analizy ryzyka, zarządzania zasobami ludzkimi i wielu innych.

W logistyce, metoda simpleks może być stosowana do optymalizacji tras transportowych, minimalizacji kosztów magazynowania i zarządzania zapasami. Dzięki niej można znaleźć optymalne rozwiązania, które zapewniają maksymalną wydajność i minimalizują koszty operacyjne.

W zarządzaniu łańcuchem dostaw, metoda simpleks może być wykorzystywana do optymalizacji procesów zaopatrzenia, dystrybucji i zarządzania zapasami. Dzięki niej można znaleźć optymalne rozwiązania, które minimalizują koszty i zapewniają płynność operacji.

W analizie ryzyka, metoda simpleks może być stosowana do oceny ryzyka i znalezienia optymalnych strategii zarządzania ryzykiem. Dzięki niej można znaleźć optymalne rozwiązania, które minimalizują ryzyko i maksymalizują korzyści.

Metoda simpleks znajduje również zastosowanie w zarządzaniu zasobami ludzkimi, gdzie może być stosowana do optymalizacji alokacji zasobów ludzkich, planowania harmonogramu pracy i zarządzania wynagrodzeniami. Dzięki niej można znaleźć optymalne rozwiązania, które zwiększają wydajność pracowników i minimalizują koszty.

Metoda simpleks — artykuły polecane

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

Bibliografia

• Dębski S. (2011), Ekonomika i organizacja przedsiębiorstw. Część 2, Wydawnictwa Szkolne i Pedagogiczne, Warszawa
• 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
• Hillier F., Libereman G. (2001), Introduction to Operations Research, Uniwersytet Stanforda, Stanford
• Kostrzewska M. (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 P. (2013), Wykłady z programowanie liniowego, Wydział Matematyki Stosowanej AGH, Kraków

Autor: Bartosz Karlikowski