Dualitatea in programarea liniara

Dualitatea in programarea liniara

Problema dualitatii in programarea liniara prezinta un interes deosebit din punct de vedere matematic cat si economic. In paragra-fele anterioare am facut ipoteza ca pana la metoda bazei artificiale, ramanand totusi restrictia care nu va mai fi necesara in abordarea problemei duale.

Pentru formarea unui program dual trebuie sa tinem seama de urmatoarele reguli:

fiecarei variabile nenegative (nepozitive) din programul primal ii corespunde in programul dual o inecuatie ();

unei variabile fara semn specificat din programul primal ii corespunde in dual o ecuatie;

coeficientii functiei obiectiv din problema primala sunt opusii termenilor liberi din sistemul de restrictii al problemei duale;

termenii liberi ai restrictiilor din problema primala sunt opusii coeficientilor functiei obiectiv din problema duala;

fiecarei restrictii de forma ( sau =) din programul primal ii corespunde in cel dual o variabila nenegativa (nepozitiva sau oarecare);

matricea coeficientilor din sistemul de restrictii din programul dual este transpusa matricii coeficientilor din programul primal.

Utilizand notatiile vectoriale avem urmatoarele forme de programe duale:

Daca programul primal este:

atunci programul dual va fi:

In problema (P) putem da urmatoarele interpretari elementelor: poate fi vectorul preturilor unitare ale bunurilor rezultate din desfasurarea activitatilor, vectorul - cererea de produse (sau disponibilul de materii prime) - costul fiecarei activitati (sau beneficiul realizat din desfasurarea activitatii) iar valoarea totala a bunurilor create sa fie maxima. Putem interpreta problema duala (D) astfel: daca sa reprezinte nivelul la care se desfasoara activitatile fenomenului economic respectiv; - cererea de produse (sau disponibilul de materii prime); - costul fiecarei activitati (sau beneficiul realizat din desfasurarea activitatii respective), sa se determine nivelul fiecarei activitati asa incat sa fie indeplinite sau depasite cererile iar costul total al activitatilor desfasurate sa fi minim.

Daca programul primal (P) este dat sub forma standard:

dualul va fi:

De observat ca dualul nu are forma standard.

Intre cuplurile de probleme duale exista o stransa interdependenta a solutiilor lor. Vom da in continuare cateva rezultate fara demonstratie.

Lema. Daca X si Y constituie solutii posibile pentru cuplul de programe (P) - (D), avem inegalitatea

Pentru un cuplu de programe liniare duale teorema de existenta ne asigura de urmatoarele posibilitati:

Teorema 7.1. (de existenta) Pentru un cuplu de programe liniare duale avem alternativele urmatoare:

a.      nici unul din programe nu admite solutii posibile;

b.      un program are optim finite iar celalalt nu admite solutii posibile;

c.       ambele programe admit solutii optime finite.

Teorema 7.2. (fundamentala a dualitatii) Pentru un cuplu de programe duale (2.7.) - (7.12.), conditia necesara si suficienta pentru ca solutia realizabila de baza a programului primal (P) sa fie optima, este sa existe o solutie realizabila de baza a programului dual (D) asa incat sa avem

Pe baza teoremei dualitatii se poate da si urmatorul rezultat:

Teorema 7.3. Pentru un cuplu de programe lianiare duale (P) - (D) conditia necesara si suficienta ca solutiile posibile si sa fie optime este: