Kolejne kroki otrzymywania T⁢S 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 T⁢S startową jest

-cN0...0b0ANIb

i w m-tym kroku uzyskaliśmy tablicę zawiązana z wyborem zmiennych bazowych xi1,xi2,…,xit. Oznacza to, że macierz B=ki1,ki2,…,kit gdzie kij jest ij-tą kolumną macierzy A=[An|I], spełnia warunek

B-1¯⋅1-cN0...0b00ANIb

jest m-tą T⁢S,

to znaczy jej kolumny kij,…,kit tworzą macierz jednostkową

B¯=1-cB0B  B-1¯=1cB⁢B-10B-1

Co pewien czas (np. co 100 kroków) zamiast wyliczać T⁢S metodą eliminacji G⁢J, wyliczamy ją bezpośrednio ze startowej T⁢S mnożąc ją z lewej strony przez odpowiednią podmacierz B-1¯ wyznaczoną przez wybór bazy.

Kolejna T⁢S powstaje z poprzedniej przez mnożenie z lewej strony przez macierz różniącą się od jednostkowej tylko jedną kolumna a więc postaci

E=1⋯-α0,ra⁢γ⁢r00…-α1,raγ⁢r0⋮⋮…⋮-1aγ,r⋮⋮…⋮0⋮-αt⁢raγ,r1=I-1αγ⁢r⁢0α0,r0⋮α1,r⋮⋮⋮⋮0αt,r0+j⁢0…0⋮1αγ,r⋮0…0

gdzie kolumna główna macierzy poprzedniej ma postać α0,rα1,r…αj,r…αt,ri elementem centralnym jest αγ,r.

E⋅α0,rα1,r⋮αt,r=α0⁢r-α0⁢rαj,r⋅αj,r⋮αt⁢r-α⁢t⁢rαj,r⋅αj,r=0⋮1⋮←j

Macierze Bt-1=Et⋅Et-1⁢…⁢E1. Ponieważ macierze typu E są podobne do macierzy elementarnych I+α⋅ei⁢j można tak modyfikować uzyskiwanie macierzy B (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 ≠0, by macierz wynikowa była też rozrzedzona.

Algorytm zrewidowanej metody sympleks:

Dana jest początkowa T⁢S (lub macierz opisująca wielościan i koszty).

W kolejnym kroku mamy dodatkowo macierz B-1¯ powstałą przez odwrócenie podmacierzy wyznaczonej przez zmienne bazowe i listę zmiennych bazowych.

x01c⁢B-1xi1xi2⋮xit00⋮B-1

1) wyliczamy wyrazy wolne b0′b1′…bt′=B¯-1⁢b0b1…bt

2) wyliczamy koszty zredukowane

zi=-ci+c⁢B-1⁢ki

gdzie ki jest i-ta kolumną macierzy A (początkowej)

3) test optymalności

Jeżeli ∀i zi≥0 to stop:

wierzchołkiem optymalnym jest xj=⁡0,⁢j∉i1,i2,…,itbi′,⁢w⁢p⁢p⁢

Jeżeli nie, to wybieramy kolumnę główną taką, że ci<0

4) obliczamy kolumnę główną ki′=B-1⋅ki

5) test skończoności

Jeżeli ki≤0 to stop: otrzymujemy nieskończoną krawędź poprawiajacą

6) wyznaczamy element centralny M⁢i⁢nxj⁢i′>0⁢⁢bj′αj′

7) wyliczamy nową B¯′A-1 stosując do B-1¯ przekształcenia G⁢J i ustalamy nową listę zmiennych bazowych.

-cN0b0=0ANIb

następna

T⁢S⁢=⁢-cN+cN⁢B-1⁢ANc⁢B-1b0′=c⁢B-1AN⁢B-1nie interesująca - nie wyliczamyB-1B-1⁢b

Policzmy ile działań wykonujemy w przypadku tablicy o n kolumnach i t wierszach.

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].

Rada praktyczna:

Krawędzie zdegenerowane pochodzą od tych zmiennych, które na przecięciu swojej kolumny i równania (wiersza) o wyrazie wolnym 0 mają liczbę >0.

Badamy wiersze o zerowym wyrazie wolnym i szukamy krawędzi poprawiających, które mają w tym wierszu liczbę ≤0.