Problema duală

Problema duală este o problemă de programare liniară. Existenţa ei presupune existenţa unei alte probleme de programare liniară numită problema primală, împreună cu care formează cuplul primală – duală. Pentru a vedea cum arată problema duală trebuie să cunoaştem cum arată problema primală şi care este legătura dintre ele.

A cunoaşte cum arată problema primală înseamnă a şti:

1. Dacă problema este de maxim sau de minim;

2. Care sunt necunoscutele problemei, adică vectorul variabilelor:

x^T = (x₁,x₂, … ,x_n)

3. Care sunt coeficienţii funcţiei obiectiv, adică elementele vectorului:

c^T = (c₁,c₂, … ,c_n)

4. Care sunt termenii liberi ai restricţiilor, adică elementele vectorului:

b^T = (b₁,b₂, … ,b_m)

5. Care sunt coeficienţii combinaţiei liniare din fiecare restricţie, adică elementele matricei:

A =

6. Care este natura fiecărei restricţii, adică dacă:

a_i1x₁ + a_i2x₂ + … + a_inx_n ³ b_i sau a_i1x₁ + a_i2x₂ + … + a_inx_n £ b_i sau a_i1x₁ + a_i2x₂ + … + a_inx_n = b_i

7. Care este restricţia de semn a fiecărei variabile, adică dacă:

x_j ³ 0 sau x_j £ 0 sau x_j – oarecare

Problema duală se construieşte folosind elementele problemei primale şi o serie de reguli, câte una pentru fiecare din cele şase componente ale unei probleme de programare liniară, listate mai sus.

În acest scop vom nota elementele problemei duale cu:

- u^T = vectorul variabilelor problemei duale;

- = vectorul coeficienţilor funcţiei obiectiv ai problemei duale;

- = vectorul termenilor liberi ai restricţiilor din problema duală;

- A_D = matricea coeficienţilor combinaţiilor liniare din restricţiile problemei duale;

şi vom introduce noţiunile de restricţie concordantă şi restricţie neconcordantă:

- O restricţie se numeşte concordantă dacă:

- Este de tipul: a_i1x₁ + a_i2x₂ + … + a_inx_n ³ b_i într-o problemă de minim sau

- Este de tipul: a_i1x₁ + a_i2x₂ + … + a_inx_n £ b_i într-o problemă de maxim.

- O restricţie se numeşte neconcordantă dacă:

- Este de tipul: a_i1x₁ + a_i2x₂ + … + a_inx_n ³ b_i într-o problemă de maxim sau

- Este de tipul: a_i1x₁ + a_i2x₂ + … + a_inx_n £ b_i într-o problemă de minim.

- O restricţie de tipul: a_i1x₁ + a_i2x₂ + … + a_inx_n = b_i nu este nici concordantă nici neconcordantă.

În aceste condiţii, problema duală va avea componentele:

- Duala va fi o problemă de minim dacă primala este de maxim şi reciproc;

- u^T = (u₁, u₂, … u_m), deci duala va avea m variabile, număr egal cu numărul de restricţii al primalei, fiecare variabilă u_i fiind asociată unei restricţii i a primalei;

- = b^T, deci coeficienţii funcţiei obiectiv a dualei sunt termenii liberi ai restricţiilor primalei;

- = c^T, deci termenii liberi din restricţiile dualei sunt coeficienţii funcţiei obiectiv a primalei.

- A_D = A^T, deci restricţiile dualei se obţin înmulţind fiecare coloană a matricei primalei cu vectorul variabilelor dualei. În acest mod şi variabilelor primalei li se asociază câte o restricţie a dualei;

- restricţia j a dualei va fi:

§ concordantă dacă x_j ³ 0

§ neconcordantă dacă x_j £ 0

§ egalitate dacă x_j oarecare

- variabila u_i va fi:

§ u_i ³ 0 dacă restricţia corespunzătoare din primală este concordantă

§ u_i £ 0 dacă restricţia corespunzătoare din primală este neconcordantă

§ u_i oarecare dacă restricţia corespunzătoare din primală este egalitate

Din cele de mai sus se observă că, pentru a scrie restricţia j a dualei, avem nevoie de:

- coloana coeficienţilor corespunzători variabilei j din matricea problemei primale pentru a scrie termenul stâng al restricţiei:

a_1ju₁ + a_2ju₂ + … + a_mju_m

- restricţia de semn a variabilei x_j pentru a stabili natura restricţiei;

- coeficientul lui x_j din funcţia obiectiv a primalei, care va fi termenul liber al restricţiei;

