Podsumowanie

W zrewidowanej metodzie sympleksowej oszczędzamy - w porównaniu z metodą oryginalną przedstawioną w rozdziale trzecim - czas i pamięć (komputera).

Czas

- bowiem nie liczymy iloczynu ${\bf A}^{-1}_B{\bf A}_N$ a tylko jego jedną kolumnę. To w praktycznych zadaniach PL bardzo istotna oszczędność, bowiem na ogół zmiennych, a więc kolumn macierzy jest bardzo dużo.

Pamięć

- ponieważ do kolejnych obliczeń w ogóle nie są nam potrzebne żadne słowniki poprzednie, poza słownikiem pierwszym.

Każdą iterację w metodzie zredukowanej można opisać następująco:

Krok 1.

Obliczamy ${\bf y}={\bf c}_B{\bf B}^{-1}$ (z równania ${\bf yB}={\bf c}_B$)^5.1

Krok 2.

Jeśli ${\bf c}_N \leq {\bf yA}_N$ to aktualna rozwiązanie bazowe jest optymalne. Jeśli nie, to znaczy dla pewnej kolumny ${\bf k}$ macierzy ${\bf A}_N$ zachodzi $c_j - {\bf yk}>0$, dla odpowiedniej współrzędnej $c_j$ wektora ${\bf c}_N$, to kolumna ${\bf k}$ wyznacza zmienną wychodzącą.

Krok 3.

Obliczamy kolumnę ${\bf d}$ macierzy ${\bf D}={\bf B}^{-1}{\bf A}_N$, odpowiadającą zmiennej wchodzącej. Jeśli wszystkie jej współrzędne sąujemne, to problem jest nieograniczony. W przeciwnym przypadku jako zmienną wychodzącą wybieramy tę dla której iloraz

$$\frac{\mbox{wartość w rozwiązaniu bazowym}}{\mbox{wartość współrzędnej w kolumnie} {\bf d}}$$

jest minimalna (i nieujemna).

Krok 4.

Ustalamy nowe zmienne bazowe i niebazowe i dla nich wartości dla macierzy ${\bf B}, {\bf A}_N$ oraz wektorów ${\bf c}_B$ i ${\bf c}_N$.