Matematici aplicate în economie · Optimizare liniară

Dualitate și analiza sensibilității

Avansat70 min

Pe această pagină

Ce înveți

  • Scrii problema duală a unei probleme de programare liniară și explici ce înseamnă variabilele ei.
  • Interpretezi prețul umbră al unei resurse și decizi dacă merită să cumperi o unitate în plus.
  • Calculezi între ce limite se poate schimba un profit sau o resursă fără ca planul optim să se schimbe.

Teorie

În lecția despre programare liniară, atelierul de mobilă (mese x cu 50 de lei profit, scaune y cu 40 de lei, 30 de ore de montaj, 40 de unități de lemn) a găsit planul optim: 10 mese și 20 de scaune, cu 1300 de lei profit. În tabelul simplex final au mai apărut două numere, 30 și 10, în dreptul resurselor. Ele răspund la o întrebare foarte practică: cât valorează pentru atelier o oră sau o unitate de lemn în plus?

Partea 1. Problema duală

Exemplu ipotetic. Un antreprenor vrea să închirieze pentru o săptămână toate resursele atelierului: cele 30 de ore și cele 40 de unități de lemn. El oferă u lei pentru fiecare oră și v lei pentru fiecare unitate de lemn. Atelierul acceptă doar dacă, pentru fiecare produs, banii primiți pe resursele lui sunt cel puțin cât profitul pe care l-ar face singur:

  • o masă folosește 1 oră și 2 unități de lemn, deci u+2v≥50u + 2v \ge 50;
  • un scaun folosește 1 oră și 1 unitate de lemn, deci u+v≥40u + v \ge 40.

Antreprenorul vrea să plătească în total cât mai puțin, adică min⁡W=30u+40v\min W = 30u + 40v. Aceasta este problema duală a problemei atelierului (numită problema primală).

Regulile prin care scrii duala:

  • fiecărei restricții din primală îi corespunde o variabilă în duală (orele dau u, lemnul dă v);
  • fiecărei variabile din primală îi corespunde o restricție în duală (masa și scaunul);
  • maximizarea devine minimizare, iar restricțiile „≤” devin „≥”;
  • profiturile din funcția-obiectiv devin termenii liberi, iar cantitățile de resurse devin coeficienții noii funcții-obiectiv; tabelul coeficienților se citește pe coloane în loc de linii.

În scriere matriceală, unde ATA^T este transpusa matricei A (liniile devin coloane):

primala: max⁡Z=cTx, Ax≤b, x≥0duala: min⁡W=bTu, ATu≥c, u≥0\text{primala: } \max Z = c^T x,\ Ax \le b,\ x \ge 0 \qquad \text{duala: } \min W = b^T u,\ A^T u \ge c,\ u \ge 0

Când primala are și restricții „≥” sau „=”, ori variabile care pot fi negative, regulile complete de trecere de la o problemă de maximizare la duala ei de minimizare sunt:

Primala (max)Duala (min)
restricția i de tip „≤”variabila ui≥0u_i \ge 0
restricția i de tip „≥”variabila ui≤0u_i \le 0
restricția i de tip „=”variabila uiu_i fără restricție de semn
variabila xj≥0x_j \ge 0restricția j de tip „≥”
variabila xjx_j fără restricție de semnrestricția j de tip „=”
profitul cjc_j din funcția-obiectivtermenul liber al restricției j
termenul liber bib_icoeficientul lui uiu_i în funcția-obiectiv

Tabelul se citește și invers: duala dualei este primala.

Vârfurile zonei admisibile a dualei sunt (0, 40), (30, 10) și (50, 0). Costul în fiecare vârf este W=1600W = 1600, W=30×30+40×10=900+400=1300W = 30 \times 30 + 40 \times 10 = 900 + 400 = 1300 și W=1500W = 1500 de lei. Minimul este 1300 de lei, exact cât profitul maxim al atelierului.