Pentru o cât mai bună ilustrare a modului în care se găseşte duala unei probleme vom da câteva exemple.

Exemplul 1. Ne propunem să construim duala problemei următoare:

(max) f = 2x₁ – 5x₂ + 4x₃

x₁ £ 0, x₂ oarecare, x₃ ³ 0

Conform regulilor de mai sus vom avea:

- duala este de minim deoarece primala este de maxim;

- variabilele dualei vor fi:

u₁ corespunzătoare restricţiei: x₁ – x₂ + 4x₃ ³ 7

u₂ corespunzătoare restricţiei: x₂ – 5x₁ + 3x₃ = 6

u₃ corespunzătoare restricţiei: x₁ + 2x₃ £ 3

u₄ corespunzătoare restricţiei: –x₃ + 2x₁ - 5x₂ ³ 8

- funcţia obiectiv a dualei va fi produsul dintre termenii liberi ai restricţiilor primalei cu variabilele corespunzătoare din duală: g = 7u₁ + 6u₂ + 3u₃ + 8u₄

- duala va avea 3 restricţii, câte variabile are primala, ele obţinându-se astfel:

prima restricţie (asociată variabilei x₁)

§ termenul stâng al restricţiei se obţine înmulţind coeficienţii variabilei x₁ din cele 4 restricţii ale primalei cu variabilele corespunzătoare acestora din duală:

u₁ –5u₂ + u₃ + 2u₄

§ termenul liber al restricţiei va fi coeficientul lui x₁ din funcţia obiectiv a primalei, adică b₁ = c₁ = 2

§ deoarece variabila corespunzătoare acestei restricţii, x₁, este negativă, restricţia va fi neconcordantă şi deoarece duala este problemă de minim rezultă că va fi cu £.

În concluzie, prima restricţie va fi: u₁ –5u₂ + u₃ + 2u₄ £ 2

a doua restricţie (asociată variabilei x₂)

§ termenul stâng al restricţiei se obţine înmulţind coeficienţii variabilei x₂ din cele 4 restricţii ale primalei cu variabilele corespunzătoare acestora din duală:

-u₁ + u₂ - 5u₄

§ termenul liber al restricţiei va fi coeficientul lui x₂ din funcţia obiectiv a primalei, adică b₂ = c₂ = -5

§ deoarece variabila corespunzătoare acestei restricţii, x₂, este oarecare, restricţia va fi o egalitate.

În concluzie, a doua restricţie va fi: -u₁ + u₂ - 5u₄ = -5

a treia restricţie (asociată variabilei x₃)

§ termenul stâng al restricţiei se obţine înmulţind coeficienţii variabilei x₃ din cele 4 restricţii ale primalei cu variabilele corespunzătoare acestora din duală:

4u₁ +3u₂ + 2u₃ - u₄

§ termenul liber al restricţiei va fi coeficientul lui x₃ din fiuncţia obiectiv a primalei, adică b₃ = c₃ = 4

§ deoarece variabila corespunzătoare acestei restricţii, x₃, este pozitivă, restricţia va fi concordantă şi deoarece duala este problemă de minim rezultă că va fi cu ³ .

În concluzie, a treia restricţie va fi: 4u₁ + 3u₂ + 2u₃ - u₄ ³ 4

- restricţiile de semn ale variabilelor dualei vor fi:

§ u₁ £ 0, deoarece restricţia corespunzătoare este neconcordantă;

§ u₂ oarecare, deoarece restricţia corespunzătoare este egalitate;

§ u₃ ³ 0, deoarece restricţia corespunzătoare este concordantă;

§ u₄ £ 0, deoarece restricţia corespunzătoare este neconcordantă.

În final, problema duală este:

(min) g = 7u₁ + 6u₂ + 3u₃ + 8u₄

u₁ £ 0, u₂ oarecare, u₃ ³ 0, u₄ ³ 0

Exemplul 2. Considerăm o unitate economică care fabrică produsele P₁, P₂ şi P₃. Pentru obţinerea lor se utilizează trei resurse: forţa de muncă, mijloacele de muncă şi materii prime. În tabelul de mai jos se dau consumurile specifice şi cantităţile disponibile din cele trei resurse, precum şi preţurile de vânzare ale celor trei produse.

Produse Resurse	P1	P2	P3	Disponibil (unităţi fizice)
Forţa de muncă	1	3	4	15
Mijloace de muncă	2	5	1	10
Materii prime	4	1	2	25
Preţ de vânzare (unităţi monetare)	3	2	6	_

