Algebra - Algoritmul Simplex

Algoritmul simplex

            Se consideră problema de programare (2) şi un program de bază nedegenerat . După unele renumerotări şi rearanjări putem considera ; deci variabilele  sunt principale iar  secundare, iar vectorii coloană  formează baza B a programului de bază . Fie

Mai notând:

  problema (2) poate fi scrisă:

            Înmulţind  la stânga cu obţinem:

care reprezintă transcrierea sistemului de restricţii în baza B, căci dacă scriem  (exprimarea vectorilor coloană în funcţie de vectorii bazei B) vom avea:

  Corespunzător programului problema (2) devine:

Deci  sunt componentele vectorului L în baza B.

Deci relaţia (8) devine:

 de unde

  şi atunci

:  

sau explicit:

Notând:  atunci:

Observăm că

          Acum putem asocia problemei PL- min următorul tabel:

          Teorema II.4.1. Dacă este un program de bază nedegenerat pentru PL - min şi în tabelul asociat (S) avem  atunci  este program optim.

          Demonstraţie: Din (13) avem:

 pentru orice program admisibil X. Deci este optim.

          Teorema II.4.2. Dacă este un program de bază nedegenerat şi în tabelul simplex asociat (S) există un t,  astfel încât , atunci PL - min nu are optim finit.

          Demonstraţie: Fie: unde:

Astfel avem

Pentru  avem:

       Deci  este soluţie admisibilă. Avem:

din definirea lui .

          Deoarece  atunci , adică funcţia obiectiv nu are optim finit.

            Teorema II.4.3. Dacă este un program de bază nedegenerat pentru PL - min, iar în tabelul simplex asociat (S) există un t,  şi cel puţin un indice i, , astfel încât , atunci alegând , după criteriul:

se poate substitui în baza B vectorul cu vectorul , obţinând o bază , corespunzătoare unui program de bază care ameliorează valoarea funcţiei obiectiv.

          Demonstraţie. Deoarece  folosind lema substituţiei rezultă că înlocuind  în B cu sistemul de vectori nou obţinut , este o bază. Soluţia de bază corespunzătoare luieste dată tot de lema substituţiei:

cu toate componentele nenegative (pentru  dacă  atunci

 , deci o sumă de numere nenegative; iar dacă  avem şi ţinând seama de (14) înseamnă că  este produs de două numere nenegative).

Deci este o soluţie de bază. Valoarea funcţiei obiectiv pentru este:

          Acum putem prezenta algoritmul simplex pentru o problemă PL - min în formă standard.

-Pasul 1⁰: Se găseşte un program de bază nedegenerat cu baza B; se construieşte tabelul simplex (S).

-Pasul : Se verifică dacă diferenţele pentru orice . Dacă DA se trece la pasul 5; dacă NU, dintre toate diferenţele , negative, se alege cea mai mică. Indicele j corespunzător să-l notăm cu t. (Dacă există mai mulţi t se alege primul de la stânga la dreapta). Vectorul va intra în bază. Se cercetează dacă  pentru  Dacă DA, se trece la pasul 4, dacă NU, se trece la pasul 3.

-Pasul : Se alege s, astfel încât .

Vectorul va ieşi din bază. Elementul devine pivot. Se construieşte 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 obţine un alt program de bază cu baza şi o nouă valoare a funcţiei obiectiv.

Se revine la pasul cu şi

-Pasul 4⁰ .Concluzie: “PL - min nu are optim finit” şI algoritmul se opreşte.

-Pasul .Concluzie: “PL - min are optim iar valoarea minimă ". STOP.

          Exemplul II.4.1. Fie problema:

Alegem . Avem:

          Coordonatele vectorilor în baza B sunt , respectiv . Pentru a afla coordonatele lui  se procedează astfel: punem  , deci:

 ceea ce ne dă . Deci în baza B, . Analog se găsesc:

Aşadar tabelul simplex corespunzător bazei B are forma:

		5      7      9      2      1
3		1       0      1       1      -1    0       1     -1       1
		0       0     11    -10    -15

          Deci intră în bază,  iese din bază, z₂₅ - pivot. Se execută pivotajul şi obţinem:

4/3		1    1/3    2/3             0    0    1/3   -1/3   1/3     1
		0     5       6      -5      0

          Intră în baza şi iese .

          Şi am obţinut Deci programul optim este .

            Algoritmul se aplică şi problemelor PL - max în forma standard cu observaţia că  . De asemenea algoritmul se aplică şi în cazul în care funcţia obiectiv are forma , deoarece punctele de extrem ale acesteia sunt aceleaşi cu punctele de extrem ale funcţiei: