Podręcznik

Przedstawimy teraz formalny zapis przedstawionego wyżej dwufazowego schematu rozwiązywania zadania programowania liniowego w postaci kanonicznej (zadania PLin_K).

       $x≥0.$

Przypominamy, że $b ≥ 0$, a elementy macierzy $A$ oznaczmy $A_{sr}$, tak że $A=[A_{sr} ]_{s∈\overline{1,p},r∈\overline{1,n}}.$ 

Podobnie:  $A_k$ to k-ta kolumna macierzy A, zatem $A=[A_1\,⋮...⋮\,A_k\,⋮...⋮\,A_n];$

a dla wektorów $c_k$ to k-ty element wektora c, tak że $c=\begin{bmatrix}c_1\\ \vdots \\ c_n\end{bmatrix}=[c_k]_{k\in \overline{1,n}}..$

 Algebraiczny opis algorytmu Simplex 

Faza I (Obliczenia wstępne)

1. Przekształć zadanie do postaci kanonicznej PLin_K.
2. Utwórz zadanie pomocnicze PLin_P.
3. Używając algorytmu opisanego w fazie II z macierzą jednostkową jako pierwszą macierzą bazową, rozwiąż zadanie PLin_P. Jeżeli wartość optymalna funkcji minimalizowanej w tym zadaniu jest większa od zera to ograniczenia są sprzeczne i stop. Jeżeli nie, przejdź do 4.
4. Wyznacz zbiór indeksów początkowych zmiennych bazowych $Ind\mathbf{B}^{(0)} = K$, gdzie zbiór K jest określony wzorem (2.4), oraz początkową macierz bazową $\mathbf{B}^{(0)}=[A_{k∈Ind\mathbf{B}^{(0)} }]$. Przejdź do fazy II.

Faza II (Zasadnicza)

Informacja początkowa

Znamy zbiór indeksów początkowych zmiennych bazowych  $Ind\mathbf{B}^{(0)}=K⊂\overline{1,n}$

0. Podstaw l: = 0.

1. Wylicz tzw. wektor cen zredukowanych:  $\mathbf{Δ}^{(l)}=[(\mathbf{B}^{(l)} )^{-1} A]^T \mathbf{c}_{Ind\mathbf{B}}^{(l)}-c∈\mathbb{R}^n,$

gdzie: $\mathbf{B}^{(l)}=[A_{k∈Ind\mathbf{B}^{(l)} }]=[A_r^{(l)} ]_{r∈\overline{1,p}}$   oraz  $\mathbf{c}_{Ind\mathbf{B}}^{(l)}=[c_k ]_{k∈Ind\mathbf{B}^{(l)}}).$

2. Sprawdź czy $\mathbf{Δ}^{(l)}\leq 0$ ?

Jeżeli tak – znaleziono rozwiązanie, którego niezerowe elementy są równe:  $[x_k]_{k \in Ind\mathbf{B}^{(l)}}=(\mathbf{B}^{(l)})^{-1}b$

i stop. Jeżeli nie, przejdź do 3 Fazy II.

3. (Wybór indeksu kolumny wprowadzanej do bazy)  Wyznacz  $r ̂= \mathrm{argmax}_{k∈\overline{1,n}}⁡\mathbf{Δ}_k^{(l)} .$

4. (Sprawdzenie warunku braku rozwiązania)  Sprawdź czy $(\mathbf{B}^{(l)})^{-1} A_{r ̂ }=A_{r ̂}^{(l)} ≤0$ ? 

Jeżeli tak – to zadanie nie ma rozwiązania (jest nieograniczone) i stop. Gdy nie, przejdź do 5 Fazy II.

5. (Wybór indeksu kolumny usuwanej z bazy)

gdzie  $S^{(l)} (r ̂)=s∈Ind\mathbf{B}^{(l)} |A_(sr ̂)^{(l)}>0,$  a $A_{sr ̂}^{(l)}$ to s-ty element kolumny (wektora)$A_{r ̂}^{(l)}$.

6. Wylicz nową bazę

$B^{(l+1)}=B^{(l)}+(A_{r ̂ }-A_{s ̂ }([0⋮...⋮0⋮1⋮0⋮...⋮0]),$ ,

podstaw $l:= l+1$ i przejdź do 1 Fazy II.

Omówimy krótko kroki kluczowej II fazy algorytmu.

• Poszukiwanie największego (krok 3) albo najmniejszego (krok 5) elementu to przeglądanie tablicy o n albo nie więcej niż $p < n$ elementach, nie jest więc zadaniem skomplikowanym.
• W kroku 5 może się zdarzyć tzw. degeneracja. Algorytmowi to nie przeszkodzi w wykonywaniu dalszych kroków, ale gdy degeneracja nastąpiła w iteracji l-tej, to w iteracji $l+2$ może nastąpić zerowe zmalenie funkcji celu. Stwarza to potencjalną możliwość powrotu algorytmy do tego samego wierzchołka po liczbie iteracji większej od pięciu (możliwość wystąpienia cyklu – pętlenia). Określono sposoby zabezpieczenia się przed tym zjawiskiem, por. wspomniany podręcznik A. Stachurskiego (podrozdział 2.3), i z praktycznego punktu widzenia można go pominąć.
• Krok 6 to przejście do nowego wierzchołka, przy czym wybór kolumny wprowadzonej do bazy w kroku 3 daje największe możliwe zmalenie funkcji celu.
• Główne problemy implementacyjne związane są z szybkością i dokładnością tego algorytmu. Najwięcej kłopotów jest w nim z opracowaniem procedur, które nie odwracając wprost macierzy będą dawały takie same wyniki jak odwracanie macierzy bazowych. 

W ciągu tych lat, które upłynęły od pierwszej publikacji G.B. Dantziga poprawiano i ulepszano metodę Simplex w różnych kierunkach, tak że współczesne implementacje tej metody potrafią znaleźć w rozsądnym czasie rozwiązania zadań o setkach tysięcy zmiennych i kilkudziesięciu tysiącach ograniczeń (praktyczne zadania o takich wymiarach mają dużo zer w macierzy A, macierz A jest rzadka, zatem przy zastosowaniu odpowiednich metod można takie zadania „zmieścić” w pamięci komputerów).