|
|
|
ALGORITMUL SIMPLEX DUAL
Prin aplicarea algoritmului simplex problemei duale se obtine un nou algoritm pentru problema initiala, numit algoritmul simplex-dual, care este tot un algoritm pentru problema initiala, ca si simplexul, si intr-un anumit sens dual acestuia.
Algoritmul simplex exploreaza bazele admisibile, pana cand acestea devin si dual-admisibile, deci optime, in timp ce algoritmul simplex-dual exploreaza bazele dual-admisibile pana cand acestea devin si admisibile, deci optime.
Consideram problema de minimizat (26) ca problema initiala.
Pasul 1. Se determina o baza initiala B
a matricei A, se calculeaza elementele 
si se intocmeste tabelul simplex
corespunzator.
Pasul 2. Daca baza B nu este dual-admsibila atunci executa:
Se adauga restrictia suplimentara
, M - suficient de
mare;
Se aduce restrictia la forma standard:
;
Se
face schimbarea de baza 
, unde k se
determina din relatia: 
.
Pasul 3. Daca 
atunci scrie ' Programul gasit este optim'; Stop.
altfel se determina indicele l din relatia:
.
Pasul 4. Daca
atunci scrie
'Problema nu are programe'; Stop.
altfel se determina indicele k din relatia:
.
Pasul 5. Se
face schimbarea de baza 
, se transforma tabelul simplex conform formulelor de
transformare cu pivotul 
si se reia
algoritmul de la pasul 3.
