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 în 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 în 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;

În final, modelul dual va fi:

Corespondenta biunivoca a cuplurilor de probleme este pusa în 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 Y₀^t(AX₀-b)

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

Adunând relatiile de mai sus obtinem:

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

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₀ 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 însa 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 ("

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 în cazul dualitatii simetrice.

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

categorii de variabile

variabile nenegative: x_j

variabile nepozitive: x_j

variabile libere: x_j R

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 încadreaza în dualitatea simetrica si constatam urmatoarele:

modelul dual:

va fi de minim;

va avea 4 restrictii;

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

în modelul primal:

prima restrictie este concordanta, deci y₁

a dou restrictie este egalitate, deci y₂ R;

a treia restrictie este neconcordanta, deci y₃

în 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. În tabelul urmator se dau consumurile specifice si cantitatile disponibile din cele trei resurse, precum si preturile de vânzare ale produselor.

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

max

în conditiile:

(j=1,2,3)

Utilizând regulile de dualitate prezentate mai înainte rezulta urmatoarea problema duala de programare liniara:

min

în conditiile:

(j=1,2,3)

Solutia optima a problemei primale este prezentata în 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.

În 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 atât solutia optima a problemei primale cât 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 în întregime are o valoare pozitiva, iar cea de a doua arata ca daca resursa i nu este utilizata în întregime.

Analizând 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 decât , atunci nu este eficient sa includem în programul optim activitatea j (ca urmare ).