Metoda simpleks — algorytm rozwiązywania zadań programowania liniowego

Mgr inż.

Sebastian Dziarmaga-Działyński

Wirtualna kancelaria korepetytorska i konsultacyjna – wszechwiedza.pl

Metoda simpleks jest jednym z najważniejszych algorytmów rozwiązywania zadań programowania liniowego. Jej idea jest prosta, ale zarazem niezwykle skuteczna: zamiast sprawdzać wszystkie punkty obszaru dopuszczalnego, metoda simpleks przechodzi od jednego wierzchołka tego obszaru do następnego, wybierając taki kierunek, który poprawia albo przynajmniej nie pogarsza wartości funkcji celu.

W artykule o metodzie graficznej programowania liniowego widzieliśmy, że optimum zadania liniowego znajduje się zwykle w jednym z wierzchołków obszaru dopuszczalnego. Metoda simpleks wykorzystuje dokładnie tę obserwację, ale robi to algebraicznie, bez konieczności rysowania obszaru dopuszczalnego. Dzięki temu działa również w zadaniach z większą liczbą zmiennych, których nie da się już przedstawić na płaszczyźnie.

Metoda ta została opracowana przez George’a Dantziga i do dziś należy do klasycznych narzędzi badań operacyjnych, optymalizacji oraz ekonomii matematycznej. Mimo że współczesne programy komputerowe korzystają z wielu zaawansowanych wariantów algorytmów optymalizacyjnych, zrozumienie metody simpleks pozostaje bardzo ważne, ponieważ pokazuje, co naprawdę dzieje się podczas rozwiązywania zadania programowania liniowego.

Czym jest metoda simpleks?

Metoda simpleks jest algorytmem iteracyjnym. Oznacza to, że nie otrzymujemy rozwiązania w jednym kroku, lecz przechodzimy przez kolejne tabele simpleksowe. Każda tabela opisuje pewne rozwiązanie bazowe, czyli algebraiczny odpowiednik jednego z wierzchołków obszaru dopuszczalnego.

Jeżeli aktualne rozwiązanie nie jest jeszcze optymalne, metoda wskazuje, która zmienna powinna wejść do bazy i która zmienna powinna z tej bazy wyjść. Po przekształceniu tabeli otrzymujemy nowe rozwiązanie bazowe. W zadaniu maksymalizacji powinno ono dawać wartość funkcji celu nie mniejszą niż poprzednie rozwiązanie, a w typowych sytuacjach — większą.

Właśnie w tym tkwi pewna genialność metody simpleks. Algorytm nie sprawdza wszystkich możliwych rozwiązań. Nie porusza się również przypadkowo. W sposób uporządkowany przechodzi od jednej bazy do drugiej, czyli od jednego wierzchołka obszaru dopuszczalnego do wierzchołka sąsiedniego, szukając poprawy wartości funkcji celu.

Skąd pochodzi nazwa simpleks?

Samo słowo simpleks oznacza najprostszy wielowymiarowy odpowiednik odcinka, trójkąta i czworościanu. W wymiarze pierwszym simpleksem jest odcinek, w wymiarze drugim — trójkąt, w wymiarze trzecim — czworościan. W wymiarze \(n\) simpleks jest figurą wyznaczoną przez \(n+1\) odpowiednio niezależnych wierzchołków.

Nazwa metody simpleks nawiązuje więc do geometrii wielowymiarowej. Nie należy jednak rozumieć tej metody jako zwykłego rysowania trójkątów czy czworościanów. W praktyce metoda simpleks jest procedurą algebraiczną, która operuje na tabelach i bazach. Jej geometryczny sens polega na przemieszczaniu się po wierzchołkach wielościanu rozwiązań dopuszczalnych.

Związek metody simpleks z metodą graficzną

