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:

Apar astfel calculate coordonatele lui D in bazele succesive obtinute prin inlocuirea in baza a cate unui vector din A. In final se obtine solutia de baza a sistemului restrictiilor PPL,

X=B^-1D=D^B.

Daca vectorul V_k intra in baza si vectorul E_h iese, se obtine o noua baza B₁ si, cu transformarile de coordonate la schimbarea bazei datorate aplicarii regulei pivotului a_hk 0 se obtin relatiile:

Se pune problema determinarii pentru sistemul compatibil AX=D, ,n>m ,rang A=m,

a acelor solutii de baza pentru care . Cum atunci

Deci, se poate formula

Criteriul de iesire din baza:

Daca in baza intra vectorul V_k, atunci din baza se scoate vectorul care indeplineste conditia:

Avem descompunerea: A=(B,S), unde , si corespunzator descompunerea vectorului in variabile bazice si nebazice , ;

Sistemul de restrictii devine: . Daca notam atunci solutia sistemului de restrictii devine: sau, scrisa pe componente, . Inlocuind in functia obiectiv, se obtine:

.

Notam: valoarea functiei obiectiv corespunzatoare programului de baza

si avem: Se pot enunta deci urmatoarele criterii folosite de algoritmul de optimizare

Criteriul de optim pentru PPL

Programul de baza este optim pentru problema de minim daca

Observatiie: pentru o problema de maxim, inegalitatea se schimba.

Criteriul de intrare in baza

Daca

atunci programul nu este optim si programul se imbunatateste daca vectorul V_k intra in baza.

Observatii:

1)     Daca indicele k pentru care se verifica relatia a criteriului de intrare in baza, nu este unic determinat, atunci pentru o valoare a functiei obiectiv cat mai apropiata de valoarea minima, se adopta regula:

Daca intra in baza vectorul V_k pentru care

2)     La o problema de maxim, avem:

Daca intra in baza vectorul V_k pentru care

Criteriul de optim infinit

Daca si , , atunci spunem ca PPL admite un optim infinit si algoritmul de optimizare se opreste.

Enuntarea algoritmului SIMPLEX

Algoritmul SIMPLEX oferera solutia optima a PPL. Il enuntam pentru problema de minim.

a)     Se determina o baza admisibila B si se calculeaza :

- programul de baza corespunzator

- valoarea functiei obiectiv

- diferentele =;

Datele se introduc intr-un tabel SIMPLEX:

b)     (testul de optim) Daca , atunci programul este optim si STOP.

Daca nu, adica atunci programul nu este optim si se aplica criteriul de intrare in baza: intra in baza vectorul V_k pentru care

c)     (testul de optim infinit) Daca atunci problema admite un optim infinit si STOP.

d)     Daca atunci se aplica criteriul de iesire din baza, adica iese din baza vectorul V_h pentru care

Se obtine o noua baza B₁ si se reia algoritmul de la punctul b), iar iesirea din el are loc fie la punctul b) (testul de optimalitate), fie la punctul c) (testul de optim infinit).

Deci: algoritmul SIMPLEX va testa conditia de optim pentru programul de baza gasit si, in caz ca aceasta nu este satisfacuta, va determina un alt program de baza care va apropia functia obiectiv da valoarea optima, iar in final va determina valoarea optima a sa.

Observatie:

a)Pentru o problema de maxim se schimba semnul inegalitatii in criteriul de optim si inf devine sup la criteriul de intrare in baza.

b)Daca criteriile decid ca este pivot, atunci tabelul SIMPLEX se transforma dupa regulile:

i) linia pivotului se imparte cu pivotul.

ii) coloana pivotului se completeaza cu 0 pana se obtine vectorul unitar al bazei canonice.

iii) orice alt element din tabel se transforma dupa regula dreptunghiului (pivotului) introdusa la metoda eliminarii complete.

Metoda bazei artificiale ( a celor doua faze si a penalizarii)

Fie forma standard a unei P.P.L.

Daca matricea sistemului de restrictii nu contine vectorii unitari care alcatuiesc baza canonica necesara determinarii unei solutii initiale de baza , recurgem la metoda bazei artificiale prin introducerea variabilelor artificiale si se rezolva problema de programare liniara:

Avem urmatorul rezultat teoretic :

Orice solutie posibila a problemei initiale este o solutie posibila a programului extins pentru care valorile tuturor variabilelor artificiale sunt nule si reciproc orice solutie a programului extins in care toate variabilele artificiale sunt nule, este o solutie a programului initial dupa inlaturarea acestora.

Deci problema initiala are solutii daca si numai daca sistemul extins al restrictiilor are solutii de forma

O astfel de problema se rezolva prin metoda celor doua faze:

