Skuteczność sympleksu

Panuje powszechna, jak się wydaje, zgoda co do tego, że sympleks jest praktycznie bardzo skutecznym i szybkim algorytmem, pozwalającym rozwiązywać problemy w których występują setki czy nawet tysiące zmiennych. Także różnego rodzaje testy tego dowodzą (por. [3,8,12,14,16,18]). A jednak. Okazuje się, że jeśli dobrać wystarczająco złośliwie przykład, to okazuje się, że ilośc iteracji może wynosić nawet $2^n-1$, gdzie $n$ oznacza ilość zmiennych. Oznacza to konieczność utworzenia $2^n$ słowników. To zaś z kolei, znaczy, że sympleks jest teoretycznie beznadziejny: licząc $1$ mikrosekundę na utworzenie słownika (przy dużej liczbie zmiennych to kompletnie nierealne, nawet przy bardzo szybkim komputerze), oznaczałoby to konieczność oczekiwania trudno wyobrażalnej liczby lat na obliczenie zadania o 1000 zmiennych^3.7. Takim złośliwym przykładem jest zadanie Klee-Minty'ego (por. [3,16]). Przedstawimy je w formie następującego twierdzenia.

Twierdzenie 3.4   Algorytm sympleks nie jest algorytmem wielomianowym.

Dowód twierdzenia wynika z lematu:

Lemat 3.1   Algorytm sympleks rozwiązuje problem $PL_n$:

$$\begin{array}{rcrcrcccrcr} &x_1 &&&&&&& \leq 5 \\ &4x_... ...+ & 2x_{n-1} & + & x_n \rightarrow \mbox{max}\\ \end{array}$$ (3.36)

w $2^n-1$ iteracjach (tj. $2^n$ słownikach).

Dowód lematu . Udowodnijmy najpierw dwa proste fakty.

Fakt 1.

$z= 5^n$ jest wartością optymalną, zaś

$$x_1=...=x_{n-1}=0, \ x_n=5^n$$ (3.37)

rozwiązaniem optymalnym problemu ().
Rzeczywiście, pierwszy słownik problemu () można zapisać następująco^3.8:

$$\begin{array}{lcrcccccc} y_1 = 5 &- & x_1\\ y_2 = 25 &-... ...}x_1 + & 2^{n-2}x_2 + & ... & + & 2x_{n-1} + x_n \end{array}$$ (3.38)

Słownikiem w którym zmiennymi niebazowymi są $x_1, ...,x_{n-1}, y_{n}$, zaś zmiennymi bazowymi $y_1, ..., y_{n-1}, x_n$ jest

$$\begin{array}{lcrcccccc} y_1 = 5 &- & x_1\\ y_2 = 25 &-... ...c}_2x_2 + & ... & + & \bar{c}_{n-1}x_{n-1} - y_n \end{array}$$ (3.39)

gdzie $\bar{c}_i=2^{n-j}-2^{n-i+1}$ dla każdego $i=1,...,n-1$. Jest oczywistym, że słownik () jest ostatnim słownikiem algorytmu sympleks dla (), zaś () optymalnym rozwiązaniem (współczynniki $\bar{c}_i$ są oczywiście ujemne).

Fakt 2.

W każdym słowniku problemu (), dla każdego $i \in \{ 1,...,n\}$ dokładnie jedna ze zmiennych $x_i, \ y_i$ jest zmienną bazową.
Gdyby tak nie było, to w w pewnym słowniku dla pewnego $i_0$ zarówno $x_{i_0}$ jak i $y_{i_0}$ byłyby zmiennymi niebazowymi. Dla odpowiadającego temu słownikowi bazowego rozwiązania dopuszczalnego $(\bar{x}_1,...,\bar{x}_n,\bar{y}_1,..., \bar{y}_n)$ mamy oczywiście $\bar{x}_{i_0}=0$ i $\bar{y}_{i_0}=0$. Napiszmy równania $i_0-1$ i $i_0$ słownika ().

$$2^{i_0-1}x_1 +2^{i_0-2}x_2 + ...+ 4x_{i_0-2} + x_{i_0-1} + y_{i_0-1} = 5^{i_0-1}$$ (3.40)

$$2^{i_0} x_1 + 2^{i_0-1}x_2 + ...+ 8x_{i_0-2} + 4x_{i_0-1} + x_{i_0} +y_{i_0} = 5^{i_0}$$ (3.41)

Dla naszego rozwiązania bazowego w którym $x_{i_0}=0$ i $y_{i_0}=0$ mamy więc z ()

$$2^{i_0}\bar{x}_1 + 2^{i_0-1}\bar{x}_2 + ... + 4\bar{x}_{i_0-1} = 5^{i_0}$$

Z drugiej zaś strony, korzystając z (), (), nierówności $2\bar{x}_{i_0-1} \leq 2\cdot 5^{i_0-1}$ wynikającej w sposób banalny z () i pamiętając, że wszystkie współrzędne rozwiązania są nieujemne, otrzymamy

$$5^{i_0}=2^{i_0}\bar{x}_1 + 2^{i_0-1}\bar{x}_2 + ... + 8\bar{x}_{i_0-2} + 4\bar{x}_{i_0-1} =$$

$$2(2^{i_0-1}\bar{x}_1 + 2^{i_0-2}\bar{x}_2 + ... + 4\bar{x}_{i_0-2} + \bar{x}_{i_0-1})+ 2\bar{x}_{i_0-1} \leq$$