Metoda graficzna i metoda simpleks opisują tę samą ideę z dwóch różnych stron. W metodzie graficznej widzimy obszar dopuszczalny na rysunku, zaznaczamy jego wierzchołki i przesuwamy prostą funkcji celu. W metodzie simpleks nie rysujemy już tego obszaru, ale wykonujemy operacje rachunkowe, które odpowiadają przechodzeniu między jego wierzchołkami.

Każda baza w metodzie simpleks odpowiada pewnemu rozwiązaniu bazowemu. Jeżeli rozwiązanie to jest dopuszczalne, możemy interpretować je geometrycznie jako wierzchołek obszaru dopuszczalnego. Zmiana bazy oznacza przejście do innego wierzchołka. W przypadku degeneracji może się zdarzyć, że baza się zmienia, ale geometrycznie pozostajemy w tym samym wierzchołku.

Dzięki temu metoda simpleks jest naturalnym uogólnieniem metody graficznej. W dwóch zmiennych możemy zobaczyć wszystko na rysunku. W większej liczbie zmiennych rysunek przestaje być możliwy, ale algebraiczna idea przechodzenia po wierzchołkach nadal działa.

Od postaci klasycznej do postaci standardowej

Metodę simpleks najwygodniej stosować wtedy, gdy zadanie jest zapisane w postaci równań, a wszystkie prawe strony są nieujemne. Tymczasem zadania programowania liniowego często zapisuje się początkowo w postaci nierówności. Przykładowo:

\[ \begin{aligned} \max \quad & Z = 4x_1+3x_2 \\ \text{przy warunkach} \quad & 2x_1+x_2 \le 10, \\ & x_1+2x_2 \le 12, \\ & x_1,x_2 \ge 0. \end{aligned} \]

Aby przejść do postaci standardowej, zamieniamy nierówności na równania. W przypadku ograniczeń typu \(\le\) dodajemy zmienne dodatkowe, nazywane też zmiennymi bilansującymi:

\[ \begin{aligned} 2x_1+x_2+s_1 &= 10, \\ x_1+2x_2+s_2 &= 12, \\ x_1,x_2,s_1,s_2 &\ge 0. \end{aligned} \]

Zmienne \(s_1\) i \(s_2\) oznaczają niewykorzystane zasoby, czyli zapasy w ograniczeniach. Jeżeli na przykład \(s_1=0\), pierwsze ograniczenie jest aktywne. Jeżeli \(s_1>0\), oznacza to, że w pierwszym ograniczeniu pozostał niewykorzystany zapas.

W funkcji celu zmienne dodatkowe mają współczynniki równe zero, ponieważ same w sobie nie wpływają na wartość optymalizowanego kryterium:

\[ Z = 4x_1+3x_2+0s_1+0s_2. \]

Postać bazowa zadania programowania liniowego

Postać bazowa to taka postać układu równań, w której w każdym równaniu występuje zmienna ze współczynnikiem równym jeden, która nie występuje w pozostałych równaniach. Mówiąc inaczej: w macierzy współczynników możemy wskazać kolumny tworzące macierz jednostkową.

W naszym przykładzie po dodaniu zmiennych \(s_1\) i \(s_2\) otrzymujemy układ:

\[ \begin{aligned} 2x_1+x_2+s_1 &= 10, \\ x_1+2x_2+s_2 &= 12. \end{aligned} \]

Zmienna \(s_1\) występuje z jedynką w pierwszym równaniu i nie występuje w drugim. Zmienna \(s_2\) występuje z jedynką w drugim równaniu i nie występuje w pierwszym. Dlatego \(s_1\) i \(s_2\) mogą utworzyć bazę początkową.

Jeżeli przyjmiemy zmienne niebazowe \(x_1=0\), \(x_2=0\), to otrzymujemy:

\[ s_1=10, \quad s_2=12. \]

Ponieważ prawe strony są nieujemne, otrzymane rozwiązanie bazowe jest dopuszczalne. To ważne: klasyczna tabela simpleksowa startuje od rozwiązania bazowego dopuszczalnego. Jeżeli prawa strona któregoś równania byłaby ujemna, należałoby najpierw uporządkować zadanie, na przykład mnożąc odpowiednie równanie przez \(-1\) albo stosując procedurę ze zmiennymi sztucznymi.

