Zagadnienia

7.1 Zrewidowana metoda sympleks.

7. Własności metody sympleks

7.1. Zrewidowana metoda sympleks.

Kolejne kroki otrzymywania $TS$ prowadzą do narastania błędów - duża liczba mnożeń i dzieleń powoduje, że wyniki są coraz mniej dokładne (algorytm metody sympleks nie jest stabilny).

Przypuśćmy, że $TS$ startową jest

$\left[\begin{array}[]{c|c|c}-c_{{N}}&0...0&b_{{0}}\\ \hline A_{{N}}&I&b\end{array}\right]$

i w m-tym kroku uzyskaliśmy tablicę zawiązana z wyborem zmiennych bazowych $x_{{i_{{1}}}},x_{{i_{{2}}}},...,x_{{i_{{t}}}}$ . Oznacza to, że macierz $B=[k_{{i_{{1}}}},k_{{i_{{2}}}},...,k_{{i_{{t}}}}]$ gdzie $k_{{i_{{j}}}}$ jest $i_{{j}}$ -tą kolumną macierzy $A=[A_{{n}}|I]$ , spełnia warunek

$\overline{B^{{-1}}}\cdot\left[\begin{array}[]{c|c|c|c}1&-c_{{N}}&0...0&b_{{0}}\\ \hline 0&A_{{N}}&I&b\end{array}\right]$

jest m-tą $TS$ ,

to znaczy jej kolumny $k_{{i_{{j}}}},...,k_{{i_{{t}}}}$ tworzą macierz jednostkową

$\overline{B}=\left[\begin{array}[]{c|c}1&-c_{{B}}\\ \hline 0&B\end{array}\right]$ $\overline{B^{{-1}}}=\left[\begin{array}[]{c|c}1&c_{{B}}B^{{-1}}\\ \hline 0&B^{{-1}}\end{array}\right]$

Co pewien czas (np. co 100 kroków) zamiast wyliczać $TS$ metodą eliminacji $GJ$ , wyliczamy ją bezpośrednio ze startowej $TS$ mnożąc ją z lewej strony przez odpowiednią podmacierz $\overline{B^{{-1}}}$ wyznaczoną przez wybór bazy.

Kolejna $TS$ powstaje z poprzedniej przez mnożenie z lewej strony przez macierz różniącą się od jednostkowej tylko jedną kolumna a więc postaci

$E=\left[\begin{array}[]{c|c|c|c}1&\cdots&\frac{-\alpha _{{0,r}}}{a\gamma r}&0\\ 0&...&\frac{-\alpha _{{1,r}}}{a_{{\gamma r}}}&0\\ \vdots&\vdots&...&\\ \vdots&&\frac{-1}{a_{{\gamma,r}}}&\vdots\\ \vdots&&...&\vdots\\ 0&\vdots&\frac{-\alpha _{{t}}r}{a_{{\gamma,r}}}&1\end{array}\right]=I-\frac{1}{\alpha _{{\gamma r}}}\left[\begin{array}[]{c|c|c}0&\alpha _{{0,r}}&0\\ \vdots&\alpha _{{1,r}}&\vdots\\ \vdots&\vdots&\vdots\\ 0&\alpha _{{t,r}}&0\end{array}\right]+j\left[\begin{array}[]{c|c|c}0&...&0\\ \vdots&\frac{1}{\alpha _{{\gamma,r}}}&\vdots\\ 0&...&0\end{array}\right]$

gdzie kolumna główna macierzy poprzedniej ma postać $\left[\begin{array}[]{c}\alpha _{{0,r}}\\ \alpha _{{1,r}}\\ ...\\ \alpha _{{j,r}}\\ ...\\ \alpha _{{t,r}}\end{array}\right]$ i elementem centralnym jest $\alpha _{{\gamma,r}}$ .

