Cykliczność

Zacznijmy od przykładu.

Przykład 3.4   Rozważmy słownik

$$\begin{array}{rrrrrr} x_4 & = & & -x_1 & - x_2 & + 3 x_3 ... ...3 \\ \hline z & = & 3 & + 2x_1 & - x_2 & - x_3 \end{array}$$ (3.25)

Rozwiązaniem bazowym tego słownika jest $x_1=x_2=x_3=x_4=x_6=0, x_5=2, z=3$. Zmienną wchodzącą będzie $x_1$, zaś zmienną wychodzącą może być $x_4$ lub $x_6$. Wybierzmy na przykład $x_4$. Nowym słownikiem będzie:

$$\begin{array}{rrrrrr} x_1 & = && x_2 & -3 x_3 & - x_4 \\ ... ...4 \\ \hline z & = & 3 & + x_2 & - 7x_3 & - 2x_4 \end{array}$$ (3.26)

Zauważmy więc, że na naszej operacji zamiany słownika nic nie zyskaliśmy w tym sensie, że wartość $z$ nie wzrosła.

Sytuacja w której zastąpienie jednej ze zmiennych bazowych zmienną niebazową według podanych przez nas reguł nie spowoduje zwiększenia wartości $z$ w rozwiązaniu bazowym może zajść tylko wtedy, gdy wartość jednej ze zmiennych w rozwiązaniu bazowym wynosi zero. W naszym przykładzie takimi zmiennymi były $x_4$ i $x_6$ dla słownika () i $x_1$ i $x_6$ dla słownika ().

Definicja 3.3   Mówimy, że rozwiązanie bazowe słownika jest zdegenerowane jeżeli co najmniej jedna zmienna bazowa w tym rozwiązaniu przyjmuje wartość zero. Odpowiedni słownik także nazywamy zdegenerowanym.

Przykład 3.4 (cd)   Czytelnik zechce sprawdzić, że następnym (po ()) słownikiem będzie

$$\begin{array}{rrrrrr} x_1 & = && 2x_3 & + x_4 & - x_6\\ ... ..._4 & - 4x_6\\ \hline z & = & 3 & -2x_3 &&-x_6 \end{array}$$

a więc simpleks doprowadził do rozwiązania optymalnego PPl (), rozwiązaniem optymalnym jest $x_1=x_2=x_3=x_4=x_6=0$, $x_5=2$, $z=3$.

Ponieważ przy przejściu ze słownika () do () rozwiązanie nie polepszyło się (wartość $z$ w tych słownikach jest taka sama) powstaje pytanie, czy może zaistnieć sytuacja w której po kilku zmianach słownika algorytm wróci do słownika który był już rozważany?
Odpowiedź na to pytanie brzmi tak! Jest jasne, że jeśli konsekwentnie według jakiejś reguły wybieramy zmienne wchodzące i wychodzące i na jeden i ten sam słownik wpadamy dwa razy, wtedy algorytm będzie już gonił w piętkę, te same słowniki będą sie pojawiały cyklicznie.
Zauważmy od razu, że taka sytuacja może się pojawić tylko wtedy gdy pojawi się słownik zdegenerowany - jeśli nie, to w każdej iteracji rozwiązanie bazowe jest inne, różni się od wszystkich poprzednich wartością $z$ chociażby.
W przykładzie oba słowniki () i () są zdegenerowane. Czytelnik zechce sprawdzić, że przykład Chvátala [3] zaproponowany poniżej jako ćwiczenie jest problemem PL w którym po kilku odpowiednio przeprowadzonych iteracjach wracamy do wyjściowego słownika ^3.3.
Z twierdzenia wynika w szczególności, że każde rozwiązanie bazowe jest rozwiązaniem każdego innego słownika (nie tylko tego którego jest rozwiązaniem bazowym). Stąd zaś, że wszystkich możliwych rozwiązań bazowych dla PPL jest tyle na ile sposobów można wybrać $n$ elementów (zmiennych bazowych) spośród $n+m$ elementów (tyle jest wszystkich zmiennych), a więc $\left( \begin{array}{c} m+n\\ n \end{array} \right)$. Tak więc słowników dla danego PPL jest skończona liczba $\left( \begin{array}{c} m+n\\ n \end{array} \right)$ i jeśli w każdej iteracji otrzymujemy inny słownik, wtedy algorytm simpleks musi nas doprowadzić do rozwiązania problemu w skończonej liczbie iteracji (co najwyżej $\left( \begin{array}{c} m+n\\ n \end{array} \right)$). Wykazaliśmy więc twierdzenie:

Twierdzenie 3.2   Jeśli algorytm simpleks nie goni w piętkę^3.4, to rozwiązuje PPL w skończonej liczbie iteracji. Co więcej, jeśli problem jest niesprzeczny i ograniczony, to istnieje rozwiązanie bazowe które jest równocześnie rozwiązaniem optymalnym.