6.3 Algorytm simpleksowy
Ogólną metodą rozwiązywania zadań programowania liniowego jest algorytm simpleks.
Jest to procedura numeryczna, która pozwala dokonać kontrolowanego przeglądu tylko pod-
zbioru kolejnych wierzchołków wielościanu wypukłego (lub wielościennego zbioru wypu-
kłego) X �" Rn . Dla każdego sprawdza się, czy liniowa funkcja
f (x1, x2 ,..., xn ) = c1x1 + c2 x2 + ... + cn xn
osiągnęła swą wartość największą (najmniejszą). W szczególności, algorytm pozwala usta-
lić, że funkcja celu nie osiąga skończonej wartości optymalnej w zbiorze X , gdzie
X ={x : x" Rn '" Ax d" b '" x e" 0},
Bądz
też stwierdzić, że zadanie PL jest sprzeczne, tzn. że zbiór X = ź .
/
Schemat postępowania w algorytmie simpleks zaprezentowany jest na Rys. 1.
Zapisać zadanie
programowania liniowego (PL)
w postaci modelu
simpleksowego
Wynaczyć początkowe (startowe)
rozwiązanie bazowe i zapisać je
w tablicy simpleksowej
Sprawdzić czy dla
NIE
wyznaczonego rozwiązania
TAK
bazowego spełnione są warunki
zakończenia procesu
obliczeniowego
Wyznaczyć kolejne rozwiązanie
Koniec
bazowe, poprzez jednokrotną
obliczeń
wymianą wektora bazowego,
gwarantujące wartość funkcji
celu nie gorszą niż
w poprzednim wierzchołku
Sprawdzić, czy
rozwiązanie
bazowe jest
rozwiązaniem
dopuszczalnym
Rys. 1. Schemat blokowy postępowania w algorytmie simpleks
6
Omówimy teraz poszczególne fragmenty tego postępowania.
A. Zapis zadania PL w postaci modelu simpleks.
Dla prawidłowego działania algorytmu układ nierówności określający ograniczenia zapi-
sujemy tak, aby w wektorze ograniczeń wszystkie składowe były nieujemne ( b e" 0 ), mno-
żąc ewentualnie wybrane nierówności przez (-1). Jeśli w układzie ograniczeń występowały
równania, to nie zamieniamy ich na koniunkcję dwóch nierówności. Z teorii algebraicznego
rozwiązywania układów nierówności liniowych wiadomo, że aby można było określić
wierzchołki zbioru X , należy układ nierówności sprowadzić do równoważnego układu
równań liniowych (danego w postaci bazowej). Każdą nierówności uzupełniamy o niewia-
dome swobodne Si i ewentualnie, jeżeli zachodzi konieczność, o niewiadome sztuczne ti
(na ogół zmienne te otrzymują indeks zgodny z numerem ograniczenia).
I tak:
a) nierówność ai1x1 + ai2 x2 + L + ain xn d" bi zapisujemy jako równanie
ai1x1 + ai2 x2 + L+ ain xn + Si = bi '" Si e" 0;
b) nierówność ai1x1 + ai2 x2 + L + ain xn e" bi zapisujemy jako równanie
ai1x1 + ai2 x2 + L + ain xn - Si + ti = bi '" Si e" 0 '" ti = 0 ;
c) równanie ai1x1 + ai2 x2 + L + ain xn = bi zapisujemy jako równanie
ai1x1 + ai2 x2 + L + ain xn + ti = bi '" ti = 0 .
Wszystkie nowe niewiadome, wprowadzone do układu ograniczeń, muszą zostać
~
uwzględnione jako nowe zmienne w liniowej funkcji f równej sumie: funkcji
f (x1, x2 ,K, xn ) i funkcji liniowej, której argumentami (zmiennymi) są dołączone niewia-
dome, przy czym:
- współczynniki przy każdej niewiadomej swobodnej Si są zawsze równe zero;
- jeżeli pojawiają się niewiadome sztuczne ti , to współczynniki przy tych zmiennych
przyjmują wartości równe (-M) w przypadku wyznaczenia wartości największej funkcji f,
zaś (+M) gdy poszukujemy wartości najmniejszej funkcji f, gdzie M jest dowolnie dużą licz-
bą dodatnią ( M >> 0 ).
Zatem przy wyznaczeniu wartości największej, funkcję liniową
f (x1, x2 ,..., xn ) = c1x1 + c2 x2 + ... + cn xn
~
zamieniamy na funkcję f postaci:
~
f (x1, x2 ,..., xn , S1, S2 ,..., Sh ,t1,...,tk ) =
= c1x1 + c2 x2 + ... + cn xn + 0S1 + 0S2 + ... +0Sh - Mt1 - Mt2 - ... - Mtk ,
bądz
przy wyznaczaniu wartości najmniejszej, funkcję liniową f zamieniamy na funkcję
~
f , gdzie:
~
f (x1, x2 ,..., xn , y1, y2 ,..., ym ,t1,...,tk ) =
= c1x1 + c2 x2 + ... + cn xn + 0S1 + 0S2 + ... + 0Sh + Mt1 + Mt2 + ... + Mtk ,
Jeżeli wektor x = [x1, x2 ,..., xn ]T " X , to zmienne sztuczne przyjmują wartości zerowe
~
i funkcje f i f mają równe wartości
~
f (x1, x2 ,..., xn ) = f (x1, x2 ,..., xn , S1, S2 ,..., Sh ,t1,...,tk ) .
7
 Model simpleks jest to zatem taki zapis zadania PL, w którym układ nierówności zamie-