Zmienne dodatkowe, nadwyżkowe i sztuczne

Przy sprowadzaniu zadania do postaci odpowiedniej dla metody simpleks trzeba rozróżniać kilka rodzajów zmiennych technicznych.

Zmienne sztuczne nie są elementem rzeczywistego modelu. Są narzędziem rachunkowym, które pomaga uzyskać bazę początkową. W dalszej części obliczeń powinny zostać usunięte z rozwiązania. Jeżeli po zakończeniu procedury pomocniczej jakaś zmienna sztuczna ma dodatnią wartość, oznacza to, że pierwotne zadanie nie ma rozwiązania dopuszczalnego.

Warto również odróżnić te pojęcia od zmiennej nieograniczonej co do znaku, czyli zmiennej bez narzuconego warunku nieujemności. Taka zmienna może przyjmować wartości dodatnie, ujemne i zero. Nie jest ona tym samym co zmienna bilansująca ani sztuczna.

Tabela simpleksowa

Tabela simpleksowa porządkuje wszystkie informacje potrzebne do wykonania kolejnych kroków algorytmu. W najczęściej spotykanej konwencji zawiera między innymi kolumnę kosztów bazowych \(C_B\), kolumnę zmiennych bazowych, współczynniki przy zmiennych, prawą stronę \(b_i\), wiersz \(z_j\), wiersz wskaźników optymalności \(\Delta_j\) oraz kolumnę ilorazów wyjścia.

W tym artykule przyjmujemy konwencję:

\[ \Delta_j = c_j-z_j. \] 

W niektórych podręcznikach można spotkać odwrotny zapis \(z_j-c_j\). Nie oznacza to, że metoda jest inna. Zmieniają się tylko znaki w kryterium optymalności. Ważne jest, aby w całym rozwiązaniu konsekwentnie trzymać się jednej konwencji.

W tabeli zaznaczono kolumnę główną, wiersz główny oraz element główny. Kolumna główna wskazuje zmienną wchodzącą do bazy. Wiersz główny wskazuje zmienną wychodzącą z bazy. Element główny znajduje się na przecięciu kolumny głównej i wiersza głównego.

Kryterium optymalności

Przy konwencji \(\Delta_j=c_j-z_j\) kryterium optymalności zależy od tego, czy rozwiązujemy zadanie maksymalizacji, czy minimalizacji. Metoda simpleks nie jest ograniczona tylko do jednego z tych przypadków. To, czy rozwiązujemy maksimum, czy minimum, wpływa na sposób interpretacji wskaźników optymalności.

W części opracowań metoda simpleks jest przedstawiana wyłącznie dla zadań maksymalizacji albo wyłącznie dla zadań minimalizacji. Nie oznacza to jednak, że sama metoda działa tylko w jednym z tych przypadków. Różnica polega na przyjętej konwencji zapisu oraz na odpowiednim kryterium wyboru zmiennej wchodzącej do bazy.

Zmienna wchodząca i zmienna wychodząca z bazy

W zadaniu maksymalizacji, przy konwencji \(\Delta_j=c_j-z_j\), do bazy wchodzi zwykle zmienna o największej dodatniej wartości \(\Delta_j\). Taka zmienna daje największą jednostkową poprawę funkcji celu spośród aktualnie rozważanych możliwości.

Po wybraniu kolumny głównej trzeba zdecydować, która zmienna opuści bazę. W tym celu liczymy ilorazy wyjścia:

\[ \frac{b_i}{a_{ij}}, \]

ale tylko dla dodatnich elementów kolumny głównej. Jeżeli element w kolumnie głównej jest zerowy albo ujemny, w danym wierszu wpisujemy kreskę i nie bierzemy tego wiersza pod uwagę przy wyborze zmiennej wychodzącej.

