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 te same słowniki będą sie pojawiały cyklicznie (będziemy wtedy też mówić, że algorytm zapętla się.
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 [4] zaproponowany poniżej jako ćwiczenie jest problemem PL w którym po kilku odpowiednio przeprowadzonych iteracjach wracamy do wyjściowego słownika ^3.1.
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 zapętla się^3.2, 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.

Wśród metod unikania cykliczności elegancją ^3.3 wyróżnia się reguła R.G. Blanda [2] zwana także regułą najmniejszego indeksu.
Reguła Blanda.

1. Wybierz jako zmienną wchodzącą tę zmienną która

   (i)

   ma dodatni współczynnik we wzorze na $z$,

   (ii)

   spośród wszystkich zmiennych o dodatnim współczynniku we wzorze na $z$ ma najmniejszy indeks.

2. Wybierz jako zmienną wychodzącą tę która

   (iii)

   powoduje najsilniejsze ograniczenie od góry dla zmiennej wchodzącej,

   (iv)

   spośród wszystkich kandydatów na zmienną wychodzącą (tj zmiennych bazowych spełniających (iii)) ma najmniejszy indeks.
   

Regułę Blanda można podać nieco bardziej formalnie w sposób następujący.
Niech będzie dany słownik

$$\begin{array}{llllll} x_i & = & b_i & - &\sum_{j \notin B... ...hline z & = & z_0 & + & \sum_{j \notin B}c_jx_j \end{array}$$ (3.27)

(w słowniku () $B$ jest zbiorem indeksów zmiennych bazowych).

-

Wybierz jako zmienną wchodzącą $x_{j_{0}}$ dla której

(a)

$c_{j_{0}} > 0$

(b)

$j_0 = \mbox{min}\{ j: j \notin B \wedge c_j > 0 \}$

-

Wybierz jako zmienną wychodzącą $x_{i_{0}}$ dla której

(a)

$a_{{i_{0}}{j_0}} > 0$

(b)

$\frac{b_{i_{0}}}{a_{{i_{0}}{j_{0}}}} = \mbox{min}\{ \frac{b_i}{a_{{i}{j_{0}}}}: a_{ij_{0}}>0, i=1,...,m \} =a$

(c)

$i_0 = \mbox{min}\{i: i \in B \wedge \frac{b_i}{a_{{i}{j_{0}}}} = a\}$

W porównaniu z metodą którą stosowaliśmy do tej pory różnica pojawia się tylko w punkcie (ii) - stosujemy tę regułe zamiast wybierać zmienną wchodzącą o największym współczynniku (dodatnim) w funkcji celu.

Przykład 3.5   Dla słownika

$$\begin{array}{lrrrr} x_4 & = 4 & + x_1 & + 2x_2 & - x_3\\ ... ..._3 \\ \hline z & = 1 & - x_1 & + 2x_2 & + 3 x_3 \end{array}$$

postępując według reguły Blanda wybierzemy $x_2$ jako zmienną wchodzącą i $x_5$ jako zmienną wychodzącą.

Twierdzenie 3.3 (Bland [2])   Jeśli wybory zmiennych wchodzących i wychodzących w algorytmie simpleks dokonywane są według reguły Blanda, to algorytm kończy się po skończonej liczbie iteracji.

Idea dowodu twierdzenia Blanda zaczerpnięta jest z [4].
Dowód. Ze względu na twierdzenie wystarczy wykazać, że jeżeli zmienne wchodząca i wychodząca będą wybierane według reguły Blanda to nie może wystąpić cykliczność .
Dla dowodu nie wprost przypuśćmy, że zmienne są wybierane regułą Blanda, a jednak algorytm zapętla się. to znaczy, że poczynając od pewnego słownika $S_1$ w kolejnych iteracjach otrzymujemy $k$-elementowy ciąg słowników
$S_1, S_2, ... , S_{k-1}, S_k$ taki,że $k>1$ i $S_k=S_1$. Oczywiście wszystkie słowniki $S_1,...,S_{k-1}$ są wtedy zdegenerowane.
Zmienną będziemy nazywali błędną^3.4 jeżeli dla pewnych słowników spośród $S_1,...,S_{k-1}$ jest zmienną bazową a dla innych niebazową.
Przypuśćmy, że $x_t$ jest zmienną błędną o największym inteksie $t$. Niech $S$ będzie jednym ze słowników $S_1, S_2, ... , S_{k-1}, S_k$, takim, że $x_t$ jest zmienną bazową wychodzącą słownika $S$ i niech $x_s$ będzie zmienną wchodzącą $S$. Inaczej mówiąc: $x_t$ i $x_s$ są takie, że

-

$x_t$ jest zmienną bazową $S$ i nie jest zmienną bazową słownika następnego,

-

$x_s$ jest zmienną niebazową słownika $S$ i bazową słownika następnego.

Oznaczmy przez $B$ zbiór indeksów zmiennych bazowych słownika $S$ i powiedzmy, że $S$ jest postaci

$$\begin{array}{rrrrrr} x_i & = & b_i & - & \sum_{i \notin B... ... \hline z & = & w & + & \sum_{j \notin B}c_jx_j \end{array}$$ (3.28)

Skoro $S_1,...,S_{k-1}, S_k$ jest cyklem, tzn $S_k=S_1$, musi istnieć inny słownik, nazwijmy go $S^*$ taki, że $x_t$ jest zmienną wchodzącą $S^*$. Z tego samego powodu wartość zmiennej $z$ (funkcji celu) w rozwiązaniu bazowym każdego słownika $S_1,...,S_{k-1}, S_k$ jest taka sama. Tak więc wzór na $z$ w słowniku $S^*$ jest postaci

$$z = w + \sum_{j=1}^{m+n}c^*_jx_j$$ (3.29)

przy czym $c^*_j = 0$ dla $j \in B^*$, gdzie $B^*$ jest zbiorem indeksów zmiennych bazowych słownika $S^*$. Na mocy twierdzenia , każde rozwiązanie słownika $S$ jest także rozwiązaniem słownika $S^*$. Jednym z rozwiązań słownika $S$ jest, jak łatwo zauważyć:

$x_j = 0$ dla wszystkich zmiennych niebazowych $S$ , poza $x_s$ (czyli dla $j \notin B, j \neq s$),

$\left. \begin{array}{l} x_s = y\\ x_i = b_i - a_{is}y \mbox{ \ \ dla \ \ } j \in B \\ z = w + c_s y \end{array} \right\}$ dla dowolnego $y$.

Wstawiając to rozwiązanie do wzoru () otrzymamy

$$w+c_{s}y = w + c_{s}^{*} y + \sum_{i\in B}c^*_i(b_i - a_{is}y)$$

Stąd

$$(c_s - c^*_s + \sum_{i \in B}c^*_ia_{is})y = \sum_{i \in B}c_i^*b_i$$

dla każdego $y \in {\bf R}$. Wobec dowolności $y$ mamy

$$c_s - c^*_s + \sum_{i \in B}c_i^* a_{is} = 0$$ (3.30)

-

Z faktu, że $x_s$ jest zmienną wchodzącą słownika $S$ wynika, że $c_s > 0.$

-

Przypomnijmy, że $x_t$ jest błędną zmienną o największym indeksie. Stąd oczywiście wynika, że $s < t$ ($x_s$ jest także zmienną błędną).

-

Skoro $x_s$ nie jest zmienną wchodzącą w słowniku $S^*$, $s < t$, i wybór zmiennej wchodzącej następuje według reguły Blanda, mamy $c^*_s \leq 0$.

Ze wzoru () wynika więc, że

$$% latex2html id marker 1449 c^*_{i_{0}}a_{i_{0}s} < 0 \mbox{ \ \ \ dla pewnego \ }i_0 \in B$$ (3.31)

Oczywiście $x_{i_{0}}$ jest zmienną bazową w słowniku $S$ (bo $i_0 \in B$) i zmienną niebazową w słowniku $S^*$ ( $c^*_{i_{0}} \neq 0$, w przeciwnym przypadku nie moglibyśmy mieć $c^*_{i_{0}}a_{i_{0}s} < 0$).
$x_{i_{0}}$ jest więc zmienną błędną i wobec tego $i_0 \leq t$. Co więcej: $i_0 \neq t$, bowiem $a_{ts}>0$ skoro $x_t$ jest zmienną wychodzącą a $x_s$ zmienną wchodzącą słownika $S$. Pamiętamy, że $x_t$ jest zmienną wchodzącą słownika $S^*$. Wobec tego $c^*_t > 0$ i w konsekwencji $c^*_ta_{ts}>0$. Ostatecznie $i_0 < t$.
$x_{i_{0}}$ nie jest jednak zmienną wchodzącą słownika $S^*$ (jest nią przecież $x_t$, a właśnie wykazaliśmy, że $i_0 \neq t$), a ponieważ zmienną wchodzącą wybieramy według reguły Blanda, musi być $c^*_{i_{0}} \leq 0$. Ze wzoru () mamy więc $a_{i_{0}s} >0$.
Z faktu, że $x_{i_{0}}$ jest błędną zmienną oraz, że wartość $z$ w rozwiązaniu bazowym jest stale równa $w$ dla wszystkich słowników $S_1,...,S_k$ wynika, że $b_{i_{0}} = 0$. Tak więc $x_{i_{0}}$ była zmienną która powinna, według reguły Blanda, być zmienną wychodzącą ze słownika $S$ ($i_0 < t$). Ta sprzeczność kończy dowód twierdzenia Blanda.