Algoritmul Simplex Dual

Extras din referat Cum descarc?

Problemei de programare liniara:
(24)                           
i se asociaza problema:
(25)                            unde  
Problema (24) se va numi primala iar problema (25) duala problemei (24) si reciproc.
Exemplul II.7.1
Folosind tabelul:
1      2        2       0	 
gasim duala:
Teorema II.7.1. Fie X o solutie posibila pentru problema (24) si Y o solutie posibila pentru problema (25). Atunci  
Demonstratie: Din  inmultind la stanga cu  obtinem: 
Pe de alta parte:  
Dar cum   ajungem la concluzia  .
Teorema II.7.2. Daca (24) are optim finit atunci (25) are optim finit si avem     unde  este o solutie optima pentru (24) iar  o solutie optima pentru (25).
Demonstatie: Din teorema II.7.1. pentru orice pereche de programe duale X,Y, avem  . Deci are loc si  . Cum f este o functie liniara, deci continua, atunci   exista si are loc  .
Pe de alta parte folosind (13) si teorema II.4.1. avem  . Se demonstreaza ca   este un program optim pentru duala (25). Atunci:
Teorema II.7.3. (teorema ecarturilor complementare)
Fie X,Y solutii ale problemelor (24), respectiv (25). Atunci X,Y sunt solutii optime daca si numai daca au loc relatiile:
Demonstratie. Avem:
Folosind teoremele II.7.2. si II.7.1. obtinem ca X,Y sunt programe optime daca si numai daca  ceea ce conduce la:
sau:  
Dualitatea se foloseste cel mai frecvent in cazul in care problema primala necesita calcule multe:
Exemplul II.7.2.
Pentru a rezolva aceasta problema cu algoritmul simplex trebuie introduse patru variabile de egalizare, dar scriind problema duala:
aceasta necesita numai doua variabile de egalizare. Obtinem:
2       1       3      2       1      0
1       1               3       0      1	 
-1      -1     -3      -1      0      0	0
1/2   -1/2     0    -5/2     1   -3/2
1/2    1/2     1     3/2     0     1/2	 
1/2    1/2     0     7/2     0     3/2	 -3/2
deci  
Pentru a putea formula duala unei probleme de minim am vazut ca restrictiile trebuie sa aiba forma (24). In acest caz, restrictiile  sunt numite concordante, iar cele  neconcordante. Pentru problema


Fisiere in arhiva (1):

  • Algoritmul Simplex Dual
    • Referat.doc

Imagini din acest proiect Cum descarc?

Descarca gratuit aceast referat (0 €)

Completezi numele, prenumele și adresa de email. După aceea primesti prin email link-ul pentru descărcare. Completeaza o adresă de email validă.

1. Numele, Prenumele si adresa de email:

Daca nu gasesti email-ul, verifica si directoarele spam, junk sau toate mesajele.

* Prin apăsarea pe butonul “Descarcă gratuit acum” declar că am citit, înțeles și agreat termenii și condițiile.


Hopa sus!