niono na równoważny układ równań (dany w postaci bazowej), a liniową funkcję f zastąpio-
~
no funkcją f , w której uwzględnia się wszystkie nowe niewiadome tego układu (jako nowe
zmienne) z odpowiednimi współczynnikami.
B. Wyznaczanie startowego rozwiązania bazowego i zapis tego rozwiązania w tablicy
simpleks
Startowe rozwiązanie bazowe dla modelu simpleks wyznaczamy zgodnie z zasadą: nie-
wiadoma niebazowa przyjmuje wartość zero oraz niewiadoma bazowa odpowiadająca wek-
torowi bazowemu pj występującemu w bazie w wierszu i-tym przyjmuje wartość bi . Roz-
wiązanie to i wszystkie następne zapisujemy w odpowiedniej tablicy nazywanej tablicą
simpleksową, którą budujemy według następującego schematu:
Tablica 1
Wzór tablicy simpleks
Współczynniki funkcji celu
Nie-
x1 K xn S1 K Sh t1 K tk Wartości Wartości
Nr
Baza wiad. niewiad.
cB
iteracji
p1 K pn pn+1 Kpn+h pn+h+1 K pn+h+k bazowych Kryterium
Bazowe
Współczynniki postaci bazowej
układu równań (współrzędne
wektorów w danej bazie)
~
w
f (xi )
" = z - c
"1 K "n "n+1 K"n+h "n+h+1 K "n+h+k
j j j
Tablica 1 jest rozbudowaną tablicą, używaną do zapisu kolejnych rozwiązań bazowych, któ-
rą posługujemy się przy wyznaczaniu rozwiązań układu równań z warunkiem brzegowym.
Nowe fragmenty to:
- dodatkowa kolumna w boczku tablicy - cB zawierająca współczynniki stojące przy tych
~
zmiennych liniowej funkcji f , które w układzie równań występują jako niewiadome bazo-
we;
- dodatkowy wiersz w główce tablicy nad niewiadomymi układu równań, zawierający
~
współczynniki stojące przy zmiennych w liniowej funkcji f (niewiadome układu równań są
~
tu bowiem jednocześnie zmiennymi albo inaczej argumentami, funkcji f ).
- dodatkowy wiersz (pod całą tablicy), który zawiera tak zwane wskaz
niki optymalności
~
" obliczane dla każdego wektora p odpowiadającego zmiennym funkcji f . Ostatni ele-
j j
~
ment w tym wierszu jest równy wartości funkcji f w punkcie wierzchołkowym wyznaczo-
nym przez odpowiednie rozwiązanie bazowe.
C. Sprawdzenie, czy wyznaczone rozwiązanie bazowe określa wierzchołek, w którym
badana funkcja osiąga swą skończoną wartość największą (najmniejszą).
2
Niech xw oznacza jakiś wierzchołek w zbiorze X wyznaczony na podstawie dopusz-
2 łł
x
�ł
2 2
czalnego rozwiązania bazowego o bazie B', zaś xw kolejny wierzchołek zbioru X
�łS2 śł
�ł �ł
2
B
2 2 łł
x
�ł
wyznaczony przez sąsiednie dopuszczalne rozwiązanie bazowe związane z bazą B''.
�łS2 2 śł
�ł �ł
2 2
B
8
Zakładamy również, że baza B'' powstaje z bazy B' przez wymianę jednego wektora, przy
2 2
czym na miejsce wektora  opuszczającego bazę B wchodzi do bazy B'' wektor p " B .
j
Twierdzenie z którego wynika kryterium pozwalające stwierdzić czy postępowanie nume-
ryczne można zakończyć, czy należy je dalej kontynuować jest następujące:
2 łł �ł 2 2 łł
x x
�ł
Jeżeli i są sąsiednimi rozwiązaniami bazowymi określającymi kolejne
�łS2 śł �łS2 2 śł
�ł �ł �ł �ł
2 2 2
B B
2 2 2
wierzchołki xw i xw w zbiorze X , to zmiana wartości funkcji liniowej celu przy
2 2 2
zmianie wierzchołka xw na wierzchołek xw wynosi:
2 2 2 2 2
"f = f (xw ) - f (xw ) = -Ś (z - c ) (6.1)
j j j
gdzie:
2 2
Ś > 0 - wartość niewiadomej bazowej odpowiadającej wektorowi p w nowej
j j
bazie B2 2 ;
~
cj - współczynnik liniowej funkcji f przy zmiennej (niewiadomej) związanej
z wektorem p
j
zj - suma, której składnikami są iloczyny elementów tworzących kolumnę cB2
(współczynniki funkcji liniowej przy niewiadomych bazowych) przez od-
powiednie współrzędne wektora p w bazie B'.
j
W zapisie wektorowym liczbę z można przedstawić jako:
j
2
B
z = (cB2 )T ą (6.2)
j j
2
B
gdzie ą jest wektorem współrzędnych wektora p w bazie B'.
j j
2
B
Wzór (6.2) można też zapisać jako iloczyn skalarny wektorów cB2 i ą :
j
2
B
z = cB2 o ą (6.2a)
j j
2
B
2
Zwróćmy uwagę, że jeżeli wektor pl " B , to ą jest wektorem jednostkowym, stąd
j
zl = cl . Zatem w tablicy simpleks zawierającej rozwiązanie bazowe wyznaczone przez bazę
2
B mamy, że
"l = zl - cl = 0 . (6.3)
Oznacza to, że wskaz
niki optymalności dla wektorów bazowych (albo niewiadomych
bazowych) są zawsze równe zero.
2 2
Znak "f we wzorze (6.1) zależy tylko od znaku różnicy z - c (czynnik Ś przyjmują-
j j j
cy wartość dodatnią nie ma wpływu na znak "f ). Czynniki " nazywamy wskaz
nikami
j
optymalności. Wynika stąd, że:
9
2
Jeżeli, we wzorze (6.1) dla każdego wektora p " B zachodzi warunek " = z - c > 0
j j j j
2 2 2
to "f < 0 i oznacza to spadek wartości funkcji przy przejściu z wierzchołka xw do xw
w zbiorze X .
2
Jeżeli natomiast dla każdego p " B zachodzi " = z - c < 0 to "f > 0 i oznacza to
j j j j
2 2 2
wzrost wartości funkcji przy przejściu z wierzchołka xw do xw zbiorze X .
Oczywiście "f < 0 jest korzystne wówczas, gdy na zbiorze X wyznaczamy wartość naj-
mniejszą, natomiast nie jest korzystne przy wyznaczaniu wartości największej funkcji i na
odwrót, "f > 0 określa korzystną sytuację, gdy interesuje nas wartość największa funkcji na
zbiorze X , niekorzystną - gdy poszukujemy wartości najmniejszej tej funkcji w zbiorze X .
Z powyższego wynika:
1. Jeżeli dla pewnego rozwiązania bazowego wszystkie wskaz
niki optymalności spełniają
warunek
"" = z - c e" 0 (6.4)
j j j
j
to funkcja linowa, w wierzchołku wyznaczonym przez to rozwiązanie bazowe, osiąga
swoją skończoną wartość największą na zbiorze X .
2. Jeżeli dla pewnego rozwiązania bazowego wszystkie wskaz
niki optymalności spełniają
warunek
"" = z - c d" 0 (6.5)
j j j
j
to funkcja liniowa w wierzchołku wyznaczonym przez to rozwiązanie bazowe osiąga
swoją skończoną wartość najmniejszą na zbiorze X .
Tak więc wzory (6.4) oraz (6.5) określają tzw. kryterium optymalności rozwiązania bazo-
wego, a mówiąc inaczej, pozwalają stwierdzić kiedy postępowanie numeryczne w algoryt-
mie simpleks zostaje zakończone.
D. Budowa nowego, poprawionego rozwiązania bazowego
Jeżeli rozwiązanie bazowe nie spełnia warunków określonych przez wzory (6.4) lub (6.5)
tzn. wśród wektorów niebazowych istnieją wektory p dla których "j = zj -cj <0 (albo
j
"j = zj -cj >0) to oznacza, że badana funkcja liniowa f nie osiągnęła jeszcze na zbiorze X
swej wartości największej (najmniejszej). Wówczas postępowanie numeryczne w algoryt-
mie simpleks należy kontynuować i poszukiwać nowego poprawionego rozwiązania bazo-
wego poprzez jednokrotną wymianę wektora w bazie. Aby jednak zagwarantować nie
10
gorszą niż w wierzchołku już wyznaczonym wartość funkcji f trzeba zaproponować pewien
racjonalny sposób wyboru wektora  wchodzącego do nowej bazy.
Kryterium wyboru wektora wprowadzanego do nowej bazy
1) Przy wyznaczaniu wartości największej funkcji liniowej f na zbiorze X do nowej
2 2
bazy B wchodzi wektor pk , którego wskaz
nik optymalności spełnia warunek:
"k = zk - ck = min(z - c ) . (6.6)
j j
" <0
j
2) Przy wyznaczaniu wartości najmniejszej funkcji liniowej f na zbiorze X , do nowej
bazy B2 2 wchodzi wektor pk , którego wskaz
nik optymalności spełnia warunek:
"k = zk - ck = max(z - c ). (6.7)
j j
" >0
j
Jeżeli istnieją "k < 0 ("k > 0) , i każdy wektor pk z takim wskaz
nikiem optymalności ma
niedodatnie współrzędne w danej bazie, to zbiór X jest nieograniczony i funkcja f nie
osiąga na tym zbiorze skończonej wartości największej (najmniejszej).
Ponieważ wyznaczamy zawsze rozwiązania bazowe o nieujemnych składowych to po-
trzebne jest kryterium, określające wektor, który  opuszcza bazę B'.
T
B
Załóżmy, że do bazy B2 2 wchodzi wektor pk o współrzędnych ąk 2 = [ą1k ą2k K ąmk ]
w bazie B'. Niech Ś oznacza wartość niewiadomej bazowej odpowiadającej wektorowi p
j j
w tej bazie. Wówczas:
Bazę B'  opuszcza ten wektor pi dla którego spełniony jest warunek:
�ł �ł
Ś
Śi
j
�ł �ł
= min (6.8)
�łą jk �ł
>0
ąik ą jk
�ł łł
Może zajść przypadek, że najmniejsza nieujemna wartość ilorazu określona wzorem
(6.8) wystąpi dla dwóch lub więcej wektorów, wówczas decyzja który z tych wektorów
 opuszcza bazę B' należy do rozwiązującego zadanie.
Budując nową tablicę simpleks dla bazy B2 2 wykonujemy obliczenia numeryczne na
wierszach poprzedniej tablicy tak, aby przy pomocy operacji elementarnych przekształcić
współrzędne wektora pk w wektor jednostkowy (w bazie B2 2 będzie on wektorem bazo-
wym). Szczegóły postępowania numerycznego w algorytmie simpleks wyjaśnimy dalej na
przykładach.
Z odmiennym podejściem, poprzez stosowanie wzorów przejścia zdanej do kolejnej ta-
blicy simpleks, można się zapoznać, np w [3] s. 40-53, [5] s. 46-70. Szczegóły postępowania
numerycznego w algorytmie simpleks wyjaśnimy dalej na przykładach.
11