ALGORITMUL SIMPLEX PRIMAL

Algoritmul Simplex primal

Determinarea solutiilor primal admisibile, de baza ale PPL

Teoreme (criteriul deiesire din baza, criteriul de optim, criteriul de intrare in baza, criteriul de optim infinit)

Fie problema PPL standard: Consideram sistemul compatibil AX=D, ,n>m ,rang A=m, A=(V₁, V₂ ,. V_n), este solutia sistemului ,daca:

Definitie: Vectorul este o solutie de baza a sistemului ,daca vectorii corespunzatori coordonatelor nenule ale sale sunt liniari independenti.

Solutia de baza se numeste nedegenerata daca are chiar m coordonate nenule ,in caz contrar solutia se numeste degenerata.

Daca B baza a matrici A ,deci a spatiului R^m ,notam:

S- matricea formata din vectorii coloana ale lui A care nu fac parte din baza.

X^B - variabilele principale (bazice) care insotesc vectorii din baza B

X^S - variabilele secundare ( nebazice)

Sistemul se poate scrie: BX^B+SX^S=D si inmultind la stanga cu B^-1 se obtine solutia sistemului :

X^B= B^-1 D-(B^-1S)X^S. Pentru X^S=0 X^B = B^-1 D=D^B ( coordonate vectorului D in baza B)

Solutia particulara obtinuta din D^B completata cu 0 pentru variabilele secundare este o solutie de baza a sistemului si se numeste solutie de baza corespunzatoare bazei B.

Aceasta este nedegenerata pentru componentele D^B nenule si degenerata in caz contrar.

Deci fiecarei baze din A ii corespunde o solutie de baza . Reciproc nu este adevatat. O solutie de baza poate corespunde mai multor baze. Numarul maxim de solutii de baza ale unui sistem este combinari de n luate cate

Exprimand vectorii coloana ai matricei A in functie de vectorii bazei B, se obtine o noua matrice A^B, numita matricea redusa a matricii A corespunzatoare bazei B. .

Astfel , coloanele lui A^B sunt coordonatele vectorilor in baza B, dati de relatia :

B^-1=

Forma redusa contine o matrice unitate U_m formata din coloabele corespunzatoare vectorilor care formeaza baza B. Pentru determinarea formei reduse se foloseste metoda eliminarii complete prim eliminarea succesiva a cate unui singur vector din baza. Pentru calcule se aranjeaza totul intr-un singur tabel: