Dualitatea simetrica si dualitatea nesimetrica

Dualitatea simetrica si dualitatea nesimetrica

Putem vorbi de existenta unui cuplu, primal-dual, de probleme de programare liniara care se pot utiliza in modelarea matematica a fenomenelor economice.

Fie modelele de programare liniara (P.L.):

(1)

(2)

Definitie:

Modelele (1) si (2) sunt modele de programare liniara (P.L.) aflate in relatia de dualitate simetrica (modelul (1) este dualul modelului (2) si invers).

Exemplu:

Fie problema de P.L.:

Pentru modelul dual, avem urmatoarele elemente constitutive:

• modelul dat (numit model primal) este de minim, deci modelul dual va fi de maxim;
• modelul primal are doua variabile, deci modelul dual va avea doua restrictii; coeficientii acestor restrictii se vor citi pe coloanele matricii sistemului primal;
• modelul primal are trei restrictii, deci modelul dual va avea trei variabile, pe care le vom note cu y₁, y₂, y₃;
• termenii liberi ai restrictiilor sitemului dual vor fi coeficientii lui f din modelul primal;
• coeficientii functiei obiectiv a modelului dual vor fi termenii liberi al modelului primal;

In final, modelul dual va fi:

Corespondenta biunivoca a cuplurilor de probleme este pusa in evidenta de teoremele dualitatii prezentate si demonstrate mai jos:

Teorema:

Fie X₀ o solutie admisibila pentru modelul (1), cu valoarea functiei obiectiv f₀=f(X₀); fie Y₀ o solutie admisibila pentru modelul (2), cu valoarea functiei obiectiv g₀=g₀(Y₀);

Atunci avem f₀ g_0.

Demonstratie:

Avem evident f(X₀)=c^tX₀, g₀(Y₀)=Y₀^tb;

din AX₀ -b 0 si din Y₀^t 0 TY₀^t(AX₀-b) 0

din c^t-Y₀^tA 0 si din X₀ 0 T (c^t-Y₀^tA)X₀ 0

Adunand relatiile de mai sus obtinem:

(c^t-Y₀^tA)X₀+Y₀^t(AX₀-b) 0 c^tX₀-Y₀^tb 0 deci f₀-g₀ 0

Teorema

Fie X₀ o solutie admisibila (program) pentru modelul (1) si Y₀ o solutie admisibila (program) pentru modelul (2); daca avem relatia f(X₀)=g(Y₀), atunci:

- X₀ este o solutie optima (program optim) pentru modelul (1)

- Y₀ este o solutie optima (program optim) pentru modelul (2)

Demonstratie:

Presupunem ca X₀ nu ar fi solutie optima pentru modelul(1), deci ar exista o solutie admisibila pentru (1) notata cu X₁, pentru care f(X₀)>f(X₁) c^tX₀>c^tX₁.

Dar c^tX₀ = Y₀^tb, c^tX₁ < c^tX₀ T c^tX₁ <Y₀^tb, ceea ce nu este posibil, conform teoremei 1.

Presupunem ca y₀ nu ar fi solutie optima pentru modelul (2) deci ar exista o solutie admisibila pentru (2) notata cu Y₁, pentru care g(Y₀) < g(Y₁) Y₀^tb < Y₁^tb

Dar c^tX₀ = Y₀^tb, Y₁^tb < Y₁^tb c^tX₀ < Y₁^tb, ceea ce nu este posibil conform teoremei 1.

Teorema:

Daca una dintre problemele (1), (2) are functia obiectiv nemarginita, atunci cealalta problema nu are solutii admisibile.

Demonstratie:

Presupunem ca modelul (2) ar avea solutia admisibila Y₀. Cum functia f(X) = c^tX este nemarginita inferior, deducem ca exista o solutie admisibila X₁, pentru care c^tX₁ < Y₀^tb, aceea ce este absurd conform teoremei 1.

Exista insa modele care nu au forma ceruta de catre dualitatea simetrica, adica:

- nu toate restrictiile au inegalitati pentru problema de maxim

- nu toate restrictiile au inegalitati pentru problema de minim

- nu toate variabilele modelului dat sunt nenegative ( 0).

