Dualitatea in programarea liniara

Dualitatea in programarea liniara

In principiu, fiecarei probleme de programare liniara (numita problema primala) ii corespunde o alta problema de programare liniara, numita duala sa. Impreuna cele doua probleme formeaza un cuplu primala - duala.

Reguli de construire a problemei duale

Problema duala se construieste folosind elementele problemei primale si o serie de reguli, cate una pentru fiecare dintre componentele unei probleme de programare liniara.

Aceste componente se refera la:

Natura operatorului functiei obiectiv (minim sau maxim).

Necunoscutele problemei, adica vectorul X (vector transpus) al variabilelor:.

Coeficientii functiei obiectiv, adica elementele vectorului

Termenii liberi ai restrictiilor, adica elementele vectorului .

Coeficientii tehnologici din sistemul de restrictii, adica elementele matricei A:

Natura fiecarei restrictii ("≤", " " sau "=").

Conditia de semn a fiecarei variabile:sausau- oarecare.

Elementele problemei duale vor fi notate astfel:

vectorul variabilelor (transpus);

vectorul coeficientilor functiei obiectiv;

vectorul termenilor liberi ai restrictiilor;

AD - matricea coeficientilor tehnologici ai restrictiilor.

Regulile de constructie a problemei duale sunt urmatoarele:

Duala este o problema de minim daca primala este o problema de maxim si invers.

Fiecarei restrictii i a problemei primale ii corespunde o variabila u_i a problemei duale, deci duala va avea un numar de m variabile, numar egal cu numarul de restrictii ale problemei primale.

Coeficientii functiei obiectiv ai dualei sunt termenii liberi ai restrictiilor primalei.

Termenii liberi ai restrictiilor dualei sunt coeficientii functiei obiectiv a problemei primale.

Matricea coeficientilor tehnologici din restrictiile dualei este transpusa matricei coeficientilor tehnologici din restrictiile primalei.

Natura fiecarei restrictii a problemei duale depinde de conditia de semn a variabilei x_j a problemei primale, asociata respectivei restrictii:

restrictia dualei este concordanta , daca

restrictia dualei este neconcordanta, daca

restrictia dualei este egalitate, daca oarecare.

Conditia de semn a variabilei ui a problemei duale este:

, daca restrictia corespunzatoare din primala este concordanta;

, daca restrictia corespunzatoare din primala este neconcordanta;

oarecare, daca daca restrictia corespunzatoare din primala este egalitate.

Exemplu: sa se scrie modelul matematic al dualei urmatorei probleme de programare liniara :

Conform regulilor enuntate anterior, vom avea:

Optimul functiei obiectiv a dualei este minim, deoarece primala este o problema de maxim;

Variabilele dualei vor fi:

- u₁    corespunzatoare restrictiei

- u₂ corespunzatoare restrictiei

Coeficientii functiei obiectiv a dualei vor fi egali cu termenii liberi ai restrctiilor problemei primale; functia obiectiv a dualei este:

Duala va avea doua restrictii, cate variabile are primala, ele obtinandu-se astfel:

- matricea a coeficientilor tehnologici este transpusa matricei A a primalei:

T

- termenii liberi ai restrictiilor dualei sunt egali cu coeficientii functiei obiectiv ai primalei;

- ambele restrictii ale dualei sunt concordante, deoarece cele doua variabile ale problemei primale ; cum duala este o problema de minim, semnul restrictiilor este "

Sistemul de restrictii al dualei va fi:

Conditiile de semn ale variabilelor dualei vor fi:

- oarecare, deoarece prima restrictie a problemei primale este egalitate;

- , deoarece a doua restrictie a problemei primale este concordanta.

In final, problema duala este:

Dualele unor forme particulare de probleme de programare liniara

1. Duala unei forme canonice de maximizare este o forma canonica de minimizare si reciproc.

(2.1)

In forma matriciala, cuplul de probleme primala-duala se scrie:

(2.2)

2. Duala unei probleme in forma standard nu este o problema in forma standard

(2.3)

sau matricial

(2.4)

Analog, se scrie duala formei standard in care optimul functiei obiectiv este minim.

(2.5)

Teoreme de dualitate

Se considera cuplul de probleme (P)-(D), primala-duala in forma canonica:

(P) (D)

Teorema 1. Fie X o solutie admisibila a problemei (P) si U o solutie admisibila a problemei (D). Atunci:

2. Daca atunci este o solutie optima a problemei (P) iar este o solutie optima a problemei (D).

Demonstratie:

si Rezulta:

2. Daca si daca X^* nu ar fi solutie optima pentru (P) ar exista o solutie admisibila mai buna X si , contrar celor demonstrate la punctul precedent. Rezulta ca X^* este solutie optima pentru (P). Analog, U^* este solutie optima pentru (D).

Teorema 2 (teorema fundamentala a dualitatii). Intr-un cuplu de probleme primala-duala, una si numai una din urmatoarele afirmatii este adevarata:

a.   Ambele probleme au solutii. In acest caz ambele probleme au solutii optime si valorile optime ale functiilor obiectiv coincid

b.   Una dintre probleme are solutie, iar cealalta nu. In acest caz problema care are solutie admite un optim infinit.

c.    Nici una dintre probleme nu are solutie.

Teorema 3. Daca una dintre problemele unui cuplu primara-duala are solutie optima atunci si cealalta are solutie optima si valorile optime ale functiilor obiectiv coincid.