Wybieramy najmniejszy dodatni iloraz wyjścia. Dzięki temu po wykonaniu przekształcenia simpleksowego nie otrzymamy ujemnej wartości po prawej stronie. Innymi słowy: kryterium wyjścia chroni dopuszczalność rozwiązania bazowego.

Jeżeli wybraliśmy kolumnę główną, ale w tej kolumnie nie ma żadnego dodatniego elementu, nie da się wyznaczyć ilorazu wyjścia. Oznacza to, że funkcję celu można poprawiać bez ograniczenia, a zadanie nie ma skończonego rozwiązania optymalnego.

Przykład 1. Zadanie bez zmiennych sztucznych

Rozwiążmy zadanie:

\[ \begin{aligned} \max \quad & Z = 4x_1+3x_2 \\ \text{przy warunkach} \quad & 2x_1+x_2 \le 10, \\ & x_1+2x_2 \le 12, \\ & x_1,x_2 \ge 0. \end{aligned} \]

Dodajemy zmienne bilansujące \(s_1\) i \(s_2\):

\[ \begin{aligned} 2x_1+x_2+s_1 &= 10, \\ x_1+2x_2+s_2 &= 12. \end{aligned} \]

Początkową bazę tworzą zmienne \(s_1\) i \(s_2\). Otrzymujemy pierwszą tabelę simpleksową:

Największa dodatnia wartość \(\Delta_j\) znajduje się w kolumnie \(x_1\), dlatego \(x_1\) wchodzi do bazy. Ilorazy wyjścia wynoszą \(10/2=5\) oraz \(12/1=12\). Najmniejszy dodatni iloraz to 5, więc z bazy wychodzi \(s_1\). Elementem głównym jest liczba 2.

Po przekształceniu tabeli otrzymujemy:

W wierszu \(\Delta_j\) nadal występuje dodatnia wartość: \(\Delta_2=1\). Do bazy wchodzi więc \(x_2\). Ilorazy wyjścia liczymy tylko dla dodatnich elementów kolumny \(x_2\). Otrzymujemy \(5/(1/2)=10\) oraz \(7/(3/2)=14/3\). Z bazy wychodzi \(s_2\).

Po drugim przekształceniu otrzymujemy tabelę końcową:

Wszystkie wartości \(\Delta_j\) są niedodatnie, więc dla zadania maksymalizacji rozwiązanie jest optymalne. Odczytujemy:

\[ x_1=\frac{8}{3}, \quad x_2=\frac{14}{3}, \quad Z_{\max}=\frac{74}{3}. \]

Przykład 2. Zadanie ze zmienną sztuczną

Zmienne sztuczne pojawiają się wtedy, gdy po sprowadzeniu ograniczeń do równań nie mamy oczywistej bazy początkowej. Rozważmy na przykład ograniczenie typu \(\ge\):

\[ x_1+x_2 \ge 4. \] 

Aby zamienić je na równanie, odejmujemy zmienną nadwyżkową \(s_1\):

\[ x_1+x_2-s_1=4. \]

Kolumna zmiennej \(s_1\) ma jednak współczynnik \(-1\), więc nie daje nam naturalnej kolumny bazowej. Dlatego wprowadzamy zmienną sztuczną \(a_1\):

\[ x_1+x_2-s_1+a_1=4. \]

Zmienna \(a_1\) służy tylko do rozpoczęcia obliczeń. W metodzie wielkiej kary otrzymuje bardzo niekorzystny współczynnik w funkcji celu, a w metodzie dwóch faz najpierw minimalizujemy sumę zmiennych sztucznych. W obu podejściach chodzi o to samo: zmienne sztuczne powinny zostać usunięte z rozwiązania, jeżeli zadanie pierwotne jest dopuszczalne.

Metoda „wielkiej kary”

Jednym ze sposobów radzenia sobie ze zmiennymi sztucznymi jest metoda nazywana często metodą wielkiej kary. Nazwa jest dość obrazowa: zmiennej sztucznej nadajemy w funkcji celu bardzo niekorzystny współczynnik, czyli nakładamy na nią dużą „karę”. Dzięki temu algorytm simpleks będzie dążył do usunięcia tej zmiennej z bazy, o ile tylko jest to możliwe.

Załóżmy, że rozwiązujemy zadanie maksymalizacji. Jeżeli do ograniczenia musimy wprowadzić zmienną sztuczną \(a_1\), to w funkcji celu wpisujemy ją z bardzo dużym ujemnym współczynnikiem:

\[ Z = 4x_1+3x_2 - M a_1. \]

gdzie \(M\) oznacza bardzo dużą dodatnią liczbę. W zadaniu maksymalizacji obecność zmiennej \(a_1\) obniża wartość funkcji celu, dlatego algorytm będzie próbował doprowadzić do sytuacji, w której \(a_1=0\). Gdybyśmy rozwiązywali zadanie minimalizacji, znak kary byłby przeciwny: zmienna sztuczna otrzymałaby bardzo duży dodatni współczynnik, aby jej obecność silnie zwiększała wartość minimalizowanej funkcji celu.

Ogólna zasada jest więc następująca: zmiennym sztucznym nadajemy bardzo duże wagi działające przeciwnie do kierunku optymalizacji. W maksymalizacji są to bardzo duże współczynniki ujemne, a w minimalizacji — bardzo duże współczynniki dodatnie. Zmienna sztuczna ma być dla algorytmu „nieopłacalna”, ponieważ nie opisuje rzeczywistej decyzji ani rzeczywistego zasobu. Jest jedynie technicznym narzędziem pozwalającym rozpocząć obliczenia od postaci bazowej.

Rozważmy przykładowe ograniczenie:

\[ x_1+x_2 \ge 4. \]

Po przejściu do równania odejmujemy zmienną nadwyżkową \(s_1\):

\[ x_1+x_2-s_1=4. \]

Nie mamy jednak jeszcze wygodnej zmiennej bazowej, ponieważ współczynnik przy \(s_1\) wynosi \(-1\). Wprowadzamy więc zmienną sztuczną \(a_1\):

\[ x_1+x_2-s_1+a_1=4. \]

Zmienna \(a_1\) może utworzyć bazę początkową, ponieważ występuje w tym równaniu ze współczynnikiem 1. Jej obecność nie oznacza jednak, że należy do rzeczywistego modelu. Jest to tylko „rusztowanie” rachunkowe, które chcemy usunąć w toku działania algorytmu.

Jeżeli zadanie pierwotne ma rozwiązanie dopuszczalne, algorytm simpleks powinien doprowadzić do wyzerowania zmiennej sztucznej. Jeżeli natomiast po zakończeniu obliczeń zmienna sztuczna nadal ma dodatnią wartość, oznacza to, że bez niej nie da się spełnić pierwotnych ograniczeń. W takim przypadku zadanie jest niedopuszczalne.

Trzeba przy tym pamiętać o ważnym niuansie: sama obecność zmiennej sztucznej w bazie nie przesądza jeszcze o sprzeczności zadania. Jeżeli zmienna sztuczna pozostała w bazie, ale ma wartość równą zero, rozwiązanie jest zdegenerowane, ale może być dopuszczalne. O niedopuszczalności mówimy dopiero wtedy, gdy zmienna sztuczna ma dodatnią wartość.

Metoda dwufazowa

Alternatywą dla metody wielkiej kary jest metoda dwufazowa. Jej idea jest podobna, ale zamiast wprowadzać bardzo dużą stałą \(M\), rozdzielamy obliczenia na dwa etapy.

W pierwszej fazie tworzymy pomocniczą funkcję celu, której zadaniem jest usunięcie zmiennych sztucznych z rozwiązania. Najczęściej minimalizujemy sumę zmiennych sztucznych:

\[ \min \quad a_1+a_2+\ldots+a_k. \]

