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

Ai nevoie de ajutor la matematica? Pune o întrebare!

la Aritmetica

la Algebra

la Geometrie

despre Examene

sau despre altceva

 

Noutăţi

Ultimele pagini adăugate

Calculul ariei unui patrulater convex

Teorema transversalei

 

Aplicaţii pe mobil

Descompune în factori primi
Numere Prime

 
 

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

Vă mulţumim!'

Site partener:
www.mathematicshelp.org

 

Avem nevoie de o donaţie mică