Jeżeli zadanie PL opisane jest macierzą, która nie ma postaci tablicy sympleks, to by móc stosować metodę sympleks stosujemy chwyt genialny w swej prostocie - dopisujemy macierz jednostkową. Dokładniej:
Dwufazowa metoda sympleks
Badamy zadanie:
macierzą układu jest
Mnożąc w razie potrzeby niektóre równania przez możemy
przyjąć, że
. Aby uzyskać
dopisujemy macierz
jednostkową i otrzymujemy tablicę sympleks
.
Odpowiada temu układ równań
gdzie
Pierwsza faza
Rozwiązujemy zadanie
zadanie jest ograniczone ponieważ
. Dodatkowo jeżeli
należy do
obszaru dopuszczalnego zadania pierwotnego, czyli
to
jest punktem optymalnym
gdyż
zaś
I Przypadek:
Jeżeli w rozwiązaniu optymalnym zadania
to wielościan
jest zbiorem pustym (zadanie pierwotnie sprzeczne).
II Przypadek:
Jeżeli to
opisująca wierzchołek optymalny
zadania
pozwala nam opisać wierzchołek
zadania pierwotnego.
a) Jeżeli wszystkie zmienne są niebazowe
to macierz powstała po wykreśleniu kolumn z nimi związanych jest
opisująca wierzchołek obszaru dopuszczalnego zadania
pierwotnego.
Rzeczywiście. Jeżeli jest
wierzchołkiem opisanym
to
,
( zawiera macierz jednostkową)
powstała z
przez operacje
elementarne na wierszach, więc opisuje ten sam wielościan.
b) Niech będzie zmienną bazowa. Przyjmijmy, że kolumna
odpowiadająca
ma jedynkę w j-tym wierszu i pozostałe
współrzędne
.
jeżeli wiersz j-ty ma tylko jeden element niezerowy
(
- ty wiersz
jest zerowy ) to znaczy, że
i
były układem zależnym. Taki wiersz i kolumny można wykreślić (
w praktyce zostaje).
Jeżeli oprócz jedynki odpowiadającej
istnieje
w j-tym wierszu
macierzy
to wybieramy go jako element centralny i
po przekształceniach elementarnych otrzymujemy
, w której
jest niebazowe, zaś
jest dołączone do bazy.
Po wykonaniu I fazy otrzymujemy opisującą wierzchołek obszaru
dopuszczalnego
lub informację, że zadanie było sprzeczne.
Druga faza:
Najpierw budujemy wiersz kosztów zredukowanych
Koszty zredukowane to gdzie
to
gdy
- bazowa. Wektor
wyliczamy
wstawiając do równania
równania pochodzące z
=
Dalej zadanie rozwiązujemy prosta metodą sympleks.
Badamy zadanie:
I faza:
Wprowadzamy sztuczne zmienne i
i funkcje celu i otrzymujemy:
Zamieniamy teraz funkcję celu podstawiając: i
.
Otrzymujemy:
Zadanie opisujemy tablicą:
Opuściliśmy tu kolumnę odpowiadającą zmiennej bo, jak wcześniej zauważyliśmy, kolumna ta nie ulega zmianie podczas rozwiązywania.
Wybieramy kolumnę poprawiającą .
i element
centralny zaznaczamy nawiasem
Zmienne sztuczne wypadły z bazy więc możemy je wykreślić.
Pozostała tablica opisuje wierzchołek startowy .
Wracamy do pierwotnej funkcji celu i liczymy koszty zredukowane:
i otrzymujemy tablicę sympleks:
Pierwsza kolumna wyznacza krawędź poprawiającą. Idąc nią otrzymujemy.
Ta tablica opisuje jedyny wierzchołek optymalny ,
w
którym
Rozwiążmy zadanie:
I faza:
Wprowadzamy sztuczne zmienne i
i funkcje celu
co daje tablicę sympleks
stosując prosty algorytm metody sympleks otrzymujemy kolejno:
Nad kreską są same liczby nieujemne a funkcja celu jest równa -2 zatem zadanie jest sprzeczne (obszar dopuszczalny jest zbiorem pustym).
1. Metoda częściowej bazy sztucznej
W metodzie dwufazowej wystarczy dodać tylko tyle zmiennych sztucznych, by otrzymać macierz jednostkową.
np.
W tym przypadku mamy zmiennych bazowych i gdy
dodajemy tylko
zmiennych sztucznych.
W przypadku rzeczywistych obliczeń ( na maszynach) zwykle nie
stosuje się częściowej bazy sztucznej. Nie trzeba wówczas
wyszukiwać w macierzy kolumn zero - jedynkowych.
2. Można obie fazy rozwiązać na jednej . W zadaniu:
Rozważamy obie funkcje celu jednocześnie.
Budujemy tablicę sympleks mającą dwa wiersze nad kreską.
,
gdzie
W fazie 1 maksymalizujemy i w rezultacie otrzymujemy,
że zadanie jest sprzeczne lub
opisująca
wierzchołek startowy (łącznie z kosztami zredukowanymi funkcji
).
Ta metoda nigdy nie prowadzi do zmniejszenia liczby operacji (np. wyszło, że zadanie jest sprzeczne, więc naliczyliśmy się zupełnie niepotrzebnie).
Badamy zadanie:
I faza:
Wprowadzamy sztuczne zmienne i
i funkcje celu
Wybieramy kolumnę poprawiającą
.
i element centralny
zaznaczamy nawiasem
Koniec fazy pierwszej. Wszystkie sztuczne zmienne są niebazowe wykreślamy wiersze i kolumny związane ze sztucznymi zmiennymi.
Kolumna wyznacza krawędź poprawiającą. Idąc nią otrzymujemy.
Ta tablica opisuje jedyny wierzchołek optymalny ,
w którym
3 Metoda dużego .
Czasami potrafimy oszacować wartość i
.
Szczególnie w zagadnieniach całkowitoliczbowych np. transport
ciężarówkami i gdy wśród warunków są
.
Aby rozwiązać zadanie:
wybieramy liczbę M dostatecznie dużą i rozpatrujemy zadanie
.
Teraz poprawione zadanie opisane jest tablicą sympleks:
,
gdzie wektor jest sumą wierszy macierzy
.
Rozwiązanie zawsze istnieje, ale czasami w opisie kosztów
zredukowanych wierzchołka optymalnego występuje - oznacza to,
że zadanie wyjściowe jest sprzeczne. W stosunku do poprzednich
metod zyskujemy to, że mamy jedną fazę i jedną funkcję celu.
Sprowadzamy do zadania:
,
Otrzymujemy następujące tablice sympleks:
Rozwiązaniem jest wierzchołek , w którym funkcja celu
osiąga wartość 3.
Opisz dwufazowy algorytm metody sympleks na przykładzie zadania:
Min , gdy:
,
,
,
Opisz dwufazowy algorytm metody sympleks na przykładzie zadania:
Min , gdy:
,
,
,
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.