Totusi, s-a pus la punct o modalitate de a constitui dualul oricarui model. Principalele teoreme corespunzatoale acestui tip de dualitate, numita dualitate nesimetrica, nu vor fi enuntate; afirmam numai ca sunt valabile aceleasi teoreme ca si in cazul dualitatii simetrice.

Ansamblul regulilor de scriere a unui astfel de model de dualitate nesimetrica sunt prezentate in continuare:

categorii de variabile

variabile nenegative: x_j 0

variabile nepozitive: x_j 0

variabile libere: x_jIR

categorii de restrictii:

restrictii concordante:

pentru minim : cu

pentru maxim : cu

restrictii necorcondante:

pentru minim : cu

pentru maxim : cu

restrictii egalitati

reguli de corespondenta:

De exemplu:

Modelul dat nu se incadreaza in dualitatea simetrica si constatam urmatoarele:

modelul dual:

va fi de minim;

va avea 4 restrictii;

va avea 3 variabile, anume y₁, y₂, y₃

in modelul primal:

prima restrictie este concordanta, deci y₁ 0;

a dou restrictie este egalitate, deci y₂IR;

a treia restrictie este neconcordanta, deci y₃ 0.

in modelul primal:

x₁ este nenegativa, deci prima restrictie duala va fi concordanta (deci

x₂ este nepozitiva, deci a doua restrictie duala va fi necorcondanta (deci

x₃ este libera, deci a treia restrictie duala va fi egalitate;

x₄ este nepozitiva, deci a patra restrictie duala va fi necorcondanta (deci

Modelul dual va fi deci:

Rezolvam urmatoarea problema economica pentru a vedea semnificatia economica a variabilelor duale si a interpreta rezultatele dualei pe tabelul simplex

Consideram o unitate economica care fabrica

produsele si . Pentru obtinerea lor se utilizeaza trei resurse: forta de munca, mijloace de munca si materii prime. In tabelul urmator se dau consumurile specifice si cantitatile disponibile din cele trei resurse, precum si preturile de vanzare ale produselor.

Modelul matematic pe baza caruia se stabileste programul optim de productie, avand drept criteriu de eficienta valoarea maxima a productiei, are forma:

max

in conditiile:

(j=1,2,3)

Utilizand regulile de dualitate prezentate mai inainte rezulta urmatoarea problema duala de programare liniara:

min

in conditiile:

(j=1,2,3)

Solutia optima a problemei primale este prezentata in tabelul simplex final, unde se testeaza la criteriul de optim daca sunt

Dupa cum s-a aratat, prin rezolvarea uneia dintre problemele cuplului primala-duala se obtin solutiile ambelor probleme.

In cazul examinat, solutia optima a problemei duale se citeste pe linia z la intersectia cu coloanele vectorilor a₄ a_{5 ,} si a₆ care au format baza initiala, deci:

si

Este usor de verificat ca Spre exemplu rezulta din relatia:

Pe baza rezultatelor obtinute se verifica imediat ca

max[Z(x)]=min[G(u)]:

max[Z(x)]= unitati monetare

min[G(u)]= unitati monetare.

Concluzii: Fie cuplul de probleme duale:

i) Tabelul simplex final corespunzator problemei primale contine atat solutia optima a problemei primale cat si a problemei duale.

ii) Solutia problemei primale se obtine pe coloana vectorului b, iar solutia problemei duale se obtine pe linia z la intersectia cu coloanele vectorilor care au format baza initiala.

Teorema ecarturilor complementare:

O conditie necesara si suficienta pentru ca un cuplu de solutii admisibile de baza si sa fie optim, este ca solutiile sa verifice simultan relatiile:

Pe baza acestor relatii se pot formula urmatoarele concluzii:

a)daca atunci

b)daca atunci

c)daca atunci ;

d)daca atunci

Prima relatie arata ca variabila duala corespunzatoare unei resurse utilizata in intregime are o valoare pozitiva, iar cea de a doua arata ca daca resursa i nu este utilizata in intregime.

Analizand punctele c si d se trage concluzia ca, daca costul unitar al activitatii ,obtinut prin evaluarea consumurilor specifice cu ajutorul componentelor solutiei optime a problemei duale, este egal cu coeficientul din functia obiectiv (de exemplu beneficiul unitar) atunci componenta iar daca acest cost este mai mare decat , atunci nu este eficient sa includem in programul optim activitatea j (ca urmare ).