Kolejne kroki otrzymywania prowadzą do narastania błędów - duża liczba mnożeń i dzieleń powoduje, że wyniki
są coraz mniej dokładne (algorytm metody sympleks nie jest stabilny).
Przypuśćmy, że startową jest
i w m-tym kroku uzyskaliśmy tablicę zawiązana z wyborem zmiennych bazowych .
Oznacza to, że macierz
gdzie
jest
-tą kolumną macierzy
, spełnia warunek
jest m-tą ,
to znaczy jej kolumny tworzą macierz jednostkową
Co pewien czas (np. co 100 kroków) zamiast wyliczać metodą eliminacji
, wyliczamy ją bezpośrednio ze
startowej
mnożąc ją z lewej strony przez odpowiednią podmacierz
wyznaczoną przez wybór
bazy.
Kolejna powstaje z poprzedniej przez mnożenie z lewej strony przez macierz różniącą się od jednostkowej tylko jedną kolumna a więc postaci
gdzie kolumna główna macierzy poprzedniej ma postać i elementem centralnym jest
.
Macierze . Ponieważ macierze typu
są podobne do macierzy elementarnych
można tak modyfikować uzyskiwanie macierzy
(dobierając kolejność mnożenia przez
macierze elementarne by zminimalizować błędy) i dodatkowo jeśli macierz początkowa był a rozrzedzona, tzn. miała
mało współczynników
, by macierz wynikowa była też rozrzedzona.
Algorytm zrewidowanej metody sympleks:
Dana jest początkowa (lub macierz opisująca wielościan i koszty).
W kolejnym kroku mamy dodatkowo macierz powstałą przez odwrócenie podmacierzy wyznaczonej
przez zmienne bazowe i listę zmiennych bazowych.
1) wyliczamy wyrazy wolne
2) wyliczamy koszty zredukowane
gdzie jest i-ta kolumną macierzy
(początkowej)
3) test optymalności
Jeżeli
to stop:
wierzchołkiem optymalnym jest
Jeżeli nie, to wybieramy kolumnę główną taką, że
4) obliczamy kolumnę główną
5) test skończoności
Jeżeli to stop: otrzymujemy nieskończoną krawędź poprawiajacą
6) wyznaczamy element centralny
7) wyliczamy nową stosując do
przekształcenia
i ustalamy nową
listę zmiennych bazowych.
następna
Policzmy ile działań wykonujemy w przypadku tablicy o kolumnach i
wierszach.
Przekształcenia | |||
Metoda | Gausa | Koszty | Razem |
Jordana | zredukowane | ||
Sympleks
![]() |
![]() |
![]() |
|
Zrewidowana
![]() |
![]() |
![]() |
![]() |
Wniosek:
Zazwyczaj metoda zrewidowana jest droższa, ale zyskujemy dokładność.
Niestety macierzowy algorytm metody sympleks, w przeciwieństwie do geometrycznego, może się zapętlić. Sytuacja zachodzi wtedy gdy jeden wierzchołek może być przedstawiony za pomocą wielu tablic sympleks. Możemy w nieskończoność wędrować krawędziami zdegenerowanymi po jednym i tym samym wierzchołku. Aby uniknąć tej sytuacji niektóre algorytmy wykorzystują numerowanie leksykograficzne wierzchołków. Patrz [4]
Aby wierzchołek mógł być przedstawiony wieloma tablicami sympleks z prawej strony kreski muszą znajdować się zera. Algorytmy wykonujące przekształcenia Gaussa - Jordana nie są stabilne co w konsekwencji daje błąd ale i przerwanie pętli - co wykorzystują inne algorytmy.
Podamy teraz przykład zapętlenia się algorytmu sympleks pochodzący z [3].
, gdzie
Ten układ równań daje następującą TS
Otrzymujemy następujące TS:
I tak ostatnia siódma TS jest identyczna z pierwszą.
Wszystkie tablice opisują wierzchołek nieoptymalny
Idąc inną drogą otrzymujemy:
Ostatnia tablica opisuje wierzchołek optymalny .
Rada praktyczna:
Krawędzie zdegenerowane pochodzą od tych zmiennych, które na
przecięciu swojej kolumny i równania (wiersza) o wyrazie wolnym
mają liczbę
.
Badamy wiersze o zerowym wyrazie wolnym i szukamy krawędzi
poprawiających, które mają w tym wierszu liczbę .
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.