Matematici Financiare

Problema complementara, formulare si definire a conceptelor

Teoria complementaritatii este deosebit de importanta, deoarece unifica problemele din domenii foarte diferite cum ar fi: programarea matematica, teoria jocurilor, teoria echilibrului economic, teoria echilibrului in probleme de transport, etc.

In mod obisnuit,teor 19519i816t ia omplementara este privita ca un capitol de programare matematica. De exemplu,codul ei in clasificarea AMS(American Mathematical Society) este 90C33. Codul 90XXX este specific economiei-matematice, cercetarilor operationale si jocurilor, in timp ce 90CXX este specific programarii matematice. Se poate concluziona ca problema poate fi inclusa in clasa problemelor de optimizare si a celor de echilibru.

Problema complementara acopera domenii foarte profunde, interesante si dificile ale matematicii si economiei. Ea stabileste in acelasi timp un teren foarte propice cercetarii, realizand interconexiuni intre capitole importante din economie si analiza neliniara.

Numita initial ' problema compozita', 'fundamentala' sau de 'pivotare complementara', problema a fost privita pentru prima oara, ca o problema de sine statatoare de catre W.S. Dorn. In 1963, Dantzing si Cottle generalizeaza rezultatele lui Dorn, iar in 1965 Lemke propune PC ca o metoda de rezolvare a jocurilor.

In mod cert, unul din primele articole semnificative referitoare la importanta aplicatiilor PC in inginerie este cel al lui A.W. Ingleton.

Din punct de vedere matematic, problema complementara liniara(PCL) se poate formula astfel: fiind data functia , sa se determine asa incat:

unde f(x)=q+Mx,

Generic, problema PCL va fi definita de perechea (q, M).

Notand w=q+Mx, conditia (3) devine si astfel problema PCL va fi reformulata:

In acest caz, variabilele si formeaza o pereche complementara in sensul ca cele doua variabile sunt complementare una alteia( daca una este nula, atunci cealalta este in mod obligatoriu nenula).

Vectorii si din sunt aproape complementari in raport cu indicele daca pentru orice.

O forma extinsa a PCL(q,M), un scalar si un vector d>0, consideram PCL extinsa , unde :

, (7)

Se pune problema existentei unei solutii a PCL extinse, adica a unui vector si a unui scalar astfel incat:

Se observa imediat ca daca este o solutie pentru , cu , atuncieste o solutie a PCL(q, M).

Model de echilibru regional

Modelele de echilibru regional sunt cele care studiaza comportamentul in spatiu al agentilor economici.Procesele economice sunt analizate din punctul de vedere al dispunerii lor spatiale.

Modelele clasice se bazeaza pe ipoteza 'punctualitatii' economiei si ignora, de obicei, aspectul situarii geografice a agentilor si pietelor. Problemele esentiale ale analizei economice ca, de exemplu, ce trebuie produs, cum trebuie produs, pentru cine trebuie produs, sunt studiate fara a lua in calcul distantele, costurile de transport sau alte neajunsuri generate de dimensiunea pietei. Aceste imperfectiuni sunt inlaturate cu ajutorul modelului regional.

Avand in vedere ca activitatile economice sunt derulate nu doar in timp, ci si in spatiu, modelele regionale introduc acest ultim concept. Notiunea de regiune defineste astfel un subsistem spatial al unei economii.

Inca din 1952, Samuelson sugera formularea unor probleme de optimizare si echilibru pentru piete separate spatial, care pot fi privite ca noduri ale unei retele in care costurile de transport sunt luate in mod explicit in considerare.

Modelul de echilibru spatial prezentat in continuare poate fi redus la o optimizare, dar care va fi detaliat ca o problema complementara. Acest model este de fapt o generalizare a problemei de transport.

Presupunem ca exista doua sau mai multe regiuni intre care se schimba produse omogene. Sistemul considerat este unul interconectat cu m surse si n destinatii.

La fiecare sursa este disponibil un singur tip de produs care este solicitat in diferite cantitati(posibil nule) la destinatii. Dupa cum vom vedea, aceasta presupunere nu restrange generalitatea modelului, deoarece el poate fi aplicat atat in cazul unui singur produs, dar si in cazul mai multor produse.

In vederea realizarii modelului matematic, vom introduce urmatoarele notatii:

(vector oferta)

(vector cerere sau vector al consumurilor pentru cele n destinatii)

(costul unitatii de produs la sursa I)

(vector al costurilor la sursa)

( costul unitatii de produs la destinatia j)

( vector al costurilor la destinatie)

(cantitatile de produse vehiculate intre surse si destinatii)

(cost unitar de transport de la sursa I la destinatia j)

(vector al preturilor de piata la surse)

(vector al preturilor de piata la destinatie)

(matrice cu toate elementele nule, excptand elementele de pe pozitia i din coloanele (i-1)n+k, i=1,m j=1,n , care sunt 1)

(matrice cu toate elementele nule, excptand elementele de pe pozitia j din coloanele j+nk, k=1,m-1 j=0,n-1 , care sunt 1).

Rezolvarea problemei de echilibru consta in determinarea vectorilor astfel incat:

(i)

(costul unui produs la sursa este mai mare sau egal decat pretul de piata la sursa respectiva)

(ii)

(daca oferta este strict pozitiva, atunci pretul de piata de la sursa i este egal cu costul produsului de la sursa respectiva)

(iii)

(costul unui produs la destinatie este mai mic sau egal decat pretul de piata la destinatia respectiva)

(iv)

(daca cererea este strict pozitiva, atunci pretul de piata de la destinatia j este egal cu costul produsului de la destinatia respectiva)

(v)

(diferenta dintre preturile de piata la destinatii si surse este mai mica sau egala cu costul unitar de transport)

(vi)

(daca fluxul este strict pozitiv, atunci diferenta dintre preturile de piata este egala cu costurile de transport)

(vii)

(oferta este mai mare sau egala cu cantitatea de produs transportata din regiune)

(viii)

(daca pretul de piata la sursa i este strict pozitiv, atunci intreaga cantitate de produs va fi transportata la acea sursa)

(ix)

(cererea este mai mica sau egala cu cantitatea de produs intrata la fiecare destinatie)

(x)

(daca pretul de piata la destinatia j este strict pozitiv, atunci este egala cu intreaga cantitate de produs adusa in regiune)

(xi)

Observatii:

In cazul mai multor produse, trebuie rezolvate mai multe probleme de acest tip( egal cu numarul de produse) in care sursele ca si destinatiile pot fi identice, din punct de vedere fizic, dar sa corespunda unor produse diferite.

Preturile de piata sunt exogene regiunilor considerate.

Daca se obtine o problema de transport 'clasica', fiind variabile duale( preturi umbra).

Consideram urmatoarea problema de transport:

Gasim problema duala asociata:

(P)   (D)

Conform teoremei ecarturilor complementare, la un cuplul de probleme duale:

(P)   (D)

, sunt solutii optime ale problemelor daca si numai daca si .

In aceste conditii, problema de echilibru devine:

(P) (D)

Restrictiile in acest caz devin:

(i)       

(ii)    

(iii)

(iv)

(v)

(vi)

(vii)

(viii)

(ix)

(x)

(xi) .

Deoarece , primele 4 conditii devin de superflue.

Problema determinarii echilibrului in acest model este echivalenta cu urmatoarea PC:

Sa se determine astfel incat:

unde ; .

Daca functiile sunt integrabile, adica sunt gradientii

, atunci conditiile Kuhn-Tucker se vor scrie:

Conditiile de optim vor fi:

.

Cazul integrabil este tratat practic ca o problema de programare patratica.

Pentru cazul neintegrabil, cand problema de echilibru corespunde unei probleme de programare matematica.

Exemple.

1.O problema de optimizare a activitatilor de transport

Doua fabrici de conserve Fi unde i = (1,2), aprovizioneaza trei unitati comerciale engros Cj unde j = (1, 2, 3) si plateste transportul pe unitatea de conserva, astfel: de la F la cele trei unitati comerciale cu 200, 250, 300 lei, iar de la F2 la cele trei centre cu 400, 200 si 100 lei.

În fabrica F se realizeaza 40% din întreaga cantitate, iar în F Conform necesitatilor, unitatile comerciale Cj absorb 20%, 30%, 50% din productia de conserve.

Se cere sa se gaseasca un plan de repartitie a produsului fabricat în Fi unde i = (1,2), astfel încât costul total de transport sa fie minim.

Pentru rezolvare se formeaza în prealabil planul de transport conform datelor din problema.

Grafic, planul de transport poate arata ca în figura urmatoare:

C1

F1

F2

C3

C2

În continuare, se noteaza cu Xij cantitatea de produs transportata de la F , F la cele trei centre. Ţinând seama de restrictiile problemei se poate scrie urmatorul sistem de ecuatii:

Legenda:

F - reprezinta fabrica

C - reprezinta centrul engros X + X + X X + X + X

X + X

X + X

X + X

Xij 0 (i = 1,2 ; j = 1,2,3)

Se ia în considerare ca întreaga cantitate de conserve produsa în cele doua fabrici F1, F2 este transportata la cele trei centre (C1, C2, C3).

Functia de eficienta, care reprezinta costul total al transportului este:

f(min) = 200X + 250X + 300X + 400X + 200X + 100X

Din sistemul de egalitati se pot exprima necunoscutele Xij, în functie de X si X , astfel:

X = 20 - X

X = 30 - X

X = 40 - X - X

X = 60 - (30 - X ) - (20 - X ) = 10 + X + X

Cu aceste valori, functia de eficienta f(min) devine:

f(min) = - 400 X - 150X

Daca se noteaza X = X si Y = X si tinând seama de conditia de nenegativitate (Xij 0) vom obtine:

40 - X - Y 0 X + Y - 40 0

20 - X 0 X 20

30 - Y 0 sau Y 30

X + Y + 10 0 X + Y + 10 0

X 0 ; Y 0

S-a ajuns astfel la o problema cu doua necunoscute.

Pentru reprezentarea grafica se stabilesc dreptele:

y (D ): X + Y - 40 = 0