Jeżeli minimum tej funkcji pomocniczej jest większe od zera, oznacza to, że przynajmniej jedna zmienna sztuczna musi pozostać dodatnia. Wtedy zadanie pierwotne jest niedopuszczalne. Jeżeli minimum wynosi zero, przechodzimy do drugiej fazy, w której rozwiązujemy już właściwe zadanie z pierwotną funkcją celu.

Metoda dwufazowa bywa rachunkowo bardziej przejrzysta, ponieważ nie wymaga operowania symbolem \(M\) ani bardzo dużymi liczbami. Metoda wielkiej kary jest natomiast wygodna dydaktycznie, bo od razu pokazuje, że zmienne sztuczne są w modelu czymś niepożądanym i algorytm powinien się ich pozbyć, o ile tylko pozwalają na to ograniczenia.

Degeneracja, zmienne sztuczne i dopuszczalność

Bardzo ważny niuans dotyczy sytuacji, w której zmienna sztuczna pozostaje w bazie. Sama obecność zmiennej sztucznej w bazie nie oznacza jeszcze, że zadanie jest sprzeczne. Trzeba sprawdzić jej wartość po prawej stronie tabeli.

Jeżeli zmienna sztuczna jest bazowa, ale jej wartość wynosi zero, mamy do czynienia z rozwiązaniem zdegenerowanym. Taka sytuacja nie przekreśla dopuszczalności zadania. Oznacza tylko, że baza zawiera zmienną o wartości zerowej. Geometrycznie algorytm może wtedy zmienić bazę, ale pozostać w tym samym wierzchołku obszaru dopuszczalnego.

Niedopuszczalność zadania stwierdzamy dopiero wtedy, gdy po zakończeniu etapu pomocniczego zmienna sztuczna ma wartość dodatnią. Wtedy nie da się spełnić pierwotnych ograniczeń bez korzystania ze zmiennej, która została wprowadzona wyłącznie sztucznie.

Przykład 3. Zadanie niedopuszczalne

Zadanie niedopuszczalne to takie zadanie, w którym układ ograniczeń jest sprzeczny. Nie istnieje żaden punkt spełniający wszystkie warunki jednocześnie. Przykładowo warunki:

\[ x_1+x_2 \le 2, \] 

\[ x_1+x_2 \ge 5, \] 

nie mogą być jednocześnie spełnione. Geometrycznie obszar dopuszczalny jest pusty. W procedurze simpleksowej ze zmiennymi sztucznymi objawi się to tym, że po zakończeniu fazy pomocniczej co najmniej jedna zmienna sztuczna pozostanie z dodatnią wartością.

Zobaczmy, jak taka sytuacja wygląda rachunkowo. Dla ograniczeń:

\[ x_1+x_2 \le 2, \]

\[ x_1+x_2 \ge 5 \]

po przejściu do równań otrzymujemy:

\[ x_1+x_2+s_1=2, \]

\[ x_1+x_2-s_2+a_1=5. \]

Pierwsze równanie ma naturalną zmienną bazową \(s_1\). W drugim równaniu po odjęciu zmiennej nadwyżkowej \(s_2\) musimy wprowadzić zmienną sztuczną \(a_1\), aby uzyskać bazę początkową.

W fazie pomocniczej próbujemy sprowadzić zmienną sztuczną do zera. W tym przykładzie nie jest to możliwe. Największa wartość sumy \(x_1+x_2\), jaka wynika z pierwszego ograniczenia, to 2, natomiast drugie ograniczenie wymaga, aby ta suma była co najmniej równa 5. Brakuje więc 3 jednostek. Tę sprzeczność widać w końcowej tabeli fazy pomocniczej:

W tabeli końcowej zmienna sztuczna \(a_1\) nadal jest zmienną bazową i ma wartość dodatnią: \(a_1=3\). Oznacza to, że nawet po najlepszym możliwym dobraniu zmiennych decyzyjnych nie da się spełnić pierwotnych ograniczeń bez korzystania ze zmiennej sztucznej. Zadanie jest więc niedopuszczalne.

Przykład 4. Zadanie bez skończonego optimum