Duala unei probleme de minimizare. Fermierul din lecția „Programare liniară” caută furajul cel mai ieftin: min⁡C=2a+3b\min C = 2a + 3b, cu 2a+b≥82a + b \ge 8 (proteine) și a+3b≥9a + 3b \ge 9 (energie). Duala lui este o problemă de maximizare: un fabricant de suplimente vrea să vândă fermierului proteina pură cu u lei pe unitate și energia pură cu v lei pe unitate, cât mai scump, max⁡W=8u+9v\max W = 8u + 9v, dar fără ca suplimentele să fie mai scumpe decât furajele care conțin aceleași substanțe: 2u+v≤22u + v \le 2 (furajul A) și u+3v≤3u + 3v \le 3 (furajul B). Din cele două ecuații, v=2−2uv = 2 - 2u și u+6−6u=3u + 6 - 6u = 3, deci u=0,6u = 0{,}6 și v=0,8v = 0{,}8. Valoarea dualei este 8×0,6+9×0,8=4,8+7,2=128 \times 0{,}6 + 9 \times 0{,}8 = 4{,}8 + 7{,}2 = 12 lei, exact costul minim al fermierului. Prețurile umbră spun că o unitate de proteine în plus ar costa 60 de bani, iar una de energie 80 de bani.

Teoremele dualității

Trei rezultate leagă cele două probleme. Notăm cu Z funcția-obiectiv a primalei (maximizare) și cu W pe cea a dualei (minimizare).

  • Dualitatea slabă: pentru orice soluție admisibilă x a primalei și orice soluție admisibilă u a dualei, Z(x)≤W(u)Z(x) \le W(u). Orice ofertă acceptabilă a antreprenorului este o margine superioară pentru profitul atelierului.
  • Dualitatea tare (teorema dualității): dacă una dintre probleme are soluție optimă, o are și cealaltă, iar valorile optime sunt egale: Z∗=W∗Z^* = W^*. Dacă primala are profit nemărginit, duala nu are soluții admisibile.
  • Ecarturile complementare: la optim, pentru fiecare restricție, produsul dintre partea ei nefolosită și variabila duală corespunzătoare este zero:
ui⋅si=0pentru fiecare resursa˘ i,xj⋅(a1ju1+…+amjum−cj)=0pentru fiecare produs ju_i \cdot s_i = 0 \quad \text{pentru fiecare resursă i}, \qquad x_j \cdot \left(a_{1j} u_1 + \ldots + a_{mj} u_m - c_j\right) = 0 \quad \text{pentru fiecare produs j}

A doua relație spune că un produs care se fabrică (xj>0x_j > 0) aduce exact cât valorează resursele lui la prețurile umbră. Pentru atelier, masa: 1×30+2×10=501 \times 30 + 2 \times 10 = 50, exact profitul ei; scaunul: 30+10=4030 + 10 = 40.

Partea 2. Prețurile umbră

Pentru atelier, u=30u = 30 și v=10v = 10:

  • o oră de montaj în plus aduce 30 de lei profit în plus. Verificare: cu 31 de ore, noul optim este 9 mese și 22 de scaune, cu 50×9+40×22=450+880=133050 \times 9 + 40 \times 22 = 450 + 880 = 1330 de lei;
  • o unitate de lemn în plus aduce 10 lei în plus. Verificare: cu 41 de unități, optimul este 11 mese și 19 scaune, cu 550+760=1310550 + 760 = 1310 de lei.

Prețul umbră este suma maximă pe care merită s-o plătești pentru o unitate în plus. Dacă un angajat ar face ore suplimentare cu 25 de lei pe oră, atelierul câștigă 30−25=530 - 25 = 5 lei la fiecare oră. Dacă un furnizor cere 15 lei pe o unitate de lemn în plus, nu merită: ar pierde 15−10=515 - 10 = 5 lei pe unitate.

Ce se întâmplă cu o resursă care nu se folosește integral? Să zicem că piața cumpără cel mult 15 mese pe săptămână, deci apare restricția x≤15x \le 15. Planul optim rămâne 10 mese, deci 5 „locuri” de vânzare rămân nefolosite. A mai putea vinde o masă nu ajută la nimic, deci prețul umbră al acestei restricții este 0. Regula generală se numește ecarturi complementare:

  • dacă dintr-o resursă rămâne ceva nefolosit, prețul ei umbră este 0;
  • dacă prețul umbră al unei resurse este mai mare decât 0, resursa se folosește integral.

