Extras din seminar

Problema nr 1

Dualitatea problemelor de optimizare

Sa presupunem ca o problema de optimizare care se poate rezolva cu ajutorul programarii liniare cere determinarea a „u” numere xj 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 y1 , y2 , ........ym , care sa corespunda celor „m” inecuatii ale multimii M .

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

Se constata ca matricea sistemului M1 scrisa sub forma

este transpusa matricii A

În amândoua problemele apar aceleasi constante cj , aij , bi, în schimb. numarul variabilelor xj, yi 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 Ax B , x 0

unde

g(min)= min B’y în conditiile A1y C , y 0 unde

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

Matricea generala a problemei duale

Tabel nr.

Produse

Resurse c1 c2 .............................cj..........................cm

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 :

1. 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

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

3. 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.