CAMELIA FRIGIOIU

ALGEBR I GEOMETRIEpentru inginerie economica

Galati 2006

ALGEBR LINIAR I GEOMETRIE

3

ALGEBR LINIAR

CAPITOLUL 1 SPAII VECTORIALE

1. Spaii vectoriale Spaiul vectorial este una din cele mai importante structuri matematice, care servete disciplinelor tehnice si economice. Definiia 1.1. Fie K un corp comutativ i 1K elementul su unitate. Un triplet format din: -o mulime nevid V -o lege de compoziie intern, definit pe V, notat aditiv + : V V V

(u, v ) u + v ,-o lege de compoziie extern :KV V

u,vV

(,u) u, urmtoarele axiome:

,vV

se numete spaiu vectorial (liniar) peste K (sau K-spaiu vectorial), dac verific (V1) (V,+) este grup abelian (elementul neutru al acestui grup va fi notat ) (V2) (u + v ) = u + v (V3) ( + ) u = u + u (V4) ( u ) = ( ) u (V5) 1K u = u complex). Elementele unui K-spaiu vectorial se numesc vectori, iar elementele corpului K se numesc scalari.u, v V, K u V, , K

uV , , Ku V

Dac K=R (respectiv K=C) vom spune c V este un spaiu vectorial real (respectiv

4

CAMELIA FRIGIOIU

Propoziia 1.1. afirmaii:

Fie V un K-spaiu vectorial. Atunci sunt adevrate urmtoarele

1) (u - v) = u - v K u, v V 2) ( - ) u = u - v , K u V

3) = 4) 0 k u = 5) (1K ) u = u

K

uVu V

6) dac u = , atunci = 0 K sau u = . Exemple. 1. Spaiul aritmetic K n cu n dimensiuni Fie K un corp comutativ oarecare i nN un numr natural nenul. Vom considera produsul cartezian

Kn =

K 4 244 K K 1 4 .... 3n ori

unde elementele lui Kn sunt de forma ( xi ) = ( x1 , x2 ...xn ) i se numesc n-uple ordonate. Produsul cartezian K n poate fi dotat cu o structur de spaiu vectorial peste corpul K, dac se definesc pe K n : -o lege de compoziie aditiv, intern, prin:( xi ), ( y i ) K n (x i ) + ( y i ) = ( xi + y i )

-o lege de compoziie extern peste K prin:( xi ) K , K (x i ) = (xi ) .

Se verific uor c aceste legi de compoziie determin pe K n o structur de spaiu vectorial peste K. K-spaiul vectorial ( K n ,+, ) se numete spaiul aritmetic (standard) cu n dimensiuni. 2. Mulimea matricelor cu m linii i n coloane, cu elemente reale , formeaz un spaiu liniar real, notat M mxn (R). Operaiile acestui spaiu liniar sunt: adunarea matricelor i nmulirea dintre un numr real i o matrice. 3. Mulimea polinoamelor cu coeficieni compleci, mpreun cu adunarea polinoamelor i nmulirea unui numr real cu un polinom formeaz un spaiu vectorial real,notat C [X ] .

ALGEBR LINIAR I GEOMETRIE

5

4. Mulimea polinoamelor de grad cel mult n, cu coeficieni reali constituie un spaiu vectorial real notat P n [X ] , cu legile de compoziie din exemplul 3. Definiia 1.2. Fie v1 , v2 ...vn V , n vectori din K-spaiul vectorial V i 1 , 2 ... n K .n Vectorul v = 1v1 + 2 v2 + ... + n v n sau v = j v j se numete combinaia liniar a j =1

vectorilor v1 ,..., vn .

2. Subspaii vectoriale (liniare) Fie K-spaiul vectorial V. Definiia 2.1. O submulime nevid W V se numete subspaiu vectorial (liniar) a lui V dac: 1) u, v W 2) K , u Wu+vW u W

Definiia 2.2. O submulime nevid WV se numete subspaiu vectorial (liniar) al lui V dac:

u, v W , , K, u + v W .Observaii 1) Cele dou definiii de mai sus sunt echivalente i deci n aplicaii poate fi verificat oricare dintre ele. 2) Deoarece adunarea vectorilor i nmulirea cu scalari, pe W sunt restricii ale operaiilor din V, atunci W mpreun cu aceste legi de compoziie verific toate axiomele spaiului vectorial. Se poate da o definiie echivalent cu cele de mai sus: Definiia 2.3. WV este subspaiu vectorial a lui V dac i numai dac W este spaiu vectorial peste K n raport cu operaiile din V.

6

CAMELIA FRIGIOIU

Exemple. 1. n orice spaiu vectorial V/K mulimile {} i V sunt subspaii vectoriale ale lui V i se numesc subspaii improprii; oricare alt subspaiu al lui V se numete propriu. 2. n Kn/K, mulimea W={x=(0,x2,x3,,xn), xjK, j=2,,n} este subspaiu vectorial al lui Kn. 3. n spaiul liniar M 2 x 2 (R) /R al matricelor ptratice de ordinul 2, mulimea S a matricelor nesingulare de ordinul 2 (al crui determinant este diferit de 0) nu este subspaiu liniar, deoarece suma a dou matrice nesingulare nu este mereu o matrice nesingular, de exemplu:

1 2 2 1 3 3 A= 3 1 S i B = 0 4 S , A + B = 3 3 S . Teorema 2.1. Dac S este o submulime nevid a spaiului liniar V/K, atunci mulimea tuturor combinaiilor liniare finite formate cu vectori din S este un subspaiu liniar al lui V numit acoperirea liniar a lui S n V sau nfurtoarea liniar a lui S sau subspaiul liniar generat de S i se noteaz L(S) sau . Observaii. 1) S L( S ) , pentru c: oricare ar fi vectorul vjS, j = 1, p , se poate scrie ca o combinaie liniar vj=1vj L(S ) . Se poate demonstra c L(S) este cel mai mic subspaiu vectorial care l conine pe S. 2) Diferite mulimi de vectori din V pot genera acelai spaiu (subspaiu) liniar. De exemplu, mulimile

t tn 1, ,..., , {1,(1-t),...,(1-t)n} i {1,t,t2...,tn} genereaz n! 1!

spaiul vectorial al polinoamelor de grad mai mic sau egal cu n. Teorema 2.2. vectorial V , atunci: 1) mulimea W1 + W2 ={v= v1 + v2 v1 W1 i v 2 W 2 }, numit suma dintre W1 i W2 , este un subspaiu vectorial al lui V. 2) intersecia W1 W2 este un subspaiu vectorial al lui V. Observaie. Reuniunea a dou subspaii vectoriale W1 , W 2 (cu W1W2 i W2W1) nu este ntotdeauna subspaiu vectorial . Dac W1 i W2 sunt dou subspaii vectoriale ale K-spaiului

ALGEBR LINIAR I GEOMETRIE

7

3. Independena liniar i dependena liniar a vectorilor Fie V/K spaiu vectorial. Definiia 3.1. O mulime S de vectori din V se numete sistem de vectori. Definiia3.2. Sistemul de vectori S= {v1 , v 2 ,..., v n } V se numete liniar

independent sau liber (vectorii v1 , v2 ,..., vn sunt liniar independeni) dac orice combinaie liniar nul a vectorilor lui S se obine numai cu toi scalarii nuli. Adic:1v1 + 2 v 2 + K + n v n = i = 0, i = 1, n .

Definiia 3.3. Sistemul de vectori S V se numete liniar dependent sau legat (vectorii v1 ,..., vn sunt liniar dependeni) dac nu este liber, adic exist n scalari i , i = 1, n nu toi nuli, astfel nct combinaia liniar a vectorilor lui S cu aceti scalari s fie nul. Teorema 3.1. Sistemul de vectori S = {v1 , v 2 ,..., v n } este liniar dependent dac i numai dac unul din vectori este o combinaie liniar a celorlali vectori din S. A stabili natura unui sistem de vectori nseamn a studia dac vectorii sunt liniar dependeni sau independeni. Exemplu. S se stabileasc natura sistemului de vectori S din

R4 ,

unde

S = {v1 , v 2 , v3 }, v1 = (1,1,0,1); v 2 = (-1,2,1,1); v 3 = (0,1,1,0).Fie 1 , 2 , 3 scalari din R astfel nct combinaia lor liniar cu vectorii lui S s fie nul

1v1 + 2 v 2 + 3 v3 = 1 (1,1,0,1) + 2 (1,2,1,1) + 3 (0,1,1,0) = (0,0,0,0)Obinem sistemul de ecuaii liniar omogen:1 2 = 0 + 2 + = 0 1 2 3 . 2 + 3 = 0 1 + 2 = 0

1 1 Matricea sistemului liniar omogen este A = 0 1 Rangul lui A este 3. Singura soluie a sistemului deliniar independent.

1 0 2 1 . 1 1 1 0 ecuaii este cea nul. Atunci, S este

8

CAMELIA FRIGIOIU

Observaii. 1) Matricea A a sistemului de ecuaii liniar omogen, obinut mai sus, are pe coloane coordonatele vectorilor lui S i rangul ei arat numrul de vectori din S liniar independeni; 2) Dac S = {} este liniar dependent; 3) Dac S = {v}, v este liniar independent, pentru c: din v = rezulta = 0 ; 4) n orice spaiu vectorial V/K orice subsistem de vectori S ' S al unui sistem S liniar independent este, de asemenea, liniar independent; 5) Dac S conine vectorul nul, sistemul de vectori S este liniar dependent; 6) Orice suprasistem S, S ' S ,al unui sistem de vectori liniar dependent S este liniar dependent.

4. Baz i dimensiune Definiia 4.1. Un sistem de vectori S din spaiul vectorial V/K se numete sistem de generatori pentru V, dac orice vector din V se poate scrie ca o combinaie liniar cu vectorii lui S. Vectorii lui S se numesc generatori pentru V. Observaii. 1) V=L(S); 2) Orice spaiu vectorial V/K admite cel puin un sistem de generatori. Definiia 4.2. Spaiul vectorial V/K se numete finit generat, dac exist S sistem de generatori finit pentru V. Definiia 4.3. Dou sisteme de vectori care genereaz acelai spaiu se numesc echivalente. Fie S un sistem de generatori pentru V/K. Urmtoarele transformri duc la obinerea tot a unui sistem de generatori pentru V/K: -schimbarea ordinei vectorilor lui S; -nmulirea unui vector din S cu un scalar nenul; -nlocuirea unui vector din S cu o combinaie liniar a acelui vector cu ali vectori din S. Teorema 4.1. Fie V/K spaiu vectorial i S = {v1 , v2 ,..., vn } sistem de generatori, liniar independent pentru V. Atunci orice sistem de n+1 vectori din V este liniar dependent.

ALGEBR LINIAR I GEOMETRIE

9

