Czy simpleks może się zaciąć?

Działanie algorytmu polega na wykonywaniu następujących kroków:

1. Wybór zmiennej bazowej wchodzącej.
   Przypomnijmy, że nową zmienną wchodzącą jest zmienna $\bar{x}_{j_{0}}$ taka, że $\bar{c}_{j_{0}} > 0$. Jeśli jest więcej niż jedna taka zmienna, można, jak to robiliśmy w przykładach, wybrać tę dla której dodatnie $\bar{c}_{j_0}$ jest największe (z nadzieją - ale bez gwarancji - że taki wybór nas najszybciej doprowadzi do celu).
   Jeśi taki wybór jest niemożliwy to wszystkie współczynniki $\bar{c}_j$ dla $j=1,...,n$ we wzorze
   
   $$z = a + \bar{c}_1\bar{x}_1 + ... +\bar{c}_n\bar{x}_n$$
   
   
   są ujemne. To zaś oznacza, że rozwiązanie dopuszczalne stowarzyszone ze słownikiem dopuszczalnym jest optymalne (w szczególności maksymalna wartość $z$ jest równa $a$).
2. Wybór zmiennej wychodzącej.
   Jako zmienną wychodzącą przyjmujemy tę która daje najostrzejsze ograniczenie od góry na zmienną wchodzącą $x_{j_0}$.
   Na przykład, dla słownika dopuszczalnego
   
   $$\begin{array}{lcrrrr} x_3 & = & 5 & - x_1 & + x_2 & - x_4\... ...\ \hline z & = & 15 & + 2x_1 & - x_2 & - x_4\\ \end{array}$$
   
   
   zmienną wchodzącą jest $x_1$. Nierówności $x_3 \geq 0$ i $x_5 \geq 0$ dają dla odpowiedniego rozwiązania dopuszczczalnego (tj. takiego w którym $x_2=x_4=0$) ograniczenia następujące:
   
   $$x_3 \geq 0 \Rightarrow x_1 \leq 5, \hspace{1cm} x_5 \geq 0 \Rightarrow x_1 \leq 3$$
   
   
   Wybieramy zmienną wychodzącą $x_5$.
   Jeśli na wartości zmiennej wchodzącej nie otrzymujemy ograniczenia od góry, jak w przykładzie słownika
   
   $$\begin{array}{lcrrrr} x_3 & = & 5 & + x_1 & - x_2 & + x_4\... ...\ \hline z & = & 15 & + 2x_1 & - x_2 & - x_4\\ \end{array}$$
   
   
   czyli jeśli współczynniki przy $x_{j_0}$ są nieujemne, to wartość $z$ jest oczywiście nieograniczona od góry. Nie ma rozwiązania maksymalnego, $z$ może być dowolnie duże.
3. Tworzenie nowego słownika
   W tym kroku algorytmu tworzymy nowy słownik przy pomocy prostych operacji arytmetycznych.

Ostatecznie na pytanie czy simpleks może się zaciąć? postawione w tytule niniejszego ustępu odpowiedź brzmi nie. Nie w tym sensie, że w każdym momencie swojego działanie algorytm albo poda rozwiązanie problemu (tzn rozwiązanie optymalne lub informację, że problem jest sprzeczny lub nieograniczony), albo będzie wykonywał następne kroki. Czy to oznacza, że wszystko musi się dobrze skończyć? Zobaczymy zaraz, że niekoniecznie.