Faza I . In aceasta faza se rezolva problema:

La sfarsit putem avea urmatoarele situatii :

1) deci toate variabilele artificiale sunt nule si nici o variabila artificiala nu este bazica fata de solutia optima. In acest caz dispunem de o solutie de baza a programului extins din care prin inlaturarea variabilelor artificiale se obtine o solutie de baza a programului initial si se trece la faza a II-a

2) si cel putin o variabila artificiala este bazica, ea trebuind eliminata astfel:

- daca pe linia variabilei artificiale exista elemente nenule (rang A=m) alegem unul dintre acestea drept pivot si facem inca o iteratie pentru a o elimina din baza .

daca pe linia variabilei artificiale nu avem

elemente nenule (rang A<m), o vom neglija suprimand-o din tabel . Se trece la faza a II-a.

3) problema initiala nu are solutie de baza (vezi exemplul de mai jos)

Faza a II-a . In aceasta faza se elimina din ultimul tabel simplex coloanele variabilelor artificiale si se continua algoritmul introducand coeficientii functiei obiectiv z=C^TX . Daca in baza au mai ramas variabile artificiale nenule, aceasta este dovada ca problema initiala nu admite solutii (exemplul de mai jos).

Constructia unei baze initiale unitare pentru pornirea algoritmului simplex, in situatia ca nu exista in matricea sistemului, sau nu este completa, revine deci la a construi o baza artificiala.

In varianta metodei penalizarilor, problema initiala se inlocuieste cu o problema modificata, pe care o putem numi problema extinsa:

cu , suficient de mare, numit coeficient de penalizare (pentru max z se scade ).

Deci, varianta penalizarii modifica functia obiectiv, introducand vectorii artificiali cu acesti coeficienti. Cum pentru acestia nu exista corespondent in interpretarea economica a rezultatelor, rezulta evident ca, ei vor fi folositi doar in scopul constructiei bazei artificiale necesare unei baze unitare, primal admisibile , algoritmul trebuind in final sa-i excluda din programul optim de baza. Asa se explica de ce coeficientii de penalizare au valori pozitive foarte mari, cu semnul plus la problemele de minim, respectiv minus la cele de maxim.

In iteratiile succesive, algoritmul simplex inlatura bazele pentru care functia obiectiv nu e optima, deci, va excludere din baza vectorii artificiali. Daca nu, atunci spunem ca P.P.L. initiala nu are solutie posibila de baza si deci nu are solutie optima.

Observatie :

Daca un vector artificial a fost inlaturat din baza, putem sa nu mai calculam in iteratiile urmatoare coordonatele lui din matricea redusa a noii baze. Daca insa ne intereseaza inversa bazei optime, pentru verificarea solutiei optime sau alte calcule care o implica, completam in tabloul simplex si coloanele vectorilor artificiali iesiti din baza.

Avem urmatorul rezultat teoretic :

Daca problema initiala are program optim de baza, acesta este si pentru problema extinsa program optim de baza si reciproc.

De aceea este suficient sa rezolvam problema extinsa, plecand de la o solutie primal admisibila de baza

.

Exemplu :

Sa se rezolve urmatoarea P.P.L.

a) prin metoda penalizarii.

b) prin metoda celor doua faze.

Solutie:

a) Aducem P.P.L la forma standard. Introducand y₁, y₂ variabile de compensare se observa ca matricea sistemului de restrictii contine doar un vector unitar, y₁.

In completarea bazei unitare, se aduna vectorul unitar care lipseste la ecuatia a doua a sistemului, adica variabila artificiala a. . Fie M>0 coeficientul de penalizare cu care intra variabila artificiala in functia obiectiv. Obtinem problema extinsa:

pentru care aplicam algoritmul simplex:

Intrucat toate diferentele , conditia de optim este indeplinita, algoritmul se opreste, dar, se observa ca in baza optima a ramas variabila artificiala (de penalizare) a, cu a>0, deci P.P.L nu are solutie.

b) Metoda celor 2 faze

Faza I. Rezolvam P.P.L.:

Intrucat toate diferentele:

,

P.P.L nu are solutie.

Exemplu:

Se aduce modelul la forma standard, aici introducand doua variabile de compensare u,v:

Acest model nu are o baza formata din vectori unitate, deci se introduc si doua variabile artificiale p,q in completarea bazei canonice,variabile care modifica functia obiectiv, intrand cu coeficienti nenuli, de regula foarte mari si pozitivi pentru ca in final algoritmul de optimizare sa-i excluda din solutia de baza:

Pentru acest model, iteratiile simplex sunt prezentate in continuare:

Solutia problemei este deci:

(min)z=4; =0 =4/3;u=0;v=4/3.