1267

UNIVERSITATEA „EFTIMIE MURGU” REŞIŢA FACULTATEA DE ŞTIINŢE ECONOMICE ŞI ADMINISTRATIVE CENTRUL DE ÎNVĂŢĂMÂNT LA DISTANŢĂ

ALGEBRĂ LINIARĂ

Prof.univ.dr. Constantin Popp

- 2001 -

1

Prefaţă Pentru a uşura urmărirea materialului, se vor utiliza următoarele

! " # $

Important

Sfat

Avertizare

Detalii

semne cu semnificaţii speciale, în partea exterioară a paginii:

! Important. Cu acest simbol sunt marcate elementele esenţiale pentru înţelegerea materialului.

" Sfat. Acest semn sugerează comentarea unor noţiuni, dându-se mai multe detalii, precum şi prezenţa unor teoreme sau proprietăţi..

# Avertizare. Va fi avertizat cititorul asupra unor greşeli tipice, multe desprinse din experienţa personală.

$ Detalii. Sunt furnizate detalii suplimentare, pentru a creşte gradul de detaliere al explicaţiilor. Pentru a realiza autocontrolul însuşirii noţiunilor prezentate, subcapitolele sunt însoţite de întrebări şi exerciţii. Răspunsurile şi soluţiile acestora se pot trimite la sediu Centrului ID prin poşta, sau se pot trimite prin e-mail, la adresa [email protected]. Există şi două teste de control, câte unul la sfârşitul fiecărei părţi, care verifică capacitatea de sintetizare a materialului acumulat.

2

Cap. 1. ELEMENTE DE ALGEBRĂ LINIARĂ În prima parte, a cărei parcurgere necesită circa două ore, sunt reamintite cunoştinţele despre matrice învăţate în clasa a XI-a, la disciplina de Algebră. Aceste prime trei subcapitole nu reprezintă un scop în sine, ci ţelul lor este de a pregăti cititorul pentru introducerea noţiunilor noi din paragrafele următoare. 1.1. Generalităţi despre matrice. Se numeşte matrice o mulţime de mn numere (elemente) aranjate într-un tablou cu m linii şi n coloane (de tipul m×n). Astfel, o matrice dreptunghiulară este:

% Matrice

 a11  a A =  21 "  a  m1

a12 a 22 " am2

! a1n   ! a2n  "   ! a mn 

Folosind elementul generic aij (i = 1, m; j = 1, n) , matricea se notează prescurtat: A = (a ij ) m×n , elementele sale fiind numere reale

%

Matrice pătrată

sau complexe. Dacă m=n, atunci matricea este pătratică (pătrată). Unei matrice pătrate (aij ) n×n i se asociază un număr numit determinant, care se calculează după regulile curente din algebra de a

liceu (clasa a XI )

% Determinant

det A =

a11 # a1n a n1 # a nn

Dacă A≥a, a∈R înseamnă că toate elementele matricei sunt mai mari ca a; la fel dacă A≥0, elementele matricei sunt nenegative. O matrice cu toate elementele nule se numeşte matrice nulă sau matrice zero: Om×n. Matricea de dimensiune 1×n se mai numeşte vector linie iar cea de tipul m×1 se numeşte vector coloană. Elementele aii , i = 1, n formează diagonala principală a matricei iar suma elementelor de pe diagonala principală se numeşte urma matricei.

3

%

Matrice nulă Vector linie Vector coloană Urma maricei

!

Matrice nesingulară (cea cu determinant

!

Matrice triunghiulară. Matrice diagonală Matrice scalară Sibolul lui Kronecker

Dacă A este o matrice pătrată şi det A≠0, atunci A se numeşte nesingulară sau nedegenerată, iar dacă det A=0 se numeşte singulară sau degenerată. O matrice pătrată este triunghiulară dacă toate elementele sale situate de o parte a diagonalei principale sunt nule, iar determinantul ei este egal cu produsul elementelor de pe diagonala principală. Dacă elementele situate de ambele părţi ale diagonalei principale sunt nule, atunci matricea se numeşte matrice diagonală. Dacă într-o matrice diagonală elementele sunt egale între ele, aii=k, avem o matrice scalară şi se poate scrie prescurtat: K=(kδij)n unde δij este simbolul lui Kronecker: 0, i ≠ j δ ij =  1, i = j

!

notează de obicei cu E, U sau I indicându-se şi ordinul (dimensiunea).

Matrice unitate

Fiecărui ordin de matrice pătrată îi corespunde o matrice unitate:

Matricea scalară în care k=1 se numeşte matricea unitate şi se

En=(δij)n sau Un sau In. De exemplu: 1  0 U4 =  0  0

!

0 0 0  1 0 0  0 1 0  0 0 1

Matricea -A=(-aij)m×n se numeşte opusa matricei A=(aij)m×n. Dacă A=(aij)n×n=(aij)n atunci: det (-A)=(-1)ndet A.

Matricea opusă

O matrice pătrată este simetrică dacă aij = a ji (∀) i, j = 1, n şi antisimetrică dacă aij = - a ji (∀) i, j = 1, n . Din aii=-aii rezultă aii=0,

!

adică elementele de pe diagonala principală a unei matrice

Matrice simetrică Matrice antisimetrică

Două matrice A şi B de acelaşi tip sunt egale dacă elementele lor

antisimetrice sunt nule. analoge aij şi bij sunt egale, adică: A = B ⇔ aij = bij , ( ∀ ) i = 1, m şi j = 1, n Egalitatea matricelor reducându-se la egalitatea a mn numere (elementele matricelor) are aceleaşi proprietăţi ca şi egalitatea 4

numerelor. Dacă două matrice pătrate sunt egale, determinanţii lor sunt egali (reciproc nu!). Teme 1. Definiţi noţiunile de matrice, matrice pătrată, matrice nulă, vector linie şi vector coloană. 2. Daţi exemplu de matrice singulară şi unul de matrice nedegenerată. 3. Precizaţi pentru fiecare dintre următoarele matrice dacă este scalară, diagonală şi triunghiulară. 2   2 1 3   0 A =  0 2 3 , B =  0  0 0 5    0 

0 3 0 0

0 0 4 0

0  4 0 0 2 0 1     0 , 0 4 0 , 0 0 2 C = D =     0  0 0 4  0 0 4      0 

1.2. Operaţii cu matrice 1) Suma şi diferenţa a două matrice de acelaşi tip este tot o matrice de acelaşi tip. Fie A=(aij)m×n, B=(bij)m×n. Avem A+B=C, unde C=(cij)m×n şi cij = aij + bij (∀) i = 1, m; j = 1, n . Zicem că adunarea este o operaţie internă (interioară) în mulţimea

%

Suma şi diferenţa matricelor

M a matricelor de acelaşi

tip.

"

Proprietăţile adunării: 1. A+B=B+A (comutativitate)

Proprietăţile adunării

2. (A+B)+C=A+(B+C) (asociativitate) 3. A+0=0+A=A (matricea 0 - neutră la adunare) 4. A+(-A)=(-A)+A=0 (matricea opusă) Vedem deci, că mulţimea matricelor de acelaşi tip formează grup aditiv abelian (comutativ). Diferenţa matricelor A şi B de acelaşi tip este A-B=A+(-B)=D, unde D=(dij)m×n, d ij = aij − bij (∀) i = 1, m; j = 1, n . În particular, suma sau diferenţa a două matrice triunghiulare (superior sau inferior) este tot o matrice triunghiulară. La fel şi în cazul a două matrice diagonale. 2) Înmulţirea unei matrice cu un scalar (număr algebric). 5

$ Grup este un ansamblu format dintr-o mulţime şi o operaţie definită între elementele ei, ce are proprietea de asociativitate, un element neutru şi orice element este inversabil

!

Înmulţirea matricelor cu un scalar

"

Fie A=(aij)m×n şi λ un scalar. Avem λA=(λaij)m×n. În particular, dacă λ=-1 se obţine opusa lui A. Fie acelaşi tip şi

Spaţiul vectorial este un ansablu format din grupul prezentat pe pagina precedentă şi corpul scalarilor

mulţimea matricelor de

mulţimea scalarilor. Operaţia λA este o operaţie

externă a mulţimii M definită prin intermediul mulţimii S. Proprietăţi:

1. λ(A+B)=λA+λB (dubla distributivitate 2.(λ 1+λ 2)A=λ 1A+λ 2A în M şi S)

3.(λ 1λ 2)A=λ 1(λ 2A)=λ 2(λ 1A) (asociativitate în S)

Proprietăţile înmulţirii cu scalari

$

S

M

4.(∃)1∈S astfel încât 1⋅A=A⋅1=A (element unitate în S) Pe baza proprietăţilor (axiomelor) adunării şi respectiv înmulţirii cu un scalar, tragem concluzia că mulţimea M formează spaţiu liniar (sau vectorial). 3) Înmulţirea matricelor A şi B are sens dacă numărul de coloane ale lui A este egal cu numărul de linii ale lui B, adică: A=(aij)m×n şi B=(bij)n×p.

!

Se defineşte A⋅B=C=(cij)m×p, unde: n

cij = ai1 b1j + ai 2 b2j + # + ain b nj = ∑ aik bkj ; i = 1, m; j = 1, p

Înmulţirea matricelor

k =1

În general: AB≠BA. Mai mult, dacă AB este o operaţie posibilă, operaţia BA este posibilă numai dacă numărul liniilor lui A este egal cu numărul coloanelor lui B.

"

Proprietăţi: 1. A(BC)=(AB)C - asociativitate

Proprietăţile înmulţirii matricelor

2. A(B+C)=AB+AC - distributivitate faţă de adunare 3. λ(AB)=(λA)B=A(λB) - asociativitate faţă de un scalar 4. A⋅0=0

#

Înmulţirea matricelor nu este comutativă

Observaţie: Dacă A şi B sunt matrice pătrate de acelaşi ordin, atunci AB şi BA sunt posibile dar în general AB≠BA. Dacă totuşi AB=BA, matricele A şi B sunt permutabile, de exemplu: a2 + b2 a − b  a b , B =   ⇒ AB = BA =  A =   b 2a   − b 0  − ab 6

ab   b 2 

Produsul dintre o matrice scalară şi o matrice pătrată, de acelaşi ordin, este egal cu produsul dintre scalarul k (de pe diagonala principală) şi matrice. În particular, dacă k=1 atunci K=U şi UA=AU=A, adică matricea unitate este elementul unitate (sau de efect nul) la înmulţirea matricelor pătrate. Dacă A=(aij)n şi B=(bij)n atunci det(AB)=det A⋅ det B. Produsul a două matrice pătrate nesingulare este o matrice pătrată nesingulară şi reciproc. Spre deosebire de cazul determinanţilor, produsul a două matrice pătrate poate fi nul fără ca una din matricele factori să fie nulă. De exemplu:  0 0  0 0  0 0  ⋅   =   = 0 2 A ⋅ B =  1 0 2 3 0 0       În acest caz, zicem că A şi B sunt divizori ai lui zero. Deoarece BA≠0, A este divizor la stânga şi B divizor la dreapta. Teme 1. Efectuaţi A+C, A⋅D. Se poate efectua A+B ? Dar A⋅B ? Dar B⋅A ?

2   2 1 3   0 A =  0 2 3 , B =  0  0 0 5    0 

Divizori ai lui zero

0 0 0   4 0 0 2 0 1     3 0 0 = = C D , 0 4 0 , 0 0 2     0 4 0     0 0 4 0 0 4     0 0 0

1.3. Matricea transpusă şi matricea inversă. Fie A=(aij)m×n. Transpusa matricei A se obţine schimbând liniile cu coloanele, adică: AT=(aij)n×m. Proprietăţi:

%

T

T

T

T

Transpusa matricei

T T

1. (A+B) =A +B

3. (A ) =A

T

T

2. (kA) =k⋅A

%

T

T

4. (AB) =B A T

Dacă A=(aij)n este simetrică, atunci A =A i reciproc. Dacă A este antisimetrică, atunci: AT+A=0. O matrice este inversabilă dacă este pătrată şi nesingulară. Fie A=(aij)n şi det A=k≠0 Atunci (∃) A-1 astfel încât AA-1=A-1A=Un. Determinarea matricei inverse presupune efectuarea următoarelor operaţii: - se calculează det A=k≠0 (în caz contrar nu are sens A -1) 7

"

Proprietăţile transpusei matricei

%

Matrice inversabilă

T

" Calculul inversei unei matrice

- se scrie A

* - se scrie A (matricea asociată sau adjuncta lui A), înlocuind

toate elementele aij ale transpusei prin complementele lor algebrice Aij i+j

unde Aij=(-1) Mij (Mij fiind minorul elementului aij) - se împart elementele matricei asociate cu k. 1 Deci : A −1 = A* k

"

Proprietăţi:

-1 -1 -1 1.AA =A A=U (permutabile) şi detA⋅detA =1(reciproce)

2. Dacă A=(aij)n şi B=(bij)n iar AB=U atunci matricele

Proprietăţile inversei matricei

sunt nesingulare şi una este inversa celeilalte. -1 -1 -1 -1 -1 -1 3. (A⋅B) =B ⋅A şi în general:(A1A2 … An) =An … A1 -1 T

T -1

4. (A ) =(A ) -1 -1

5. (A ) =A Teme 1. Calculaţi inversa matricei A. Este matricea B inversabilă ?

2   2 1 − 3   0 A =  0 2 3 , B =  0 0 0 1     0 

0 0 0  3 0 0 0 4 0  0 0 0 

Rezumat Matricea unitate este matricea care are toate elementele de pe diagonala principală egale cu 1, iar celelalte egale cu 0. Matricea ce are determinantul nenul se numeşte inversabilă sau nedegenerată. Inversa ei se poate calcula conform metodei studiate în cala a XI-a şi este acea matrice care înmulţită cu matricea iniţială furnizează ca rezultat matricea unitate. Suma şi produsul matricelor se calculează, aşa cum s-a studiat în liceu „element cu element”. Produsul a două matrice, dacă are sens, se calculează însumând produsul câte unui element din fiecare linie a primei matrice cu câte un element din fiecare coloană a celei de-a doua matrice. Test de evaluare 1. Daţi exemplu de o matrice care nu este inversabilă 25 puncte 2. Daţi exemplu de două matrice care nu se pot înmulţi 25 puncte 3. Daţi câte un exemplu de matrice triunghiulară, diagonală, pătratică şi scalară 40 puncte 8

1.4. Operaţii cu matrice prin partiţionare Acest subcapitol, al cărui studiu necesită circa două ore propune o abordare alternativă a noţiunilor prezentate în primele trei. Scopul său este desprinderea treptată a cititorului de tiparele din liceu. Prin partiţionarea unei matrice A=(aij)m× n se înţelege împărţirea acesteia în submatrice (blocuri) Aij, prin linii orizontale şi verticale. De exemplu,

!

Partiţionarea matricei

 2 - 1 ! 1 0    - 1 1 ! 0 1    A11 A =  " " " " " =      A21 ! 2 - 1  1 0    0 1 ! - 1 1

A12    A22 

 2 - 1 unde: A11 = A22 =   , A12=A21=U.  - 1 1 În general, A=(aij)m×n

 A11 # A1q    se poate partiţiona în A =  ! A pq  A   p1 # A pq 

unde A11, …, A1q, …, Ap1, …, Apq sunt blocurile sau submatricele lui A. În particular, are loc descompunerea în linii (vectori linii),

"

 L1   L1 = ( a11" a1n )    A =  !  unde: """"""", L   = ( a "a ) m1 mn  m  Lm

Partiţionarea matricei în linii

precum şi descompunerea în coloane (vectori coloane):

"

 a11   a1n      A=(K1 … Kn) unde: K 1 =  !  ," , K n =  !  a  a   m1   mn 

Partiţionarea matricei în coloane

Operaţiile cu matrice sunt valabile şi în cazul partiţionării. Operaţiile cu matrice prin partiţionare, în special determinarea inversei, sunt avantajoase de aplicat atunci când unele din submatrice sunt matrice zero sau unitate. Două matrice sunt egale când se pot partiţiona în submatrice egale.

9

Suma a două matrice partiţionate în acelaşi mod este egală cu matricea care are ca submatrice suma submatricelor termeni. În cazul operaţiei de înmulţire prin partiţionare, partiţionarea matricelor trebuie

"

făcută astfel încât să se poată efectua înmulţirea submatricelor (blocurilor).

Calcularea sumei a două matrice prin partiţionare

De exemplu, pentru :

 a11   a 21 A=#   a31   a 41

a13   a 23   A11 A12  ; #  =    A21 A22  a33   a 43   b11 b12 ! b13     b21 b22 ! b23   B11 B12   = B= # # # #   B21 B22    b   31 b32 ! b33  a12 ! a 22 ! # # a32 ! a 42 !

Avem:

 A11 B11 + A12 B21 AB =    A21 B11 + A22 B21

A11 B12 + A12 B 22    A21 B12 + A22 B 22 

Determinarea inversei prin partiţionare se bazează pe posibilitatea partiţionării unei matrice unitate în submatrice unitate şi submatrice zero şi pe proprietatea că produsul dintre o matrice şi inversa sa este o matrice unitate.

" Calcularea produsului a două matrice prin partiţionare

U m Din AB calculat mai sus şi AB =   0

0   , prin identificare, U n −m 

se obţine sistemul de ecuaţii matriceale:

 A11 B11 + A12 B 21 = U m   A11 B12 + A12 B 22 = 0   A21 B11 + A22 B 21 = 0  A21 B12 + A22 B 22 = U n -m din care se deduc blocurile B11, B12, B21, B22. Calculul se simplifică dacă cunoaştem inversa matricei A11, care este nesingulară de ordinul m
 A 0 , B =  V 1  obţinută prin bordarea matricei nesingulare A=(bij)n cu vectorul linie V1×n şi vectorul coloană 0n×1 completaţi cu un ultim element egal cu 1. Notând:  B11 V 2  -1  B =   α  V1  sistemul devine: AB11=Un, AV2=0, VB11+V1=0, VV2+(α)=(1), de unde: -1 -1 B11=A , V2=0, V1=-VA , α =1.

Rezultă:  A −1 B =   − VA −1 -1

0  1

Exemplu: Să se calculeze B-1 dacă:  1 0 - 1 ! 0    2 1 0 ! 0   B=  1 -1 0 ! 0    " " " " "   ! 1  1 -2 3 Matricea este de forma:  A 0  B =  V 1 unde:  1 0 - 1    A-1 0  -1  A =  2 1 0  ,V = ( 1 - 2 3 ), iar B =    1    - VA 1  1 1 0   Mai întâi determinăm A-1. Det A=3≠0

11

" Calcularea inversei unei matrice prin partiţionare

 0 1 2 1  0 +1 +1    *   −1  T A =  0 1 − 1, A =  0 + 1 − 2 , A = 0  −1 0 0  − 3 +1 +1      −1 

1 1   3 3  1 2 −  3 3 1 1   3 3 

Apoi:   0    -1 VA = ( 1 - 2 3 )  0   −1  

1 3 1 3 1 3

 1  3   2 = - 3 -   3   1  3

2 3

 8  3

Deci: 1 1 0  0   3 3      0 1 2 0   3 3   -1 B =  - 1 1 1 0   3 3     2 8 1  3   3 3   Teme 1. Calculaţi inversa matricei A, prin partiţionarea propusă. Apoi calculaţi A⋅B prin partiţionare.

 2 1 − 3 2 0 1     A =  0 2 3 , B =  0 − 1 6  0 0 1  1 0 1    

2. Calculaţi pentru matricele din exerciţiul precedent produsul B⋅A. Verificaţi dacă A⋅B=B⋅A. Rezumat Operaţiile cu matrice prezentate în subcapitolele precedente pot fi efectuate prin partiţionare adică prin divizarea matricelor în blocuri, iar calculele se vor face între acestea. 12

Câteodată, se pot obţine soluţiile mai uşor prin partiţionare, cu un număr mai mic de calcule (cum ar fi, de exemplu, calcularea inversei anumitor matrice). Pentru a se putea efectua calculele, partiţionarea nu poate fi făcută întâmplător, ci în aşa fel încât între blocurile rezultate să aibă sens operaţiile necesare (adunări, înmulţiri de matrice, etc.). Test de evaluare 1. Daţi exemplu de o două matrice care se pot înmulţi, însă găsiţi o partiţionare care nu permite aceasta

25 puncte

2. Este posibilă calcularea inversei unei matrice, partiţionând-o astfel încât partiţiile să conţină fiecare câte o linie întreagă ? Justificaţi. 25 puncte 3. Calculaţi, prin partiţionare X+Y şi X⋅Y pentru :

1 3   3 2 0  2     X =  − 2 1 3 , Y =  − 2 − 1 − 3   2 0 1  1 1 1     40 puncte

13

1.5. Rangul unei matrice Acest capitol, după ce reaminteşte câteva noţiuni studiate în liceu, introduce o nouă metodă pentru calcularea rangului unei matrice. Scopurile sale sunt prezentarea unei metode cunoscute, precum şi a unei metode noi de a calcula rangul unei matrice. Studiul subcapitolului curent necesită circa două ore.

!

Definiţie. Fie A=(aij)m×n. Se numeşte rang al matricei A, ordinul maxim al unui determinant minor diferit de zero. Se notează:

Rangul matricei

rang A=r. Din definiţie, deducem că rang 0n=n. De asemenea, rangul unei matrice pătrate nesingulare este egal cu ordinul matricei.

! Determinant (minor)

Definiţie: Orice minor diferit de zero (δ≠0), de un ordin egal cu rangul r al matricei, se numeşte determinant principal sau minor principal. În general, o matrice are mai mulţi determinanţi principali; doar în cazul unei matrice pătrate nesingulare, determinantul ei este singurul minor principal. Rangul matricei se poate determina fie cu ajutorul minorilor, fie prin transformări elementare. Teoremă. Dacă toţi minorii de ordinul p sunt nuli, atunci şi toţi minorii de ordinul p+1 sunt nuli. Teorema rezultă din faptul că în dezvoltarea după elementele unei linii sau coloane a unui minor de ordinul p+1, toţi determinanţii minori sunt de fapt minori de ordinul p ai matricei, deci nuli. Pentru a determina Rang A, A≠0, calculăm minorii de ordinul 2 până când obţinem unul diferit de zero sau arătăm că toţi minorii de ordinul 2 sunt nuli. În primul caz, rang A≥2 şi trecem la minorii de ordinul 3. Dacă toţi δ3=0 atunci r=2. Dacă (∃)δ3≠0, atunci r≥3 şi

" Teorema lui Kronecker pentru calculul rangului

trecem la minorii de ordinul 4, etc. În al doilea caz, r=1. Calculul poate fi simplificat folosind teorema lui Kronecker: Dacă δp≠0 este un minor al matricei A şi toţi minorii de ordin (p+1) obţinuţi prin bordarea lui δp sunt nuli, atunci orice minor de ordin (p+1) este nul.

14

Observaţie: Metoda de mai sus presupune calculul multor determinanţi minori, mai ales când matricea este de dimensiune mare. În cazul unor matrice de dimensiune mare, care conţin submatrice de structuri deosebite (unitate, diagonale, triunghiulare etc.), rangul se poate determina utilizând proprietăţi ale determinanţilor şi rangurilor cunoscute ale unor submatrice.

#

De exemplu, să determinăm rangul matricei: ! 1 0 0  1 0 0    0 1 0 ! 0 1 0    0 0 1 ! 0 0 1   U 3 U 3  A=  =  " " " " " " "   M 1 M 2  1 1 1 ! 0 0 0   ! 0 0 0 1 1 1  

Determinarea rangului unei matrice

Observăm că A se poate partiţiona în 4 blocuri, cele din linia întâi fiind U3. De asemenea, vedem că suma primelor trei linii este egală cu suma ultimelor două (L1+L2+L3=L4+L5), deci toţi minorii de ordinul 5 sunt nuli. Suprimând linia a 4-a, matricea formată cu primele patru coloane este triunghiulară şi are toate elementele de pe diagonala principală egale cu 1, deci este nesingulară (det A=1≠0). Rangul matricei este r=4. Generalizând, considerăm matricea:  U n U n " U n , M =   M 1 M 2 " M m unde Un sunt matrice unitate de ordinul n, iar M1, … , Mm matrice de tipul (m×n) cu elemente de pe liniile respectiv 1, 2, …, m egale cu 1, iar celelalte nule. Matricea A se obţine din M pentru n=3 şi m=2. Aplicând procedeul de mai sus, de determinare a rangului matricei A, rezultă că rang M=m+n-1. Transformări elementare. Fie matricele Am×n şi Tm×n. Prin TA=B înţelegem transformarea matriceală a matricei A prin matricea T în

$

matricea B. Două transformări T1 şi T2 sunt egale dacă: (∀) A, Transformări T1A=T2A. Evident, pentru matricea unitate U avem: T1=T2. Transformările pot fi înmulţite: (T1T2)A=T2(T1A) şi se bucură de 15

matriceale

proprietăţile egalităţii şi înmulţirii matricelor. U (sau E, I) reprezintă transformarea identică. Dintre toate transformările, un rol deosebit îl au acelea care se pot obţine ca un produs de trei transformări (numite transformări elementare). Introducem notaţiile:

U1   U 1 = (1 0 " 0)    U =  !  unde : """"""    = (0 0 " 1) U m  U m Transformările elementare sunt următoarele:

!

1. 2. 3.

T1: Înmulţirea unei linii cu un număr c≠0.

Transformări elementare Înulţirea unei linii cu un număr nenul Adunarea unei linii la ală linie Schimbarea locului a două linii

 !   !      -1  1  -1 -1 T 1 =  cU i  , T 1 =  U i  , T 1 T 1 = T 1 T 1 = U c  !       !  T2: Adunarea la o linie a unei alte linii înmulţite cu c≠0. ! !          Ui   Ui      , -1 = -1 -1 ! ! , = =U T2 =   T2   T 2 T 2 T 2T 2  cU i + U j   - cU i + U j      ! !     T3: Schimbarea locului a două linii.  !    E j   -1 -1 T 3 =  ! , T 3 T 3 = T 3 T 3 = U  Ei     ! 

"

Observaţii 1) Transformările de mai sus se pot opera şi cu coloane. 2) Transformarea T3 poate fi exprimată ca un produs de

Prin aplicarea unei transformări elementare se păstrează rangul matricei

transformări elementare de tipul T1 şi T2. În acest sens, T3 nu este „elementară”, totuşi din motive de ordin aplicativ, T3 este prin definiţie o transformare elementară. 16

3) Două matrice obţinute una din alta prin transformări elementare se numesc echivalente (A~B). Aplicând transformări elementare asupra unui determinant diferit de zero, el rămâne diferit de zero, pe când un determinant nul îşi păstrează valoarea. Rangul unei matrice fiind legat de noţiunea de determinant minor diferit de zero, rezultă că două matrice echivalente au acelaşi rang. Pentru a determina rangul unei matrice prin transformări elementare, aducem matricea la o formă mai simplă pe care să putem „citi” rangul ei. Una din aceste forme este forma canonică diagonală, în care în colţul din stânga sus apare o matrice unitate, celelalte elemente fiind nule.

"

Exemplu: Să se determine rangul matricei:  - 3 0 - 1 3   A =  2 2 0 - 1    1 4 - 1 1

Calcularea rangului unei matrice prin transformări elementare

Avem succesiv:  - 3 0 - 1 3   1 4 - 1 1   1 4 - 1 1       A =  2 2 0 - 1 ~  2 2 0 - 1  ~  0 - 6 2 - 3        1 4 - 1 1  - 3 0 - 1 3   0 12 - 4 6  (L1 schimbă cu L3)

(L2-2L1 şi L3+2L1)

 1 0 0 0 1    ~ 0 - 6 2 - 3 ~ 0    0 12 4 6   0 1 0  1 0 0 0    0 1  0 1 1 1 ~  # #    0 0 0 0 0 0  

0

0

1

1

-2 -2 ! 0 ! 0 # 0

(C2-4C1,C3+C1,C4-C1) (C2/(-6),C2/2,C4/(-3))

0  1 ~  - 2  0  0   0  (L3+2L2)

(C3-C2,C4-C2) deci: rang A=r=2. Observaţii:

17

1. Rangul unui produs de matrice, nu poate depăşi rangul fiecăreia dintre matricele factori (fără demonstraţie) 2. Rangul unei matrice nu se schimbă dacă o înmulţim la stânga sau la dreapta cu o matrice pătrată nesingulară (consecinţă a primei observaţii). Teme 1. Calculaţi rangurile matricelor A şi B prin transformări elementare.

2   2 1 − 3   1 A =  0 2 3 , B =  0 1 0 1     3 

0 0 1  3 0 0 0 4 0  3 4 1 

Rezumat Petru calcularea rangului unei matrice se poate utiliza metoda învăţată în liceu, anume determinarea celui mai mare minor nenul, rangul fiind egal cu numărul de linii al acestuia. Se mai poate utiliza şi metoda transformărilor elementare. Transformările elementare seamănă cu metoda utilizată „de a face zerouri pe linii sau coloane” utilizată la calcularea determinanţilor de ordin mare, prin reducerea acestora la determinanţi de ordin mai mic. Deosebirile sunt următoarele : Se poate înmulţii o linie (coloană) cu o constantă nenulă, fără a modifica rangul. Se pot inversa două linii (coloane) fără a modifica rangul. Test de evaluare 1. Calculaţi rangul matricei A prin ambele metode.

 1 −1 2    A =  2 1 − 3 1 0 1  

30 puncte

2. Calculaţi rangul matricei B prin ambele metode.

3 2 1  5 4 6 B= 1 − 3 −1  3 2 1 

18

2  2 2  2 

40 puncte

1.6. Rezolvarea matriceală a sistemelor de ecuaţii liniare Şi în acest subcapitol se continuă reamintirea unor noţiuni cunoscute din liceu abordându-se această problematică şi din alt punct de vedere. Acest subcapitol necesită circa 2 ore pentru a fi parcurs. 1. Forma generală a unui sistem de m ecuaţii cu necunoscutele, xi, ce intervin la gradul I este următoarea:

!

Sistem de ecuaţii liniare

 a11 x1 + a12 x 2 + ! + a1n x n = b1  a 21 x1 + a 22 x 2 + ! + a 2n x n = b 2   !!!!!!!!!!!!!!!!  a m 1 x1 + a m 2 x2 + ! + a mn x n = b m

(1.6.1)

Matricea A=(aij)m×n este matricea sistemului şi rang A este rangul sistemului iar minorul δp al matricei este determinantul principal al sistemului. Notând: B=(b1 b2 … bm)T - vectorul coloană al termenilor liberi şi T X=(x1 x2 … xn) - vectorul coloană al necunoscutelor, sistemul (1.6.1)

se scrie matriceal sub forma: AX=B. Dacă B≠0 sistemul este neomogen, iar dacă B=0 sistemul este omogen (fără termeni liberi). Orice vector X care verifică ecuaţia

! Matricea sistemului

!

Forma matriceală a sistemului

!

Sistem omogen şi neomogen

matriceală respectiv sistemul (1.6.1) este soluţie a sistemului. Un sistem care admite cel puţin o soluţie este compatibil. Dacă soluţia sistemului este unică, sistemul este compatibil determinat iar dacă sistemul admite o infinitate de soluţii este compatibil nedeterminat. Dacă sistemul nu admite soluţie (deci nu este compatibil) zicem că este incompatibil.

! Sistem compatibil (determinat, nedeterminat) şi incompatibil

În legătură cu sistemele liniare, se pun, deci, două probleme mai importante: discuţia (natura soluţiilor) şi rezolvarea lor. 2. Sisteme de n ecuaţii cu n necunoscute. Forma matriceală este AX=B cu A=(aij)n. Dacă Δ=det A≠0 (A - nesingulară) atunci (∃)A-1 şi soluţia va fi: -1 X=A B. În acest caz deci, sistemul este compatibil determinat (de tip

Cramer). Regula lui Cramer cunoscută din liceu este exprimarea sub -1

formă de determinanţi a formulei X=A B, cele două metode 19

!

Soluţia sub forma matriceală

comportând practic aceleaşi calcule. Metoda scrierii matricei inverse este de preferat totuşi datorită unei scrieri mai concentrate. De exemplu:  x1 + 2x 2 - x3 = -3  + x3 = -3 , 3x1  2x + 2x - x = -5 2 3  1 are soluţia: 1 - 1 0    x1     - 3   - 2    5 1 2   - 3  =  1  = (-2 1 3 )T X =  x 2  = A-1 B =   2 2       x     5   3   3  3 1 - 3   adică: x1=-2, x2=1, x3=3. 3. Sisteme de m ecuaţii cu n necunoscute Fie

AX=B , unde

A=(aij)m×n , X=(xi)n×1 , B=(bi)m×1

şi

presupunem rang A=p≤inf(m,n) iar δp un determinant principal al sistemului. Determinanţii obţinuţi prin bordarea lui δp cu liniile rămase din A şi coloana termenilor liberi sunt de ordinul P+1 şi se numesc determinanţi caracteristici ai sistemului.

"

de m ecuaţii liniare cu n necunoscute să fie compatibil este ca toţi

Teorema lui Rouche

determinanţii caracteristici să fie nuli. Aceasta este echivalentă cu

Teorema lui Rouché: condiţia necesară şi suficientă ca un sistem

rang A=rang à (matricea extinsă) exprimată de teorema lui Kronecker-Capelli (exprimarea în limbaj matriceal a teoremei lui Rouché). Matricea à se obţine din A la care se adaugă coloana B şi se scrie Ã=(AB).

" Rezolvarea sistemelor liniare

Rezolvarea sistemelor. Presupunem sistemul compatibil, având rang à =rang A=p≤inf(m,n), iar P formată din primele p linii şi coloane ale lui A este nesingulară, adică det P=δp (determinant principal). Prin intermediul lui P (sau δp) ecuaţiile sistemului se împart în: ecuaţii principale şi ecuaţii secundare. În cazul acesta, primele p ecuaţii (formate cu elemente din P) sunt principale iar 20

celelalte (m-p) ecuaţii (care nu conţin elemente din P) sunt ecuaţii secundare. La fel, primele p necunoscute sunt principale şi celelalte sunt secundare. Se păstrează numai ecuaţiile principale, matricea sistemului devenind (Ps), unde S este matricea formată cu coeficienţii necunoscutelor secundare. Obţinem X=(XpXs)T, Xp=vector coloană al necunoscutelor principale şi Xs=vectorul coloană al necunoscutelor secundare. Notând cu Bp primele p linii din B sistemul AX=B devine: p

p

p

PX =B -SX Înmulţim la stânga cu P-1 şi obţinem:

p -1 p -1 s X = P B - ( P S) X ,

(1.6.2)

relaţie matriceală care exprimă necunoscutele principale în funcţie de necunoscutele

secundare.

Atribuind

valori

arbitrare

reale

necunoscutelor secundare, obţinem diferite soluţii ale sistemului iniţial. Dacă rang A=n, atunci toate necunoscutele sunt principale şi sistemul este compatibil determinat. Dacă rang A
21

2 -1 3  ~ 3 2 -1 A= 5 1 2  1 1 1

1  2  3  1

Prin transformări elementare se arată că rang A=rang Ã=3, deci sistemul este compatibil determinat (n=3), conform teoremei lui Kronecker-Capelli. La fel, după teorema lui Rouché: căutăm un determinant minor principal de ordin 3, cât este rangul lui A. Fie: 1

1

δ = 2 -1 3

1 3 = 13 ≠ 0

2 -1

Calculăm determinantul caracteristic: 1 ∆c =

1

2 -1

1 1 3

1

3

2 -1 2

5

1

= 0,

2 3

deci sistemul este compatibil. Ecuaţiile principale vor fi:  x1 + x 2 + x 3 = 1   2 x1 - x 2 + 3 x 3 = 1 , 3 x + 2 x - x = 2 2 3  1 cu soluţia: x1 =

6 2 5 , x2 = , x3 = (Conform regulii lui Cramer) 13 13 13

Exemplul 2: Să se determine parametrul a∈R astfel ca sistemul:  x1 + 2 x 2 - 3 x 3 + x 4 = 1   3 x1 + x2 + x3 - 2 x4 = 3 , 3 x - 4 x + 11 x - 7 x = a 2 3 4  1 să fie compatibil şi apoi să se rezolve. Aplicăm teorema lui Kronecker:

22

1 ~  A = 3  3 1 0  ~ 0 1  0 0

1 1  1 0 0 0 0    1 - 2 3  ~  0 - 5 10 - 5 0    11 - 7 a   0 - 10 20 - 10 a - 3  0 0  0 0  0 a - 3 

2 -3 1 -4 0 0 0

Transformările elementare s-au aplicat numai coloanelor. Matricea A fiind conţinută în matricea extinsă Ã simultan determinăm şi rang A, deci: rang Ã=rang A=2 dacă a-3=0, a=3. Deoarece r
δ=

12  x1 + 2 x2 = 1 + 3 x3 - x4 şi ecuatiile principale :  31 3 x1 + x2 = 3 - x3 + 2 x4

Notând x3=λ şi x4=μ, (λ, μ∈R) şi rezolvând sistemul de mai sus, obţinem: x1=1-λ+μ, x2=2λ-μ. Deci, sistemul este compatibil dublu nedeterminat şi are soluţiile:(1-λ+μ, 2λ-μ, λ, μ). 4. Sisteme liniare omogene Aceste sisteme au termenii liberi nuli, adică sunt de formă matriceală: AX=0 unde A=(aij)m×n. În acest caz rang A=rang Ã, deci un sistem liniar şi omogen este totdeauna compatibil, admiţând soluţia banală X=0. Sistemul omogen admite şi soluţii diferite de soluţia banală dacă este compatibil nedeterminat, adică rang A
23

" Sistemele omogene au întodeauna o soluţie

Notând

x1=α,x2=β

rezultă

soluţia

dublu

nedeterminată:

(α,β,-(α+β)) Dacă λ=3, considerând primele două ecuaţii ca principale, sistemul devine: - 2 x1 + x2 + x3 = 0 ,   x1 - 2 x 2 + x 3 = 0 cu soluţia: x1=x2=x3=k. Exerciţiul 2: Să se rezolve sistemul:  A1 x + B1 y + C 1 z = 0   A2 x + B2 y + C 2 z = 0 Fiecare ecuaţie a sistemului omogen reprezintă câte un plan ce trece prin origine. Intersecţia lor este o dreaptă în spaţiu ce trece prin origine având ecuaţiile sub forma canonică x = y = z , unde l, m, n l m n sunt parametrii directori daţi de relaţiile (determinanţii): l=

C 1 A1 B1 C 1 A1 B1 , m= , n= C 2 A2 B2 C 2 A2 B2

Făcând abstracţie de această interpretare geometrică, sistemul se rezolvă cu una din necunoscute (de exemplu z), presupunând că rangul matricei sistemului este r=2. Apoi notăm pe z cu o literă (λ, μ, …) care joacă rol de parametru real. Teme 1. Rezolvaţi sistemele următoare : 2 x1 + x 2 − x3 = 0  x1 + 2 x 2 − x3 = 0 − 2 x1 − x 2 + 3 x3 = 2     x1 + 3 x 2 + x3 = 1 ; 2 x1 + x 2 + x3 = −1 ;  − x1 + x 2 + x3 = 1  x − x + x = −1  x − x + 2 x = −1  x + 2 x − 2 x = 1 2 3 2 3 2 3  1  1  1  x1 + x 2 − x3 = 0  x1 + 2 x 2 − x3 = 0  − 2 x1 − x 2 + 3x3 = 1    x1 + 3 x 2 + x3 = 0 ; 2 x1 + x 2 + x3 = 0 ;   x − 2 x + x = 0  x − x + 2 x = 0 − x1 − 2 x 2 + 2 x3 = −1 2 3 2 3  1  1  x1 + 2 x 2 = 2   2 x1 + x 2 = 3  x − x =1 2  1 2. Rezolvaţi, în funcţie de valorile parametrului α, sistemul următor 24

 αx1 + x 2 − x3 = 0   x1 + 3αx 2 + x3 = 0  x − 2x + x = 0 2 3  1 Rezumat Sistemele de ecuaţii liniare se pot rezolva atât prin intermediul metodei lui Cramer, cât şi matriceal. Soluţia prin metoda Cramer presupune determinarea rangului matricei sistemului şi rangul matricei extinse. Dacă cele două coincid, sistemul este compatibil, în caz contrar este incompatibil. Dacă sistem este compatibil şi rangul este egal cu numărul de necunoscute, atunci sistemul este compatibil determinat (are soluţie unică), altfel este compatibil nedeterminat (are o infinitate de soluţii). Matriceal, sistemul se poate rezolva înmulţind vectorul coloană al termenilor liberi la stânga cu inversa matricei sistemului (dacă există). Sistemele omogene (cele la care toţi termenii liberi sunt nuli) sunt întotdeauna compatibile. Test de evaluare 1. Rezolvaţi şi discutaţi sistemele următoare : − 2αx1 − αx 2 + 3 x3 = 1 a)   − 2 x1 − x 2 + 2 x3 = −1  x1 + 2 x 2 = 2  b) 2 βx1 + βx 2 = 3  βx − βx = 1 2  1

45 puncte

45 puncte

25

1.7. Spaţiu vectorial (liniar). Dependenţă liniară

"

Spaţiul vectorial este o structură algebrică, ce include două mulţimi, ale căror elemente satisfac diferite proprietăţi. Prima mulţime (V), denumită de vectori, este înzestrată cu o operaţie de adunare a elementelor sale, faţă de care formează o structură de grup abelian. Cea de-a doua mulţime (K), denumită de scalari, este înzestrată cu operaţiile de adunare şi înmulţire, faţă de care formează o structură de corp. Elementele celor două mulţimi sunt legate între ele printr-o operaţie externă, de înmulţire a vectorilor cu scalari, cu proprietăţile : 1. ∀ a,b ∈ K, ∀ v ∈V (a ⋅ b) ⋅ v = a ⋅ (b ⋅ v) 2. ∀ a,b ∈ K, ∀ v ∈V (a + b) ⋅ v = (a ⋅ v)+(b ⋅ v) 3. ∀ a ∈ K, ∀ u,v ∈V a ⋅ (u + v) = (a ⋅ u)+(a ⋅ v) 4 ∀ V 1

!

Următoarele

trei

paragrafe

realizează

o

introducere

în

problematica spaţiilor liniare. Cu aceste capitole se începe, de fapt, prezentarea materialului cu aspect de noutate. Cele trei paragrafe au ca scopuri imediate prezentarea noţiunilor de spaţiu liniar, vectori, dependenţă şi independenţă liniară, însă aceste noţiuni servesc ca suport teoretic noţiunilor din paragrafele următoare, precum şi celor din capitolul doi. Pentru studierea acestor trei subcapitole se recomandă alocarea a circa trei ore. Mulţimea matricelor linii cu n elemente (vectori linii), formează o structură algebrică în raport cu operaţia de adunare (internă) şi în raport cu operaţia de înmulţire a matricei cu un scalar (externă), numită spaţiu vectorial n-dimensional (sau spaţiu liniar) şi pe care-l notăm cu S(n). Spaţiul vectorial poate fi real sau complex după cum câmpul scalarilor este real sau complex. Mai general, orice structură izomorfă cu S(n) se numeşte spaţiu vectorial n-dimensional. Spaţiul real n-dimensional se mai notează şi cu Rn. Axiomele adunării şi înmulţirii cu un scalar s-au evidenţiat la § 1.2. (operaţii cu matrice). Considerăm vectorii V i = ( v1i v2i ! vni )T , i = 1, m din spaţiul S(n). Zicem că Vi sunt liniar dependenţi dacă există m scalari nu toţi nuli, λi, astfel încât să aibă loc relaţia:

Liniar independenţă

λ 1 V 1 + λ 2 V 2 + !+ λ m V m = θ

(1.7.1)

În caz contrar, adică dacă (1.7.1) are loc numai pentru toţi λi=0 sau

λ 1V 1 + λ 2 V 2 + ! + λ m V m ≠ θ , ( λ i ≠ 0) , vectorii se numesc liniar independenţi. Din definiţie rezultă că dacă vectorul nul (θ) face parte din sistem, vectorii Vi sunt liniar dependenţi şi că sistemul format dintr-un singur vector nenul este liniar independent. Dacă are loc relaţia (1.7.1) atunci orice vector Vi cu λi≠0 se poate exprima ca o combinaţie liniară de ceilalţi (m-1) vectori. De exemplu, dacă λ1≠0 atunci: 26

v1 = −

λ λ2 v2 − ! − m vm = α 2 v2 + ! + α m vm λ1 λ1

Dacă doi vectori V1≠0, V2≠0 sunt liniar dependenţi, din relaţia λ1V1+λ2V2=0 cu λ1≠0, λ2≠0, rezultă V1=kV2 unde k = - λ 2 este un λ1 scalar nenul. Deci, coordonatele a doi vectori liniar dependenţi sunt proporţionale. Explicitând

relaţia

(1.7.1),

prin

înlocuirea

coordonatelor

vectorilor, obţinem un sistem liniar omogen de n ecuaţii cu m necunoscute λ1, λ2, … ,λm:  x11 λ 1 + x12 λ 2 + ! + x1m λ m = 0  v11 v12 ! v1m      x 21 λ 1 + x 22 λ 2 + ! + x2m λ m = 0  v 21 v22 ! v 2m  , cu matricea : V =    "" " !!!!!!!!!!!!!!      x n1 λ 1 + x n 2 λ 2 + ! + x nm λ m = 0 ! v v v 1 2 n n nm   (1.7.2) Dacă rang V=m atunci sistemul admite numai soluţia banală (λ1=λm=0) şi vectorii sunt liniar independenţi (şi reciproc). Deci: condiţia necesară şi suficientă ca un sistem de vectori să fie liniar independent este ca rangul matricei sistemului să fie egală cu numărul de vectori. Deoarece rang V≤inf(n,m), rezultă că într-un spaţiu vectorial S(n) există cel mult n vectori liniar dependenţi, în sensul că dacă sistemul de vectori conţine un număr mai mare de vectori decât dimensiunea spaţiului, cei care sunt în plus vor fi liniar dependenţi. Dacă rang V=p<m, atunci orice subsistem de p vectori ai sistemului iniţial a cărui matrice are rangul p este format din vectori liniar independenţi şi sistemul (1.7.2) admite soluţii diferite de soluţia banală (nu toate vor fi nule). Numărul maxim de vectori liniar dependenţi, ai unui sistem de vectori este egal cu rangul sistemului. T T Exemplu: Să se arate că vectorii: V1=(3 0 -2 3) , V2=(1 2 1 2) , T

V3=(-3 6 7 0)

sunt liniar dependenţi şi să se afle relaţia de

#

Determinarea relaţiei de dependenţă

dependenţă. Calculăm rangul matricei sistemului de vectori: 27

 3 1 - 3  1     0 2 6  0 V = ~   - 2 1 7  0     3 2 0  0

0 0  1 0  , rangV = 2 0 0  0 0

Deoarece rang V=2 mai mic decât m=3, vectorii daţi sunt liniar dependenţi şi există între ei o relaţie de dependenţă de forma (1.7.1). În calculul rangului matricei V, nu s-a schimbat ordinea coloanelor deci primii doi vectori (unde apar elementele 1 pe coloană) sunt liniar independenţi. Aşa că, scriem relaţia (1.7.1) numai pentru primele două coordonate care intervin în ecuaţiile principale: 3λ1 + λ 2 − 3λ3 = 0  2λ 2 + 6λ 3 = 0  Rezultă: λ1=2λ3, λ2=-3λ3 pe care îi înlocuim în relaţia λ1V1+λ2V2+λ3V3=θ, adică: 2λ3V1-3λ3V2+λ3V3=θ. Împărţim cu λ3≠0 şi deducem relaţia de dependenţă dintre cei trei vectori: 2V1-3V2+V3=θ. Teme 1. Definiţi noţiunea de liniar dependenţă. 2. Să se arate că vectorii: V1=(2 1 1 2)T, V2=(-1 2 -1 -3)T, V3=(1 3 0 -1)T sunt liniar dependenţi şi să se afle relaţia de dependenţă. 1.8. Bază în spaţiul vectorial S(n). Exprimarea unui vector într-o bază dată.

!

Bază a spaţiului vectorial

Definiţie. Se numeşte bază a spaţiului S(n) orice sistem de n vectori liniar independenţi ai spaţiului. Fie vectorii Vi=(a1i a2i … ani)T care formează o bază în S(n) şi pe care o notăm B=(v1 v2 … vn)T. Vectorii bazei fiind liniar independenţi, matricea sistemului de vectori care formează baza (pe care o notăm tot cu B) este nesingulară. Orice vector arbitrar X=(x1 x2 … xn)T al spaţiului S(n) se exprimă în funcţie de vectorii bazei, ca o combinaţie liniară. Astfel, deoarece sistemul ( V i X) i = 1, n , de (n+1) vectori este liniar dependent are loc o relaţie de forma: λ1V1+ … +λnVn+λn+1X=0 28

unde nu toţi λi sunt nuli. Vectorii bazei fiind liniar dependenţi, λn+1≠0 şi avem:

x= -

λ1 λn v1 - ! v n = α 1 v1 + ! + α n v n λ n+1 λ n+1

Coeficienţii α i , i = 1, n se numesc coordonatele vectorului x în baza B. Dacă xiB , i = 1, n sunt coordonatele lui x în baza B, putem

$

scrie:

Coordonatele vectorului n

X = x v1 +!+ x v n = ∑ xiB vi B 1

B n

i=1

(1.8.1)

ele sunt tot vectori. Deci un vector arbitrar X are componente

$

vectoriale şi coordonate scalare. Zicem că (1.8.1) reprezintă scrierea

Componentele vectorului

Termenii xiVi se numesc componentele vectorului X în baza B şi

analitică a unui vector X într-o bază B. Notând: XB=(x1B … xnB)T, relaţia (1.8.1) devine: X = BX B

(1.8.2)

Înmulţind la stânga cu B-1 obţinem o relaţie care ne permite să calculăm coordonatele unui vector într-o bază dată: B -1 X =B X

(1.8.3)

Observaţie: Vom numi bază a unei matrice Am×n de rang p, orice sistem de p vectori liniar independenţi ai matricei. Dacă rang A este egal cu dimensiunea spaţiului S(n), adică p=n, atunci bazele matricei A vor fi baze în S(n). Definiţie: Se numesc vectori unitari în spaţiul Rn, vectorii:

$

 1 0  0        0   1 0  E 1 =   , E 2 =   ,! , E n =   , " " "       0  0   1      

Vectorii unitari

matricea sistemului fiind matricea unitate E (sau U sau I), deci vectorii unitari formează o bază a spaţiului numită bază iniţială.

29

Denumirea se justifică deoarece fiind dat un vector X=(x1 …xn)T el se exprimă: X=X1E1+ … xnEn şi coordonatele lui sunt coordonate în baza formată de E i , i = 1, n. Notă: Din (1.8.3) rezultă că dacă un vector face parte dintr-o bază B, coordonatele lui în baza B formează un vector unitar. Soluţii de bază ale unui sistem de ecuaţii liniare. Fie AX=D un sistem compatibil, cu Am×n, n>m şi rang A=m (adică din sistem am eliminat ecuaţiile secundare). Notăm A=(V1 V2 … Vn), unde Vi sunt vectorii coloană ai matricei A aparţinând spaţiului Rn. Sistemul se poate scrie deci: x1 V 1 + x 2 V 2 + ! + x n V n = D

(1.8.4)

Un vector X = ( x1 x 2 ! x n )T este soluţie a sistemului (1.8.4) dacă: x1 V 1 + x 2 V 2 + ! + x n V n = D

!

Soluţii de bază

Vectorul X este soluţie de bază a sistemului (1.8.4) dacă vectorii corespunzători coordonatelor lui nenule sunt liniar independenţi. Deoarece Vi∈Rm, o soluţie de bază are cel mul m coordonate diferite de zero şi zicem că este nedegenerată. În caz contrar, dacă are mai puţin de m coordonate nenule, zicem că ea este degenerată. Dacă B este o bază a matricei A, deci a spaţiului Rm, notând cu S matricea formată cu vectorii care nu fac parte din bază, cu XB variabilele principale sau bazice (însoţesc vectorii din bază) şi cu XS vectorul variabilelor secundare sau nebazice, sistemul dat se poate scrie sub forma: B S BX + SX = D

Înmulţind la stânga cu B-1, deducem: B -1 -1 S X = B D - ( B S) X

(1.8.5)

Relaţia (1.8.5) exprimă variabilele principale în funcţie de variabilele secundare, adică soluţia sistemului. Dacă Xs=0, atunci: B -1 -1 S X = B D - ( B S) X

30

(1.8.6)

unde DB sunt coordonatele vectorului D în baza B. Soluţia particulară obţinută din DB completat cu vectori pentru variabilele secundare este o soluţie de bază (vectorii din B fiind liniar independenţi) corespunzătore bazei B. Ea este nedegenerată dacă toate coordonatele vectorului DB sunt diferite de zero. În caz contrar este degenerată. Rezultă că fiecărei baze din matricea A îi corespunde o soluţie de bază. Numărul maxim al soluţiilor de bază ale unui sistem de m ecuaţii cu n necunoscute (presupunând rang A=m) este Cnm. Numărul lor poate fi mai mic deoarece în A pot exista sisteme de m vectori liniar independenţi. Reciproca nu este adevărată, o soluţie de bază putând să corespundă mai multor baze. Exemplu: Să se determine soluţiile de bază ale sistemului:

#

2 x1 + x 2 - 4 x 3 + 5 x 4 = 4   x1 + x 2 - 2 x 3 + 2 x 4 = 2

Determinarea soluţiilor de bază

Avem: 2 1 - 4 5  A =  11 - 2 2  Determinăm bazele matricei din cele C42=6 combinaţii (Vi Vj) posibile. Pentru fiecare bază anulăm variabilele nebazice şi rezolvăm sistemul: B1 = ( V 1 V 2 ), det B1 = 1 ≠ 0, X1 = (2 0 0 0 ) B2 = (V1 V3), det B2 = 0 - nu este baz ă

T

B3 = (V1 V 4), det B3 = -1 ≠ 0, X3 = (2 0 0 0 )

T T

B4 = (V2 V3), det B4 = 2 ≠ 0, X 4 = (0 0 - 1 0 ) 2 2 T B5 = (V 2 V4), det B5 = -5 ≠ 0, X5 = (0 0 ) 3 3 T B6 = (V3 V 4), det B6 = 2 ≠ 0, X6 = (0 0 - 1 0 ) S-au obţinut astfel 5 baze. Dintre soluţiile de bază doar X 5 este nedegenerată. Cele degenerate, egale două câte două, corespund la câte două baze distincte.

31

Teme 1. Definiţi noţiunile de bază şi soluţie de bază degenerată. 2. Daţi exemplu de bază în spaţiul vectorial al matricelor cu două şi două coloane. 1.9. Schimbarea bazei Fie X∈Rn şi XA, XB coordonatele lui X în bazele A şi B, deci: X = AX A , X B = B-1 X,

! Coordonatele lui X în baza B

de unde: B -1 A X = ( B A) X ,

(1.9.1)

relaţie care exprimă coordonatele lui X în baza B funcţie de coordonatele lui X în baza A. Exemplu: Se dau bazele:  1 - 1 2  1 2 - 1     A =  1 3 2  , B =  3 0 1      2 1 - 1  2 2 - 1 şi vectorul V=(0 4 -2)T. Se cere: a) Să se afle VA b) Din VA să se determine VB. Soluţie:

a) Aplicăm (1.8.3) şi rezultă VA=A-1V=(-1 1 1)T b) Aplicăm (1.9.1): VB=(B-1A)VA=(-2 6 10)T

Modificarea unui singur vector coloană din bază. Fie baza B=(V1 … Vh-1 Vh Vh+1 … Vn)⊂Rn şi vectorul Vk∈Rn cu coordonatele în baza B, aik (i = 1, n ) , necunoscute. În baza B înlocuim vectorul Vh cu vectorul Vk. Se obţine o nouă matrice B1 care formează o bază dacă ahk≠0. Zicem că Vh iese din bază şi Vk intră în bază. Fie un vector X=(X1B … XnB)T∈Rn cu coordonatele XiB cunoscute. Să calculăm coordonatele xiB1 . Avem: V k = ∑ aik V i = i∈B

∑

aik V k + a hk V h

i∈B \{h}

Din (1.9.2) scoatem pe Vh şi-l înlocuim în X: 32

(1.9.2)

Vh=

1 a hk

Vk -

1 a hk

X = ∑ xiB V i = i∈B

∑

aik V k , a hk ≠ 0

∑

xiB V i + xh V h ,

i∈B \{h} B

i∈B \{h}

adică: 1

X=

∑ ( xiB ahk - xhB aik )V i +

a hk i∈B1

B

xh Vk a hk

(1.9.3)

Din (1.9.3) deducem coordonatele lui X în noua bază B1:    xiB1 =    

B

xh , dac_ i = h a hk ( a hk ≠ 0) B B xi a hk - x h a ik , dac_ i h ≠ a hk

(1.9.4)

Formulele (1.9.4) se reţin mai uşor dacă formăm un tabel care să conţină pe coloane vectorii din baza B, coordonatele vectorului Vh care iese din bază, coordonatele vectorului Vk care intră în bază şi coordonatele vectorului XB: B

B

Vh

Vk

X

V1

0

a1k

x1

B

V2

0

a2k

x2

B

"

"

"

"

Vi

0

aik

xi

"

"

"

"

Vh

1

ahk

xh

"

"

"

"

Vn

0

ank

xn

B

B

B

aik

xi

ahk

xh

B

B

Coordonata ahk din tabloul de mai jos se numeşte element pivot sau pivot şi joacă un rol fundamental în transformarea coordonatelor vectorului X. Formulele (1.9.4) exprimă operaţiile: - coordonatele de pe linia h (a pivotului) se împart cu pivotul ce trebuie să fie diferit de zero (în caz contrar problema nu este posibilă, B1 nu formează o bază);

33

$ Metoda pivotului

-

se determină coordonata

xiB1 , când i≠h, formându-se

dreptunghiul din dreapta tabloului, cu coordonate ale vectorilor Vk şi XB, având ca vârfuri opuse pivotul şi coordonata xiB. Se aplică formula (1.9.4) Aceasta este regula dreptunghiului. Teme 1. Determinaţi un element pivot pentru a înlocui vectorul V2 cu un alt vector. Precizaţi care vector va putea intra în bază, V1, V3 ? Poate intra vectorul V2 în locul V2 ? are sens ? B

V1

V2

V3

E1

2

0

-2

V2

0

1

-2

E3

2

0

1

2. Se poate înlocui vectorul V2 cu V3 în matricea următoare ? B

V1

V2

V3

E1

2

0

-2

V2

0

1

1/6

E3

2

0

1

Rezumat Spaţiul vectorial este o structură algebrică complexă. O mulţime de vectori este liniar dependentă, dacă se poate găsi o combinaţie liniară (o sumă a vectorilor, eventual înmulţiţi cu scalari, din care cel puţin unul să fie nenul) care să aibă ca rezultat vectorul nul. În caz contrar, vectorii se zic liniar independenţi. O mulţime de vectori liniar independenţi, care are atâţia vectori cât este dimensiunea spaţiului, este o bază. Numărul de vectori se numeşte dimensiunea spaţiului. Într-un spaţiu vectorial sunt mai multe baze, existând un algoritm de trecere dintr-o bază în alta. Test de evaluare Să se decidă dacă vectorii: V1=(-3 2 1 2)T, V2=(-1 -2 1 1)T, V3=(2 -4 0 -1)T sunt liniar dependenţi şi să se afle relaţia de dependenţă în caz afirmativ. 34

90 puncte

1.10. Forma redusă a unei matrice corespunzătoare unei baze. Următoarele două paragrafe pun în valoare noţiunile introduse în precedentele trei. Paragraful 1.11 va ilustra câteva aplicaţii ale metodei pivotului, deocamdată punând la dispoziţie o nouă metodă pentru calcularea diferitelor caracteristici ale unei matrice (rangul, inversa), precum şi rezolvarea sistemelor de ecuaţii liniare, metodă care are calitatea de permite obţinerea rezultatelor prin aplicarea unor operaţii aritmetice simple şi printr-un procedeu mai simplu, fără să necesite calcule complicate cum ar fi calcularea unor determinanţi. Acest subcapitol necesită circa două ore pentru a putea fi asimilat şi constituie un bun exerciţiu pentru partea a doua a cursului, care va extinde aceste noţiuni şi va introduce o metodă (cu mai mute variante) pentru rezolvarea câtorva probleme cu specific economic (căutarea rutei de transport minim, obţinerea profitului maxim sau a costurilor minime, etc.). Considerăm o matrice A=(aij)m×n cu rang A=p şi o bază B a ei. Exprimând vectorii coloană Vi ai matricei în funcţie de vectorii bazei, obţinem o nouă matrice AB de acelaşi tip, numită matricea redusă a matricei A corespunzătoare bazei B. Dacă n>m şi rang A=m, baza B a matricei A este bază a spaţiului vectorial Rm şi coloanele lui AB sunt coordonatele vectorilor Vi în baza B daţi de relaţia B-1Vi=ViB. Deci: AB=B-1A. Forma redusă a matricei A conţine o matrice unitate Um formată din coloanele corespunzătoare vectorilor care formează baza B. Dacă rang A=p<m, baza B a matricei A nu este bază a spaţiului m R , dat toţi vectorii Vi se exprimă liniar în funcţie de vectorii bazei B.

Forma redusă a matricei A conţine p vectori unitari şi (m-p) linii formate din zerouri. Pentru a determina forma redusă, putem aplica metoda schimbării unui singur vector din bază, eliminând succesiv un vector Eh din bază şi introducând în locul lui un alt vector Vk. Pentru aceasta, alcătuim un tabel care conţine o coloană B cu vectorii bazei, matricea A cu vectorii coloană V1, … ,Vn şi baza iniţială:

35

!

Matricea redusă

B

V1

V2

… Vk

…

Vn

E1 a11 a12 … a1k … a1n

1

0

…

0

…

0

E2 a21 a22 … a2k … a2n

0

1

…

0

…

0

!

!

!

Eh ah1 ah2 … ahk … ahn

0

0

!

!

!

0

0

! !

! !

!

!

!

!

Em am1 am2 … amk … amn

" Elementul pivot este un număr nenul.

E1 E2 … En … Em

! …

1

! …

! …

0

0 !

…

1

Elementul pivot este ahk≠0 şi aplică formulele (1.9.4). Continuă procedeul până la eliminarea tuturor vectorilor Ei din bază (rang A=m) sau până obţinem un tabel în care eliminarea unui vector unitar din bază devine imposibilă deoarece toţi pivoţii sunt nuli. (rang A<m). Acest procedeu, de modificare succesivă a unui vector din bază, îl numim metoda pivotului datorită rolului important al elementelor ahk în transformarea tabelelor. 1.11. Aplicaţii ale metodei pivotului în algebră.

1. Determinarea rangului unei matrice. În forma redusă a unei matrice A=(aij)m×n se poate pune în evidenţă atât rangul matricei cât şi un determinant principal al ei. Deoarece vectorii bazei B în general nu sunt nominalizaţi, vom alege pivoţii în aşa fel încât să avem calcule cât mai puţine, de preferinţă +1 sau -1. Exemplul 1: Să se determine rangul matricei:

#

 2 1 3 - 2   A = - 1 1 - 4 1    2 2 - 1 1

Determinarea rangului matricei prin metoda i l i

Formăm tabelul menţionat:

36

B

V1

V2

V3

V4

E1

E2

E3

E1

2

1

3

-2

1

0

0

2

1

E2

-1

1

-4

1

0

1

0

-1

1

E3

2

2

-1

1

0

0

1

V2

2

1

3

-2

0

0

E2

-3

0

-7

3

1

0

E3

-2

0

-7

5

0

1

V2

0

3

-5

0

0

V4

-3

0

-7

3

0

E3

9

0

14

0

1

V2

0

1

-5/3

0

0

V4

-1

0

-7/3

1

0

E3

3

0

14/3

0

1

V2

0

1

-5/3

0

V4

-1

0

-7/9

1

V1

1

0

14/9

0

⇒

−1− 2 = −3 1

simplificăm cu 3

elementele matricei

Matricea unitate fiind de ordinul 3 înseamnă că rang A=3 şi sistemul de vectori (V2 V4 V1) reprezintă o bază a matricei iar vectorul 5 7 14 V3 se exprimă în funcţie de aceştia: V 3 = - V 2 - V 4 + V 1 . 3 9 9 La rezolvarea problemei s-au folosi trei iteraţii. Exemplul 2: Să se determine rangul matricei:

 2 1 - 3 0   A =  1 3 1 - 5    - 1 0 2 - 1 Avem:

37

B

V1

V2

V3

V4

E1

E2

E3

E1

2

1

3

0

1

0

0

E2

1

3

1

-5

0

1

0

E3

-1

0

2

-1

0

0

1

V2

2

1

-3

0

0

0

E2

-5

0

10

-5

1

0

E3

-1

0

2

-1

0

1

V2

0

1

1

-2

0

E2

0

0

0

0

1

V1

1

0

-2

1

0

Elementele liniei a doua fiind nule, rang A=2. Sistemul de vectori (V2 V1) reprezintă o bază a matricei iar ceilalţi doi vectori se exprimă ca o combinaţie liniară de V1 şi V2: V3=V2-2V1 şi V4=-2V2+V1. S-au folosit două iteraţii (3 tabele succesive).

2. Determinarea inversei unei matrice.

# Determinarea inversei matricei prin metoda pivotului

Fie A=(aij)n cu det A≠0. Prin metoda pivotului, în ultimul tablou, în locul matricei A apare forma redusă a ei — o matrice formată din vectori unitari, iar în dreptul matricei unitate din primul tablou apare inversa bazei înscrisă în coloana B. Exemplu: Să se calculeze inversa matricei: 0 - 1 2   A =  1 0 - 1   2 3 4   Vom avea succesiv:

38

B

V1

V2

V3

E1

E2

E3

E1

0

-1

2

1

0

0

E2

1

0

-1

0

1

0

E3

2

3

-4

0

0

1

V2

0

1

-2

-1

0

0

E2

1

0

-1

0

1

0

E3

2

0

2

3

0

1

V2

0

1

-2

-1

0

0

V1

1

0

-1

0

1

0

E3

0

0

4

3

-2

1

V2

0

1

0

1 2

-1

1 2

V1

1

0

0

3 4

1 2

1 4

3 4

−

V3

0

0

1

1 2

a11=0, a12=-1≠0 (pivot)

(:4)

1 4

Matricea din ultimul tabel situată în dreptul matricei unitate este inversa bazei (V2 V1 V3). Inversa matricei A=(V1 V2 V3) se obţine schimbând între ele primele două linii, deci: 3  4  1 -1 A = 2  3 4 

1  4   3 2 1  -1 1 1   = 2 4 2  2 4  3 - 2 1      1 1 2 4  1 2

3. Rezolvarea unui sistem de n ecuaţii liniare cu n necunoscute. Fie sistemul AX=D cu A=(aij)n nesingulară. Soluţia sistemului -1

A

este X=A D=D (coordonatele vectorului D în baza A). În tabelul de mai sus adăugăm coloana vectorului D (termen liber) şi-i calculăm coordonatele în bazele succesive obţinute prin introducerea în bază a câte unui vector din A. 39

# Rezolvarea unui sistem de ecuaţii liniare prin metoda pivotului

Exemplu: Să se rezolve sistemul:  x1 + 2 x 2 - x3 = -3   3 x1 + x3 = -3 2 x + 2 x - x = -5 2 3  1 Avem: B

D

V1

V2

V3

E1

E2

E3

E1

-3

1

2

-1

1

0

0

E2

-3

3

0

1

0

1

0

E3

-5

2

2

-1

0

0

1

V1

-3

1

2

-1

0

0

E2

6

0

-6

4

1

0

E3

1

0

-2

1

0

1

V1

-2

1

0

0

0

E2

2

0

2

0

1

V3

1

0

-2

1

0

V2

-2

0

0

0

V1

1

0

1

0

V3

3

0

0

1

(:2)

Rezultă: X=(-2 1 3)T=DA - soluţia sistemului, respectiv: x1=-2, x2=1, x3=3. 4. Discuţia şi rezolvarea unui sistem de m ecuaţii liniare cu n necunoscute

#

Discuţia şi rezolvarea unui sistem de ecuaţii liniare prin metoda i l i

Fie sistemul AX=D, A=(aij)m×n şi rang A=p≤inf{m,n}. Aplicând metoda pivotului, după introducerea în bază a p vectori Vi* din A se obţine forma redusă a vectorului A corespunzătoare bazei B, formată din vectorii Vi*, având (m-p) linii formate din zerouri. Dacă în ultimul tablou coordonatele lui D de pe liniile formate din zerouri sunt nule, rang (AD)=rang A=p şi sistemul este compatibil. În caz contrar, dacă nu toate coordonatele lui D de pe aceste linii sunt nule, rang (AD)>rang A şi sistemul este incompatibil. 40

Dacă sistemul este compatibil, prin eliminarea celor (m-p) linii formate din zerouri se obţine un sistem de forma AX=D cu rangA=p şi A=(aij)p×n. Baza B a matricei A=(aij)p×n este bază în Rn şi sistemul se scrie: B BX = D - ∑ V j x j

,

j∈S

unde j∈S înseamnă că j ia toate valorile indicilor vectorilor care nu fac parte din bază. Înmulţim cu B-1 şi obţinem soluţia sistemului dat, sub formă matriceală: B B X = D - ∑ V Bj x j

(1.11.1)

j∈B

Transcrisă în coordonate, aceasta devine: B B xi = d i - ∑ aijB x j , i ∈ B j∈S

(1.11.2)

Exemplu: Să se discute şi să se rezolve sistemul:  x1 + 2x 2 - 3x3 + x 4 = 1   3x1 + x 2 + x3 - 2x 4 = 3 3x - 4x + 11x - 7x = a 2 3 4  1 B

D

V1

V2

V3

V4

E1

E2

E3

E1

1

1

2

-3

1

1

0

0

E2

3

3

1

1

-2

0

1

0

E3

a

3

-4

11

-7

0

0

1

V1

1

1

2

-3

1

0

0

E2

0

0

-5

10

-5

1

0

E3

a-3

0

-10

20

-10

0

1

V1

1

1

0

1

-1

0

V2

0

0

1

-2

1

0

E3

a-3

0

0

0

0

1

se împarte cu pivotul

Elementele liniei a treia din A fiind nule, rang A=2 şi sistemul este compatibil dacă a-3=0, a=3 (atunci rang A=rang (AD)). Înmulţind vectorii Vi din ultimul tabel, cu xi şi sumând avem: 41

 x1 + x 3 - x 4 = 1   x 2 - 2 x3 + x4 = 0 (ecuaţii principale cu x1, x2 necunoscute principale) de unde:  x1 = 1 - λ - µ  = 2λ - µ  x2 ; λ, µ ∈ R   x3 = λ  x4 = µ Sistemul este compatibil dublu - nedeterminat, având soluţia: (1-λ+μ, 2λ-μ, λ, μ) 5. Determinarea soluţiilor de bază nenegative ale unui sistem liniar.

#

Considerăm sistemul AX=D cu A=(aij)m×n şi rang A=m. Ne B propunem să aflăm soluţiile de bază X ≥ 0 , având coordonatele:

Determinarea soluţiilor de bază ale unui sistem de ecuaţii liniare prin metoda pivotului

d iB , dacă i ∈ B =  x  0, dacă i ∉ B B i

(1.11.3)

Dacă X B ≥ 0 atunci DB≥0 şi reciproc. Presupunem D≥0 şi DB≥0. Dacă Vk intră în bază şi Vh iese din bază se obţine o nouă bază B1 şi din relaţiile ce dau coordonatele vectorului în noua bază B1,  x hB ,i = h   a hk B1 xi =  B B  xi a hk - x h a ik , i ≠ h  ahk obţinem:  d hB ,i = h  B  a hk d iB 1 =  B B B B  d i a hk - d h aik , i ≠ h B  a hk

(1.11.4)

B B Condiţia d iB 1 ≥ 0, ( ∀ )i ∈ B1 devine: a hk > 0, d iB a hk - d hB a ikB ≥ 0 şi

este satisfăcută pentru:  d iB  d hB inf , (∀) i ∈ B =  B a hkB  aik  a B >0 hk

42

(1.11.5)

Deci, pentru a ne păstra în cadrul soluţiilor de bază nenegative trebuie repetat criteriul de ieşire din bază: dacă Vk intră în bază se scoate din bază vectorul pentru care este îndeplinită condiţia (1.11.5). Dacă (1.11.5) se realizează pentru doi indici p şi q se introduce în bază unul din vectorii Vp sau Vq şi soluţia X B1 este degenerată, deoarece d qB 1 = 0 sau d Bp 1 = 0 . Dacă X B ≥ 0 este o soluţie degenerată cu d hB = 0 , introducând în bază orice vector Vj∈B cu ahjB≠0, soluţia B X nu se modifică.

Observaţie: Pentru determinarea soluţiilor de bază nenegative se consideră pivoţi pozitivi. Singura excepţie este cea semnalată când soluţia X B este degenerată. Exemplu: Să se determine soluţiile de bază nenegative ale sistemului: 2 x1 + x 2 - 4 x 3 + 5 x 4 = 4   x1 + x 2 - 2 x 3 + 2 x 4 = 2 B

În tabelul obişnuit adăugăm o coloană cu d i pentru aikB>0. B aik B

B

D

V1

V2

V3

V4

E1

E2

E1

4

2

1

-4

5

1

0

E2

2

1

1

-2

2

0

1

V1

2

1

E2

0

0

V1

2

1

1 2 1 2 0

V2

0

0

1

2 3 2 3

1 3 1 3

V4 V2

0 1

-2

5 2 1 2 3

0

-1

-2 0

2 3 2 3 -

0 1

di B aik 4 2  ,  2 1     2 0  1 , 1    2 2  2   3

(I)

(II)

(III)

1 (IV) 0

În (I) se pot introduce în bază doar unul din vectorii V1, V2, V4 şi nu V3 care are toate coordonatele negative. Se introduce V1. Rapoartele fiind egale se scoate din bază E1 sau E2. S-a scos E1. 43

În (II) soluţia este degenerată. Se pot introduce V2 sau V4 în locul lui E2. S-a introdus V2. În (III) baza aparţine matricei A; eliminarea lui V2 din bază nu modifică soluţia. Dacă eliminăm pe V1, singurul vector care poate fi introdus în bază este V4 şi se obţine tabelul (IV). Soluţiile de bază nenegative sunt aşadar: X1=(2 0 0 0)T care  corespunde bazelor (V1 V2), (V1 V4) şi X 2 =  0 

2 3

0

2  3

T

ce

corespunde bazei (V2 V4). Aplicaţie în economie: Modelul matematic al „balanţe”.

#

sistemelor de ecuaţii liniare în economie, este balanţa legăturilor dintre

Modelul matematic al balanţei

ramurile de producţie. Modelul matematic al balanţei numit model

Una dintre cele mai importante aplicaţii ale matricelor şi respectiv

input-output elaborat de Leontief, consideră economia naţională descompusă în n ramuri de producţie, care se stabilesc convenţional: industria construcţiilor de maşini, industria uşoară, agricultura, industria metalurgică, etc. Aceste n ramuri le notăm cu primele n numere naturale (abstract). Producţia se poate exprima într-o formă naturală sau într-o formă valorică, legătura între cele două expresii fiind realizată prin preţurile exprimate în unităţi monetare. Să considerăm expresia valorică a producţiei. Producţia totală (brută) xi a oricărei ramuri i are două destinaţii: •

parte, ce conţine producţiile intermediare în cantităţile xij , j = 1, n , trece în cele n ramuri pentru a fi folosită la realizarea producţiei ramurii respective;

•

altă parte, yj, producţia finală, se consumă în afara ramurilor, în primul rând prin fondul de consum. Astfel, se poate scrie sistemul de ecuaţii liniare: n

xi = ∑ xij + y i j=1

44

,

i = 1, n

care caracterizează repartiţia. Notând cu z j , j = 1, n , valoarea producţiei nete constituită în primul rând din venitul naţional, se poate scrie un sistem de ecuaţii liniare echivalent cu cel de sus: n

x j = ∑ xij + z j

,

j = 1, n

i=1

Presupunând consumurile xij proporţionale cu producţiile brute xj, se pot introduce coeficienţii de proporţionalitate: aij =

xij ; i, j = 1, n , xj

numiţi coeficienţii cheltuielilor directe şi în locul primului sistem de ecuaţii liniare putem scrie: n

xi = ∑ aij x j + yi

,

i = 1, n

j=1

sau matriceal: X=AX+Y, adică (E-A)X=Y. Dacă pentru vectorul produs final (Y) dat, sistemul este compatibil atunci se obţine vectorul producţiei brute corespunzătoare, X. Acest model al lui Leontief se foloseşte (ca instrument matematic) mai ales în planificare, în stabilirea balanţei după un ciclu de lucrări trimestriale sau anuale, de aceea modelul detaliat, în formă dinamică prin care se reflectă variaţia în timp a „balanţei” se studiază la disciplina de specialitate utilizând un aparat matematic mai complex. Teme 1. Folosind metoda pivotului, calculaţi rangul matricei :  1 −2 7    5 A = −3 4  − 1 0 19    Verificaţi rezultatul, folosind alte metode calculare a rangului matricei. 2. Folosind metoda pivotului, calculaţi inversa matricei :  2 3  B =   7 1 Verificaţi rezultatul obţinut. 45

3. Folosind metoda pivotului, rezolvaţi sistemul de ecuaţii liniare :  2x + 3y − z = 2  − x + 2 y + 2 z = 1  x + 5y + z = 3  Verificaţi rezultatul, folosind alte metode de rezolvare a sistemului de ecuaţii. Rezumat Metoda pivotului este o metodă eficientă pentru determinarea rangului şi inversei unei matrice, precum şi pentru rezolvarea şi discutarea sistemelor de ecuaţii liniare, întrucât pune la dispoziţie o metodă unică ce foloseşte doar operaţiile aritmetice fundamentale : adunare, scădere, înmulţire şi împărţire. În plus această metodă este potrivită pentru a fi programată, deci o bună stăpânire a sa coroborată cu anumite cunoştinţe de programare poate genera un program eficient şi general pentru soluţionarea multor probleme algebrice. În finalul ultimului paragraf s-a prezentat o aplicare în domeniul economic

a

noţiunilor

prezentate

în

decursul

subcapitolelor

precedente. Test de evaluare 1. Folosind metoda pivotului, calculaţi şi discutaţi în funcţie de parametrul α, rangul matricei : 1 2   A =  2 α 

30 puncte

2. Folosind metoda pivotului, rezolvaţi şi discutaţi, în funcţie de valorile parametrilor α şi β, sistemul de ecuaţii liniare :  x + αy − z = 2  − x + βy + 2 z = 1  x + 5y + z = 3 

46

60 puncte

Testul nr. 1 1.

2.

Folosind partiţionarea să se calculeze AB, unde :

2 − 2 1 − 1 − 2  1 −1  2     2 −2 1 2  −1  1 −1 − 2 A= ,B = 2 −2 1 − 1 2 1 −1 − 2     − 2  − 2  1 1 2 2 1 1 − −    

Să se calculeze inversa matricei :

3 2 4   1 C = 0 1  2 2 − 1   3.

Să se rezolve ecuaţia matriceală AX=B, unde :

1 − 1 1  1 − 1 3     1 0  şi B =  4 3 2 A = 2  1 −1  1 − 2 5 1    4.

Să se rezolve sistemul :

1 x   − 1 2 −1       1 2 − 3  y  =  − 5  3 1 4  z   − 4  

5.

Să se determine λ, µ∈R astfel încât matricele următoare să fie liniar dependente :

3 1  −1 2  0 −1 − 5 λ µ       5 − 2  , C =  − 9 10 − 1 A =  − 3 4 − 1 , B =  − 3  0 1 − 2  1 0 − 5 − 2 5 0      

6.

Se dau bazele :

 1 − 1 2  1 2 − 1     1 A =  1 3 2 , B =  3 0 2  2 2 − 1 1 − 1    T şi vectorul v = (0 4 − 2 ) 7.

a) să se afle vA ; b) Din vA să se determine vB Folosind metoda pivotului să se calculeze rangul matricei :

 1 − 2 7   4 5 A = − 3  −1 0 19    2 3  şi să se B =   7 1

8.

Utilizând metoda pivotului să se afle inversa matricei

9.

verifice rezultatul obţinut. Cu metoda pivotului să se rezolve sistemul de ecuaţii liniare :

 2x + 3y − z = 2  − x + 2 y + 2 z = 1  x + 5y + z = 3  Notă : Din oficiu se acordă 10 puncte. Fiecare subiect este notat cu maxim 10 puncte. (Astfel o lucrare perfectă obţine 100p, adică nota 10). Testele rezolvate se predau la prima întâlnire de lucru sau prin poştă. Titular de disciplină, Prof. univ. dr. Constantin Popp 47

1.12. Spaţiu euclidian În finalul primului capitol sunt prezentate noţiuni legate de problematica

spaţiilor

euclidiene

(transformări

liniare,

forme

pătratice), care îşi găsesc şi ele aplicabilitatea în domeniul economic. Pentru o bună asimilare a cunoştinţelor din acest subcapitol se recomandă alocarea a circa trei ore de studiu.

! Produsul scalar

1. Produsul scalar a doi vectori n-dimensionali. Fie vectorii din spaţiul Rn, X=(x1, x2, … ,xn)T. Definim (analitic) produsul scalar al vectorilor X şi Y prin scalarul: X ⋅ Y = x1 y1 + x2 y 2 + ! + x n y n

(1.12.1)

sau matriceal: XY=XTY, unde XTY este elementul matricei (XTY). Din (1.12.1) deducem uşor proprietăţile produsului scalar:

"

Proprietăţile produsului scalar

! Vectori ortogonali

! Norma

1) X⋅Y=Y⋅X (comutativ) 2) X⋅(y+Z)=X⋅Y+X⋅Z (distributiv faţă de adunarea vectorilor) 3) (λX)⋅Y=λ(X⋅Y) (asociativ la înmulţirea cu un scalar) 4) X⋅Y=0 dacă X sau Y sunt nuli sau dacă X ⊥ Y (ortogonali) Dacă Y=X, din (1.12.1) obţinem: X ⋅ X = X 2 = x12 + x 22 + ! + x 2n , de unde: X = x12 + x 22 + ! + x 2n

(1.12.2)

reprezintă norma sau mărimea sau lungimea vectorului X. Proprietăţile normei: a) X=0 dacă X=0 şi X>0 dacă X≠0 b) λX=λ⋅X c) X+Y≤X+Y

Definiţie: Un spaţiu vectorial Rn în care am definit produsul scalar a doi vectori, adică am introdus o metrică prin norma unui vector, se numeşte spaţiu euclidian n-dimensional şi-l notăm En.

48

2. Sisteme ortogonale de vectori. Considerăm în En un sistem de T m vectori X i = ( x1i , x 2i ,! , xni ) , i = 1, m .

Dacă vectorii Xi sunt

# Sistem ortogonal

ortogonali doi câte doi, zicem că sistemul de vectori este ortogonal. Între vectorii Xi şi Xj are loc relaţia: X i ⋅ X j = X i ⋅ X j ⋅ δ ij

(1.12.3)

unde δij este simbolul lui Kronecker. Se arată uşor că vectorii sistemului sunt liniar independenţi şi dacă n m=n ei formează o bază în E , numită bază ortogonală.

Astfel, considerând relaţia: λ1X1+ … +λmXm=0, înmulţim

#

Bază ortogonală

succesiv cu vectorii bazei şi ţinem seama de (1.12.3) şi că X i > 0 , ( ∀ )i = 1, m . Rezultă că λ 1 = λ 2 = ! = λ m = 0 Considerând versorii sistemului (vectorii unitate), baza obţinută (ortogonală şi normată) se numeşte ortonormată. De exemplu baza iniţială formată cu vectorii unitari Ei este o bază ortonormată. Matricea unei baze ortonormate se numeşte matrice ortogonală, T T A=(V1 V2 … Vn), ViVj=δij _i A⋅A =A A=Un, adică inversa unei

matrice ortogonale coincide cu transpusa, iar det A=±1.

#

Bază ortonormată

# Matrice ortogonală

Teme 1. Să se calculeze produsul scalar şi normele următorilor vectori v1=(1 0 –1) ; v2=(2 0 2). Sunt ortogonali ? 2. Fie vectorii : v1 = (1

2 01

2 ) , v 2 = (1

2 0 -1

2 ) , v3 = (0 1 0) .

Formează ei o bază ortogonală ? Dar un ortonormată ? 3. Car este diferenţa între o matrice ortogonală şi o bază ortogonală ? 1.13. Transformări liniare. 1. Definiţii. Se numeşte formă un polinom omogen. Polinomul este omogen dacă toţi termenii săi au acelaşi grad. n Numim formă liniară în R o expresie omogenă de gradul întâi în

n variabile: 49

#

Formă liniară

f = c1 x1 + c2 x2 +!+ c n xn

(1.13.1)

Introducând vectorii: X=(x1 x2 … xn)T şi C=(c1 c2 … cn)T - numit vector al formei liniare, forma f se scrie matriceal: f = C ⋅ X = C T X, fiind

f

elementul

matricei

T

(C X)1×1.

(1.13.2) Din

(1.13.2)

rezultă

corespondenţa biunivocă dintre formele liniare f în n variabile şi vectorii C∈Rn.

!

Ansamblul a m forme liniare în n variabile se numeşte sistem de n forme liniare în R :

Sistem de forme liniare

! Transformare liniară

f i = ci1 x1 + ci 2 x 2 + ! + cin x n , i = 1, n

(1.13.3)

Matricea C=(cij)m×n se numeşte matrice a sistemului de forme liniare, iar rangul ei este rangul sistemului. Dacă m=n sistemul de forme liniare se numeşte transformare liniară. Fie transformarea liniară:  y 1 = c11 x1 + c12 x 2 + ! + c1n x n   y 2 = c 21 x1 + c 22 x 2 + ! + c 2n x n   !!!!!!!!!!!!  y n = c n1 x1 + c n 2 x 2 + ! + c nn x n 

(1.13.4)

T T unde: f i = y i , C = ( cij )n , Y = ( y1 y 2 ! y n ) , X = ( x1 x 2 ! xn ) .

!

Sub formă matriceală, transformarea (1.13.4) se scrie, deci: Y = CX,

Matricea transformării. Modulul transformării

(1.13.5)

matricea C fiind matricea transformării iar μ=det C modulul ei. Dacă C este nesingulară (μ≠0), transformarea este nedegenerată

!

(sau inversabilă), iar în caz contrar (rang C
Matrice degenerată

Transformarea liniară (1.13.5) transformă un vector X∈Rn într-un

degenerată. alt vector Y∈Rn deci este o transformare internă a spaţiului vectorial

! Transformare internă, identică. Omotetie

n

R. În particular, dacă C=Un atunci Y=X şi transformarea este identică. 50

Dacă C este o matrice scalară, atunci Y=kX şi transformarea este o omotetie. 2. Operaţii cu transformări liniare 1) Suma transformărilor liniare Y=AX, Z=BX este transformarea V=(A+B)X=SX unde: (1.13.6)

S=A+B

2) Produsul transformărilor liniare Y=AX, Z=BY este o transformare care permite trecerea directă de la X la Z, adică aplicarea succesivă a celor două transformări:

# Suma transformărilor

# Produsul transformărilor

Z=B⋅AX=(BA)X

(1.13.7)

Aceasta este tot o transformare liniară, nedegenerată dacă transformările factori sunt nedegenerate. 3) Transformarea inversă a unei transformări liniare. Fie Y=CX nedegenerată (C - nesingulară ⇒(∃)C-1). Înmulţind la stânga cu C-1, obţinem inversa transformării liniare date: -1

care transformă pe Y în X din Rn. 3. Tranformări ortogonale. Zicem că transformarea liniară Y=AX ortogonală

dacă

matricea

Transformarea inversă

(1.13.8)

X=C Y,

este

#

A

este

ortogonală.

Inversa

transformării, deoarece A-1=AT este X=ATY, tot o transformare ortogonală. Vom arăta în continuare că produsul scalar a doi vectori este un invariant al transformărilor ortogonale. Astfel, fie X1 şi X2 din Rn şi respectiv transformările ortogonale Y1=AX1, Y2=AX2. Avem:

# Transformare ortogonală

"

Inversă transformării ortogonală este egală cu transpusa

T T T T T -1 T Y 1 Y 2 = Y 1 Y 2 = ( AX 1 ) AX 2 = X 1 ( A A) X 2 = X 1 ( A A) X 2 = X 1 X 2 = X 1 X 2

În particular, transformările ortogonale păstrează mărimile

" Produsul scalar este un invariant al transformărilor ortogonale

vectorilor şi ortogonalitatea a doi vectori. De exemplu, transformarea:  x′ = x cosθ - y sin θ   y′ = x sin θ + yxosθ

"

este ortogonală. Inversa ei,

Rotaţie de unghi θ a axelor de coordonate

51

 x = x′ cos θ + y′ sin θ   y = -x′ sin θ + y′ cos θ este tot o transformare ortogonală (det A=cos2θ+sin2θ=1) Din (x')2+(y')2=x2+y2 rezultă că mărimea vectorului X'=(x'y')T este

egală

cu

mărimea

vectorului

T X=(xy) .

Tranformarea

exemplificată reprezintă o rotaţie de unghi θ a axelor de coordonate din plan, în jurul originii. 4. Valori proprii ale unei matrice. Fie transformarea liniară Y=AX cu A=(aij)n şi punem condiţia ca X să fie paralel cu transformatul său (Y) adică Y=sX (s - scalar). Deci: Y = AX ⇒ sX = AX ⇒ (A - sU)X = 0 ,

(1.13.9)

sau dezvoltat:  ( a 11 - s) x1 + a12 x 2 + ! + a1n x n = 0   a 21 x1 + ( a 22 - s) x 2 + ! + a 2n x n = 0   !!!!!!!!!!!!!!  a n1 x1 + a n 2 x 2 + ! + ( a nn - s) x n = 0

(1.13.10)

Condiţia ca sistemul omogen (1.13.10) să admită şi soluţie diferită de soluţia banală este: " a11 − s a12 a1n a21 a22 − s " a2 n =0 # # # " ann − s an1 an 2

!

Ecuaţie caracteristică Valori proprii

(1.13.11)

Ecuaţia (1.13.11) de gradul n în s, se numeşte ecuaţie caracteristică a transformării sau a matricei A, iar rădăcinile sale se numesc valori proprii ale matricei A. O matrice pătrată de ordinul n are n valori proprii (reale sau complexe). Se demonstrează că dacă A este simetrică atunci toate valorile proprii sunt reale.

! Vectori proprii

Vectorii Xi obţinuţi prin înlocuirea succesivă a lui s cu valorile proprii, în sistemul (1.13.10), se numesc vectori proprii ai matricei A. Exemplu: Să se afle valorile proprii ale matricei: 52

5 5 0   A = 5 8 - 3    0 - 3 13  Avem ecuaţia caracteristică: 5-s

5

5 8-s 0

$

0

Pentru devoltarea determinantuli, se observă că dacă se adună linnile a doua şi a treia la pima linie, se obţine de trei ori 10-s pe linia întâi, care se poate scoate factor comun, iar apoi se va dezvolta determinantul

- 3 = 0 care se scrie (s-1)(s-10)(s-15)=0.

- 3 13 - s

Deci valorile proprii sunt: s1=1, s2=10, s3=15. Teme 1. Să se calculeze valorile şi vectorii proprii ai matricei : 1 2 1   A =  0 5 9  0 0 3   1.14. Forme pătratice 1. Expresia generală şi rangul unei forme pătratice. Se numeşte formă pătratică o expresie algebrică omogenă, de

#

Formă pătratică

gradul doi în variabilele x1, x2, … ,xn:

f = a11 x12 + a 22 x 22 + ! + a nn x 2n + 2 a12 x1 x 2 + 2 a13 x1 x3 + ! + 2 a n-1,n x n-1 x n = n

n

= ∑ ∑ aij xi x j ; aij = a ji i=1 j=1

(1.14.1)

Această expresie se poate scrie: f = x1 ( a11 x1 + a12 x 2 + ! + a1n xn ) + x 2 ( a12 x1 + a 22 x 2 + ! + a2n x n ) + + ! + xn ( a1 n x1 + a 2 n x 2 + ! + a nn xn ) +

(1.14.2)

Introducem notaţiile:  y 1 = a11 x1 + a 12 x 2 + ! + a 1n x n   y 2 = a12 x1 + a 22 x 2 + ! + a 2n x n   !!!!!!!!!!!!  y n = a1n x1 + a 2n x 2 + ! + a nn x n 

(1.14.3)

53

Se obţine astfel o transformare liniară (1.14.3) cu matricea simetrică:  a11 a12 " a1n     a12 a22 " a2 n  A= # # #    a   n1 an 2 " ann 

!

Matricea formei pătratice

(1.14.4)

numită matricea formei pătratice iar rangul ei - rangul formei pătratice.

!

Discriminantul formei pătratice Formă pătratică nedegenerată

Determinantul Δ=det A se numeşte discriminantul formei pătratice Dacă rang A=n, forma pătratică este nedegenerată iar în caz contrar, când rang A
f = ∑ xi y i = X ⋅ Y = X T Y sau f = X T AX,

(1.14.5)

i=1

sub formă matriceală.

!

Aplicarea unei transformări liniare asupra variabilelor dintr-o formă pătratică

2. Aplicarea unei transformări liniare asupra variabilelor dintr-o formă pătratică. Aplicăm formei (1.14.5) transformarea liniară X=BY. Deoarece T T T T X =(BY) =Y B , forma pătratică f devine:

f = Y T ( BT AB)Y = Y T CY

(1.14.6)

iar (BTAB)T=BTAT(BT)T=BTATB=BTAB, adică în urma aplicării transformării liniare, se obţine o nouă formă pătratică cu matricea T

C=B AB unde B este matricea transformării liniare.

"

Rangul formei pătratice nu se schimbă dacă se aplică o transformare liniară nedegenerată

" di

Teorema i i tl i

Dacă B este nesingulară, rang C=rang A, adică rangul formei pătratice nu se schimbă dacă asupra variabilelor aplicăm o transformare liniară nedegenerată. Notând cu Δ şi respectiv Δ' discriminanţii formei pătratice (1.14.5) şi formei pătratice (1.14.6) iar cu μ - modulul transformării liniare, avem: ∆′ = µ 2 ∆ ,

(1.14.7) 54

relaţie numită teorema discriminantului. Dacă transformarea liniară este unimodulară, Δ'=Δ. Exerciţii: Se dă forma pătratică: f = 2 x12 + 3 x22 + 9 x32 + 4 x1 x2 - 4 x1 x3 , asupra căreia se aplică transformarea liniară:  x1 = y 1 - y 2 + 3 y 3   x2 = y 2 - 2 y3  y3  x3 = Să se scrie forma pătratică transformată. Avem:  1 - 1 3  2 2 - 2     A =  2 3 0  , B =  0 1 - 2  şi:     1  - 2 0 9 0 0 2 0 0   C = BT AB =  0 1 0    0 0 3   2 2 2 Forma transformată va fi deci: f = 2 y1 + y 2 + 3 y 3 .

3. Forma canonică a unei forme pătratice. Forma canonică a unei forme pătratice este o sumă algebrică de cel mult n pătrate şi se poate aplica fie metoda lui Gauss fie metoda transformărilor liniare. Reţinem că forma canonică a unei forma

#

Forma canonică a unei pătratice f

pătratice nu este unică, aşa cum va rezulta mai jos. a) Metoda lui Gauss. În forma (1.14.1) presupunem a11≠0 şi formăm un pătrat din termenii care conţin variabila x1: f=

1 a11

f =

2 11

Metoda lui Gauss de obţinere a formei canonice a unei forme pătratice

2 1

[ a x + 2 a11 x1 ( a12 x 2 + ! + a1n x n )] + f 1 ' 1 [a11x1 + a12 x2 + ! + a1n xn ]2 + f1 , a11

"

(1.14.8)

unde f1 este o formă pătratică în (n-1) variabile. Aplicăm transformarea liniară:

55

 X 1 = a 11 x1 + ! + a1n x n   x i = x0 , ∀ i = 2,n

(T1)

şi forma pătratică devine: f=

1 a11

X 1 + α 22 x 2 + 2 α 23 x2 x3 +!+ 2 α 2n x2 xn +!+α n-1,n x n-1 x n 2

2

Presupunem acum α22≠0 şi procedăm analog: f=

1 a11

2

X1+

1

α 22

( α 22 x 2 +α 23 x3 +!+α 2n x n )2 + f 2

unde f2 este o

formă liniară în (n-2) variabile. Apoi, aplicăm transformarea: X 1 = X 1   X 2 = α 22 x 2 + α 23 x 3 + ! + α 2n x n   xi = x i , ∀ i = 3,n

(T2)

şi forma devine: f=

1 a11

2

X1+

1

α 22

2 X 2+ f 2

Procedeul continuă până la epuizarea tuturor variabilelor obţinându-se o sumă algebrică de cel mult n pătrate, numită forma canonică a formei pătratice: f = k 1 X 12 + k 2 X 22 +!+ k n X 2n ,

(1.14.9)

unde Xi sunt forme liniare în variabilele x1, x2, … ,xn. Observaţie: S-a presupus iniţial că a11≠0. În caz contrar, considerăm altă necunoscută xi pentru care aii≠0. Dacă forma nu conţine termeni pătratici, aplicăm transformarea liniară nedegenerată:  x1 = y 1 + y 2   x2 = y1 - y 2   x i = y i , i = 3,n

(1.14.10)

şi procedeul poate fi aplicat. Exemplul 1: Să se aducă la forma canonică: f = 2 x12 + 3 x22 + 9 x32 + 4 x1 x2 - 4 x1 x3 . 56

Avem succesiv: f = 2[ x12 + 2 x1 ( x2 - x3 )] + 3 x 22 + 9 x32 f = 2( x1 + x2 - x3 )2 + x 22 + 7 x32 + 4 x 2 x3 f = 2( x1 + x 2 - x3 )2 + ( x 2 + 2 x3 )2 + 3 x32 f = 2 X 12 + X 22 + 3 X 32 , unde: X 1 = x1 + x 2 - x3 , X 2 = x 2 + 2 x3 , X 3 = x3 Exemplul 2: Să se aducă la forma canonică: f = x1 x 2 + 2 x1 x 3 + x 2 x 3 Aplicăm transformarea (1.14.10) pentru că forma nu conţine termeni pătratici.  x1 = y 1 + y 2  (T) x 2 = y 1 - y 2 ⇒ f = y 12 - y 22 + 3 y 1 y 3 + y 2 y 3   x3 = y3 Prin metoda lui Gauss avem succesiv: 3 2 9 2 2 y3 ) - y3 - y2 + y2 y3 2 4 3 1 1 9 f = ( y1 + y 3 )2 - ( y 2 - y 3 )2 + y 32 - y 32 4 2 2 4 3 1 f = ( y1 + y 3 )2 - ( y 2 - y 3 )2 - 2 y 32 2 2 f = ( y1 +

Transformarea inversă va fi: 1 1 y1 = ( x1 + x 2 ), y 2 = ( x1 - x2 ), y 3 = x3 2 2 şi revenind la variabilele xi: 1 1 f = ( x1 + x 2 + 3 x3 )2 - ( x1 - x 2 - x3 )2 - 2 x32 4 4 . b) Metoda transformărilor liniare (Jacobi). Rangul unei forme pătratice fiind un invariant în aplicarea unei transformări liniare asupra variabilelor, rangul formei canonice (1.14.9) este egal cu rangul matricei Δ. Rezultă că numărul de pătrate din forma canonică a unei forme pătratice este egal cu rangul ei. Se demonstrează că printr-o transformare liniară, o formă pătratică poate fi adusă la forma canonică: 57

"

Metoda lui Jacobi de obţinere a formei canonice a unei forme pătratice

f = s1 X 12 + s 2 X 22 + !+ s m X 2m ,

(1.14.11)

unde si sunt valorile proprii ale matricei A. De asemenea, folosind transformarea Jacobi, forma canonică a unei forme pătratice nedegenerate devine: f = ∆0 X 12 + ∆1 X 22 +!+ ∆ n-1 X 2n , ∆1 ∆2 ∆n

(1.14.12)

unde: a 11 a12 a 13 a11 a 12 , ∆ 3 = a 12 a 22 a 23 ,! , ∆ n = detA ∆0 = 1 , ∆1 =| a11 | , ∆ 2 = a 12 a 22 a13 a 23 a 33 sunt determinanţii principali ai matricei A. Exemplu: Considerăm forma pătratică din exemplul precedent, f = 2 x12 + 3 x22 + 9 x32 + 4 x1 x2 - 4 x1 x3 . şi aplicăm (1.14.12). Avem: 22-2 22 = 2 , ∆3 = 2 3 0 = 6 ∆ 0 = 1 , ∆1 = 2 , ∆ 2 = 23 -20 9 ⇒f =

1 2 2 2 2 2 1 2 1 2 2 X 1+ X 2+ X 3 = X 1+ X 2+ X 3 2 2 6 2 3

4. Forme pătratice pozitiv definite.

!

Forme pătratice pozitiv, semipoitiv, negativ, seminegativ definite şi nedefinite

Definiţie: Forma pătratică f=XTAX este semipozitiv definită dacă: X T AX ≥ 0 , ( ∀ )X ∈ R n şi pozitiv definită dacă: XTAX>0 (∀) T

X≠0, adică X AX=0 ⇒ X=0. În aceste situaţii, zicem că matricea A, a formei,

este

semipozitiv

definită

respectiv

pozitiv

definită.

Asemănător se definesc formele şi matricele seminegativ definite sau negativ definite. Din definiţie, rezultă că în forma canonică (1.14.9) toţi coeficienţii ki sunt pozitivi sau negativi. În caz contrar, forma nu este pozitiv definită (respectiv negativ definită). De exemplu, forma pătratică 2 2 2 2 f=2x1 +4x1x2+x2 =2(x1+x2) -x2 este nedefinită, semnul ei depinzând

de vectorul X∈R2. Dacă X=(0 1)T atunci f>0 iar dacă X=(-2 4)T 58

atunci f<0.

"

Proprietăţi: 1) O formă pătratică pozitiv (negativ) definită este nedegenerată 2) O formă pătratică este pozitiv definită dacă toate valorile proprii ale matricei ei sunt pozitive 3) O formă pătratică este pozitiv definită dacă toţi Δi>0. Pentru ca n * f să fie negativ definită trebuie să avem Δi =(-1) Δi>0(∀)i=1,n

Exerciţiu: Să se arate că forma pătratică f = x12 + 5 x 22 + 10 x32 - 4 x1 x 2 - 6 x 2 x3 este pozitiv definită. Avem:  1 - 2 0   A =  - 2 5 - 3  şş ∆1 = 1 , ∆ 2 = 1 , ∆ 3 = 1 Deci: ∆i > 0 pentru    0 - 3 10  i=1, 2, 3 ⇒ f>0 iar forma canonică este: f = X 12 + X 22 + X 32 Teme 1. Să se aducă la forma canonică atât prin metoda Guass cât şi prin metoda Jacobi forma pătratică următoare : f = 5 X 12 + X 22 + 10 X 32 + 4 X 1 X 2 + 6 X 1 X 3 Rezumat Un spaţiu euclidian este un spaţiu vectorial înzestrat cu operaţia de produs scalar. Pe baza produsului scalar se poate defini norma unui vector. Doi vectori sunt ortogonali, dacă produsul scalar al lor este nul. O bază este ortogonală dacă toţi vectorii săi sunt ortogonali. O bază ortogonală, în care toţi vectorii au norma egală cu 1, este ortonormată. Matricea unei baze ortonormate, se numeşte ortogonală. Inversa unei matrice ortogonale este egală cu transpusa ei. 59

Proprietăţi ale naturii formei pătratice

Transformarea liniară este o aplicaţie (funcţie) liniară între două spaţii vcetoriale. Matricea asociată sistemului de ecuaţii ce definesc transformarea liniară, se numeşte matricea transformării liniare. Determinantul acestei matrice se numeşte modulul transformării. Formă pătratică este o funcţie de la un spaţiu vectorial la R, care este un polinom care are toţi termenii de gradul doi. Forma pătratică se poate transforma prin mai multe metode (Gausss, Jacobi, a valorilor proprii) în aşa fel încât să fie doar o sumă algebrică de variabile la puterea a doua (forma canonică). Dacă în forma canonică toţi termenii au semnul plus atunci forma pătratică este pozitiv definită (dacă numărul termenilor este egal cu dimensiunea spaţiului) sau semipozitiv definită (dacă sunt mai puţini), respetiv negativ sau negativ definită dacă toţi termenii au semnul minus. Dacă există cel puţin câte un termen cu semnul plus şi unul cu semnul minus, forma pătratică este nedefinită. Valorile proprii ale unei matrice A, sunt soluţiile sistemului de ecuaţii AX=X, unde X este un vector. Test de evaluare 1. Să se aducă la forma canonică forma pătratică următoare : f = 5 X 12 + X 22 + 9 X 32 + 4 X 1 X 2 + 6 X 1 X 3 Precizaţi natura sa.

35 puncte

2. Calculaţi valorile şi vectorii proprii ai matricei :  2 1 3   X = 1 4 1  3 1 2   55 puncte

60

Cap. 2. PROGRAMARE LINIARĂ

2.1. Introducere Se ştie că unui sistem de ecuaţii liniare i se poate asocia o singură ecuaţie matriceală AX=B. Rezolvarea ei se face prin reducerea matricei [A,B] în raport cu matricea A. O problemă ceva mai complicată, derivată din această metodă este rezolvarea condiţionată a sistemului de ecuaţii liniare astfel ca necunoscutele xi , i = 1, n , să fie nenegative şi în acelaşi timp să se optimizeze (maximizeze sau minimizeze) o funcţie liniară de forma: f( x1 , x2 ,! , x n ) = c1 x1 + c 2 x 2 +!+ cn x n - d Funcţia se poate scrie prescurtat sub forma: f=CX-d, unde C=[c1,…,cn] este matricea coeficienţilor, X=[x1,…,xn] este matricea

!

Funcţia obiectiv

necunoscutelor iar d termenul liber. Problema formulată mai sus este o problemă de programare liniară. Acest al doilea capitol propune o incursiune în această problematică ce are implicaţii profunde în economie. În primele două paragrafe, a căror studiere necesită circa două ore, se propune o introducere în terminologie şi problematica studiată. Datele problemei pot fi trecute într-o matrice de forma:  A B S=  C d  La o problemă de programare liniară, soluţia sistemului AX=B, X≥0, numită soluţie posibilă, se deosebeşte de soluţia problemei de programare liniară, pentru care în afară că este o soluţie posibilă, avem şi fopt=CV-d (max. sau min.) La fel cum soluţia sistemului de ecuaţii liniare, AX=B, se obţine prin reducerea matricei [A,B] şi soluţia problemei de programare liniară se obţine printr-o reducere de tip special a matricei S. Metoda respectivă se numeşte metoda simplex, pe care o prezentăm în continuare.

61

!

Soluţie posibilă

2.2. Noţiunea de matrice simplex

"

Definiţia 1: se numeşte matrice simplex o matrice de forma:  A B S=  C d 

Matrice simplex

formată dintr-o matrice oarecare Am× n, o matrice coloană Bm× 1, o matrice linie C1× n şi un număr d. Orice matrice pătrată de ordin cel puţin doi se poate organiza ca o matrice simplex.

" Cazurile în care se poate situa matricea simplex

După natura submatricelor A, B şi C deosebim mai multe cazuri: 1) Matricea linie C se află într-unul din următoarele trei cazuri: a) C≤0 (nepozitivă) b) Conţine cel puţin un element cj>0, pentru care coloana corespunzătoare Kj a matricei A este nepozitivă (Kj≤0). c) Conţine elemente pozitive cj>0 şi oricare ar fi cj>0 coloana corespunzătoare Kj a matricei A conţine cel puţin un element pozitiv (aij>0). 2) Matricea coloană B se află într-unul din următoarele două cazuri: a) B≥0 (nenegativă) şi oricare ar fi elementul bi=0, primul element diferit de zero din linia Li a matricei A este pozitiv. b) Conţine cel puţin un element bi<0 sau un element bi=0 astfel ca primul element diferit de zero din linia Li a matricei A este negativ.

#

Dacă matricea A include toate coloanele celei mai mari matrice unitate ce se pot îngloba în ea, indiferent de ordinea în care apar, atunci matricea A este redusă. Dacă pe linia C, sub fiecare coloană a matricei unitate identificată ca mai înainte este valoarea 0, atunci C este redusă în raport cu A

 A 3) Matricea   se află într-unul din următoarele trei cazuri: C  a) Este redusă în raport cu matricea A. b) Matricea A este redusă, dar C nu este redusă în raport cu A. c) Matricea A nu este redusă. Cele opt cazuri simple determină pentru matricea simplex în total 3⋅2⋅3=18 cazuri compuse: (1a,2a,3a),(1a,2a,3b), … Exemplul 1. Matricea simplex 1 " - 1 - 1 2   1 -3 -2 " - 2  S= ,  ! ! ! ! !   - 2 " - 6  1 -2 62

cu submatricele: 1 - 1 2  - 1 A=   , B =   , C = [-2 1 - 2] , d = -6 , se încadrează în - 2   1 - 3 - 2 cazul (1c,2b,3c), deoarece: - linia C conţine elementul c2=1>0 (singurul element pozitiv) şi 2 coloana K 2 =   a matricei A conţine elementul pozitiv a12=2. - 3  - coloana B conţine elemente negative, de exemplu b1=-1 - matricea A nu este redusă Exemplul 2: Matricea simplex 1 " 7  1 0   0 1 1 " 3  S= , ! ! ! ! !    0 - 3 - 4 " - 4  cu submatricele: 1 0 1 7  A=  , B =   , C = [0 - 3 - 4] , d = -4 ,  0 1 1 3  este în cazul (1a,2a,3b), deoarece: C≤0, B>0, primele două coloane ale matricii sunt reduse, dar c1=0 şi c2=-3≠0. Astfel matricea 1 1 0 A     1 1 C  = 0     0 - 3 - 4  este în situaţia când A este redusă, dar linia C nu este redusă în raport cu A. Exemplul 3: Matricea simplex:  1 0 0 0   S = 0 - 3 1 2  , 0 1 0 3  cu submatricele: 1 0 0 0  A=   , B =   , C = [0 1 0] , d = 3 , 2 0 - 3 1 este în cazul (1b,2a,3a), pentru că linia C conţine elementul c2=1>0 pentru care K 2 = [

0 ] ≤ 0 , coloana B este nenegativă (B≥0) iar pentru -3 63

elementul b1=0 , primul element diferit de zero , a11 din linia L1=[1 0 0] a matricei A este pozitiv (a11=1) şi în fine matricea 1 0 0 A     C  = 0 - 3 1 este redusă în raport cu A (coloanele 1 şi 3)    1 0  0 Din punct de vedere aplicativ, prezintă o importanţă deosebită cazurile (1a,2a,3a) şi (1b,2a,3a), pentru care dăm următoarea:

" Matrice simplex redusă

Definiţie 2. Matricea simplex  A* B*  = S  * * C d  se numeşte matrice simplex redusă, dacă sunt îndeplinite condiţiile : *

*

-

linia C este în cazul 1 a) sau 1 b) -

-

*

coloana B este în cazul 2 a)  A*  matricea  *  este în cazul 3 a) C 

În cazul particular când elementele pivot cu coloană redusă au perechile de indici (1,1), (2,2), …, (m,m), matricea simplex redusă are următoarea formă: 1 # 0 a1*, m +1  " " " * S = * 0 # 1 a m ,m +1  * 0 # 0 c m +1 unde B*≥0 şi în cazul 1a) C*≤0, iar în

b1*   " bm*   # c n* d *  cazul 1b) de exemplu c*m+1>0, # a1*n " * # a mn

dar K*m+1≤0, unde:

" Matrice simplex se poate reduce

 a*1,m+1   b*1    *   * * * * B =  "  , K m+1 =  "  , C = [0 ! 0 c m+1 ! c n ] a*m,m+1 b*m    Dacă o matrice simplex neredusă S admite matrice simplex redusă S*, aceasta se poate obţine printr-o transformarea E*, produs de transformări elementare. Exemplul 4: Matricea simplex S, din exemplul 2, prin adunarea la linia a treia a liniei a doua înmulţită cu trei (transformare E*), trece în matricea simplex redusă S*=E*S: 64

1 0 1 7    * S = 0 1 1 3, 0 0 - 1 5  

$

Matrice simplex şi reducerea lor

cu submatricele: 1 0 1 * 7  * * , B =   , C = [0 0 - 1] , d * = 5 . A =  0 1 1 3  Linia C* este nepozitivă, deci este în cazul 1a). Coloana B* este pozitivă, deci este în cazul 2a), iar matricea:  1 0 1  A*     *  = 0 1 1 C    0 0 - 1 este redus_ în raport cu matricea A, deci este în cazul 3a). Coloanele reduse sunt coloana întâi şi coloana a doua. Rezultă că S* este o matrice simplex redusă. Transformarea E*, prin care matricea simplex S trece în matricea simplex redusă S*, nu poate fi oarecare ci numai una convenabilă. Astfel, reducerea matricelor simplex este o problemă specială de reducere, ce se rezolvă prin metoda simplex, potrivit căreia, cazurile simple (1a,b,c;2a,b;3a,b,c) se reduc la o parte din ele, conform schemei: 1c) 2b) 3c) _ _ ↓ ↓ 1a) 1b) 2a) 3b) ↓ 3a) de unde se vede că cele 18 cazuri compuse se reduc la cele două care caracterizează o matrice simplex redusă şi prin urmare pe această cale se rezolvă şi problema reducerii. Rezumat Orice matrice S se poate organiza ca o matrice simplex, partiţionând-o astfel încât să fie puse în evidenţă ultima linie 65

(denumită C), ultima coloană (denumită B) şi ultimul element (denumit d). Partea rămasă este notată cu A. Când toate elementele lui C sunt mai mici sau egale cu 0, matricea S este în cazul 1 a). Dacă printre elementele strict pozitive ale lui C există cel puţin unul care are întreaga coloană situată deasupra sa mai mică sau egală cu 0, atunci matricea S este în cazul 1 b). Dacă nu e în nici unul din cazurile precedente, matricea S este în cazul 1 c). Când toate elementele lui B sunt strict mai mari ca zero, atunci matricea S este în cazul 2 a). Tot în cazul 2 a) este atunci când B are pe lângă elemente strict pozitive şi zerouri, iar linia situată în stânga fiecărui element egal cu 0 al liniei B, are primul element (diferit de zero) un număr pozitiv. În caz contrar (fie B are cel puţin un element strict mai mic ca zero, fie un linia situată în stânga unui element egal cu zero are primul element nenul strict mai mic decât zero), matricea S este în cazul 2 b). Dacă matricea A nu este redusă (nu include toate coloanele matricei unitate), atunci matricea S este în cazul 3 c). Dacă matricea A este redusă, dar C nu este redusă în raport cu A (sub cel puţin o coloană a matricei unitate înglobată în A există un element nenul în linia C), atunci matricea este în cazul 3 b). Dacă C est redusă în raport cu A, matricea S este în cazul 3 a). Matricea simple S este redusă dacă este într-unul din cazurile 1 a) 2 a) 3 a) sau 1 b) 2 a) 3 a) Test de evaluare 1. Să se decidă în ce cazuri sunt matricele următoare : 0  0 A= 1  0 

1 0 0 0

0 1 0 0

1 0 −1   1 0 2 ; B=  2 1 0   1 2 2  

0 1 0 0

1 2 − 2 0 0    0 0 −1 1 0 ; C = 2 1 0 0 2     2 2 0 2 2   

(fiecare va fi notată cu câte 30 de puncte)

66

2.3. Algoritmul simplex Cele patru paragrafe ce sunt cuprinse în acest modul descriu algoritmul simple de aducere o matrice simple la forma redusă a ei. Se recomandă alocarea a minim trei ore pentru înţelegerea algoritmului simplex. Întrucât ultimul modul conţine un set bogat de exerciţii, recomandăm utilizarea sa ca suport pentru uşurarea înţelegerii noţiunilor din acest modul. Considerăm două matrice linie oarecare: X=[x1 … xn;x] şi Y=[y1 … yn;y] Zicem că linia X este mai mică decât linia Y, X
! Definirea comparaţiei întredoi vectori

De exemplu, X=[1 1 2;4] < Y=[10 0 1;7] deoarece x=4<7=y. La fel, X=[2 3 -1;6] < Y=[2 5 -3;6] deoarece x=6=y, x1=2=y1,x2=3<5=y2. Dacă XX. Dacă elementele corespunzătoare sunt egale, liniile sunt egale: X=Y. O astfel de ordonare a liniilor se numeşte ordonare lexicografică. Pe baza ordonării lexicografice, toate liniile cu un acelaşi număr de elemente pot fi comparate cu linia 0 formată numai din elemente egale cu zero. Observaţie: Matricea S* s-a notat cu asterisc ca şi matricea redusă, dar în general aceasta nu este o matrice redusă. Fie aij elementul pivot fixat în matricea simplex S': ! !    -1 -1 aij Li aij bi     ! !    A′ B ′ S′ =  =    C ′ d ′  L p - a pj aij-1 Li b p - a pj a-ij1 bi    ! !    d - c j a-ij1 bi   c - c j aij-1 Li Condiţia că matricele simplex sunt egale în cazul 2a) înseamnă că liniile sunt negative şi linia pivot chiar pozitivă, adică: 67

! Ordonare lexicografică

[ aij-1 Li , a-1ij bi ] > 0 _ aij > 0 , iar din: [ L p - a pj aij-1 Li , b p - a pj aij-1 bi ] ≥ 0 , rezultă fie apj≤0, fie, prin împărţirea inegalităţii cu apj, apj>0, să avem: [ L i , bi ] aij

≤

[ Lp ,bp ] a pj

Astfel, pentru alegerea elementului pivot dintr-o coloană fixată Kj a matricei A trebuie să determinăm linia minimă (sau una oarecare dintre liniile minime când există mai multe), a-1ij[Li,bi], dintre liniile

"

Condiţia de alegere a elementului pivot

-1 pj[Lp,bp]:

a

[ L i , bi ] aij

= min

[ L p ,bp ] a pj

,

unde p parcurge mulţimea de indici pentru care apj>0. Să presupunem cj>0. Comparând liniile [C',d'] şi [C,d] constatăm că [C,d]>[C',d']. Într-adevăr, dacă bi≠0, atunci în virtutea condiţiilor cj>0 şi aij>0 rezultă: d'=d-cja-1ijbi0, rezultă: -1

cr ′ = c r - c j aij air < c r ′ unde c'r este primul element în linia C', care diferă de elementul corespunzător al liniei C. În concluzie, inegalitatea stabilită pentru ultimele două linii are loc. Dacă matricea S' încă nu este în cazul 1a) sau 1b), transformarea de mai înainte se repetă schimbând locul matricei S cu S', a lui S' cu S", … ,obţinându-se un şir de matrice simplex: S', S", …, căruia îi corespunde un şir de inegalităţi de linii: [C , d] > [C ′ , d ′] > [C" , d" ] > " Se poate arăta că şirul de matrice simplex construit este finit cu un ultim element S* care este o matrice simplex aflată în cazul 1a) sau 1b) şi în concluzie: algoritmul simplex descris mai sus este finit şi conduce la matricea S*. Pentru ca numărul matricelor simplex construit să fie minim, nu se cunoaşte nici un criteriu, dar se acceptă „apriori“ criteriul de alegere a coloanei de redus (costuri marginale) : pentru ca numărul matricelor 68

simplex intermediare să fie minim, considerând un mare număr de cazuri de aplicare a algoritmului simplex, este suficient ca la fiecare etapă ultima linie a matricei simplex să descrească cu valoarea maximă. Pentru ca diferenţa: [ ,b ] [C , d] - [C ′ , d ′] = c j Li i aij să fie maximă, trebuie să alegem acel indice de coloană j pentru care are loc relaţia: cj

[ Li , bi ] aij

!

Condiţia de alegere a coloanei de redus

[ ,b ] = max ( c q Li i ) , aiq q

unde q parcurge mulţimea de indici pentru care cq>0. Formularea algoritmului simplex: Pentru a transforma matricea simplex S, aflată în cazul (1c,2a) într-o matrice simplex S*, aflată în cazul (1a,2a) sau (1b,2a) se procedează în felul următor: 1) Se alege un element pivot aij>0. Operaţia se poate efectua în două moduri: - fără aplicarea criteriului de alegere a coloanei de redus, determinând indicele i potrivit relaţiei: [ L i , bi ] aij

= min

[ L p ,bp ] a pj

,

unde j este un indice pentru care cj>0 ales în mod arbitrar şi p parcurge mulţimea de indici pentru care apj>0, - cu aplicarea criteriului menţionat, determinând perechea de indici (i,j) potrivit relaţiei: cj

[ Li , bi ] aij

= max ( c q min q

p

[ Lp ,bp ] a pq

),

unde q _i p (pentru q fixat) parcurg mulţimea de indici pentru care cq>0, respectiv apq>0. 2) Se trece, prin reducerea coloanei de indice j cu elementul pivot ales, la o matrice simplex S'. 3) Se reiau operaţiile de la punctele precedente, schimbând locul matricei S cu S', a lui S' cu S", … până ce termenul S* al şirului de 69

! Algoritmul simplex

matrice simplex astfel construit, va fi o matrice simplex care se găseşte în cazul 1a) sau 1b). Observaţie: În cazul când pentru fiecare coloană Kq există un singur raport pozitiv minim c-1iqbi, relaţiile prin care se determină elementul pivot iau următoarele forme simple: bp bp bi b = min _i c j i = max ( c q min ) aij a pj aij a pq p p q 2.4. Aplicaţii ale algoritmului simplex Algoritmul simplex se aplică îndeosebi în două cazuri particulare:  A 1) Matricea   este redusă în raport cu matricea A. C  În acest caz şi matricele:  A′ C ′ ,  

 A*   * C 

 A"  C"  , " ,  

vor fi reduse în raport cu matricea corespunzătoare: A', A", … , A*. 2) Matricea [C,d] este suma acelor linii ale matricei [A,B], care nu sunt linii pivot cu coloană redusă. În acest caz se poate scrie: C = ∑ Lk k∈K

, d = ∑b , k

k∈K

unde K este mulţimea indicilor liniilor care se însumează. Matricea simplex în acest caz are forma:  A S =  ∑ Lk  k∈K

# Teorema de existenţă

B



∑b  k

k∈K



Teoremă. Dacă există o matrice X≥0, pentru care are loc egalitatea AX=B, atunci prin aplicarea algoritmului simplex, se obţine o matrice redusă de forma (fără demonstraţie) :  A* B*  = S   0 0  *

70

2.5. Algoritmul simplex modificat Pentru a transforma matricea simplex S cu coloana B nenegativă şi cu linia C aflată în cazul 1c) într-o matrice simplex S* cu coloana B* nenegativă şi cu linia C* aflată în cazul 1a) sau 1b), se procedează în felul următor: 1) Se alege un element pivot aij>0. Operaţia se poate efectua cu cele două procedee amintite la formularea algoritmului simplex: - fără aplicarea criteriului (modificat) de alegere a coloanei de redus, determinând indicele i potrivit relaţiei:

# Algoritmul simplex modificat

b bi = min p , a pj aij p unde j este un indice ales în mod arbitrar a_a ca cj>0, iar p parcurge mulţimea de indici pentru care apj>0, - cu aplicarea criteriului, determinând perechea de indici (i,j) potrivit relaţiilor: c j = max c q , q

b bi = min p , a pj aij p

unde q parcurge mulţimea de indici pentru care cq>0, iar pentru i fixat p parcurge mulţimea de indici pentru care apj>0 2) Se trece prin reducerea coloanei de indice j cu elementul pivot ales la o matrice simplex S' 3) Se reiau operaţiile de la punctele precedente, schimbând locul matricei S cu S', a lui S' cu S", … până ce termenul S* al şirului astfel construit va fi o matrice simplex care se găseşte în cazul 1a) sau 1b) sau se constată că s-a produs fenomenul de ciclare: au apărut două matrice simplex identice. Avantajele algoritmului simplex modificat. - Condiţia B≥0 este mai simplă decât condiţiile cuprinse în cazul 2a), care, pentru liniile cu elemente bi egale cu zero, cer ca primul element diferit de zero din linia respectivă să fie pozitiv. - Criteriul de alegere a elementului pivot este mai simplu deoarece se determină numai rapoarte simple şi nu rapoartele unor linii. Totodată maximul elementelor pozitive cq se poate aprecia la vedere, 71

# Avantajele algoritmului simplex modificat

fără a fi nevoie de calcularea mai multor coloane de rapoarte.

# Dezavantajele algoritmului simplex modificat

Dezavantajele algoritmului simplex modificat. - Considerând numai condiţia B≥0, pot fi elemente bi=0. Aplicând algoritmul simplex modificat, poate să apară fenomenul de ciclare. Matricea simplex, dacă conţine elemente bi=0, se numeşte matrice simplex degenerată şi dacă nu conţine elemente bi nule, se numeşte matrice simplex nedegenerată. Astfel, are loc cazul de degenerare, respectiv nedegenerare, după cum în şirul S, S', S", … sunt sau nu sunt matrice degenerate. - Un dezavantaj datorat renunţării la cazul 2a) constă în aceea  A că, la aplicaţia a doua de la paragraful 2.4, matricea   poate să nu se C  reducă. Criteriul de alegere a coloanei de redus în cazul de faţă asigură într-o măsură şi mai mică, decât criteriul corespunzător de la algoritmul simplex (nemodificat), ca numărul matricelor intermediare să fie minim. Comparând avantajele şi dezavantajele prezentate mai sus, bilanţul înclină în direcţia avantajelor. Odată cu folosirea noţiunii de algoritm simplex modificat se modifică şi noţiunea de matrice simplex redusă.

" Matrice simplex redusă modificată

Definiţie: Se numeşte matrice simplex redusă modificată, matricea simplex S* care se găseşte în cazul (1a,3a) sau (1b,3a) şi are coloană B* nenegativă. 2.6. Algoritmul reducerii simplex. Pentru a determina în cazul unei matrice simplex,  A B S=  C d  matricea simplex redusă,  A* B*  S =  * * , C d  *

" Algoritmul reducerii simplex

se parcurg următoarele trei etape: I) Matricea simplex S se transformă, prin înmulţirea cu (-1) a liniilor negative ale matricei [A,B], într-o matrice simplex S1, care este în cazul 2a): 72

 A1 B!  S1 =  , Cd  II) Matricea simplex S1 se transformă într-o matrice simplex S3:  A*1 B*1 = S3  * * , C d  aflată în cazul 3a), după cum urmează: 1) Se asociază matricei S1 o matrice simplex S2:  A1  S2 =  L1k  k∑  ∈K

B1   b1k  ∑ k∈K 

,

în care ultima linie este suma acelor linii [L1k,b1k] ale matricei [A1,B1] care nu sunt linii pivot cu coloana redusă în raport cu matricea A1. Matricea simplex S2, prin aplicarea algoritmului simplex, se reduce la o matrice simplex:  A*1 B*1 = S  , 0 0  * 2

2) Ultima linie a matricei S2*, formată din zerouri, se înlocuieşte cu linia [C,d] a matricei simplex S1, obţinând matricea simplex S2**: *

*

A1 B1 ], S =[ C d ** 2

aflată în cazul 3b). 3) Se adună la ultima linie a lui S2**, combinaţia liniară: - c j [ L*1i , b*1i ] - c q [ L*1p , b*1p ] - " a celor r linii pivot cu coloană redusă ale matricei [A*1,B*1], unde (i,j),(p,q),… sunt perechile de indici ale elementelor pivot cu coloană redusă. Ca rezultat se obţine matricea simplex redusă S*. Observaţii: 1) Dacă matricea simplex S se găseşte în cazul 2a), respectiv ** B≥0, atunci S1=S. Dacă S1 se găseşte în cazul 3b) atunci S1=S2 . Dacă ** ** S2 se găseşte în cazul 3a) atunci S2 =S3. Dacă S3 se găseşte în cazul * 1a) sau 1b) atunci S3=S .

2) Toate transformările care se aplică sunt produse de 73

transformări elementare, deci transformarea E*, prin care matricea simplex S se reduce la matricea S*, E*S=S* este tot un produs de transformări elementare. 3) În cazul r<m, liniile egale cu zero ale matricei [A*1,B*1] pot fi omise. Rezumat 1. Matricea simplex S se transformă, prin înmulţirea cu (-1) a liniilor negative ale matricei [A,B], într-o matrice simplex S1, care este în cazul 2a). Se asociază matricei S1 o matrice simplex S2:  A1  S2 =  L1k  k∑  ∈K

B1   b1k  ∑ k∈K 

,

în care ultima linie este suma acelor linii [L1k,b1k] ale matricei [A1,B1] care nu conţin valoarea 1 a unei coloane a matricei unitate, ce are 0 sub ea (coloană redusă). Matricea simplex S2, prin aplicarea algoritmului simplex, se reduce la o matrice simplex:  A*1 B*1 = S  , 0 0  * 2

2) Ultima linie a matricei S2*, formată din zerouri, se înlocuieşte cu linia [C,d] a matricei simplex S1, obţinând matricea simplex S2**:  A*1 B*1 ** S2 =  , C d  aflată în cazul 3b). 3) Se adună la ultima linie a lui S2**, combinaţia liniară: - c j [ L*1i , b*1i ] - c q [ L*1p , b*1p ] - " a acelor linii care au valoarea 1 a unei coloane a matricei unitate, ce nu are 0 sub ea (nu e redusă). Ca rezultat se obţine matricea simplex redusă S*.

74

Test de evaluare 1. Să se aplice algoritmul studiat matricei următoare : 1 −2 1   1   1 1 − 2  1 X = 1 1  −2 1    1 −2 1 1  

90 de puncte

75

2.7. Formularea problemei canonice. Acest ultim modul, a cărui dimensiune este justificată printr-un bogat set de exemple aflat la finalul său, prezintă diferite variante ale algoritmului simplex, precum şi aplicaţiile sale în diferite situaţii concrete (probleme de transport, etc.). În funcţie de cititor studiul său necesită 2–4 ore.

! Problema canonică

În limbajul sistemelor de ecuaţii liniare, problema canonică generală sau mai simplu problema canonică se poate formula astfel: Să se determine acele soluţii nenegative x1, x2, … ,xn ale sistemului de ecuaţii liniare:  a11 x1 + ! + a1n x n = b1  !!!!!!!!!! ,  a 1 x +!+ a x = b mn n m  m 1 pentru care funcţia liniară f=-d+c1x1+ … +cnxn, devine maximă.

! Formularea matriceală

! Formularea problemei canonice reduse

Formularea matriceală: Să se determine acele soluţii X≥0, ale ecuaţiei AX=B, pentru care funcţia liniară f=-d+CX devine maximă. (A este matricea sistemului, X - matricea coloană a necunoscutelor, B matricea coloană a termenilor liberi iar C=[c1 … cn]). Formularea problemei canonice reduse. Problemei canonice date i se poate asocia matricea simplex S, care prin reducere devine S*, căreia îi corespunde o problemă, numită problema canonică redusă, care constă în: Să se determine acele soluţii X≥0 ale ecuaţiei matriceale * * * * A X=B pentru care funcţia liniară f=-d +C X devine maximă. Caz particular: În cazul când elementele pivot cu coloană redusă au perechile de indici (1,1), (2,2), … ,(m,m), problema canonică redusă, în limbajul ecuaţiilor şi formelor liniare, se formulează astfel: Să se determine soluţiile nenegative x1, x2, … ,xn ale sistemului:  x1 + a*1,m+1 x m+1 + ! + a*1n x n = b*1   !!!!!!!!!!!! ,  + * * *  xm a m,m+1 x m+1 + ! + a mn xn = bm pentru care funcţia liniară f=-d*+C*m+1Xm+1+ … +Cn*Xn devine maximă. Matricelor simplex intermediare S', S", … le corespund 76

probleme canonice intermediare. După natura fiecăreia dintre matricele care apar, problema canonică respectivă se numeşte problemă canonică degenerată, respectiv problemă canonică nedegenerată. 2.8. Rezolvarea problemei canonice. Rezolvarea problemei canonice în cazul 1a). În acest caz, prblema canonică are maxim finit. Pentru simplitate, considerăm problema în cazul particular de mai sus. În cazul general, când numărul elementelor pivot cu coloană redusă este r≤m, se poate raţiona în mod similar. 1) Determinarea soluţiilor de bază. Mai întâi demonstrăm existenţa unei soluţii de bază, iar după aceea le determinăm pe toate. Se constată direct că matricea:  b*1    " b*m  X1=   , 0  "    0  este o soluţie nenegativă, X1≥0, A*X1=B*. O astfel de soluţie cu cel mult m componente pozitive, numite componente de bază, se numeşte soluţie de bază, anume soluţie de bază degenerată, respectiv soluţie de bază nedegenerată, după cum conţine sau nu conţine componente de bază nule. Pentru X1, funcţia ia valoarea f1=-d*. Fie X' o soluţie nenegativă oarecare: A*X'=B*. Deoarece C*≤0, rezultă C*X'≤0 şi deci pentru X' avem: f'=-d*+C*X'≤-d*=f1. Astfel, f1=fmax şi prin urmare X1 este o soluţie de bază a problemei canonice. Aceasta se poate citi împreună cu valoare fmax=-d* direct din matricea simplex redusă S*. Urmează să determinăm toate soluţiile de bază. Pentru a avea f'=fmax este necesar ca acele componente * x'q ale matricei X' pentru care coeficientul corespunzător cq al funcţiei

este negativ cq*<0, să fie egale cu zero: x'q=0. Notăm cu t numărul coeficienţilor c* egali cu zero, cj*=0. Pentru simplificarea notaţiei, să presupunem că aceşti coeficienţi sunt primii t, adică: 77

" Rezokvarea problemei canonice

*

*

*

*

c1 = ! = cm = c m+1 = ! = ct = 0 Fără a restrânge generalitatea se poate presupune că t≥m+1. În ecuaţia A*X=B* anulăm necunoscutele xt+1, … ,xn corespunzătoare coeficienţilor negativi cq* şi scriem sistemul de ecuaţii liniare:  x1 + a*1,m+1 xm+1 + ! + a*1t xt = b*1  !!!!!!!!!!!!!! ,  * * *  xm + a m,m+1 x m+1 + ! + a mt xt = bm Anulăm câte (t-m) necunoscute în toate cele Ctt-m=Ctm moduri posibile şi obţinem tot atâtea sisteme de ecuaţii, fiecare cu câte m necunoscute. Rezolvând aceste sisteme se stabilesc soluţiile nenegative de bază X1, … ,Xs care totodată sunt soluţiile de bază ale problemei canonice. În afară de aceste s soluţii, problema nu are alte soluţii de bază. 2) Determinarea soluţiei generale.

!

Combinaţie liniară convexă

Definiţie. Orice matrice X = g 1 X 1 + ! + g s X s , unde numerele g i (i = 1, s ) îndeplinesc condiţia g i ≥ 0, i = 1, s , g 1 + ! + g s = 1 se numeşte combinaţie liniară convexă a soluţiilor de bază X1, …, Xs. Nu este o restricţie esenţială din punctul de vedere al aplicaţiilor programării liniare, dacă se presupune că valorile necunoscutelor soluţiilor problemei canonice sunt mărginite. Are loc următoarea

"

Combinaţiile liniare ale soluţiilor de bază formează soluţiile

Teoremă: În cazul când valorile componentelor soluţiilor sunt mărginite, combinaţiile liniare ale soluţiilor de bază (ele şi numai ele), formează soluţiile. Demonstraţia teoremei are două părţi: combinaţiile liniare convexe formează soluţii şi orice soluţie este o combinaţie liniară convexă a soluţiilor de bază. Vom demonstra numai prima parte: Fie X o combinaţie liniară convexă a soluţiilor de bază X1, … ,Xs. Din egalităţile AX1=B, … , AXs=B rezultă AX=B, deoarece: AX=A(g1X1+ … +gsXs)=g1AX1+ … +gsAXs=g1B+ … +gsB=(g1+ … +gs)B=B. La fel, din: -d+CX1=-d*, … ,-d+CXs=-d*, rezultă că: -d+CX=78

* * * d , deoarece: -d+CX=-d+C(g1X1+ … +gsXs)=g1(-d )+ … +gs(-d )=(g1+ * * * … +gs)(-d ) =-d . Prin urmare, -d+CX=-d =fmax. Deoarece condiţia

X≥0 se verifică potrivit condiţiilor g1≥0, … ,gs≥0, rezultă că orice combinaţie liniară convexă, X a soluţiilor de bază este o soluţie a problemei canonice. Observaţie: Fără detaliere, menţionăm că în anumite cazuri simple combinaţia liniară convexă se numeşte simplex, de unde derivă denumirea de metodă simplex. Discutarea problemei canonice în cazul 1b. Pentru fixarea ideilor, considerăm C*m+1>0 şi K*m+1≤0. Matricea coloană,

" Discutarea problemei canonice în cazul 1 b)

 b*1 - Ma*1,m+1    "   b*m - Ma*m,m+1  X(M) =  M   0    "   0  pentru M≥0 este o soluţie nenegativă, X(M)≥0, a ecuaţiei matriceale * * * * A X(M)=B . Valoarea funcţiei f pentru X(M) este f(M)=-d +MC m+1 şi

prin urmare f(M) odată cu M poate lua valori oricât de mari. În acest caz se spune că fmax=+∞. Cazul însă nu prezintă interes din punctul de vedere al aplicaţiilor şi de aceea nu-l detaliem în continuare. 2.9. Schema de rezolvare a problemei canonice prin metoda simplex Acele soluţii X≥0 ale ecuaţiei matriceale AX=B, pentru care funcţia liniară f=-d+CX devine maximă, se determină astfel: 1) Se scrie matricea simplex corespunzătoare, S iar prin algoritmul reducerii simplex se construieşte matricea simplex redusă, * S:

 A B  *  A* B*  S=  , S =  * * C d  C d  2) Dacă S* este în cazul 1a) atunci fmax=-d* (finit), iar dacă S* 79

" Schema de rezolvare a problemei canonice prin metoda simplex

este în cazul 1b) atunci fmax=+∞. 3) Se determină soluţiile finite după cum urmează: - Componentele de bază ale soluţiilor de bază X1, … ,Xs sunt soluţiile de bază nenegative ale ecuaţiei matriceale A* X = B* , unde A* este formată din acele coloane Kj* ale matricei A* pentru care elementul corespunzător cj* al liniei C* este egal cu zero, cj*=0, iar matricea coloană X este formată din necunoscutele corespunzătoare xj; restul componentelor sunt nule. - Soluţia generală este dată de combinaţia liniară convexă a soluţiilor

de

bază:

X=g1X1+

…

+gsXs,

unde:

g i ≥ 0 , i = 1, s _i g 1 + !+ g s = 1. Observaţie: Dacă problema canonică are o singură soluţie, care desigur este soluţie de bază, atunci nu numai fmax, ci şi soluţia se citeşte nemijlocit din matricea simplex redusă. Dacă (i,j),(p,q),… sunt perechile de indici ale elementelor pivot cu coloană redusă, atunci componentele de bază ale soluţiei sunt următoarele: xj=bi*, xq=bp*,… 2.10 Problema generală. Cea mai cuprinzătoare problemă de programare liniară se numeşte problemă generală. În limbajul sistemelor de ecuaţii şi inecuaţii precum şi de forme liniare, problema generală se formulează astfel: Să se determine acele soluţii xi ≥ 0 , i = 1, n , ale sistemului de

!

Problema generală

ecuaţii-inecuaţii liniare:  a11 x1 + ! + a1n x n = b1  !!!!!!!!!!!!   a p 1 x1 + ! + a pn x n = b p }   a p+1,1 x1 + ! + a p+1,n xn ≤ b p+1   !!!!!!!!!!!! }  a x +!+ a x ≤ b q1 1 qn n q   a q+1,1 x1 + ! + a q+1,n x n ≥ bq+1 }  !!!!!!!!!!!!!  a m1 x1 + ! + a mn x n ≥ bm  pentru care funcţia liniară f=-d+c1x1+ … +cnxn devine maximă (fmax), respectiv minimă (fmin) 80

Observaţie: În programarea liniară se folosesc uzual şi alte denumiri, ca de exemplu: Sistemul de ecuaţii-inecuaţii de mai sus se numeşte sistemul de restricţii (condiţii). Funcţia liniară se numeşte funcţie obiectiv (funcţie scop sau funcţie de eficienţă). O soluţie nenegativă a sistemului de restricţii se numeşte soluţie posibilă. O soluţie posibilă pentru care funcţia obiectiv devine maximă sau minimă se numeşte soluţie optimă. Formularea matriceală a problemei generale: Să se determine acele soluţii X≥0 ale sistemului de ecuaţii-inecuaţii matriceale: A1X=B1, A2X≤B2, A3X≥B3 pentru care funcţia liniară f=-d+CX devine optimă. (Notaţiile matriceale se disting uşor din sistemul dat) Rezolvarea problemei generale, constă în asocierea unei probleme canonice la problema generală dată prin folosirea necunoscutelor auxiliare:  xn+q - p+1  x n+1      U =  "  ,V =  "   x n+m - p   x n+1- p  Sistemul de ecuaţii matriceale, al problemei canonice asociate va fi:  A1 X = B1   A2 X + U = B 2  A X -V = B 3  3 O soluţie X≥0 a sistemului, completată cu matricele nenegative U=B2-A2X≥0, V=A3X-B3≥0, dau o soluţie nenegativă a sistemului de ecuaţii matriceale asociat. Invers, o soluţie nenegativă (X,U,V) a sistemului asociat dă totodată o soluţie nenegativă X a sistemului de ecuaţii matriceale dat, deoarece A1X=B1, iar A2X+U=B2⇒ U=B2A2X≥0, adică A2X≤B şi A3X-V=B3⇒V=A3X-B3≥0⇒ A3X≥B3. Pentru fmax se lucrează cu funcţia dată, iar pentru fmin se trece la (-f), opusă celei date, deoarece din (-f)≤(-f)max rezultă: f≥-(-f)max şi deci fmin=-(-f)max

81

# Formularea matriceală a problemei generale

" Schema de rezolvare a problemei generale

Schema de rezolvare a problemei generale 1) Problemei generale date i se asociază o problemă canonică cu sistemul de ecuaţii matriceale:  A1 X = B1   A2 X + U = B 2  A X -V = B 3  3 şi cu funcţia: f=-d+CX când se cere fmax, respectiv -f=d-CX când se cere fmin. Această problemă canonică asociată se rezolvă. 2) fmax=-d* şi fmin=d*, obţinute prin rezolvarea problemei canonice asociate. 3) Soluţiile sunt următoarele: - soluţiile de bază: X1, … ,Xs sunt matricele corespunzătoare grupelor de matrice X1,U1,V1; … ;Xs,Us,Vs care reprezintă soluţiile de bază ale problemei canonice asociate, - soluţia generală, care este combinaţia liniare convexă: X=g1X1+ … +gsXs, unde: g i ≥ 0 , i = 1, s _i g 1 + !+ g s = 1. Observaţie: În cazul când se cere simultan atât maximul cât şi minimul funcţiei f, operaţiile algoritmului reducerii simplex pentru determinarea matricei simplex reduse sunt identice până la scrierea matricei simplex S3. 2.11. Probleme duale.

!

Problema duală

Formularea problemelor duale. Folosind notaţiile matriceale:  a11 # a1n   x1   b1      A= " "  , X =  "  , B =  "  , Y=[y1, …, ym], C=[c1, …, a m1 # a mn   x n  bm  cn] se pot formula următoarele probleme: 1) Să se determine acele soluţii X≥0 ale inecuaţiei AX≤b, pentru care funcţia f=CX devine maximă. 2) Să se determine acele soluţii Y≥0 ale inecuaţiei YA≥C, pentru care funcţia g=YB devine minimă. Aceste probleme sunt duale una alteia. Rezolvarea problemelor duale se bazează pe 82

Teorema: Dacă problema 1) admite soluţie finită, atunci şi problema 2) admite soluţie şi reciproc, având loc relaţia: fmax=gmin.

" Reciprocitatea existenţei soluţiilor

Demonstraţia conţine evident două părţi, pornind de la una din cele două probleme. Dacă plecăm de la problema 1), potrivit rezolvării problemei generale, trebuie să trecem la o problemă canonică asociată: AX+U=B, CX=f, unde:  x n+1  U =  "  ≥ 0  x n+m  Presupunem că am determinat matricea simplex redusă, care prin ipoteză are m elemente pivot cu coloană redusă. Pentru simplificare, presupunem liniile acestei matrice, reordonate, astfel ca elementele pivot cu coloană redusă de indice de coloană mai mic să fie şi într-o linie de indice mai mic. Notăm cu A1 matricea determinată de cele m linii şi acele coloane ale matricei [A,E] care corespund coloanelor reduse considerate din matricea simplex redusă. Cu C1 notăm matricea determinată de linia [C,0] şi coloanele matricei A1, unde 0 este o linie formată din m zerouri corespunzătoare necunoscutelor auxiliare cu coeficienţi egali cu zero, în funcţia f. Pentru a trece de la problema canonică la problema canonică redusă, ecuaţia AX+U=B se înmulţeste la stânga cu Y0=C1A-1. Apoi: (C - Y 0 A)X - Y 0 U = f - Y 0 B Din expresia care conţine funcţia f, potrivit cazului 1a) al algoritmului simplex, se citeşte: Y0A≥C, Y0≥0 şi fmax=Y0B. Rezolvând problema 1), s-a găsit o soluţie posibilă Y0 a problemei 2), pentru care funcţia g ia valoarea g0=Y0B. Pentru a demonstra teorema (partea a doua), va fi suficient să se arate că gmin=g0. Pe baza inecuaţiilor celor două probleme, considerând o soluţie oarecare X≥0, respectiv Y≥0, au loc inegalităţile AX≤B, YA≥C, de unde obţinem: YAX≤YB, YAX≥CX, adică: YB≥CX. Considerând că X şi Y reprezintă soluţiile problemei, rezultă: fmax≤gmin. Având în vedere că 83

g0=fmax, rezultă că are loc egalitatea ce trebuia demonstrată: fmax=gmin. Totodată s-a obţinut o soluţie Y0 pentru care g îşi atinge valoare minimă. Această soluţie s-a obţinut însă rezolvând problema formulată pentru fmax fără să se rezolve şi problema formulată pentru gmin. Componentele matricei Y0 sunt tocmai coeficienţii, cu semn schimbat, ai necunoscutelor auxiliare din funcţia de maximizat f. X  Pentru o soluţie   cu k componente pozitive şi (n+m-k) U  componente nule, corespund C nm+- km- k soluţii de bază care, din cauza celor (m-k) componente nule sunt identice, dar pentru care ultima linie diferă în general în matricea simplex redusă. Continuând reducerea matricei simplex S* pentru toate aceste posibilităţi, se determină toate soluţiile de X  bază Y pentru o soluţie de bază   . Efectuând aceste calcule pentru U  X  toate soluţiile de bază   , se obţin toate soluţiile de bază X. U  Observaţie: Din AX=B rezultă AX≤B, respectiv din YA=C rezultă YA≥C. Astfel, în ipoteza că valoarea maximă, respectiv minimă, este atinsă de o soluţie de bază X, cu U=0, respectiv V=0, teorema dualităţii se poate considera şi în cazul când cel puţin una dintre restricţiile matriceale este ecuaţie. 2.12. Probleme derivate. Metoda simplex este metoda generală de rezolvare a tuturor problemelor de programare liniară. Prin particularizări ale sistemului de restricţii, a funcţiei de optimizat sau prin impunerea unor restricţii suplimentare asupra datelor problemei, se obţin diferite modele derivate ale problemei de programare liniară ce se rezolvă prin metode specifice modelului derivat. În continuare ne referim la descrierea sumară a modelelor respective.

! Probleme de transport

2.12.1 Problema de repartiţie (transport) Se cere să se determine acele soluţii xij ≥ 0 , i = 1, m , j = 1, n ale sistemului de ecuaţii liniare:

84

 x11 + ! + x1n = a1 !!!!!!!!!   x m 1 + ! + x mn = a m ,   x11 + ! + x m1 = b1 !!!!!!!!!   x1n ! + x mn = bn unde: ai ≥ 0 , i = 1, m ; b j ≥ 0 , j = 1, n ; a1 +!+ a m = b1 +!+ bn , pentru care funcţia: f=c11x11+…+c1nx1n+…+cm1xm1+…+cmnxmn devine minimă. Problemei i se poate asocia un tabel de repartiţie: c11

…

c1n

a1

...................................................

…

cm1

…

cmn

am

b1

…

bn

Dacă a1 + !+ a m ≠ b1 +!+ bn , problema se numeşte problemă de repartiţie neechilibrată. Dacă a1 + !+ a m > b1 +!+ bn , problema se poate echilibra completând tabelul cu o coloană de indice (n+1), punând: c1,n+1 = 0,! ,cm,n+1 = 0 şi m

n

1

1

bn+1 = ∑ ai - ∑ b j La fel, dacă sensul inegalităţii este „<“. 2.12.2. Programarea liniară cu reoptimizare. Mai multe probleme de programare liniară, dintre care unele diferă parţial de altele, formează probleme de programare liniară cu reoptimizare. Astfel, fiind rezolvată una dintre probleme, rezolvarea celorlalte necesită în general mai puţine calcule, unele rezultate fiind comune. Operaţiile prin care se poate trece de la o problemă la alta sunt următoarele: - modificarea vectorului C - modificarea vectorului B - modificarea unei coloane a matricei A 85

# Probleme cu reoptimizare

- modificarea unei noi variabile şi a unor noi restricţii. Aici, A, B, C sunt submatricele din matricea simplex S. 2.12.3. Programarea liniară în numere întregi.

! Probleme cu variabilele numere întregi

Spre deosebire de problemele de programare liniară care se cer a fi rezolvate în mulţimea numerelor reale nenegative (notate PL), apar frecvent probleme care cer ca toate componentele soluţiei să fie numere întregi, conducând la o problemă de programare liniară total întreagă (PLT), sau ca o parte din componentele soluţiei să fie numere întregi, iar celelalte să fie numere reale, conducând la probleme de programare liniară mixtă (PLM). 2.12.4. Programarea liniară în numere reale. Metoda simplex (PL) se poate adapta uşor la rezolvarea

!

problemelor de programare liniară în domeniu real, respectiv parţial real

Probleme cu variabilele numere negative

necunoscută yn+1 şi să facem substituţia xi = yi - y n+1 , i = 1, n , ca

- parţial nenegativ. În acest scop, cel mai uşor este să introducem o nouă

problemă PL obişnuită şi prin substituţia inversă se obţine valoarea necunoscutelor reale

xi , i = 1, n . Se pot substitui numai unele

necunoscute xi. Cele nesubstituite se consideră necunoscute nenegative. În afara acestor modele derivate mai există şi programarea liniară parametrică în care matricea simplex depinde de un număr de parametrii ti=S(t1, … ,ts). Pentru multe modele există programe pe calculator.

! Decizii economice

2.13. Decizii economice. Aplicarea programării liniare în economie poate fi descompusă în

trei

faze principale caracterizate pe rând

prin

modelele

corespunzătoare: modelul economic, modelul matematic şi din nou modelul economic. În prima fază, pe baza caracteristicilor domeniului de aplicaţie, se formulează condiţiile activităţii economice-tehnice, inclusiv scopul economic. Potrivit modelului economic se formulează modelul matematic. În faza a doua se rezolvă modelul matematic şi rezultatele se 86

interpretează în modelul economic. În faza a treia se discută rezultatele obţinute în modelul economic şi se ia decizia economică. Această decizie poate fi punerea în aplicare a planului stabilit sau modificarea modelului economic iniţial şi trecerea apoi din nou la cele trei faze descrise mai sus. Aplicarea programării liniare în economie se bazează pe discipline economice, tehnice şi matematice cum ar fi: economia politică, analiza economică, economia ramurilor, analiza matematică şi statistică matematică, statistici de ramură, organizare, tehnologie etc. Aceasta presupune colaborarea a trei categorii de specialişti: economişti, ingineri şi matematicieni (sau informaticieni). 2.14. Probleme. 1. Să se prezinte schema generală de rezolvare a unei probleme canonice. Soluţie. Notăm cu S matricea simplex asociată problemei de programare liniară. Matricea simplex redusă, S*, se obţine din S prin aplicarea algoritmului reducerii simplex (ARS), care conţine în mod implicit algoritmul simplex (AS). Reducerea se face numai în raport cu matricea sistemului de restricţii A. Din coloana termenilor liberi şi din linia funcţiei de optimizat nu se alege element pivot. Dacă se cere transformarea T corespunzătoare (ARS) atunci matricea S se înlocuieşte cu matricea [E,S], care prin transformarea T devine [T,S*]. (ARS) are trei etape, realizând respectiv cazurile 2a), 3a) _i 1a) AX=B sau 1b). CX=d+f

 A B S=  C d   A* S* =  * C

B*   d*

A*X=B* C*X=d*+f

87

În cazul (AS) elementul pivot este strict pozitiv (aij>0) spre deosebire de algoritmul reducerii matricelor (ARM) când aij≠0. 2. Să se determine acele soluţii xi , xi ≥ 0 , i = 1,6 ale sistemului de ecuaţii liniare: - x1 - 2 x 2 + x4 - 5 x5 = 1   - 3 x 2 + 2 x4 - 8 x 5 = 4  - 4 x - x - x - x = -3 1 3 5 6  pentru care funcţia liniară f=-7+6x1+x2+x4+3x5 devine maximă. Soluţie. Etapa I: Aflăm mai întâi o soluţie de bază, asociind problemei date o matrice simplex apoi aplicăm (ARS) -1 - 2 0 1   0 -3 0 2 S = - 4 0 - 1 0  ! ! ! !   6 1 0 1

-5

0

"

-8

0

"

-1 -1

"

! ! ! 3

0

"

1  4 - 3  !  7 

Înmulţind linia a treia cu (-1), matricea S va fi în cazul 2a): - 1 - 2 0 1 - 5 0   0 -3 0 2 -8 0 4 0 1 0 1 1   6 1 0 1 3 0

1  4 3 7 

a Etapa II : Ultima linie se înlocuieşte cu suma primelor două linii

care nu sunt linii pivot cu coloană redusă. Se aplică (AS) -1 - 2   0 -3  4 0  − 1 − 5

1 1 / 1 = 1  0 2 - 8 0 4 4 / 2 = 2 1 0 1 1 3 0 3 − 13 0 5 0

1

-5 0

Pentru reducere se alege coloana a patra deoarece c4=3>0. Formând rapoartele dintre termenii liberi şi elementele pozitive ale coloanei a patra, observăm că 1/1=min(1/1 , 4/2) şi elementul pivot se va alege a14=1>0. Se efectuează reducerea matricei:

88

- 1 - 2 0 1 - 5 0 1   1 0 0 2 0 2  2  4 0 1 0 1 1 3   2 1 0 0 2 0 2 Alegem elementul pivot a22=1: 3  2 4   0

1 − 1 0 5  1 0 0 2 0 2 0 1 0 1 1 3 0 0 0 0 0 0 0 0

Matricea A este redusă. Ultima linie formată din zerouri se înlocuieşte cu [C,d] iniţială: 3  2 4   6

1 − 1 0 5  1 0 0 2 0 2 0 1 0 1 1 3  1 0 1 3 0 7  0 0

Se consideră reducerea astfel încât coloanele 2,3,4 să fie reduse  A în matricea   . Pentru aceasta, efectuăm transformarea elementară C  (-L1)+(-L2)+L3: 3  2 4   1

1 − 1 0 5  1 0 0 2 0 2 2 / 2 = 1 0 1 0 1 1 3 3 / 1 = 3 0 0 0 2 0 0 0 0

Acum matricea simplex se află în

cazul 3a) a Etapa III : Se aplică (AS):

1  0 1 4 2  1 1 0 0 2  3 −1 1 0  2 − 1 − 1 0 0

 6   1 0 1   0 1 2  0 0 − 2 0 0

Matricea S se află în cazul 1a) pentru că C≤0. În concluzie, ultima matrice fiind redusă suntem în cazul (1a,2a,3a). Scriem problema de programare liniară canonică redusă şi citim soluţia de bază corespunzătoare: 89

1  4 + x x 2 + x4 = 6 1  2   x + 1 x + x = 1 1 2 5 2   1 3 x1 - x2 + x3 + x6 = 2 2   - x1 - x2 = -2 + f Necunoscutele principale sunt cele corespunzătoare coloanelor reduse, adică x3, x4, x5, iar cele secundare, care se consideră nule sunt: x1, x2, x6. Deci: x1=0, x2=0, x3=2, x4=6, x5=1, x6=0 şi fmax=2. Pentru a afla soluţia generală considerăm submatricea formată din coloana B şi acele coloane ale matricei A pentru care coeficientul corespunzător al liniei funcţiei (cj) este egal cu zero: x3 x4 x5 0 1 0 0  0 0 1 0 1 0 0 1 

x6 6  1 2 

Avem C43=4 posibilităţi de a forma soluţii de bază din câte 3 necunoscute de bază, restul de o necunoscută fiind egală cu zero. Practic se anulează atâtea necunoscute cât este diferenţa între numărul variabilelor (4) şi numărul ecuaţiilor (3). Anularea se face într-un număr egal cu C41=C43=4. Rezolvând cele 4 sisteme de ecuaţii, se obţin toate soluţiile de bază, ca în tabelul de mai jos: Numărul curent

x3

x4 x5

x5

Natura sistemului

2

6

0

compatibil

al sistemului 1. 2.

0

3. 4.

1

incompatibil

0 0

6

incompatibil 1

2

compatibil

Obţinem atât soluţia de bază de mai sus cât şi încă o soluţie de bază:x1=0, x2=0, x3=0, x4=6, x5=1, x6=2. Putem scrie soluţiile de bază astfel: 90

0  0  0  0      2 0  X1=   , X 2=   6  6   1 1     0   2  iar soluţia generală: X=g1X1+g2X2 unde g1, g2≥0 şi g1+g2=1. 3. Să se rezolve problema canonică dată prin matricea simplex: 1 − 2 5 − 4 2  6 1 1  S = 1 1 2 0 − 1 1 0 Soluţie: Ultima linie se înlocuieşte cu suma primelor două linii şi aplicăm (AS) 1 − 2 5 − 4 2  2 / 1 = 2 1 1 6 1 1  1 / 1 = 1   2 − 1 11 − 3 3 0 − 3 − 1 − 5 1 1 1 6 1 1  0 − 3 − 1 − 5 1 Deoarece în ultima linie (a matricei C, respectiv linia funcţiei) nu avem cj>0, nu putem continua reducerea, deşi linia respectivă nu a devenit egală cu linia zero. Cauza este că sistemul este incompatibil, pentru valori nenegative ale necunoscutelor:  - 3 x 2 - x3 - 5 x 4 = 1   x1 + x 2 + 6 x 3 + x 4 = 1 4. Să se determine acele soluţii xi ≥ 0 , i = 1,6 ale sistemului de ecuaţii-inecuaţii liniare:  x1 - x 2 + 2 x 3 + 3 x 4 - x 5 ≤ 6   x 3 + 2 x 4 - x 5 + x6 ≥ 2 x + 3 x = 1 4  1 pentru care funcţia f=x1-x2-x3+x4 devine maximă, respectiv minimă. Soluţie: 1) Introducem necunoscutele auxiliare, nenegative x7 şi x8 pentru a „echilibra“ primele două inecuaţii şi a obţine astfel problema 91

canonică:  x1 - x2 + 2 x3 + 3 x4 - x5 + x7 = 6   x 3 + 2 x 4 - x 5 + x6 - x 8 = 2  x1 + 3 x 4 = 1  cu funcţia f neschimbată. Matricea S asociată este: " 6  1 -1 2 3 -1 0 1 0    0 0 1 2 - 1 1 0 - 1 " 2 S= 1 0 0 3 0 0 0 0 " 1  ! ! ! ! ! ! ! ! ! !    1 - 1 - 1 1 0 0 0 0 " 0  2) Aplicăm (ARS) pentru a afla fmax. 1 - 1 2  0 0 1  S = 1 0 0     1 0 0

3 -1 0

1

0

2 -1 1 0 -1 3

0 0 0

0

3

0 0 0

0

6  6 /1 = 6 2  1  1/1 = 1   1

" 5  0 -1 2 0 -1 0 1 0    0 0 1 2 - 1 1 0 - 1 " 2 S= 1 0 0 3 0 0 0 0 " 1  ! ! ! ! ! ! ! ! ! !   " 0  0 0 0 0 0 0 0 0 " 5  0 -1 2 0 -1 0 1 0   0 1 2 - 1 1 0 - 1 " 2 0 S= 1 0 0 3 0 0 0 0 " 1   ! ! ! ! ! ! ! ! ! !   " 0  1 − 1 − 1 1 0 0 0 0 0 - 1 2 0 - 1 0 1 0 5    0 0 1 2 - 1 1 0 - 1 2  * S = 3 0 0 0 0 1 1 0 0 0 - 1 - 1 - 2 0 0 0 0 - 1 Matricea simplex a apărut deja sub forma redusă, S*, în etapa a doua, deci nu are rost să se mai execute etapa a treia. Citim o soluţie de bază: 92

*

x1=1, x2=0, x3=0, x4=0, x5=0, x6=2, x7=5, x8=0 şi vedem că fmax=-d =1. Pentru a obţine soluţia generală, considerăm submatricea: x1

x5

x6

x7

x8

0 − 1 0 1 0 5  0 − 1 1 0 − 1 2    1 0 0 0 0 1 Constatăm că x1, x6, x7 nu se pot anula, deci soluţia de bază obţinută este unică. Într-adevăr, reconsiderând problema determinării soluţiei generale, numărul total al grupelor formate din câte trei necunoscute (cele de bază) C53 este egal cu numărul total al grupelor formate din câte două necunoscute egale cu zero, adică C53=C52=10. Construim un tabel în care necunoscutele egale cu zero (două din cinci) sunt trecute dinainte de tabel: Nr

x1

x5

1.

0

0

2.

0

3.

0

4.

0 0 0

Soluţie NU NU NU

0

6.

0

NU NU

0 2

5

8.

0

0

9.

0

10.

x8

0 0

1

x7

0

5. 7.

x6

0

NU 0

DA NU

0

NU

0

NU

Pe baza submatricei se scrie pentru fiecare caz sistemul de ecuaţii respectiv. De exemplu, în cazul poziţiei nr. 1 se poate scrie:  x7   x 6 − x8  0 

= 5 = 2 = 1

care se încearcă a se rezolva în domeniul numerelor reale nenegative. În cazul de faţă este incompatibil (0=1) deci nu are soluţie. Repetăm raţionamentul pentru celelalte poziţii şi vedem că obţinem doar o soluţie de bază (poziţia nr.7) Având toate soluţiile de 93

bază X i , i = 1, m (m ≥ 1) se scrie soluţia generală: m

m

i=1

1

X = ∑ g i X i , g i ≥ 0 , i = 1, m _i ∑ g i = 1. Pentru fmin, calculele de mai înainte se pot folosi până la etapa a doua inclusiv. În S* ultima linie se înmulţeşte cu (-1) şi se trece la etapa a treia, aplicând (AS): 0 - 1 2 0 - 1 0 1 0  0 0 1 2 -1 1 0 -1 S′ =  1 0 0 3 0 0 0 0  0 1 1 2 0 0 0 0

5  2 1 1

Deoarece elementul c'2=1>0, dar coloana respectivă a matricei A' este negativă, rezultă că suntem în cazul 1b) şi fmin=-∞. Dacă nu s-ar fi cerut şi fmax, atunci pentru a calcula fmin am fi schimbat semnul elementelor în ultima linie a matricei simplex iniţiale (S) şi aşa am fi obţinut matricea simplex S'. 5. Să se prezinte schema generală de rezolvare a unei probleme de programare liniară prin duala ei. Soluţie. Problema primală (duală)  A B ≤ S=  C d  fmax

Problema duală (primală)  Aτ Sτ =  τ C

Bτ   d 

gmin

Fiind date două probleme de programare liniară generale, zicem că una este duala celeilalte dacă pentru una se cere fmax (inecuaţiile fiind scrise cu „≤“) iar pentru a doua se cere gmin (inecuaţiile fiind scrise cu „≥“). Nici una nu conţine ecuaţii şi matricele simplex (neechilibrate) asociate sunt una transpusa celeilalte. Rezolvând problema primală, se obţine şi soluţia problemei duale: fmax=gmin, iar necunoscutele apar cu semn opus în ordine în linia funcţiei, în coloanele corespunzătoare necunoscutelor de compensare în matricea simplex redusă (teorema dualităţii). Dacă una din probleme are soluţie infinită, atunci cealaltă este incompatibilă şi invers. 94

Pentru a putea aplica teorema dualităţii şi în cazul când sistemul de restricţii conţine ecuaţii, acestea se înlocuiesc cu câte două inecuaţii conform echivalenţei: a = b ⇔ (a ≤ b) ∧ (a ≥ b) 6. Să se rezolve problema de programare liniară (cu soluţie finită):  - 4 x1 + x 2 ≤ -1   x1 - x 2 + x 3 ≥ 1 5 x + x + x = 10  1 2 3 f = 2 x1 + 3 x 2 + 3 , determinând fmax şi fmin prin intermediul problemei duale. Soluţie: Aflăm fmax scriind problema primală sub forma a două inecuaţii (adecvată aplicării teoremei dualităţii): 5 x1 + x2 + x3 ≤ 10 ,  5 x1 + x2 + x3 ≥ 10 după ce toate inecuaţiile se scriu cu relaţia „≤“. Problema primală: Să se determine acele soluţii xi≥0 , i=1,2,3 ale sistemului de inecuaţii liniare:  − 4 x1 + x 2 −x +x −x  1 2 3   5 x1 + x 2 + x3 − 5 x1 − x 2 − x3

≤ −1 1 ≤ ≤ 10 ≤ − 10

pentru care f=2x1+3x2+3 ia valoarea maximă (fmax). Matricea simplex asociată (în formă neechilibrată) este: 0 −1  ≤ − 4 1 −1 1 −1 −1  ≤   S= 5 1 1 10  ≤    − 5 − 1 − 1 − 10 ≤  2 3 0 − 3  τ

Problema duală: Scriem matricea transpusă S : − 4 − 1 5 − 5 2  ≥ 1 1 1 − 1 3  ≥ τ  S =  0 −1 1 −1 0  ≥    − 1 − 1 10 − 10 − 3 95

În formă detaliată, problema duală se formulează astfel: Să se determine acele soluţii y i ≥ 0 , i = 1,4 ale sistemului de inecuaţii liniare: - 4 y1 - y 2 + 5 y 3 - 5 y 4 ≥ 2   y1 + y 2 + y 3 - y 4 ≥ 3  - y2 + y3 - y4 ≥ 0 ,  pentru care funcţia g=-y1-y2+10y3-10y4+3 ia valoarea minimă. Rezolvarea problemei primale prin duala ei. Trecem la echilibrarea problemei duale în vederea rezolvării ei şi deoarece se cere gmin, înlocuim g cu -g: − 4 y1  y  1    y1

− y2 + y2 − y2 + y2

+ 5 y3 + y3 + y3 − 10 y 3

− 5 y4 − y4 − y4 − 10 y 4

− y5 − y6 − y7 −3

= 2 = 3 = 0 = −g

Rezultă matricea simplex: 0 − 5 −1 0 − 4 − 1 5 1 1 1 −1 0 −1 0 S′ =   0 −1 1 0 −1 −1 0  1 − 10 10 0 0 0 1

2 3  0  3

Se găseşte că: 0    1  * S ′ =  0    0 

0

1 -1

0 0

0

1 0

0

0 0

0

1 12

-

4 12

-

3 12

2 12

-

4 12

-

6 12

-

1 12

-

4 12

-

11 32 12 12

-

9 12 -

33 12

14  12    8 12    14  12    154  12 

Rezultă: f max = g min = 154 , iar necunoscutele x1, x2, x3 iau pe 12 rând, în valoare absolută, numerele marcate cu asterisc în linia funcţiei: x1 =

11 32 33 , x2 = , x3 = 12 12 12 96

Din linia funcţiei se pot citi şi necunoscutele de compensaţie a problemei primale; ele corespund primelor patru coloane: x4=0, x5=0, x6=0, x7=0. Pentru a afla fmin, pornim de la formularea problemei primale în cazul maxim şi înmulţim fiecare restricţie cu -1 pentru a avea toate restricţiile exprimate cu relaţia „≥“. Problema primală. Matricea simplex în formă neechilibrată este: 1 ≥  4 −1 0  1 −1 1 1 ≥   S = − 5 − 1 − 1 − 10 ≥   1 1 10  ≥ 5  2 3 0 − 3  τ Problema duală. Scriem S în formă neechilibrată:

 4 1 −5 5 2 ≤ − 1 − 1 − 1 1 3  ≤ τ  S = 0 1 −1 1 0  ≤   1 − 10 10 − 3 1 Rezolvarea problemei primale prin duala ei. Echilibrarea inecuaţiilor duce la matricea simplex:  4 1 -5 5  -1 -1 -1 1 S′ =   0 1 -1 1   1 1 - 10 10

2  0 1 0 3 , 0 0 1 0  0 0 0 - 3 1 0 0

care în formă redusă, cum se poate verifica prin calcul direct, este următoarea:  1 - 1 0 0 1 0 5  4 4   * = 1 1 9 S ′ 0 - 3 0 0  4 4   1 0 35 0 - 8 0 0  4 4

 1  2  7 2   7 -  2

De aici se citeşte soluţia problemei primale:

97

x1 =

1 35 7 , x 2 = 0 , x3 = şş f min = g max = . Valorile 4 4 2

necunoscutelor

de compensare sunt: x4=0, x5=8, x6=0, x7=0. Rezumat În general problemele economice nu se supun restricţiilor formulate în algoritmul simple (adică doar numere nenegative, doar relaţii de egalitate). Aceste ultime paragrafe ilustrează modalităţile prin care se poate extinde algoritmul simplex pentru soluţionarea şi cazurilor mai complexe. Adesea trebuie introduse condiţii suplimentare (variabilele să ia doar valori întregi), sau poate fi rezolvată mai uşor problema „inversă” (duală). În plus, situaţiile particulare, precum problemele de repartiţie, necesită o abordare specifică. Test de evaluare Să se găsească valoarea minimă şi maximă a funcţiei f= 2x+y-3z a) direct

40 puncte

b) prin metoda duală

50 puncte

variabilele x, y şi trebuind să satisfacă sistemul de restricţii :  x + y + 2z = 2  2 x + 3 y + 4 z ≤ 5 ; x,y,z ≥ 0 3 x + 5 y + 6 z ≥ 8 

98