Lema Farkas-MinkowskiFie Considerm urmtoarele sisteme liniare: (S1)(S2)Lem. Dintre sistemele (S1) i (S2) doar unul i numai unul are soluii.Demonstraie.1. Cele dou sisteme nu pot avea simultan soluii. Prin absurd, presupunem x0 o soluie a lui (S1) i u0 o soluie a lui (S2).Avem:Contradicie !Rezult: dac unul din sisteme are o soluie, cellalt este incompatibil.2. Dac unul din sisteme este incompatibil, atunci cellalt are soluie.

Cursul 5

Presupunem sistemul (S1) incompatibil.Cazul 1. Sistemul de ecuaii este incompatibil.Considerm sistemul de ecuaii:Acesta este compatibil:Rezult: sistemul (S2) este compatibil.Cazul 2. Sistemul de ecuaii este compatibil, dar nu admite o soluie Construim o soluie a sistemului (S2) folosind un raionament prin inducie dup numrul coloanelor lui

Cursul 5

Considerm sistemul (S1) format dintr-o singur coloan A1.Atunci b 0 i avem soluia x1 < 0 astfel nct A1 x1 = b .n acest caz, vectorul u = -b este o soluie a sistemului (S2):Fie k 1 i presupunem:Considerm c (S1) are k + 1 coloane i nu admite o soluie x 0.Dac atunci u0 este o soluie a sistemului (S2).

Cursul 5

Presupunem i vom construi o soluie a sistemului (S2).Definim urmtorii vectori:construii cu proprietatea:Sistemul nu admite o soluiePrin absurd, dac exist o soluieavem:Contradicie cu ipoteza c (S1) nu are soluie pentru k + 1 coloane!

Cursul 5

Folosind ipoteza de inducie, rezult c exist astfel nctPentru fiecare avem:Definim:n plus, avem:

Cursul 5

De asemenea, se verific i relaia:Prin urmare, sistemul (S2) este compatibil.(q.e.d.)Observaie. Sistemele (S1) i (S2) se mai numesc sisteme duale n sens Farkas-Minkowski. Lema Farkas-Minkowski se poate aplica i la alte perechi de sisteme liniare. duala F-M

Cursul 5

O consecin la Lema Farkas-Minkowski:Teorem. Fie o matrice antisimetric Sistemulare o soluie cu proprietateaDemonstraie.Considerm sistemele duale Farkas-Minkowski: iVom lua b = - ei pentru i fixat, 1 i n, i A = - S .Obinem sistemele duale F-M:(S1)(S2)Cazul 1. Sistemul (S1) are o soluieAvem:Rezult:Cazul 2. Sistemul (S2) are o soluieAvem:Rezult:Lum i avem evident(q.e.d.)

Cursul 5

Dualitate n optimizarea liniarProblema 1.D1 = 13D2 = 17B1 = 12B2 = 8B3 = 10523342S se distribuie marfa din depozite la beneficiari, n aa fel nct, costul total de transport s fie minim. Dac notmcantitatea de marf transportat de la depozitul Di ctre beneficiarul Bj, modelul matematic este:

Cursul 5

Problema 2.D1 = 13D2 = 17CumprVndB1 = 12B2 = 8B3 = 10u1u2v1v3v2Condiie: diferena dintre preul de vnzare i cel de cumprare s nu depeasc costul unitar de transport de la depozitul Di la beneficiarul Bj.S se stabileasc costurile de cumprare i vnzare a mrfii n aa fel nct s se obin un beneficiu maxim.

Cursul 5

Problema primal:Problema dual:( P )( D )=========================================================================

Cursul 5

Unei probleme de minimizare i corespunde o problem de maximizare, i reciproc.Reguli de asociere a problemelor duale

Cursul 5

Problema primal:Problema dual:( P )( D )=========================================================================

Cursul 5

Unei probleme de minimizare i corespunde o problem de maximizare, i reciproc.Coeficienii din funcia obiectiv a unei probleme devin coeficienii termenului liber n cealalt problem, i reciproc.Reguli de asociere a problemelor duale