Unde găsești prețurile umbră. Nu trebuie să rezolvi separat duala: ele apar în linia lui Z a tabelului simplex final, în coloanele variabilelor de compensare. Pentru atelier, tabelul final din lecția anterioară avea în linia lui Z numerele 30 (sub s1s_1, orele) și 10 (sub s2s_2, lemnul). În aceeași linie, sub fiecare produs, apare costul redus:

dj=(a1ju1+a2ju2+…+amjum)−cjd_j = \left(a_{1j} u_1 + a_{2j} u_2 + \ldots + a_{mj} u_m\right) - c_j

adică valoarea resurselor consumate de o unitate din produsul j (la prețurile umbră) minus profitul ei. Pentru produsele din planul optim, dj=0d_j = 0; pentru un produs care nu se fabrică, djd_j arată cu cât ar trebui să crească profitul lui ca să merite fabricat.

Partea 3. Analiza sensibilității

Datele unei firme nu sunt niciodată sigure: prețurile se schimbă, un furnizor întârzie. Analiza sensibilității arată între ce limite se pot schimba datele fără ca planul optim sau prețurile umbră să se schimbe.

Când se schimbă un profit. Planul (10, 20) rămâne optim cât timp dreapta de izoprofit este „între” cele două restricții care se întâlnesc în acest vârf. În cuvinte: raportul dintre profitul unei mese și profitul unui scaun trebuie să rămână între 1 (raportul orelor, 1 : 1) și 2 (raportul lemnului, 2 : 1).

  • Dacă scaunul aduce în continuare 40 de lei, masa poate aduce între 1×40=401 \times 40 = 40 și 2×40=802 \times 40 = 80 de lei. Planul nu se schimbă; se schimbă doar profitul total.
  • Dacă masa aduce în continuare 50 de lei, scaunul poate aduce între 50:2=2550 : 2 = 25 și 50:1=5050 : 1 = 50 de lei.

Când se schimbă o resursă. Prețul umbră de 30 de lei pe oră nu este valabil la nesfârșit. Cu b ore și 40 de unități de lemn, planul optim este la intersecția dreptelor x+y=bx + y = b și 2x+y=402x + y = 40, adică x=40−bx = 40 - b și y=2b−40y = 2b - 40. Ambele cantități sunt pozitive doar când b este între 20 și 40 de ore. Peste 40 de ore, lemnul ajunge doar pentru 40 de scaune, iar orele în plus nu mai aduc nimic: prețul lor umbră scade la 0. La fel, prețul umbră de 10 lei al lemnului este valabil între 30 și 60 de unități.

Regula generală pentru două produse. Dacă în vârful optim se întâlnesc restricțiile a1x+b1y≤r1a_1 x + b_1 y \le r_1 și a2x+b2y≤r2a_2 x + b_2 y \le r_2, planul rămâne optim cât timp raportul profiturilor c1:c2c_1 : c_2 stă între rapoartele a1:b1a_1 : b_1 și a2:b2a_2 : b_2 ale celor două restricții. Pentru resurse, metoda este cea de mai sus: scrii coordonatele vârfului în funcție de cantitatea resursei și ceri ca ele să rămână pozitive.

Raportul de sensibilitate. Programele de calcul (de exemplu, Solver din Excel) adună toate aceste informații în două tabele. Pentru atelier, ele arată așa:

ProdusCantitate optimăCost redusProfit pe bucatăCreștere permisăScădere permisă
Mese100503010
Scaune200401015
ResursăFolositPreț umbrăDisponibilCreștere permisăScădere permisă
Ore3030301010
Lemn4010402010

Se citește așa: profitul mesei poate urca cu 30 de lei (până la 80) sau coborî cu 10 lei (până la 40) fără ca planul să se schimbe; orele pot varia între 20 și 40 cu același preț umbră de 30 de lei; lemnul, între 30 și 60 cu prețul umbră de 10 lei.

Video

Introduction to Shadow Prices

de Eric Verburg

Se încarcă de pe YouTube

Introduction to Shadow Prices · de Eric Verburg · Deschide pe YouTube

Întrebare-ghid: Clipul este în engleză (shadow price = preț umbră, constraint = restricție). Urmărește cum se calculează noul profit când o resursă crește cu o unitate și compară cu verificarea din Partea 2.

