Zagadnienia

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]

Ostatnia tablica opisuje wierzchołek optymalny q=(\frac{3}{4},0,0,1,0,1,0).

Rada praktyczna:

Krawędzie zdegenerowane pochodzą od tych zmiennych, które na przecięciu swojej kolumny i równania (wiersza) o wyrazie wolnym 0 mają liczbę >0.

Badamy wiersze o zerowym wyrazie wolnym i szukamy krawędzi poprawiających, które mają w tym wierszu liczbę \leq 0.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.