Modele economico-matematice celebre

E cunoscut că Premiul Nobel nu se oferă pentru cercetări în domeniul matematicii. Totuşi, de-a lungul anilor mai mulţi matematicieni au fost distinşi cu acest premiu, pentru aplicarea matematicii în alte domenii. Leonid Kantorovich este unul dintre matematicienii căruia i-a fost decernat Premiul Nobel în 1975, împreună cu Tjalling Koopmans, “Pentru contribuţia acestora la teoria folosirii optimale a resurselor”. Precum am menţionat în articolul “Iniţiere în programarea matematică” denumirea de programare matematică provine de la primele cercetări legate de elaborarea prin metode matematice a programelor optime de activitate a agenţilor economici în baza modelelor matematice. Prezint în continuare câteva exemple de situaţii/fenomene economice, devenite deja clasice, pentru care se construiesc modele matematice – probleme de programare matematică.

Problema repartizării eficiente a resurselor limitate

Această problemă e numită şi problemă a asortimentului optim, şi problemă a planificării producţiei. Pentru claritate se consideră la început un exemplu.

Exemplul 1 (problemă liniară). Întreprinderea produce garnituri de mobilă de două tipuri. Producerea unui număr cât mai mare de garnituri e limitată de resursele disponibile de scândură calitativă şi de timpul prelucrării ei cu ajutorul unor maşini automate. Se ştie că la producerea unei garnituri de tipul întâi se utilizează 4 m3 de scândură, iar de tipul doi 5 m3, timpul de prelucrare la maşinile automate a scândurii utilizate pentru o garnitură de fiecare tip fiind egal, corespunzător, cu 15 min şi 30 min. Săptămânal  întreprinderea  dispune de 2100 m3 de scândură, iar maşinile automate pot lucra  în total nu mai mult de 150 de ore.

Câte garnituri de mobilă  de fiecare tip trebuie să producă săptămânal  întreprinderea cu scopul de a maximiza beneficiul total, dacă beneficiul de la comercializarea unei garnituri de fiecare tip  este egal, respectiv, cu 21 unităţi monetare (u.m.) şi 40 u.m?

Introducem notaţiile: x1, x2 – numărul de garnituri de tipurile 1, 2, produse săptămânal. E clar că beneficiul săptămânal de la comercializarea mobilei va fi

f(x)=21 x1 + 40 x2.__________(1)

Restricţiile pentru resurse sunt:

4 x1 +5 x2 2100,__________(2)
1/4 x1 + 1/2 x2 150,_______(3)
x1 ≥ 0, x2 ≥ 0._____________(4)

Pproblema de programare matematică obţinută cere maximizarea beneficiului (1)  în restricţiile (2)-(4). Situaţia din exemplul 1 poate fi generalizată.

Întreprinderea produce n tipuri de produse, utilizând pentru aceasta  m tipuri de resurse (capital, materii prime, forţă de muncă, timp etc.). Cantitatea de resursă i disponibilă  în decursul perioadei examinate de timp (săptămână, lună, an ec.) este egală cu bi, (i=1,…,m). E cunoscut că la fabricarea unei unităţi de produs j  întreprinderea utilizează aij unităţi de resursă i (i=1,…,m, j=1,…,n), iar beneficiul obţinut de la valorificarea unei unităţi de produs j este egal cu cj (j=1,…,n) unităţi monetare.

Să se determine cantităţile de produse ce urmează a fi fabricate  în perioada de timp dată,  încât beneficiul total să fie maxim.

Dacă notăm cu xj (j=1,…,n) cantitatea de produs j fabricat pe parcursul  întregii perioade de timp, atunci f(x)=c1x1+c2x2 +…+cnxn este beneficiul total obţinut de la valorificarea asortimentului x1, x2, …, xn;
ai1x1+ai2x2 +…+ainxn este cantitatea de resursă i utilizată la producerea asortimentului x1, x2, …, xn, cantitate ce nu poate depăşi bi.

În aceste notaţii, problema iniţială, numită problemă de repartizare eficientă a resurselor limitate, poate fi scrisă:

f(x)=c1x1+c2x2 +…+cnxn → max,_______(5)
ai1x1+ai2x2 +…+ainxn bi, i=1,…,m,____(6)
xj ≥ 0, j=1,…,n.______________________(7)

