Algoritmul simplex
Se considera problema de programare (2) si un program de baza nedegenerat . Dupa unele renumerotari si rearanjari putem considera ; deci variabilele sunt principale iar secundare, iar vectorii coloana formeaza baza B a programului de baza . Fie
Mai notând:
problema (2) poate fi scrisa:
Înmultind la stânga cu obtinem:
care reprezinta transcrierea sistemului de restrictii în baza B, caci daca scriem (exprimarea vectorilor coloana în functie de vectorii bazei B) vom avea:
Corespunzator programului problema (2) devine:
Deci sunt componentele vectorului L în baza B.
Deci relatia (8) devine:
de unde
si atunci
:
sau explicit:
Notând: atunci:
Observam ca
Acum putem asocia problemei PL- min urmatorul tabel:
c1 c2 cn
a1 a2 an
vectorii bazei
componentele nenule ale lui
.........................................
Teorema II.4.1. Daca este un program de baza nedegenerat pentru PL - min si în tabelul asociat (S) avem atunci este program optim.
Demonstratie: Din (13) avem:
pentru orice program admisibil X. Deci este optim.
Teorema II.4.2. Daca este un program de baza nedegenerat si în tabelul simplex asociat (S) exista un t, astfel încât , atunci PL - min nu are optim finit.
Demonstratie: Fie: unde:
Astfel avem
Pentru avem:
Deci este solutie admisibila. Avem:
din definirea lui .
Deoarece atunci , adica functia obiectiv nu are optim finit.
Teorema II.4.3. Daca este un program de baza nedegenerat pentru PL - min, iar în tabelul simplex asociat (S) exista un t, si cel putin un indice i, , astfel încât , atunci alegând , dupa criteriul:
se poate substitui în baza B vectorul cu vectorul , obtinând o baza , corespunzatoare unui program de baza care amelioreaza valoarea functiei obiectiv.
Demonstratie. Deoarece folosind lema substitutiei rezulta ca înlocuind în B cu sistemul de vectori nou obtinut , este o baza. Solutia de baza corespunzatoare luieste data tot de lema substitutiei:
cu toate componentele nenegative (pentru daca atunci
, deci o suma de numere nenegative; iar daca avem si tinând seama de (14) înseamna ca este produs de doua numere nenegative).
Deci este o solutie de baza. Valoarea functiei obiectiv pentru este:
Acum putem prezenta algoritmul simplex pentru o problema PL - min în forma standard.
-Pasul 10: Se gaseste un program de baza nedegenerat cu baza B; se construieste tabelul simplex (S).
-Pasul : Se verifica daca diferentele pentru orice . Daca DA se trece la pasul 5; daca NU, dintre toate diferentele , negative, se alege cea mai mica. Indicele j corespunzator sa-l notam cu t. (Daca exista mai multi t se alege primul de la stânga la dreapta). Vectorul va intra în baza. Se cerceteaza daca pentru Daca DA, se trece la pasul 4, daca NU, se trece la pasul 3.
-Pasul : Se alege s, astfel încât .
Vectorul va iesi din baza. Elementul devine pivot. Se construieste un nou tabel simplex folosind regula dreptunghiului:
a) se împarte linia pivotului la pivot.
b) în coloana pivotului, elementele se înlocuiesc cu 0
c) elementele se înlocuiesc cu .
Se obtine un alt program de baza cu baza si o noua valoare a functiei obiectiv.
Se revine la pasul cu si
-Pasul 40 .Concluzie: “PL - min nu are optim finit” sI algoritmul se opreste.
-Pasul .Concluzie: “PL - min are optim iar valoarea minima ". STOP.
Exemplul II.4.1. Fie problema:
Alegem . Avem:
Coordonatele vectorilor în baza B sunt , respectiv . Pentru a afla coordonatele lui se procedeaza astfel: punem , deci:
ceea ce ne da . Deci în baza B, . Analog se gasesc:
Asadar tabelul simplex corespunzator bazei B are forma:
5 7 9 2 1
1 0 1 1 -1
0 1 -1 1
0 0 11 -10 -15
Deci intra în baza, iese din baza, z25 - pivot. Se executa pivotajul si obtinem:
1 1/3 2/3 0
0 1/3 -1/3 1/3 1
0 5 6 -5 0
Intra în baza si iese .
...