Dorim să producem acele cantităţi x_i din fiecare produs pentru care:

1. se utilizează în întregime forţa de muncă;

2. se produce cel puţin o unitate din produsul de tipul P₂;

3. se obţine valoarea maximă a vânzărilor.

Modelul matematic pe baza căruia se stabileşte programul optim de producţie are forma:

(max) f = 3x₁ + 2x₂ + 6x₃

x_j ³ 0 (j = 1,2,3)

Duala sa va fi:

(min) g = 15u₁ + 10u₂ + 25u₃ + u₄

u₁ oarecare, u₂ ³ 0, u₃ ³ 0, u₄ £ 0

Se remarcă faptul că, într-o problemă economică, nenegativitatea variabilelor primalei (x_j³0) impune ca în duală toate restricţiile să fie concordante.

Exemplul 3.

Primala (min) f = 4x1 + 3x2 x1, x2 ³ 0

Duala (max) g = 56u1 + 43u2 + 31u3 + 20u4 + 30u5 + 41u6 + 65u7 uI ³ 0 (i = 1,7)

Corespondenţa care există între problema primală şi problema duală, atât sub aspect matematic, cât şi economic, va fi lămurită de observaţiile şi teoremele de mai jos:

Lema 1. Duala problemei duale este problema primală.

Demonstraţia acestei leme este uşoară, făcându-se pe baza simetriilor care se observă în construcţia dualei şi va fi lăsată în seama cititorului, semnificaţia ei fiind că operaţia de trecere la duală este o operaţie involutivă (adică e o transformare f cu proprietatea: (f ○ f )(x) = x) şi, deci, perechea primală-duală formează un cuplu în care fiecare este duala celeilalte. Din această cauză vom vorbi de cuplul primală-duală fără a mai specifica expres care este primala şi care duala.

Observaţia 1. Dacă o problemă este la forma canonică atunci şi duala sa este o problemă la forma canonică.

Observaţia 2. Dacă o problemă este la forma standard atunci duala sa nu este la forma standard.

Lema 2. Dacă P₁ şi P₂ sunt două probleme de programare liniară echivalente atunci şi dualele lor sunt de asemenea echivalente. Vom înţelege, în această afirmaţie, prin probleme echivalente, două probleme care se pot obţine una din cealaltă prin transformări elementare. Aceste transformări realizează un izomorfism între mulţimile soluţiilor celor două probleme şi un homeomorfism între funcţiile lor obiectiv.

Teorema fundamentală a dualităţii.

Rezolvarea celor două probleme din cuplul primală-duală poate duce doar la unul din următoarele trei rezultate:

- Dacă una din cele două probleme are soluţie optimă finită atunci şi cealaltă are soluţie optimă finită şi valorile funcţiilor obiectiv corespunzătoare celor două soluţii sunt egale;

- Dacă una din cele două probleme are optim infinit atunci cealaltă nu are soluţii admisibile.

- Dacă una din cele două probleme nu are soluţii admisibile atunci cealaltă are optim infinit sau nu are soluţii admisibile.

Rezolvare. Presupunem că cele două probleme au fost aduse la forma canonică:

Primala (max) c^Tx Ax £ b x ³ 0

Duala (min) b^Tu A^Tu ³ c u ³ 0

Această presupunere nu va afecta rezultatul, deoarece, dacă nu erau deja aşa, noile probleme sunt echivalente cu cele iniţiale. În continuare, pentru rezolvarea acestei teoreme demonstrăm următoarea lemă:

Lema 3. Dacă există soluţii admisibile pentru fiecare problemă atunci pentru orice x soluţie admisibilă a primalei şi orice u soluţie admisibilă a dualei avem:

c^Tx £ b^Tu

Demonstraţie: Avem:

A^Tu ³ c Û (A^Tu)^T ³ c^T Û u^TA ³ c^T

De asemenea:

Obţinem:

Pentru a demonstra teorema, presupunem că am rezolvat una din cele două probleme, aceasta fiind considerată ca fiind primala. Avem trei variante:

1. Problema are optim finit. Fie în acest caz fie x_B o soluţie de bază a primalei sub forma standard, care dă optimul problemei, adică c^Tx_B = . Toţi D_j corespunzători acestei baze vor fi pozitivi şi ţinând cont de expresia lui D_j, rezultă:

B^-1A ³ c^T Û A^T(B^-1)^T ³ c

relaţie care spune că vectorul cu m componente u^* = (B^-1)^T este o soluţie de bază admisibilă a problemei duale (primala fiind la forma standard, variabilele dualei pot avea orice semn).

Avem, conform lemei 3: c^Tx_B £ u^Tb pentru orice soluţie admisibilă a problemei duale. Pe de altă parte c^Tx_B = c^TB^-1b = (u^*)^Tb de unde rezultă că pentru orice soluţie admisibilă a problemei duale se verifică:

(u^*)^Tb £ u^Tb

care este echivalent cu faptul că u^* este soluţia de optim a dualei şi că f(x_B) = g(u^*).

2. Problema are optim infinit. În acest caz, dacă duala ar avea soluţii admisibile u, g(u) ar fi un majorant pentru mulţimea {f(x)/ x admisibilă}, în contradicţie cu ipoteza de optim infinit.

3. Problema nu are soluţii. În acest caz, dacă duala ar avea optim finit ar rezulta, conform celor arătate în varianta 1, că primala are optim finit, în contradicţie cu ipoteza.

În concluzie, deoarece cele trei variante acoperă toate situaţiile posibile, toate ducând la unul din rezultatele afirmate ca posibile în teoremă şi ţinând cont de faptul că nu a avut importanţă care problemă a fost aleasă spre rezolvare, teorema este demonstrată.

Teorema ecarturilor complementare.

Fie x^* = şi u^* =două soluţii admisibile ale primalei, respectiv dualei, scrise sub forma canonică. Atunci ele sunt soluţii optime ale celor două probleme dacă şi numai dacă verifică sistemul:

sau, matricial

Demonstraţie.

“Þ” Presupunem că x^* şi u^* sunt soluţiile optime ale celor două probleme. Atunci:

(u^*)^T(b – Ax^*) ³ 0

(( u^*)^TA - c)(x^*) ³ 0 Þ

cum (u^*)^Tb = cx^* (conform teoremei fundamentale) Þ

Þ (u^*)^T(b – Ax^*) + (( u^*)^TA - c)(x^*) = (u^*)^Tb – (u^*)^T Ax^* + ( u^*)^TA x^* - cx^* = 0

Þ (u^*)^T(b – Ax^*) = (( u^*)^TA - c)(x^*) = 0

“Ü”

Dacă (u^*)^T(b – Ax^*) = (( u^*)^TA - c)(x^*) = 0 Þ (u^*)^T(b – Ax^*) + (( u^*)^TA - c)(x^*) = 0 Þ (u^*)^Tb = cx^* Þ ( conform teoremei fundamentale) x^* şi u^* sunt soluţiile optime ale celor două probleme.

Teorema ecarturilor complementare dă o caracterizare pentru optimalitatea soluţiilor primalei şi dualei, dacă ele există. Sistemul din teoremă se obţine aplicând metoda multiplicatorilor lui Lagrange pentru extreme cu legături, în cazul particular al unei probleme de programare liniară.

Această teoremă nu reprezintă o modalitate practică de a rezolva cele două probleme decât în anumite cazuri simple, rezolvarea sistemului fiind mai grea, în cazul problemelor liniare, decât rezolvarea cu algoritmul simplex al fiecărei probleme, dar, pe baza ei, se poate găsi soluţia uneia din probleme dacă se cunoaşte soluţia celeilalte sau se poate verifica dacă o soluţie a unei probleme este optimă, introducând-o în sistem, găsind celelalte necunoscute şi verificând că ele formează o soluţie admisibilă a dualei.

Observaţia 3. Demonstrarea teoremei fundamentale s-a făcut găsind efectiv soluţia optimă a dualei, considerându-se că primala a fost rezolvată cu algoritmul simplex. Ea este B^-1 şi, pentru găsirea practică a acesteia, trebuie cunoscută B^-1. Matricea B^-1 nu apare explicit în rezolvarea problemei cu algoritmul simplex, dar se poate demonstra că este formată din coloanele din tabelul simplex al soluţiei optime corespunzătoare poziţiilor care formau baza soluţiei iniţiale. B^-1 reprezintă chiar z_j corespunzătoare acestor coloane din ultimul tabel, deci putem formula rezultatul:

“soluţia dualei este formată din valorile z_j ale tabelului soluţiei optime, corespunzăoare vectorilor coloană ai bazei iniţiale”

Introducerea dualităţii este motivată din mai multe puncte de vedere:

1. Teoretic. Una din problemele centrale ale programării matematice este caracterizarea situaţiilor în care există optimul unei probleme şi găsirea unor metode prin care să recunoaştem optimalitatea unei soluţii. Teorema fundamentală a dualităţii şi teorema ecarturilor complementare reprezintă rezultate chiar în acest sens, în care se foloseşte dualitatea.

2. Practic. Rezultatele obţinute mai sus conturează faptul că putem rezolva o problemă rezolvând problema duală a acesteia sau cunoscând soluţia dualei. În unele cazuri, rezolvarea dualei este mult mai uşoară decât rezolvarea primalei, de exemplu când numărul de restricţii al primalei este mai mare decât numărul de variabile al acesteia sau când primala necesită mai multe variabile suplimentare decât duala. Astfel, pentru exemplul 3 de mai sus, rezolvarea primalei duce la opt iteraţii cu tabele cu 7 linii şi 16 coloane, iar rezolvarea dualei la 5 tabele cu 2 linii şi 9 coloane. În alte cazuri, soluţiile dualei sunt deja cunoscute, găsirea soluţiilor primalei revenind la a rezolva sistemul din teorema ecarturilor complementare, după ce au fost înlocuite soluţiile celei duale.

3. Economic. În cele mai multe probleme economice, a căror rezolvare se face printr-un model de programare liniară, soluţia dualei aduce o serie de informaţii suplimentare despre problema studiată. Semnificaţia economică a soluţiei dualei depinde de specificul problemei şi trebuie găsită de la caz la caz. Expunem în continuare interpretarea economică a variabilelor şi soluţiilor dualei în cazul unei probleme de producţie.

În paragrafele precedente s-a demonstrat că, prin rezolvarea unei probleme de programare liniară, se obţine atât soluţia optimă a problemei iniţiale cât şi a problemei duale. Corespondenţa dintre problema iniţială şi duală se reflectă în conţinutul economic al parametrilor incluşi în soluţia problemei duale. Semnificaţia economică a indicatorilor u_i este determinată de natura problemei economice şi de tipul restricţiilor problemei primale.

Într‑o problemă sub formă canonică, în care se cere maximizarea funcţiei obiectiv, restricţiile pot fi interpretate ca inecuaţii ce se referă la resurse şi, de aceea, interpretarea variabilelor u_i este mai simplă.

Vom analiza modelul de programare liniară al problemelor de mai jos:

Exemplul 1: O unitate economică fabrică produsele P₁, P₂ şi P₃ utilizând trei resurse: forţa de muncă, mijloace de muncă şi materii prime. Consumurile specifice, cantităţile disponibile din fiecare resursă şi preţurile de vânzare ale produselor sunt date în tabelul de mai jos:

Produse Resurse	P1	P2	P3	Disponibil (unităţi fizice)
Forţa de muncă	1	3	4	15
Mijloace de muncă	2	5	1	10
Materii prime	4	1	2	25
Preţ de vânzare (unităţi monetare)	3	2	6	-

Modelul matematic pe baza căruia se stabileşte programul optim de producţie, având drept criteriu de eficienţă valoarea maximă a producţiei, are forma:

(max) f = 3×x₁ + 2×x₂ + 6×x₃

x₁, x₂, x₃ ³ 0

Utilizând regulile de trecere la duală, rezultă următoarea problemă duală:

(min) g = 15×u₁ + 10×u₂ + 25×u₃

u₁, u₂, u₃ ³ 0

După rezolvarea cu algoritmul simplex se obţine soluţia optimă a celor două probleme în ultimul tabel simplex, dat în continuare:

			3	2	6	0	0	0
cB	xB	xB	x1	x2	x3	s1	s2	s3
6	x3		0		1			0
3	x1		1		0			0
0	x6		0	-9	0	0	-2	1
zj	-		3		6			0
Dj	-	-	0		0			0

Exemplul 2: Activitatea unei întreprinderi industriale se concretizează în fabricarea produselor omogene P₁, P₂, P₃ şi P₄, ale căror costuri unitare de producţie sunt: c₁ = 4, c₂ = 3, c₃ = 7 respectiv c₄ = 2 unităţi monetare. Pentru desfăşurarea procesului de producţie este necesar ca din produsul P₁ să se asigure un stoc de cel puţin 5 unităţi şi, în plus, câte cel puţin 2 unităţi pentru fiecare piesă P₃ (produsul P₁ intră în componenţa produsului P₃). În anul de bază, volumul producţiei realizate de întreprindere a fost de 20 unităţi. În urma analizei desfacerilor s-a ajuns la concluzia că cererea este în creştere. De asemenea, întreprinderea îşi propune ca în perioada de plan să obţină un beneficiu total cel puţin egal cu cel din perioada de bază, care a fost de 100 u.m.. Beneficiul unitar corespunzător celor 4 produse s-a estimat a fi de 2, 5, 8 respectiv 3 u.m..

