Pachet de Programe pentru Algoritmul Simplex

Algoritmul simplex primal

Determinarea soluţiilor primal admisibile, de bază ale problemei de programare liniara (PPL)

Teoreme (criteriul de ieşire din bază, criteriul de optim, criteriul de intrare în bază, criteriul de optim infinit)

Fie problema PPL standard: Consideram sistemul compatibil AX=D, ,n>m ,rang A=m, A=(V1, V2 ,… Vn), ; 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 Rm ,notam:

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

XB – variabilele principale (bazice) care insotesc vectorii din baza B

XS - variabilele secundare ( nebazice)

Sistemul se poate scrie: BXB+SXS=D si inmultind la stanga cu B-1 se obtine solutia sistemului : XB= B-1 D-(B-1S)XS. Pentru XS=0 XB = B-1 D=DB ( coordonate vectorului D in baza B)

Solutia particulara obtinuta din DB 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 DB nenule si degenerata in caz contrar.

Deci fiecarei baze din A îi corespunde o solutie de baza . Reciproc nu este adevătat. 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 coloană ai matricei A in functie de vectorii bazei B, se obtine o noua matriceAB,numita matricea redusa a matricii Acorespunzatoare bazeiB. . Astfel , coloanele lui AB sunt coordonatele vectorilor in baza B, dati de relatia : B-1 =

Forma redusă conţine o matrice unitate Um formată din coloanele corespunzătoare vectorilor care formează baza B. Pentru determinarea formei reduse se foloseşte metoda eliminarii complete prim eliminarea succesivă a câte unui singur vector din bază.

Pentru calcule se aranjeaza totul intr-un singur tabel:

Apar astfel calculate coordonatele lui D în bazele succesive obţinute prin înlocuirea în bază a câte unui vector din A. În final se obţine soluţia de bază a sistemului restricţiilor PPL, X=B-1D=DB.

Dacă vectorul Vk intră în bază şi vectorul Eh iese, se obţine o nouă bază B1 şi, cu transformările de coordonate la schimbarea bazei datorate aplicării regulei pivotului ahk 0 se obţin relaţiile:

Se pune problema determinării pentru sistemul compatibil AX=D, ,n>m ,rang A=m, a acelor soluţii de bază pentru care .

Cum = atunci

Deci, se poate formula

Criteriul de ieşire din bază:

Dacă în bază intră vectorul Vk, atunci din bază se scoate vectorul care îndeplineşte condiţia:

Avem descompunerea: A=(B,S), unde , şi corespunzător descompunerea vectorului în variabile bazice şi nebazice, ;

Sistemul de restricţii devine: . Dacă notăm atunci soluţia sistemului de restricţii devine: sau, scrisă pe componente, . Înlocuind în funcţia obiectiv, se obţine: .

Notăm: valoarea funcţiei obiectiv corespunzătoare programului de bază şi avem: Se pot enunţa deci următoarele criterii folosite de algoritmul de optimizare