$E\cdot\left[\begin{array}[]{c}\alpha _{{0,r}}\\ \alpha _{{1,r}}\\ \vdots\\ \alpha _{{t,r}}\end{array}\right]=\left[\begin{array}[]{c}\alpha _{{0}}r-\frac{\alpha _{{0}}r}{\alpha _{{j,r}}}\cdot\alpha _{{j,r}}\\ \vdots\\ \alpha _{{t}}r-\frac{\alpha tr}{\alpha _{{j,r}}}\cdot\alpha _{{j,r}}\end{array}\right]=\left[\begin{array}[]{c}0\\ \vdots\\ 1\\ \vdots\\ \par \end{array}\right]\leftarrow j$

Macierze $B_{{t}}^{{-1}}=E_{{t}}\cdot E_{{t-1}}...E_{{1}}$ . Ponieważ macierze typu $E$ są podobne do macierzy elementarnych $(I+\alpha\cdot e_{{ij}})$ można tak modyfikować uzyskiwanie macierzy $B$ (dobierając kolejność mnożenia przez macierze elementarne by zminimalizować błędy) i dodatkowo jeśli macierz początkowa był a rozrzedzona, tzn. miała mało współczynników $\neq 0$ , by macierz wynikowa była też rozrzedzona.

Algorytm zrewidowanej metody sympleks:

Dana jest początkowa $TS$ (lub macierz opisująca wielościan i koszty).

W kolejnym kroku mamy dodatkowo macierz $\overline{B^{{-1}}}$ powstałą przez odwrócenie podmacierzy wyznaczonej przez zmienne bazowe i listę zmiennych bazowych.

$\left[\begin{array}[]{c|c|c}x_{{0}}&1&cB^{{-1}}\\ \hline\begin{array}[]{c}x_{{i_{{1}}}}\\ x_{{i_{{2}}}}\\ \vdots\\ x_{{i_{{t}}}}\end{array}&\begin{array}[]{c}0\\ 0\\ \vdots\\ \par \end{array}&B^{{-1}}\end{array}\right]$

1) wyliczamy wyrazy wolne $\left[\begin{array}[]{c}b_{{0}}^{{\prime}}\\ b_{{1}}^{{\prime}}\\ ...\\ b_{{t}}^{{\prime}}\end{array}\right]=\overline{B}^{{-1}}\left[\begin{array}[]{c}b_{{0}}\\ b_{{1}}\\ ...\\ b_{{t}}\end{array}\right]$

2) wyliczamy koszty zredukowane

$z_{{i}}=-c_{{i}}+cB^{{-1}}k_{{i}}$

gdzie $k_{{i}}$ jest i-ta kolumną macierzy $A$ (początkowej)

3) test optymalności

Jeżeli $\forall _{{i}}$ $z_{{i}}\geq 0$ to stop:

wierzchołkiem optymalnym jest $x_{{j}}=\left\{\begin{array}[]{l}0,\quad j\notin\left\{ i_{{1}},i_{{2}},...,i_{{t}}\right\}\\ b_{{i}}^{{\prime}},\quad wpp\end{array}\right.$

Jeżeli nie, to wybieramy kolumnę główną taką, że $c_{{i}}<0$

4) obliczamy kolumnę główną $k_{{i}}^{\prime}=B^{{-1}}\cdot k_{{i}}$

5) test skończoności

Jeżeli $k_{{i}}\leq 0$ to stop: otrzymujemy nieskończoną krawędź poprawiajacą

6) wyznaczamy element centralny $\underset{x_{{ji}}^{{\prime}}>0}{Min}\quad\left\{\frac{b_{{j}}^{{\prime}}}{\alpha _{{j}}^{{\prime}}}\right\}$

7) wyliczamy nową $\overline{B}^{{\prime-1}}$ stosując do $\overline{B^{{-1}}}$ przekształcenia $GJ$ i ustalamy nową listę zmiennych bazowych.

$\left[\begin{array}[]{c|c|c}-c_{{N}}&0&b_{{0}}=0\\ \hline A_{{N}}&I&b\end{array}\right]$

następna