Cursul 5

Problema primal:Problema dual:( P )( D )=========================================================================

Cursul 5

Reguli de asociere a problemelor dualeUnei probleme de minimizare i corespunde o problem de maximizare, i reciproc.Coeficienii din funcia obiectiv a unei probleme devin coeficienii termenului liber n cealalt problem, i reciproc.Matricea restriciilor dintr-o problem este matricea transpus din cealalt problem, i reciproc.

Cursul 5

Problema primal:Problema dual:( P )( D )=========================================================================

Cursul 5

Reguli de asociere a problemelor dualeUnei probleme de minimizare i corespunde o problem de maximizare, i reciproc.Coeficienii din funcia obiectiv a unei probleme devin coeficienii termenului liber n cealalt problem, i reciproc.Matricea restriciilor dintr-o problem este matricea transpus din cealalt problem, i reciproc.Fiecrei restricii dintr-o problem i corespunde o variabil n cealalt problem, i reciproc.Relaia de asociere este urmtoarea:unei restricii concordante i corespunde o variabil nenegativ i reciproc;unei restricii egalitate i corespunde o variabil oarecare (fr condiii de semn), i reciproc;unei restricii neconcordante i corespunde o variabil nepozitiv i reciproc.

Cursul 5

Problema primal:Problema dual:( P )( D )=========================================================================

Cursul 5

Problema primal:Problema dual:( P )( D )=========================================================================

Cursul 5

Problema primal:Problema dual:( P )( D )=========================================================================

Cursul 5

Problema primal:Problema dual:( P )( D )=========================================================================

Cursul 5

Problema primal:Problema dual:( P )( D )=========================================================================

Cursul 5

Problema primal:Problema dual:( P )( D )=========================================================================

Cursul 5

Cursul 5

Teoreme de dualitateFiei definim domeniile de admisibilitate:Considerm perechea de probleme (canonice) duale:( P )( D )Teorem (dualitate slab). Dac domeniile de admisibilitateatunci are loc relaia:Demonstraie. Pentru avem:Prin urmare,(q.e.d.)

Cursul 5

Teorem (dualitate tare). Dac domeniile de admisibilitatei astfel nct atunci, este soluie optim pentru (P) i este soluie optim pentru (D) .Demonstraie. Presupunem prin absurd c nu este optim pentru (P).Atunci, astfel nct Contradicie!Teorema (fundamental a dualitii). Fiind dat perechea de probleme duale (P) i (D) doar una din urmtoarele afirmaii are loc: i n cazul acesta i soluii optime pentru (P), respectiv (D), astfel nct i i sau i n cazul acesta problema care are soluii admisibile are optimul infinit.(q.e.d.)

Cursul 5

Demonstraie. Considerm matricea ptratic de ordinul n+m+1:Deoarece putem aplica consecina Lemei Farkas-Minkowski:exist astfel nct iNotm: unde Avem:

Cursul 5

Definim:Evident, mprind relaiile (1) i (2) la r, obinem:Deci,Din dualitatea slabDin relaia (3) / rDin dualitatea tare rezult optime pentru (P), respectiv (D).adic,

Cursul 5

Nu putem aveaPrin absurd, dac exist avem:deci, Contradicie! cu (6)Rezult:

Cursul 5

Presupunem, spre exemplu, c existDefinim vectorulAvem evident iDeci,Deoarecerezult,(q.e.d.)

Cursul 5

Teorem (tare a ecarturilor complemetare). Dacatunci, pentru (P) i (D) exist soluiile optime respectiv astfel nctDemonstraie. Rezult din (4) i (5) pentru cazul r > 0 .Teorem (slab a ecarturilor complemetare). FieAtunci, x este soluie optim pentru (P) u este soluie optim pentru (D)Demonstraie. Din TFD a) rezult: Deci,Adunm membru cu membru relaiile din enun i obinem:Din teorema de dualitate tare rezult ca soluiile sunt optime.(q.e.d.)(q.e.d.)

Cursul 5