Definiia 4.4. Un sistem de vectori B al spaiului vectorial V/K care are proprietile: -B este sistem de generatori pentru V (=V) -B este sistem liniar independent se numete baz pentru spaiul V/K. Se poate demonstra c orice spaiu vectorial diferit de {} admite cel puin o baz. Definiia 4.5. Spaiul vectorial V se numete finit dimensional dac are o baz finit sau V = {} . n caz contrar se numete infinit dimensional. Teorema 4.2. Fie V/K un spaiu vectorial finit dimensional. Oricare dou baze ale lui V au acelai numr finit de elemente. Consecin. Toate bazele unui spaiu vectorial, finit dimensional au acelai numr de vectori. Definiia 4.6. Numrul notatn, dac V are o baz format din n vectori dim K V = 0, dac V = {}se numete dimensiunea lui V. Un spaiu vectorial cu dimensiunea n se numete n-dimensional i se noteaz cu Vn .Exemple1) n spaiul vectorial K n , vectorii e1=(1,0,0,...,0), e2=(0,1,0,...,0), en=(0,0,...,0,1) determin o baz B = {e1 , e2 ,..., en } ( numit baza canonic). Artm c B este liniar independent: combinaia liniar nul cu scalarii1,2,n, 1e1 + 2 e2 + ... + n en = este echivalent cu (1 , 2 ,..., n ) = (0,0,...,0) adic 1 = 2 = ... = n = 0Pe de alt parte x K n , x = (x 1 , x 2 ,..., x n ) = x 1e1 + x 2 e 2 + ... + x n e n .Deci V=. Dimensiunea lui K n este n. 2) Spaiul vectorial Mmxn(K) are dimensiunea mn, o baz a sa este mulimeaB = E ij 1 i m, 1 j n , Eij este matricea care are elementul 1 la intersecia liniei i cu{}coloana j, celelalte elemente fiind nule . 3) n spaiul vectorial C [X ] al polinoamelor cu coeficieni compleci i nedeterminata X, polinoamele 1, X , X 2 ,..., X n ,... formeaz o baz a lui C [X ] i deci dim C [X ] = . 3) Spaiul vectorial Pn[X] al tuturor polinoamelor de grad n are dimensiunea n+1 i o baz a acestuia este B = 1, X , X 2 ,..., X n .{}10CAMELIA FRIGIOIUTeorema 4.3. Sistemul de vectori B = {v1 , v2 ...vn } este baz pentru V dac i numaidac orice vector din V se scrie ca o combinaie liniar cu vectorii lui B. Demonstraia este imediat folosind teorema 5.1.Definiia 4.7. Scalarii 1, 2 ...n cu ajutorul crora se scrie un vector v V ca ocombinaie liniar de vectorii bazei B se numesc coordonatele vectorului v n raport cubaza B .Teorema 4.4. Coordonatele unui vector ntr-o baz sunt unice. Definiia 4.8. Fie Vn/K i B={u1,u2,un} o baz a lui Vn . Bijecia f : Vn K n , princare fiecrui vector vV i se asociaz n-uplul format cu coordonatele lui v n baza B, definit prin f(v)=(1,2n), unde v= i u i , se numete sistem de coordonate pe Vn.i =1 nUneori vom prefera identificarea v B = (1 ,..., n ) .Teorema 4.5. FieV/K spaiu vectorial, finit dimensional cu dim KV=n. Atunci auloc urmtorele afirmaii: i) orice sistem de vectori liniar independent are cel mult n vectori ii) orice sistem de vectori liniar independent format din n vectori este baz pentru V iii) orice sistem de generatori al lui V are cel puin n vectori. iv) orice sistem de generatori format din n vectori este baz pentru V.Observaie.Dimensiunea spaiului V/K este numrul maxim de vectori liniar independeni i numrul minim de generatori ai lui V.Lema 4.1. (substituiei)Fie V un K-spaiu vectorialde dimensiune n, B = {u1, u 2 ,.., u i 1, u i , u i +1, u n } bazpentru V, vV un vector care n baza B, are coordonatele v B = ( 1,..., n ) i sistemul devectori B*= {u1, u 2 ,..., u i 1,v , u i +1,..., u n } . Atunci: 1) B* este sistem liniar independent de vectori din V dac i numai dac i 0 ; 2) Dac i 0 , B* este o baz a lui V i coordonatele *1,.*2 ,...*n ale unui vector xV n baza B* se exprim n funcie de coordonatele sale 1. 2 ,... n n baza B prin:*i = i ; i *j = j j i ipentru ij.ALGEBR LINIAR I GEOMETRIE11Aceast lem se aplic in diverse probleme numerice ale algebrei liniare. De exemplu, pentru aflarea coordonatelor unor vectori v,x,z, n baza B*, cnd se cunosc coordonatele acestora n baza B. Se folosesc pentru aceasta tabele ale cror linii sunt afectate vectorilor bazei B, respectiv B* i n coloanele crora sunt inserate coordonatele vectorilor v,x,z, n baza B, respectiv B*. u1 ui uj V1 . x1 u1 V 0 1 0 x 1 ( 1i ) / i..i / ii. v uj [ i ]...jnjn j ( j i ) / i.. n ( n i ) / i .. un . un. 0. Tabelul BTabelul B*Dac i 0 , atunci vectorul u i al bazei B se poate nlocui cu vectorul v, obinnduse baza B*. i se va numi pivot i tabelul B* se obine din tabelul B n urmtorul mod: 1) se mparte cu pivotul, fiecare element de pe linia acestuia; 2) pivotul se va nlocui cu 1 i toate celelalte elemente de pe coloana lui cu 0; 3) toate elementele j , care nu se afl pe linia i coloana pivotului, se vor nlocui cu elementele calculate prin "regula dreptunghiului", adic prin:i det i j 1 j ( j i ) / i =i . j Exemplu. n spaiul vectorial R3, considerm vectorii u1 = (1,2,3) , u 2 = (1,1,0) ,u 3 = (0,1,2) , care formeaz o baz i vectorul x = (2,1,1) .Vom determina coordonatelevectorului x n baza format din aceti vectori, plecnd de la baza canonic a lui R3 i inlocuind pe rnd vectorii acesteia cu vectorii u1, u2,u3.u1e1 e2 e3[1]2 3u2 1 -1 0u3 0 1 2x 2 1 -1 u1 e2 e3u1 1 0 0u2 1[ 3]-3u3 0 1 2x 2 -3 -712CAMELIA FRIGIOIUu1u2u3 1/31 3x 1 1 -4 coordonatele f1f2u1u2u3 0 0 1x 7/3 -1/3 -4u1u21 0 00 1 0 am1 0 0 x n0 1 0 bazae3[1] aflatf3vectoruluiDeci,{u1,u 2 ,u 3 } ,adicx=7 1 u1 u 2 4u 3 . 3 3 5. Matrice.Sisteme de ecuatiiFie K corp comutativ. Am notat M mxn (K ) mulimea matricelor cu m linii i n coloane i coeficieni n K A = (ai j ) i =1,m M mxn ( K ) .j =1,nM mxn (K ) mpreun cu adunarea matricelor i nmulirea unei matrice cu un scalar are o structur de spaiu vectorial peste corpul K. Fie matriceaA = (a ij )i=1,m Mmxn (K) .j=1,nNotmu1 = (a11 , a12 ,...a1n );u 2 = (a 21 , a 22 ,...a 2 n ) ; ; u m = (a m1 , a m 2 ,...a mn ) . u i R n i = 1, m se numesc vectorii linie aimatricei A. Considerm vectorii vi=(a1i,a2i,...,ami) R m , i = 1, n , care se numesc vectorii coloan ai matricei A.Definiia 5.1.Se numete rangul matricei A, numrul vectorilor coloan liniarindependeni ai matricei A.Teorema 5.1. (rangului unei matrice)Rangul unei matrice A este egal cu numrul maxim de vectori coloan liniar independeni.Observaia 5.1. 1. Pentru o matrice A M n n (K ) cu coeficienii ntr-un corp comutativ K, lemasubstituiei d o metoda eficient pentru calcululinversei acesteia. n primul tabloucoloanele reprezint coordonatele vectorilor coloan ai matricei A n baza canonic a luiALGEBR LINIAR I GEOMETRIE13K n , urmate de coloane formate tocmai din vectorii bazei canonice. Dac det A 0, atuncivectorii coloan ai matricei A sunt liniar independeni peste K, ei pot fi introdui prin aplicarea succesiv a lemei substituiei, n locul vectorilor din baza canonic e1, e2 ,..., en . Se obine astfel: v1 e1 e2 . en A11 A21 . an1 v2 .. vn e1 1 0 . 0 e2 0 1 .. 0 . en . 0 . 0 . . . 1 v1 v2 . vn v1 1 0 . 0 v2 0 1 . 0 .. . . . . vn 0 0 . 1 e1 e2 . ena12 .. A1n a22 .. A2n . . .b11 b12 .. b1n b21 b22 .. b2n .. .an2 .. annbn1 bn2 .. bnnMatriceaB = (bij )i , j =1, n M n n (K ) este inversa matricei A, deoarece din ultimultablou se observa c: e j = b1 j v1 + b2 j v2 + ... + bnj vn , j = 1, n , ceea ce este echivalent cu egalitatea I=AB.2. Pentru o matrice A M mxn (K ) , cu m i n numere mari, o metod rapid de calcula rangului matricei este dat de lema substituiei. Considerm vectorii coloan ai matriceiA, vectori din K m i baza canonic a acestui spaiu vectorial. Rangul matricei A coincidecu numrul r al vectorilor coloan ai matricei A, care prin aplicarea lemei substituiei pot fi introdui n locul unor vectori din baza canonic a lui K m .Sisteme de ecuaii liniare.Fie K corp comutativ, R sau C, aijK i fie sistemul liniar de ecuaii cu m ecuaii i n necunoscutea11 x1 + a12 x2 + ... + a1n xn = b1 a 21 x + a 22 x + ... + a 2 n xn = b2 a x + a x + .. + a x = b m2 2 mn n m m1 1(1)Notm A = aij( )i=1,m, j=1,n x1 b1 x2 b n matricea sistemului i X = R i b = 2 R n . M M x b n nAtunci sistemul (1) se mai poate scrie: aij x j = bij =1ni = 1, m(2)14CAMELIA FRIGIOIUsau a1 j a2 j m sau dac notm v j = R M a mj AX=b(3)j = 1, n , atunciv j x j = bj =1n.(4)Definiia 5.2. Sistemul liniar de ecuaii (1) se numete compatibil dac existx = (1 , 2 ,..., n ) K n care verific identic acest sistem.Teorema 5.2. (Kronecker-Kapelli)Sistemul de ecuaii (1) este compatibil dac i numai dac r ( A) = r ( A) , unde A este matricea extins a sistemului. Dac b = , sistemul AX=0 sauv j x j =j =1nse numete sistem liniar omogen.Teorem 5.3. Mulimea soluiilor unui sistem de ecuaii liniar omogen cu nnecunoscute formeaz un subspaiu vectorial al lui Kn. Prezentm acum, metoda eliminrii pariale a lui Gauss pentru rezolvarea unui sistem liniar de n ecuaii cu n necunoscute.a11 x1 + a12 x 2 + ... + a1n x n = b1 a x + a x + ... + a x = b 21 22 2 2n n 2 , cu det(A)0. .......................................... a n1 x1 + a n 2 x 2 + .. + a nn x n = bn Fie sistemul de ecuaii:Dac n este un numr natural mare, numrul de operaii efectuate in metoda lui Gauss pentru rezolvarea sistemului este mult mai mic dect cel din metoda lui Cramer. Vom considera matricea extins a sistemului A =(A b). 1.Presupunem ca a110. In acest caz, a11 este declarat pivot. Se las linia pivotului neschimbat i se aduna prima linie inmulit cu ai1/a11 la fiecare liniei i, i = 2, n ; se obine o nou matrice A . [a11 ] a 21 A = a31 .. a n1 a12 a 22 a32 .. an2 a13 a 23 a33 .. a n3 ... a1n b1 a11 a12 a13 ... a 2 n b2 0 [a' 22 ] a' 23 ... a3n b3 0 a' 32 a ' 33 .. .. ... .. .. .. 0 ... a nn bn a' n 2 a ' n3 ... a1n ... a' 2 n ... a' 3n ... .. ... a ' nn b1 b' 2 b' 3 = A (1). .. b' n (1)ALGEBR LINIAR I GEOMETRIE15Se observ c aceasta revine la a inlocui cu 0 elementele de sub pivot din coloana acestuia i a transforma celelalte elemente aflate sub linia pivotului, folosind regula dreptunghiului . Dac a11=0, printr-o permutare adecvat de linii se aduce mai inti pe pozitia (1,1) un element nenul din prima coloan, in cazul in care exist. Altfel se trece la pasul urmtor. 2. Daca a220, atunci a22 este declarat pivot i se adun linia a doua inmulit cu -ai2/a22 la fiecare linie i a matricei A(1), 3 i n, obinindu-se Aa12 a13 a11 0 [a' 22 ] a' 23 = 0 a' 32 a' 33 .. .. .. 0 a' n 2 a' n3 ... ... ... ... ... a1n b1 a11 a ' 2 n b' 2 0 a ' 3n b' 3 0 .. .. .. a' nn b' n 0 a12 a' 22 0 .. 0 a13 a' 23,, a33 ( 2)... ... ... ... ...A(1).., a n,3a1n b1 a ' 2 n b' 2 ( 2) , , a 3,n b3, = A . .. .. ,, , a nn bn, Daca a22=0, printr-o permutare adecvat de linii in matricea A (1) se aduce mai inti in pozitia (2,2) un element nenul de sub a22 , din coloana acestuia, in cazul in care exist. Altfel, se trece la pasul urmator, s.a.m.d. Dupa n-1 pai, matricea A se transform intr-o matrice A * 11 0 A *= 0 .. 0 12 22 0 .. 0 13 23 33 .. 0 .. 1n 1 .. 2 n 2 .. 3n 3 . .. .. .. .. nn n Aceast matrice corespunde unui sistem de ecuaii triunghiular, echivalent cu cel iniial:11 x1 + 12 x 2 + ... + 1n x n = 1 22 x 2 + ... + 2 n x n = 2 . .......................................... nn x n = n Trecerea la acest sistem are ca efect eliminarea variabilelor x k , 1 kn, din ecuaiile k+1, k+2,n. Vom rezolva acest sistem obinnd:xn = n 1 n 1n x n n 12 x 2 ... 1n x n ; x n 1 = ; .. , x1 = 1 . nn n 1n 1 1116CAMELIA FRIGIOIUMetoda eliminrii totale Gauss-JordanEfectum in matricea extins a sistemului, A , transformri elementare, astfel inct s se obin forma diagonal a matricei A, adic matricea A * , de forma: 11 0 0 22 A* = 0 0 .. .. 0 00 0 33.. 0.. 0 .. 0 .. 0 .. .. .. nn .. n 1 2 3 i deci sistemul iniial este echivalent cu sistemul de ecuaii:= 1 11 x1 22 x2 = 2 ........................................ nn xn = n in care s-a realizat o eliminare total a variabilelor. Se obine soluia xk =k , 1 k n . kk 6. Schimbarea bazei unui spaiu vectorialFie B={e1,e2,..,en} i B={e1,e2,...,en} dou baze distincte n spaiul vectorial Vn. Fiecare vector din baza B se poate scrie ca o combinaie liniar a vectorilor bazei B cu scalarii s ij Ki, j = 1, n. e j ' = sij ei j = 1, nn(1)Notm cu S = sij( )i, j=1,ni =1matricea ptratic ale crei coloane sunt coordonatelevectorilor bazei B n raport cu baza B, adic matricea de trecere de la baza B la baza B. Fie xi i xi' , i = 1, n coordonatele aceluiai vector v n raport cu baza B respectiv B. Prin urmare, v = xi ei respectivi =1 n nv = x ,j e j ' .j =1(2)Prelucrm ultima relaien n n n n v = x' j e j ' = x' j s ij e i = s ij x' j e i . j=1 j=1 i=1 j=1 i=1 (3)ALGEBR LINIAR I GEOMETRIE17Folosim unicitatea coordonatelor unui vector ntr-o baz se obine:xi = sij x' j , i = 1, n .j =1 n(4)Aceste relaii caracterizeaz transformarea coordonatelor vectorului v la schimbarea bazei spaiului vectorial Vn .' x1 x1 x' x X i X sunt matricele coloan X = 2 i X ' = 2 ,care conin coordonatele lui v n . . x x' n nbazele B i B, (4) se scrie X = SX ' .Observaie.Matricea de trecere de la baza B la baza B este nesingular, pentru c coloanele ei sunt formate cu coordonatele vectorilor din B n baza B i aceti vectori sunt liniar independeni, deci rangul ei este n. 7. Aplicaii liniare(operatori liniari)Fie K spaiile vectoriale V i W .Definiia 7.1. Funcia f : V W cu proprietile:f(u+v) =f(u) + f(v) f(u) = f(u) u,v V K, u Vse numete aplicaie liniar de la V la W(operator liniar)Definiia 7.2. Funcia f : V W cu proprietateaf(u+ v) = f(u) + f(v) , K i u,v V se numete aplicaie liniar de la V la W(operator liniar). Cele dou definiii sunt echivalente.n aplicaii poate fi verificat oricare dintre ele.Exemple.1) V/K spaiu vectorial, IV: V V , IV(u) =u u V este aplicaia liniar identic. 2) V/K , dim V =n , B={e1,e2,.en} baz a lui V, f :VKn f(v)=(1,2,.,n), undev = i ei , este aplicaie liniar i se numete sistem de coordonate.i =1n18Teorema 7.1. Fie K-spaiile vectoriale V i W i f : V W o aplicaie liniar.Atunci f are urmtoarele proprieti : 1) f(u-v) = f(u) - f(v) u,v V 2) f(V) = WCAMELIA FRIGIOIU n n 3) f i u i = i f(u i ) i=1 i=1u1,u2,unV ,1,2,.nK.Aplicaiile liniare se mai numesc i morfisme de spaii vectoriale sau homomorfisme .Definiia 7.3. O aplicaie liniar f:V V se numete endomorfism al lui V sau transformare liniar. Propoziia 7.1. Compusa a dou aplicaii liniare este o aplicaie liniar. Definiia 7.4. Fie f : V W aplicaie liniar. Se numete nucleul lui f i se noteaz Ker f, mulimea tuturor vectorilor din V care au ca imagine prin funcia f vectorul nul WKer f ={ u V|f(u)= W}.Definiia 7.5. Fie f : V W aplicaie liniar. Se numete imaginea lui f i se noteaz Im f, mulimea tuturor imaginilor vectorilor din V prin funcia fIm f ={f(u)uV}.Teorema 7.2. O aplicaie liniar f :VW este injectiv dac i numai dac nucleulei Ker f = {V}.Teorema 7.3. Fie f: VW aplicaie liniar i LV subspaiu vectorial al lui V. Atuncif(L)={wW/ w=f(u), uV} este subspaiu vectorial al lui W .Observaie. Im f= f(V) este un subspaiu vectorial al lui W . Teorema 7.4. Nucleul unei aplicaii liniare este un subspaiu vectorial al lui V. Teorema 7.5. Fie f : VW aplicaie liniar i S={u1,u2, ..,un} un sistem de vectoridin V. Atunci au loc urmtoarele afirmaii : 1) Dac S este liniar dependent,atunci f(S)={f(u1),f(u2), ..,f(un)} este liniar dependent . 2) Dac S este sistem de generatori, atunci f(S) este sistem de generatori pentru Imf . 3) Dac S este liniar independent i f este injectiv, atunci f(S)={ f(u1),f(u2), ..,f(un)} este liniar independent .Consecin. Dac f : V W aplicaie liniar injectiv i B este o baz pentru V, atunci f(B) este baz pentru Im f i dimK( Im f) = n . Teorema 7.6. Fie f: VnWm aplicaie liniar, unde V i W sunt spaii finit dimensionale peste acelai corp K . Atunci: dimK Ker f + dimK Im f = dimKV = n .ALGEBR LINIAR I GEOMETRIE19Definiia 7.5. Spaiile vectoriale V,W se numesc izomorfe dac exist unizomorfism f : VW i notm V W .Teorema 7.7. (Teorema fundamental de izomorfism)Dou spaii vectoriale, finit dimensionale, definite peste acelai corp sunt izomorfe dac i numai dac au aceeai dimensiune . 8. Matricea asociat unui operator liniar definit pe spaii vectoriale finit dimensionaleFie f:VnWm operator liniar i fie B={u1,u1,un} baz pentru Vn i B1={v1,v2,.vm} baz pentru Wm. Vectorii f(u1),f(u2),f(un) Im f Wm i deci ei se pot exprima in baza B1 astfel f (u i ) = a ji v jj=1 mi=1,n .(1)Scalarii aij sunt coordonatele vectorilor f(u1),f(u2),f(un) n baza B1 i formeaz o matrice A=(aij) cu m linii i n coloane .Definiia 8.1. Matricea A se numete matricea ataat operatorului liniar f n bazeleB i B . Matricea A are numrul de linii egal cu dimensiunea lui W i numrul de coloane egal cu dimensiunea lui V. Matricea A este transpusa coordonatelor imaginilor vectorilor din baza B exprimai n baza B1. Reciproc, fiind dat o matrice, se poate determina o aplicaie liniar astfel nct A s fie matricea asociat lui f. Fiind dat A se construiete sistemul, de mai sus, (1) i se demonstreaz c f este liniar. Fie uVn. Atunci1 n f(u) = f x iui i=1Dar, f(u)W i atuncin m m n = x i f(ui ) = x i a ji v j = j=1 j=1 i=1 i=1 n a ji x i v j i=1(2)f(u)= y j v jj =1m(3)Din (2) i (3), folosind unicitatea coordonatelor unui vector ntr-o baz rezult:y j = aij xii =1n j= 1, m .20CAMELIA FRIGIOIUNotm x1 y1 x2 y X = i Y = 2 i se obine . . x y n mY=AX(4)unde Y este format cu coordonatele lui f(u) n baza B1 i X conine coordonatele lui u n baza B. Notm cu L(Vn,Wm) ={ f : VnWmf aplicaie liniar}. Dac f este endomorfism pe un spaiu finit dimensional, atunci folosim o singur baz i matricea endomorfismului este ptratic . Ne propunem s determinm legtura dintre matricele unui endomorfism n dou baze diferite ale spaiului Vn . Fie Vn i bazele sale B={u1,u1,un} i B1={v1,v2,.vn} legate prin v k = s ik u i k= 1, n .i=1 nTeorema 8.1. Dac endomorfismul f : VnVn are matricea A n baza B i matriceaA n baza B, atunciA =S-1A S . 9. Vectori proprii, subspaii proprii.Diagonalizarea unei matriceFie V/K spaiu vectorial i f :VV un endomorfism al lui V.Definiia 9.1. Un vector uV, u, se numete vector propriu al endomorfismului f,dac exist K astfel nct f(u)=u. Scalarul se numete valoarea proprie a lui f corespunztoare vectorului propriu u. Mulimea tuturor valorilor proprii ale endomorfismului f se numete spectrul lui f.Definiia 9.2.Un subspaiu vectorial S al lui V/K se numete invariant fa deendomorfismul f:VV, dac f(S)S.Teorema 9.1 a) Unui vector propriu al endomorfismului f i corespunde o singurvaloare proprie. b) independeni. c) Mulimea S()={u uV i f(u)=u }{ } este subspaiu vectorial al lui V invariant fa de f i se numete subspaiul propriu al endomorfismului f, corespunztor valorii proprii . Vectorii proprii corespunztori valorilor proprii distincte sunt liniarALGEBR LINIAR I GEOMETRIE21Determinarea valorilor i vectorilor propriiFie V/K spaiu vectorial, finit dimensional cu dimKV=n i B={u1,u2,...un} o baz n V. Considerm o transformare liniar f:VV. Atunci A Mn(K) astfel nctY=AX. uV i Y coordonatele lui f(u) n baza B.(9.1)(9.1) este ecuaia matriceal a lui f in baza B; vectorul X conine coordonatele unui vector Dac u este vector propriu, atunci:f(u)=u AX=X.(9.2) (9.3)Se obine(A-In)X=Oun sistem liniar omogen de ecuaii, cu parametrul K. Un vector propriu corespunztor valorii proprii reprezint o soluie nebanal a sistemului liniar omogen, (9.3). Deci, pentru a exista vectorii proprii, trebuie ca sistemul (9.3) s admit soluii nenule, ceea ce este echivalent cu:det (A - In) = 0.(9.4)Ecuaia (9.4) se numete ecuaia caracteristic a endomorfismului f. Soluiile ecuaiei caracteristice 1, 2, ...., n K sunt valorile proprii ale endomorfismului f.Definiia 9.3. Polinomul Pn()=det(A-In) se numete polinomul caracteristicasociat endomorfismului f, n baza B (A fiind matricea lui f in baza B).Propoziia 9.1. Polinomul caracteristic este invariant la schimbarea de baz aspaiului V.Observaia 9.1. S() coincide cu mulimea soluiilor sistemului de ecuaii, liniaromogen (9.3).Propoziia 9.2. Dimensiunea lui S() este mai mic sau egal dect ordinul demultiplicitate al lui .Observaia 9.2. Dac toate valorile proprii sunt rdcini simple ale ecuaieicaracteristice, (9.4), atunci subspaiile proprii asociate acestora au dimesiunea egal cu 1 iV = S(1) S(2) ....... S(n).22CAMELIA FRIGIOIUDiagonalizarea unui endomorfism Definiia 9.4. Un endomorfism f:VnVn se numete diagonalizabil, dac exist obaz B a lui V, astfel nct matricea asociat lui f n aceast baz s fie o matrice diagonal.Propoziia 9.3. Endomorfismul f:VnVn este diagonalizabil dac i numai dacexist o baz a lui Vn format din vectori proprii ai endomorfismului.Observaia 9.3. Forma diagonal canonic a unei matrice (endomorfism) se obinentr-o baz format din vectori proprii i pe diagonala ei principal sunt valorile proprii, corespunztoare vectorilor proprii din baz. Se poate demonstra c un endomorfism f:VnVn este diagonalizabil dac i numai dac valorile proprii i K i dimKS (i)=ordinul de multiplicitate al lui i.Observaia 9.4. 1.Dac rdcinile ecuaiei caracteristice sunt 1,2,....pK (1+2+..+p=n) i f:VnVneste diagonalizabil atunci:Vn=S(1) S(2) ... S(p) V este sum direct de subspaii proprii.2.Baza B a lui V n care se obine forma diagonal a matricei A este reuniuneabazelor subspaiilor proprii asociate.10. Probleme1) Notm cu V = (0,), mulimea numerelor reale strict pozitive i definim pe V operaiile: i date prin: x y = xy i x = x, x,y V i R. Este (V, , ) spaiu vectorial real? 2) n R fixm un numr xo i definim operaiile i prin: x y = x + y xo, x = x + (1-)xo x,y R, R.Este (R, , ) spaiu vectorial real ? Dar dac xo = 0 ? 3) Se consider M2x1(R), mulimea matricelor reale cu dou linii i o coloan. Definim i astfel: ( x 3 + x 3 ) 13 1 2 A1 A2 = 1 (y 3 + y 3 ) 3 2 1 x1 x1 x2 , A1 = y , R, A1= y , A2= y M2x1(R). 1 1 2 Este (M2x1(R), , ) spaiu vectorial peste R ?ALGEBR LINIAR I GEOMETRIE234) n spaiul vectorial real P 2 [X] = {f f R[X], gr f 2} se consider mulimile S1={p1,p2}, S2={q1,q2} unde p1 = x + x 2 , p 2 = 1 x + x 2 , q1 = 5 x + 9x 2 , q 2 = 4 x + 7x 2 S se arate ca S1 si S2 genereaz acelai subspaiu. 5) n spaiul vectorial R 3 se consider mulimea de vectori S={u1, u2, u3} ;u1=(1,-1,0), u2=(2,1,-1), u3=(0,3,-1). a)s se determine o baz a subspaiului L(S). b)s se verifice dac vectorul x=(2,-1,3) aparine subspaiului L(S). x 0 y 6) Fie L = A A = 0 u z , x, y , u , z R . S se arate ca L este subspaiu vectorial al lui M2x3(R) i s se determine o baz a sa. 7) Fie Pn = {f | f: R R, f polinomial, grad f n} i SPn = {h | h: R R, h polinomial, grad h = n}. Care dintre cele dou mulimi are structur de spaiu vectorial real, fa de operaiile: i date prin (fg)(x) = f(x) + g(x); ( f)(x) = f(x),R? 8) n spaiul Pn(R) al funciilor polinomiale reale de grad cel mult n; Pn(R) = {f| f: R R, f polinomial, grad f n}, se consider submulimile: Q = {f| f(0) = a; a fixat n R} U = {f| 3f(0) 2f(1)= 0} W = {f| f(1) + f(2)+ + f(k)= 0, k fixat} Care dintre aceste submulimi sunt subspaii n Pn(R)? n cazurile afirmative s se afle dimensiunea acelor subspaii. 9) n spaiul vectorial M3x2(R) se consider submulimea x S= {A | A = 0 z 10) n R3, fie mulimea vectorilor: S = {v | v= ( - 2, 2 +, -3 +); , R}. S se verifice c S este subspaiu i s se afle dimR S. 11) n R3 se consider submulimile: A = { v = (x1, x2, x3)| x1 3x2 +4x3 = 0} 0 y | x,y,z R }. 0 S se verifice c S este subspaiu i s afle dim RS.24CAMELIA FRIGIOIU2 2 C = { v = (x1, x2, x3) | x 1 + x 2 + x 3 = 25 } 2D = { v = (x1, x2, x3) | Care dintre acestea sunt subspaii ?x1 = x2 = x3 }12) Fie f o funcie polinomial de grad strict egal cu n. S se verifice dac sistemul S = {f,f,f, ,fn} este liniar independent. f, f.. reprezint derivatele funciei f. 13) Fie Co(R) spaiul vectorial al funciilor reale continue i submulimile: A = {eax, x eax, x2 eax, ...,xk eax} B = {1, cos 2x, cos 3x, ., cos k x} Care dintre acestea sunt liniar independente? 14) n spaiul funciilor polinomiale reale de grad cel mult 3, s se scrie formulele de schimbare a coordonatelor cnd se trece de la baza canonic B = {1, x, x2, x3} la baza B1 = {1, x -1, (x -1)2, (x -1)3} ; i de la baza canonic la baza B2 = {5, x+1, x2-1, x3+ x}. 15) n R3 se consider bazele B1= {v1, v2, v3} i B2 = {u1, u2, u3} date ambele, n baza canonic prin v1=(1,-1,2);v2=(-1,3,-2);v3 = (0,1,-1);u1 = (2,0,-1); u2= (1,3,2); u3= (1,4,0).S se afle formulele de schimbare ale coordonatelor cnd se trece de la B1 la B2. 16) n M2x2(R) se consider sistemul de vectori: 0 0 0 0 1 1 1 1 S = E1 = 0 0 ,E 2 = 0 0 ,E 3 = 1 1 ,E 4 = 1 1 . x y S se verifice c S este o baz i s se exprime n baza S matricea A = z t . 17) n R4 s se treac de la baza canonic la baza B = {e1, e2, e3, e4}, unde: e1 = (1,0,-1,0); e2 = (0,1,1,0); e3 = (1,-1,0,1); e4 = (0,0,1,-1). 18)Se d funcia T:R3R2 prin T(x)= (x1-x2+2x3,x2+x3) x=( x1,x2,x3) R3 a)S se arate c T este aplicaie liniar b)S se determine nucleul i imaginea lui T . 19)Se d funcia f: R3R3 prin f(x)=( x2, -x1+2x2,4x3) , x=( x1,x2,x3) R3. S se arate c f este transformare liniar i s se determine matricea asociat n baza canonic a lui R3. 20)S se arate c funciile de mai jos sunt aplicaii liniare : a) f: R3R3 prin f(x)=( x2,x3,x1) , x=( x1,x2,x3) R3ALGEBR LINIAR I GEOMETRIE25b) f: R2R3 prin f(x)=( x1-x2,2x2,2x1+x2) , x=( x1,x2) R2. 21)Fie spaiul vectorial P2[X]={p pR[X], gr p2}. Definim funcia D: P2[X]P2[X] prin D(p)=p derivata polinomului . a) S se arate c D este aplicaie liniar b) S se determine matricea lui D n baza canonic B={1,X,X2} i apoi in baza B={-1,1-X,(1+X)2} 22) S se determine nucleul i imaginea urmtoarelor aplicaii liniare i cte o baz pentru acestea : f: R3R3 prin f(x)=( 0,x1,x1+x2) , x=( x1,x2,x3) R3 f: R2R5 prin f(x)=(x1-x2,x1, x2 ,3x1,x1+x2) , x=( x1,x2) R2 i s se determine i matricele lor n bazele canonice ale spaiilor considerate. 23)Se consider R3 i R2 cu bazele canonice i f: R3R2 un operator liniar , cu proprietile : f(e1)=(2,-3) ; f(e2)=(1,2) ; f(e3)=(1,-1) , unde e1=(1,2,-1), e2=(0,3,-2) e3=(3,-1,2). S se afle matricea lui f n bazele canonice i imaginea lui v=(5,-1,4) prin f. 24) Se consider aplicaiile f: R3 R3 date prin: a) f(u) = a, a un vector fixat n R3, u R3 arbitrar; b) f(u) = u, R;2 c) f(u) =(x1,x2, x 3 ),unde u = (x1, x2, x3) R3;d) f(u) = (x1 +, x3, x2), R, fixat. Care dintre acestea sunt aplicaii liniare? 25) Se consider T : R3 R3 dat prin : T(u) = (x1 +x2 +x3, x1 +x2 +x3, x1 +x2 +x3); u = (x1,x2,x3) R3. S se verifice c T este liniar i s se afle cte o baz n Ker T i ImT.1 1 0 26)O transformare liniar T : R R are matricea A = 1 0 1 ntr-o baz 0 1 1 B={u1,u2,u3}. S se determine matricea ataat lui T n baza B={v1,v2,v3} unde v1=u1+2u2+u3, v2=2u1+u2+3u3, v3=u1+u2+u3. 27)S se determine pentru endomorfismele T1: R2 R2 T1 (x) = (x1 + 2x2, 2x1 +x2) x = (x1, x2) R23 3T2 : R 3 R 3T2 (x) = (x1 - 2x3, 2x1 + 2x2 2x3, 0) x = (x1, x2, x3) R3T3 : R3 R3 T3 (x) = (-x1, - 2x1+x2, 2x1 + x3) x = (x1, x2, x3) R3 a) nucleul si imaginea b)matricea n baz canonic; c)valorile proprii si vectorii proprii corespunzatori26CAMELIA FRIGIOIUProgramare liniar Capitolul II.1.Programare liniarProgramarea liniar este un capitol important al cercetrilor operaionale, cu o larg aplicare n practica de zi cu zi, dar mai ales n economie.Vom ilustra cteva direcii de aplicare ale programrii liniare in activitatea productiv.a)Problema utilizrii optime a unor resurseSe urmrete producerea reperelor R1,R2,Rn n fabricarea crora se utilizeaz materiile prime (resursele) E1,E2,.Em (resursele mai pot fi: disponibil de for de munc, disponibil de capital, energie). Resursele sunt disponibile n cantiti limitate; asfel din resursa Ej dispunem de o cantitate maxim bj, cunoscut n prealabil. Se mai cunosc: consumurile tehnologice: i = 1, n i j= 1, m se cunoate cantitatea aij 0, reprezentnd cantitatea din resursa Ej ce se consum pentru a fabrica o unitate din produsul Ri; beneficiile unitare: i = 1, n se cunoaste valoarea ci (real) reprezentnd suma obinut prin vnzarea unei uniti de produs Ri;---costurile unitare de achiziie pentru materiile prime: j= 1, m se cunoate valoarea j , reprezentnd suma necesar cumprrii unei uniti din materia prima Ej;-capital total disponibil: se cunoate mrimea S, reprezentnd suma total disponibil pentru achiziionarea de resurse in vederea realizrii produciei.Vom nota cu xi (i= 1, n ) cantitatea de produs ce va fi fabricat. Cunoaterea mrimilor xi, i= 1, n reprezint scopul final ntr-o problem de planificarea produciei. n aceste condiii: -ncasrile totale rezultate din vnzarea produselor sunt date de expresia f(x1,x2,xn) = ci xii =1 nALGEBR LINIAR I GEOMETRIE27-din resursa Ej s-a consumat n total cantitatea a ij x i ,i =1n j = 1, m ; j = 1, m ;-costul total al materiei prime Ej consumate este j aij xi-cheltuielile totale pentru achiziionarea tuturor materiilor prime necesare realizrii produciei vor fi aij xi j .j =1 i =1mnSe pot prezenta dou modele diferite, care au ca scop determinarea mrimilor x1,x2,xn. 1)Dac unitatea are materiile prime E1,E2,.Em n cantitile b1,b2,bm cunoscute, se pune problema utilizrii acestora ntr-un mod care s conduc la ncasri totale ct mai mari.n acest caz modelul matematic poate fi scris: maxim f(x1,x2,xn) = ci xi ;i =1nn aij xi b j j = 1, m i =1 x 0 i = 1, n i 2)Dac unitatea productiv dispune de un capital S, cu care dorete s achiziioneze materii prime pentru fabricarea produselor R1,R2,Rn asfel nct ncasrile totale s fie ct mai mari i s se recupereze capitalul investit. Modelul matematic va fi :n n m aij xi j S i =1 j =1 n c x S ; x 0 i = 1, n i i i i =1maxim f(x1,x2,xn) = ci xi ;i =1Aceste modele pot fi completate cu numeroase detalii reprezentnd condiii suplimentare de care trebuie s se in seama.b)Problema aprovizionrii (cu o singur marf )Se ia n considerare un sistem de depozite D1,D2,Dn: n depozitul Di se afl cantitatea ai de marf (i= 1, n ). Se tie c aceast marfa este destinat unor consumatori C1,C2,Cm.Beneficiarul Cj are nevoie de cantitatea bj de marf (j= 1, m ). Notm cu cij (0 cij ) costul transportului unei unitai de marf de la depozitul Di la consumatorul Cj. Acest model are scopul de a determina cantitaile xij ( i = 1, n , j = 1, m ) de marf ce vor fi scoase din depozitul Di i trimise beneficiarului Cj, astfel nct costul transportului ntregii28cantiti de produse s fie ct mai mic.Cazul cij= arat c transportul de la Di la Cj este imposibil. Vom prezenta modele care vor conine ca restricii condiiile ca totalul mrfii extrase dintr-un depozit s nu depaeasc marfa existent n acel depozit, iar cantitatea total de marf primit de un beneficiar s nu fie sub necesarul acelui beneficiar. Costul total de transport are forma:n mCAMELIA FRIGIOIU c ij x ij .i =1 j =1Modelele sunt: minim c ij x iji =1 j =1nmm xij = ai i = 1, n j =1 n ; xij = b j j = 1, m i =1 xij 0 i = 1, n , j = 1, m pentru problema echilibrat, n care i pentru problema neechilibrat ai = b ji =1 j =1nmminim cij xij ;i =1 j =1nmm xij ai i = 1, n j =1 n xij b j j = 1, m i =1 x ij 0 i = 1, n , j = 1, m c)Problema de nutriieSe tie din cercetrile nutriionitilor c un sistem de alimentaie, ntr-un anumit interval de timp trebuie s conin anumite substane active, care se gsesc n diverse tipuri de alimente. Notm cu Si substanele active necesare i= 1, m , cu Aj alimentele care trebuie procurate j= 1, n i care conin aij cantitate din substana Si pe unitatea de aliment Aj. Notm cu xj cantitatea din alimentul Aj, cu cj costul unitar al alimentului Aj i cu bi necesarul din substana Si. Se pune problema: care sunt cantitile de alimente xj, care pot fi procurate mai ieftin, fr abatere de la alimentaia tiinific. Modelul matematic este: minim f(x1,x2,xn) =n aij x j bi i = 1, m . j =1 x 0 i = 1, n i ci xi ;i =1nALGEBR LINIAR I GEOMETRIE29Un model asemntor, cu acesta prezentat mai sus, este problema amestecurilor de benzine, impunnd drept condiie alegerea celor mai economicoase amestecuri cu condiia obinerii unui produs final cu anumite caracteristici tehnice (putere caloric, temperatur de aprindere, grad de rafinare) care s fie inferioare sau superioare unor anumite mrimi prestabilite. Se poate rezolva i problema alctuirii celui mai ieftin amestec din diferite sortimente de crbune pentru nclzirea cazanelor cu aburi, cu anumite caracteristici tehnice. Exemplele de mai sus ne arat c o problema de programare liniar este o problem de optimizare cu restricii. La o problema de programare liniar (model de programare liniar) ntlnim: -o funcie obiectiv (funcie scop) care este o funcional liniar cu variabilele x1,x2,xn f(x1,x2,..xn)=c1x1+c2x2+..+cnxn -un sistem de restricii format din ecuaii i inecuaii liniare -condiii asupra variabilelor ( de obicei, condiii de nenegativitate x1 0 ,x2 0 ,xn 0 ) -un criteriu de optim, care poate fi minim sau maxim. Vom folosi matricele c1 . C= , b = . c n b1 . . , A = b n a11 . . a m1. . a1n . . . ,X= . . . . . a mn x1 . . . x n(1)Definiia1.1. Se numete o restricie concordant , o restricie care:-n problemele de maxim are semnul n problemele de minim are semnul .n celelalte cazuri restriciile se numesc neconcordante. Din modelele prezentate mai sus s-au dedus dou forme particulare ale problemei de programare liniar, numite forme canonice. Acestea sunt: [max] f =TCX; i [min] f =TCX ; AX b X 0 AX b . X 0(2) (3)30CAMELIA FRIGIOIUConvenim s nelegem prin condiia X 0 , condiiile care arat c toate componentele vectorului X sunt nenegative.Observaie. n formele canonice (2) sau (3) ale problemei de programare liniar,restriciile sunt concordante.Definiia 1.2.Se numete forma standard a problemei de programare liniar, forma[min] f =TCX ( sau [max] f = TCX ); AX = b X 0.(4)Evident c sistemul de restrictii AX=b poate fi incompatibil, compatibil unic determinat sau compatibil nedeterminat. Se inelege c numai ultimul caz este cu adevrat interesant, pentru c numai atunci se pune efectiv problema de a alege din mai multe soluii pe cea bun. Pentru a aduce o problema de programare liniar la forma standard, singura forma pe care tim s o rezolvm, vom aduga sau scdea noi variabile pozitive problemei, numite variabile de compensare sau variabile de ecart.Observaii.1) Se poate trece de la o problem de maxim la una de minim folosind relaia: max f = - min (-f ) si invers. 2) Dac problema de programare liniar nu are forma canonica, deci nu conine restricii de acelai tip, atunci se adaug sau se scad varibilele de compensare, dup cum cere restricia respectiv.Exemplu. S se aduc la forma standard problema de programare liniarurmtoare [max] f = 16x1+20 x2 2x3+3x4 ; x1 + 2 x2 + x3 x4 200 + x4 100 2 x1 x2 x 0 , j = 1,4 j Se adaug o variabil de compensare la prima restricie i se scade o variabil din a doua restricie. Forma standard este x1 + 2 x2 + x3 x4 + x5 = 200 [max] f = 16x1+20 x2 2x3+3x4; 2 x1 x2 + x4 x6 = 100 . x j 0 , j = 1,6 Se poate demonstra c orice problem de programare liniar se poate aduce la forma standard i c aceasta are aceleai soluii ca i problema iniial.ALGEBR LINIAR I GEOMETRIE31Soluiile unei probleme de programare liniarFie problema de programare liniar (P.L) AX = b . [min] f =TCX ; X 0Definiia 1.3. Un vector X0 Rn care verific sistemul de restricii AX=b, ct icondiiile de nenegativitate X 0 ale unei (P.L) se numete soluie posibil a problemei (admisibil sau realizabil sau program).Definitia 1.4. O soluie posibil X0 pentru care numrul de componente nenule,rm , iar vectorii matricei A care corespund componentelor nenule sunt liniar independeni, se numete soluie de baz ; dac r< m, soluia de baz se numete degenerat.Definiie 1.5. Un vector X0Rn, soluie posibil pentru (P.L) se numete soluieoptim (program optim) a problemei (P.L) dac optimizeaz funcia f, adic dac pentru orice soluie posibil X are loc relaia TC X0 TCX. S-au obtinut diveri algoritmi de rezolvare a unei probleme de acest tip.Toi aceti algoritmi au o caracteristic comun: metoda iterativ - se pornete de la o soluie posibil iniial care se modific treptat, pn cnd funcia de eficien devine optim sau se dovedete c optimul nu exist. Esena fiecrei metode este gsirea soluiei iniiale i mbunatirea ei cu un algoritm de calcul. Noi vom prezenta algoritmul lui Dantzig numitalgoritmul simplex. .2.Mulimi convexe n Rn( ( ( Definiia 2.1. Fie x(1) , x(2) ,...,x(k) Rn, unde x (i ) = ( x1 i ) , x 2i ) ,......, x ni ) ) R n , i = 1, ki scalarii 1 ,2,..k R, j [0,1] i j = 1 . Vectorul x= i x (i ) se numete combinaiaj =1 i =1kkliniar convex a vectorilor dai. Definiia 2.2. O mulime C Rn se numete convex dac pentru orice x(1), x(2)C,cu x(1) x(2), combinaia lor convex x = x(1)+(1-)x(2)C, cu [0,1]. Geometric aceast definiie se exprim astfel: Mulimea C Rn este convex dac orice punct de pe segmentul de dreapt ce unete dou puncte distincte oarecare ale lui C, se afl, de asemenea n C.32CAMELIA FRIGIOIUObservaie. Orice punctinterior al unei mulimi convexe poate fi scris ca ocombinaie liniar convex de puncte distincte ale mulimii. Excepie de la aceasta, fac anumite puncte pe care le vom numi vrfuri ale mulimii convexe.Definiia 2.3. Se numete punct de extrem sau vrf al mulimii convexe C, un punctxC, care nu se poate scrie ca o combinaie liniar convex de puncte distincte din C..3.Forma matriceal i vectorial a unei probleme de programare liniarFie problema de programare liniar, n forma standad, scris matriceal AX = b [max] f = TCX ; , X 0unde A = (a ij ) i =1,m, j =1,n i bT=(b1,b2,bm). Dac a1,a2,.,an Rm sunt vectorii coloan ai matricei A, atunci sistemul de restricii din forma standard, care de fapt este un sistem de ecuaii liniare, se mai poate scrie x ja j = b .j =1nTeorema 3.1. Mulimea S a tuturor soluiilor realizabile ale sistemului AX=b, X Oeste convex n Rn. n cele ce urmeaz, vom presupune c S este o mulime mrginit.Dac vor aprea cazurile S= sau S nemrginit, metoda simplex pe care o prezentm este n msur s o detecteze.Teorema 3.2. O condiie necesar i suficient ca XS, cu X0 s fie punct deextrem pentru S este ca X s fie o soluie realizabil de baz, care satisface sistemul AX=b, X 0.Observaii.1)Orice punct de extrem al lui S corespunde unei soluii de baz a problemei de programare liniar i invers, orice soluie de baz corespunde unui punct de extrem. 2)Un punct de extrem degenerat poate avea mai mult de o soluie de baz corespunztoare, n timp ce un punct nedegenerat de extrem va corespunde numai unei singure soluii de baz.Teorema 3.3. Soluia optim a unei probleme de programare liniar, dac estefinit,se afl ntr-un punct de extrem al spaiului soluiilor S. Dac soluia optim se afl nALGEBR LINIAR I GEOMETRIE33mai multe puncte de extrem atunci valoarea funciei de eficien va fi aceeai pentru toate combinaiile convexe ale acestor puncte. Aceast teorem arat c soluia optim a unei probleme de programare liniar poate fi obinut numai pornind de la soluiile realizabile de baz..4.Metoda simplexMetoda simplex, pentru prima dat publicat de americanul G. B. Dantzig n 1947, presupune analizarea anumitor soluii realizabile de baz i trecerea de la o soluie la alta, mai bun, prin schimbarea cte unui vector din baz. Mai exact,se pornete de la o soluie realizabil de baz (care se deduce ct mai simplu posibil), se testeaz optimalitatea acestei solutii, folosind un test de optimalitate.Dac soluia este optim, metoda ia sfrit, dac nu, se trece la o alt soluie de baz corespunztoare unei baze care difer de precedenta numai printr-un singur vector. Alegerea lui se face prin criteriul de intrare n baz. Vectorul pe care acesta l nlocuiete se alege conform criteriului de ieire din baz. Criteriul de ieire din baz se deduce din condiia de admisibilitate a noii soluii; criteriul de intrare n baz se obine din condiia ca noua soluie s mbunteasc valoarea funciei de eficien.Condiie pentru alegerea vectorului ar care iese din baz Condiia de admisibilitateFie a1,a2,,am,..,an vectorii coloan ai matricei A i (XB, 0) o soluie admisibil de baz a problemei, unde prin XB am notat primele m componente nenule ale soluiei X, baza corespunztoare ei fiind B={a1,a2,,am}. Aceast soluie se numete soluie curent, iar B baza curent. Sistemul de restricii al problemei de programare liniar se scrie: x j a j =B XB=bj =1m(1) (2)sauXB=B-1b. Vom genera o nou soluie realizabil de baz pornind de la cea curent.Fie aj un vector, ales din ceilali n-m vectori ai matricei A, care nu sunt n baza curent i xj variabila corespunztoare lui.34CAMELIA FRIGIOIUVectorii a1,a2,,am sunt liniar independeni i atunci putem exprima vectorul aj nj j baza B, astfel: exist scalarii 1j , 2 ,......, m astfel nctaj= kj a k .k =1m(3)j j Notm j = ( 1j , 2 ,..., m ) T i atunci relaia (3) se mai poate scrieBj = aj sau j =B-1aj . Fie > 0, oarecare.nmulim relaia (4) cu i se obine folosind (1) B ( XB - j ) + aj = b. Aceasta arat faptul c noul vector X cu m+1 componente nenule(4)(5) X j B 1b j = X = B este o soluie a noului sistem de restricii cu o nou variabil xj= > 0. Deci X este o soluie nebazic, deoarece are m+1 variabile nenule.(6)Pentru a obine o nou soluie admisibil de baz, scalarul trebuie ales astfel nct una din vechile variabile de baz s fie zero, adic s devin variabil nebazic. Pe de alt parte toate elementele lui X trebuie s fie nenegative. Aceasta nseamn: xk - kj 0 , k = 1, m xj = > 0. Deoarece xk 0, expresia xk kj poate deveni negativ numai dac kj > 0. Deci, cnd stabilim condiia de admisibilitate a soluiei X' vom lua n considerare numai kj > 0. n acest caz, vechea variabil bazic care trebuie fcut 0, trebuie aleas astfel nct (7)x x j = min kj , k 0 = rj , k r k rj > 0,(8)unde k=r reprezint indicele variabilei bazice care atinge minimul rapoartelor pozitive de mai sus. Astfel n noua soluie, X, variabila xr devine 0. ntr-adevr: xr - rj = xr -xr rj rj = 0,(9)i xr devine nebazic. Deci, vectorul aj este vectorul care intr n baz, iar ar este vectorul care iese din baz. Dac acelai minimum dat de valoarea (8) apare pentru mai mult de o variabil xr, noua soluie de baz va fi degenerat, deoarece cel puin o variabil bazic va fi 0 n noua soluie X.ALGEBR LINIAR I GEOMETRIE35O alt situaie critic este atunci cnd toi kj 0, ceea ce nseamn c noile variabile xk - kj >0 pentru 0; deci nici o variabil nu poate fi nlturat din soluie. Acesta nseamn c noua soluie va fi ntotdeauna nebazic i c variabilele sale pot crete orict de mult. n acest caz soluia se numete nemrginit.Condiie pentru alegerea vectorului aj care intr n baz, condiia de optimalitateS considerm o problem de programare liniar i fie B o baz curent,T CB =(c1,c2,cm) vectorul coeficienilor funciei obiectiv, corespunztor bazei curenteXB = B-1 b. DefinimT fj = C B j , unde j este dat de (4) sau j =B-1aj .Teorema 4.1. Fiind dat soluia realizabil de baz XB =B-1 b , vectorul aj este unvector care poate intra n baz dac cj -fj>0 (pentru problemele de maxim) sau fj cj > 0 (pentru problemele de minim). Dac cj -fj 0 (sau fj cj 0) pentru toi vectorii nebazici aj atunci soluia curent este optim.Observaii.1.Noua valoare a funciei de eficien f0 se poate mbunti numaidac >0. Dac =0, f0= f0 rmne aceeai. Acesta este cazul soluiei degenerate care se trateaz separat.2. Dac cj -fj < 0 (n problema de maxim) i valoarea rezultat xj este nemrginit,adic ar putea lua orice valoare nenegativ, atunci valoarea lui f0 va fi nemrginit i n consecin problema nu are soluie finit.3.Dac cj -fj = 0 pentru o variabil nebazic xj, este posibil s introducem aj pentru aobine o nou soluie de baz, care va conduce la aceeai valoare pentru funcia de eficien.4.Deoarece, prin definiie, fj =CBTj =CBTB-1aj, atunci pentru toate variabileleproblemei fj = CBTB-1A. Rezult,c de ndat ce a fost determinat inversa matricei B, din iteraia curent va fi posibil s calculm toate elementele din tabelul curent, utiliznd informatiile originale ale problemei.36CAMELIA FRIGIOIUDeterminarea unei soluii iniiale de bazDac problema de programare liniar are forma canonic: max f=c1x1+c2x2++cnxn a11 x1 + a12 x2 + ... + a1n xn b1 a x + a x + ... + a x b 22 2 2n n 2 21 1 ........................................... a x + a x + ... + a x b m2 2 mn n m m1 1 x1 0, x2 0, .....xn 0 i presupunem c n plus toi termenii liberi sunt pozitivi, adic b1 0,...,bm 0. Adugm variabilele de compensare: xn+1,xn+2,xn+m 0 i se obine forma standard: a11 x1 + a12 x 2 + ... + a1n x n + xn+1 = b1 a x + a x + ... + a x + x 22 2 2n n n + 2 = b2 21 1 ........................................... a x + a x + ... + a x + x m2 2 mn n n + m = bm m1 1 x1 0, x2 0, .....x n+ m 0 max f=c1x1+c2x2++cnxn;Rangul matricei sistemului de ecuaii de mai sus este m, deoarece matricea sistemului conine exact m vectori unitari, pe care i vom nota: an+1,an+2,,an+m. O soluie de baz trebuie s aib maxim m componente nenule. Drept soluie iniial vom lua o soluie foarte uor de determinat i anume: x1=x2=.=xn=0, xn+1=b1, xn+2=b2,, xn+m=bm. Cum toate componentele termenului liber sunt pozitive, rezult c soluia sistemului de restricii al problemei de programare liniar :XT=(0,0,,0,b1,b2,bm)Rn+m servete drept soluie iniial de baz.Observaie. Se tie c problema de programare liniar se poate aduce mereu laforma standard, totui condiia suplimentar b1 0 ,...,bm0 face ca ntotdeauna soluia iniial s poat fi dedus ca mai sus. Metoda simplex are n vedere testarea optimalitii soluiei de baz (iniiale) curente; n caz c soluia este optim, algoritmul se oprete; dac nu este optim, soluia se modific prin modificarea unui vector din baza curent, aplicnd criteriul de intrare n baz;acest nou vector care se alege prin criteriul de intrare n baz, nlocuiete un vector din vechea baz, care se alege prin criteriul de ieire din baz.ALGEBR LINIAR I GEOMETRIE37Noua soluie se calculeaz utiliznd metoda Gauss-Jordan. Aceast soluie se testeaz, la rndul ei, cu criteriul de optimalitate, etc. Algoritmul ia sfrit dup un numr finit de pai.Organizarea calculelor - tabelul simplexPresupunem c baza curent B este format din primii m vectori ai matricei sistemului de restricii din forma standard, a1,a2,,am, deci primele m componente ale soluiei x1,x2,,xm sunt diferite de 0. Vom nota CB subvectorul lui C format cu componentele lui C corespunztoare bazei B. Se observ c vectorii bazei se exprim n felul urmtor n baza B: a1=1a1+0a2++0am;a2=0a1+1a2++0am;.,am =0a1+0a2++1am. De asemenea, aa cum am vzut mai sus, toi vectorii a j care nu aparin bazei se pot exprima prin:j j a j = 1j a1 + 2 a 2 + ...... + m a m , j= m + 1, m + n .Tabelul simplex pentru baza curent este urmtorul: c1 c2crcmcj CB c1 c2 . cr . cm ck fk B a1 a2 . ar . am xB x1 x2 . xr . xm f0 a1 a2aramaj 1 0..0.0.1j 0 1..0.0.2j 0 0..10..rj. 0 0..01..mj. 00.0.0cj-fj cm+n am+n1m+n 2m+n rm+n mm+ncm+n-fm+n..Reguli practice pentru aplicarea algoritmului simplex 1.Criteriul de optimalitate. Dac toate diferenele k=ck-fk (pentru problema demaxim) sau k= fk - ck (pentru problema de minim) corespunztoare vectorilor care nu sunt n baza curent B sunt negative sau egale cu 0, soluia XB este optim i algoritmul se oprete.38CAMELIA FRIGIOIU2.Criteriuldeintrareinbaz.Daccelpuinunadintrediferenelecorespunztoare vectorilor care nu se afl n baza curent, este pozitiv, k=ck -fk >0 (pentru problema de maxim) sau k =fk-ck>0 (pentru problema de minim), atunci soluia XB nu este optim. Se alege max { k | k >0} = j . Vectorul aj intr n baz.3.Criteriul de ieire din baz. Se aplic dup aplicarea criteriului de intrare nbaz.Se adaug o nou coloan n partea dreapt a tabelului, coloana , n care se scriu rapoartelexk kj, pentru care kj > 0. Nu se scriu cele cu kj 0.Se alege raportul minim: x x min kj , kj 0 = rr . Vectorul ar iese din baz. k k 4.Stabilirea pivotului, dac soluia curent nu este optim.La intersecia liniei vectorului ar , care iese din baz, cu coloana vectorului aj, care intr n baz, se afl pivotul rj > 0 , cu care se lucreaz n metoda lui Gauss-Jordan pentru obinerea noului tabel simplex. Adic elementele noului tabel simplex se vor calcula astfel: -linia pivotului se mparte la pivot; -coloana pivotului are elementele egale cu 0, cu excepia elementului de pe locul pivotului, care este 1; -celelalte elemente se calculeaz dup regula dreptunghiului. Se obine astfel o nou soluie. Noua baz B1, va conine n locul lui ar vectorul aj, iar aj va deveni vector unitar.Exemplu.S se rezolve problema de programare liniar, utiliznd algoritmulsimplex: max f = 5x1 + 4x2 + 3x3 x1 + 2x2 + 2x3 10 2x1 + x2 8x1, x2 ,x3 0.2x2 - x3 8ALGEBR LINIAR I GEOMETRIE39Soluie. Se aduce problema la forma standard, adugndu-se variabilele decompensare x4 , x5, x6 0.Funcia de eficien rmne neschimbat, dar inegalitile se vor transforma n egaliti: max f = 5x1 + 4x2 + 3x3+0x4+0x5+0x6 x1 + 2x2 + 2x3 + x4 2x1 + x2 2x2 - x3 +x5 =10 = 8 +x6 = 8 xj 0 , j= 1,6 .Baza iniial este baza unitar, reprezentat de matricea unitate de ordinul trei, format cu vectorii coloan a4,a5,a6 ai matricei A a sistemului de restricii. Soluia iniial de baz se obtine astfel: x1=x2=x3=0, x4=10, x5=8, x6=8. Construim tabelul simplex iniial cu soluia iniial de baz, matricea sistemului de restricii, baza initiala: 5 CB 0 0 0 B a4 a5 a6 XB 10 8 804 a2 2 1 243 a3 2 0 -130 a4 1 0 000 a5 0 1 000 a6 0 0 10a1 1 2 05j=cj-fjUltima linie a diferenelor se calculeaz conform definiiei : f1 = CBT B a 1=-1CBT1 a1 =(0, 0, 0) 2 =0 ; c1-f1= 5 0 =5 0 2 a2 =(0, 0, 0) 1 =0; c2 f2 = 4 - 0=4 2 f2 =CBTB a 2=-1CBTf3= CBT2 a3 =(0, 0, 0) 0 =0; c3 f3 = 3 - 0=3;f4=0; c4-f4=0; f5=0, c5-f5 =0 ; f6=0, c6-f6=0. 1 Criteriul de optimalitate se aplic dup calcularea diferenelor j. Soluia nu este optim, deoarece nu toate diferenele sunt negative sau egale cu 0. Vom schimba baza curent, prin introducerea unui nou vector n baz. Criteriul de ieire din baz indic40CAMELIA FRIGIOIUalegerea max { 5,4,3 } = 5 =c1 f1, deci vectorul a1 intr n baz, j=1. Vom stabili vectorul care iese din baz i pentru aceasta adugm coloana . Acum tabelul va arta astfel: CB 0 0 0 cj-fj B a4 a5 a6 XB 10 8 8 0 5 a1 1 (2) 0 5* 4 a2 2 1 2 4 3 a3 2 0 -1 3 0 a4 1 0 0 0 0 a5 0 1 0 0 0 a6 0 0 1 010/1 8/2 x55 1Criteriul de ieire din baz indic ieirea vectorului, care realizeaz min {10,4} = 4=,deci iese din baz a5. Pivotul iteraiei este egal cu 2. Noua baz va fi format din vectorii a4, a1, a6. Calculul elementelor noului tabel se va efectua cu metoda Gauss - Jordan. Tabloul simplex va fi : 5 CB 0 5 0cj-fj4 a2 3/2 1/2 23/23 a30 a4 1 0 000 a5 -1/2 1/2 0-5/20 a6 0 0 10B a4 a1 a6XB 6 4 820a1 0 1 003 -(2)0 -13*Soluia dat de acest tabel este XT=(4,0,0,6,0,8), iar valoarea funciei este de 20. Aplicm iar criteriile de optimalitate pentru a studia aceast soluie . Linia diferenelor arat c soluia nu este optim va intra n baz a3; coloana lui arat c iese din baz vectorul a4. Pivotul este egal cu 2. Noua baz va fi format din vectorii a3 , a1, a6. Iteraia corespunztoare este dat de tabelul de mai jos: CB 3 5 0 cj-fj B a3 a1 a6 XB 3 4 11 29 5 a1 0 1 0 0 4 A2 3/4 11/4 -3/4 3 A3 1 0 0 0 0 a4 1/2 0 1/2 -3/2 0 a5 -1/4 1/2 -1/4 -7/4 0 a6 0 0 1 0Soluia corespunztoare este XT = (4,0,3,0,0,11), iar valoarea functiei de eficien este 29.Testul de optimalitate indic faptul c aceast soluie este optim.ALGEBR LINIAR I GEOMETRIE41Determinarea unei soluii iniiale de baz, cnd problema are forma canonic:min f=c1x1+c2x2++cnxn a11 x1 + a12 x 2 + ... + a1n x n b1 a x + a x + ... + a x b 22 2 2n n 2 21 1 ........................................... a x + a x + ... + a x b m2 2 mn n m m1 1 x1 0, x 2 0, .....x n 0 Presupunem c termenii liberi sunt pozitivi: b1 0 ,b2 0,, bm 0. Introducem variabilele de compensare, cu coeficientul -1 n fiecare restricie si se obine forma standard a problemei de programare liniara: min f=c1x1+c2x2++cnxn a11 x1 + a12 x 2 + ... + a1n x n x n+1 = b1 a x + a x + ... + a x x 22 2 2n n n + 2 = b2 21 1 ........................................... a x + a x + ... + a x + x m2 2 mn n n + m = bm m1 1 x j 0, j = 1, n + m Dac procedm ca mai nainte, vom lua drept soluie iniial de baz, soluia: x1=x2=.=xn=0, xn+1= -b1,xn+2= - b2,,xn+m= - bm, ns acesta nu este i realizabil, pentru c ea nu satisface condiiile algoritmului simplex. Pentru a obine o soluie admisibil de baz, vom introduce n fiecare egalitate o nou variabil nenegativ, cu coeficientul +1, care s nlesneasc alegerea soluiei iniiale. Aceste m variabile pe care le introducem se numesc variabile artificiale, iar metoda de lucru pe care o expunem se numete metoda variabilelor artificiale sau metodapenalizrii .Astfel, dup adugarea variabilelor artificiale sistemul de restricii devine : a11 x1 + a12 x2 + ... + a1n xn xn+1 + xn+ m+1 = b1 a x + a x + ... + a x x + x 22 2 2n n n+ 2 n + m + 2 = b2 21 1 ........................................... . a x + a x + ... + a x + x m2 2 mn n n + m + x n + 2 m = bm m1 1 x j 0, j = 1, n + 2m Evident, aceste variabile artificiale vor disparea din soluia optim sau vor fi 0 la sfritul rezolvrii, altfel restriciile iniiale ale problemei vor fi modificate. Totui, soluia iniial de baz pentru problema cu restriciile de mai sus poate fi acum una convenabil i anume: x1=x2=.=xn==xn+m=0, xn+m+1=b1,xn+m+2=b2,xn+2m=bm.42CAMELIA FRIGIOIUIniial, variabilele artificiale sunt n baz. Le putem elimina treptat din baz dac le asociem un coeficient foarte mare n funcia de eficien, practic . Acest coeficient foarte mare se numete coeficient de penalizare, se noteaz cu M pentru toate variabilele artificiale i se consider practic infinit. n concluzie, funcia de eficien se modific i ea devenind: min w= c1x1+c2x2++cnxn+Mxn+m+1+Mxn+m+2+Mxn+2m. Dac totui, la sfritul rezolvrii problemei de programare liniar prin metoda variabilelor artificiale, una din variabilele artificiale (sau mai multe) are vectorul su n baza optim i ea este nenul, rezult c problema dat initial nu admite soluie.Exemplu.S se rezolve problema de programare liniar, utiliznd algoritmul simplex: min f = 4x1 + 3x2 + 5x3 2x1 + x2 -5x3 300 x1 + x2 + x3 75 x1, x2 ,x3 0.Soluie. Aducem problema la forma standardmin f = 4x1 + 3x2 + 5x3 2x1 + x2 -5x3 x4 x1 + x2 + x3 xj 0j = 1,5 .=300 - x5 = 75Vom aduga variabilele artificiale x6, x7, introducndu-le n restricii cu coeficientul 1 i n funcia de eficien cu coeficientul de penalizare M: min w = 4x1 + 3x2 + 5x3+Mx6+Mx7 2x1 + x2 - 5x3 x4+ x1 + x2 + x3 - x5 x6 =300 + x7= 75xI 0, l=1,7. Soluia iniial de baz este x1=x2=x3=x4=x5=0, x6=300, x7=75. Calculele aferente algoritmului simplex sunt redate n tabelul urmtor. Pentru calculul liniei diferenelor i stabilirea criteriilor de optimalitate i de intrare n baz se folosete j = fj cj . Pentru criteriul de intrare n baz se folosesc coeficienii lui M din diferenele j. La prima iteraie a1 intr n baz, deoarece se compar coeficientul 3 al lui M din diferena 1=3M 4 cu coeficientul 2 al lui M din diferena 2 = 2M-3 i se alege coeficientul cel mai mare, deci intr n baz a1.ALGEBR LINIAR I GEOMETRIE434 CB M Mfj-cj3 a2 1 12M-35 a3 -5 1-4M-50 a4 -1 0-M0 a5 0 -1-MM a6 1 00M a7 0 10B a6 a7 a6 a1 a5 a1XB 300 75 150 75 75 150600a1 2150 75 75 -(1)3M-4*M 4fj-cj0 10-1 1-M+1-7 1-7M-1-1 0-M(2)-12M-4*1 00-0 4fj-cj0 10-1/2 -1-7/2 - 5/2- 15- 1/2 - 1/2-21 00--Dac o variabil artificial iese din baz, ea nu va mai intra niciodat n baz, fapt care justific eliminarea din calcul a coloanelor a7 i a8 din tabelul de mai sus. Soluia optim a problemei este: x1=150, x2=x3=x4=0, x5=75, min f =600.Soluie optim multipl.Calcul soluiei optime generaleDac o problem de programare liniar are mai multe soluii optime de baz, atunci orice combinaie liniar convex a acestor soluii este de asemenea o soluie optim. Din cele expuse a rezultat, de asemenea, cnd o soluie este multipl: dac n iteraia optim cj - fj=0 (sau fj - cj=0) pentru un vector aj care nu aparine bazei, atunci este posibil s introducem n baz vectorul aj pentru a determina alt soluie optim care s conduc la aceeai valoare pentru funcia de eficien.Exemplu. Se face un amestec de uleiuri minerale U1,U2,U3,U4, n vederea unuiprodus finit cu anumite caliti i n cantitate de cel puin 800 l.Amestecul trebuie s conin substanele S1 i S2 n cantitate de cel puin 18000 g respectiv 21000 g.Coninutul de substane S1 i S2 ale fiecrui tip de ulei i costurile unitare sunt date mai jos: Uleiuri Coninut n grame/ l Substane U1 U2 U3 S1 20 10 30 S2 10 20 10 Cost unitar Mii u.m./t 5 4 4,5 Cum trebuie fcut amestecul cu cost total minim? U4 20 30 3 Necesar (g) 18000 2100044CAMELIA FRIGIOIUSoluie.Fie x1,x2,x3,x4 cantitile din uleiurile U1,U2,U3,U4 care trebuie puse namestec. Funcia de eficien este o funcie cost, costul total al amestecului.Ea trebuie minimizat: min f = 5 x1+4x2+4,5 x3+3x4 (mii u.m.) x1+x2+x3+x4 800. Celelalte dou restricii se refer la substanele S1 i S2 necesare amestecului: 20 x1+10x2+30x3+20x4 18000 10 x1+20x2+10x3+30x4 21000. Condiiile de nenegativitate asupra variabilelor sunt: min f = 5x1+4x2+4,5 x3+3x4 x1+x2+x3+x4 800; 20 x1+10x2+30x3+20x4 18000;10 x1+20x2+10x3+30x4 21000 x1 ,x2 , x3 , x4 0. mprim cu 10 restriciile doi i trei: min f =5 x1+4x2+4,5 x3+3x4 x1+x2+ x3+ x4 800 2 x1+x2+3x3+2x4 1800 x1+ 2x2+ x3+3x4 2100; Se aduce problema la forma standard i se obine: min f =5 x1+4x2+4,5 x3+3x4 x1+x2+x3+x4 x5 = 800 2 x1+x2+3x3+2x4 x6 = 1800 x1+2x2+x3+3x4 x7 = 2100 xj 0, j = 1,7 Pentru a reduce calculele, vom scdea din ecuaia cu termenul liber cel mai mare, pe rnd fiecare dintre ecuaiile sistemului de restricii. Sistemul de restricii devine: x2 +2x4 +x5 x7 = 1300 x7 = 2100 - x1+x2 - 2x3+x4 x1+2x2+x3+3x4 + x6 x7 = 300 x1 ,x2 , x3 , x4 0 x1 ,x2 , x3 , x4 0. Deci, modelul matematic al problemei de amestec este : Restricia referitoare la cantitate este:xj 0, j=1,..,7 Matricea ataat acestui ultim sistem este :ALGEBR LINIAR I GEOMETRIE45 0 1 0 2 1 0 1 A= 1 1 2 1 0 1 1 1 2 1 3 0 0 1 Ea coine doi vectori unitari a5 i a6, deci nu este nevoie pentru determinarea soluiei iniial de baz dect de o singur variabil artificial, care va fi notat x8 i va fi adugat la ultima restricie. Problema de programare liniar devine : min f =5 x1+4x2+4,5 x3+3x4+Mx8 x2 +2x4 +x5 x7 = 1300 = 300 - x1+x2 - 2x3+x4 x1+2x2+x3+3x4 Tabelul simplex este dat mai jos: 5 CB 0 0 Mfj-cj+ x6 x7 x7 +x8= 2100; xj 0, j=1,..,8. 4,5 a3 0 -2 1M-4,54 a2 1 1 22M-43 a4 2 (1) 33M-3*0 a5 1 0 000 A6 0 1 000 a7 -1 -1 -1-MM a8 0 0 10B a5 a6 a8 a5 a4 a8XB 1300 300 2100 700 300 1200a1 0 -1 1M-5650 300 700 700/4 -0 3 Mfj-cj2 -1 4 4M-8-1 1 -1 -M-1 -3/7 5/7 -1/7-2,54 -2 (7)0 1 01 0 0 0 1 0 00-2 1 -3 -3M+3 -2/7 1/7 -3/7-1,51 -1 2 2M-3 -1/7 -3/7 2/70*0 0 1 0 --1200 77M-0,5* 0 0 0 100 3 4,5fj-cja5 a4 a3100/7-2/70 1 004500/7 1/7 1200/7 4/72700 -2Soluia optim este XoT=( 0,0, funciei de eficien este f min = 2700.1200 4500 100 , , , 0 ,0 ), iar valoarea minim a 7 7 7Pe linia diferenelor f7- c7 = 0, fr ca vectorul a7 s fie n baz.46CAMELIA FRIGIOIUPentru a determina o alt soluie optim vom introduce n baz vectorul a7 i vom construi un nou tabel simplex 5 CB 0 304 a2 -1/2 1/2 -1/2 -2,54,5 a3 1/2 3/2 7/2 03 A4 0 1 0 00 a5 1 0 0 00 a6 -1/2 -1/2 -3/2 -1,50 a7 0 0 1 0B a5 a4 a7XB 100 900 600 2700a1 0 1 2 -2fj -cjSoluia optim obinut este X1T=( 0 , 0 , 0, 900, 100, 0 , 600) . Se poate construi o combinaie liniar convex a celor dou soluii optime care reprezint soluia optim general: X() = X0+(1-)X1, [0,1] Pentru orice [0,1], f(X())=4,5 de eficien rmne minim.1200 1800 +3(900 ) = 2700, adic valoarea funciei 7 7Rezolvarea unei probleme de programare liniar care nu este la nici una din formele canoniceSe aduce problema la forma standard, cu toi termenii liberi ai sistemului de restricii pozitivi. Matricea sistemului adus la forma standard va arta care sunt vectorii coloan unitari existeni i care ar mai trebui adugai pentru a obine o baz unitar. In funcie de acest fapt se adaug variabile artificiale la restriciile potrivite i se modific i funcia de eficien astfel : -dac problema este de minim, atunci se adaug la funcia de eficien iniial, variabilele artificiale cu coeficienii de penalizare M (M pozitiv, foarte mare); -dac problema este de maxim, atunci se adaug la funcia de eficien iniial, variabilele artificiale cu coeficienii de penalizare -M (negativ, practic -) Spunem c problema se rezolv prin metoda penalizrii. Vom construi tabelul simplex, cu baza iniial format din vectori unitari, care pot fi: vectori corespunztori variabilelor problemei sau vectori corespunztori variabilelor de compensare sau vectori corespunztori variabilelor artificiale.-ALGEBR LINIAR I GEOMETRIE47Exemplu de problem care nu admite soluieS se rezolve problema de programare liniar, utiliznd algoritmul simplex: max f = 2x1 + x2 + 2x3 5x1 + x2 + x3 20 -x1 + x2 + x3 = 30 x1, x2 ,x3 0.Soluie. Aducem problema la forma standard adugnd variabila de compensare x4la restricia nti i variabila artificial x5 la restricia a doua . max w = 2x1 + x2 + 2x3 - Mx5 5x1 + x2 + x3+ x4 -x1 + x2 + x3 xj 0 2 CB 0 -Mcj-fj=20 +x5 =30j = 1,5 .1 a2 1 11+M2 a30 a4 1 00-M a5 0 10B a4 a5 a3 a5XB 20 30 20 10a1 5 -12-M20* -(1)12+M*2 -Mcj-fj5 -6 -8-6M1 0 -11 0 01 -1 -2-M0 1 0Ultima iteraie a tabelului de mai sus indic optimalitatea soluiei datorit faptului c toate diferenele sunt j = c j- fj sunt negative sau 0. Totui variabila artificial x5 , a rmas n baz cu valoarea 10, x50; deci problema nu admite soluie.Exemplu de problem care admite optim S se rezolve problema de programare liniar, utiliznd algoritmul simplex: max f = 6x1 + 10x2 x1 - x2 1 -2x1 + x2 2; x1, x2 0.48CAMELIA FRIGIOIUAducem problema la forma standard: max f = 6x1 + 10x2 x1 - x2 +x3 -2x1 + x2 =1 +x 4= 2x1, x2 , x3 , x4 0. Tabelul simplex corespunztor este : 6 CB 0 0cj-fj10 a2 -10 a3 1 000 a4 0 10B a3 a4 a3 a2XB 1 2 3 2 20a1 1 -262(1)10*0 10cj-fj-1 -2 260 1 01 0 01 1 -10Calculele nu mai pot continua, deoarece aplicarea criteriului de intrare n baz indic intrarea vectorului a1, iar toate componentele vectorului care intr n baz sunt negative, adic funcia f poate fi fcut orict de mare.Criteriu de optim infinit. Dac toate componentele vectorului care intr n baz( la o anumit iteraie a simplexului) sunt negative sau nule, problema admite optim infinit. n cazul nostru putem scrie max f = .Dualitatea n programare liniarFiecrei probleme de programare liniar i se poate ataa, ntr-un anumit mod o alt problem de programare liniar, care se numete problema dual, iar problema iniial se numete problema primal.Duala se construiete cu datele primalei. Adesea, ne vom referi la cuplul de probleme primal-dual. Dualitatea care se refer la problemele de prorgamare liniar sub forma canonic se numete dualitate simetric, iar dac problemele nu sunt la una dintre formele canonice, se numete dualitate nesimetric. Regulile de construire a dualei sunt aceleai n ambele tipuri de dualitate.ALGEBR LINIAR I GEOMETRIE49Dualitatea simetricFie problema de programare liniar , care are forma canonic: max f = CT X AXb X0 n care (x1,x2,,xn)T sunt variabilele, CRn, AMmn(R), bRm. Problema are m restricii. Fie vectorul Y= (y1,y2,,ym)T cu m componente.Vom face s corespund fiecrei restricii a problemei (P) una din componentele lui Y. Astfel, restriciei 1 i va corespund y1,, n general restriciei I i va corespunde variabila yI . Aceste variabile se numesc variabilele dualei sau variabile duale. (P)Definiia 4.1. Se numete duala problemei (P), problema de programare liniar:min g = YT b YT A CT Y 0. Definiia 4.2. Fie problema de programare liniar min f = CT X AXb X0 n care X, C Rn, A Mmn(R), bRm. Duala problemei (P1) este problema : max g = YT b YT A CT Y 0. m unde Y R este vectorul variabilelor duale. Se observ c duala lui (D) este chiar (P) i duala lui (D1) este (P1). (D)(P1)(D1)Dualitatea nesimetricDefiniia problemei duale n cazul cnd primala nu este la nici una din formele canonice se va face cu ajutorul tabelului de mai jos ; Primala (P) min (max) x1,x2,,xn, n variabile m restricii A matricea sistemului de restricii CRn coeficienii funciei de Eficien BRm vectorul termenilor liberi Duala (D) max (min) n restricii y1,y2,,ym - m variabile AT matricea sistemului de restricii bRm coeficienii funciei de eficien CRn vectorul termenilor liberi50CAMELIA FRIGIOIURestricia i concordant Restricia i neconcordant Restricia i egalitateyi 0 yi 0 yi oarecare restricia j concordant restricia j neconcordant restricia j egalitate0xj 0 xj oarecareRegulile de construire a dualei pentru cazul dualitii nesimetrice sunt aceleai cu cele pentru dualitatea simetric, cu excepia cazurilor cnd restriciile nu sunt concordante i variabilele nu sunt pozitive.Exemplu. Duala problemei : min f = 3x1 + 2x2 x3 +16 x4x1 - x2 +2 x3 +3x4 2 x2 - 2x3 + x4 10 3x1 + x2 +2 x3 15x1, x2 0 , x3 0, x4 oarecare este problema cu 4 restricii i 3 variabile: max g = 2y1 + 10y2 +15 y3 y1 + 3y3 3 -y1 + y2 + y3 2 2y1 - 2y2 +2 y3 -1 3y1 + y2 = 16 y1, y3 0 , y2 0..5. Probleme1.Un ntreprinztor dispune de mijloacele tehnice necesare pentru a fabrica 4 tipuri de produse,care folosesc dou tipuri de materii prime A i B. Consumurile specifice i cheltuielile pe unitatea de produs, sunt n tabelulul de mai jos: Produse Materii prime A B P1 3 0 P2 2 1 P3 4 2 P4 2 3 Disponibil 300 80ALGEBR LINIAR I GEOMETRIE51Cheltuieli unitare5424Dac i propune s produc n total cel puin 100 uniti,iar din produsul P3 nu mai puin de 20 uniti, cum trebuie organizat producia, asfel nct cheltuielile totale s fie minime? 2.O ntreprindere fabric trei tipuri de produse folosind gaz metan i ap.Consumurile specifice, disponibilul de ap i gaz, precum i beneficiile nete unitare sunt date n tabelul de mai jos: Produse Resurse Ap Gaz metan Beneficiu unitar beneficiului total? b) Dac i propune acelai scop, cu aceleai resurse, dar trebuie s produc cel puin 3000 uniti din P1,cum trebuie organizat producia? 3.n cadrul unei uniti agricole de producie pentru a se experimenta 4 culturi s-a pus la dispoziia unui grup de cercettori un lot avnd suprafaa maxim de 6 ha. Necesarul de for de munc i bani pentru realizarea unui hectar din fiecare cultur i venitul net sunt date n tabelul de mai jos: Culturile Unitatea For de munc Bani investii Venitul net Om/zi Mii u.m./ha Mii u.m./ha A 1 4 2 B 2 7 6 C 3 5 3 D 5 2 4 Disponibil 15 20 Consumuri specifice P1 2 10 10 P2 3 50 15 P3 2 30 25 Disponibil 40.000 t 500.000 mca) Cum se organizeaz producia, dac se urmrete maximizareaS se ntocmeasc planul de cultivare astfel nct venitul net total s fie maxim. 4.O ntreprindere fabric trei tipuri de produse P1,P2,P3 , utiliznd 4 locuri de munc L1,L2,L3,L4 .Necesarul de timp exprimat n ore pentru fabricarea fiecrui produs, capacitile de producie ale celor trei locuri de munc precum i preurile de desfacere ale produselor sunt trecute n tabelulul de mai jos:52CAMELIA FRIGIOIUProdusele Locul de munc L1 L2 L3 L4 Preul unitar de desfacere capacitatea de producie.P1 3 1 0 0 1P2 2 0 1 0 2P3 1 0 0 1 3Capacitile de Producie 15 10 5 5S se determine structura optim a produciei, tiind c L1 folosete toat 5.Din dou alimente A1 i A2 se obin trei principii nutritive N1,N2,N3. Costul unei uniti de aliment, cantitatea de principiu nutritiv coninut ntr-o unitate de produs i necesarul de uniti din fiecare principiu nutritiv sunt date n tabelul de mai jos: A1 N1 N2 N3 Cost unitar fie minim. 6.S se rezolve problemele: a) min f = 3x1 - 2x2 + x3 3x1 + x2 - 2 x3 = 2 4x1 +3x2 +2 x3= 1 x1, x2 , x3 0 b) max f = 3x1 + 2x2 x3 +16 x4 3x1+2x2+5x3+4x4 8 x1+x2+2x3+x4 4 x1, x2 , x3 ,x4 0 . 0,3 0,4 0,1 2 A2 0,1 0,3 0,2 1 Necesar 0,3 0,6 0,2S se determine cantitile x1,x2 din cele dou produse astfel nct preul dietei s7. O main produce trei produse P1,P2,P3.Produsul P1 aduce ntreprinderii un venit de 3 u.m. pe unitatea de produs, P2 de 12 u.m. iar P3 de 4 u.m. Randamentul mainii este de 75, 25 i respectiv 50 buci/or pentru P1,P2,P3. Vnzrile sunt limitate pentru P1 la 1500, pentru P2 la 500 i pentru P3 la 1000 buci.tiind c maina lucrez sptmnal 45 ore, s se determine repartiia produciei, astfel nct beneficiul s fie maxim.ALGEBR LINIAR I GEOMETRIE538.S se rezolve urmtoarele probleme de programare liniar: a) min f = 4x1 + 8x2 +3x3 2x1 + x2 +3x3 4 5x1 + 2x2 +7x3 8 x1, x2,x3 0 c) max f = 4x1 + x2 +6 x3 2x1 +3x2 +x3 7 3x1 + x2 +x3 11 x1, x2, x3 0 e) min f = 9x1 + 3x2 +2 x3 4x1 + x2 +5 x3 = 7 3x1 + x2 +4 x3 5 x1, x2 , x3 0 g) max f = x1 + 3x2 +6x3 5x1 +2x2 +3x3 =11 3x1 + x2 +2x3 8 x1, x2 , x3 0 h) min f = 6x1 + x2 x1 +2 x2 3 3x1 + x2 4 x1, x2 0 b) max f = 10 x1 +15 x2 2x1 +4x2 40 6x1 +2x2 60 x1, x2 0 d) min f = x1 +3x2 4x3 - 2x4 -9x5 x1 + x3 x4 x5 = 3 - 3x5 = -1 x1 +x2 2x3x1, x2, x3 ,x4, x5 0 f) max f = x1 + 2x2 +3x3 - x4 x1 +2x2 +3x3 2 x1+ x2 + 5x3 =15 =20x1 +2x2 + x3 +x4 =10 x1, x2 ,x3,x4 0.54ALGEBR LINIAR I GEOMETRIEGEOMETRIE ANALITICCAPITOLUL 1 VECTORI LIBERI 1. Vectori liberi Fie E3 spaiul punctual tridimensional al geometriei elementare i AB un segment orientat (fig.1).Figura 1 Punctul A se numete originea, iar punctul B se numete extremitatea segmentului orientat AB . Dreapta determinat de punctele A i B se numete dreapta suport a luiAB . Aceast dreapt este unic determinat dac A B. n cazul, n care A B se obine /segmentul orientat nul i dreapta lui suport este nedeterminat. Dou segmente orientate se numesc coliniare (respectiv paralele) dac dreptele lor suport coincid (respectiv sunt paralele). Definiia 1.1. Dou segmente orientate nenule au aceeai direcie dac dreptele lor suport sunt paralele sau coincid. Direcia unui segment orientat nul este nedeterminat. Pe o dreapt se pot stabili dou i numai dou sensuri de parcurs (ordini ale punctelor dreptei) pe care le notm prin sgei (fig.2).Figura 2 O dreapt mpreun cu un sens de parcurs fixat se numete dreapt orientat. Un segment orientat nenul, AB , determin unic dreapta AB i un sens de parcurs pe aceast dreapt sensul de la A ctre B.ALGEBR LINIAR I GEOMETRIE55Definiia 1.2. Dou segmente orientate, nenule, coliniare au acelai sens dac sensurile determinate pe dreapta suport comun coincid. Dou segmente orientate nenule, paralele au acelai sens dac extremitile lor se afl n acelai semiplan determinat de dreapta care unete originile segmentelor (fig. 3), n planul dreptelorsuport paralele. Figura 3 Admitem c sensul unui segment orientat nul este nedeterminat. Lungimea (norma sau modulul) unui segment orientat AB se definete ca fiind lungimea segmentului neorientat [AB], adic distana dintre punctele A i B i se noteaz AB . Un segment orientat are lungime zero dac i numai dac el este segmentul nul. Dou segmente neorientate care au aceeai lungime se numesc congruente. Definiia 1.3. Dou segmente orientate ale caror segmente neorientate corespunztoare sunt congruente se numesc segmente orientate cu aceeai lungime. Definiia 1.4. Dou segmente orientate, nenule se numesc echipolente dac au aceeai direcie, acelai sens i aceeai lungime. Dac AB este echipolent cu CD , atunci vom nota AB ~ CD . Teorema 1.1. Relaia de echipolen pentru segmente orientate nenule este o relaie de echivalen. Definiia 1.5. Clasele de echivalen ale segmentelor orientate, relativ la relaia de echipolen se numesc vectori liberi. Direcia, sensul i lungimea care sunt comune segmentelor orientate ce definesc un vector liber se numesc direcia, sensul i lungimea vectorului liber. Vectorii liberi vor fi notai cu litere mici i bar deasupra a , b , c , i vor fi reprezentai n desen printr-unul din segmentele orientate care definesc clasa de echivalen, numit vector liber. Vectorii liberi se mai pot nota i prin AB , CD , Fiecare segment orientat din clasa numit vector liber este un reprezentant al clasei i notm AB AB . Pentru lungimea (norma) unui vector liber a folosim notaia || a ||.56ALGEBR LINIAR I GEOMETRIEUn vector liber de lungime unu se numete versor. Vectorul liber care are lungimea zero se numete vector nul, se noteaz cu . Reprezentanii vectorului nul sunt segmentele orientate AA cu A E3. Vectorii liberi care au aceeai direcie se numesc coliniari. Doi vectori coliniari care au aceiai lungime, dar au sensuri opuse se numesc vectori opui. Dac unul dintre ei este notat cu a , atunci opusul su este notat (- a ) (fig. 4).Figura 4 Doi vectori liberi a i b sunt egali i se noteaz a = b , dac au un reprezentant comun, adic au aceeai direcie, acelai sens i aceeai lungime. Notm cu E 3 mulimea tuturor vectorilor liberi din spaiul E3. 2. Spaiul vectorial al vectorilor liberi E 3 Adunarea vectorilor liberiSe poate defini pe mulimea vectorilor liberi E 3 adunarea vectorilor liberi prin regula triunghiului (sau regula paralelogramului). Astfel E 3 va avea mpreun cu aceasta o structur de grup aditiv comutativ. Definiia 2.1. Fie a i b doi vectori liberi. Fie OA un reprezentant al vectorului a i AB un reprezentant al vectorului b . Vectorul liber c reprezentat de segmentulorientat OB se numete suma vectorilor a i b i se noteaz c = a + b unde OB = OA + AB (fig.5).Adunarea vectorilor liberi: +: E 3 x E 3 E 3 (a , b ) a + b este o lege de compoziie intern, bine definit deoarece vectorul liber c = a + b nu depinde de alegerea punctului O.Regula din definiia 2.1. se numete regula triunghiului.ALGEBR LINIAR I GEOMETRIE57Figura 5Figura 6Teorema 2.1. Adunarea vectorilor liberi are urmtoarele proprieti:1) asociativitatea: a , b , c E 3, a + ( b + c ) = ( a + b ) + c ; 2) este element neutru: a E 3, a + = + a = a ; 3) opusul lui a este simetricul lui a : a E 3, a + (- a ) = (- a ) + a = ;Figura 74) comutativitatea : a , b E 3, a + b = b + a . De aici, se obine o nou regul pentru determinarea sumei a doi vectori necoliniari, numit regula paralelogramului. Folosind aceast regul, suma a doi vectori a i b are ca reprezentant segmentul orientat, care este diagonala paralelogramului construit cu reprezentanii celor 2 vectori ca laturi, avnd originea comun. Aceasta nseamn c vectorul sum este un vector care are direcia diagonalei, originea reprezentantului sumei este comun cu cea a reprezentanilor celor 2 vectori, modulul este egal cu lungimea diagonalei (fig.6). Asociativitatea adunrii vectorilor liberi permite generalizarea regulei triunghiului la regula poligonului pentru n 3 vectori.Definiia 2.2. Suma vectorilor a1 , a 2 ,... a n este vectorul liber al crui reprezentantnchide poligonul, ale crei laturi sunt reprezentani ai vectorilor termeni, astfel nct58ALGEBR LINIAR I GEOMETRIEextremitatea reprezentantului lui a1 este origine pentru reprezentantul lui a 2 , iar originea lui a 3 este extremitatea lui a 2 , .a.m.d. Teorema 2.1. arat c (E 3,+) are o structur de grup abelian (comutativ). Fiind dai doi vectori a i b suma dintre vectorul a i opusul vectorului b se numete vectorul diferen al vectorilor a i b i se noteaz c = a - b . Deci c = a + (- b ).Figura 8 Dac OA este reprezentant al lui a i AC este reprezentantul lui (- b ), atunci segmentul OC (conform regulei triunghiului) va fi reprezentant al diferenei c = a - b (fig.8).nmulirea unui vector cu un scalarFie R cmpul numerelor reale i E 3 grupul aditiv al vectorilor liberi. Definim o lege de compoziie extern, definit pe R x E 3 cu valori n E 3 numit nmulirea unui vector liber cu un scalar astfel: pentru orice R i a E 3 vectorul a este coliniar cu a , adic: 1) dac a i 0 atunci a are aceeai direcie cu a , acelai sens pentru > 0 i sens contrar dac < 0 i lungimea egal cu || || a ||; 2) Dac =0 sau a = atunci a = .Teorema 2.2. nmulirea vectorilor cu scalari are urmtoarele proprieti: 1) , R , a , b E 3, ( a + b ) = a + b (distributivitatea fa de adunarea vectorilor) 2) ,R, a E 3, (+) a = a + a (distributivitatea fa de adunarea scalarilor)3) , R, a E 3, ( a ) = () a 4) a E 3, 1 a = a .Teoremele 2.1 i 2.2 arat c E 3 mpreun cu adunarea vectorilor i nmulirea unui vector cu un scalar este un spaiu vectorial real.ALGEBR LINIAR I GEOMETRIE59 3. Vector de poziieAlegem n E3 un punct O, numit origine. Oricrui alt punct M din E3 i corespunde un vector i numai unul r E 3 al crui reprezentant este OM. Reciproc, oricrui vector r i corespunde un punct i numai unul M, astfel nct OM s l reprezinte pe r . Mulimile E3 i E 3 sunt n coresponden biunivoc, bijecia fiind unic determinat prin fixarea originii O. Vectorul liber r = OM se numete vectorul de poziie al punctului M fa de originea O. Cunoscnd vectorii de poziie ai punctelor M1( r 1) i M2( r 2), obinem M1M2 = OM 2 - OM 1 = r 2 - r 1 (fig.9).Figura 9 ntre vectorii determinai de trei puncte oarecare din spaiu M1, M2, M3 (fig. 10) avem relaia evident M1M2 + M2M3 + M3M1 = . Aceast relaie se numete relaia lui Chasles. Vectorul de poziie al mijlocului M al segmentului M1M2 este dat de formula (fig.11):r =ntr-adevr OM = OM 1 + M1M = OM 1 +r1 + r 2 21 r 2 - r1 r1 + r 2 M1M 2 = r 1 + = . 2 2 2Figura 10Figura 11Aplicaie. Vectorul de poziie al centrului de greutate al unui triunghi.Fie triunghiul M1M2M3 (fig. 12) unde cu M1, M2, M3 am notat mijloacele laturilor M2M3, M3M1 i respectiv M1M2. tim c dac M2 i M3 au vectorii de poziie r 2 i r 3 fa60ALGEBR LINIAR I GEOMETRIEde un pol oarecare (care nu este indicat n figur), atunci M1 fa de acest pol va avea vectorul de poziie r2 + r3 . 2Fie G centrul de greutate al triunghiului. El se afl pe M1M1 astfel nct M1G = 2 GM 1 .Atuncir G - r 1 = 2(r2 + r3 - r G) 2r 2 + r 3 + r1 . 3 Deci, centrul de greutate al triunghiului, punctul G are vectorul de poziie r1 + r 2 + r 3 rG= 3 unde r i (i = 1, 2, 3) sunt vectorii de poziie ai vrfurilor (fig.12). 3r G = r 2 + r 3 + r 1 r G =Figura 12 4. Coliniaritate i coplanaritateFie E 3 spaiul vectorial real al vectorilor liberi. Oricrui vector a de lungime || a || 1 a , numit versorul lui a . > 0, i se asociaz un vector a 0 = || a || Versorul lui a are aceeai direcie i sens cu a dar are lungimea egal cu 1. Putem scrie a = || a || a 0. Teorema 4.1. Fie a , b E 3. Dac a i b sunt coliniari i a , atunci exist un numr real t unic astfel nct b = t a . Propoziia 4.1. Mulimea V1={ b E 3| tR b =t a ; a } a tuturor vectorilor coliniari cu un vector nenul a , este un subspaiu vectorial unidimensional al lui E 3. Intr-adevr V1 este subspaiul generat de vectorul nenul a i are dimensiunea 1.ALGEBR LINIAR I GEOMETRIE61Observaia 4.1. Coliniaritatea a doi vectori liberi este echivalent cu dependenaliniar a acestora. De aceea oricare doi vectori liberi, nenuli, necoliniari sunt liniari independeni.Definiia 4.1. Fie a , b , c trei vectori nenuli, distinci din E 3. Ei se numesc coplanari, dac segmentele orientate care i reprezint sunt paralele cu un plan dat. Teorema 4.2. Vectorii nenuli a , b , c sunt coplanari dac i numai dac ei suntliniar dependeni.Consecin. Mulimea V2={ c E 3 | r,s R, c =r a +s b , a , b necoliniari}a tuturor vectorilor coplanari cu doi vectori necoliniari a i b este un subspaiu vectorial al lui E 3 bidimensional. ntr-adevra ,bfiind necoliniari formeaz o mulime de vectori liniarindependeni care genereaz pe V2.Observaia 4.2. Liniar dependena a trei vectori liberi, nenuli, fiind echivalent cucoplanaritatea acestora, rezult c orice trei vectori liberi, nenuli, necoplanari sunt liniar independeni.Teorema 4.3. Spaiul vectorial E 3 are dimensiunea 3. Demonstraie. n E 3 exist trei vectori liniar independeni i anume oricare treivectori necoplanari a , b , c . Artm c acetia genereaz pe E 3. Fie d un al patruleavector i OA , OB , OC , OD reprezentanii vectorilor a , b , c , d (fig. 13). Se observ c OD = OD 1 + OD 2 + OD 3 = r OA + s OB + t OC i deci d = ra + sb + tc .g62ALGEBR LINIAR I GEOMETRIEDac { a , b , c } este o baz fixat n E 3 i r, s, t sunt coordonatele lui d n raport cu aceast baz, atunci vom nota d = (r,s,t). n acest context pentru vectorii d i = (ri,si,ti) i = 1,2,3, avem: 1) d 1= d 2 r1 = r2, s1= s2, t1= t2; 2) d 1 + d 2 = (r1 + r2, s1 + s2, t1 + t2); 3) k d 1 = (kr1,ks1,kt1), kR; 4) d 1 este coliniar cu d 2 dac i numai dac coordonatele lor sunt proporionale; 5) vectorii d 1, d 2, d 3 sunt coplanari dac i numai dac coordonatele unuia dintre ei sunt combinaii liniare ale coordonatelor celorlali doi: r3 =r1+r2, s3 = s1+s2; t3 =t1+t2, , R . 5. Proiecie ortogonalFie dreapta i un punct M, exterior dreptei (fig. 14). Dac prin punctul M construim planul PM perpendicular pe , acest plan va ntlni dreapta n punctul M. Punctul M se numete proiecia ortogonal a punctului M pe dreapta . Planul PM se numete planul proiectant.Figura 14 Fie a un vector liber, nenul i un reprezentant al su AB , iar 1 este o dreapt. Prin A i B construim planele proiectante pe dreapta 1, notate cu PA i PB (fig.15). Notm cu {A} = 1 PA, {B} = 1 PB.Teorema 5.1. Vectorul liber A' B' nu depinde de segmentul orientat AB careeste reprezentantul vectorului a .ALGEBR LINIAR I GEOMETRIE63Definiia 5.1. Vectorul liber A' B' se numete proiecia ortogonal a vectoruluia pe dreapta 1 i se noteaz 1 ( a ).Figura 15Teorema 5.2. Dac 1 i 2 sunt drepte paralele, a un vector liber, atunci ( a ) = 2 ( a ).1Notm cu u un vector liber nenul i u 0 versorul su, adic u = || u || u 0, || u 0|| = 1. Pentru orice a , vectorul u ( a ) numit proiecia vectorului a pe vectorul u este coliniar cu u 0 i exist un numr real pru a astfel nct (fig. 16): u ( a ) = ( pru a ) u 0.Figura 16Definiia 5.2. Numrul real pru a definit prin relaia precedent se numetemrimea algebric a proieciei ortogonale u ( a ).Definiia 5.3. Fie a , b E 3 \{ } i OA , OB segmente orientate care suntreprezentanii lui a respectiv b . Unghiul [0,] determinat de OA i OB se numeteunghiul dintre vectorii a i b . Definiia nu depinde de pu