Algebra - Algoritmul Simplex

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 Algebra Liniara sunt principale iar Algebra Liniara secundare, iar vectorii coloană  formează baza B a programului de bază . Fie

Mai notând:

 Algebra Liniara, Simplex, formula problema (2) poate fi scrisă:

Algebra Liniara, Simplexul

            Înmulţind Algoritmul Simplex la stânga cu Algebra Liniaraobţinem:

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


 

 Algoritmul Simplex Corespunzător programului Algebra Superioara, formula algoritm simplexproblema (2) devine:

Deci Algoritmul Simplex sunt componentele vectorului L în baza B.

Algebra Liniara

Deci relaţia (8) devine:

Algoritmul Simplex de unde

  şi atunci

:  

sau explicit:

Notând: Algoritmul Simplex atunci:

Observăm că Algoritmul Simplex

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

 

Algoritmul Simplex

 c1     c2            cn

a1      a2            an

(S)

 

vectorii bazei

componentele nenule ale lui

.........................................

       

 

          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 10: 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 40 .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ă, z25 - 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 .

 

  15/4    25/4      17/2     0    0

 

          Ş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:

Forum

...
 

Noutăţi

 

Daca vreti sa ne dati o idee scrieti-ne la opinii@mateonline.net

Vă mulţumim!'

 

Avem nevoie de o donaţie mică