(D ): X + Y + 10 = 0

(D X = 20

(D Y = 30

B Functia de eficienta se poate scrie sub forma:

0 (D₃) x unde

Coordonatele punctului B fac minima functia obiectiv B

Solutia problemei prevede urmatorul plan de transport:

Rezulta ca fabrica F1 trebuie sa trimita cantitatea în mod egal la centrele C1 si C2, iar F2 va trimite produsele numai la centrele C2 si C3.

Functia de eficienta va fi :

f(min) =

2.Dualitatea problemelor de optimizare

Sa presupunem ca o problema de optimizare care se poate rezolva cu ajutorul programarii liniare cere determinarea a "u" numere x_j unde pentru care functia este maxima , cu urmatoarele restrictii :

Matricea sistemului M poate fi scrisa astfel :

In baza acelorasi date se poate construi o noua problema , numita problema duala a celei propuse . Fie "m" variabile y₁ , y₂ , ........y_m , care sa corespunda celor "m" inecuatii ale multimii M .

Problema duala are ca scop gasirea minimului functiei în conditiile :

Se constata ca matricea sistemului M₁ scrisa sub forma

este transpusa matricii A

În amândoua problemele apar aceleasi constante c_j , a_ij , b_i, în schimb. numarul variabilelor x_j, y_i se schimba de la "n" la "m" , iar numarul restrictiilor de la "m" la "n" . Cele doua probleme formeaza împreuna o uniune de probleme duale .

Pentru simplificarea prezentarii , cele doua probleme se pot exprima sub forma matriciala astfel:

a - Problema primara

f(max)= maxC x cu restrictiile AxB , x0

unde

, si

b - Problema duala

g(min)= min B y în conditiile A_1yC , y0 unde

.

Pentru formularea problemei duale este bine sa se întocmeasca urmatorul tabel :

Matricea generala a problemei duale.

Tabel nr.

Problema primara se realizeaza pe linii , iar cea duala pe coloane .

Între doua probleme de optimizare prin programare liniara, care formeaza un cuplu de probleme duale, exista legaturi strânse de interdependenta a solutiilor lor, formulate de teorema fundamentala a dualitatii , care arata ca pentru orice cuplu de probleme duale este posibila numai una dintre urmatoarele trei situatii :

Daca ambele probleme au solutii de realizare, atunci ambele probleme au solutii optime si valorile functiilor obiectiv coincid, adica max C'X = min B'Y

Daca problema primara nu are solutii realizabile, cea duala are un optim infinit

Nici una dintre cele doua probleme nu are solutii realizabile.

Avantajele dualitatii problemelor de optimizare, care se pot rezolva prin programare liniara, se pot sintetiza astfel:

transformarea minimului unei functii liniare într-un maxim si invers;

se poate alege un program care solicita calcule mai putine;

rezultatele pot fi verificate.

Pentru exemplificare se ia o problema de organizare a productiei din cadrul unei sectii a unei unitati economice agricole.

Resursele R_j unde j = (1,2) coeficientii tehnologici a_ij, stocurile din fiecare resursa a profitului pe unitatea de produs sunt trecute în tabelul urmator:

Se urmareste determinarea numarului de produse din fiecare sortiment astfel încât profitul total sa fie maxim.

Aceasta este problema primara care, matematic se exprima astfel:

f(max) =max(5x+3y)

în care :

x , y reprezinta numarul de produse de fiecare fel .

f - profitul total .

Prin rezolvarea sistemului rezulta : x=3 si y=2 iar f(max)=21 .

Formarea problemei duale urmareste determinarea preturilor unitare p₁ si p₂ ale resurselor R_j în asa fel ca , date fiind stocurile din fiecare resursa si profitul pe fiecare unitate de produs , valoarea cheltuielilor sa fie cât mai mica posibil .

Folosind datele din tabelul de mai sus si notând cu C_h valoarea cheltuielilor totale putem scrie : minC_h = min(5s₁+8s₂) unde s₁ , s₂ reprezinta stocurile de resurse . Asa cum s-a aratat , profiturile sunt de 5 si respectiv 3 unitati valorice pentru cele doua produse .

Sistemul problemei duale se poate scrie astfel :

Solutiile problemei duale sunt :

s₁=1 ; s₂=2 .

Se obtine astfel minim C_h = 21 unitati valorice .

Prin acest exemplu se constata importanta programului optim dual .

Batten, D.F., Fischer, M.M., Hewings, G.J.D., Nijkamp,

P., Snickamp, F., Advanced in Spacial Science, Springer - Verlag, Berlin, New York 1996

Cottle, R.W., Pang,J.S., Stone, The liniar Complementarity Problem, Academic Press, Inc.,1992

Irwin, C.L., Yang, C.W., Iteration and Sensitivity of a Spatial Equilibrium Problem with Supply and Demand Functions, Operations Research, vol. 30, 1982

Siebert, H., Regional Economic Growth: Theory and Policy, International Textbook Company, 1968

Sommerschuh, J.. Properties of the general quadratic optimization problem and the corresponding linear complementary problem, Optimization, 18,1987