Algoritmul simplex
Algoritmul Simplex (primal) a fost elaborat i aplicat de G.B. Dantzig n 1947 ca metod
de rezolvare a unor probleme de optimizare.
Metoda simplex cerceteaz valorile funciei obiectiv n mulimea SAB (solu ie admisibil
de baz) i permite trecerea de la o soluie la o alta mai bun fr a fi necesar cercetarea
tuturor SAB i este un proces iterativ.
Etapele algoritmului simplex se pot stabili att pentru probleme de maxim ct i pentru
probleme de mnim, dei se poate nlocui aflarea lui max f cu aflarea lui min(-f) deoarece:
max f =min(f )
i
min f =max(f )
La probleme de maxim, dac x0 i x sunt dou SAB, soluia x este mai bun dect x0
'
dac f (x ) f ( x 0) adic valoarea funciei obiectiv crete.
Pe lng faptul c prin algoritmul simplex se determin att solu ia optim ct i valoarea
optim a funciei obiectiv, rezult i cazurile n care nu exist solu ie optim sau valoarea optim
a funciei obiectiv nu este finit.
Etapele algoritmului Simplex pentru probleme de maxim
Dup aducerea la forma standard a problemei de programare liniar, se aplic algoritmul
simplex cu urmtoarele etape:
Etapa I. Se determin o SAB de pornire. Apar dou situaii:
Matricea A a ceficienilor variabilelor din restricii conine toate coloanele matricei
unitate de ordinul m,
Im
. n acest caz, SAB se afl din restricii prin anularea
variabilelor nebazice (secundare)
Matricea A nu conine toate coloanele matricei
bazei artificiale.
Im
. n acest caz se folosete metoda
Etapa II. Se alctuiete primul tabel simplex. Capul de tabel este:
Baza
CB
P0
c1
P1
c2
P2
.
.
.
.
.
.
cn
Pn
z k c k
Pe coloana 1 (baza) se scriu vectorii bazei canonice, n ordinea apariiei lor n baz,
(1 0 0 ... 0) T, al doilea
deci: primul este vectorul care are componentele
este cel de componente (0 1 0 ... 0)T, ... iar ultimul de pe colona 1 are componentele (0
... 0 0 1)T
Pe coloana a doua, CB , se scriu coeficienii din funcia obiectiv, c i, care corespund
variabilelor bazice xi de pe prima coloan.
Pe coloana a treia, P0 , se scriu componentele soluiei de pornire X0
Pe prima linie din tabel se scriu coeficienii c1 , c2 , ... , cn din funcia obiectiv a
tuturor variabilelor.
Pe coloanele P1, P2 , ..., Pn se scriu respectiv coloanele matricei A a coeficienilor
variabilelor din restricii.
Pe ultima linie din primul tabel simplex se calculeaz diferenele z k-ck din relaia:
z k c k =CB Pk c k
Practic se procedeaz astfel: se nmulesc elementele coloanei CB, pe
rnd cu elementele coloanelor P1, P2 , ..., Pn nsumnd rezultatele i apoi se scade coeficientul ck
din FO ce se afl deasupra coloanei Pk , k =1,n .
De exemplu
z 1c 1=C B P1c 1
Etapa III. Se aplic criteriul de optimalitate:
z 2c 2=C B P2 c 2
, etc.
Toate diferenele
Exist i diferene
z k c k 0
z k c k <0
, soluia este optim i stop
, soluia de pe coloana P0 nu este optim i trecem la
Etapa IV. Se va efectua o schimbare de baz. Criteriul de intrare n baz pentru probleme de
maxim este
min z k c k =z h c h ( z k c k <0)
k
adic intr n baz vectorul Ph cruia i corespunde cea mai mic valoare negativ pentru
z k c k
Acest vector Ph intr n baz n locul unuia dintre vectorii Pi aflai pe coloana 1 (baza),
deci unul dintre aceti vectori va iei din baz i trecem la etapa urmtoare:
Etapa V. Aplicarea criteriului de ieire din baz
Apar dou situaii:
a) Vectorul Ph, care a intrat n baz are toate componentele (de pe coloana sa) nepozitive, adic
aih 0. n acest caz problema de PL nu are soluie STOP.
b) Vectorul Ph care a intrat n baz are i componente strict pozitive. n acest caz, aplicm
criteriul de ieire din baz:
Iese din baz vectorul Pj pentru care avem:
b
b
min i = j (a ij >0)
a jh
i aih
adic se alege valoarea minima a raportului dintre componentele soluiei (aflate pe coloana P0) i
componentele strict pozitive ale vectorului Ph care a intrat n baz.
Elementul aflat la intersecia coloanei Ph cu linia vectorului Pj care a ieit din baz, se
numete pivot.
Etapa VI. Dup aplicarea etapelor 4 i 5 se va obine un nou tabel simplex.
Dup introducerea pe coloana baza a vectorului Ph n locul lui Pj , ceea ce nseamn c
vectorul Ph va deveni un vector din baza canonic , se nlocuiete pe coloana CB coeficientul Ch
din funcia obiectiv.
Apoi se procedeaz astfel:
Regula 1
Se obine mai nti linia vectorului Ph, care a intrat n baz, prin mprirea la pivot a
liniei care a corespuns lui Pj. Astfel n noul tabel simplex va apare cifra 1 n locul pivotului.
Celelalte componente ale vectorului Ph trebuie s fie zero, deoarece acesta are drept
componente una din coloanele matricei unitate. Pentru a obine celelalte linii din al doilea tabel,
se aplic regula 2:
Regula 2
Linia obinut prin regula 1 se nmulete convenabil iar rezultatul se adun pe rnd, la
toate liniile din tabelul precedend astfel c pe toat coloana pivotului se obine cifra zero. Pe
coloana lui P0 se va obine, n al doilea tabel, o nou soluie admisibil de baz , avnd
componentele nenegative.
Dup calcularea liniei
z k c k
n al doilea tabel se repet etapele, ncepnd cu etapa 3.
Dup un numr finit de iteraii se va determina soluia optim, dac exist; se specific i
faptul c nu exist soluie optima ori pot exista mai multe soluii optime.
Valoarea functiei obiectiv se calculeaza din
C B P0
si odata cu fiecare noua solutie
gasita ea creste.
Etapele algoritmului Simplex pentru probleme de minim
Dei avem min f = - max (-f) este mai comod s se specifice etapele algoritmului pentru
probleme de minim.
Aceastea sunt identice cu etapele pentru probleme de maxim cu urmtoarele dou
excepii:
Etapa III. Criteriul de optimalitate este:
Toate diferenele
Exist i diferene
z k c k 0
z k c k >0
, soluia este optim i stop
, soluia de pe coloana P0 nu este optim i trecem la:
Etapa IV. Se va efectua o schimbare de baz. Criteriul de intrare n baz pentru probleme de
minim este
z k c k
k =z h c h ( z k c k >0)
max