Linear Programming by Graphing, Sensitivity Analysis on Constraints, Shadow Price

de Dr D’s Math Help

Se încarcă de pe YouTube

Linear Programming by Graphing, Sensitivity Analysis on Constraints, Shadow Price · de Dr D’s Math Help · Deschide pe YouTube

Întrebare-ghid: Clipul este în engleză (range of feasibility = intervalul în care prețul umbră rămâne valabil). Urmărește cum se mută dreapta unei restricții când crește resursa și până unde rămâne același vârful optim.

Exemple grafice

Primul grafic arată profitul maxim al atelierului în funcție de câte ore de montaj are, cu lemnul fixat la 40 de unități. Panta fiecărei porțiuni este prețul umbră al orelor pe acel interval.

05001.0001.5002.000102030405060Ore de montaj disponibileProfit maxim (lei)profit maxim20 de ore30 de ore: 1300 lei40 de ore
Până la 20 de ore, fiecare oră aduce 50 de lei (se fac doar mese). Între 20 și 40 de ore, fiecare oră aduce 30 de lei, prețul umbră din tabelul simplex. Peste 40 de ore, lemnul se termină și orele în plus nu mai aduc nimic.
Vezi datele ca tabel
Profitul maxim în funcție de orele de montaj
SerieOre de montaj disponibileProfit maxim (lei)
profit maxim00
profit maxim201.000
profit maxim401.600
profit maxim601.600
20 de ore201.000
30 de ore: 1300 lei301.300
40 de ore401.600

Încearcă să calculezi panta porțiunii din mijloc: (1600−1000):(40−20)=600:20=30(1600 - 1000) : (40 - 20) = 600 : 20 = 30 de lei pe oră. Concluzie: prețul umbră este panta profitului maxim și rămâne același doar pe un interval; dincolo de el, altă resursă devine limita.

Al doilea grafic arată problema duală a antreprenorului. Zona colorată conține perechile de prețuri (u, v) pe care atelierul le acceptă, iar în vârfuri este scrisă suma totală plătită.

012,52537,550102030405060Preț pe oră (u, lei)Preț pe unitatea de lemn (v, lei)masă: u + 2v = 50scaun: u + v = 401600 lei1300 lei (minim)1500 lei
Restricțiile u + 2v ≥ 50 (masa) și u + v ≥ 40 (scaunul) lasă o zonă deschisă în sus și la dreapta. Costul total 30u + 40v este minim, 1300 de lei, în vârful (30, 10): 30 de lei pe oră și 10 lei pe unitatea de lemn.
Vezi datele ca tabel
Problema duală: prețurile resurselor
SeriePreț pe oră (u, lei)Preț pe unitatea de lemn (v, lei)
masă: u + 2v = 50025
masă: u + 2v = 50500
scaun: u + v = 40040
scaun: u + v = 40400
prețuri acceptate (vârf)040
prețuri acceptate (vârf)3010
prețuri acceptate (vârf)500
prețuri acceptate (vârf)600
prețuri acceptate (vârf)6050
prețuri acceptate (vârf)050
1600 lei040
1300 lei (minim)3010
1500 lei500

Încearcă să verifici vârful (30, 10): 30+2×10=5030 + 2 \times 10 = 50 și 30+10=4030 + 10 = 40, deci ambele restricții sunt îndeplinite la limită, la fel cum în primală ambele resurse se foloseau integral. Concluzie: costul minim al dualei, 1300 de lei, este egal cu profitul maxim al atelierului.

Aprofundare

Demonstrația dualității slabe

Fie x un plan admisibil al atelierului și u o pereche de prețuri acceptată (ATu≥cA^T u \ge c, u≥0u \ge 0). Atunci:

Z=cTx≤(ATu)Tx=uT(Ax)≤uTb=WZ = c^T x \le (A^T u)^T x = u^T (A x) \le u^T b = W