Remarcă. În afară de restricţiile pentru resurse,  în condiţiile problemei şi, respectiv, în modelul ei matematic mai pot fi restricţii de sortiment, de completare etc.

Menţionăm că (5)-(7) este o problemă de programare liniară. Dacă introducem notaţiile:

x=( x1, x2, …, xn)T,
c=( c1, c2, …, cn)T,
b=( b1, b2, …, bm)T,
A= [aij ]i = 1,…m; j = 1,…,n

atunci (5)-(7) poate fi scrisă şi în formă matriceală:

f(x)=cT x → max,
Ax ≤ b,
x ≥ 0.

Problema dietei

Mai are şi denumirile: problema nutriţiei, problema  meniului optim, problema amestecului.

Din considerente de sănătate orice fiinţă trebuie să consume zilnic necesarul biologic constituit din cantităţi minime de anumite substanţe/principii nutritive: proteine, vitamine, glucide, hidrocarburi etc., care se conţin în anumite cantităţi în diferite produse alimentare. Problema dietei constă în asigurarea necesarului biologic cu cheltuieli minime.

Fie:

n – numărul de produse alimentare;
m - numărul de principii nutritive;
bi – cantitatea de principiu nutritiv i ce intră în necesarul biologic (i=1,…,m);
aij - cantitatea de principiu nutritiv i ce se conţine într-o unitate de produs j, (i=1,…,m, j=1,…,n);
cj – costul unei unităţi de produs alimentar j,( j=1,…,n);
xj – cantitatea de produs alimentar j, (j=1,…,n), care urmează să fie întrebuinţat zilnic.

În notaţiile de mai sus, modelul matematic al problemei dietei are forma:

f(x)=c1x1+c2x2 +…+cnxnmin,_______(8)
ai1x1+ai2x2 +…+ainxn bi, i=1,…,m,____(9)
x 0, j=1,…,n. _____________________(10)

Dacă utilizăm notaţiile matriceale, atunci (8)-(10) se scrie:

f(x)=cT x → min,
Ax ≥ b,
x ≥ 0.

Problema de transport

Marfa omogenă, stocată în m depozite în cantităţile a1, a2,…, am, urmează a fi transportată la n consumatori care solicită cantităţile b1, b2,…, bn, corespunzător. Se presupune că disponibilul total este egal cu cererea totală. Fiind cunoscute tarifele de transport cij, (i=1,…,m, j=1,…,n), să se determine planul de transport care asigură cheltuieli minime.

Dacă notăm cu xij cantitatea de marfă ce urmează a fi transportată de la depozitul i la consumatorul j, atunci:

xi1+xi2+…+xin reprezintă volumul de marfă ce urmează a fi transportată de la depozitul i tuturor consumatorilor;
x1j+x2j+…+xmj reprezintă volumul de marfă ce urmează a fi primită de consumatorul j de la toate depozitele;
c11 x11+c12 x12+…+c1n x1n + c21 x21+…+cmn xmn reprezintă cheltuielile totale necesare pentru realizarea planului de transport xij (i=1,…,m, j=1,…,n).

În asemenea notaţii, problema de transport ia forma:

f(x)= c11 x11+c12 x12+…+c1n x1n + c21 x21+…+cmn xmn → min,___(11)
xi1+xi2+…+xin = ai,  i=1,…,m,_______________________________(12)
x1j+x2j+…+xmj = bj, j=1,…,n,________________________________(13)
xij ≥ 0,  i=1,…,m, j=1,…,n. ___________________________________(11)

Dacă notăm:

C= [cij ]i = 1,…m; j = 1,…,n
_____??| I O … O |
_____??| O I … O |
Amxn = |     …     |
______?| O O … I |
______?| E E … E |

unde

I = (1, 1,…, 1),
O = (0, 0,…, 0),
Enxn - matrice unitate,
x = (x11, x12,…, x1n, x21, x22, …, xmn)T,
c = (c11, c12,…, c1n, c21, c22, …, cmn)T,
b = (a1, a2,…, am, b1, b2, …, bn)T,

atunci (11)-(13) se scrie şi sub formă matriceală:

