Algorytm sympleks
3.1
Wprowadzenie
Stosowanie geometrycznej metody rozwiązywania ZPL jest możliwe właściwie tylko w przypadku zagadnień, w których sformułowaniu występują tylko dwie zmienne decyzyjne. Jeże-li liczba zmiennych decyzyjnych jest równa 3, to możliwa jest geometryczna interpretacja ograniczeń (wyznaczają one pewien wielokąt wypukły zawarty w pierwszym oktancie ukła-du współrzędnych), ale, na ogół, trudne jest wykonanie dostatecznie dokładnego rysunku ilustrującego wzajemne położenie zbioru rozwiązań dopuszczalnych i poziomic funkcji ce-lu, które są płaszczyznami w
3
R . W przypadku większej liczby zmiennych decyzyjnych
praktycznie niemożliwe jest efektywne sporządzenie rysunków mogących ułatwić znalezie-nie rozwiązania ZPL. Dodatkową trudność sprawia duża liczba dopuszczalnych rozwiązań bazowych (czyli wierzchołków zbioru rozwiazań dopuszczalnych D), jakie należy wyliczyć, aby poprawnie opisać wielościan D (np. dla ZPL z ośmioma zmiennymi bazowymi i za-wierajacego cztery ograniczenia liczba takich wierzchołków może być równa 70). Rodzi się więc pytanie, czy istnieje metoda rozwiązywania ZPL, która działa niezależnie od liczby zmiennych decyzyjnych, jest efektywna i nie wymaga wyznaczania wsystkich dopuszczalnych rozwiązań bazowych. Na szczęście, odpowiedź na to pytanie jest twierdząca i brzmi: algorytm sympleks. Jest to algorytm iteracyjny, który startuje od dowolnie ustalonego dopuszcalnego rozwiązania bazowego i w każdym kroku zastępuje aktualne rozwiązanie nowym „sąsiednim” dopuszczalnym rozwiązaniem bazowym, dla którego wartość funkcji celu jest bliższa wartości optymalnej, przy czym zmiana wartości funkcji celu przy przejściu od „starego” do „nowego” rozwiązania jest największa z możliwych. Przez „rozwiązania sąsiednie” rozumiemy tutaj dwa dopuszczalne rozwiązania bazowe, dla których zbiory ich zmiennych bazowych różnią się jednym elementem. Rozwiązania takie odpowiadają końcom łączącej je krawędzi w wielościanie D.
1
W poprzednim rozdziale pokazaliśmy, w jaki sposób przekształcić dowolne ZPL do zagadnienia równoważnego zapisanego w bazowej postaci kanonicznej. W dalszym ciągu omówimy stosowanie algorytmu sympleks właśnie dla takiej postaci ZPL. Istnieją modyfi-kacje tego algorytmu, które działają przy nieco innych założeniach (np. nie wymaga się, aby kanoniczna postać zagadnienia była bazowa), ale wydaje się, że opis algorytmu sympleks i uzasadnienie jego poprawności są najłatwiejsze w postulowanej powyżej sytuacji.
3.2
Wskaźniki optymalności
Zacznijmy od przypomnienia ogólnych założeń. Dane jest ZPL:
f ( x 1 , x 2 , . . . , xn) = c 1 x 1 + c 2 x 2 + . . . + cnxn → max (min)
a 11 x 1 + a 12 x 2 + . . . + a 1 nxn
=
b 1 ,
. . .
(3.1)
am 1 x 1 + am 2 x 2 + . . . + amnxn =
bm,
x 1 0 , x 2 0 , . . . , xn 0 .
gdzie współczynniki aij oraz bi są ustalonymi liczbami rzeczywistymi, bi 0 dla każdego i = 1 , 2 , . . . , m oraz m < n. Zbiór rozwiązań dopuszczalnych zadania (3.1), czyli zbiór wszystkich punktów ( x
n
1 , x 2 , . . . , xn) ∈ R
spełniających ograniczenia, będziemy oznaczać
symbolem D, tak jak to robiliśmy dotychczas. Zauważmy, że wymiar zbioru D jest równy n − m i jest mniejszy od wymiaru przestrzeni
n
R , ale nadal jest to wielościan zawarty w
pierwszym ortancie układu współrzędnych przestrzeni
n
R , którego wierzchołki wyznaczone
są przez odpowiednie dopuszczalne rozwiązania bazowe układu równań
a
11 x 1 + a 12 x 2 + . . . + a 1 nxn = b 1 ,
a
21 x 1 + a 22 x 2 + . . . + a 2 nxn = b 2 ,
.
(3.2)
.
.
a
m 1 x 1 + am 2 x 2 + . . . + amnxn = bm.
Wobec uwagi poczynionej na końcu poprzedniego podrozdziału będziemy zakładać, że układ równań tworzących ograniczenia w ZPL (3.1) zapisany jest w bazowej postaci kanonicznej, a jego zmiennymi bazowymi są x 1, x 2, . . . , xm. Założenie to de facto nie wprowadza żadnych dodatkowych warunków, lecz służy jedynie wygodzie zapisu. Przy 2
takim założeniu układ ograniczeń (3.2) można zapisać prościej w nastepującej postaci:
x
1 + a 1 m+1 xm+1 + a 1 m+2 xm+2 + . . . + a 1 nxn = b 1 ,
x
2 + a 2 m+1 xm+1 + a 2 m+2 xm+2 + . . . + a 2 nxn = b 2 ,
.
(3.3)
.
.
x
m + am m+1 xm+1 + am m+2 xm+2 + . . . + amnxn = bm.
Ze względu na założenie o znakach prawych stron ograniczeń, rozwiązanie bazowe
¯
X = ( b 1 , b 2 , . . . , bm, 0 , 0 , . . . , 0) układu równań (3.3) jest dopuszczalnym rozwiązaniem bazowym. Zbudowanie następnego dopuszczalnego rozwiązania bazowego polega na zastąpieniu jednej ze zmiennych bazowych (nazywanej dalej: zmienną wychodzacą z bazy) przez odpowiednią zmienną niebazową (czyli zmienną wchodzącą do bazy). Zmienną wychodzacą z bazy wybieramy tak, aby w nowym rozwiązaniu bazowym wszystkie wartości zmiennych były nieujemne. W poprzednim rozdziale został omówiony sposób, jak to zrobić: po ustaleniu, która zmienna ma wejść do bazy, zmienną wychodzącą z bazy wyznacza się obliczając ilorazy wyjścia dla wszystkich dodatnich zmiennych bazowych i wybierając tę zmienną, dla której iloraz wyjścia jest najmniejszy. Pozostaje więc znaleźć kryterium pozwalające na optymalny wy-bór zmiennej wchodzącej do bazy. W celu znalezienia tego kryterium należy przeprowadzić pewne rozważania teoretyczne.
Rozważmy dowolne rozwiązanie dopuszczalne X = ( x 1 , x 2 , . . . , xn) układu równań (3.3). Wówczas
n
x
X
i = bi −
aisxs
dla
i = 1 , 2 , . . . , m,
s= m+1
Korzystając z tej równości możemy teraz obliczyć różnicę pomiędzy wartościami funkcji celu f dla rozwiązań X i ¯
X (pamiętamy,że ¯
xi = bi dla i = 1 , . . . , m:
m
n
m
f ( X) − f ( ¯
X) = X c
X
X
ixi +
csxs −
cibi =
i=1
s= m+1
i=1
m
n
n
m
= X c
X
X
X
i
b
a
c
c
i −
isxs +
sxs −
ibi =
i=1
s= m+1
s= m+1
i=1
n
m
!
=
X
X aisci − cs xs.
s= m+1
i=1
Ponieważ wszystkie wartości xs są nieujemne, znak różnicy f ( x) − f (¯
x) zależy od znaków
wyrażeń w nawiasach w ostatniej sumie. Przyjmujemy następującą definicję.
3
Definicja 1. Przy wprowadzonych powyżej oznaczeniach, dla każdej zmiennej niebazowej xs liczbę
m
∆
X
s =
aisci − cs
i=1
nazywamy wskaźnikiem optymalności dla tej zmiennej.
Oczywiście, w praktyce zmienna niebazowa może mieć indeks mniejszy lub równy m.
Zakres zmienności dla tego indeksu, którym posługiwaliśmy się wyżej, był konsekwencją przyjętego założenia mającego na celu uproszczenie notacji.
Posługując się oznaczeniem wskaźnika optymalności można powyżej otrzymaną równość zapisać następująco:
n
f ( X) = f ( ¯
X) − X
∆ sxs.
(3.4)
s= m+1
Załóżmy teraz, że rowiązywane ZPL polega na maksymalizacji funkcji celu. Jeżeli ∆ s 0
dla s = m + 1 , . . . , n, to z równości (3.4) wynika, że f ( X) ¬ f ( ¯
X) dla każdego rozwią-
zania dopuszczalnego x, a więc ¯
X jest optymalnym rozwiązaniem rozważanego zadania.
Z drugiej strony, jeżeli istnieje taki wskaźnik s, że xs > 0 oraz ∆ s < 0, to f ( X) > f ( ¯
X
i, w konsekwencji, rozwiązanie bazowe ¯
X nie jest rozwiązaniem optymalnym. Podobne
rozumowanie przeprowadzone w przypadku ZPL(min) pokazuje, że wówczas ¯
X jest roz-
wiązaniem optymalnym, jeżeli wszystkie wskaźniki optymalności są niedodatnie. Zachodzi więc twierdzenie:
Twierdzenie 1. Niech ¯
X będzie bazowym rozwiązaniem dopuszczalnym ZPL
f ( x) → max
(min)
Ax = b,
x 0 ,
zaś X będzie dowolnym rozwiązaniem dopuszczalnym tego zadania. Wówczas 1) jeżeli dla każdej zmiennej niebazowej odpowiadający jej wskażnik optymalności spełnia warunek ∆ j 0 , to f ( X) ¬ f ( ¯
X) ; w szczególności ¯
X jest rozwiązaniem ZPL(max),
2) jeżeli dla każdej zmiennej niebazowej odpowiadający jej wskażnik optymalności spełnia warunek ∆ j ¬ 0 , to f ( X) f ( ¯
X) ; w szczególności ¯
X jest rozwiązaniem ZPL(min).
Na koniec rozważań poświęconych wskaźnikom optymalności zajmiemy się problemem wymiany zmiennej bazowej w nieoptymalnym bazowym rozwiazaniu dopuszczalnym. Ak-tualnie rozważane rozwiązanie bazowe nie jest optymalne, gdy ∆ s < 0 dla pewnego s w przypadku ZPL(max) oraz gdy ∆ s > 0 dla pewnego s w przypadku ZPL(min). W tym 4
przypadku wzór (3.4) pozwala wybrać zmienną niebazową, która zostanie wprowadzona do bazy w następnym rozwiązaniu. Wyboru tej zmiennej należy dokonać w taki sposób, aby w przypadku ZPL(max) (odpowiednio: ZPL(min)) przyrost (odpowiednio: spadek) wartości celu był jak największy. Można to zrobić podstawiając wartość 1 w miejsce sprawdzanej zmiennych niebazowej i 0 w miejsce pozostałych zmiennych niebazowych, a następnie wybierając tę zmienną niebazową, dla której wartość bezwzględna różnicy f ( X) − f ( ¯
X) jest
największa. W przypadku ZPL(max) będzie to ta zmienna niebazowa xs, dla której ∆ s ma wartość najmniejszą, a w przypadku ZPL(min) — ta zmienna niebazowa xs, dla której ∆ s ma wartość największą.
3.3
Opis algorytmu sympleks
Wnioski dotyczące wskaźników optymalności sformułowane w poprzednim podrozdziale pozwalają na opisanie procedury iteracyjnej, w wyniku stosowania której albo zostanie znalezione rozwiązanie optymalne ZPL, albo zostanie ustalone, że takie rozwiązanie optymalne nie istnieje.
Algorytm sympleks
Dane jest ZPL w bazowej postaci kanonicznej:
f ( x 1 , x 2 , . . . , xn) = c 1 x 1 + c 2 x 2 + . . . + cnxn → max (min)
a 11 x 1 + a 12 x 2 + . . . + a 1 nxn
=
b 1 ,
. . .
(3.5)
am 1 x 1 + am 2 x 2 + . . . + amnxn =
bm,
x 1 0 , x 2 0 , . . . , xn 0 .
gdzie współczynniki aij oraz bi są ustalonymi liczbami rzeczywistymi, bi 0 dla każdego i = 1 , 2 , . . . , m oraz m < n, przy czym z kolumn macierzy A = [ aij] można wybrać m kolumn tworzących pełny układ kolumn macierzy jednostkowej I m.
Krok 1. Tworzymy tablicę sympleksową:
zmienne
c 1
c 2
. . .
cn
iloraz
bazowe
cB
x 1
x 2
. . .
xn
b
wyjścia
xk
c
a
1
k 1
11
a 12
. . .
a 1 n
b 1
.
.
.
.
.
.
.
.
.
..
..
..
..
..
xk
c
a
m
km
m 1
am 2
. . .
amn
bm
∆ j
5
Tablica ta zawiera w nagłówku środkowych kolumn nazwy wszystkich zmiennych decyzyjnych i współczynniki znajdujące się we wzorze funkcji celu przy tych zmiennych. Każda z tych kolumn zawiera wyrazy z odpowiedniej kolumny macierzy współczynników układu równań tworzących ograniczenia ZPL. W dwóch kolumnach z lewej strony tabeli wpisujemy nazwy zmiennych bazowych i odpowiednie współczynniki cj w ten sposób, że na przecięciu wiersza i kolumny zawierających zmienną xj znajduje się liczba 1. Dwiema kolumnami po prawej stronie tabeli są: kolumna wyrazów wolnych kolejnych ograniczeń (kolumna ta ozna-czona jest w nagłówku symbolem b) i kolumna, w której wpisywane bedą ilorazy wyjścia.
W ostatnim wierszu tabeli wpiszemy w każdej kolumnie zmiennej niebazowej obliczony dla tej zmiennej wskaźnik optymalności.
Krok 2. Z tablicy sympleksowej odczytujemy dopuszczalne rozwiązanie bazowe X przypisując każdej zmiennej bazowej xk odpowiednią wartość wyrazu wolnego b i
i znajdującego
się w tym samym wierszu. Zmiennym niebazowym przypisujemy wartość 0.
Krok 3. Dla każdej zmiennej niebazowej xj obliczamy wskaźnik optymalności m
∆
X
j =
ck a
i
ij − cj
i=1
i umieszczamy go w ostatnim wierszu tablicy w kolumnie zmiennej niebazowej xj.
Krok 4. Sprawdzamy, czy otrzymane rozwiązanie X jest optymalne. W przypadku ZPL(max) rozwiązanie jest optymalne, jeżeli wszystkie wskaźniki optymalności są nieujemne: ∆ j 0.
W przypadku ZPL(min) rozwiązanie jest optymalne, jeżeli wszystkie wskaźniki optymalności są niedodatnie: ∆ j ¬ 0. Jeżeli rozwiązanie jest optymalne, to kończymy procedurę sympleksową. W przeciwnym wypadku wykonujemy następny krok.
Krok 5. Ustalamy zmienną, która wejdzie do bazy w następnym dopuszczalnym rozwią-
zaniu bazowym. Czynimy to znajdując w przypadku ZPL(max) (odpowiednio: ZPL(min)) najmniejszy (odpowiednio: największy) ze wskaźników optymalności; jest on oczywiście niedodatni (odpowiednio: nieujemny). Zmienna, w której kolumnie znajduje się znaleziony wskaźnik optymalności, jest zmienną wchodzącą do bazy. Załóżmy, że jest to zmienna xj .
0
Krok 6. Ustalamy zmienną, która opuści bazę w następnym dopuszczalnym rozwiązaniu bazowym. W tym celu dla wszystkich dodatnich wyrazów kolumny zmiennej xj obliczamy 0
ilorazy wyjścia:
bi
i = 1 , . . . , m,
(o ile
aij > 0) .
a
0
ij 0
Najmniejszy z obliczonych ilorazów wyjścia wyznacza zmienną wychodzącą z bazy.
Przyjmijmy, że zmienna ta znajduje się w wierszu o numerze i 0, czyli zmienną wychodzącą z bazy jest xk .
i 0
6
Krok 7. Element stojący na skrzyżowaniu kolumny zawierającej zmienną wchodzącą do bazy i wiersza zawierającego zmienną wychodzącą z bazy nazywamy elementem cen-tralnym lub głównym. Korzystając z metody eliminacji Gaussa-Jordana przekształcamy macierz
a 11
a 12
. . . a 1 n
b 1
a
21
a 22
. . . a 2 n
b 2
..
..
..
..
.
.
.
.
am 1 am 2 . . . amn bm
zawartą w tablicy sympleksowej w ten sposób, aby kolumna o numerze j 0 stała się kolumną macierzy jednostkowej z elementem 1 w wierszu o numerze i 0. Otrzymane współ-
czynniki zapisujemy w nowej tablicy sympleksowej, w której z lewej strony zastępujemy nazwę zmiennej wychodzącej z bazy nazwą zmiennej wchodzącej do bazy i wpisujemy odpowiadający jej współczynnik cj. Nazwy pozostałych zmiennych i odpowiednie wartości współczynników pozostawiamy bez zmian. Dla tak otrzymanej nowej tablicy sympleksowej powracamy do kroku 2.
7