Ćwiczenie (przykład Chvatála)

Zastosuj algorytm simpleks do PPL

$$\begin{array}{rrrrrrr} x_5 & = && -0,5 x_1 & + 5,5 x_2 & ... ...& = & & 10 x_1 & - 57 x_2 & - 9 x_3 & - 24 x_4 \end{array}$$ (3.27)

wybierając za każdym razem

-

zmienną wchodzącą o największym współczynniku we wzorze na $z$,

-

zmienną wychodzącą o najmniejszym indeksie spośród tych które dają najostrzejsze ograniczenie od góry na zmienną wchodzącą (np pierwszą zmienną wychodzącą będzie $x_5$).

Iteracje powtarzaj aż do pojawienia się ponownie słownika (). Wśród metod unikania cykliczności elegancją ^3.5 wyróżnia się reguła R.G. Blanda [1] zwana także regułą najmniejszego indeksu.
Reguła Blanda.

1. Wybierz jako zmienną wychodzą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.28)

(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 [1])   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 [3].
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ść (gonienie w piętkę).
Dla dowodu nie wprost przypuśćmy, że zmienne są wybierane regułą Blanda, a jednak algorytm goni w piętkę 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.6 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.29)

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

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

-

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 1445 c^*_{i_{0}}a_{i_{0}s} < 0 \mbox{ \ \ \ dla pewnego \ }i_0 \in B$$ (3.32)

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łedną 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.