Inna szczególna sytuacja występuje wtedy, gdy zadanie jest dopuszczalne, ale funkcję celu można poprawiać bez ograniczenia. Mówimy wtedy, że zadanie nie ma skończonego rozwiązania optymalnego.

W tabeli simpleksowej rozpoznajemy to następująco: istnieje zmienna, która powinna wejść do bazy, ponieważ jej wskaźnik optymalności wskazuje możliwość poprawy funkcji celu, ale w jej kolumnie nie ma żadnego dodatniego elementu. Nie da się więc obliczyć żadnego dodatniego ilorazu wyjścia.

W kolumnie \(x_1\) mamy dodatnią wartość \(\Delta_j\), więc dla zadania maksymalizacji zmienna \(x_1\) mogłaby poprawić funkcję celu. W tej kolumnie nie ma jednak żadnego dodatniego współczynnika w wierszach ograniczeń. Nie można więc wyznaczyć zmiennej wychodzącej z bazy. Jest to sygnał, że zadanie nie ma skończonego optimum.

Co dalej? Analiza postoptymalizacyjna

Ostatnia tabela simpleksowa zawiera więcej informacji niż tylko wartości zmiennych decyzyjnych i wartość funkcji celu. Można z niej odczytać także informacje przydatne w analizie postoptymalizacyjnej, na przykład wrażliwość rozwiązania na zmiany współczynników funkcji celu lub prawych stron ograniczeń.

W praktycznych zastosowaniach jest to bardzo ważne. Często nie wystarczy wiedzieć, jakie rozwiązanie jest optymalne dla jednego zestawu danych. Chcemy również wiedzieć, co stanie się, gdy zmieni się dostępność zasobów, cena produktu albo koszt jednostkowy. Tego typu zagadnienia omówimy jednak osobno w artykule poświęconym analizie postoptymalizacyjnej.

Podsumowanie

Metoda simpleks jest algebraicznym sposobem przechodzenia po wierzchołkach obszaru dopuszczalnego. Każda baza odpowiada pewnemu rozwiązaniu bazowemu, a każda iteracja polega na wyborze zmiennej wchodzącej do bazy, wyborze zmiennej wychodzącej z bazy oraz przekształceniu tabeli simpleksowej.

W klasycznej konwencji stosowanej w tym artykule obliczamy wiersz \(z_j\), a następnie wskaźniki optymalności \(\Delta_j=c_j-z_j\). Dla zadania maksymalizacji rozwiązanie jest optymalne, gdy wszystkie wskaźniki \(\Delta_j\) są niedodatnie. Jeżeli istnieje dodatni wskaźnik, można poprawić wartość funkcji celu.

Wybór zmiennej wychodzącej z bazy odbywa się na podstawie najmniejszego dodatniego ilorazu wyjścia. Dzięki temu zachowujemy nieujemność prawych stron, czyli dopuszczalność kolejnego rozwiązania bazowego.

Warto pamiętać także o sytuacjach szczególnych. Jeżeli po fazie pomocniczej zmienna sztuczna ma dodatnią wartość, zadanie jest niedopuszczalne. Jeżeli natomiast zmienna sztuczna pozostaje w bazie z wartością zero, mamy rozwiązanie zdegenerowane, ale nadal dopuszczalne. Jeżeli zaś istnieje zmienna poprawiająca funkcję celu, lecz nie można wyznaczyć ilorazu wyjścia, zadanie nie ma skończonego optimum.

Utworzono: 19.05.2026

Powiązane artykuły

• Programowanie liniowe – metoda graficzna 
• Dualność w programowaniu liniowym — zadanie prymalne, zadanie dualne i warunki komplementarności 

Masz problem z tym tematem?

Wszechwiedza.pl pomaga zrozumieć matematykę, statystykę, ekonometrię, badania operacyjne, analizę danych, mechanikę i wiele innych przedmiotów — spokojnie, konkretnie i krok po kroku. 

Zapytaj o pomoc