$$2 \cdot 5^{i_0-1} + 2 \cdot 5^{i_0-1} = 4 \cdot 5^{i_0-1}$$

- sprzeczność która kończy dowód faktu 2.

Reszta dowodu lematu przez indukcję ze względu na $n$.
Dla $n=1$ problem jest banalny: $PL_n$ ma postać

$$\begin{array}{c} x_1 \leq 5 \\ \hline z=x_1 \end{array}$$

i rozwiązuje się w 2 słownikach: $\begin{array}{rr} y_1=&5-x_1 \\ \hline z=&x_1 \end{array}$, $\begin{array}{rr} x_1=&5-y_1 \\ \hline z = &5-y_1 \end{array}.$
Pierwszy słownik dla $PL_n$ ($n \geq 2$) jest postaci

$$\begin{array}{rrrrlrr} y_1 = & 5 - & x_1 \\ y_2 = & 25 ... ...-1}x_1 & + 2^{n-2}x_2 + & ... + 2x_{n-1} & + x_n \end{array}$$ (3.42)

a ostatni (o rozwiązaniu bazowym $\bar{x}_1=...=\bar{x}_{n-1}=0, \bar{x}_n=5^n, \bar{z}-5^n$)

$$\begin{array}{lrrrrrrr} y_1 =& 5 &- x_1 \\ y_2 =& 25& - ... ...-2}x_2 & - & ... + 4x_{n-2} & - 2x_{n-1} & - y_n \end{array}$$

Napiszmy teraz pierwszy słownik dla $PL_{n+1}$

$$\begin{array}{lrrrlrrrr} y_1 = 5 - x_1\ \ \\ y_2 = 25 - ... ...2 + ... + 2^3x_{n-2} + 4x_{n-1} + 2x_n + x_{n+1} \end{array}$$

Słownik ten różni się od () tym, że dodaliśmy do niego jeden wiersz ograniczeń, a funkcję celu najpierw pomnożyliśmy przez $2$, a potem dodaliśmy do niej $x_{n+1}$. Wszystkie współczynniki (a także wyrazy wolne) we wszystkich słownikach są całkowite. Rzeczywiście: skoro, jak stwierdziliśmy wyżej, dla każdego $i$ dokładnie jedna ze zmiennych $x_i, \ y_i$ jest bazowa, za każdym razem zmienna wchodząca ($x_i$ lub $y_i$) jest obliczana z $i-$tego równania w którym występuje zawsze ze współczynnikiem $-1$. Tak więc, dopóki we wzorze na funkcję $z$ któregokolwiek słownika problemu $PL_{n+1}$ występuje któraś ze zmiennych $x_i$, $i < n+1$, ze współczynnikiem dodatnim, zmienną wchodzącą jest jedna z nich (ta której współczynnik w funkcji $z$ jest największy). Tak więc algorytm sympleks będzie funkcjonował na pierwszych $n$ wierszach ograniczeń dopóty, dopóki wszystkie współczynniki przy zmiennych $x_1,...,x_n,y_1, ... ,y_n$ nie będą ujemne. W ostatnim z tych słowników podstawiamy

$$x_n = 5^n-2^nx_1-2^{n-1}x_2 - ... - 2^3x_{n-2}-2^2x_{n-1}-y_n$$

do

$$y_{n+1} = 5^{n+1} - 2^{n+1}x_1-2^nx_2-...-2^4x_{n-2}-2^3x_{n-1}-4x_n-x_{n+1}$$

i do

$$z=2^nx_1 + 2^{n-1}x_2+...+4x_{n-1}+2x_n+x_{n+1}$$

otrzymując

$$\begin{array}{ll} y_1 & = 5 - x_1\\ y_2 & = 5^2 - 4x_1 -... ... 2^{n-2}x_3 - ... - 4x_{n-1} - 2y_{n} + x_{n+1} \end{array}$$

Zmienną wchodzącą teraz jest $x_{n+1}=5^{n} + 2^{n+1}x_1 + 2^nx_2 + ... + 2^4x_{n-2} + 2^3x_{n-1} + 4y_n - y_n$. Tak więc następnym, $2^{n+1}-$szym słownikiem $PL_{n+1}$ jest słownik następujący

$$\begin{array}{ll} y_1 & = 5 - x_1\\ y_2 & = 5^2 - 4x_1 -... ...+ ... + 2^3x_{n-2} + 2^2x_{n-1} + 2y_n - y_{n+1} \end{array}$$

Otrzymaliśmy problem w którym następne iteracje będą polegały na minimalizacji funkcji

$$z =3\cdot 5^n +2^nx_1 + 2^{n-1}x_2 + ... + 2^3x_{n-2} + 2^2x_{n-1} + 2y_n.$$ (3.43)

Operacje na wierszach ograniczeń dotyczyć będą wyłącznie pierwszych $n$ wierszy. Funkcja $z$ dana wzorem () równa jest stałej $3\cdot 5^n$ plus $2$ razy funkcja celu $PL_n$, potrzebować będziemy więc jeszcze $2^n$ słowników, czyli w sumie $2\cdot 2^n=2^{n+1}$ słowników, co należało udowodnić.

Ćwiczenie 3.1   Algorytmem sympleks rozwiąż zadanie Klee-Minty'ego dla $n=3$ (a jeśli masz cierpliwość i potrzebę lepszego zrozumienia dowodu twierdzenia to dla $n=4$). Ile otrzymasz iteracji a ile słowników w każdym z tych przypadków?