Metody numeryczne - laboratorium
Ćwiczenie 9,10: Programowanie liniowe  metoda simplex
Zadanie programowania liniowego ZPL
Definiuje się N niezależnych zmiennych x1, x2, ..., xN wraz z liniową funkcją celu
z = a01x1 + a02 x2 + ... + a0 N xN .
Poszukuje się maksymalnej wartości funkcji celu z przy następujących ograniczeniach:
- N podstawowych: x1 e" 0, x2 e" 0,..., xN e" 0,
- M=m1+m2+m3 dodatkowych:
ai1x1 + ai2 x2 + ... + aiN xN d" bi , bi e" 0 , i = 1,..., m1
a x1 + a x2 + ... + a xN e" bj , bj e" 0 , j = m1 +1,...,m1 + m2
j1 j2 jN
ak1x1 + ak 2 x2 + ... + akN xN = bk , bk e" 0 , k = m1 + m2 +1,..., m1 + m2 + m3
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, m1=2, m2=m3=1, stąd M=4. Znalez
ć maksimum
funkcji
1
z = x1 + x2 + 3x3 - x4
2
przy ograniczeniach podstawowych x1 e" 0, x2 e" 0, x3 e" 0, x4 e" 0 oraz dodatkowych
x1 + 2x3 d" 740
2x2 - 7x4 d" 0
1
x2 - x3 + 2x4 e"
2
x1 + x2 + x3 + x4 = 9
Rozwiązaniem tak postawionego zadania jest następujący wektor: x1=0, x2=3.33, x2=4.73, x4=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
1
Wyobraz
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łaszczyz
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 x1 e" 0 . 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
2
Przykład 2 (postać normalna ZPL)
Dane jest ZPL o następujących parametrach: N=4, m1=2, m2=m3=0, stąd M=2. Znalez
ć maksimum
funkcji
z = 2x2 - 4x3
przy ograniczeniach podstawowych x1 e" 0, x2 e" 0, x3 e" 0, x4 e" 0 oraz dodatkowych
x1 = 2 - 6x2 + x3
x4 = 8 + 3x2 - 4x3
Zmienne bazowe przy tej postaci to x1, x4, a niebazowe to x2, x3. 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:
Zmienne niebazowe x2, x3
Aktualna wartość f. celu
x2 x3
z 0 2 -4
Funkcja celu
x1 2 -6 1
Element centralny yrk
x4 8 3 -4
Zmienne bazowe x1, x4
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.
Ćwiczenie 9,10: Programowanie liniowe  metoda simplex
3
W rozpatrywanym przykładzie jedynie kolumna x2 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 x2
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:
1 1 1
x1 = 2 - 6x2 + x3 x2 = - x1 + x3
3 6 6
1 1 1 1 7
ëÅ‚ öÅ‚
x4 = 8 + 3 - x1 + x3 - 4x3 = 9 - x1 - x3
ìÅ‚ ÷Å‚
3 6 6 2 2
íÅ‚ Å‚Å‚
Aktualizacja funkcji celu:
1 1 1 2 1 11
z = 2x2 - 4x3 = 2ëÅ‚ - x1 + x3 öÅ‚ - 4x3 = - x1 - x3
ìÅ‚ ÷Å‚
3 6 6 3 3 3
íÅ‚ Å‚Å‚
Powyższe równania tworzą nową tabelę sympleksową:
x1 x3
-4+2*(1/6)=-11/3
2/(-6)=-1/3
z 2/3 -1/3 -11/3
-4+3*(1/6)=-7/2
x2 1/3 -1/6 1/6
8+3*(1/3)=9
x4 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:
1
x1 = 0, x2 = , x3 = 0, x4 = 9
3
Optymalna wartość funkcji celu wynosi z=1/3.
Kolejne kroki algorytmu simplex (dla tablicy składającej się z elementów aij):
1. Określ element centralny dla kolejnej iteracji ark (znajduje się on na przecięciu
kolumny k oraz wiersza r).
2. Wiersz r-ty podziel przez minus element centralny -ark.
3. Do każdego i-tego z pozostałych wierszy dodaj wiersz centralny pomnożony przez
aik.
4. OryginalnÄ… kolumnÄ™ k-tÄ… podziel przez element centralny ark.
5. Element centralny ark zastąp jego odwrotnością 1/ark.
6. Powtarzaj procedurę dopóki możliwe jest określenie elementu centralnego.
Ćwiczenie 9,10: Programowanie liniowe  metoda simplex
4
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ć:
x1 + 2x3 + y1 = 740
2x2 - 7x4 + y2 = 0
1
x2 - x3 + 2x4 - y3 =
2
x1 + x2 + x3 + x4 = 9
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ć
z1 = 740 - x1 - 2x3 - y1
z2 = -2x2 + 7x4 - y2
1
z3 = - x2 + x3 - 2x4 + y3
2
z4 = 9 - x1 - x2 - x3 - x4
Tak określone zadanie będzie równoważne zadaniu poprzedniemu tylko wtedy, gdy wszystkie
zmienne zi są równe 0. Stąd w pierwszej fazie rozwiązywania problemu wprowadza się dodatkową
funkcję celu określoną jako
1
z'a" -z1 - z2 - z3 - z4 = -ëÅ‚749 - 2x1 - 4x2 - 2x3 + 4x4 - y1 - y2 + y3 öÅ‚
ìÅ‚ ÷Å‚
2
íÅ‚ Å‚Å‚
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 xi, yi 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
5
 x1 x2 x3 x4 y1 y2 y3
z 0 1 1 3 -1/2 0 0 0
z1 740 -1 0 -2 0 -1 0 0
z2 0 0 -2 0 7 0 -1 0
z3 1/2 0 -1 1 -2 0 0 1
z4 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ć:
x1 y2 y3
z 17.03 -0.95 -0.05 -1.05
x2 3.33 -0.35 -0.15 0.35
x3 4.73 -0.55 0.05 -0.45
x4 0.95 -0.10 0.10 0.10
y1 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
6
Zadania laboratoryjne
Napisać program rozwiązujący zadanie programowania liniowego. Za pomocą napisanego programu
rozwiązań następujące problemy.
a) max z = 3x1 + 2x2 + x3
przy ograniczeniach:
x1 e" 0, x2 e" 0, x3 e" 0
x1 + 3x2 + 2x3 = 4
2x1 - 4x2 + x3 = 5
b) max z = 2x1 + x2 - 3x3 + 4x4
przy ograniczeniach:
x1 e" 0, x2 e" 0, x3 e" 0, x4 e" 0
x1 + 2x2 + 2x4 = 1
3x2 + 2x3 + x4 = 3
c) max z = 7x1 +11x2
przy ograniczeniach:
x1 e" 0, x2 e" 0
3x1 + 3x2 d" 21
2x1 + 4x2 d" 20
d) max z = x1 - x2
przy ograniczeniach:
x1 e" 0, x2 e" 0
2x1 - x2 e" 2
x1 + x2 d" 5
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
Ćwiczenie 9,10: Programowanie liniowe  metoda simplex
7