f(x)=cT x → min,
Ax = b,
x ≥ 0.

Exemplul 2 (problemă neliniară). Întreprinderea produce recipiente cilindrice de volum unitar din materie primă costisitoare (foi metalice). Pentru a asigura cheltuieli minime, se cer determinate dimensiunile recipientului de acelaşi volum unitar, dar de suprafaţă minimă.

Dacă notăm: r – raza bazei, h – înălţimea recipientului, atunci obţinem următorul model:

s(r, h) = 2πr2 + 2πrh → min,____(14)
πr2h = 1,__________________(15)
r, h ≥ 0.____________________(16)

Problema (14)-(16)  poate fi rezolvată cu uşurinţă.  Într-adevăr, din (15) reiese că h=1/(πr2). Înlocuind această expresie pentru h în (14), obţinem o funcţie de o singură variabilă s(r, h)=s(r)=2πr2+2πr/(πr2)=  2(πr2+ 1/r) şi o problemă de optimizare necondiţionată. E cunoscut că în punctele de optim derivata funcţiei în raport cu r trebuie să fie nulă. Deci, punctele critice ale funcţiei sunt soluţii ale ecuaţiei: s′(r)=4πr – 2/r2=0. De unde, r*=3√( 1/(2π)).

Se observă că pentru valorile variabilei r mai mici decât r* derivata este negativă, iar pentru valori mai mari decât r* este pozitivă. Rezultă că r* este punct de minim şi dacă revenim la problema  iniţială, obţinem soluţia optimă:
r* =3√ (1/( 2π));  h* =3√  (4/π); s* = 3 3√ (2π).

De reţinut că exemplul 2 a fost rezolvat prin metode tradiţionale, bine cunoscute din analiza matematică. Se observă însă că acelaşi procedeu nu poate fi utilizat la rezolvarea nici a exemplului 1, nici a celorlalte probleme de programare liniară construite în acest paragraf.  Într-adevăr, deoarece funcţia obiectiv este liniară, fiecare dintre derivatele parţiale este egală cu coeficientul respectivei variabile,  adică valoarea derivatei este constantă. Ar fi o trivialitate ca toţi coeficienţii funcţiei obiectiv să fie egali cu zero concomitent.

Deci în interiorul domeniului de puncte admisibile optimuri nu pot fi. Ele se pot afla doar pe frontieră. Punctele frontierei, în schimb, nu pot fi explorate, deoarece derivatele sunt constante. Aşadar, soluţionarea problemelor de programare liniară necesită metode speciale.

Solicită metode speciale şi alte probleme.  În calitate de exemplu poate servi următoarea problemă, formulată pentru prima dată de profesorul Universităţii California Harry Markowitz, laureat al premiului Nobel în economie în anul 1990 împreună cu Merton Miller şi William Sharpe “pentru lucrul de pionierat în teoria economiei financiare”.

Problema portofoliului de investiţii.

La bursa de valori se vând n tipuri de acţiuni. Conform datelor unui eşantion de volum nl (l – numărul de luni cuprinse de sondaj) în luna k acţiunile de tipul j au adus un venit de pj(k) procente. Se aşteaptă că fiecare acţiune de tipul j va aduce în medie un venit de pj procente.

În baza datelor de eşantion se calculează matricea de covariaţie a veniturilor  C=[cij ]i,j=1,…,n.

Agentul economic planifică o investiţie în hârtii de valoare a unei anumite sume de bani, proporţiile de procurare dorind să le aleagă în aşa mod încât să-şi asigure un venit maxim la un risc minim.

Dacă notăm cu xj partea din activ investită în acţiunile de tipul j, atunci ∑j=1n pj xj reprezintă venitul aşteptat de la portofoliul x1, …, xn, iar ∑j=1ncij xi xj reprezintă valoarea riscului.

Problema respectivă de programare matematică se formulează în felul următor:

j=1n pj xj → max,________(17)
i=1nj=1ncij xi xj → min,__(18)
j=1n xj = 1,_____________(19)
xj ≥ 0, j=1,…,n.___________(20)

(17)-(18) reflectă scopurile investorului: maximizarea venitului (17) şi minimizarea riscului (18). Portofoliul x1, … , xn de hârtii de valoare e considerat eficient dacă nu există alte portofolii cu venit mai mare şi risc mai mic, cu venit mai mare şi acelaşi risc sau cu risc mai mic şi acelaşi venit.

