Zagadnienia

7. Własności metody sympleks

7.1. Zrewidowana metoda sympleks.

Kolejne kroki otrzymywania TS 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 TS 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ą TS,

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

B¯=1-cB0B  B-1¯=1cBB-10B-1

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

Kolejna TS 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γ,r0-αtraγ,r1=I-1αγr0α0,r0α1,r0αt,r0+j001αγ,r00

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=α0r-α0rαj,rαj,rαtr-αtrαj,rαj,r=01j

Macierze Bt-1=EtEt-1E1. Ponieważ macierze typu E są podobne do macierzy elementarnych I+αeij 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 TS (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.

x01cB-1xi1xi2xit00B-1

1) wyliczamy wyrazy wolne b0b1bt=B¯-1b0b1bt

2) wyliczamy koszty zredukowane

zi=-ci+cB-1ki

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

3) test optymalności

Jeżeli i zi0 to stop:

wierzchołkiem optymalnym jest xj=0,ji1,i2,,itbi,wpp

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

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

5) test skończoności

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

6) wyznaczamy element centralny Minxji>0bjαj

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

-cN0b0=0ANIb

następna

TS=-cN+cNB-1ANcB-1b0=cB-1ANB-1nie interesująca - nie wyliczamyB-1B-1b

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

Przekształcenia
Metoda Gausa Koszty Razem
Jordana zredukowane
Sympleks  i /+i- t+1n-t+1tn-t+1 tn-t+n+1tn-t+1
Zrewidowana  i /+i- t+12tt+1 tn-ttn-t tn-t+t+12tn+1

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

Przykład 7.1

Maxx0=34x4-20x5+12x6-6x7, gdzie

x1+14x4-8x5-x6+9x7=0x2+12x4-12x5-12x6+3x7=0x3+x6=1

x10,x20,x30,x40,x50,x60,x70

Ten układ równań daje następującą TS

1000-3420-1260010014-8-190001012-12-1230000100101

Otrzymujemy następujące TS:

13000-4-7233004001-32-43600-2100432-150000100101

111000-21800-1280108-8400-121400138-1540000100101

1-2301400-300-32101801-21200116-180-364103160032-11-18002121

1-110-121600002-60-5256100013-230-141630100-26152-56001

10-20-7444120001-30-542812000013016-4-1610000100101

1000-3420-1260010014-8-190001012-12-1230000100101

I tak ostatnia siódma TS jest identyczna z pierwszą.

Wszystkie tablice opisują wierzchołek nieoptymalny p=0,0,1,0,0,0,0

Idąc inną drogą otrzymujemy:

1000-3420-1260010014-8-190001012-12-1230000100101

1032002-54212001-1200-2-34152000201-24-160000100101

1032540202125401-12340-201523400211-24061000100101

Ostatnia tablica opisuje wierzchołek optymalny q=34,0,0,1,0,1,0.

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.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

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.