Ć
wiczenie 9,10: Programowanie liniowe – metoda simplex
1
Metody numeryczne - laboratorium
Ć
wiczenie 9,10: Programowanie liniowe – metoda simplex
Zadanie programowania liniowego ZPL
Definiuje się N niezależnych zmiennych x
1
, x
2
, ..., x
N
wraz z liniową funkcją celu
N
N
x
a
x
a
x
a
z
0
2
02
1
01
... +
+
+
=
.
Poszukuje się maksymalnej wartości funkcji celu z przy następujących ograniczeniach:
- N podstawowych:
,
0
,...,
0
,
0
2
1
≥
≥
≥
N
x
x
x
- M=m
1
+m
2
+m
3
dodatkowych:
i
N
iN
i
i
b
x
a
x
a
x
a
≤
+
+
+
...
2
2
1
1
,
0
≥
i
b
,
1
,...,
1
m
i =
j
N
jN
j
j
b
x
a
x
a
x
a
≥
+
+
+
...
2
2
1
1
,
0
≥
j
b
,
2
1
1
,...,
1
m
m
m
j
+
+
=
k
N
kN
k
k
b
x
a
x
a
x
a
=
+
+
+
...
2
2
1
1
,
0
≥
k
b
,
3
2
1
2
1
,...,
1
m
m
m
m
m
k
+
+
+
+
=
Wektor x, który spełnia wszystkie ograniczenia nazywa się wektorem dopuszczalnym. Wektor, który
maksymalizuje funkcję celu nazywa się optymalnym wektorem dopuszczalnym. Wektor, który
reprezentuje punkt wierzchołka obszaru ograniczonego nazywa się bazowym wektorem
dopuszczalnym.
Rozwiązanie ZPL może nie istnieć z dwóch powodów:
- nie istnieją wektory dopuszczalne (ograniczenia są sprzeczne),
- nie ma wartości maksymalnej (jedna ze zmiennych może dążyć do nieskończoności).
Przykład 1
Dane jest ZPL o następujących parametrach: N=4, m
1
=2, m
2
=m
3
=1, stąd M=4. Znaleźć maksimum
funkcji
4
3
2
1
2
1
3
x
x
x
x
z
−
+
+
=
przy ograniczeniach podstawowych
0
,
0
,
0
,
0
4
3
2
1
≥
≥
≥
≥
x
x
x
x
oraz dodatkowych
9
2
1
2
0
7
2
740
2
4
3
2
1
4
3
2
4
2
3
1
=
+
+
+
≥
+
−
≤
−
≤
+
x
x
x
x
x
x
x
x
x
x
x
Rozwiązaniem tak postawionego zadania jest następujący wektor: x
1
=0, x
2
=3.33, x
2
=4.73, x
4
=0.95.
Twierdzenie 1 (Podstawowe twierdzenie optymalizacji liniowej)
Jeżeli istnieje optymalny wektor dopuszczalny, to istnieje bazowy wektor dopuszczalny, który jest
optymalny.
Ć
wiczenie 9,10: Programowanie liniowe – metoda simplex
2
Wyobraźmy sobie, że ZPL określone jest na N wymiarowej przestrzeni. Ograniczenia określają pewną
dopuszczalną podprzestrzeń, której granice są opisane hiperpłaszczyznami. Ponieważ funkcja celu
jest liniowa (ma niezerowy gradient), optymalny wektor dopuszczalny nigdy nie będzie umiejscowiony
wewnątrz podprzestrzeni (poruszając się wzdłuż gradientu funkcji celu zawsze natkniemy się na
płaszczyznę ograniczającą).
Brzeg dowolnego obszaru geometrycznego ma wymiar o jeden mniejszy niż jego wnętrze.
Analogicznie poruszając się wzdłuż gradientu rzutowanego na N-1 wymiarową płaszczyznę
ograniczającą, otrzymuje się punkt będący brzegiem tej płaszczyzny. Kontynuując ten proces
dochodzimy do sytuacji, gdy brzeg obszaru został zredukowany do punktu. Ponieważ wektor
reprezentujący ten punkt opisany jest przez N zmiennych oraz leży on na płaszczyźnie ograniczającej
obszar dopuszczalny, to jest on jednocześnie rozwiązaniem N równości wynikających ze wszystkich
ograniczeń.
Wektory dopuszczalne, które spełniają N ograniczeń równościowych nazywane są bazowymi
wektorami dopuszczalnymi i reprezentują punkty wierzchołkowe obszaru dopuszczalnego. Jeżeli
N>M, to dopuszczalny wektor bazowy ma przynajmniej N-M składowych równych zero (ponieważ
przynajmniej tyle ograniczeń będzie dopełniać N współrzędnych wektora, które muszą spełniać
ograniczenia równościowe). Oznacza to, że najwyżej M składowych wektora będzie niezerowych.
W przykładzie 1 można sprawdzić (przez podstawienie), że otrzymane rozwiązanie spełnia 3 pierwsze
ograniczenia w sposób równościowy oraz dodatkowo ograniczenie na
0
1
≥
x
. W ten sposób
optymalny wektor dopuszczalny ma 4 składowe, które spełniają 4 ograniczenia równościowe. Jest to
jednocześnie bazowy wektor dopuszczalny.
Powyższe rozumowanie pozwala na zamianę zadania optymalizacji na problem
kombinatoryczny, w którym należy stwierdzić, które N ograniczeń (ze wszystkich M+N ograniczeń)
powinno być spełnione przez wektor dopuszczalny, aby otrzymać rozwiązanie optymalne. Oznacza to
wybór wektora reprezentującego odpowiedni wierzchołek obszaru dopuszczalnego (wektora
bazowego). Rozwiązanie tego problemu otrzymuje się na przykład przez zastosowanie algorytmu
simplex.
Algorytm simplex (Dantzig, 1948)
Zakłada się, że zadanie programowania liniowego zapisane jest w postaci, w której (normalna postać
ZPL):
- występują tylko ograniczenia równościowe,
- każde ograniczenie posiada zmienną z dodatnim współczynnikiem, który występuje tylko w tym
ograniczeniu.
Jeżeli powyższe założenia nie są spełnione, to ZPL trzeba sprowadzić do takiej postaci.
Dzięki powyższym założeniom można wybrać tzw. zmienne bazowe, względem których zostaną
rozwiązane M równania reprezentujące ograniczenia równościowe. Pozostałe N-M zmiennych nazywa
się zmiennymi niebazowymi. Funkcja celu zapisana jest wyłącznie za pomocą zmiennych
niebazowych (w tak postawionym problemie każdą funkcję celu można przedstawić za pomocą
zmiennych niebazowych przez podstawienie).
Ć
wiczenie 9,10: Programowanie liniowe – metoda simplex
3
Przykład 2 (postać normalna ZPL)
Dane jest ZPL o następujących parametrach: N=4, m
1
=2, m
2
=m
3
=0, stąd M=2. Znaleźć maksimum
funkcji
3
2
4
2
x
x
z
−
=
przy ograniczeniach podstawowych
0
,
0
,
0
,
0
4
3
2
1
≥
≥
≥
≥
x
x
x
x
oraz dodatkowych
3
2
4
3
2
1
4
3
8
6
2
x
x
x
x
x
x
−
+
=
+
−
=
Zmienne bazowe przy tej postaci to x
1
, x
4
, a niebazowe to x
2
, x
3
. Z postaci normalnej ZPL w każdym
momencie można bardzo łatwo odczytać dopuszczalny wektor bazowy (który niekoniecznie jest
optymalny). Robi się to podstawiając wartość zero za wszystkie zmienne niebazowe. W ten sposób
otrzymuje się wektor, dla którego ograniczenia równościowe są spełnione. Metoda simplex polega na
przeprowadzeniu wymienianiu zmiennych bazowych z niebazowymi tak, aby zachowane były
ograniczenia oraz wartość funkcji celu rosła. Zadanie w postaci normalnej może zostać zapisane w
następującej tabeli:
x
2
x
3
z
0
2
-4
x
1
2
-6
1
x
4
8
3
-4
Ustala się wartość zmiennych niebazowych na zero. Powstaje pytanie, jak zmieni się wartość funkcji
celu, gdy jedna ze zmiennych bazowych zostanie zwiększona (przy pozostałych cały czas równych 0).
Jeżeli współczynniki przy tej zmiennej są dodatnie, to przy jej zwiększaniu również funkcja celu
zwiększy swoją wartość. Dlatego rozpatrujemy tylko kolumny, w których współczynniki przy zmiennych
niebazowych są dodatnie. Jeżeli takiej kolumny nie ma, to znaczy, że funkcja celu nie może dalej
wzrosnąć, czyli jest już maksymalna.
Dla danej kolumny (dla której współczynnik jest dodatni) pytamy, jak bardzo możemy
zwiększyć wartość danej zmiennej, aby zmienne bazowe nie stały się ujemne (co jest niedozwolone
ze względu na podstawowe ograniczenia). Jeżeli element tablicy na przecięciu analizowanej kolumny i
danej zmiennej bazowej jest dodatni, to znaczy, że nie ma ograniczeń. Jeżeli wszystkie elementy w
każdej kolumnie niebazowej są dodatnie, to znaczy, że zadanie jest nieograniczone.
Jeżeli jeden z elementów analizowanej kolumny jest ujemny (element centralny), to będzie on
miał wpływ na maksymalne możliwe zwiększenie wartości elementu niebazowego. Granica ta
określona jest przez podzielenie składowej wektora bazowego przez element centralny. Największe
ograniczenie wprowadzi najmniejsza wartość wyznaczona dla każdego rozpatrywanego wiersza.
Ograniczenie to określa się dla każdej z kolumn, która ma dodatni współczynnik. Jako kolumnę
centralną można wybrać tą, której zamiana powoduje powiększenie funkcji celu o największą wartość.
W ten sposób wybrany zostaje element centralny.
Zmienne niebazowe x
2
, x
3
Zmienne bazowe x
1
, x
4
Funkcja celu
Aktualna wartość f. celu
Element centralny y
rk
Ć
wiczenie 9,10: Programowanie liniowe – metoda simplex
4
W rozpatrywanym przykładzie jedynie kolumna x
2
ma niezerowy współczynnik o wartości 2.
Dodatkowo jest tylko jeden element ujemny w tej kolumnie (o wartości -6), który zostanie elementem
centralnym. Wartość w kolumnie stałej wynosi 2. Stąd takie przestawienie pozwoli, aby składowa x
2
wzrosła o 2/6, natomiast wartość funkcji celu wzrośnie o (2*2)/6.
Trzecim krokiem procedury jest wykonanie zaplanowanej zamiany. Oznacza to, że wartość
wybranego elementu bazowego zostanie zmniejszona do 0, przez co stanie się on elementem
niebazowym. Natomiast poprzedni element niebazowy wzrośnie o zadaną wartość (w tym wypadku o
1/3) i zostanie nowym elementem bazowym. Wartość funkcji celu również wzrośnie. Wymaga to
aktualizacji pozostałych współczynników ze względu na następującą zamianę zmiennych:
3
2
1
6
2
x
x
x
+
−
=
→
3
1
2
6
1
6
1
3
1
x
x
x
+
−
=
3
1
3
3
1
4
2
7
2
1
9
4
6
1
6
1
3
1
3
8
x
x
x
x
x
x
−
−
=
−
+
−
+
=
Aktualizacja funkcji celu:
3
1
3
3
1
3
2
3
11
3
1
3
2
4
6
1
6
1
3
1
2
4
2
x
x
x
x
x
x
x
z
−
−
=
−
+
−
=
−
=
Powyższe równania tworzą nową tabelę sympleksową:
x
1
x
3
z
2/3
-1/3
-11/3
x
2
1/3
-1/6
1/6
x
4
9
-1/2
-7/2
Powyższa procedura jest powtarzana tak długo, aż istnieją zmienne niebazowe, które mają
dodatnie współczynniki. W powyższym przykładzie nie ma możliwości dalszego zwiększania funkcji
celu. Rozwiązanie może być odczytane wprost z tablicy:
9
,
0
,
3
1
,
0
4
3
2
1
=
=
=
=
x
x
x
x
Optymalna wartość funkcji celu wynosi z=1/3.
Kolejne kroki algorytmu simplex (dla tablicy składającej się z elementów a
ij
):
1.
Określ element centralny dla kolejnej iteracji a
rk
(znajduje się on na przecięciu
kolumny k oraz wiersza r).
2.
Wiersz r-ty podziel przez minus element centralny -a
rk.
3.
Do każdego i-tego z pozostałych wierszy dodaj wiersz centralny pomnożony przez
a
ik.
4.
Oryginalną kolumnę k-tą podziel przez element centralny a
rk.
5.
Element centralny a
rk
zastąp jego odwrotnością 1/a
rk.
6.
Powtarzaj procedurę dopóki możliwe jest określenie elementu centralnego.
8+3*(1/3)=9
-4+3*(1/6)=-7/2
-4+2*(1/6)=-11/3
2/(-6)=-1/3
Ć
wiczenie 9,10: Programowanie liniowe – metoda simplex
5
Może się zdarzyć, że jeden z elementów wektora bazowego jest zerowy. Jest to tak zwany
zdegenerowany wektor dopuszczalny. W takim wypadku należy tak długo wymieniać zdegenerowaną
składową bazową z niebazową, aż otrzyma się wektor niezdegenerowany.
Sprowadzanie problemu do postaci normalnej
Zamiana na ograniczenia równościowe
Postać normalna ZPL wymaga, aby występowały jedynie ograniczenia równościowe. Jeżeli w zadaniu
występuje inny rodzaj ograniczeń, możliwe jest sprowadzenie ich do ograniczeń równościowych przez
wprowadzenie tak zwanych zmiennych dopełniających. Ich znak zależy od rodzaju ograniczenia w
zadaniu początkowym. Dla przykładu 1 ograniczenia w postaci normalnej przyjmują postać:
9
2
1
2
0
7
2
740
2
4
3
2
1
3
4
3
2
2
4
2
1
3
1
=
+
+
+
=
−
+
−
=
+
−
=
+
+
x
x
x
x
y
x
x
x
y
x
x
y
x
x
Znajdowanie początkowego dopuszczalnego wektora bazowego
Aby możliwe było zapoczątkowanie metody simplex, konieczne jest określenie M wektorów bazowych,
czyli znalezienie dowolnego dopuszczalnego wektora bazowego. W tym celu wprowadza się do
zadania M dodatkowych zmiennych dopełniających (sztucznych). Rozpatrywany przykład przyjmuje
postać
4
3
2
1
4
3
4
3
2
3
2
4
2
2
1
3
1
1
9
2
2
1
7
2
2
740
x
x
x
x
z
y
x
x
x
z
y
x
x
z
y
x
x
z
−
−
−
−
=
+
−
+
−
=
−
+
−
=
−
−
−
=
Tak określone zadanie będzie równoważne zadaniu poprzedniemu tylko wtedy, gdy wszystkie
zmienne z
i
są równe 0. Stąd w pierwszej fazie rozwiązywania problemu wprowadza się dodatkową
funkcję celu określoną jako
+
−
−
+
−
−
−
−
=
−
−
−
−
≡
3
2
1
4
3
2
1
4
3
2
1
4
2
4
2
2
1
749
'
y
y
y
x
x
x
x
z
z
z
z
z
Następnie uruchamia się procedurę simplex dla tak zdefiniowanego zadania. Celem jest
maksymalizacja pomocniczej funkcji celu z`, która powinna przyjąć wartość zero dla pewnego
wierzchołka bazowego. Jeżeli taki wierzchołek istnieje (istnieje przynajmniej jeden dopuszczalny
wektor bazowy), to wszystkie zmienne pomocnicze staną się zmiennym niebazowymi. Można je wtedy
pominąć, a otrzymana tablica opisuje początkowe zadanie w postaci normalnej ze zmiennymi x
i
, y
i
z
określonym dopuszczalnym wektorem bazowym.
Tablica sympleksowa opisująca przykładowe zadanie pomocnicze rozwiązywane w pierwszej fazie
wygląda następująco:
Ć
wiczenie 9,10: Programowanie liniowe – metoda simplex
6
x
1
x
2
x
3
x
4
y
1
y
2
y
3
z
0
1
1
3
-1/2
0
0
0
z
1
740
-1
0
-2
0
-1
0
0
z
2
0
0
-2
0
7
0
-1
0
z
3
1/2
0
-1
1
-2
0
0
1
z
4
9
-1
-1
-1
-1
0
0
0
z’
-749,5
2
4
2
-4
1
1
-1
Jest to więc tylko inny sposób zapisania zadania początkowego. Ostateczna postać tablicy dla
rozpatrywanego przykładu (po wykreśleniu zmiennych pomocniczych) przyjmuje postać:
x
1
y
2
y
3
z
17.03
-0.95
-0.05
-1.05
x
2
3.33
-0.35
-0.15
0.35
x
3
4.73
-0.55
0.05
-0.45
x
4
0.95
-0.10
0.10
0.10
y
1
730.55
0.10
-0.10
0.90
Pierwsza kolumna tablicy zawiera optymalny wektor będący rozwiązaniem zadania wraz z wartością
funkcji celu osiąganą dla tego punktu. Zmienne, które są niebazowe przyjmują w rozwiązaniu wartość
zero. Zmienne dopełniające o wartości zero reprezentują ograniczenia, które są spełnione jako
równości. Wartość zmiennych dopełniających określa, do jakiej wartości odpowiadające im
ograniczenia nierównościowe są spełnione.
Ć
wiczenie 9,10: Programowanie liniowe – metoda simplex
7
Zadania laboratoryjne
Napisać program rozwiązujący zadanie programowania liniowego. Za pomocą napisanego programu
rozwiązań następujące problemy.
a)
3
2
1
2
3
max
x
x
x
z
+
+
=
przy ograniczeniach:
0
,
0
,
0
3
2
1
≥
≥
≥
x
x
x
4
2
3
3
2
1
=
+
+
x
x
x
5
4
2
3
2
1
=
+
−
x
x
x
b)
4
3
2
1
4
3
2
max
x
x
x
x
z
+
−
+
=
przy ograniczeniach:
0
,
0
,
0
,
0
4
3
2
1
≥
≥
≥
≥
x
x
x
x
1
2
2
4
2
1
=
+
+
x
x
x
3
2
3
4
3
2
=
+
+
x
x
x
c)
2
1
11
7
max
x
x
z
+
=
przy ograniczeniach:
0
,
0
2
1
≥
≥
x
x
20
4
2
21
3
3
2
1
2
1
≤
+
≤
+
x
x
x
x
d)
2
1
max
x
x
z
−
=
przy ograniczeniach:
0
,
0
2
1
≥
≥
x
x
2
2
2
1
≥
− x
x
5
2
1
≤
+ x
x
Dla jednego z przykładów pokazać kolejne operacje wykonywane na tablicy sympleksowej.
Literatura
[1] Press W., Teukolsky S., Vetterling W., Flannery B. Numerical Recipes in C, Cambridge University
Press, 2002
[2] Findeisen W., Szymanowski J. Teoria i metody obliczeniowe optymalizacji, PWN, 1980
[3] Stachurski A., Wierzbicki A.P., Podstawy optymalizacji, WPW, 1999