Prima inegalitate vine din faptul că fiecare produs valorează, la prețurile u, cel puțin cât profitul lui (iar x≥0x \ge 0); a doua, din faptul că planul nu folosește mai mult decât resursele disponibile (Ax≤bAx \le b), iar prețurile sunt pozitive. Exemplu: u=0u = 0 și v=40v = 40 este o ofertă acceptată, cu W=1600W = 1600, deci niciun plan nu poate aduce peste 1600 de lei. Când ambele inegalități devin egalități, adică exact în condițiile ecarturilor complementare, Z=WZ = W și ambele soluții sunt optime.

Costul redus: merită un produs nou?

Atelierul se gândește să facă și rafturi: un raft cere 2 ore și 2 unități de lemn și aduce 70 de lei profit. La prețurile umbră, resursele unui raft valorează 2×30+2×10=802 \times 30 + 2 \times 10 = 80 de lei. Diferența 70−80=−1070 - 80 = -10 lei se numește cost redus: un raft ar aduce cu 10 lei mai puțin decât ar aduce aceleași resurse folosite la mese și scaune. Rafturile nu merită fabricate, decât dacă profitul unui raft ar crește peste 80 de lei.

Excepții și nuanțe

  • Prețul umbră este valabil doar pe intervalul din analiza sensibilității. Pentru schimbări mari, trebuie rezolvată din nou problema.
  • Prețul umbră nu este prețul de piață al resursei. Este valoarea ei pentru această firmă, cu planul ei; altă firmă poate avea alt preț umbră pentru aceeași resursă.
  • Când mai mult de două restricții trec prin vârful optim (caz numit degenerat), prețul umbră poate fi diferit la creșterea și la scăderea resursei.
  • Programele de calcul tabelar (de exemplu, Solver din Excel) afișează prețurile umbră și intervalele lor într-un „raport de sensibilitate”.

Un caz real: prețurile lui Kantorovici

În lucrările lui despre planificarea producției, Leonid Kantorovici a observat că soluția problemei duale dă fiecărei resurse o valoare, pe care a numit-o „evaluare obiectiv determinată”. În economia planificată a URSS, ideea a fost primită cu suspiciune, pentru că aceste valori semănau cu prețurile și chiriile unei economii de piață. Cartea lui din 1959, „Cea mai bună utilizare a resurselor economice”, a ajutat la acceptarea metodelor, pentru care a primit în 1965 Premiul Lenin, iar în 1975 a primit Premiul Nobel pentru economie, împreună cu Tjalling Koopmans. Astăzi, aceeași idee stă la baza prețurilor din unele piețe de energie electrică, unde prețul energiei într-un nod al rețelei este prețul umbră al restricției care cere ca oferta să acopere consumul în acel nod.

Quiz

Verifică ce ai înțeles. Poți reîncerca oricând.

1. Ce arată prețul umbră al unei resurse?

Alege o singură variantă.

2. Primala este o problemă de maximizare cu restricții „≤”. Cum este duala ei?

Alege o singură variantă.

3. Dacă la planul optim rămân nefolosite 5 kg dintr-o materie primă, prețul umbră al acelei materii prime este 0.

Alege o singură variantă.

4. Profitul maxim al unei firme este 1300 de lei, iar prețul umbră al orelor de muncă este 30 de lei. Ce profit maxim are firma dacă primește 2 ore în plus (în intervalul de valabilitate)?

Scrie un număr.

lei

5. Prețul umbră al lemnului este 10 lei pe unitate. Un furnizor oferă lemn suplimentar cu 14 lei pe unitate. Ce ar trebui să facă firma?

Alege o singură variantă.

6. Duala unei probleme are vârfurile (0, 40), (30, 10) și (50, 0), iar funcția-obiectiv W = 30u + 40v trebuie minimizată. Care este valoarea minimă a lui W?

Scrie un număr.

7. Planul optim (10 mese, 20 de scaune) se află la intersecția restricțiilor x + y ≤ 30 și 2x + y ≤ 40. Scaunul aduce 40 de lei. Pentru ce profit al mesei NU mai rămâne optim acest plan?

Alege o singură variantă.

8. Prețurile umbră sunt 30 de lei pe oră și 10 lei pe unitatea de lemn. Un produs nou cere 2 ore și 2 unități de lemn. Ce profit minim, în lei, ar trebui să aducă pentru ca fabricarea lui să nu scadă profitul total?

Scrie un număr.

lei