Modelul matematic corespunzător problemei primale şi respectiv problemei duale are forma:

Primală	Duală
(min) f = 4×x1 + 3×x2 + 7×x3 + 2×x4 în condiţiile x1, x2, x3, x4 ³ 0	(max) g = 5x1 + 20x2 + 100x3 în condiţiile u1 oarecare, u2,u3 ³ 0 şi u4 £ 0

Exemplul 3: Considerăm problema dată în exemplul 1 căreia îi ataşăm două modificări:

1. forţa de muncă trebuie folosită în întregime;

2. volumul producţiei planificate al produsului P₂ trebuie să fie cel puţin egal cu o unitate fizică;

Cuplul de probleme primală-duală va avea forma:

Primală	Duală
(max) f = 3×x1 + 2×x2 + 6×x3 x1, x2, x3 ³ 0	(min) g = 15×u1 + 10×u2 + 25×u3 + u4 u1 oarecare, u2, u3 ³ 0, u4 £ 0

Se constată ca, în funcţia obiectiv a problemei duale, apar cantităţile disponibile din cele trei resurse, înmulţite cu mărimile u₁, u₂, şi respectiv u₃. Întrucât resursele reprezintă valori de întrebuinţare diferite, cantităţile b_i nu se pot însuma decât dacă indicatorii u_i evaluează resursele în aceeaşi unitate de măsură. După cum se vede din aceste model, valoarea indicatorilor u_i depinde de cantitatea de resurse disponibile, de structura consumurilor directe din resursa respectivă şi de structura matematică a modelului.

Conform teoremei ecarturilor complementare, resurselor utilizate în întregime le corespund evaluări u_i strict pozitive, iar resurselor excedentare le corespund indicatori u_i = 0. Un produs P_j va apărea în soluţia optimă, (x_j > 0) numai atunci când costul său unitar de producţie, obţinut prin evaluarea resurselor consumate cu ajutorul indicatorilor u_i, nu depăşeşte preţul unitar de producţie c_j, adică atunci când:

= c_j (R)

Ideea enunţată mai sus se confirmă şi în cazul exemplelor analizate. Astfel, în exemplul 1, produsul P₂ nu apare în soluţia optimă (x₂ = 0) deoarece costul său de producţie depăşeşte preţul unitar de realizare:

a₁₂×u₁ + a₂₂×u₂ + a₃₂×u₃ > c₂

adică: 3× + 5× + 1×0 = 8,1 > 2.

Celelalte două produse intră în programul optim, întrucât este satisfăcută relaţia (R). Deci, fabricarea unui produs care nu figurează în programul optim este neeficientă din punctul de vedere al folosirii resurselor.

Prin urmare, pentru o problemă de programare liniară scrisă sub forma canonica, în care se urmăreşte maximizarea funcţiei f (x), mărimea u_i reprezintă valoarea ultimei unităţi folosite în producţie din resursa R_i.

Având în vedere că max[f(x)] = min [g(u)], rezultă că, dacă, cantitatea disponibilă din resursa R_i creşte cu o unitate, atunci valoarea funcţiei obiectiv creşte cu u_i, deci u_i măsoară creşterea valorii funcţiei obiectiv determinată de creşterea cu o unitate a cantităţii disponibile b_i.

Aceste evaluări obţinute dintr‑un program optim au fost denumite în literatura de specialitate "preţuri umbră" sau "evaluări obiectiv determinate".

Preţul umbră u_i arată cu cât se modifică funcţia obiectiv a problemei duale[1], atunci când termenul liber al restricţiei R_i se "relaxează" cu o unitate. A "relaxa" are semnificaţia de a spori cantitatea disponibilă b_i a unei resurse deficitare sau, pentru restricţiile de tip calitativ cu limită inferioară impusă (³ b_i), de a reduce nivelul termenului liber b_i. Este evident că, dacă o resursă nu este utilizată în întregime pentru satisfacerea programului optimal x_B (< b_i), atunci u_i = 0 iar funcţia obiectiv nu este afectată de sporirea[2] cantităţii disponibile b_i. În cazul restricţiilor de tip calitativ, acestea nu constituie un "loc îngust" pentru programul optimal x_B dacă şi numai dacă > b_i, ca urmare u_i = 0 iar funcţia obiectiv nu este influenţată de reducerea² nivelului pentru indicatorul b_i.

