Tabele simpleksowe

Przyjrzyjmy się jeszcze raz przykladowi zapisując PPL w nim rozważany nieco inaczej. Rozważmy mianowicie układ równać:

$$\begin{array}{rrrrrrrr} & x_1 & + 2x_2 & + 3x_3 & + x_4 & ... ... \hline -z & + 2x_1 & + x_2 & + 3x_3 &&&& = 0 \end{array}$$

Powyżej linii pionowej zapisaliśmy ograniczenia naszego PPL (pominęliśmy $x_j \geq 0, \ j=1,...,6$, ale w PL wystarczy zapamiętać, że ograniczenia na nieujemność wszystkich zmiennych występują często), poniżej zaś funkcję celu. Skojarzone z tym PPL rozwiązanie bazowe jest w naszym przykładzie postaci: $x_1=x_2=x_3=0, \ x_4=5, \ x_5 = 8, \ x_6 = 4, \ z=0$. Schematycznie można to zapisać w tabeli:

$$\begin{array}{rrrrrrr\vert r} & 1 & 2 & 3 & 1 & 0 & 0 & 5\... ... 0 & 1 & 4\\ \hline & 2 & 1 & 3 & 0 & 0 & 0 & 0 \end{array}$$

Naszą metodę przedstawioną na przykładach i można teraz przedstawić następująco:

Krok 1: Wyznaczanie zmiennej wchodzącej.

Sprawdzamy ostatni
wiersz tabeli, pomijając ostatni wyraz tego wiersza (odpowiadający wartości $z$). Jeśli w tym wierszu wszystkie współczynniki są mniejsze od zera STOP, tablica opisuje rozwiązanie optymalne.
Jeśli niektóre ze współczynników w tym wierszu są dodatnie, wybieramy największy z nich. Numer $j$ kolumny w której się znajduje jest numerem zmiennej wchodzącej $x_j$ (inaczej: $x_j$ jest nową zmienną bazową).
W naszym przypadku zmienną bazową wchodzącą jest $x_3$

$$\begin{array}{rrr\vert r\vert rrr\vert r} \cline{4-4} &&... ...2 & 1 & {\bf 3} & 0 & 0 & 0 & 0\\ \cline{4-4} \end{array}$$

Krok 2: Wybieramy zmienną wychodzącą.

Wybieramy wiersz $i_0$ w którym $a_{ij}>0$ i iloraz $\frac{b_i}{a_{ij}}$ jest najmniejszy. W naszym przykładzie najmniejszą z liczb $\frac{5}{3}, \ \frac{8}{5}, \ \frac{4}{3}$ jest $\frac{4}{3}$. Wybieramy więc trzeci wiersz ($i_0=3$).

$$\begin{array}{lrr\vert r\vert rrr\vert r} \cline{4-4} & ... ...2 & 1 & {\bf 3} & 0 & 0 & 0 & 0\\ \cline{4-4} \end{array}$$

Krok 3: Tworzymy nowy słownik.

Wymnażamy wiersz $i_{0}$ przez odpowiednie współczynniki i odejmujemy od pozostałych tak, by w $j$-tej kolumnie jedynym niezerowym wyrazem był wyraz w wierszu $i_0$. Dzielimy wiersz $i_0$ przez $a_{i_0j}$.
Tak więc w naszym przykładzie:

1. odejmujemy trzeci wiersz od pierwszego,
2. mnożymy trzeci wiersz przez $\frac{5}{3}$ i odejmujemy od drugiego,
3. odejmujemy trzeci wiersz od ostatniego (tego pod kreską, odpowiadającego zmiennej $z$,
4. dzielimy trzeci wiersz przez $3$.

Otrzymamy następną tabelę:

$$\begin{array}{rrrrrrr\vert r} & -2 & 1 & 0 & 1 & 0 & -1 &... ...{3} \\ \hline & -1 & 0 & 0 & 0 & 0 & -1 & -4\\ \end{array}$$ (3.16)

Zauważmy, że otrzymana tabela dokładnie odpowiada słownikowi. Źeby się o tym przekonać należy przypomniec sobie, że:

• Pierwszy wiersz tabeli () odpowiada drugiemu równaniu słownika (),
• drugi wiersz tabeli () trzeciemu równaniu (),
• trzeci wiersz pierwszemu równaniu (),
• należy uwzględnić zmiany znaków (np w ostatnim wierszu i kolumnie tabeli () mamy minus wartość zmiennej $z$, podczas gdy w słowniku () występuje wartość $z$ itd.
  

Jest oczywistym, że przedstawienie algorytmu przy pomocy ciągu tabel simpleksowych niczym istotnym nie różni się od przedstawienia go w postaci ciągu zmieniających się słowników. Wielu autorów (np. [17], [14], [20]) tak właśnie robi. My w dalszym ciągu prezentacji metody simpleks tabelami tymi nie będziemy się posługiwać.
Słownik jest układem równań liniowych - tabela macierzą jednoznacznie mu przyporządkowaną. Jeden słownik powstaje z drugiego przez operacje algebraiczne prowadzące do układów równoważnych. Stąd oczywista jest własność wszystkich słowników każdego PPL, którą wygodnie będzie nam zapisać w postaci twierdzenia.

Twierdzenie 3.1   Dla ustalonego PPL dowolne dwa słowniki są równoważne. W szczególności każde rozwiązanie dowolnego słownika jest rozwiązaniem każdego innego słownika.