$TS\qquad=\ \left[\begin{array}[]{c|c|c}-c_{{N}}+c_{{N}}B^{{-1}}A_{{N}}&cB^{{-1}}&b_{{0}}^{{\prime}}=cB^{{-1}}\\ \hline\underset{\text{nie interesująca - nie wyliczamy}}{A_{{N}}B^{{-1}}}&B^{{-1}}&B^{{-1}}b\end{array}\right]$

Policzmy ile działań wykonujemy w przypadku tablicy o $n$ kolumnach i $t$ wierszach.

	Przekształcenia
Metoda	Gausa	Koszty	Razem
	Jordana	zredukowane

Sympleks $\begin{array}[]{c}\ast\text{ i }/\\ +\,\text{i}\,-\end{array}$	$\begin{array}[]{c}(t+1)(n-t+1)\\ t(n-t+1)\end{array}$		$\begin{array}[]{c}t(n-t)+n+1\\ t(n-t+1)\end{array}$

Zrewidowana $\begin{array}[]{c}\ast\text{ i }\,/\\ +\,\text{i}\,-\end{array}$	$\begin{array}[]{c}\left(t+1\right)^{{2}}\\ t(t+1)\end{array}$	$\begin{array}[]{c}t(n-t)\\ t(n-t)\end{array}$	$\begin{array}[]{c}t(n-t)+(t+1)^{{2}}\\ t(n+1)\end{array}$

Wniosek:

Zazwyczaj metoda zrewidowana jest droższa, ale zyskujemy dokładność.

Niestety macierzowy algorytm metody sympleks, w przeciwieństwie do geometrycznego, może się zapętlić. Sytuacja zachodzi wtedy gdy jeden wierzchołek może być przedstawiony za pomocą wielu tablic sympleks. Możemy w nieskończoność wędrować krawędziami zdegenerowanymi po jednym i tym samym wierzchołku. Aby uniknąć tej sytuacji niektóre algorytmy wykorzystują numerowanie leksykograficzne wierzchołków. Patrz [4]

Aby wierzchołek mógł być przedstawiony wieloma tablicami sympleks z prawej strony kreski muszą znajdować się zera. Algorytmy wykonujące przekształcenia Gaussa - Jordana nie są stabilne co w konsekwencji daje błąd ale i przerwanie pętli - co wykorzystują inne algorytmy.

Podamy teraz przykład zapętlenia się algorytmu sympleks pochodzący z [3].

Przykład 7.1

$Max\ x_{0}=\frac{3}{4}x_{4}-20x_{5}+\frac{1}{2}x_{6}-6x_{7}$ , gdzie

$\begin{array}[]{r}x_{1}+\frac{1}{4}x_{4}-8x_{5}-x_{6}+9x_{7}=0\\ x_{2}+\frac{1}{2}x_{4}-12x_{5}-\frac{1}{2}x_{6}+3x_{7}=0\\ x_{3}+x_{6}=1\end{array}$

$x_{1}\geq 0,x_{2}\geq 0,x_{3}\geq 0,x_{4}\geq 0,x_{5}\geq 0,x_{6}\geq 0,x_{7}\geq 0$

Ten układ równań daje następującą TS

$\left[\begin{array}[]{r|rrrrrrr|r}1&0&0&0&-\frac{3}{4}&20&-\frac{1}{2}&6&0\\ \hline 0&1&0&0&(\mathbf{\frac{1}{4}})&-8&-1&9&0\\ 0&0&1&0&\frac{1}{2}&-12&-\frac{1}{2}&3&0\\ 0&0&0&1&0&0&1&0&1\end{array}\right]$

Otrzymujemy następujące TS:

$\left[\begin{array}[]{r|rrrrrrr|r}1&3&0&0&0&-4&-\frac{7}{2}&33&0\\ \hline 0&4&0&0&1&-32&-4&36&0\\ 0&-2&1&0&0&(\mathbf{4})&\frac{3}{2}&-15&0\\ 0&0&0&1&0&0&1&0&1\end{array}\right]$

$\left[\begin{array}[]{r|rrrrrrr|r}1&1&1&0&0&0&-2&18&0\\ \hline 0&-12&8&0&1&0&(\mathbf{8})&-84&0\\ 0&-\frac{1}{2}&\frac{1}{4}&0&0&1&\frac{3}{8}&-\frac{15}{4}&0\\ 0&0&0&1&0&0&1&0&1\end{array}\right]$

$\left[\begin{array}[]{r|rrrrrrr|r}1&-2&3&0&\frac{1}{4}&0&0&-3&0\\ \hline 0&-\frac{3}{2}&1&0&\frac{1}{8}&0&1&-\frac{21}{2}&0\\ 0&\frac{1}{16}&-\frac{1}{8}&0&-\frac{3}{64}&1&0&(\mathbf{\frac{3}{16}})&0\\ 0&\frac{3}{2}&-1&1&-\frac{1}{8}&0&0&\frac{21}{2}&1\end{array}\right]$

$\left[\begin{array}[]{r|rrrrrrr|r}1&-1&1&0&-\frac{1}{2}&16&0&0&0\\ \hline 0&(\mathbf{2})&-6&0&-\frac{5}{2}&56&1&0&0\\ 0&\frac{1}{3}&-\frac{2}{3}&0&-\frac{1}{4}&\frac{16}{3}&0&1&0\\ 0&-2&6&1&\frac{5}{2}&-56&0&0&1\end{array}\right]$

$\left[\begin{array}[]{r|rrrrrrr|r}1&0&-2&0&-\frac{7}{4}&44&\frac{1}{2}&0&0\\ \hline 0&1&-3&0&-\frac{5}{4}&28&\frac{1}{2}&0&0\\ 0&0&(\mathbf{\frac{1}{3}})&0&\frac{1}{6}&-4&-\frac{1}{6}&1&0\\ 0&0&0&1&0&0&1&0&1\end{array}\right]$

$\left[\begin{array}[]{r|rrrrrrr|r}1&0&0&0&-\frac{3}{4}&20&-\frac{1}{2}&6&0\\ \hline 0&1&0&0&\frac{1}{4}&-8&-1&9&0\\ 0&0&1&0&\frac{1}{2}&-12&-\frac{1}{2}&3&0\\ 0&0&0&1&0&0&1&0&1\end{array}\right]$

I tak ostatnia siódma TS jest identyczna z pierwszą.

Wszystkie tablice opisują wierzchołek nieoptymalny $p=(0,0,1,0,0,0,0)$

Idąc inną drogą otrzymujemy:

$\left[\begin{array}[]{r|rrrrrrr|r}1&0&0&0&-\frac{3}{4}&20&-\frac{1}{2}&6&0\\ \hline 0&1&0&0&\frac{1}{4}&-8&-1&9&0\\ 0&0&1&0&(\mathbf{\frac{1}{2}})&-12&-\frac{1}{2}&3&0\\ 0&0&0&1&0&0&1&0&1\end{array}\right]$

$\left[\begin{array}[]{r|rrrrrrr|r}1&0&\frac{3}{2}&0&0&2&-\frac{5}{4}&\frac{21}{2}&0\\ \hline 0&1&-\frac{1}{2}&0&0&-2&-\frac{3}{4}&\frac{15}{2}&0\\ 0&0&2&0&1&-24&-1&6&0\\ 0&0&0&1&0&0&(\mathbf{1})&0&1\end{array}\right]$

$\left[\begin{array}[]{r|rrrrrrr|r}1&0&\frac{3}{2}&\frac{5}{4}&0&2&0&\frac{21}{2}&\frac{5}{4}\\ \hline 0&1&-\frac{1}{2}&\frac{3}{4}&0&-2&0&\frac{15}{2}&\frac{3}{4}\\ 0&0&2&1&1&-24&0&6&1\\ 0&0&0&1&0&0&1&0&1\end{array}\right]$