Metoda simplex de rezolvare a unui program liniar standard

Metoda simplex de rezolvare a unui program liniar standard

Fie programul standard

cu notatiile din paragraful 1. Daca vectorii coloana ai matricei formeaza o baza in , atunci se numesc coordonate bazice (variabile de baza). Matricea poate fi descompusa in doua submatrice formata din vectorii si formata cu celelalte coloane, deci:

si analog

iar forma standard se scrie

Facand calculele, rezulta

O solutie a sistemului (4.9) este

Luand aici obtinem o solutie de baza pentru (4.9.) si anume

Daca spunem ca baza este primal admisibila. Daca vectorul () are aceste componente in raport cu baza B iar ,

cu .

Dispunand de o baza primal admisibila se intocmeste tabelul simplex in care trecem:

a)      solutia

b)     

c)      valoarea functiei obiectiv corespunzatoare solutiei de baza.

d)      care reprezinta coordonatele vectorilor , in baza . daca este baza canonica sunt coeficientii din sistemul de restrictii dat.

e)      se calculeaza

f)        se calculeaza diferentele

Un astfel de tabel simplex, considerand ca , arata deci sub forma:

In continuare se aplica testul de optimalitate al solutiei si bazat pe urmatoarele teoreme pe care le dam fara demonstratie si anume:

Teorema 4.1. Daca pentru toti , problema de programare liniara are optim finit si

Teorema 4.2. Daca pentru un indice pentru care toate componentele , programul are optim infinit.

a. Daca toti atunci este solutia optima si

b. Daca exista cel putin o diferenta atunci solutia nu este optima. In acest caz exista urmatoarele posibilitati:

a. Fie asa incat si daca toti , problema nu are optim finit.

b. Fie cu si exista cel putin un , atunci solutia poate fi imbunatatita.

Se trece la prima iteratie prin care se determina vectorul care intra in baza si vectorul care iese din baza. Indicele k al vectorului care intra in baza ne este dat de:

iar indicele h al vectorului care iese din baza este dat de:

In acest mod vectorului din baza ii ia locul vectorul

Se stabileste elementul pivot y_kh y_kh si se recalculeaza toate elementele tabloului simplex si se obtine o noua solutie de baza. Daca aceasta solutie nu este optima se trece la iterata urmatoare.

Exemplul 4.1 Sa se rezolve problema de programare liniara

Solutie

, .

Vectorii si formeaza o baza.

Variabilele bazice sunt si .

Alcatuim tabelul simplex:

Cea mai mare diferenta pozitiva este c₁ - f₁ = 3 si avem y_i1 > deci solutia poate fi imbunatatita.

In baza va intra vectorul Pentru a vedea ce vector iese in baza calculam

deci din baza iese vectorul . Pivotul este 4.

Tabelul simplex din iterata urmatoare este:

Mai avem o diferenta pozitiva deci in baza intra vectorul si iese vectorul deoarece pe coloana lui avem o singura coordonata pozitiva 3/2. Pivotul este 3/2. Tabloul simplex in iterata urmatoare este:

Avem doua diferente pozitive dar pe coloanele lor ele-mentele transformate sunt negative deci problema nu are optim finit.