Problemele de atare tip, în care se optimizează concomitent valorile ale mai multor funcţii obiectiv, se numesc probleme de optimizare multicriterială. Se înţelege că ele solicită şi tratări speciale.

În încheiere vom menţiona  că necesităţile de metode netradiţionale de soluţionare şi de noi abordări teoretice sunt dictate, în mare măsură, şi de complexitatea domeniului. Ca o confirmare a acestei afirmaţii ne poate servi faptul că multe dintre problemele bine cunoscute şi unanim recunoscute ca “pietre unghiulare” în matematică se formulează şi se cercetează în cadrul programării matematice.

Teorema lui Pierre Fermat, datată din 1637, despre imposibilitatea rezolvării în numere întregi a ecuaţiei:

xn + yn =zn,

unde n ≥ 3, demonstrată (pe 150 de pagini) abia în 1994 de către Andrew Wiles, profesor al Universităţii Princeton, este echivalentă cu următoarea problemă de programare matematică:

(xn + yn – zn)2 + M (1 – cos 2πx)2 + M (1 – cos 2πy)2 + M (1 – cos 2πz)2 + M (1 – cos 2πn)2 → min,

n ≥ 3,  x, y, z ≥ 1, M » 0 este un coeficient de penalizare.

O eventuală enumerare a tuturor problemelor de aşa natură practic e imposibilă. Totuşi atât problemele de mai sus, precum şi altele cum sunt problema satisfiabilităţii formelor booleene din logica matematică, problema izomorfismului a două grafe din teoria grafelor etc., probleme care se formulează şi se cercetează ca probleme de programare matematică, sunt o dovadă în plus a importanţei programării matematice şi a conexiunii ei cu domeniile contemporane de cercetări şi aplicaţii.

Sursa: V. Ungureanu, Programarea Matematică, Chişinău, USM, 2001.

P.S. Câteva probleme gasite din Internet, cu autori necunoscuti, pentru verificare si eventuale corectii a lor…

1. O maşină care lucrează 25 de ore pe săptămână produce trei articole. Beneficiul obţinut în urma vânzării acestor articole este de 40 lei/buc pentru primul articol, respectiv 120 lei/buc pentru al doilea articol şi 30 lei/buc pentru ultimul articol. Într-o oră maşina poate realiza 50 buc din primul articol sau 25 buc din al doilea articol sau 75 buc din al treilea articol. Cererea săptămânală nu depăşeşte 1000 buc din primul articol, 500 buc din al doilea articol, 1500 buc din al treilea articol. Cum trebuie repartizată producţia celor trei articole pentru ca întreprinderea să-şi asigure un beneficiu maxim!

2. O fabrică de zahăr trebuie să producă între 1 noiembrie – 28 februarie. Livrările de zahăr se fac lunar, după contract: în noiembrie 20.000 t, în decembrie 30.000 t, în ianuarie 50.000 t şi în februarie 40.000 t. Producţia excedentară a unei luni poate fi livrată luna următoare, suportând cheltuielile de depozitare de 2.000 lei/tonă pe lună. Capacitatea lunară de producţie a fabricii este: 55.000 t în noiembrie, 40.000 t în decembrie, 25.000 t în ianuarie, 50.000 t în februarie. Preţurile de cost sunt: 140.000 lei/tonă în noiembrie, 160.000 lei/tonă în decembrie, 150.000 lei/tonă în ianuarie, 170.000 lei/tonă în februarie.

Să se stabilească nivelul de producţie lunar astfel încât contractele să fie satisfăcute cu cheltuieli minime.

3. Un atelier de construcţii metalice dispune de ţevi cu lungimea de 5m, din care trebuie să taie cel puţin 35 ţevi în lungime de 2m, 25 ţevi de 2,5m şi 10 ţevi de 3m lungime. Cum trebuie procedat astfel ca să se realizeze consumuri minime de material?

2 comments to Modele economico-matematice celebre

Leave a Reply

 

 

 

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

*
Introdu codul de securitate anti-spam din imagine.
Click to hear an audio file of the anti-spam word