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).