Observatie: pe baza acestei teoreme rezulta ca rezolvarea uneia dintre cele doua probleme ale cuplului primala-duala ofera solutia optima si pentru cealalta problema. Alegerea spre rezolvare a uneia dintre probleme este determinata de dimensiunea cea mai redusa a bazelor admisibile.

Teorema 4 (teorema ecarturilor complementare). O conditie necesara si suficienta pentru ca un cuplu de solutii admisibile de baza X^* si U^* sa fie optim este ca solutiile sa verifice relatiile:

(2.6)

Pe baza acestor relatii se pot formula urmatoarele concluzii:

daca atunci ;

daca atunci ;

daca atunci ;

daca atunci .

Prima relatie arata ca variabila duala corespunzatoare unei resurse consumate in intregime are o valoare pozitiva.

Adoua relatie arata ca daca o resursa nu a fost utilizata in intregime, variabila duala corespunzatoare ei este nula.

Din analiza relatiilor 3 si 4 se trage concluzia ca daca costul unitar al activitatii a_j, obtinut prin evaluarea consumurilor specifice a_ij cu ajutorul componentelor solutiei optime a problemei duale, este egal cu coeficientul c_j din functia obiectiv (de exemplu beneficiul unitar) atunci componenta , iar daca acest cost este mai mare decat c_j atunci nu este eficient sa includem in programul optim activitatea a_j ().

Interpretarea economica a problemei duale

Se considera urmatoarea problema de programare liniara in care se cere stabilirea unui plan optim de productie.

O firma realizeaza n produse P_j, j = 1, . ,n, folosind m resurse R_i , i = 1, . ,m. Consumurile specifice a_ij , cantitatile disponibile din fiecare resursa bi si beneficiile unitare c_j pentru fiecare produs sunt cunoscute.

Pentru construirea modelului matematic se introduc variabilele de decizie x_j = numarul de produse P_j (j = 1, . ,n) ce se vor fabrica.

Obiectivul firmei fiind maximizarea beneficiului total realizat din vanzarea produselor, programul liniar pentru determinarea combinatiei optime de produse este:

(P)

Sa notam cu combinatia de produse care aduce firmei beneficiul maxim:

Daca admitem ca singura posibilitate a firmei de a obtine beneficiul B^* este transformarea resurselor disponibile in produse conform programului X^* si vanzarea acestora, apare intrebarea: care este contributia fiecarei resurse in parte la formarea acestui beneficiu?

Raman valabile ipotezele de liniaritate care au condus la stabilirea modelului matematic si anume:

contributia unei resurse la beneficiul total al firmei este - pana la o anumita limita- direct proportionala cu cantitatea disponibila din resursa respectiva;

nivelul contributiei unei resurse nu este conditionat de celelalte resurse, ci numai de cantitatea in care ea este disponibila.

Notam cu aportul unei unitati din resursa R₁, din resursa R₂ s.a.m.d. la formarea beneficiului maxim B^* . Dat fiind ipotezele de liniaritate, se poate scrie:

(2.7)

Producerea unei unitati din produsul P necesita a_1j unitati din resursa R₁, a_2j unitati din resursa R₂ , . , a_mj unitati din resursa R_m . Partea din beneficiul B^* corespunzatoare acestor cantitati este

(2.8)

Aceasta marime trebuie sa acopere pretul pe care firma il incaseaza prin vanzare, deoarece nu exista alte resurse de formare a beneficiului in afara transformarii resurselor in produse. Rezulta ca sistemul trebuie sa satisfaca relatiile:

(2.9)

si de asemenea conditiile de nenegativitate.

Sistemul (1.60) este chiar sistemul de restrictii al problemei duale. Conform teoremei ecarturilor suplimentare, resurselor utilizate in intregime le corespund evaluari u_i strict pozitive, iar resurselor excedentare le corespund indicatori u_i = 0. Un produs P_j va aparea in solutia optima a problemei primale (x_j >0) numai atunci cand costul sau unitar de productie, obtinut prin evaluarea resurselor consumate cu ajutorul indicatorilor u_i, nu depaseste pretul unitar de productie c_j , adica:

(2.10)

Prin urmare, pentru o problema de programare liniara scrisa sub forma canonica, in care se cere maximizarea functiei obiectiv, marimea u_i (solutie a problemei duale) reprezinta valoarea ultimei unitati din resursa R_i utilizata in productie. Avand in vedere ca primala este o problema de maxim si duala ei este o problema de minim, rezulta ca, in conditiile in care cantitatea disponibila din resursa R_i creste cu o unitate, atunci valoarea functiei obiectiv creste cu valoarea u_i.

Indicatorii u_i sunt numiti in literatura de specialitate "preturi umbra".

O alta interpretare pentru aceste preturi umbra poate fi urmatoarea: ele reprezinta pretul pe care firma il poate plati in plus, fata de costul de achizitie initial, pentru cumpararea unei noi unitati din resursa R_i, astfel ca, prin suplimentarea cantitatii disponibile de resursa, beneficiul total sa ramana acelasi.

O resursa R_i care a fost utilizata in intregime se numeste resursa rara, pentru ca lipsa sau neajunsul ei limiteaza productia. Ea este recunoscuta prin faptul ca, in solutia optima, restrictia care-i corespunde este satisfacuta cu semnul "=",variabila de compensare este nula, iar pretul umbra corespunzator este nenul .