Dualitatea problemelor de optimizare

Dualitatea problemelor de optimizare

Sa presupunem ca o problema de optimizare care se poate rezolva cu ajutorul programarii liniare cere determinarea a "u" numere x_j unde pentru care functia este maxima , cu urmatoarele restrictii :

Matricea sistemului M poate fi scrisa astfel :

In baza acelorasi date se poate construi o noua problema , numita problema duala a celei propuse . Fie "m" variabile y₁ , y₂ , ........y_m , care sa corespunda celor "m" inecuatii ale multimii M .

Problema duala are ca scop gasirea minimului functiei în conditiile :

Se constata ca matricea sistemului M₁ scrisa sub forma

este transpusa matricii A

În amândoua problemele apar aceleasi constante c_j , a_ij , b_i, în schimb. numarul variabilelor x_j, y_i se schimba de la "n" la "m" , iar numarul restrictiilor de la "m" la "n" . Cele doua probleme formeaza împreuna o uniune de probleme duale .

Pentru simplificarea prezentarii , cele doua probleme se pot exprima sub forma matriciala astfel:

a - Problema primara

f(max)= maxC x cu restrictiile AxB , x0

unde

, si

b - Problema duala

g(min)= min B y în conditiile A_1yC , y0 unde

Pentru formularea problemei duale este bine sa se întocmeasca urmatorul tabel :

Matricea generala a problemei duale

Tabel nr.

Problema primara se realizeaza pe linii , iar cea duala pe coloane .

Între doua probleme de optimizare prin programare liniara, care formeaza un cuplu de probleme duale, exista legaturi strânse de interdependenta a solutiilor lor, formulate de teorema fundamentala a dualitatii , care arata ca pentru orice cuplu de probleme duale este posibila numai una dintre urmatoarele trei  situatii :

Daca ambele probleme au solutii de realizare, atunci ambele probleme au solutii optime si valorile functiilor obiectiv coincid, adica max C'X = min B'Y

Daca problema primara nu are solutii realizabile, cea duala are un optim infinit

Nici una dintre cele doua probleme nu are solutii realizabile.

Avantajele dualitatii problemelor de optimizare, care se pot rezolva prin programare liniara, se pot sintetiza astfel:

transformarea minimului unei functii liniare într-un maxim si invers;

se poate alege un program care solicita calcule mai putine;

rezultatele pot fi verificate.

Pentru exemplificare se ia o problema de organizare a productiei din cadrul unei sectii a unei unitati economice agricole.

Resursele R_j unde j = (1,2) coeficientii tehnologici a_ij, stocurile din fiecare resursa a profitului pe unitatea de produs sunt trecute în tabelul urmator:

Se urmareste determinarea numarului de produse din fiecare sortiment astfel încât profitul total sa fie maxim.

Aceasta este problema primara care, matemacic se exprima astfef:

f(max) =max(5x+3y)

în care :

x , y reprezinta numarul de produse de fiecare fel .

f - profitul total .

Prin rezolvarea sistemului rezulta : x=3 si y=2 iar f(max)=21 .

Formarea problemei duale urmareste determinarea preturilor unitare p₁ si p₂ ale resurselor R_j în asa fel ca , date fiind stocurile din fiecare resursa si profitul pe fiecare unitate de produs , valoarea cheltuielilor sa fie cât mai mica posibil .

Folosind datele din tabelul de mai sus si notând cu C_h valoarea cheltuielilor totale putem scrie : minC_h = min(5s₁+8s₂) unde s₁ , s₂ reprezinta stocurile de resurse . Asa cum s-a aratat , profiturile sunt de 5 si respectiv 3 unitati valorice pentru cele doua produse .

Sistemul problemei duale se poate scrie astfel :

Solutiile problemei duale sunt :

s₁=1 ; s₂=2 .

Se obtine astfel minim C_h = 21 unitati valorice .

Prin acest exemplu simplu se constata importanta programului optim dual .