Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune. stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme


Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Matematica


Index » educatie » Matematica
» Dualitatea in programarea liniara


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:




1.   Natura operatorului functiei obiectiv (minim sau maxim).

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

3.   Coeficientii functiei obiectiv, adica elementele vectorului .

4.   Termenii liberi ai restrictiilor, adica elementele vectorului .

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

6.   Natura fiecarei restrictii (“≤”, “³” sau “=”).

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

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

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

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

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

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

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

-  restrictia dualei este concordanta , daca ;

-  restrictia dualei este neconcordanta, daca ;

-  restrictia dualei este egalitate, daca  oarecare.

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

     - u1 corespunzatoare restrictiei

     - u2 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:

1.

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

Demonstratie:

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

1.     daca atunci ;

2.     daca  atunci ;

3.     daca atunci ;

4.     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 aj, obtinut prin evaluarea consumurilor specifice aij cu ajutorul componentelor solutiei optime a problemei duale, este egal cu coeficientul cj din functia obiectiv (de exemplu beneficiul unitar) atunci componenta , iar daca acest cost este mai mare decat cj atunci nu este eficient sa includem in programul optim activitatea aj ().

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 Pj, j = 1,…,n, folosind m resurse Ri , i = 1,…,m. Consumurile specifice aij , cantitatile disponibile din fiecare resursa bi si beneficiile unitare cj  pentru fiecare produs sunt cunoscute.

Pentru construirea modelului matematic se introduc variabilele de decizie xj = numarul de produse Pj  (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 R1, din resursa R2  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 a1j unitati din resursa R1, a2j   unitati din resursa R2 ,…, amj  unitati din resursa Rm . 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 ui strict pozitive, iar resurselor excedentare le corespund indicatori ui = 0. Un produs Pj va aparea in solutia optima a problemei primale (xj >0) numai atunci cand costul sau unitar de productie, obtinut prin evaluarea resurselor consumate cu ajutorul indicatorilor ui, nu depaseste pretul unitar de productie cj , adica:

                                                                                                (2.10)

            Prin urmare, pentru o problema de programare liniara scrisa sub forma canonica, in care se cere maximizarea functiei obiectiv, marimea ui (solutie a problemei duale) reprezinta valoarea ultimei unitati din resursa Ri  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 Ri creste cu o unitate, atunci valoarea functiei obiectiv creste cu valoarea  ui.

            Indicatorii ui 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 Ri, astfel ca, prin suplimentarea cantitatii disponibile de resursa, beneficiul total sa ramana acelasi.

            O resursa Ri 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 .







Politica de confidentialitate


Copyright © 2019 - Toate drepturile rezervate

Matematica


Statistica


Functii polinomiale
Formule simple de aproximare a derivatelor
RELATII METRICE IN TRIUNGHIUL DREPTUNGHIC
Polinomul de interpolare Lagrange
Rezolvarea numerica a ecuatiilor diferentiale si a sistemelor de ecuatii diferentiale
Functii inversabile
Vectori
TRANSLATIA
Modele statice si modele dinamice
Compunerea functiilor