Algorytm sympleks wymaga by obszar dopuszczalny, na którym badamy ekstrema funkcji celu, był wielościanem z wierzchołkiem. Dowolny wielościan możemy ”przerobić” na wielościan z wierzchołkiem przechodząc do zadania równoważnego i zamieniając zmienne tak by były nieujemne.
Jeżeli to zastępujemy je nową zmienną
, gdzie
.
Jeżeli jest nieograniczone to zastępujemy je różnicą
, gdzie
oraz
.
W szczególności w tym rozdziale będziemy badać wielościany zapisane w postaci kanonicznej czyli .
Opis wierzchołków i krawędzi zadania w postaci
kanonicznej.
Niech będzie
wielościanem. Dodatkowo zakładamy, że równania opisujące
są
liniowo niezależne -
czyli
liczba równań.
Niech
będzie wierzchołkiem
. Ze zbioru równań i ”nierówności
spełnionych jako równości” które spełnia wierzchołek
wybieramy
liniowo niezależnych w specjalny sposób. Po pierwsze wybieramy
równań
opisujących wielościan a potem uzupełniamy do
liniowo niezależnych równań dodając pewne
.
Wynika to z lematu Steinitza o bazie. Dokładniej: ze zbioru równań spełnianych przez wybieramy dowolnie bazę
-
liniowo niezależnych równań. Następnie zbiór liniowo niezależny
uzupełniamy do bazy równaniami z
. Muszą to być równania typu
Otrzymaliśmy układ
liniowo niezależnych równań z
niewiadomymi, którego jedynym rozwiązaniem jest punkt
. Macierz tego układu oznaczmy literą U.
Zmienne nazywamy niebazowymi zaś pozostałe
bazowymi.
Współrzędne niebazowe wierzchołka są równe
.
Uwaga: Wierzchołek ma co najwyżej niezerowych współrzędnych.
Dla ułatwienia przenumerujmy tak zmienne by były
zmiennymi niebazowymi oraz
zmiennymi bazowymi.
Wtedy macierz równania opisującego składa się z 3 części
, gdzie
jest macierzą kwadratową.
jest odwracalna.
Mnożąc układ równań z lewej strony przez macierz
otrzymujemy równoważny opis wielościanu
Zaś wierzchołek ma współrzędne
.
Podsumowując, każdemu wierzchołkowi, przez wybór zmiennych bazowych przyporządkowujemy układ równań o macierzy zawierającej podmacierz jednostkową.
Tablicą sympleks nazywamy taką macierz rozszerzoną układu
równań , że
zawiera podmacierz jednostkową rozmiaru t. Dokładniej,
można z macierzy
tak powykreślać kolumny i poprzestawiać
wiersze by uzyskać macierz jednostkową.
Tablicę sympleks nazywamy pierwotnie dopuszczalną gdy wszystkie
wyrazy wolne są . Co zapisujemy
.
Jak pokazaliśmy poprzednio każdemu wierzchołkowi odpowiada co najmniej jedna tablica sympleks pierwotnie dopuszczalna. Dokładniej tyle tablic ile jest możliwości wyboru zmiennych (nie)bazowych.
Pierwotnie dopuszczalne tablice sympleks opisują wierzchołki.
Niech będzie tablicą sympleks pierwotnie dopuszczalną. W
macierzy wybieramy kolumny tworzące macierz jednostkową. Zmienne
odpowiadające tym kolumną nazwiemy bazowymi zaś pozostałe
niebazowymi. Zmiennym niebazowym przypisujemy wartość 0. Bazowe
zmienne wyliczamy z układu równań po opuszczeniu zmiennych
niebazowych. Tak więc zmienne bazowe przyjmują wartości wyrazów
wolnych w odpowiedniej kolejności. Otrzymany punkt jest
wierzchołkiem gdyż spełnia
nierówności jako równania.
z
równań
i
z równań
spełnianych przez zmienne
niebazowe. Dodatkowo równania te są liniowo niezależne.
Niech będzie
wielościanem. Dodatkowo zakładamy, że równania opisujące
są
liniowo niezależne -
czyli
liczba równań. Niech
będzie wierzchołkiem
. Wówczas:
a) Liczba niezerowych współrzędnych wierzchołka jest nie większa niż liczba równań.
b) Istnieje taka odwracalna podmacierz macierzy
, że
jest tablicą sympleks opisującą wierzchołek
.
c) Niech będzie odwracalną podmacierzą macierzy
. Wówczas
jest tablicą sympleks opisującą wierzchołek
wtedy i tylko wtedy gdy macierz
zawiera wszystkie kolumny
, których indeksy są indeksami niezerowych współrzędnych wierzchołka
.
Jeżeli w wielościanie opisanym
równaniami wierzchołek
ma
niezerowych współrzędnych to jest opisany dokładnie jedną tablicą sympleks.
W tablicy sympleks
możemy wybrać kolumny 1, 2 i 7. Niebazowymi
zmiennymi są
i one przyjmują wartość 0.
Wykreślamy kolumny zmiennych niebazowych i zmienne bazowe
wyliczamy z równania o macierzy
.
Więc
,
i
. Wierzchołkiem
jest
.
Wybierzmy teraz kolumny 2,
4 i 7. Otrzymamy wierzchołek
.
Niech ![]() |
wielościanem. Dodatkowo zakładamy, że równania opisujące ![]() |
liniowo niezależne - czyli ![]() |
Wybieramy maksymalne kwadratowe podmacierze ![]() ![]() |
Jeżeli ![]() ![]() |
przez ![]() |
Jeżeli otrzymana tablica jest pierwotnie dopuszczalna to opisuje |
wierzchołek. |
Niech ![]() |
opisującą wierzchołek ![]() |
wierzchołka. Zaczynamy od wybrania ![]() |
wierzchołek. Nie możemy odrzucać równań z układu ![]() |
pewnej zmiennej niebazowej zamiast ![]() ![]() |
Otrzymujemy opis prostej w której zmienna ![]() |
parametrem. Dla ustalenia uwagi przyjmijmy |
![]() |
Teraz wyliczamy zmienne bazowe ![]() ![]() |
postać ![]() ![]() |
Jeżeli wszystkie ![]() |
![]() |
W przeciwnym |
przypadku największą wartością ![]() |
dodatnich ![]() ![]() |
![]() |
Liczba wyznacza długość krawędzi. Jeżeli startujemy z wierzchołka
i poruszamy się w kierunku
to
jest kolejnym wierzchołkiem. Długością krawędzi jest liczba
.
Jeżeli minimum to krawędź ma długość 0 ( jest punktem ) i
nazywamy ją krawędzią zdegenerowaną.
Niech będzie pierwotnie dopuszczalną tablicą sympleks, z ustaloną bazą i opisującą wierzchołek
. Wówczas
opisuje
krawędzi wychodzących z wierzchołka
i wektory kierunkowe tych krawędzi są liniowo niezależne. Wliczamy krawędzie zdegenerowane zaś
oznacza liczbę kolumn i
liczbę wierszy.
Ustawmy wektory kierunkowe w macierz a następnie wykreślmy kolumny zmiennych bazowych. Otrzymaliśmy macierz jednostkową . Zatem wektory były liniowo niezależne.
Aby opisać wszystkie krawędzie wychodzące z wierzchołka należy
użyć wszystkich tablic sympleks opisujących
.
Opiszmy ostrosłup o podstawie kwadratowej z
wierzchołkami
i o szczycie w punkcie
.
jest opisane układem nierówności:
Przerabiamy nierówności na równania dodając nowe zmienne i otrzymujemy postać kanoniczna:
Zapiszmy w postaci tablicy sympleks:
Zmiennymi bazowymi są i
zaś
opisuje
wierzchołek:
,
Poruszamy się w kierunku wierzchołka krawędzią
wyznaczoną przez
:
.
Szukamy elementu centralnego.
zatem możemy
wybrać dowolny element kolumny 3-ciej.
. Zmiennymi bazowymi są teraz
i
zaś
opisuje wierzchołek
Ile krawędzi wychodzi z ?
Z rysunku widać, że 4, zaś tablica opisuje tylko trzy krawędzie o
wektorach kierunkowych
- krawędź zdegenerowana
(długość 0) gdyż
w kierunku wierzchołka
w kierunku wierzchołka
Wędrując wzdłuż krawędzi zdegenerowanej znajdujemy nową TS opisującą
.
Otrzymujemy
Tablica opisuje dalej wierzchołek
i
krawędzie:
w kierunku wierzchołka
- zdegenerowana
w kierunku wierzchołka
Tablicą Sympleks opisującą zadanie programowania liniowego
![]() |
nazywamy taką macierz, w której pierwszy wiersz reprezentuje
równanie , pozostałe wiersze równania
i macierz ta zawiera podmacierz jednostkową. Zwyczajowo
pierwszy wiersz - opisujący funkcję celu jest oddzielony linią
poziomą. Podobnie znak równości przedstawiamy jako linię pionową.
Tablicę sympleks nazywamy dualnie dopuszczalną gdy w wierszu kosztów zredukowanych (nad kreską ) wszystkie
wyrazy są , dla zadania typu Max lub są
, dla zadania typu Min.
Tablicą sympleks dla zadania
Max , gdy:
,
,
jest
Funkcję celu zastąpiliśmy równaniem zaś
podmacierz jednostkowa powstaje z kolumn odpowiadających zmiennym
o indeksach 0,4,5 i 6.
Ponieważ w algorytmie metody sympleks kolumna odpowiadająca zmiennej nie zmienia się więc zwykle ją pomijamy.
Poniższe dwie tablice sympleks opisują to samo zadanie PL.
wylicz zmienne od do
.
1 | 0 | 0 | 2 | -3 | 5 |
2 | 1 | 0 | -2 | d | e |
-3 | a | b | c | 2 | 4 |
7 | g | h | 0 | -7 | -3 |
---|---|---|---|---|---|
-4 | 1 | 2 | i | 5 | 14 |
f | 0 | 1 | j | k | ![]() |
Wiedząc, że poniższe tablice sympleks dotyczą tego samego zadania programowania liniowego wyznacz nieznane
współczynniki od do
.
oraz
Wiedząc, że punkt jest
wierzchołkiem wielościanu
, gdzie
wypisz wszystkie takie macierze , zawarte w
, że
jest tablicą sympleks opisującą .
Wędrowanie między wierzchołkami, eliminacja Gaussa - Jordana.
W zadaniu PL mamy wierzchołek opisany tablicą sympleks. Dla
ustalenia uwagi przyjmijmy
Zakładamy, że krawędź odpowiadająca zmiennej jest skończona
i szukamy tablicy sympleks opisującej drugi koniec tej krawędzi.
Wyliczamy minimum po wszystkich dodatnich z liczb
czyli liczbę
. Wybieramy dowolny współczynnik
,
na którym osiągane jest minimum. Nazywamy go elementem
centralnym. Na następnej tablicy zaznaczony będzie nawiasem.
Teraz j - ty wiersz dzielimy przez zaś od każdego innego
wiersza
odejmujemy poprawiony j-ty wiersz pomnożony przez
- czyli zerujemy pozostałe miejsca k-tej kolumny.
Otrzymujemy macierz:
,
gdzie
Otrzymaliśmy tablicę sympleks. Z bazy wypadła zmienna a
doszła zmienna
.
Test optymalności i koszty zredukowane. Rozważamy zadanie typu
![]() |
opisane tablicą sympleks TS. Oznacza to, że w górnym wierszu TS mamy kolejno liczby
![]() |
.
Ponieważ jest to tablica sympleks
wszystkie współczynniki odpowiadające zmiennym bazowym są
równe 0.
Jeżeli koszt zredukowany odpowiadający zmiennej niebazowej
jest
(
) to krawędź wyznaczona przez zmienną
jest poprawiająca. Ponieważ wędrując tą krawędzią zmieniamy
tylko zmienne bazowe nie mające wpływu na funkcję celu i
zwiększamy liczbę
.
Jeżeli koszt zredukowany odpowiadający zmiennej niebazowej
jest = 0 (
) to krawędź wyznaczona przez zmienną
jest neutralna.
Jeżeli koszt zredukowany odpowiadający zmiennej niebazowej
jest
(
) to krawędź wyznaczona przez zmienną
jest pogarszająca. Ponieważ wędrując tą krawędzią zmieniamy
tylko zmienne bazowe nie mające wpływu na funkcję celu i
zmniejszamy liczbę
![]() |
.
Jeżeli w tablicy sympleks opisującej zadanie
wszystkie koszty
zredukowane są
to tablica ta opisuje wierzchołek
optymalny zadania zaś w prawym górnym rogu tablicy otrzymujemy
optymalną wartość funkcji celu.
Jeżeli w tablicy sympleks wszystkie koszty zredukowane są to funkcja celu
może być
zapisana tylko przy pomocy zmiennych niebazowych
gdyż dla zmiennych bazowych
. Funkcja celu
przyjmuje w wierzchołku opisanym tablicą
sympleks wartość
a dla pozostałych punktów wielościanu
.
Rozważamy zadanie typu ![]() |
0) Start: Dana tablica sympleks pierwotnie dopuszczalna. |
1) Test optymalności i wybór kolumny głównej. |
1a) Jeżeli wszystkie koszty zredukowane są nieujemne |
to STOP. Tablica opisuje wierzchołek optymalny. |
1b) Jeżeli nie to wybieramy kolumnę ![]() |
zredukowany jest ujemny. |
2) Test nieograniczoności i wybór elementu centralnego. |
2a) Jeżeli wszystkie elementy kolumny ![]() |
niedodatnie to STOP. Funkcja celu jest nieograniczona. |
2b) Jeżeli istnieją ![]() ![]() |
że ![]() |
3) Znajdujemy tablicę sympleks opisującą drugi koniec krawędzi |
metodą Gaussa - Jordana, GOTO 1). |
Rozwiązujemy zadanie:
Max , gdy:
,
,
Postacią kanoniczną jest:
Max , gdy:
,
,
Wierzchołkowi odpowiada TS
Idziemy krawędzią poprawiająca wyznaczoną przez
Liczymy
więc jako element centralny wybieramy
.
Po przekształceniach Gaussa - Jordana Otrzymujemy
Tablica ta opisuje wierzchołek
Idziemy krawędzią poprawiająca wyznaczoną przez
Liczymy więc jako
element centralny wybieramy
.
Po przekształceniach Gaussa - Jordana Otrzymujemy
Kolumna odpowiadająca zmiennej ma ujemny koszt zredukowany
więc na krawędzi przez nią wyznaczonej
funkcja celu
rośnie w nieskończoność.
Niech zadanie będzie opisane tablicą sympleks pierwotnie i dualnie dopuszczalną. Wówczas zbiór punktów dopuszczalnych zadania ma wymiar nie większy niż liczba zer niebazowych.
Przyjmijmy, że tablica sympleks ma wierszy i
kolumn. Zbiór punktów optymalnych
jest wielościanem w przestrzeni
opisanym równaniami z tablicy, nierównościami
i funkcją celu. Ale jeżeli punkt
jest optymalny to jego współrzędne odpowiadające kolumnom poprawiającym muszą być równe zero. Tak więc zbiór punktów optymalnych jest przecięciem stożka opisanego nierównościami
i podprzestrzeni
opisanej równaniami z tablicy i równaniami
dla
odpowiadających kolumnom poprawiającym. Równania te są liniowo niezależne więc
. Zatem
.
Z twierdzenia 5.4 otrzymujemy bezpośrednio:
Jeżeli w tablicy sympleks pierwotnie dopuszczalnej wszystkie koszty zredukowane odpowiadające zmiennym niebazowym są to tablica ta opisuje jedyny wierzchołek
optymalny zadania.
Jeżeli w tablicy sympleks pierwotnie i dualnie dopuszczalnej każda krawędź neutralna opisywana przez tą tablicę jest niezdegenerowana to wymiar zbioru punktów optymalnych jest równy liczbie tych krawędzi. ( Liczbie zer niebazowych w tablicy sympleks.)
Przyjmijmy, że tablica sympleks opisuje wierzchołek i wychodzące z niego krawędzie neutralne
. Wtedy wymiar zbioru punktów optymalnych
spełnia warunki:
, gdyż na mocy twierdzenia 5.2 wektory krawędzi są liniowo niezależne. Z drugiej strony
na mocy twierdzenia 5.4.
Jeżeli tablica sympleks pierwotnie i dualnie dopuszczalna o wierszach pod kreską ma nad kreską dokładnie
zer, to:
a) jeżeli krawędź neutralna jest niezdegenerowana to zbiorem punktów optymalnych zadania jest ta krawędź,
b) jeżeli krawędź neutralna jest zdegenerowana to tablica ta opisuje jedyny wierzchołek optymalny zadania.
Ad a) Zbiór punktów optymalnych jest ścianą wielościanu - obszaru dopuszczalnego, zawiera krawędź neutralną opisaną tablicą sympleks i na mocy twierdzenia 5.3 ma wymiar więc jest tą krawędzią.
Ad b) Przenumerujmy kolumny tak by tablica sympleks miała postać
,
gdzie pierwszych zmiennych jest bazowych zaś
dla
.
Niech będzie punktem optymalnym. Porównując wartości funkcji celu w punkcie
opisanym tablicą i w punkcie
otrzymujemy
. Więc
.
Krawędź opisana -szą kolumną jest zdegenerowana więc istnieje wiersz
taki, że
i
. Po wstawieniu do
-tego równania
otrzymujemy
i stąd
. W rezultacie punkt
spełnia ten sam układ równań co punkt
więc
.
Jeżeli w tablica sympleks pierwotnie i dualnie dopuszczalna o wierszach pod kreską ma nad kreską więcej niż
zer, to wymiar zbioru punktów optymalnych może być każdą liczbą między 0 a liczbą zer niebazowych. Zobaczmy to na przykładzie zadania opisanego tablicą:
Wierzchołek optymalny ma współrzędne . Mamy dodatkowo dwie kolumny opisujące zdegenerowane krawędzie neutralne 5-tą i 6-tą. Pokażemy, że zbiór punktów optymalnych jest trójkątem. Po eliminacji Gaussa -
Jordana otrzymujemy inną tablicę opisującą ten sam wierzchołek.
Teraz 6-ta kolumna opisuje krawędź niezdegenerowaną. Dochodzimy nią do wierzchołka opisanego tablicą:
Teraz 3-ta kolumna opisuje kolejną krawędź niezdegenerowaną. Dochodzimy nią do wierzchołka opisanego tablicą:
Z tej tablicy możemy dojść do tablicy opisującej wierzchołek wybierając element centralny w wyznaczonym miejscu.
Opisz prosty algorytm metody sympleks na przykładzie zadania:
Max , gdy:
,
,
Opisz wszystkie punkty optymalne zadania:
,
,
Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i
Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
Projekt współfinansowany przez Unię Europejską w ramach
Europejskiego Funduszu Społecznego.
Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.