Matematici aplicate în economie · Optimizare liniară
Dualitate și analiza sensibilității
Avansat70 min✓ Terminată
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 ;
- un scaun folosește 1 oră și 1 unitate de lemn, deci .
Antreprenorul vrea să plătească în total cât mai puțin, adică . 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 este transpusa matricei A (liniile devin coloane):
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 |
| restricția i de tip „≥” | variabila |
| restricția i de tip „=” | variabila fără restricție de semn |
| variabila | restricția j de tip „≥” |
| variabila fără restricție de semn | restricția j de tip „=” |
| profitul din funcția-obiectiv | termenul liber al restricției j |
| termenul liber | coeficientul lui î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 , și 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: , cu (proteine) și (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, , dar fără ca suplimentele să fie mai scumpe decât furajele care conțin aceleași substanțe: (furajul A) și (furajul B). Din cele două ecuații, și , deci și . Valoarea dualei este 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, . 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: . 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:
A doua relație spune că un produs care se fabrică () aduce exact cât valorează resursele lui la prețurile umbră. Pentru atelier, masa: , exact profitul ei; scaunul: .
Partea 2. Prețurile umbră
Pentru atelier, și :
- 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 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 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ă lei la fiecare oră. Dacă un furnizor cere 15 lei pe o unitate de lemn în plus, nu merită: ar pierde 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 . 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 , orele) și 10 (sub , lemnul). În aceeași linie, sub fiecare produs, apare costul redus:
adică valoarea resurselor consumate de o unitate din produsul j (la prețurile umbră) minus profitul ei. Pentru produsele din planul optim, ; pentru un produs care nu se fabrică, 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 și de lei. Planul nu se schimbă; se schimbă doar profitul total.
- Dacă masa aduce în continuare 50 de lei, scaunul poate aduce între și 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 și , adică și . 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 și , planul rămâne optim cât timp raportul profiturilor stă între rapoartele și 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:
| Produs | Cantitate optimă | Cost redus | Profit pe bucată | Creștere permisă | Scădere permisă |
|---|---|---|---|---|---|
| Mese | 10 | 0 | 50 | 30 | 10 |
| Scaune | 20 | 0 | 40 | 10 | 15 |
| Resursă | Folosit | Preț umbră | Disponibil | Creștere permisă | Scădere permisă |
|---|---|---|---|---|---|
| Ore | 30 | 30 | 30 | 10 | 10 |
| Lemn | 40 | 10 | 40 | 20 | 10 |
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.
Vezi datele ca tabel
| Serie | Ore de montaj disponibile | Profit maxim (lei) |
|---|---|---|
| profit maxim | 0 | 0 |
| profit maxim | 20 | 1.000 |
| profit maxim | 40 | 1.600 |
| profit maxim | 60 | 1.600 |
| 20 de ore | 20 | 1.000 |
| 30 de ore: 1300 lei | 30 | 1.300 |
| 40 de ore | 40 | 1.600 |
Încearcă să calculezi panta porțiunii din mijloc: 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ă.
Vezi datele ca tabel
| Serie | Preț pe oră (u, lei) | Preț pe unitatea de lemn (v, lei) |
|---|---|---|
| masă: u + 2v = 50 | 0 | 25 |
| masă: u + 2v = 50 | 50 | 0 |
| scaun: u + v = 40 | 0 | 40 |
| scaun: u + v = 40 | 40 | 0 |
| prețuri acceptate (vârf) | 0 | 40 |
| prețuri acceptate (vârf) | 30 | 10 |
| prețuri acceptate (vârf) | 50 | 0 |
| prețuri acceptate (vârf) | 60 | 0 |
| prețuri acceptate (vârf) | 60 | 50 |
| prețuri acceptate (vârf) | 0 | 50 |
| 1600 lei | 0 | 40 |
| 1300 lei (minim) | 30 | 10 |
| 1500 lei | 50 | 0 |
Încearcă să verifici vârful (30, 10): și , 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ă (, ). Atunci:
Prima inegalitate vine din faptul că fiecare produs valorează, la prețurile u, cel puțin cât profitul lui (iar ); a doua, din faptul că planul nu folosește mai mult decât resursele disponibile (), iar prețurile sunt pozitive. Exemplu: și este o ofertă acceptată, cu , 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, ș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ă de lei. Diferența 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.