Pentru o problemă scrisă sub formă canonică, în care se cere minimizarea funcţiei f(x), restricţiile se referă, aşa cum s-a arătat, la caracteristici economice cărora li se impun limite inferioare sau la indicatori calitativi cu limită inferioară stabilită; în acest caz preţul umbră u_i măsoară creşterea costului total al producţiei, a cheltuielilor de muncă, a cheltuielilor cu fondurile fixe etc., determinată de creşterea cu o unitate a componentei b_i a vectorului termenilor liberi. Astfel, daca la exemplul 2 planul de producţie prevede o creştere a volumului producţiei de la 20 unităţi la 21 unităţi, atunci costul total al producţiei va creşte cu u₂ unităţi.

În cazul problemelor de programare liniară care conţin restricţii neconcordante şi egalităţi, la interpretarea preturilor umbră trebuie să se ţină seama de natura economică a funcţiei obiectiv şi de semnul variabilei u_i. Pentru a elucida acest aspect, ne vom referi la modelul matematic ce rezultă din exemplul 3.

Soluţiile optimale ale problemei primale şi duale sunt:

x_B = (x₁, x₂, x₃, x₄, x₅, x₆) = (8/7, 1, 19/7, 0, 14, 0)

u_B = (u₁, u₂, u₃, u₄) = (9/7, 6/7, 0, – 43/7).

Se constată imediat că valoarea funcţiei obiectiv f(x_B) = g(u_B) = 152/7 este mai mică decât cea obţinută prin rezolvarea modelului din exemplul 1, cu Df(x) = 195/7 – 152/7 = 43/7 unităţi monetare[3]. Această diferenţă apare datorită introducerii restricţiei x₂ > 1, al cărei preţ umbră este u₄ = – 43/7. Prin urmare variabila u₄ arată cu cât scade valoarea funcţiei obiectiv f(x) atunci când nivelul minim impus variabilei x₂ este mai mare cu o unitate.

În sfârşit variabila u₁ = 9/7, care este ataşată unei restricţii sub formă de egalitate, arată că sporirea cu o unitate a nivelului forţei de muncă disponibile conduce la creşterea valorii producţiei cu 9/7 unităţi monetare.

Rezultă că preţurile umbră aduc informaţii suplimentare pentru analiza eficienţei economice a resurselor şi a diferiţilor indicatori economici sau tehnici care apar în restricţiile unei probleme de programare liniară. Pe baza lor se pot fundamenta deciziile privind alocarea judicioasă a resurselor, se pot stabili măsuri de stimulare a consumului raţional al resurselor, se determină cât mai corect nivelul minim şi maxim al diferiţilor indicatori tehnici şi economici de care depinde structura planului optim.

Soluţia optimă obţinută prin utilizarea datelor iniţiale poate constitui un punct de plecare pentru analiza economică privind alocarea eficientă a resurselor. Vom ilustra acest aspect folosind modelul matematic elaborat în cadrul exemplului 1.

În tabelul de mai jos se dau soluţiile optime ale cuplului primală-duală, pentru diferite valori ale primei resurse (b₂ = 10, b₃ = 25).

	Cantitatea disponibilă din prima resursă (b1)
Variabile	15	16	26	36	40	41
u4 x1	3 25/7	3 24/7	3 2	3 4/7	3 0	3 0
u5 x2	57/7 0	57/7 0	57/7 0	57/7 0	57/7 0	30 0
u6 x3	6 20/7	6 22/7	6 6	6 62/7	6 10	6 10
u1 x4	9/7 0	9/7 0	9/7 0	9/7 0	9/7 0	0 1
u2 x5	6/7 0	6/7 0	6/7 0	6/7 0	6/7 0	6 0
u3 x6	0 5	0 5	0 5	0 5	0 5	0 5
f(x)	195/7	204/7	42	55	60	60

Se observă că între anumite limite de variaţie ale primei resurse, preţurile umbră au aceeaşi valoare. Pentru valori mai mari decât 40 unităţi, preţurile umbră au o altă valoare, deoarece, în acest caz, prima resursă şi a treia devin excedentare. Valoarea funcţiei de eficienţă va creşte cu u₁×Db₁, unde Db₁ reprezintă sporul disponibilului din prima resursă. Pentru b₁ > 40 preţul umbră al resursei a doua este u₂ = 6, deci valoarea funcţiei eficienţă va creşte cu 6 unităţi, atunci când b₂ creşte cu o unitate. Aste informaţii sunt utile pentru fundamentarea planului de producţie aprovizionare cu diverse resurse.

