2. Idea działania algorytmu Simplex

Zacznę od przedstawienia podstawowych definicji i faktów teoretycznych. Najpierw przypomnę definicję macierzy bazowej.

Dla równania \(Ax = b\), gdzie \(x\) jest wektorem \(n\) wymiarowym, a \(b\) wektorem \(p\) wymiarowym, macierzą bazową nazywa się każdą kwadratową nieosobliwą macierz B, którą da się utworzyć z p kolumn macierzy A.
Mówiliśmy wyżej o wierzchołkach zbioru dopuszczalnego D. Ich formalna definicja dla rozważanego przypadku wypukłych hiperwielościanów jest następująca.
 Punkt \(x^e\) nazywamy wierzchołkiem wielościennego zbioru wypukłego (vertex of a convexe polytope) D, jeżeli nie istnieją w D dwa różne punkty \(x'\) i \(x''\) oraz liczba \(0\leq α < 1\), takie że \(x^e=αx'+(1-α)x''\) (\(x^e\) nie jest wypukłą kombinacją punktów \(x'\) i \(x''\)).

Oznaczmy przez \(x^{e(l)}\) l-ty punkt wierzchołkowy zbioru DK określonego wzorem (2.1). Można pokazać, że każdy wierzchołek tego zbioru, przy stosownym przenumerowaniu zmiennych, musi mieć postać

\(x^{e(l)}= (\underbrace{x_1^{\mathbf{B}(l)},\cdots x_p^{\mathbf{B}(l)}},0\cdots ,0). \qquad (2.2)\)

dopuszczalnych: wektora i macierzy bazowej
Wektor \(x^{\mathbf{B}(l)}\geq 0 \) wyróżniony we wzorze (2.2) nazywamy dopuszczalnym wektorem bazowym. Ponadto dla każdego punktu wierzchołkowego istnieje związana z nim macierz \(\mathbf{B}(l)\), taka że \(x^{\mathbf{B}(l)}=(\mathbf{B}^{(l)})^{-1} b\). Każda macierz \(\mathbf{B}(l)\) jest taką macierzą bazową równania liniowego \(Ax = b\), dla której \((\mathbf{B}^{(l)})^{-1} b \geq 0\), dlatego jest nazywana dopuszczalną macierzą bazową.

Zatem, aby znaleźć wierzchołek wystarczy znaleźć dopuszczalną macierz bazową, a następnie poprzez odwracanie macierzy i mnożenie policzyć wektor bazowy \(x^{\mathbf{B} }\in ℝ^p\) i uzupełnić go w stosownych miejscach zerami do wektora z przestrzeni \(ℝ^n\) .

Jak więc znaleźć dopuszczalne macierze bazowe związane z wierzchołkami?

W pierwszej połowie XIX w. K. Gauss przedstawił sposób postępowania, nazwany potem algorytmem eliminacji Gaussa, pozwalający znajdować kolejne macierze bazowe układu równań liniowych, jeżeli znamy pierwszą. Pierwsza część pomysłu G.B. Dantziga polegała na wzbogaceniu algorytmu eliminacji Gaussa tak, że nowy algorytm wychodząc od znanej dopuszczalnej macierzy bazowej, generuje dopuszczalne macierze bazowe, a ponadto wybiera je w taki sposób, że kolejny punkt wierzchołkowy jest nie gorszy niż poprzedni (wartość funkcji celu w kolejnym punkcie wierzchołkowym jest nie większa niż w punkcie poprzednim). Dantzig wprowadził też pierwsze wersje stosownych zabezpieczeń przeciwko pętleniu się algorytmu (o tym zjawisku szczegółowiej piszę dalej) i pokazał, że znajdzie on rozwiązanie w skończonej liczbie kroków jeżeli tylko ono istnieje, albo w skończonej liczbie kroków wykaże, że zadanie nie ma rozwiązania (zbiór dopuszczalny jest pusty albo nie jest ograniczony i funkcja celu ucieka na nim (w naszym przypadku minimalizacji) do minus nieskończoności.

Wiadomo już jak znaleźć kolejne dopuszczalne macierze bazowe gdy znamy pierwszą. Do rozwiązania pozostał więc problem: skąd wziąć pierwszą dopuszczalną macierz bazową?

Rozwiązano ten problem drogą posłużenia się następującym zadaniem pomocniczym.

Zadanie pomocnicze metody Simplex (zadanie PLin_P)
\(f(x,v)=∑_{j=1}^pv_j=[0\,⋮⋯⋮0\,⋮1\,⋮⋯⋮1]\begin{bmatrix}x
 \\y
\end{bmatrix}→\mathrm{min }\)
p.o. 
\([A⋮I] \begin{bmatrix}x
 \\v
\end{bmatrix}=b,       \qquad    (2.3)\)
\(x ≥ 0,\,v≥0, \)
gdzie macierz A i wektor \(b≥0\) są takie jak w określeniu (2.1).

W zadaniu wprowadzono p zmiennych pomocniczych vj , tzn. tyle ile w postaci kanonicznej jest ograniczeń równościowych. Zauważmy też, że \((∀(x,v))f(x,v)≥0.\)

Jest to zadanie optymalizacji w postaci kanonicznej i do jego rozwiązania możemy posłużyć się metodą Simplex, o ile będziemy znali początkową dopuszczalna macierzą bazową równania (2.3). 

Łatwo jest pokazać, że

 Macierz jednostkowa o wymiarach  \(p\times p\) :

  • jest macierzą bazową równania (2.3),
  • wektor   jest dopuszczalny ponieważ w postaci kanonicznej \(b\geq  0\), zatem jest ona dopuszczalną macierzą bazową dla zadania PLin_P.

Zadanie PLin_P zostało tak sformułowane, aby jego rozwiązanie   miało potrzebne własności. Można, zatem pokazać, że 

\(f(x ̃,v ̃)>0⇒DK=∅⇒D=∅,\)

co oznacza, że zadanie pomocnicze i wyjściowe zadanie PLin nie mają rozwiązania;

\(f(x ̃,v ̃)=∑_{j=1}^pv ̃_j=[0\,⋮\,⋯\,⋮\,0\,⋮\,1\,⋮\,⋯\,⋮\,1]\begin{bmatrix}x ̃
 \\v ̃
\end{bmatrix}=0⇒(x ̃\, \mathrm{ jest\, wierzchołkiem\, zbioru}\,DK \wedge v ̃=0 )\).

Jeżeli wiemy, że \( f(x ̃,v ̃)=0\), co oznacza że zadanie PLin_P ma rozwiązanie, to można pokazać, że dopuszczalna macierz bazowa ma postać:

\(\mathbf{B}=[A_{k∈K} ],   \) gdzie K to zbiór indeksów niezerowych składowych wektora x ̃,(liczba elementów tego zbioru jest oczywiście równa p), a  \(A_k\)  to kolejne kolumny macierzy \(A,A=[A_1⋮...⋮A_k⋮...⋮A_n].\)     (2.4)

Na podstawie przeprowadzonych powyżej rozważań możemy teraz przedstawić ogólny schemat znajdowania rozwiązania zadania liniowego optymalizacji (zadania programowania liniowego).

Jest to schemat dwufazowy: 

  • z fazą wstępną (faza I), w której szuka się punktu wierzchołkowego, albo stwierdza się, że układ ograniczeń jest sprzeczny, a następnie 
  • z fazą zasadniczą (faza II) kończącą się znalezieniem rozwiązania. 

Faza I

– Przekształcamy zadanie wyjściowe do postaci kanonicznej. 

– Formułujemy i rozwiązujemy metodą Simplex zadanie pomocnicze PLin_P otrzymując dopuszczalny wierzchołek i związaną z nim dopuszczalną macierz bazową albo przekonujemy się ze zbiór dopuszczalny jest pusty (na Rys. 2.3 faza ta została zaznaczona szarą strzałą).

Faza II

– Metodą Simplex rozwiązujemy zadanie w postaci kanonicznej startując z wyznaczonej dopuszczalnej macierzy bazowej. W skończonej liczbie kroków albo stwierdzamy, że zadanie nie ma rozwiązania (funkcja na zbiorze dopuszczalnym ucieka do minus nieskończoności), albo znajdujemy rozwiązanie (na rys. 2.3 faza ta została zaznaczona naprzemiennie strzałkami niebieskimi i czerwonymi).

– Znalezione rozwiązanie oczyszczamy z niepotrzebnych składowych i przenumerowujemy zmienne tak aby otrzymać rozwiązania zadania wyjściowego.