La interpretarea influenţei pe care variaţia cantităţii disponibile b_i o are asupra preţurilor umbră, trebuie să se ţină seama că b_i este o variabilă continuă. Din această cauză u_i se defineşte astfel:[4]

u_i =

Este clar că u_i va avea o altă valoare când b_i creşte (scade) peste o anumită limită (de exemplu b_i > 40).

După cum s‑a arătat mai înainte, în cadrul algoritmului simplex se stabileşte activitatea cea mai eficientă a_k, prin folosirea criteriului de intrare:

DZ_k = min (z_j – c_j) la problemele de maxim

DZ_k = max (z_j – c_j) la. problemele de minim

Având în vedere relaţia formulele de calcul ale lui DZ şi u_B, rezultă că:

z_j = = j Î J_S

unde y_ij reprezintă elementele coloanei j din tabelul simplex corespunzător unei soluţii de bază. În cea de a doua sumă a relaţiei precedente se evaluează coeficienţii consumurilor directe, corespunzători activităţii a_j, prin preţurile umbră ataşate celor m restricţii şi, de aceea, mărimea rezultată poate fi interpretată ca un preţ umbră al produsului sau activităţii j. Trebuie precizat că, pentru fiecare bază, vom dispune de un vector u = (u₁, u₂, ... , u_m) care se referă la fluxurile intrări ‑ ieşiri corespunzătoare soluţiei de bază. De aceea, evaluările privind eficienţa economică a activităţilor a_j (j Î J_S = indicii variabilelor secundare), făcute cu ajutorul indicatorilor u_i, sunt valabile numai pentru baza considerată.

Concluziile obţinute pe baza analizei corespondenţei biunivoce dintre problema primală şi cea duală ne permit să înţelegem sensul economic al criteriului de intrare în bază.

Pentru problemele în care se cere maximizarea funcţiei f(x), indicatorii z_j reprezintă costul unitar de fabricaţie al produsului j, rezultat din evaluarea coeficienţilor a_ij prin preţurile umbră ataşate restricţii1or. Rezultă că, prin calcularea diferenţei D_j, se compară acest cost unitar cu coeficientul c_j (preţ unitar, beneficiu unitar etc.) din funcţia obiectiv. Dacă există diferenţe negative (D_j < 0) înseamnă că, la activităţile respective, preţul umbră al produsului j (costul unitar de fabricaţie exprimat în indicatori u_i) este mai mic decât venitul realizat şi de aceea activitatea a_j este eficientă. Aşa se explică faptul că va intra în bază vectorul a_k ce corespunde diferenţei Dz_j minime. În momentul în care toate diferenţele sunt pozitive (Dz_j ³ 0) rezultă că nu mai există activităţi eficiente şi prin urmare soluţia de bază analizată este optimă.

În cazul problemelor de minim, indicatorii z_j se pot interpreta ca venituri, exprimate în preţurile umbră ale restricţiilor, ce se obţin prin realizarea unei unităţi din produsul j. Prin urmare, dacă există diferenţe pozitive (Dz_j > 0), activităţile a_j corespunzătoare sunt eficiente, deoarece se realizează un venit unitar mai mare decât costul unitar de fabricaţie (z_j > c_j). De aceea, va intra în bază activitatea a_k, corespunzătoare diferenţei maxime, iar soluţia de bază se consideră optimă atunci când toate diferenţele Dz_j sunt nepozitive (Dz_j £ 0).

---

[1] Dar şi a problemei primale, întrucât f(x) şi g(u) sunt legate prin teorema dualităţii

[2] Variaţia termenului liber b_i trebuie interpretată ca o modificare Db_i, în condiţiile în care celelalte restricţii nu se modifică. Vezi exemplul 1.

[3] Reamintim că exemplul 3 s‑a obţinut din exemplul 1 ca urmare a unor transformări. Precizăm că, în soluţiile optime ale ambelor modele, prima restricţie se verifică cu egalitate. De aceea, diferenţa dintre cele două soluţii este determinată numai de restricţia x₂ > 1.

[4] F este o funcţie de tip Lagrange, obţinută din problema standard de programare liniară astfel:

F = f(x) + u_i×R_i (x)

unde R_i(x) reprezintă restricţiile problemei de programare liniară iar u_i, 1 £ i £ m sunt multiplicatorii lui Lagrange.