matematici aplicate

109
UNIVERSITATEA DE ŞTIINŢE AGRICOLE ŞI MEDICINĂ VETERINARĂ „ION IONESCU DE LA BRAD” IAŞI FACULTATEA DE ZOOTEHNIE ÎNVĂŢĂMÂNT LA DISTANŢĂ Prof. dr. ILIE BURDUJAN MATEMATICI APLICATE 2002

Transcript of matematici aplicate

Page 1: matematici aplicate

UNIVERSITATEA DE ŞTIINŢE AGRICOLE ŞI MEDICINĂ VETERINARĂ „ION IONESCU DE LA BRAD” IAŞI

FACULTATEA DE ZOOTEHNIE ÎNVĂŢĂMÂNT LA DISTANŢĂ

Prof. dr. ILIE BURDUJAN

MATEMATICI APLICATE

2002

Page 2: matematici aplicate

Referenţi ştiinţifici: Prof. dr. Alexandru Neagu Univ. Tehnică „Gh. Asachi”- Iaşi Conf. dr. Veronica Teodora Borcea Univ. Tehnică „Gh. Asachi”- Iaşi

Page 3: matematici aplicate

I

CUPRINS

Capitolul I. MULŢIMI. RELAŢII. FUNCŢII §1. Elemente de teoria mulţimilor……………………………………1 §2. Relaţii binare………………………………………………………2 §3. Funcţii………...……………………………………….............................5

1. Moduri de a defini o funcţie…………………………….……5 2. Procedeie de introducere a funcţiilor în cercetarea din Biologie ...6

a) Ajustarea prin funcţii polinomiale…………….…………6 b) Construcţia de polinoame de interpolare………………10

§4. Frecvenţe .………………………………………..………………11 §5. Caracteristici numerice ale mulţimii valorilor unei funcţii

reale………………………………………………..……………..15 a) Caracteristici numerice de poziţie………...……………..15

1°. Media valorilor unei funcţii……..………….……….15 calculul mediei (metoda zeroului fals) ………...…….…16 2°. Mediana…………………...………………………….17 3°. Valoarea modală…………………………….…….…18 4°. Momente ……………………………..……………....18 b) Caracteristici numerice de împrăştiere…………..……..21 1°. Amplitudinea…………..…………………………….21 2°. Dispersia………...……………………………………21 3° Cuartile …………...………………………………….22 c) Alte caracteristici numerice ale unei funcţii…….………24 1°. Coeficientul de variabilitate……..………….………24 2°. Coeficientul de asimetrie……….…………..………..25 3°. Coeficientul de aplatizere (boltire) …………………26 d) Caracteristici numerice pentru familii de funcţii...……26 1°. Covarianţa a două funcţii (caractere)………...……26 2°. Matricea de covarianţă a p funcţii ………...…...….28 4°. Regresia liniară ………………………………..…....29

Capitolul II. ELEMENTE DE ALGEBRĂ ABSTRACTĂ ……………....33

§1. Lege de compoziţie…………………………………….………...33 §2. Structuri algebrice de bază…………….……………………….35 §3. Pătrate latine……………………………….……………………37

Capitolul III. SPAŢII VECTORIALE……………………………………..39

§1. Spaţii vectoriale…………………………………………….……39 1. Definiţii. Exemple………………………………………..39

§2. Subspaţii vectoriale………………………………………….…..45 1.Definiţii. Exemple……………………………………..…...45 2. Rangul unui sistem de vectori………………………..…..45 3. Rangul unei matrice………………………………………46 4. Inversarea matricelor..…………… …………………….47

Page 4: matematici aplicate

II

5. Calculul determinanţilor………….……………….……..49 6. Rezolvarea sistemelor de ecuaţii liniare………...…..…...49

Capitolul IV. ELEMENTE DE PROGRAMARE LINIARĂ.....................53

§1. Metoda simplex de rezolvare a problemelor de programare liniară ……………..…………………………….53

1. Probleme care conduc la programe liniare………...……53 a) Reartiţia optimă a culturilor agricole………...……..53

b) Problema dietei ……………………………………….54 2. Descrierea algoritmului Simplex......................................56

§2. Problema transporturilor……………….………………………63 1. Modelul matematic al problemei transporturilor ….....63 2. Determinarea unei soluţii admisibile de bază

nedegenerate …………………………………………….66 3. Ameliorarea unei soluţii admisibile de bază nedegenerate …………………………………………….68 4. Rezolvarea unor probleme de transport neechilibrate..70

Capitolul V. ELEMENTE DE TEORIA GRAFURILOR……….………..73

§1. Grafuri orientate …………………….………………………….73 1. Definiţii. Exemple……………………………………......73

§2. Grafuri neorientate……………………….……………………..78 §.3 Probleme de optim în grafuri………………………….………..79

1. Problema arborelui parţial minimal/maximal…………79 2. Problema drumului minim/maxim ……………...……..80 3. Problema fluxului maxim şi a secţiunii minime……....86

Capitolul VI. ELEMENTE DE TEORIA PROBABILITĂŢILOR ...........87 §1. Experienţe aleatoare. Evenimente aleatoare...............................87 §2. Câmpuri de evenimente................................................................92 §3. Funcţie de probabilitate ...............................................................93 §4. Probabilităţi condiţionate.............................................................94 §5. Probabilitatea evenimentelor dependente. Inegalitatea lui Boole..........................................................................................98 §6. Formula probabilităţii totale. Formula lui Bayes.......................99 §7. Scheme probabilistice clasice .....................................................101 Schema Poisson......................................................................101 Schema binomială (Bernoulli)..............................................101 Schema multinomială............................................................102 Schema hipergeometrică.......................................................103 §8. Variabile aleatoare......................................................................104

Capitolul VII. Procese stochastice. Lanţuri Markov ................................107 §1. Procese stochastice. Lanţuri şi procese Markov.......................107 §2. Aplicaţii în Genetică..............................................................................109

Page 5: matematici aplicate

Capitolul I

MULŢIMI. RELAŢII. FUNCŢII

Prin mulţime vom înţelege o colecţie de obiecte dintr-un univers U ce este

considerată ca o entitate (un tot). Faptul că un obiect din universul U intră în

componenţa unei mulţimi îi conferă acestuia calitatea de element. De obicei

mulţimile vor notate cu litere mari, iar elementele lor – cu litere mici; vor

exista şi excepţii motivate de specificul domeniului aplicaţiei.

Mulţimile apar implicit sau explicit pretutindeni în universul în care

existăm. Populaţiile biologice (staţionare) sunt exemplele de mulţimi cele mai

obişnuite şi mai uşor de perceput.

§1. ELEMENTE DE TEORIA MULŢIMILOR

Vom presupune cunoscute elementele uzuale de teoria mulţimilor (se

pot consulta eventual manualele de liceu sau §1 din [1]).

Reamintim notaţiile standard:

∈ - apartenenţa (unui element la o mulţime),

∉ - nonapartenenţa (unui element la o mulţime),

= - egalitatea (fie a două elemente, fie a două mulţimi)

≠ - contrara situaţiei precedente

⊂ , ⊃ - incluziunea unei mulţimi în alta

⊄ - nonincluziunea

∅ - mulţime vidă,

Π(M) – mulţimea părţilor unei mulţimi, ∪ - reuniunea a două mulţimi,

UIi∈

- reuniunea unei familii de mulţimi

∩ - intersecţia a două mulţimi,

IIi∈

- intersecţia unei familii de mulţimi

\ - diferenţa a două mulţimi,

Page 6: matematici aplicate

CM(A) – complementara mulţimii A∈Π(M) în M,

∆ - diferenţa simetrică a două mulţimi,

card M sau |M|- cardinalul unei mulţimi finite (adică numărul de

elemente din mulţime)

× - produsul cartezian a două mulţimi.

Partiţia unei mulţimi. Se numeşte partiţie a mulţimii nevide A orice familie

IiiA ∈ (I fiind o familie oarecare de indici) de părţi nevide ale mulţimii A cu

proprietăţile:

a) Ai ∩Aj = ∅ , ji ≠∀ , i,j ∈ I , b) A = . Aii I∈U

Familia de părţi nevide IiiA ∈ care acoperă A (adică satisface b)) este o partiţie

a mulţimii A dacă fiecare element al mulţimii A aparţine cel mult unei părţi din

această familie.

Exemplul 1. 1B. În avifauna ţării noastre, păsările din familiile Ardeidae,

Ciconiidae şi Threskiornitidae dau o partiţie a mulţimii păsărilor ordinului

Ciconiiformes.

2°. Culturile C1, C2,..., Cn realizate de o exploatare agricolă vor conduce la o

partiţie a terenului acestei exploatări.

Exerciţiul 1. Daţi exemple concrete de mulţimi şi partiţii ale unor mulţimi care

apar în activitatea dumneavoastră. Exemplificaţi fiecare dintre noţiunile amintite

mai sus. Răspuns ………………………………………………………………………………………………..................…..

…………………………………………………………………………………

…………………………………………………………………………………

…………………………………………………………………………………

…………………………………………………………………………………

§2. RELAŢII BINARE

Între perechile de elemente ale unei populaţii se stabilesc diverse relaţii.

Modelul matematic general al acestora este noţiunea de relaţie binară. Printre

relaţiile binare pe o mulţime se disting relaţiile de echivalenţă (care apar

implicit în orice activitate de clasificare) şi relaţiile de ordine (care se implică

2

Page 7: matematici aplicate

în orice activitate de ierarhizare). Ambele tipuri de relaţii sunt implicit utilizate

în taxonomia filogenetică.

Definiţia 1. 1º. Se numeşte relaţie binară între mulţimile A şi B orice triplet

(ordonat) R = (A, B, G) unde G ⊂ A × B.

Denumiri. A = domeniul relaţiei R

B = codomeniul relaţiei R

G = graficul relaţiei R,

DR = x A | y ∈ B astfel încât (x, y) ∈ ∃ ∈ G =domeniul strict al relaţiei

binare R,

Im R = y B | x ∈ A astfel încât (x, y) ∈ ∃ ∈ G = imaginea relaţiei binare R.

Notaţii. a) Dacă (x, y) ∈ G scriem : x R y.

b) Dacă A = B scriem R = (A, G) în loc de R = (A, A, G) ; în acest caz spunem

că este dată o relaţie între elementele mulţimii A sau o relaţie binară pe A.

Exerciţiul 2. a) Daţi definiţiile operaţiilor uzuale cu relaţii binare: reuniunea,

intersecţia. b) Definiţi relaţia de incluziune între două relaţii. c) Daţi definiţia

inversei unei relaţii. d) Definiţi operaţia de compunere a două relaţii binare.

Verificaţi-vă pe baza definiţiilor din [1] pag. 20.

Definiţia 2. Relaţia binară R = (A, G) se numeşte:

a) reflexivă dacă (x,x) ∈ G oricare ar fi x ∈ A (adică A∆ R), ⊂

b) simetrică dacă din (x, y) G rezultă (y, x) ∈ ∈ G (adică R = R -1),

c) tranzitivă dacă din (x, y) G şi (y, z) ∈ ∈ G rezultă (x, z) ∈ G(adică RoR

R), ⊂

d) antisimetrică dacă ((x, y) G şi (y, x) ∈ ∈ G) ⇒ (x = y) (adică R ∩ R -1

). ⊂ A∆

Exerciţiul 3. Precizaţi, pentru fiecare dintre relaţiile următoare, care dintre

proprietăţile a), b), c), d) sunt satisfăcute:

1°. R=(A,G) cu A=1, 2, 3, 4, 5, 6, G=(1, 1), (3, 3), (5, 5), (6, 6),

2°. R=(A,G) cu A=1, 2, 3, 4, 5, 6, G=(1, 3), (3, 1), (3, 4), (4, 3), (5, 6), (6, 5),

3°. R=(A,G) cu A=1, 2, 3, 4, 5, 6, G=(1, 2), (1, 3), (1, 5), (1, 6), (2, 3),

(2, 5), (2, 6), (3, 3), (3, 5), (3, 6), (5, 3), (5, 5), (5, 6), (6, 3), (6, 5), (6, 6),

4°. R=(A,G) cu A=1, 2, 3, 4, 5, 6, G=(1, 2), (3, 4), (5, 6).

1°...a).. ..,..b). .. ,..c) ...,.d). ...(marcaţi căsuţele corespunzătoare răspunsurilor)

.. ... .. ...

3

Page 8: matematici aplicate

2°....a)......,..b)......,..c)......,.d).....

3°....a)......,..b)......,..c)......,.d).....

4°....a)......,..b)......,..c)......,.d)......

Definiţia 3. Orice relaţie R = (A, G) care este reflexivă, simetrică şi tranzitivă

se numeşte relaţie de echivalenţă pe A.

Exemplul 2. Pe mulţimea P a tuturor păsărilor dintr-un ecosistem E se pot

defini (verificaţi!) următoarele relaţii de echivalenţă :

1) aR1 b dacă şi numai dacă a şi b au acelaşi sex,

2) aR2 b dacă şi numai dacă a şi b aparţin aceleiaşi specii.

MASC este clasa de echivalenţă a păsărilor de sex masculin şi FEM - clasa de

echivalenţă a păsărilor de sex feminin, deci A/R1=MASC, FEM.

A/R2 este formată din mulţimea speciilor de păsări din ecosistem.

Definiţia 4. O relaţie R = (A, G) care este reflexivă şi tranzitivă se numeşte

relaţie de preordine pe A. Orice relaţie R = (A, G) care este reflexivă,

antisimetrică şi tranzitivă se numeşte relaţie de ordine pe A; orice mulţime

dotată cu o relaţie de ordine se numeşte mulţime ordonată.

Exerciţiul 4. Verificaţi că relaţia binară R = (A, G), unde A=1, 2, 3, 4, 5 şi

G=(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (1, 3) (1, 4), (1, 5), (2, 3), (2, 4),

(2, 5), (3, 2), (4, 5) este o relaţie de preordine pe A. Folosiţi eventual

reprezentarea grafică a relaţiei R. Apoi, verificaţi că relaţia binară R = (A, G),

unde A=1, 2, 3, 4, 5 şi G=(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (1, 3), (1,

4), (1, 5), (2, 3), (2, 4), (2, 5), (4, 5) este o relaţie de ordine pe A.

0

1

2

3

4

5

6

0 1 2 3 4 5 6

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

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

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

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

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

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

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

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

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

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

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

4

Page 9: matematici aplicate

§3. FUNCŢII Definiţia 5. Se numeşte funcţie orice triplet ordonat (A, B, f) format din

mulţimile A, B şi legea de corespondenţă (sau corespondenţa) f care asociază

fiecărui element x ∈A un singur element (şi numai unul) y ∈ B numit imaginea

lui x prin corespondenţa f şi notat cu f(x); A se numeşte domeniul funcţiei, iar

B se numeşte codomeniul funcţiei.

Pentru funcţia din definiţia de mai sus se folosesc de obicei notaţiile

mai comode

BA:f → BA f→

sau - atunci când domeniul şi codomeniul sunt cunoscute - se foloseşte doar

simbolul f.

1. Moduri de a defini o funcţie

Se disting următoarele două moduri de a defini o funcţie :

a) sintetic, b) analitic.

a) Funcţii definite sintetic. Fie f : A B având ca domeniu mulţimea finită A

= a

1, a2,..., an . Spunem că f este definită sintetic dacă se precizează direct

imaginea fiecărui element din domeniu. Acest lucru se realizează de obicei prin

tabele de tipul următor:

x a1 a2 ... an

f(x) b1 b1 ... bn

Astfel de funcţii se evidenţiază în orice experiment în care se determină

valorile numerice ale unei caracteristici cantitative.

b) Funcţii definite analitic. Sunt funcţii f : A →B pentru care legea de

corespondenţă se defineşte cu ajutorul unei proprietăţi (relaţii) care leagă un

element oarecare (generic) din domeniu cu imaginea sa. Concret, aceasta este

echivalent cu a da ecuaţia graficului funcţiei. De exemplu, funcţia f cu domeniul

¡, codomeniul ¡ şi care reflectă directa proporţionalitate dintre element şi

imaginea sa de coeficient (rată) de proporţionalitate ½, este de fapt funcţia :

:f ¡→ ¡, ∈∀= x,x2)x(f ¡.

Exerciţiul 5. Definiţi câteva funcţii elementare. Controlaţi-vă pe baza manua-

lelor de liceu!

5

Page 10: matematici aplicate

Exerciţiul 6. Daţi definiţiile pentru: funcţia identitate, funcţia constantă şi funcţia

caracteristică a unei mulţimi. Pentru control consultaţi [1] pag. 31.

Pentru funcţia (X, Y, f) şi părţile nevide A X şi B Y se definesc

mulţimile

⊂ ⊂

Bf(x)|Xx=(B)f Ax|f(x)=f(A) 1 ∈∈∈∀ − ;

f(A) se numeşte imaginea mulţimii A prin f, iar f -1(B) se numeşte contraima-

ginea prin f a mulţimii B. Mulţimea Im f = f(X) se numeşte imaginea funcţiei f.

Dacă B = b atunci notăm f -1(b) cu f -1(b) ; deci f -1(b) = x ∈ A | f(x) =

b, adică f -1(b) este mulţimea tuturor soluţiilor ecuaţiei f(x) = b.

Exemplul 3. Se consideră o populaţie dialelică P cu familia de alele a, A; fie G

= aa, aA, AA mulţimea genotipurilor acestei populaţii. Fiecare individ din P

are un anumit genotip. Definim funcţia (P, G, f) prin care se asociază fiecărui

individ din P genotipul propriu. Dacă PH ⊂ P este submulţimea homozigoţilor,

atunci f(PH) = aa, AA. În plus, f-1(aA) este submulţimea heterozigoţilor din P.

Precizaţi submulţimile f-1(aa ), f-1(AA), f-1(aa, AA).

Exerciţiul 7. Definiţi noţiunile: funcţie injectivă, surjectivă, bijectivă ([1] pag.

32). Daţi exemple de fiecare fel. Folosiţi pentru exemplificare şi funcţiile din

Exemplele 3 şi 4.

2. Procedee de introducere a funcţiilor în cercetarea

din Biologie Dintre procedeele de introducere a funcţiilor în Biologie prezentăm:

a) ajustarea prin funcţii polinomiale,

b) construcţia de polinoame de interpolare.

a) Ajustarea prin funcţii polinomiale.

Fie Pi(ti, ni), i = 1, 2, ..., m punctele corespunzătoare la m determinări

dintr-o experienţă. Ne propunem să determinăm o funcţie dintr-o clasă aleasă,

având ecuaţia graficului y = f(x) şi cu proprietatea că suma pătratelor abaterilor

dintre ordonatele ni ale punctelor Pi(ti, ni) şi ordonatele f(ti) ale punctelor

curbei să fie minimă. Procedeul de determinare a unei astfel de funcţii, având

la bază condiţia de minimizare a sumei pătratelor abaterilor, este cunoscut sub

numele de metoda celor mai mici pătrate (şi este datorată lui K. F. Gauss). 6

Page 11: matematici aplicate

Ne propunem să determinăm funcţia (polinomială) liniară f ¡ ¡, f(t) = at + b (adică să determinăm numerele reale a şi b) astfel încât

: →

)b-ta-n(=b)h(a, 2ii

m

1=i∑ să fie minimă.

Se demonstrează că dacă utilizăm notaţiile:

∑=

=m

1iit

m1)t(M , ∑

=

=m

1iin

m1)n(M , ∑

=

=m

1i

2i

2 tm1)t(M ,

222 )]t(M[)t(M)t(D −= , ∑=

=⋅m

1iiint

m

1ntM )( , S(t, n)=M(t·n)-M(t)M(n)

funcţia căutată corespunde valorilor

(1) )(),(

tD

ntSa

20= , b0 = M(n) – a0 M(t).

Pentru aplicaţiile concrete este utilă remarca

D2(t-a)=D2(t), S(t-a, n-b)= S(t, n), ∀a, b ∈¡.

În particular, dacă a=M(t) atunci M(t-a)=0, S(t, n)= S(t-a, n)=M((t-a)·n)) iar

coeficienţii de ajustare devin

)(

),(

atD

natSa

20 −

−= , bo = M(n).

Deci funcţia liniară ¡→¡, f(t) = a:f ot + bo este funcţia căutată. Această func-

ţie se numeşte funcţie liniară de ajustare a datelor sau ajustare liniară a date-

lor.

Exemplul 4. În 1923, E.Dudich a măsurat lungimea totală y şi lungimea x a

mandibulei pentru coleopterul Cyclommatus tarandus şi a obţinut datele urmă-

toare :

lungimea totală y 20,4 33,1 38,4 47,3 54,2 66,1 74,0

lungimea mandibulei x 3,9 10,7 14,1 19,9 24,0 30,7 34,5

Pe baza acestor date vom obţine funcţia de ajustare liniară f(x)=a0x +b0.

Construim tabelul următor:

xi yi xiyi xi2

3,9 20,4 79,56 15,21

10,7 33,1 354,17 114,49

14,1 38,4 541,44 198,81

19,9 47,3 941,27 396,01

24,0 54,2 1300,8 576,00

7

Page 12: matematici aplicate

30,7 66,1 2029,27 942,49

34,5 74,0 2553,00 1190,25

Σxi=137,8 Σyi=333,5 Σxiyi=7799,51 3433,26

M(x)=19,68571 M(y)=47,64286 M(xy)=1114,216 M(x2)=490,4657

Folosind formulele (1) rezultă

f(x)=1,712987x+13,92149.

După rotunjiri la două zecimale obţinem

f(x)=1,71x+13,92.

Pentru a stabili cât de bună este această ajustare considerăm tabelul

yi iy =1,71xi+13,92 ii yy − ( ii yy − )2

20,4 20,589 -0,189 0,035721

33,1 32,217 0,883 0,779689

38,4 38,031 0,369 0,136161

47,3 47,949 -0,649 0,421201

54,2 54,96 -0,760 0,577600

66,1 66,417 -0,317 0,100489

74,0 72,915 1,085 1,177225

h(a0,b0)= 3,228086

Deci min h(a, b) = h(a0, b0) ≅ 3,228086.

În locul funcţiilor de ajustare liniară se pot folosi funcţii de ajustare

polinomiale de grad ≥2; astfel de ajustări se numesc generic ajustări parabo-

lice. În particular, ajustarea parabolică de gradul doi se face printr-o funcţie de

forma ¡ ¡, f(t) = a:f → 2t2 + a1t + ao pentru care coeficienţii formează soluţia

unică a sistemului:

=++

=++

=++

∑∑∑∑

∑∑∑∑

∑∑∑

====

====

===

m

1ii

2i

m

1i

4i2

m

1i

3i1

m

1i

2i0

m

1iii

m

1i

3i2

m

1i

2i1

m

1ii0

m

1ii

m

1i

2i2

m

1ii10

nttatata

nttatata

ntatama

.

Aceste formule sunt consecinţa cerinţei ca 8

Page 13: matematici aplicate

=−∑ )ata-ta-n(=)aah(a 2iii

m

=1i0

2210 12

,, minimă

Exemplul 5. Vom ajusta parabolic datele din Exemplul 4. Se obţine tabelul xi yi xiyi xi

2 xi3 xi

4 xi2yi

3,9 20,4 79,56 15,21 59,319 231,3441 310,284

10,7 33,1 354,17 114,49 1225,043 13107,96 3789,619

14,1 38,4 541,44 198,81 2803,221 39525,42 7634,304

19,9 47,3 941,27 396,01 7880,599 156823,9 18731,27

24,0 54,2 1300,8 576,00 13824,00 331776,0 31219,2

30,7 66,1 2029,27 942,49 28,934,44 888287,4 62298,59

34,5 74,0 2553,00 1190,25 41063,63 1416695,0 88078,5

Σxi=

=137,8

Σyi=

=333,5

Σxiyi=

=7799,51

3433,26 Σxi3=

=95790,25

Σxi4=

=2846447

Σxi2yi=

=212061,8

M(x)=

19,68571

M(y)=

47,64286

M(xy)=

1114,216

M(x2)=

=490,4657

M(x3)=

=13684,3214

M(x4)=

=406635,2857

M(x2y)=

=30294,5428

Coeficienţii căutaţi sunt componentele soluţiei sistemului:

=++=++

=++

769212061a1032846447a2595790a263433

517799a2595790a263433a8137

5333a263433a8137a7

210

210

210

,,,,,,,,

,,, .

Se obţine funcţia de ajustare f(x) = 0,0304x2 + 1,5939x +14,7733. Valorile

ajustate iy = 0,0304ti2 + 1,5939ti +14,7733 şi abaterile de la valorile măsurate

sunt prezentate în tabelul de mai jos:

yi iy ii yy − ( ii yy − )2

20,4 21,0359 -0,6359 0,4044

33,1 32,1767 0,9233 0,8525

38,4 37,8525 0,5475 0,2998

47,3 47,6971 -0,3971 0,1577

54,2 54,7797 -0,5797 0,3361

66,1 66,5738 -0,4738 0,2245

74,0 73,3843 0,6157 0,3791

2,6540

Valoarea minimă a funcţiei h(a0, a1, a2) este ≈h(14,7733; 1,5939;

0,00304)≈2,6540 şi este mai mică decât valoarea minimă 3,2281 corespunzătoare

ajustării liniare. Prin urmare este firesc să utilizăm ajustarea parabolică.

9 b) Construcţia de polinoame de interpolare.

Page 14: matematici aplicate

Problemă: să se determine un polinom cu proprietatea că graficul său

trece prin m+1 puncte Pi(ti, xi), i = 0, 1, 2,..., m.

Se demonstrează că există un singur polinom de gradul m cu această proprietate. Polinomul

x)t-t)...(t-t)(t-t)...(t-t)(t-t()t-)...(tt-)(tt-)...(tt-)(tt-(t=t);t,...,t,tL( imi1+ii-1ii1ioi

m1+i-1i1om

o=im1o ⋅∑ .

este soluţie a acestei probleme; el este cunoscut sub numele de polinomul de interpolare Lagrange .

Exemplul 6 . Să determinăm polinomul de grad minim al cărui grafic trece

prin punctele Po(0,1), P1(1,1), P2(2,-1), P3(4,1) precum şi valoarea lui în t = 3.

Polinomul Lagrange corespunzător este

.))((

))(())(())()(())()(())()((

)())()(())()((

))()(())()((

))(())()(();,,,(

1t2t2

5t

2

12t1tt

24

1

4t1tt4

14t2tt

3

14t2t1t

8

11

241404

2t1t0t

1421202

4t1t0t1

412101

4t2t0t1

421

4t2t1tt4210L

23 ++−=−−+

+−−+−−⋅+−−−⋅−=⋅−−−−−−

+

+−⋅−−−−−−

+⋅−−−−−−

+⋅−−−

−−−=

Evident, putem acum calcula L(0, 1, 2, 4; 3)= -2. Se putea calcula valoarea în

t=3 şi direct (adică fără să determinăm polinomul de interpolare) şi anume:

21241404

231303

1421202

4313031

412101

4323031

421

43231334210L

−=⋅−−−−−−

+

+−⋅−−−−−−

+⋅−−−−−−

+⋅−−−

−−−=

))()(())()((

)())()(())()((

))()(())()((

))(())()(();,,,(

Exerciţiul 8. Datele din Exemplul 3 conduc la considerarea punctelor P0(3,9;

20,4), P1(10,7; 33,1), P2(14,1; 38,4), P3(19,9; 47,3), P4(24, 54,2), P5(30,7; 66,1),

P6(34,5; 74). Determinaţi polinomul de interpolare Lagrange corespunzător

acestor date şi apoi calculaţi valoarea acestuia în x=15,3 şi în x=29,9. Calculaţi

apoi aceleaşi valori direct.

În cazul în care momentele to, t1,...,tm sunt echidistante polinomul de

interpolare capătă forma mai simplă de mai jos, cunoscută şi sub numele de

polinomul de interpolare al lui Newton :

)1m)...(1(!mx

)...1k)...(1(!kx

...!1

xx)ht(P 0

m0

k0

00m +−θ−θθ∆

++−θ−θθ∆

++θ∆

+=θ+

unde: h = ti - ti-1, ht-t o=θ şi . i

k1i

ki

1ki1ii xxx,xxx ∆−∆=∆−=∆ +

++

10

Page 15: matematici aplicate

Cantităţile se numesc diferenţe finite progresive; se pot defini

şi diferenţe finite regresive şi diferenţe centrale şi câte un polinom de

interpolare Newton corespunzător.

,...2,1k,xik =∆

Exemplul 7. Să determinăm polinomul de grad minim al cărui grafic

trece prin punctele punctele Po(0,1), P1(1,1), P2(2,-1), P3(3,1), după care vom

determina valoarea lui în t = 1,3. Vom determina mai întâi diferenţele finite

progresive care apar. Calculul lor se organizează sub forma tabelului următor:

xi ∆ xi ∆2 xi ∆3 xi

1

1

-1

1

0

-2

2

-2

4

6

Ţinând cont că h = 1, to = 0, θ = t, polinomul de interpolare Newton este

)2t)(1t(t)1t(t1)t(P −−+−−= sau . 1t3t4t)t(P 23 ++−=

Prin înlocuire în polinom obţinem: P(1,3) = 0,337.

Se putea calcula direct această valoare punând θ=1,3 în formula lui Newton; se

obţine P(1,3) =1- 1,3.0,3- 1,3.0,3.0,7 =1 – 0,39 – 0,273 = 0,337.

Rezolvaţi această problemă şi folosind formula lui Lagrange!

Exerciţiul 9. Să se determine polinomul de grad minim al cărui grafic trece

prin punctele P0(-2, 3), P1(-1, 5), P2(0, -1), P3(1, 2), P4(2, -1). Folosiţi ambele

formule de interpolare. Comparaţi volumele de muncă necesare. Calculaţi apoi

valorile polinomului în t =1,27 cu două şi cu patru zecimale. Comentaţi

rezultatele!

§4. Frecvenţe Fie :f →Ω o funcţie surjectivă pentru care 'Ω Ω = ,...,, n21 ωωω şi

Ω’=x1, x2,…, xm (cu m ). n≤

Frecvenţa absolută a valorii x∈Ω’=Im f este numărul fa(x) de elemente

din Ω în care funcţia ia valoarea x, iar frecvenţa relativă fr(x) a valorii x este

raportul dintre frecvenţa sa absolută şi numărul de elemente din domeniul

funcţiei. Numărul 100.fr(x) este procentul de elemente din domeniu în care

funcţia ia valoarea x. 11

Page 16: matematici aplicate

De exemplu, pentru funcţia din Exemplul 3, frecvenţa absolută a valorii AA este

numărul de indivizi din populaţie care sunt homozigoţi dominanţi; frecvenţa

relativă a valorii AA este proporţia de indivizi homozigoţi dominanţi din

populaţie.

Vom nota cu ni frecvenţa absolută a valorii xi (i=1, 2, ..., m) şi cu fi

frecvenţa relativă a valorii xi (i=1, 2, ..., m). Evident, suma tuturor frecvenţelor

absolute ale valorilor funcţiei f este n, iar suma tuturor frecvenţelor relative ale

valorilor funcţiei f este 1, adică

1f...ff,nn...nn m21m21 =+++=+++ .

Se asociază funcţiei f tabelul

x1 x2 . . . xm

n1 n2 . . . ........ nm

care defineşte (sintetic) o nouă funcţie :~f Ω’→ ¡. Funcţia f~ se va numi şi

repartiţia frecvenţelor absolute ale valorilor funcţiei f. De asemenea îi putem

asocia funcţia f : ' ¡ care asociază fiecărei valori xΩ → i∈ Ω ' numărul fi

(adică frecvenţa relativă a valorii xi). Funcţia f se va numi şi repartiţia

frecvenţelor relative ale valorilor funcţiei f.

Exerciţiul 10. Definiţi histograma în batoane. Controlaţi-vă pe baza manua-lului [1] pag.46. .............................................................................................................................................................................................................................................................. Putem asocia funcţiei f cu domeniul de definiţie finit funcţiile gs, gd,

:g,g ds ¡ ¡ definite prin: →• gs(x) este suma tuturor frecvenţelor absolute corespunzătoare valorilor ≤x şi

se numeşte frecvenţa absolută cumulată crescătoare a valorii x

• )x(gs este suma tuturor frecvenţelor relative corespunzătoare valorilor ≤x

şi se numeşte frecvenţa relativă cumulată crescătoare a valorii x

• gd(x) este suma tuturor frecvenţelor absolute corespunzătoare valorilor ≥x

şi se numeşte frecvenţa absolută cumulată descrescătoare a valorii x

• )x(gd este suma tuturor frecvenţelor relative corespunzătoare valorilor ≥x

şi se numeşte frecvenţa relativă cumulată descrescătoare a valorii x.

Funcţia sg se numeşte funcţia de repartiţie a funcţiei f şi se notează în

mod obişnuit cu F. 12

Page 17: matematici aplicate

Exemplul 7. Pentru a aprecia starea generală a animalelor pe care le are

un mic fermier a cântărit fiecare din cele 40 oi pe care le are şi a obţinut datele din

Tabelul 1. Acest tabel se poate interpreta ca fiind o funcţie f definită sintetic cu

domeniul de definiţie mulţimea celor 40 de oi (identificată pentru comoditatea

prezentării cu mulţimea 1, 2, ... ,40 ), codomeniul mulţimea numerelor reale

şi legea de corespondenţă cea care asociază fiecărei oi masa sa.

Tabelul 1

Nr. crt. Masă Nr.crt. Masă Nr. crt. Masă Nr. crt. Masă

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

37

36

37

31

35

33

32

34

33

40

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

39

41

41

39

35

37

32

34

36

38

21.

22.

23.

24.

25.

26.

27.

28.

29.

30.

40

39

38

37

35

33

31

36

40

39

31.

32.

33.

34.

35.

36.

37.

38.

39.

40.

36

38

38

32

37

35

34

33

35

39

Frecvenţele absolute şi cele relative ale valorilor acestei funcţii sunt date

în Tabelul 2.

Tabelul 2

Masă

xi

Frecvenţa absolută

ni

Frecvenţe relative

fi

31 2 0,050

32 3 0,075

33 4 0,100

34 3 0,075

35 5 0,125

36 4 0,100

37 5 0,125

38 4 0,100

39 5 0,125

40 3 0,075

41 2 0,050

Total 40 1,00

În construcţia Tabelului 2 s-a ţinut cont că fmin = 31 şi fmax = 41 .Din Tabelul 2

se constată că 5 oi au greutatea 37 Kg., adică frecvenţa absolută a valorii 37

este 5; frecvenţa relativă a valorii 37 este 5/40=0,125. Determinarea funcţiilor 13

Page 18: matematici aplicate

asociate gs, gd, g, g ds (şi, în particular, a funcţiei de repartiţie F) funcţiei f este

realizată în Tabelul 3 .

Tabelul 3

Masă

xi

Frecvenţa

absolută

ni

Frecvenţa

relativă

fi

)x(g is

)x(g~=)xF( isi )x(g id

)x(g~ id

31 2 0,050 2 0,050 40 1,000

32 3 0,075 5 0,125 38 0,950

33 4 0,100 9 0,225 35 0,875

34 3 0,075 12 0,300 31 0,775

35 5 0,125 17 0,425 28 0,700

36 4 0,100 21 0,525 23 0,575

37 5 0,125 26 0,650 19 0,475

38 4 0,100 30 0,750 14 0,350

39 5 0,125 35 0,875 10 0,250

40 3 0,075 38 0,950 5 0,125

41 2 0,050 40 1,000 2 0,050

Din Tabelul 3 se vede, de exemplu, că

- există 21 oi cu greutatea de cel mult 36 kg,

- există 23 oi cu greutatea de cel puţin 36 kg.

Pe baza legăturii dintre frecvenţele relative şi procente se vede că 12,5% dintre

oi au cel mult 37 kg şi că 70% oi au cel puţin 35 kg.

Exerciţiul 11. Dintr-o plantaţie de flori de mac s-au ales 40 de flori la care s-a

determinat numărul stigmatelor. Datele obţinute sunt înregistrate în tabelul

următor:

Numărul stigmatelor xi 7 8 9 10 11

Frecvenţele absolute ni 6 18 8 6 2

Identificaţi funcţiile f, ddss ggggff ,,,,,~ şi determinaţi frecvenţele absolute şi

relative simple şi cumulate. Completaţi tabelul următor. Desenaţi apoi histogra-

mele corespunzătoare şi uniţi extremităţile batoanelor prin segmente de dreaptă.

Citiţi apoi câte un rezultat din fiecare coloană şi precizaţi ce reprezintă.

xi ni fi gs

sg gd dg

7 6 8 18 9 8

14

Page 19: matematici aplicate

10 6 11 2

§5. Caracteristici numerice ale mulţimii valorilor

unei funcţii reale

Pentru orice funcţie reală cu domeniul finit se pun următoarele probleme:

a) există sau nu un număr real în jurul căruia să se grupeze majoritatea valorilor

funcţiei,

b) cât de împrăştiate sunt valorile funcţiei pe axa reală.

Corespunzător acestor probleme distingem două tipuri de caracteristici :

a) caracteristici numerice de poziţie

b) caracteristici numerice de împrăştiere.

a) Caracteristici numerice de poziţie Printre caracteristicile numerice de poziţie distingem: media, mediana,

valoarea modală, momentele simple şi centrate.

1°. Media valorilor unei funcţii

Media M(f) a valorilor unei funcţii reale f, cu domeniul finit, este media arit-

metică a tuturor valorilor ei, adică

(1) [ ])(...)()()( n21n1 ffffM ω++ω+ω= .

Dacă f: Ω ¡ cu |Ω| = n are m<n valori distincte x→ 1, x2, ..., xm cu frecvenţele

relative f1, f2,...,fm media sa, notată cu M(f), se calculează cu ajutorul formulei

(2) . ∑=

=m

1iiifxfM )(

Exemplul 9. Pe baza datelor din Exemplul 8 media M(f) este egală, conform formulei (2) şi utilizând datele din Tabelul 1, cu:

12536050041075040125039100038125037

100036125035075034100033075032050031fM

,,.,,,,,,,,,)(

=⋅+⋅+⋅+⋅+⋅++⋅++⋅+⋅+⋅+⋅+⋅=

Exerciţiul 12. Calculaţi media funcţiei din Exerciţiul 11.

M(f)= ....................................................................................................................

În cazul în care majoritatea frecvenţelor absolute sunt egale cu 1 calculul mediei

se face direct pe baza definiţiei; în acest caz frecvenţele relative îşi pierd din

importanţă.

15

Page 20: matematici aplicate

Calculul mediei În multe situaţii calculul mediei şi mai ales al momentelor de ordin

superior implică utilizarea unor numere mari, fapt care îngreunează calculele.

O soluţie importantă pentru evitarea acestei situaţii este metoda „zeroului fals”

pe care o prezentăm în cele ce urmează.

Metoda zeroului fals

- se alege o valoare xo ∈ ¡ cât mai aproape de valoarea medie (în cazu-

rile concrete, se cunoaşte de obicei o zonă în care se află valoarea medie reală)

- se construieşte funcţia x-f(f) oxo=θ (care ia valori grupate în jurul lui 0)

- se ţine cont de egalitatea evidentă ox x-M(f)(f))M(o

=θ .

Exemplul 10. Vom determina folosind metoda zeroului fals media funcţiei din

Exemplul 8. Deşi numerele care se folosesc nu sunt atât de mari încât să

justifice utilizarea metodei zeroului fals vom calcula media şi folosind abaterile

funcţiei f de la valoarea xo = 35, adică folosind funcţia θ 35(f) = f – 35.

Calculele se prezintă în Tabelul 4.

Tabelul 4

Masă

xi

Abateri

xi - 35

Frecvenţe relative

fi

(xi - xo)·fi

31 -4 0,050 -0,200

32 -3 0,075 -0,225

33 -2 0,100 -0,200

34 -1 0,075 -0,075

Proprietăţile mediei

.1. M(a)=a, pentru orice funcţie constantă a 2. )(max)()(min ω≤≤ω

Ω∈ωΩ∈ωffMf

3. M(af)=aM(f), ∀a∈¡, ∀f: Ω ¡ →4. M(f+g)=M(f)+M)g), ∀f, g: Ω ¡ →

5. )()(|)(| 22 gMfMgfM ⋅≤⋅ , ∀f, g: Ω ¡. →

6. )f(Ma...)f(Ma)f(Ma)fa...fafa(M kk2211kk2211 +++=+++

∀a1, a2, ... , ak ∈ú şi ∀ f1, f2,..., fk : →Ω ú.

16

Page 21: matematici aplicate

35 0 0,125 0,000

36 1 0,100 0,100

37 2 0,125 0,250

38 3 0,100 0,300

39 4 0,125 0,500

40 5 0,075 0,375

41 6 0,050 0,300

M(θ 35) = 1,125

Din egalitatea M(θ 35(f)) = M(f) - 35 rezultă M(f) = 35 + 1,125 = 36,125,

adică se regăseşte valoarea calculată direct mai sus. Este de remarcat faptul că şi în

acest caz, simplu de tratat direct, se obţine mult mai uşor valoarea mediei prin

utilizarea abaterilor de la o valoare deoarece, în afara faptului că se lucrează cu

numere mult mai mici, apare şi avantajul compensării unor valori negative cu

unele pozitive.

Pentru funcţia din Exemplul 11 se calculează M(θ7(f))=1,05, deci M(f)

= 7+1,05 = 8,05; se regăseşte rezultatul obţinut utilizând fie definiţia fie formula

de calcul.

Funcţia θ se numeşte abaterea funcţiei f de la valoarea x)(fxo

)f(

o. Dacă xo

= M(f) notăm în loc de şi o numim abaterea de la medie a funcţiei f. θ )f(xoθ

Exerciţiul 12. Verificaţi că M(θ(f)) = 0 pentru orice funcţie f.

2°. Mediana

Se numeşte mediana funcţiei f : Ω ¡ numărul real µ = m → f care satisface simultan proprietăţile

21)f(|

n1

≥µ≤ωΩ∈ω⋅ şi 21)f(|

n1

≥µ≥ωΩ∈ω⋅ .

Deci mediana µ are proprietatea că valorile funcţiei ≤ µ sunt „aproape” la fel de frecvente ca valorile funcţiei . ≥ µ

Exemplul 11. Dacă Ω = 7 şi f are valorile 1, 2, 2, 4, 4, 5, 6 atunci fµ = 4; într-

adevăr, există 5 numere ≤4 (adică primul raport este 21

75 ≥ ) şi 4 numere ≥4

(adică al doilea raport este 21

74 ≥ ). Se verifică uşor că alte valori numerice nu

satisfac condiţiile din definiţia medianei. În cazul Ω = 8 şi f are valorile 1, 2,

17

Page 22: matematici aplicate

2, 3, 3, 4, 5, 5 atunci fµ = 3 iar dacă Ω = 8 şi f are valorile 1, 2, 2, 3, 4, 4, 4, 6

atunci fµ este orice număr cuprins între 3 şi 4.

µ

Ω

Ca mediană f pentru funcţia din Exemplul 8 se poate lua orice număr

cuprins între 35 şi 36.

Într-adevăr, pe baza Tabelului 3, rezultă că mediana funcţiei este între 35 şi 36

deoarece în coloana gs a lui citim gs(35)=0,425 < 0,500 < 0,525 = gs(36). Se va

prefera valoarea µ f = 35,750 obţinută folosind o interpolare liniară şi anume

753542505250

4250500035 ,

,,,,

=−−

+=µ .

Mediana este un estimator robust al valorii centrale pentru că, spre deosebire

de medie, este puţin sensibil la valorile extreme mari.

3°. Valoarea modală Valoarea modală (sau, pe scurt, modulul sau moda) a funcţiei f: ¡ este acea

valoare care are frecvenţa maximă. De exemplu, pentru funcţiile din Exemplul

11, valorile modale sunt 2 şi 4 pentru prima funcţie, 2, 3 şi 5 pentru a doua funcţie

şi respectiv 4 pentru a treia funcţie. Deci primele funcţii sunt plurimodale, iar

ultima este unimodală. Pentru funcţia f din Exemplul 8 valorile 35, 37 şi 39 sunt

modale pentru că apar cu frecvenţa maximă 5; deci funcţia este plurimodală.

→Ω

4°. Momente

Fie funcţia f: → ¡ unde ,...,, n21 ωωω=Ω şi k este un număr natural

(nenul) fixat. Se numeşte moment de ordinul k al funcţiei f numărul notat cu

Mk(f) definit prin:

Mk(f) = M(f k).

În particular M0(f)=1, şi M1(f) = M(f). Calculul momentelor de ordinul k se face utilizând abaterile valorilor funcţiei faţă de valoarea xo folosită şi în calculul valorii medii şi utilizând formula:

x(f))(MC(f)M ioxi-k

ik

k

o=ik oθ= ∑ .

În cazul în care xo = M(f), notăm mk = Mk(θ(f)) şi îl numim momentul

centrat de ordinul k. Din formula precedentă rezultă

18

Page 23: matematici aplicate

[ ii-k

ik

k

o=ik fMmC(f)M )(∑= ] şi m . M(f)(f)MC)(-1 i

i-kik

kk

o=ik ∑=

Exerciţiul 13. Pe baza formulelor precedente stabiliţi formulele

[ ] [ ]2222

22 fMfMmfMmfM )()(,)()( −=+= .

În acelaşi fel deduceţi că formulele de calcul pentru M3(f), M4(f), m3 şi m4 sunt

următoarele:

[ ][ ] [ ]42

2344

3233

40

30x

20x20x3x44

30

20x0x2x33

fM3fMfM6fMfM4fMm

fM2fMfM3fMm

xxfM4xfM6xfM4fMfM

xxfM3xfM3fMfM

0000

000

)()()()()()(

)()()()(

))(())(())(())(()(

))(())(())(()(

−+⋅−=

+⋅−=

+⋅θ+⋅θ+⋅θ+θ=

+⋅θ+⋅θ+θ=

Exemplul 12. Să determinăm acum momentele de ordinul 2, 3 şi 4 ale funcţiei

f din Exemplul 8. Se construieşte tabelul următor în care se foloseşte notaţia yi

= xi - xo .

Tabelul 5

xi yi yi2 yi

3 yi4 fi yi · fi yi

2 · fi yi3 · fi yi

4 · fi

31 -4 16 -64 256 0,050 -0,200 0,800 -3,200 12,800

32 -3 9 -27 81 0,075 -0,225 0,675 -2,025 6,075

33 -2 4 -8 16 0,100 -0,200 0,400 -0,800 1,600

34 -1 1 -1 1 0,075 -0,075 0,075 -0,075 0,075

35 0 0 0 0 0,125 0,000 0,000 0,000 0,000

36 1 1 1 1 0,100 0,100 0,100 0,100 0,100

37 2 4 8 16 0,125 0,250 0,500 1,000 2,000

38 3 9 27 81 0,100 0,300 0,900 2,700 8,100

39 4 16 64 256 0,125 0,500 2,000 8,000 32,000

40 5 25 125 625 0,075 0,375 1,875 9,375 46,875

41 6 36 216 1296 0,050 0,300 1,800 10,800 64,800

M(θ 35(f))=

=1,125

M2(θ 35(f))=

=9,125

M3(θ 35(f))=

=25,875

M4(θ 35(f))=

= 174,425

Se vor folosi formulele din Exerciţiul 13 şi rezultatele din Tabelul 5.

Rezultă că pentru funcţia cu care lucrăm momentele de ordinele 2, 3 şi 4 sunt

respectiv :

M2(f) = 9,125 + 2 × 1,125 × 35 + 352 = 1312,875,

M3(f) = 25,875 + 3 × 9,125 × 35 + 3 × 1,125 × 352 + 353 = 47993,375,

19

Page 24: matematici aplicate

M4(f) = 174,425 + 4 × 25,875 × 35 + 6 × 9,125 × 352 + 4 × 1,125 × 353 + 354 = 1764428,175 .

Aplicaţie

Nu este totdeauna important să utilizăm valorile exacte ale unor măsurători.

Prelucrarea datelor trebuie făcută şi în acest caz. Vom ilustra modul de lucru pe

următorul exemplu.

Cei 2000 pui ai unui fermier au greutăţile din următorul tabel

Clase de greutăţi îm grame Număr pui

1800-2000 128

2000-2200 170

2200-2400 280

2400-2600 800

2600-2800 320

2800-3000 180

3000-3200 120

Pentru a asocia caracteristici numerice unui astfel de tabel, îi asociem funcţia care ia ca valori valoarea medie a fiecărei clase, adică

Centrul clasei Număr pui

1900 128

2100 170

2300 280

2500 800

2700 320

2900 180

3100 120

S-a obţinut o funcţie pentru care se pot determina în mod obişnuit toate

caracteristicile numerice. Evident aceste valori sunt diferite de cele ale funcţiei

care ar asocia fiecărui pui greutatea sa în grame. Pentru a obţine valori mai

20

Page 25: matematici aplicate

apropiate de valorile reale se folosesc corecţiile lui Sheepard. Corecţiile pentru

primele patru momente sunt

240d7

22d

4480d

22d

44

334d

33

12d

2212d

22

4242

2

22

fmfmfmfMfMfM

fmfmfMfMfM

fmfmfMfM

0fmfmfMfM

+−=++=

=+=

−=+=

===

)()()()()()(

)()()()()(

)()()()(

)()(')()('

''

''

''

unde d este amplitudinea clasei (d=200 în exemplul de mai sus).

Propunem ca exerciţiu determinarea momentelor simple şi centrate de ordin ≤

4 pentru seria de determinări cu clase de valori de mai sus.

b) Caracteristici numerice de împrăştiere

Dintre caracteristicile numerice de împrăştiere distingem: amplitudinea, disper-

sia sau varianţa, cuartilele şi intervalul intercuartilic.

1°. Amplitudinea Amplitudinea Af a funcţiei f este diferenţa dintre valoarea maximă şi cea

minimă ale funcţiei. Pentru funcţia din Exemplul 8 amplitudinea este

Af=41-31=10.

2°. Dispersia (varianţa)

Considerăm funcţia (caracterul) f : →Ω ¡ unde ,...,, n21 ωωω=Ω .

Valorile ei pot fi mai mult sau mai puţin dispersate (depărtate unele de altele).

Împrăştierea valorilor funcţiei f se măsoară cu ajutorul unui parametru numit

dispersie sau varianţă.

Definiţia 6. Dispersia sau varianţa funcţiei f este numărul notat D2(f)

sau cu σ sau cu V(f) definit prin: 2f

V(f) = ])2M(f)-M[(f def

2f = (f)D2 =σ adică: ]M(f)-)[f(

n1(f)D 22 ω= ∑

Ω∈ω

.

Oricare ar fi funcţiile f, g : Ω ¡ unde → ,...,, n21 ωωω=Ω au loc afirmaţiile

:

21

Page 26: matematici aplicate

C

m

E

a

A

P

i

m

p

E

µ

µ

µ

µ

i

Proprietăţile dispersiei

1°. D2(f) 0, f ; D≥ ∀ 2(f) = 0 dacă şi numai dacă f este funcţie constantă

2°. D2(f) = M(f 2) - [ M(f) ] 2,

3°. D2(af) = a2D2(f), ∀ a ∈¡, ∀ f,

4°. D2(a + f) = D2(f), ∀ f şi oricare ar fi funcţia constantă a,

5°. D2(f + g) = D2(f) + D2(f), dacă şi numai dacă M(fg) = M(f) M(g) .

antitatea )f(D2f =σ=σ , se numeşte abaterea pătratică (de la) medie şi se

ăsoară cu aceeaşi unitate de măsură ca valorile funcţiei.

xemplul 13. Pentru funcţia f din Exemplul 8 dispersia se calculează cu

jutorul formulei 2° şi se obţine

D2(f)= m2(f) =1312,875-(36,125)2=7,859375.

baterea pătratică (de la) medie sau abaterea standard a funcţiei f este σf=2,8035.

3°. Cuartile

rima cuartilă µ1(f)= µ1 se defineşte prin relaţiile:

4

1)f(

n

11 ≥µ≤ωΩ∈ω⋅ | şi

4

3)f(

n

11 ≥µ≥ωΩ∈ω⋅ |

ar a treia cuartilă µ3(f)= µ3 se defineşte prin relaţiile:

4

3)f(

n

13 ≥µ≤ωΩ∈ω⋅ | şi

4

1)f(

n

13 ≥µ≥ωΩ∈ω⋅ | .

Evident, a doua cuartilă 2µ definită prin analogie cu şi este chiar

ediana. Intervalul determinat de

1µ 3µ

1µ şi 3µ se numeşte interval intercuartilic, dar

rin abuz de limbaj şi diferenţa 3µ - 1µ se numeşte tot interval intercuartilic.

xemplul 14. Dacă Ω = 7 şi f are valorile 1, 2, 2, 4, 4, 5, 6 atunci µ1=2, µ2=4,

3= 5. În general, dacă |Ω|=4p+3 şi f are valorile x1, x2,..., x4p+3 atunci µ1=xp+1,

2=x2p+2, µ3= x3p+3. În cazul Ω = 8 şi f are valorile 1, 2, 2, 3, 3, 4, 5, 5 atunci

1=2, µ2=3, µ3= 5 iar dacă Ω = 8 şi f are valorile 1, 2, 2, 3, 4, 4, 4, 6 atunci

1=2, µ2 este orice număr cuprins între 3 şi 4 iar µ3= 4.

Pentru funcţia din Exemplul 8 pag. 13, pe baza Tabelului 3 şi utilizând

nterpolarea liniară, găsim µ1=33,250, µ2=35,750, µ3=38 (Verificaţi!).

22

Page 27: matematici aplicate

Intervalul intercuartilic are lungimea µ3-µ1=4,750 şi reprezintă lungimea unui

interval care conţine jumătate din numărul valorilor funcţiei. El dă evident

informaţii asupra împrăştierii valorilor funcţiei.

Evident, cuartilele nu sunt neapărat unic definite dar sunt estimatori

robuşti în sensul că sunt mai puţin sensibili la prezenţa unor valori extreme

mari. Calculul cuartilelor se face uşor utilizând funcţia de repartiţie a funcţiei

(caracterului).

Diferenţa intercuartilică are de jucat faţă de abaterea pătratică medie acelaşi rol

pe care îl joacă mediana vis-à-vis de medie.

Inegalitatea lui Cebîşev. Fie f: →Ω ¡ cu ,...,, n21 ωωω=Ω , x1,

x2,..., xm - valorile distincte ale funcţiei f şi fi – frecvenţa relativă a valorii xi ( i

=1,2,…,m). Se pune problema să se determine frecvenţa relativă ευ a valorilor

f(ω) ale funcţiei f pentru care ε<−ω f(M)(f |)| , adică

|)f(M)(f||cardn1

ε<−ωΩ∈ω=υε .

Suntem conduşi la inegalitatea (vezi [1] pag.54)

2

2 )f(D1ε

−≥υε

cunoscută sub numele de inegalitatea lui Cebîşev.

Exemplul 15. Revenind la exemplul 8 prezentat anterior, dacă dorim să estimăm

frecvenţa relativă a numărului de oi care au masa între 34 şi 38 kg aplicăm

formula lui Cebîşev cu M(f)=35,125, ε=2,875, D

ευ

2(f)=7,859375 şi obţinem

0490,8752

85937571

22 ,

,≅−≥υ , deci cel puţin 4, 9% dintre oi vor avea masa între 34 şi

38 kg. Evident, această estimaţie este grosieră (vezi demonstraţia din [1], pag.

54) dar are avantajul că este uşor de făcut. Într-adevăr, în realitate sunt 21 oi cu

masa între 34 şi 38 kg, adică peste 50%. Ineficienţa acestei inegalităţi în acest

exemplu este motivată de faptul că ε2 şi dispersia funcţiei au valori

comparabile.

Exemplul 16. Numărul xi de purcei la o fătare la rasa Marele Alb la o fermă

este dat în tabelul următor

23

Page 28: matematici aplicate

xi 5 6 7 8 9 10 ni 7 10 15 25 25 18

(ni este numărul de scroafe care au avut xi purcei la o fătare). Se consideră

funcţia reală f definită pe mulţimea tuturor scroafelor şi care asociază fiecărei

scroafe numărul de purcei pe care i-a fătat. Atunci M(f)=8,05 şi D2(f) = 2,1475.

Dacă dorim să estimăm frecvenţa relativă ευ a numărului de scroafe care fată

între 6 şi 10 purcei (la o fătare) aplicăm formula lui Cebîşev cu M(f)=8, ε=2,

D2(f) = 2,1475 şi obţinem 4604

1475212 ,,−≥υ ≅ , deci cel puţin 46% dintre

scroafe vor făta între 6 şi 10 purcei. Evident, şi această estimaţie este grosieră

(vezi demonstraţia din [1], pag. 54) dar este mai utilă decât cea din exemplul

precedent..

Inegalitatea lui Cebîşev este de interes teoretic major.

b) Alte caracteristici numerice ale funcţiilor

1°. Coeficientul de variabilitate

Coeficientul de variabilitate (Pearson) al funcţiei f este numărul notat

prin C.V.(f)=C.V. definit prin formula

)(..

fMVC fσ= .

În practică se obişnuieşte să se folosească coeficientul de variabilitate

procentual C.V.% definit prin C.V.%= C.V.⋅100.

În zootehnie funcţionează următoarea convenţie:

0 < C.V.% < 10% - variabilitatea este mică,

10% < C.V.% < 20% - variabilitatea este medie,

C.V.% > 20% - variabilitatea este mare.

De exemplu, pentru funcţia din Exemplul 8 avem

C.V.= 0798012535

80352 ,,

,≅ sau C.V.%=7,8%<10%.

Apreciem deci că variabilitatea este mică.

24

Page 29: matematici aplicate

2°. Coeficientul de asimetrie

Pentru aprecierea simetriei graficului frecvenţelor se folosesc în mod obişnuit mai mulţi indici.

Numărul γ1(f)= γ1 definit prin 3f

31

fmf

σ=γ

)()( se numeşte coeficientul de

asimetrie al funcţiei f; γ1 dă informaţii asupra abaterii graficului funcţiei f de la simetria în raport cu dreapta x=M(f).

Pentru funcţia din Exemplul 8 se calculează, cu ajutorul formulelor din

Exerciţiul 13 şi al formulei de definiţie pentru γ1

m3(f) = - 2,07421875 γ1= - 0,094139 .

Se poate accepta că asimetria este mică.

În fapt, toate momentele centrate de ordin impar dau informaţii asupra

abaterilor de la simetrie. Aceşti indicatori sunt sensibili la prezenţa valorilor

extreme mari. Există şi indicatori robuşti ai abaterilor de la simetrie dintre care

cităm coeficientul de disimetrie c=c(f) şi indicele asimetriei As=As(f) (Pearson).

Coeficientul de disimetrie este definit prin

13

231 2fcc

µ−µ

µ−µ+µ== )( .

c ia valori între –1 şi +1. Se fac următoarele constatări:

c=0 atunci când graficul este simetric,

c>0 şi mai apropiat de +1 dacă graficul are ramura dreaptă de pantă lină,

c<0 şi mai apropiat de -1 dacă graficul are ramura stângă de pantă lină.

De exemplu, pentru funcţia din Exemplul 8 coeficientul de disimetrie este

0600588202503338

7503523825033c ,,

,,,

−≅−≅−

⋅−+= .

Se apreciază că asimetria este mică, cu graficul uşor abătut spre dreapta

(ramura stângă de pantă mai lină).

Indicele asimetriei (Pearson) este

fss

fMofMAfA

σ−

==)()()( .

Dacă As<0 distribuţia punctelor graficului are asimetrie dreaptă (ramura stângă

de pantă mai lină), dacă As>0 distribuţia punctelor graficului are asimetrie

25

Page 30: matematici aplicate

stângă (ramura dreaptă de pantă mai lină) iar dacă As=0 distribuţia este aproape

simetrică. Evident, acest indicator se foloseşte numai pentru funcţii unimodale.

3°. Coeficientul de aplatizare (boltire)

Numărul γ2(f)= γ2 definit prin 4f

42

fmf

σ=γ

)()( se numeşte coeficientul de

aplatizare (boltire) al funcţiei f; γ2 dă informaţii asupra turtirii graficului funcţiei

f comparativ cu graficul distribuţiei normale cu aceeaşi medie (vezi [2], pag. 90)

pentru care γ2 =3.

Pentru funcţia din Exemplul 8 se calculează, cu ajutorul formulelor din Exerciţiul

13 şi al formulei de definiţie pentru γ2

m4(f) = 122,4750488125 γ2= 1,9827662<3.

Curba este deci mai turtită decât graficul distribuţiei normale, adică este o curbă platicurtică.

d) Caracteristici numerice pentru familii de funcţii 1°. Covarianţa a două funcţii (caractere) Fie f, g: Ω ¡ două funcţii (caractere) definite pe mulţimea Ω=

. Se numeşte covarianţa perechii (f,g) numărul notat cu S(f,g)

definit ca medie a variabilei

,...,, n21 ωωω=

M(g))-(gM(f))-(f = h ⋅ , adică :

M(g))]-(gM(f))-M[(f = g)S(f, ⋅ .

Covarianţa este pozitivă când h ia "în dominantă" valori pozitive, adică

covarianţa este pozitivă când f şi g au tendinţa să varieze în acelaşi sens şi

negativă când f şi g au tendinţa să varieze în sensuri contrare.

Evident S(f,f) = D2(f), adică dispersia este un caz particular al covarianţei.

Proprietăţile covarianţei

1°. S(f, , ∀f, g: f)S(g,g) = →Ω ¡

2°. S(f, M(g)M(f)-M(fg)g) ⋅= , ∀f, g: →Ω ¡

3°. ∈βα∀αβ=βα , , g)S(f,g)f,S( ¡, ∀f, g: →Ω ¡ 4°. , ∀f, g: f)S(g,b)ga,S(f =−− →Ω ¡, ∀funcţiile constante a şi b

În practică, în locul covarianţei (corelaţiei) se foloseşte des un alt

indicator al dependenţei dintre două funcţii şi anume coeficientul de corelaţie

26

Page 31: matematici aplicate

care are avantajul că este adimensional şi are o interpretare geometrică simplă

ca fiind cosinusul unghiului a doi vectori din ¡n.

Se numeşte coeficientul de corelaţie al funcţiilor f, g numărul notat cu

(f, g) definit prin: ρ

(g)D(f)D

g)S(f, = g)(f,22 ⋅

ρ .

Ine

şi

for

Ex

na

S(

ρ(Ve

Ex

Y

Ne

do

co

Proprietăţile coeficientului de corelaţie

1°. , ∀f, g: ¡ )f(g,g)(f, ρ=ρ →Ω

2°. ∈βα∀ρ=βαρ αβαβ , , g)(f,g)f,( || ¡, ∀f, g: →Ω ¡

3°. )f(g,b)ga,(f ρ=−−ρ , ∀f, g: →Ω ¡, ∀funcţiile constante a şi b

galitatea Cauchy-Schwartz-Buniakowschi asigură că totdeauna 1)g,f( ≤ρ

că 1)g,f( =ρ dacă şi numai dacă între funcţiile f şi g există o relaţie de

ma af + bg + c = 0 cu a,b,c∈¡.

erciţiul 14. Scrieţi formulele pe baza cărora se fac calculele pentru determi-

rea directă a covarianţei şi a coeficientului de corelaţie:

f,g)=....................................................................................................................

f,g)=.................................................................................................................... rificaţi-vă pe baza formulelor (9) şi(11) din [1], pag.56 şi 57.

emplul 17. În urma unei experienţe în care s-au urmărit două caractere X şi

s-au obţinut următoarele date

X 1,24 1,43 1,60 1,66 1,73 1,82 1,85 1,90 1,98

Y 0,57 0,14 0,75 0,60 0,50 0,35 0,25 0,19 0,97

propunem să determinăm covarianţa şi coeficientul de corelaţie ale celor

uă caractere. Putem aplica direct definiţiile dar putem apela la “centrări”

nvenabile. Avem M(X)=1,69 şi M(Y)=0,48 – valori exacte (nerotunjite).

X Y X-1,69 Y-0,48 (X-1,69)(Y-0,48) (X-1,69)2 (Y-0,48)2

1,24 0,57 -0,45 0,09 -0,0405 0,2025 0,0081

1,43 0,14 -0,26 -0,34 0,0884 0,0676 0,1156

1,60 0,75 -0,09 0,27 -0,0243 0,0081 0,0729

1,66 0,60 -0,03 0,12 -0,0036 0,0009 0,0144

1,73 0,50 0,04 0,02 0,0008 0,0016 0,0004

1,82 0,35 0,13 -0,13 0,0169 0,0169 0,0169

27

Page 32: matematici aplicate

1,85 0,25 0,16 -0,23 0,0368 0,0256 0,0529

1,90 0,19 0,21 -0,29 0,0609 0,0441 0,0841

1,98 0,97 0,29 0,49 0,1421 0,0841 0,2401

Suma=

=15,21

Suma=

=4,32

Suma=

=0

Suma=

=0

Suma=

=0,0483

Suma=

=0,4514

Suma=

=0,6054

Atunci 05409

04830YX ,,),( ==S adică X şi Y sunt foarte slab corelate. În plus,

D2(X)=0,0501, D2(Y)=0,0673 , σX=0,2239, σY=0,2594

092970058079660

03150

2594022390

0540YX ,

,,

,,,),( ≅=⋅

=ρ .

Aceasta înseamnă că X şi Y nu acceptă legături de tip liniar.

2°. Matricea de covarianţă (corelaţie) a p funcţii Date p funcţii f1, f2,..., fp : →Ω ¡ unde ,...,, n21 ωωω=Ω , se defineşte

matricea de covarianţă ca fiind p× p-matricea S(f1, f2,..., fp) = [ , unde s]ijs ij =

S(fi, fj).

Se poate defini şi matricea coeficienţilor de corelaţie R(f1, f2,..., fp)

=[ , unde pentru i ]ijρ )jf,if(ij ρ=ρ ≠ j şi iiρ =1 pentru i = 1,2,...,n.

Exerciţiul 15. Se studiază pentru 11 specii de păsări următoarele trei variabile:

X – greutatea adultului (în grame)

Y – vârsta de maturitate sexuală (în ani)

Z – durata de incubaţie a ouălelor (în zile).

Rezultatele sunt prezentate în tabelul de mai jos: X 1050 770 400 500 800 1500 1700 120 320 300 360

Y 4,0 3,0 2,5 2,5 4,0 4,0 5,0 2,0 2,5 2,0 2,5

Z 28 25 26 25 26 28 27 21 24 23 21

Arătaţi că matricea de covarianţă a celor trei caractere (funcţii) este

=

09169101101012

9101991091482

10101291482266249

ZYXS

,,,,,,

,,),,( .

Determinaţi apoi matricea de corelaţie ρ(X, Z, Y) a celor trei caractere.

Remarcă. Am prezentat elemente de studiul corelaţiilor pentru funcţii

numerice. Se pot defini aceste noţiuni şi pentru caractere calitative sau ordinale.

28

Page 33: matematici aplicate

3°. Regresia liniară

Fie f,g: →Ω ¡ două funcţii (caractere) definite pe ,...,, n21 ωωω=Ω .

Ne propunem să găsim funcţia de forma a + bf (liniară în f) care să descrie cel

mai bine comportarea lui g . Aceasta înseamnă să determinăm numerele a şi b

care minimizează expresia:

))fb-a-M((gn=])bf(-a-)[g(=b)h(a, 22 ⋅⋅ωω∑Ω∈ω

Se demonstrează că funcţia h(a,b) ia valoarea minimă h(a0,b0) unde

ao = M(g) - bo M(f) şi (f)Dg)S(f, b 2o = .

Numerele ao şi bo se numesc coeficienţii regresiei funcţiei g asupra funcţiei f.

Dreapta y = ao + bo x se numeşte dreapta de regresie a lui g asupra lui f sau

regresia caracterului g asupra caracterului f. Similar se defineşte regresia lui f

asupra lui g; dreapta de regresie a lui f asupra lui g este x = a1 + b1y , unde

a1 = M(f) - b1 M(g) (g)Dg)S(f, 21 =b .

Exemplul 18. In cazul Exemplului 17 dreapta de regresie a caracterului Y

asupra caracterului X are ecuaţia

69105010

00540480x

05010

00540y ,

,,,

,,

⋅−+= adică y=0,1078 x+0,5826.

Similar se găseşte că dreapta de regresie a caracterului X asupra caracterului Y

are ecuaţia

x=0,02082y+1,68001 .

Exerciţiul 16. Rezultatele măsurătorilor a două caractere cantitative f şi g sunt

înregistrate în tabelul următor

i 1 2 3 4 5 6 7 8 9 10

f 0,25 0,37 0,44 0,55 0,60 0,62 0,68 0,70 0,73 0,75

g 2,57 2,31 2,12 1,92 1,75 1,71 1,60 1,51 1,50 1,41

i 11 12 13 14 15 16 17

f 0,82 0,84 0,87 0,88 0,90 0,95 1,00

g 1,33 1,31 1,25 1,20 1,19 1,15 1,00

Verificaţi că:

29

Page 34: matematici aplicate

M(f) = 0,7029, M(g) = 1,5782, D2(f)=0,0418, σf=0,2042, D2(g)=0,1806, σg=0,4250, S(f, g)=-0,0863, ρ(f, g) = 0,09943. Determinaţi apoi dreapta de regresie a caracterului f asupra lui g şi a carac-

terului g asupra lui f.

Aplicaţie Pentru un hibbrid de porumb H dorim să analizăm două caracteristici,

lungimea ştiuletelui şi numărul de boabe pe rând , în vederea comparării cu alţi

hibrizi. În acest scop se aleg 15 ştiuleţi pentru care se determină valorile celor

două caracteristici. Datele obţinute sunt înregistrate în Tabelul 6.

Acestui tabel îi asociem funcţiile cu valori reale f şi g definite pe

mulţimea D = 1, 2, …, 15 prin legile de corespondenţă f(i) = xi şi g(i) = yi

(tabelul este de fapt definiţia sintetică a celor două funcţii). Ne propunem să

determinăm covarianţa, coeficientul de corelaţie, regresia funcţiei f asupra

funciei g şi regresia funcţiei g asupra funcţiei f.

Datele necesare determinării acestor caracteristici numerice sunt conţinute

în Tabelul 7.

Nr.crt.

Lung.ştiul. mm xi

Nr. boabe/rând yi

C

Tabelul 6

1 188 36 2 185 38 3 166 41 4 158 32 5 162 41 6 173 39 7 177 42 8 156 37 9 168 35

10 182 46 11 171 45 12 157 38 13 156 37 14 179 36 15 187 42

M(f)=171 M(g)=39

Tabelul 7 Nr.

rt. Lung.ştiul. mm

xi

Nr. boabe/ rând

yi

xi - M(f)

yi –

M(g)

(xi - M(f))× (yi – M(g))

(xi - M(f))2

(yi –

M(g))2

1 188 36 17 -3 -51 329 9 2 185 38 14 -1 -14 196 1 3 166 41 -5 2 -10 25 4 4 158 32 -13 -7 91 169 49 5 162 41 -9 2 -18 81 4

30

Page 35: matematici aplicate

6 173 39 2 0 0 4 0 7 177 42 6 3 18 36 9 8 156 37 -15 -2 30 225 4 9 168 35 -3 -4 12 9 16

10 182 46 11 7 77 121 49 11 171 45 0 6 0 0 36 12 157 38 -14 -1 14 196 1 13 156 37 -15 -2 30 225 4 14 179 36 8 -3 -24 64 9 15 187 42 16 3 48 256 9

M(f)= =171

M(g)=39 S(f,g)= =13,(3)

D2(f)= =129,0(6)

D2(g)= =13,6

Covarianţa S(f,g) = 13,(3) este pozitivă şi indică faptul că cele două

caractere variază în dominantă în acelaşi fel . Coeficientul de corelaţie este

317,06,13)6(0,129

)3(,13)g,f( ≈⋅

Faptul că ρ(f,g) are valoarea apropiată de zero nu se interpretează ca semn al

unei slabe dependenţe între cele două caractere ci ca un semn al lipsei unei

dependenţe de tip liniar între cele două funcţii. Într-adevăr, există exemple de

caractere (funcţii) legate prin relaţii funcţionale nebanale pentru care coeficientul

de corelaţie este nul.

Dreapta de regresie a funcţiei f asupra funcţiei g este de forma x =

= co + doy, unde

78,1323998,0171c,98.06,13

)3(,13d oo =⋅−=≈=

adică x= 132,78 + 0,98 y este dreapta de regresie căutată. Similar se determină

şi coeficienţii dreptei de regresie a funcţiei g asupra funcţiei f; se obţin valorile

045,21a,105,0)6(0,129

)6(,13b oo ≈≈=

adică y = 21,045 + 0,105 x este dreapta de regresie căutată.

Trebuie menţionat că în acest caz am determinat cele două drepte de regresie pentru a exemplifica concret modul de lucru în acest caz. Aşa cum am menţionat mai sus , faptul că ρ(f,g) este apropiat de zero ne spune că aproximă-rile f ≈ co +dog şi g ≈ ao +bof nu sunt utilizabile. Acest lucru se vede din Tabelul 8.

Tabelul 8 Nr.crt. xi co+doyi yi ao+boxi

1 188 168,06 36 40,785

2 185 170,02 38 40,470

3 166 172,96 41 38,475

4 158 163.36 32 37,635

31

Page 36: matematici aplicate

32

5 162 172,96 41 38,055

6 173 171,00 39 39,210

7 177 173,94 42 39,630

8 156 169,04 37 37,425

9 168 167,08 35 38,685

10 182 177,86 46 40,155

11 171 177,08 45 39,000

12 157 170,02 38 37,530

13 156 169,04 37 37,425

14 179 168,06 36 39,840

15 187 173,94 42 40,680

Acceptând cele două aproximări, apare problema să decidem care dintre

ele este mai bună. Pe baza analizei Tabelului 8, s-ar părea că aproximarea g ≈

ao +bof este mai bună decât aproximarea f ≈ co +dog, dar lucrurile nu sunt clare

doar dintr-o simplă analiză a tabelului. Într-adevăr abaterea de 20 mm raportată

la valoarea medie 171 mm este comparabilă cu abaterea de 4,785 raportată la

media 39 . Prin urmare cele două aproximări sunt la fel de bune sau la fel de

rele. În concluzie, o comparaţie a două astfel de aproximări trebuie făcută pe

criterii clare, cum este – de exemplu - raportarea la valoarea medie (şi de

preferat aproximarea corespunzătoare raportului minim).

Trebuie remarcat că de această dată am calculat caracteristicile cerute

direct pe baza definiţiilor lor. Acest lucru a fost avantajos de făcut din următoarele

motive:

- mediile funcţiilor f şi g sunt numere întregi,

- frecvenţele absolute ale valorilor funcţiilor sunt , în marea lor majo-

ritate, egale cu 1 ,

- valorile funcţiilor sunt mici

Simplul fapt că valorile mediilor funcţiilor sunt numere întregi era un

motiv suficient de bun pentru a face centrările în aceste medii.

În sfârşit, trebuie menţionat că deşi caracteristicile numerice se pot

calcula totdeauna ele nu se pot utiliza totdeauna în interpretarea rezultatelor.

Rezultatele de mai sus cu privire la dreptele de regresie ne exemplifică această

afirmaţie. Astfel de calcule se fac în mod obişnuit în statistica descriptivă.

Rezultatele lor sugerează anumite concluzii care sunt sau nu validate prin

metodele statisticii decizionale (inferenţiale).

Page 37: matematici aplicate

Capitolul II

ELEMENTE DE ALGEBRĂ ABSTRACTĂ

Problemele din ce în ce mai complexe puse ştiinţei contemporane spre

rezolvare au impus transpunerea acestora în limbaj algebric în speranţa că vor

deveni mai accesibile. Speranţele au fost parţial justificate de succesele obţinute

utilizând elemente de teoria semigrupurilor, grupurilor, inelelor şi câmpurilor

finite în rezolvarea unor probleme din genetică, chimie, fizică, cristalografie,

artă, etc..

§1. Lege de compoziţie

Definiţia 1. Fie M o mulţime nevidă. Se numeşte lege de compoziţie sau operaţie

binară pe M orice aplicaţie . Pentru orice (x,y) MMM: →×ϕ ∈ M M,

elementul z=ϕ se numeşte compusul lui x cu y prin legea de compoziţie φ.

×

y)(x,

În locul notaţiei , pentru compusul elementelor x şi y, se preferă să

se folosească notaţii de forma :

y)(x,ϕ

, y x , y x , y x , y x , y x , y x , y +x o⊥∧∨∗• etc..

Pentru a arăta că pe mulţimea M este dată legea de compoziţie (operaţia) se

folosesc notaţiile sau M ( .

ϕ

( ϕ,M ) )ϕ

Exemplul 1.1°. Adunarea (+) şi înmulţirea (·) sunt operaţii binare pe fiecare dintre mulţimile de numere cunoscute ¥, ¢, ¤, ¡, £. Scăderea (-) nu este operaţie pe ¥ (de ce?), dar este operaţie pe ¢, ¤, ¡, £. 2°. Reuniunea ( ), intersecţia ( ), diferenţa ( \ ) şi diferenţa simetrică (∆) sunt operaţii binare pe mulţimea P(X) a tuturor părţilor mulţimii nevide X. 3°. Pe mulţimea R

∪ ∩

n = 0, 1, 2, ... , n-1 se definesc operaţiile: adunarea modulo n (⊕ ) şi înmulţirea modulo n (e).

Exerciţiul 1. Definiţi operaţiile: adunarea modulo 4 (⊕ ) şi înmulţirea modulo

4 (e).Verificaţi-vă pe baza manualului [1], pag. 66.

Răspuns..........................................................................................................................

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

O mulţime nevidă dotată cu una sau mai multe operaţii (binare sau nu) se

numeşte structură algebrică sau sistem algebric. 33

Page 38: matematici aplicate

Definiţia 2. Operaţia binară MMM: →×ϕ se numeşte:

1°. asociativă dacă z))(y,(x,=z)y),(x,( ϕϕϕϕ ∀x,y,z∈M.

2°. comutativă dacă . M yx, x)(y, = y)(x, ∈∀ϕϕ

Exerciţiul 2. În cazul în care operaţia binară este notată cu "*","+","·" proprietăţile

de asociativitate şi comutativitate au respectiv formele : (completaţi!)

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

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

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

Exerciţiul 3. Folosind eventual modelul din [1] pag.67, completaţi tablele Cayley

pentru R5 dotat operaţiile de adunare şi înmulţire modulo 5:

Exemplul 2.1°. Adunarea (+) şi înmulţire

comutative pe fiecare dintre mulţimile de nu

"∪ " şi intersecţia "∩ " sunt operaţii şi asocia

3°. Scăderea (-) pe Z, Q, ú, ÷ este operaţie ş

Definiţia 3. Elementul e ∈ M se numeşte elem

"*", sau element neutru pentru M(*), dacă satisfa

Dacă există element neutru pentru o o

Exerciţiul 4. Daţi exemple de operaţii bina

ple de operaţii binare care nu au element un

Definiţia 4. Fie "*" o operaţie binară pe M a

se numeşte simetrizabil dacă există x' ∈ M

acest caz x' se numeşte simetricul elementulu

Dacă x' este simetricul lui x, atunci x

Exerciţiul 5. Daţi exemple de elemente sim

Definiţia 5. Se spune că operaţia "*" este :

1°. distributivă la stânga în raport cu operaţia

34

e 0 1 2 3 4 0 0 1 3 2 1 3 4 4 2

⊕ 0 1 2 3 4 0 1 2 2 3 4 0 1 3 4

a (·) sunt operaţii şi asociative şi

mere ù, Z, Q, ú, ÷ . 2°. Reuniunea

tive şi comutative pe mulţimea P (X ).

i neasociativă şi necomutativă.

ent neutru pentru legea de compoziţie

ce condiţia: e * x = x * e = x, ∀x ∈ M.

peraţie binară "*", acesta este unic.

re care au element unitate şi exem-

itate.

vând elementul neutru e. Elementul x

astfel încât x * x' = x' * x = e. În

i x.

este simetric pentru x', adică x=(x')'.

etrizabile.

"·" dacă

Page 39: matematici aplicate

x * (y · z) = (x * y) · (x * y), ∀x, y, z ∈ M;

2°. distributivă la dreapta în raport cu operaţia "·" dacă

(y · z) * x = (y * x) · (z * x), ∀x, y, z ∈ M,

3°. distributivă dacă este şi distributivă la stânga şi distributivă la dreapta.

§2. Structuri algebrice de bază

Definiţia 6. M(*) se numeşte

1. semigrup dacă "*" este operaţie asociativă,

2. monoid dacă M(*) este semigrup cu element neutru,

3. cvasigrup dacă ecuaţiile a * x = b şi x * a = b au soluţii unice oricare ar fi a, b ∈M;

4. loop (sau buclă) dacă este cvasigrup cu element neutru

5. grup dacă este monoid pentru care fiecare element este simetrizabil.

Dacă în plus "*" este şi comutativă M(*) se numeşte respectiv semigrup comu-

tativ, monoid comutativ, cvasigrup comutativ, loop comutativ şi respectiv grup

comutativ sau abelian.

Exemplul 3. 1°. N*(+‘) este semigrup comutativ. 2°. ¥k(+) şi ¥k(·) sunt semigru-

puri comutative (aici ¥k = k, k+1, ... ).3°. ¥ (+), ¢(+) sunt monoizi comutativi.

4°. F (X)() este monoid (necomutativ).5°. Mulţimea ¡

* a tuturor numerelor

reale nenule, dotată cu operaţia "•" definită prin x • y = x3 · y ∀ x, y ∈ ¡* este

cvasigrup (necomutativ). 6°. ¢(+), ¤(+), ¡(+), £(+) sunt grupuri comutative

(abeliene).7°. Mulţimea Sn a tuturor permutărilor de n > 2 elemente este grup

(necomutativ!) în raport cu operaţia de compunere a permutărilor.

Dată M(*), pentru orice element fixat a ∈ M se pot defini aplicaţiile

La , Ra : M M prin: → Mx a*x=(x)R x*a=(x)L aa ∈∀, . La , Ra se numesc

translaţia (multiplicarea) stângă prin a şi respectiv translaţia (multiplicarea)

dreaptă prin a . De exemplu, pentru R5(⊕) translaţia stângă L2 este

x 0 1 2 3 4

L2(x) 2 3 4 0 1

iar pentru R5(u) translaţia dreaptă R3 este

x 0 1 2 3 4

R3(x) 0 3 1 4 2

În orice cvasigrup, loop sau grup , toate translaţiile stângi şi toate translaţiile

drepte sunt aplicaţii bijective.

35

Page 40: matematici aplicate

Exerciţiul 6. Cum interpretaţi bijectivitatea translaţiilor stângi şi/sau drepte pentru structurile algebrice de ordin finit? Concretizaţi pentru cvasigrupuri şi loopuri. Verificaţi-vă pe baza manualului [1], pag. 73.

Exerciţiul 7. Enumeraţi proprietăţile şi regulile de calcul ale structurilor algebrice

enumerate mai sus.

Definiţia 7. O mulţime nevidă I dotată cu două legi de compoziţie, una notată

aditiv (+) şi numită adunare iar cealaltă notată multiplicativ (·) şi numită înmulţire

se numeşte inel dacă: I1. I(+) este grup comutativ, I2. I(·) este monoid, I3.

înmulţirea este distributivă faţă de adunare. Dacă în plus înmulţirea este

comutativă inelul se numeşte inel comutativ.

Exemplul 4. 1°. ¢(+,·) este inel comutativ. 2°. Mulţimea Mn(¡)(+,·) este inel (necomutativ).

Elementele lui I simetrizabile în raport cu înmulţirea se numesc elemente inversabile sau unităţi. Unităţile inelului ¢(+,·) sunt -1 şi +1.

Exemplul 5. 1°. ¢(+,·) este inel comutativ fără divizori ai lui zero, adică este

domeniu de integritate. 4°. Mulţimea Mn(¡)(+, ·) este inel (necomutativ) cu

divizori ai lui zero .

Exerciţiul 8. Arătaţi că ,(Rn ⊕ e este inel comutativ fără divizori ai lui zero când n este număr prim şi inel cu divizori ai lui zero dacă n nu este prim.

)

Definiţia 8. Un inel K(+, ⋅ ) pentru care 0 ≠ 1 şi având proprietatea că orice

element ≠ 0 este inversabil se numeşte corp. Orice corp comutativ se numeşte câmp.

Exerciţiul 9. Verificaţi că: 1º. e) este câmp. ,(⊕5R

2º.Mulţimea K = 0, 1, a, b dotată cu operaţiile "+" şi " " date prin tablele Cayley de mai jos este câmp.

+ 0 1 a b

0 0 1 a b

1 1 0 b a

a a b 0 1

b b a 1 0

§3. Pătrate latine

Fie M o mulţime cu n elemente.

Definiţia 9. 1. Un tablou L format din n linii şi

numeşte pătrat latin peste M dacă fiecare elem

numai o singură dată în fiecare linie şi în fie

36

⋅ 0 1 a b

0 0 0 0 0

1 0 1 a b

a 0 a b 1

b 0 b 1 a

n coloane cu elemente din M se

ent din M apare în L o dată şi

care coloană. Se obişnuieşte ca

Page 41: matematici aplicate

elementele lui M să se numească elementele pătratului latin L. 2. Două pătrate

latine de ordinul n se numesc ortogonale dacă prin suprapunere fiecare element al

primului pătrat se cuplează o dată şi numai o singură dată cu fiecare element al

celuilalt pătrat latin

Exemplul 6. Tabla Cayley a oricărui cvasigrup , loop sau grup , de ordin n , G (*)

este un pătrat latin de ordinul n peste G.

Exerciţiul 10. Descrieţi o metodă de construcţie de pătrate latine ortogonale.

Consultaţi eventual [1] pag. 82.

Exerciţiul 11. Descrieţi un experiment care impune utilizarea pătratelor latine.

Exemplul 7. Vom considera câmpul K(+, .) din Exerciţiul 9. Vom construi pe

baza Teoremei 2, [1], pag.82, pătratele latine corespunzătoare lui u=a şi u=b şi

vom arăta că sunt ortogonale. Pentru a aplica formula din teoremă redenumim

elementele lui K şi anume : 0=x0, 1=x1, a=x2, b=x3. Pentru u=a avem

axxax0xxax1xxaxbxxax

bxxax1xxax0xxaxaxxax

0xxaxaxxaxbxxax1xxax

1xxaxbxxaxaxxax0xxax

33a3332

a2331

a1330

a03

23a3222

a2221

a1220

a02

13a3112

a2111

a1110

a01

03a3002

a2001

a1000

a00

=+⋅==+⋅==+⋅==+⋅=

=+⋅==+⋅==+⋅==+⋅=

=+⋅==+⋅==+⋅==+⋅=

=+⋅==+⋅==+⋅==+⋅=

S-a obţinut pătratul latin La

0 1 a b a b 0 1 b a 1 0 1 0 b a

În mod asemănător se va obţine pătratul latin Lb. Pentru u=b avem

1xxbxaxxbx0xxbxbxxbx

0xxbxbxxbx1xxbxaxxbx

bxxbx0xxbxaxxbx1xxbx

axxbx1xxbxbxxbx0xxbx

33b3332

b2331

b1330

b03

23b3222

b2221

b1220

b02

13b3112

b2111

b1110

b01

03b3002

b2001

b1000

b00

=+⋅==+⋅==+⋅==+⋅=

=+⋅==+⋅==+⋅==+⋅=

=+⋅==+⋅==+⋅==+⋅=

=+⋅==+⋅==+⋅==+⋅=

Obţinem pătratul latin Lb

0 1 a b b a 1 0 1 0 b a a b 0 1

Pentru a verifica ortogonalitatea celor două pătrate latine vom identifica elemen-

tele 0, 1, a, b respectiv cu A, B, C, D în La şi cu α, β, γ, δ în Lb. Tabelele astfel

transformate le suprapunem pentru a constata ortogonalitatea.

37

Page 42: matematici aplicate

Exerciţiul 12. Folosind tablele Cayley din Exerciţiul 9, construiţi pătratele latine

L1, L2, L3, L4 corespunzătoare elementelor din R5 şi verificaţi că sunt ortogonale

două câte două.

Aplicaţie Să considerăm experienţa care constă în administrarea a trei raţii diferite

la vaci în lactaţie. Deoarece curba de lactaţie variază mult de la o vacă la alta este

greu să se alcătuiască loturi omogene şi de aceea se obişnuieşte ca cele trei raţii

A, B, C să se experimenteze pe acelaşi animal în trei perioade succesive. Se aleg

deci, prin tragere la sorţi, trei vaci V1, V2, V3. Având în vedere că ordinea de

administrare a raţiilor are influenţă asupra efectelor acestor raţii, raţiile se vor

administra astfel încât să se elimine aceste influenţe. Acest lucru se realizează

administrând fiecare raţie la câte o singură vacă într-o anumită perioadă,

perioadele fiind separate de intervale de timp suficient de mari astfel încât să se

elimine influenţa ordinii administrării celor trei raţii. Cum fiecare vacă trebuie să

folosească fiecare dintre raţii se ajunge la o planificare de tipul următor , care a

condus la un pătrat latin L peste mulţimea M = A, B, C.

L

V1 V2 V3

perioada I A B C

perioada II B C A

perioada III C A B

A B C D

C D A B

D C B A

B A D C

α β γ δ

δ γ β α

β α δ γ

γ δ α β

38

Aα Bβ Cγ Dδ

Cδ Dγ Aβ Bα

Dβ Cα Bδ Aγ

Bγ Aδ Dα Cβ

Page 43: matematici aplicate

Capitolul III

SPAŢII VECTORIALE

Se ştie că rezolvarea multor probleme din toate domeniile de activitate se reduce

în final la rezolvarea unor sisteme de ecuaţii liniare (de exemplu, orice ajustare

polinomială utilizată în legătură cu orice experiment din biologie revine la rezol-

varea unui sistem de ecuaţii liniare) sau la determinarea vectorilor şi valorilor

proprii ale unor operatori (de exemplu, determinarea funcţiilor de undă asociate

unui sistem de microparticule se reduce la determinarea de vectori şi valori pro-

prii). În fapt, s-a ajuns la transpunerea unor probleme concrete în cadrul algebrei

liniare. Unul dintre obiectele de bază ale algebrei liniare este spaţiul vectorial sau

liniar. Ca exemple cităm spaţiile vectoriale reale ale vectorilor liberi din spaţiu sau

din plan, spaţiile vectoriale ale componentelor atomice şi moleculare.

§1. Spaţii vectoriale

1. Definiţii. Exemple

Definiţia 1. Fie K un câmp. Se numeşte spaţiu vectorial sau spaţiu liniar

peste câmpul K orice mulţime nevidă V dotată cu o operaţie binară +:V V →

V, numită adunare şi o aplicaţie ·:K

×

( ) vuv,u rrrr+→ ×V → V, ( ) uu, rrr

⋅α→α ,

numită operaţie externă (sau lege de compoziţie externă) care satisfac axiomele:

1°. V(+) este grup abelian,

2°. 1· v = vr , ∈ V (1 este elementul neutru la înmulţirea din K), r∀ vr

3°. α ·(u +r vr) = α ·u + · , rα vr ∀α ∈ K, ∀ ur , vr ∈ V,

4°. (α + β )·u = ·u + · , rα

rβ ur ∀α, β ∈ K, ∀ ur ∈ V,

5°. α ·(β ·u ) = ( ·β )·urα

r, ∀α, β ∈ K, ∀ ur ∈ V.

Terminologie. 1°. Elementele lui V se numesc vectori iar operaţia de

adunare se numeşte adunarea vectorilor. Din motive didactice preferăm să notăm

(mai greoi) vectorii prin litere având o săgeată deasupra; aceasta permite să-i

39

Page 44: matematici aplicate

distingem uşor de elementele din câmpul K. 2°. Elementele lui K se numesc

scalari iar operaţia externă se numeşte înmulţire cu scalari. 3°. Când K = , V se

numeşte spaţiu vectorial real, iar când K = , V se numeşte spaţiu vectorial

complex. 4°. Elementul neutru pentru adunare se numeşte vectorul zero şi se

notează cu 0r

; mai târziu vom nota şi vectorul zero cu 0 (la fel ca scalarul zero)

pentru că, din context, va fi totdeauna clar când este vorba de vectorul zero sau de

scalarul zero. 5°. Opusul 'vr al vectorului vr şi se va nota cu = - . v′r rv

Exemplul 1. 1°. Spaţiul vectorial peste câmpul K definit pe grupul abelian 0

dotat cu înmulţirea cu scalari definită prin ⋅α 0 = 0 , ∀ K se numeşte

spaţiul vectorial nul.

α ∈

2°. Mulţimea 2 dotată cu operaţiile: ( ) ( ) ( ) ( ) ( )212122112121 xxxxyxyxyyxx ⋅α⋅α=⋅α++=+ ,,,,,,

este spaţiu vectorial real. Într-adevăr, dacă )z(z = z , )y,y( = y , )x(x = x 212121 ,,rrr

sunt trei vectori oarecare din 2, egalităţile ( ) ( ) ( )( ) ( ) ),(,,, 222111212121 zyxzyxzzyyxxzyx ++++=++=++

rrr , rrr ( ) ( )( ) ( )222111212121 zyxzyxzzyyxxzyx ++++=++=++ ,,,),()(

asigură că adunarea este operaţie asociativă. Vectorul (0, 0) este element neutru la

adunare, iar vectorul (-x1, -x2) este opusul vectorului (x1, x2) . Comutativitatea

adunării este uşor de verificat.

Exerciţiul 1. 1°.Arătaţi că adunarea matricelor şi înmulţirea matricelor cu scalari

organizează mulţimea M ) ca spaţiu vectorial real. (nm×

2°. Arătaţi că mulţimea ς3 a vectorilor liberi din spaţiu, dotată cu operaţiile

obişnuite de adunare (definită, de exemplu, prin regula paralelogramului) şi

înmulţire cu scalari, este spaţiu vectorial real.

Exerciţiul 2. Enumeraţi regulile de calcul dintr-un spaţiu vectorial:

1°. ...............................................................................................................................

2°. ...............................................................................................................................

3°. ...............................................................................................................................

4°. ...............................................................................................................................

5°. ...............................................................................................................................

Definiţia 2. Spunem că sistemul de vectori S = v,...,v,v m21rrr este un sistem

liniar independent, sau că vectorii v,,...v,v m21rrr sunt liniar independenţi (sau că

40

Page 45: matematici aplicate

vectorii v,,...v,v m21rrr formează un sistem liniar independent), dacă orice relaţie de

forma 0 v +... mm =µ+ v + v 2211 µµ rrr implică 0... m21 =µ==µ=µ . În caz con-

trar se va spune că vectorii (sau sistemul de vectori) sunt liniar dependenţi. Dacă

orice vector din V este combinaţie liniară a vectorilor sistemului S spunem că S

este un sistem de generatori pentru spaţiul vectorial V.

∈−= ),,( v21v 21rr

),( 00v 22 =v11 µ+µ

µ−µ−µ

2 1

1

⊂,, 321 vvvrrr

),(),, 01v1 3 =1−r

0vv2v 321 =++rrr

⊂, 21 vvrr

)2α, 22 vµ+

, 21 vvrr

, 1 eerr

),(),,( 10e01 2 ==r

,( 1221 e µ=µ1e +µrr

),( 00ee 2211 ⇔=µ+µrr

22e1121 err

α+α α=α ),

vr

nn e +11 + e = vrrrr

µ n21 ,...,,µµ µµ ∈

e,...,e,e n21rrr vr

n,...,21 , µµµ ∈

11 vv nn v... rrrµ+µ=

, 21 eerr

22ex21 xxvrr

= ),(

vr

Exemplul 2. Vectorii −= ),( 11 2 sunt liniar independenţi deoarece

orice relaţie , este echivalentă cu sistemul care

are numai soluţia µ

=µ+=

0

0

2

2

1=µ2=0. Dar sistemul de vectori ú2, cu ),2−,(1v1 =r

(v 2 = este liniar dependent pentru că . Sistemul de

vectori S= ú2 este un sistem de generatori pentru 2 pentru că orice vector

( 1v α=r ∈ 2 se poate scrie: 11vv µ=

r unde µ1=-α1-α2, µ2=-2α1-α2.

Definiţia 3. Sistemul de vectori S se numeşte bază a spaţiului vectorial V dacă

r

1°. S este un sistem liniar independent,

2°. S este un sistem de generatori pentru V.

Exemplul 3. 1°.Pe baza Exemplului 2 rezultă că S= este bază în 2.

2°. Sistemul de vectori Bc = 2 cu e1r este bază în 2. Într-

adevăr, egalitatea )2µ implică )021 =µ=µ şi v

r= ( adică Bc este şi sistem liniar independent şi sistem de

generatori în 2. Bc se numeşte baza canonică din 2.

Teorema 1 (de caracterizare a bazei). Sistemul de vectori B = e,...,e,e n21rrr

este bază a spaţiului vectorial V dacă şi numai dacă orice vector ∈ V se scrie

în mod unic sub forma 22 ...+ e cu µ K.

Definiţie 4. Dacă B = este bază în V şi este un vector oarecare din V

atunci scalarii K, unic determinaţi de reprezentarea

22 vr +µ+ ,

se numesc coordonatele vectorului în baza B. vr

41

Exemplul 4. Dacă Bc = este baza canonică din 2 pentru orice vector vr

∈ 2 au loc egalităţile 11exr

+= , adică componentele x1, x2 sunt chiar coordonatele de acelaşi nume ale vectorului . Din Teorema 1 rezultă că baza Bc este singura bază cu această proprietate şi de aceea poartă numele de bază canonică sau bază naturală din 2.

Page 46: matematici aplicate

Exerciţiul 3. Definiţi baza canonică Bc = e,...,e,e n21rrr din n şi arătaţi că au loc

egalităţile nnex...2211n21 exex)x,...,x,x(vr

+++== . rrr

Rezultă că, în baza canonică din n, orice vector din n are i-componenta

(i = 1, 2,..., n) egală cu i-coordonata în baza Bc . Această bază este singura bază cu

această proprietate şi de aceea această bază se numeşte baza canonică sau baza

naturală din n.

Exerciţiul 4. Arătaţi că în spaţiul vectorial real E3 al vectorilor liberi din spaţiu,

orice sistem format din trei vectori (nenuli) necoplanari este o bază pentru E3.

Teorema 2. Din orice sistem de generatori al unui spaţiu vectorial V se poate

extrage o bază a acestui spaţiu .

Instrumentul de lucru care se poate utiliza în rezolvarea majorităţii proble-

melor de algebră liniară este aşa-numita lema substituţiei pe care o prezentăm în cele

ce urmează.

Lema substituţiei. Fie B = e,...,e,e n21rrr o bază a spaţiului vectorial V, Vu∈r -

un vector fix cu u n11e n22 e...err

α++α+α=

ier

şi sistemul de vectori B* obţinut din

B înlocuind vectorul cu vectorul ur (adică B* = ,,...,, 1i21 eee − ,..., ne, 1ieur

+ ).

Au loc afirmaţiile :

rr

rrr rr

1°. B* este bază dacă şi numai dacă 0i ≠α ,

2°. dacă B* este bază a lui V, atunci coordonatele în baza

B

λλλ n*

2*

1* ,...,,

* ale unui vector se exprimă în funcţie de coordonatele V x∈r λλλ 21 ,...,, n în

baza B ale lui xr prin egalităţile = , = ii

jjj

*

i

ii* λ⋅

α

α−λλ

αλ

λ pentru j ≠ i.

Calculele care trebuiesc făcute pentru a determina coordonatele în baza B*

ale vectorilor x , u când se cunosc coordonatele acestora în baza B se organi-

zează sub forma tablourilor:

rr

42

Page 47: matematici aplicate

În aceste tablouri, pe coloane se găsesc coordonatele vectorilor corespun-

zători în bazele indicate la începutul fiecărui tablou . Deoarece s-a presupus că

rezultă că putem înlocui e0i ≠α ir cu ur . Elementul iα se va numi pivot ca o

recunoaştere a rolului important pe care îl are de jucat. De obicei pivotul se

marchează punându-se într-un dreptunghi sau într-un cerculeţ (fie va fi scris cu

caractere mai îngroşate decât restul textului).

⇒ ⇒

. . r

ie . . jer

. . r

ne

1 1 . . . . iα iλ . . . . α j jλ . . . . α n nλ

. . ier

. . jer

. . ner

1ii1 . . . . 1 ii /αλ . . . . 0 ( ) jiij / ααλ−λ . . . . 0 ( ) niin / ααλ−λ

Trecerea de la tabloul B la tabloul B* se face în felul următor :

1°. elementele liniei din B* corespunzătoare liniei pivotului se obţin

împărţind la pivot toate elementele liniei pivotului,

2°. se completează coloana corespunzătoare pivotului cu 0-uri,

3°. toate elementele cu se înlocuiesc cu iλ ij ≠ α⋅αλ

λλ ji

ijj

* - = .

Trecerea de la jλ la λ se poate face formal pe baza următoarei reguli

cunoscută sub numele de regula dreptunghiului şi prezentată schematic în

desenul de mai jos:

*j

Exerciţiul 5. Cum s

vectori este o bază?

B ... ur ... xr ...

1er

λ α

jj

ii

||λ−−−−α

λ−−−−α ⇒

e poate folosi lema su

Verificaţi-vă pe baza

43

B* ... ur .... xr ...

1er

0 ( )/ ααλ−λ

ji

ij

i

0

|

1

α

|

αλ

−λ−−−−

α−−−−

bstituţiei pentru a arăta că un sistem de

manualului [1] pag.95.

Page 48: matematici aplicate

Exemplul 5. Vom verifica faptul că sistemul de vectori ( )321 vvvSrrr

,,= ⊂ 3 unde

=1vr (2,3,-1), ),,(),,,( 211v101v 32 −==

rr este o bază în 3 şi vom determina coordonatele vectorului v

r =(4, 3, 0) în baza S. Construim tabelele următoare

Deoarece B3 este bază în 3, rezultă că sistemul S este bază în 3 şi că

321 vv3vvrrrr

−+= , adică 1, 3, -1 sunt coordonatele lui vr în baza S.

Exerciţiul 6. Rezolvaţi problema din Exemplul 5 pornind în primul tablou de la

pivotul din locul (3,2) şi utilizând indicaţiile din [1] pag.96, Remarca 3.

Exemplul 6. Vom stabili că sistemul de vectori 4321 vvvvSrrrr

,,,= ⊂ 4 unde =1vr

=(2,3,-1,0), ),,,(),,,,(),,,,( 0176v1211v1101v 432 −=−−=−=rrr este liniar dependent şi

vom determina o relaţie de dependenţă liniară între vectorii sistemului.

Bc 1vr 2v

r 3vr 4v

r

1er 2 1 1 6

2er 3 0 -1 7

3er -1 1 2 -1

4er 0 -1 -1 0

B2 1vr 2v

r 3vr 4v

r

1er 2 0 0 6

2er 2 0 0 6

3vr -1 0 1 -1

2vr 1 1 0 1

Bc 1vr 2vr 3vr vr

1er

2 1 1 4

2er

2 0 -1 3

3er -1 1 2 0

B2 1vr 2vr 3vr vr

2vr 5 1 0 8

2er

-1 0 0 -1

3vr -3 0 1 -4

B1 1vr 2vr 3vr vr

2vr 2 1 1 4

2er

2 0 -1 3

3er -3 0 1 -4

B3 1vr 2vr 3vr vr

2vr 0 1 0 3

1vr 1 0 0 1

3vr 0 0 1 -1

Sistemul nu este independent deoarece

coloană rezultă 3214 vvv3v −+=rrr , adic

dependenţă liniară între vectorii sistem

B1 1vr

2vr

3vr 4v

r

1er 2 0 0 6

2er 3 0 -1 7

3er -1 0 1 -1

2vr 0 1 1 0

B3 1vr

2vr

3vr 4v

r

1er 0 0 0 0

1vr 1 0 0 3

3vr 0 0 1 -1

2vr 0 1 0 1

4vr nu poate fi introdus în bază. Din ultima

ă 0vvv 4321 =−−+v3rrr este o relaţie de

44ului.

Page 49: matematici aplicate

Exerciţiul 7. Arătaţi că între vectorii sistemului 4321 vvvvSrrrr

,,,= ⊂ 5 unde =1vr

=(2,3,-1,0,2), ),,,,(),,,,,(),,,,,( 02792v20121v11211v 432 −−−=−−=−−−=rrr există o relaţie

de dependenţă liniară. Care este numărul maxim de vectori liniar independenţi

din sistem?

Teorema 3 (a bazei). Dacă V are o bază B = e,...,e,e n21rrr atunci

1°. orice sistem liniar independent din V are cel mult n vectori,

2°. orice bază a lui V are n vectori.

Definiţie 5. Spunem că spaţiul vectorial V peste câmpul K are dimensiunea n

peste K şi scriem n = dimKV dacă în V există o bază formată din n vectori.

Din Exerciţiul 3 rezultă că dim n = n.

Tot pe baza lemei substituţiei se stabileşte rezultatul :

Teorema 4. Fie V un spaţiu vectorial de dimensiune n peste câmpul K. Pentru

orice sistem de n vectori S = v,...,v,v n21 următoarele afirmaţii sunt echivalente : rrr

1°. S este bază pentru V,

2°. S este un sistem de generatori pentru V,

3°. S este un sistem liniar independent .

Exerciţiul 8. Folosind Teorema 5, verificaţi că sistemul de vectori 321 vvvSrrr

,,=

⊂ 3 unde =1vr (1,2,-1), ),,(),,,( 302v130v 32 −==

rr este o bază în 3.

§2. Subspaţii vectoriale

1. Definiţii. Exemple Fie V un spaţiu vectorial peste câmpul K.

Definiţia 6. O submulţime nevidă L V se numeşte subspaţiu vectorial al lui V

dacă operaţiile din V induc pe L o structură de spaţiu vectorial.

Propoziţia 1. Submulţimea nevidă L a spaţiului vectorial V este subspaţiu

vectorial dacă şi numai dacă :

1°. y∀ LyxL,x ∈+⇒∈rrrr

2°. ∀ LxLx,K ∈⋅α⇒∈∀∈αrr .

2. Rangul unui sistem de vectori Fie S = v,...,v,v m21

rrr un sistem de vectori din spaţiul vectorial real V.

Considerăm mulţimea notată L( m21 v,...,v,v rrr ) definită prin : 45

Page 50: matematici aplicate

K,...,,,v...vvv|Vv)v,...,v,v(L m21mm2211m21 ∈µµµµ++µ+µ=∈=rrrrrrrr .

L( v,v v,..., m21rrr ) este subspaţiu vectorial al lui V şi se numeşte subspaţiul

liniar generat de sistemul de vectori S.

Definiţia 7. Se numeşte rangul sistemului de vectori S = v,...,v,v m21rrr numărul

notat rang S egal prin definiţie cu dimK L( v,...,v,v m21rrr ).

Se vede că rangul sistemului de vectori S este egal cu numărul maxim de

vectori liniar independenţi din sistem.

Exemplul 8. Să determinăm rangul sistemului de vectori ⊂= ,,, 4321 vvvvSrr 4,

unde 1vr =(1, 2, -3, -5), 2v

r =(-1, 0, 2, 7), 3vr =(1, 4, - 4, -3), 4v

r =(-1, 2, 1, 9). Construim tabelele Bc 1v

r2vr 3v

r 4vr

1er 1 -1 1 -1

2er 2 0 4 2

3er -3 2 -4 1

4er -5 7 -3 9

Rezurezul

B2 1vr

2vr 3v

r 4vr

2vr 0 1 1 2

2er 0 0 0 0

1vr 1 0 2 1

4er 0 0 0 0

3. Rangul unei matrice

Fiecărei matrice A = [ ]ija m×n îi asocie

⋅⋅⋅

a

aa

= C

m1

12

11

A1 , = CA

2

pe care îi identificăm cu elemente din

[ ]n11211A1 aaa = L .... , [ 21

A2 a =L

pe care îi identificăm în mod natural c

B1 1vr

2vr 3v

r 4vr

2vr -1 1 -1 1

2er 2 0 4 2

3er

-1 0 -2 -1

4er 2 0 4 2

ltă că rang S=2. În plus, din ultimul tabel tă că 214213 v2vvvv2v

rrrrrr+=+= , .

m vectorii coloană

,... , C

⋅⋅⋅

a

aa

2m

22

21

⋅⋅⋅

a

aa

=

mn

n2

1n

An

m şi vectorii linie

],...,n222 aa ... [ ]mn2m1mAm aaa=L ...

u elemente din n.

46

Page 51: matematici aplicate

Teorema 5 (Kronecker). Pentru orice matrice A nmM ×∈ ( ) au loc egalităţile

rang = rang = rang A . C,...,C,C nA

2A

1A A

mA2

A1 L,...,L,L

Teorema lui Kronecker permite să calculăm rangul unei matrice cu

ajutorul lemei substituţiei şi anume: este suficient să calculăm, , rangul sistemului

de vectori coloană (linie).

Exemplul 9. Vom determina rangul matricei .

Vom utiliza sistemul de vectori linie. Se obţin tabelele:

=

25446

13223

22202

11021

A

Bc A1C A

2C A3C A

4C A5C

1er 1 2 0 1 -1

2er 2 0 2 2 2

3er 3 2 2 3 1

4er 6 4 4 5 2

B2 A1C A

2C A3C A

4C A5C

1er 0 0 0 0 0

A3C 0 -2 1 0 2 A4C 1 2 0 1 -1

4er 1 2 0 0 -1

Pe baza ultimului tabel putem spune că ran

Ca exerciţiu vă propunem să determinaţi ra

vectori linie.

4. Inversarea matricelor

Pentru orice matrice pătratică inver

vectori coloană este ba C,...,C,C nA

2A

1A

inversă A-1 = [ ] nij M∈

CjIn

b ( ), elementele bi

coordonatele vectorului în baza C,C1A

Procedeul practic care decurge de

primul tabel care conţine atât vectorii sistem

vectorii coloană ai matricei unitate de ordinu

47

elementele bazei iniţiale cu vectorii sistemu

lema substituţiei).

B1 A1C A

2C A3C A

4C A5C

1er 1 2 0 1 -1

A3C 1 0 1 1 1

3er 1 2 0 1 -1

4er 2 4 0 1 -2

g

ng

sa

zj (

2

ai

u

l n

lu

B3 A1C A

2C A3C A

4C A5C

1er 0 0 0 0 0

A3C 0 -2 1 0 2 A4C 0 0 0 1 0 A1C 1 2 0 0 -1

A =3.

ul matricei A folosind sistemul de

bilă A = [ ] nij Ma ∈ ( ) sistemul de

ă în n. În plus, pentru matricea i =1, 2,…, n) ale coloanei j sunt

⊂C,..., nAA n.

ci este următorul : se construieşte

lui ⊂C,...,C,C nA

2A

1A n cât şi

după care se înlocuiesc pe rând,

i ⊂C,...,C,C nA

2A

1A n (utilizând

Page 52: matematici aplicate

Exemplul 10. Vom determina inversa matricei . Construim

tabelele:

−=

1232

1143

2311

1211

A

Bc C1A C2

A C3A C4

A 4I1C 4

I2C 4

I3C 4

I4C

e1 1 1 2 1 1 0 0 0 e2 -1 1 3 2 0 1 0 0 e3 3 4 1 1 0 0 1 0 e4 2 3 2 -1 0 0 0 1

B1 C1A C2

A C3A C4

A 4I1C 4

I2C 4

I3C 4

I4C

e1 -2 -3 1 0 1 0 -1 0 e2 -7 -7 1 0 0 1 -2 0

C4A 3 4 1 1 0 0 1 0

e4 5 7 3 0 0 0 1 1

B2 C1A C2

A C3A C4

A 4I1C 4

I2C 4

I3C 4

I4C

C3A

-2 -3 1 0 1 0 -1 0 e2 -5 -4 0 0 -1 1 -1 0

C4A 5 7 0 1 -1 0 2 0

e4 11 16 0 0 -3 0 4 1

B3 C1A C2

A C3A C4

A 4I1C 4

I2C 4

I3C 4

I4C

C3A

7/4 0 1 0 7/4 -3/4 -1/4 0 C2

A 5/4 1 0 0 1/4 -1/4 1/4 0 C4

A -15/4 0 0 1 -11/4 7/4 1/4 0 e4 -9 0 0 0 -7 4 0 1

B4 C1A C2

A C3A C4

A 4I1C 4

I2C 4

I3C 4

I4C

C3A

0 0 1 0 7/18 1/36 -1/4 7/36 C2

A 0 1 0 0 -13/18 11/36 1/4 5/36 C4

A 0 0 0 1 1/6 1/12 1/4 -5/12 C1

A 1 0 0 0 7/9 -4/9 0 -1/9

Din ultimul tabel rezultă

48

Page 53: matematici aplicate

−−

=−

125

41

121

61

367

41

361

187

365

41

3611

1813

91

94

97

1

0

A .

Exerciţiul 9. Determinaţi inversa matricei .

=

3122

4131

1213

1112

A

5. Calculul determinanţilor

Dacă dorim să calculăm valoarea determinantului ∆ al matricei pătratice

A = [ ]ija ∈Mn(ú) construim tabelul

după care, utilizând lema substituţiei,

vom înlocui numărul maxim posibil de

vectori ai bazei canonice cu coloane ale

matricei A; dacă acest număr este mai

mic decât n, unele coloane ale matricei A

vor fi combinaţii liniare ale celorlalte

Bc C C ... C

e1

e2

.

en

a11 a12 ... a1n

a21 a22 ... a2n

........…….........

an1 an2 ... ann

A1

A2

An

coloane şi deci ∆ = det A = 0. În cazul în care toţi vectorii bazei canonice se

înlocuiesc cu coloanele matricei A, înseamnă că am trecut de la matricea dată fie

la matricea unitate fie la o matrice obţinută din aceasta printr-o permutare a

coloanelor. Valoarea determinantului va fi ∆ = α1 α2 ... αn (-1)s unde s este

numărul de schimbări de coloane necesare pentru a transforma matricea finală în

matricea unitate.

De exemplu, determinantul matricei A din Exemplul 11 este

Det A = 1.1.(-4).(-9).(-1)4 = 36.

6. Rezolvarea sistemelor de ecuaţii liniare

Fie (S) un sistem de m ecuaţii cu necunoscutele x1, x2,..., xn :

(S)

=+++

=+++=+++

mnmn22m11m

2nn2222121

1nn1212111

bxa...xaxa.................................................

bxa...xaxabxa...xaxa

49

Page 54: matematici aplicate

unde aij, bi ∈ , 1 ≤ i ≤ m, 1 ≤ j ≤ n, iar xj∈ , 1 ≤ j ≤ n sunt numere reale

necunoscute . Folosind notaţiile

A=[aij] ∈Mm×n( ), b ,

=

m

2

1

b..bb

=

n

2

1

x

x

x

X..

sistemul (S) se poate pune sub forma

(S’) A·X = b .

Prin utilizarea coloanelor matricei A sistemul (S) capătă forma

(S“) C . bxC...xCx nAn2

A21

A1 =+++

Exerciţiul 10. Definiţi noţiunea de soluţie a unui sistem liniar. Ce semnificaţie

are această noţiune pentru fiecare din cele trei tipuri de forme de prezentare a

unui sistem liniar? Ce interpretare are noţiunea de soluţie a sistemului (S”)?

Pentru verificare comparaţi cu [1] pag. 109.

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

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

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

Exemplul 11. Folosind interpretarea din Exerciţiul 14 vom rezolva sistemul

=+++=+++=+++

=−−+−=−++

1x2xx2x3

1x3x2xx2

5x4x3x2x

0xxxx

6xxxx

4321

4321

4321

4321

4321

.

Construim tablourile

Bc C1A C2

A C3A C4

A b e1 1 1 1 -1 -6 e2 1 1 -1 -1 0 e3 1 2 3 4 5 e4 2 1 2 3 1 e5 3 2 1 2 1 e1 0 0 2 0 -6

C1A 1 1 -1 -1 0

e3 0 1 4 5 5 e4 0 -1 4 5 1 e5 0 -1 4 5 1 e1 0 0 2 0 -6

50

Page 55: matematici aplicate

C1A 1 0 -5 -6 -5

C2A 0 1 4 5 5

e4 0 0 8 10 6 e5 0 0 8 10 6

C3A 0 0 1 0 -3

C1A 1 0 0 -6 -20

C2A 0 1 0 5 17

e4 0 0 0 10 30 e5 0 0 0 10 30

C3A 0 1 1 0 -3

C1A 1 0 0 0 -2

C2A 0 0 0 0 2

C4A 0 0 0 1 3

e5 0 0 0 0 0 Deoarece , rezultă că xA

4A3

A1

A1 C3C3C2C2b +−+−= 1=-2, x2=2, x3=3, x4=3 este

unica soluţie a sistemului (sistemul de vectori coloane este bază într-un

subspaţiu ce conţine pe b, deci b se exprimă în mod unic ca o combinaţie

liniară a elementelor bazei).

Exerciţiul 11. Scrieţi sistemul din Exemplul precedent sub formele (S’) şi (S”).

Verificaţi apoi că (-2, 2, -3, 3) este soluţie pentru sistemul prezentat sub cele

trei forme.

Exerciţiul 12. Definiţi noţiunile:

sistem compatibil..................................................................................................

sistem incompatibil...............................................................................................

sistem compatibil determinat................................................................................

sistem compatibil nedeterminat.............................................................................

Exerciţiul 13. Enunţaţi teorema Kronecker-Capelli şi teorema Rouché-Frobenius.

Exemplul 12. Vom determina soluţia generală a sistemului

=−−+++=+−+++

=++++=+−+++

−=−−+

1xx8x4x4x7x10

12xxx3x3x4x5

23x2x6x2x2x

5xx2x2x2x3x4

9xx4xx2

654321

654321

65432

654321

6521

Construim tabelele

Bc C1A C2

A C3A C4

A C5A C6

A b e1 2 1 0 0 -4 -1 -9 e2 4 3 2 2 -2 1 5 e3 0 1 2 2 6 2 23

51

Page 56: matematici aplicate

e4 5 4 3 3 -1 2 12 e5 10 7 4 4 -8 -1 1

C2A 2 1 0 0 -4 -1 -9

e2 -2 0 2 2 10 4 32 e3 -2 0 2 2 10 4 32 e4 -3 0 3 3 15 6 48 e5 -4 0 4 4 20 6 64

C2A 2 1 0 0 -4 -1 -9

C3A -1 0 1 1 5 2 16

e3 0 0 0 0 0 0 0 e4 0 0 0 0 0 0 0 e5 0 0 0 0 0 0 0

Rezultă egalităţile

A3

A2

A3

A2

A6

A3

A2

A5

A3

A4

A3

A2

A1

C16C9b

C2CC

C5C4C

CC

CC2C

+−=

+−=

+−=

=

−=

⇒ X .

),,,,,(),,,,,(),,,,,(),,,,,(),,,,,(

0001690X

100210X

010540

001100X

000121X

p

4

3

2

1

−=−=−=−=

−=

Soluţia generală este X=Xp+k1X1+k2X2+k3X3+k4X4 ∀ k1, k2, k3, k4∈ , adică

46244312

354321311kxkxkk4k29x

kxk2k5kk16xkx

=−=++−−==−−++==

.

Xp este soluţie de bază nedegenerată. (De ce?) Reamintim că sistemul omogen asociat sistemului nostru este

=−−+++=+−+++

=++++=+−+++

−=−−+

1xx8x4x4x7x10

12xxx3x3x4x5

23x2x6x2x2x

5xx2x2x2x3x4

9xx4xx2

654321

654321

65432

654321

6521

;

soluţia generală a lui este X=k1X1+k2X2+k3X3+k4X4 ∀ k1, k2, k3, k4∈ , adică

46244312

354321311kxkxkk4k2x

kxk2k5kkxkx

=−=++−==−−+==

.

În exemplul următor prezentăm un sistem incompatibil.

Exerciţiul 14. Arătaţi că sistemul

=+−++−=+++−

=+−+−=++−

=+−+−

6x4x7x3xx2

3xxx3x7

1x3x3x3x

3x2xxx

4xx4x3x2x

54321

5432

5421

5432

54321

este incompatibil.

52

Page 57: matematici aplicate

Capitolul IV

ELEMENTE DE PROGRAMARE LINIARĂ

Programarea liniară este acea ramură a programării matematice care se

ocupă de rezolvarea problemelor de programare pentru care atât funcţia obiectiv

cât şi restricţiile sunt funcţii liniare. Forma matematică generală a problemelor

de programare liniară, în forma în care este şi astăzi acceptată, a fost propusă

de G. Dantzig în 1947 care a propus şi un procedeu eficient de rezolvare –

metoda simplex.

§1. Metoda simplex de rezolvare a problemelor de

programare liniară Ne vom ocupa numai de o anumită problemă simplificată dar a cărei rezol-

vare se generalizează şi se poate aplica în multe alte cazuri. Este vorba de aşa-

numita problemă standard de programare liniară.

1. Probleme care conduc la programe liniare Vom prezenta mai întâi câteva probleme care vor permite să formulăm proble-

ma generală de programare liniară şi care vor evidenţia şi importanţa rezolvării

unei astfel de probleme.

a) Repartiţia optimă a culturilor agricole O fermă agricolă are suprafaţa arabilă totală S pe care se vor cultiva culturile

A1, A2,..., An. Pe baza datelor statistice se ştie că producţia medie la hectar

pentru cultura Ai este qi t/ha. Cheltuielile de producţie (directe şi comune)

pentru cultura Ai sunt de ci mii lei/ha şi sunt limitate la un total C. Pe baza

acordului cu finanţatorul şi a comenzilor/necesităţilor proprii, fermierul îşi

planifică producţiile Qi pentru culturile Ai (i=1, 2, ..., n). Ştiindu-se că

beneficiul pe tona de produs Ai este bi se cere să se determine suprafeţele x1,

x2, ... , xn ce trebuie cultivate cu culturile A1, A2,..., An astfel încât să se obţină

53

Page 58: matematici aplicate

beneficiu maxim fără a se depăşi totalul de cheltuieli alocate, cu realizarea

producţiei planificate şi cultivarea întregii suprafeţe.

Se obţine modelul matematic următor.

≥≥

≤+++=+++

+++

nnn

222

111

nn2211

n21

nnn222111

Qxq

QxqQxq

Cxcxcxc

Sxxx

xqbxqbxqb

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

......

)...(max

.

b) Problema dietei

Este bine stabilit că menţinerea stării normale a unui individ este condi-

ţionată de prezenţa în hrană a unor anumite principii nutritive

(glucide, lipide, calorii, etc.) în cantităţile şi respectiv b

m21 N,...,N,N

,...b,b 21

nx,...,

m ; cantităţile

se numesc necesaruri biologice şi sunt stabilite de către biologi. Se

ştie că aceste principii nutritive se găsesc în alimentele ; mai exact, se

ştie că într-o unitate din alimentul A

m21 b,...,b,b

n21 A,...,A,A

j se găsesc aij unităţi din principiul nutritiv

Ni . De asemenea se ştie că o unitate din alimentul Ai costă ci unităţi monetare.

Să se determine un meniu (raţie alimentară) care să asigure necesarul biologic la

un preţ minim. Dacă vom nota cu xi ( i =1,2,..,n) cantitatea (încă necunoscută)

din alimentul Ai care trebuie inclusă în meniu (raţie), determinarea meniului

înseamnă determinarea vectorului ( ). 21 x,x

Datele acestei probleme se pun sub forma următorului tabel

A1 A2 … Aj … An Necesar biologic N1 a11 a12 … a1j … a1n b1 N2 a21 a22 … a2j … a2n b2 : : : … : … : :

Ni ai1 ai2 … aij … ain bi : : : … : … : :

Nm am1 am2 … amj … amn bm

Cost unitar c1 c2 … cj … cn

Rezultă că costul total al raţiei alimentare este

(1) . j

n

1jj

tn21 xcXC)x,...,x,x(f ⋅=⋅= ∑

=

Condiţia ca meniul ( x ) să asigure necesarul biologic de bn21 x,...,x, i unităţi din

principiul nutritiv Ni este

54

Page 59: matematici aplicate

i

n

1jjij bxa ≥∑

=

)m,1i( = .

Înseamnă că funcţia obiectiv (1) va fi minimizată în raport cu restricţiile:

(2) i

n

1jjij bxa ≥∑

=

m,1i = .

În plus, aşa cum este firesc, trebuie satisfăcute condiţiile de nenegativitate

(3) 0x j ≥ n,1j = .

Suntem conduşi la problema

(P.L.I)

=≥

=≥∑=

n,...2,1i,0x

. m,..2,1ibxa

CXmin

i

n

1jijij

t

Problemele practice descrise mai sus, conduc la următoarea problemă

matematică, problemă care face obiectul programării liniare.

Fie [A = o matrice reală, ... şi ... -

vectori coloană cunoscuţi iar ... vectorul coloană al necunoscutelor.

Se pune problema să se determine maximul funcţiei obiectiv

mxnij ]a 1t c[C =

]xn

2c ]cn 1t b[b= 2b ]bm

1t x[X= 2x

tCX în raport cu

restricţiile:

(4) AX = b

(5) 0X ≥

(aici este o notaţie prescurtată pentru condiţiile x 0X ≥ 0j ≥ n,1j = ).

Suntem deci interesaţi să rezolvăm problema

(P.L.S.)

=≥

==∑=

n21i0x

. m21ibxa

CX

i

n

1jijij

t

,...,,

,..,

max

Această problemă se numeşte program liniar standard .

55

Page 60: matematici aplicate

2. Descrierea algoritmului simplex Se presupune că , că există o bază admisibilă B şi că este

soluţia admisibilă de bază corespunzătoare. Fără a restrânge generalitatea vom

presupune că B = a şi că X

rm =

2 ,......,a

0X

m1 a, 0=[x10, x20, ... ,xm0, 0,...,0]. Fie

jkλ ( )n,1k;m,1j == coordonatele vectorilor a în baza k m21 aa,a ,......,B = ;

se calculează cantităţile TCXo şi şi se comple-

tează tabelul 1.

n,...,2,1k,ck

m

1iik =⋅λ=∑

=

ci −dk

Tabelul 1 BC jC → 1c 2c . . . mc 1mc + . . . jc . . . nc

↓ B 0X 1a 2a . . . ma 1ma + . . . ja . . . na

1c 1a 10x 1 0 . . . 0 1m,1 +λ . . . j,1λ . . . n,1λ 2c 2a 20x 0 1 . . . 0 1m,2 +λ . . . j,2λ . . . n,2λ . . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

ic ia 0ix 0 0 . . . 0 1m,i +λ . . . j,iλ . . . n,iλ

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

mc ma 0mx 0 0 1 1m,m +λ . . . j,mλ . . . n,mλ T

0CX 0 0 . . . 0 1md + . . . jd . . . nd

După completarea Tabelului 1 se testează optimalitatea soluţiei cu ajutorul

Teoremei 4. Dacă răspunsul este afirmativ, adică toţi dk ≥0, problema poate fi

considerată rezolvată (deoarece s-a găsit o soluţie optimă şi în general nu se

urmăreşte obţinerea tuturor soluţiilor optime, ci numai a uneia dintre ele).

În caz contrar, adică dacă există j astfel încât 0d j < , soluţia iniţială X0

nu este optimă.

Există două posibilităţi :

1.Dacă există un indice j pentru care cantitatea este strict negativă şi toţi

jd

0.ij ≤λ ( )m,1i = atunci programul liniar nu are optim finit şi determinarea lui nu

mai interesează din punct de vedere matematic.

2. În caz contrar cazului 1 soluţia se poate îmbunătăţi. Se iniţiază prima iterată

a algoritmului simplex. Aceasta revine la determinarea vectorilor şi care

intră şi respectiv ies din bază.

ja ia

56

Page 61: matematici aplicate

Vectorul ja (cel care intră în bază) se corespunde cantităţii de

valoare negativă minimă:

jd

0d|dmind iij <= .

Vectorul a , care intră în bază, se determină corespunzător indicelui

pentru care

i

kj

0k

0ij

0i xxλ

minkj>λ

,

Odată stabiliţi cei doi vectori, se recalculează elementele Tabelului 1

construind un tabel de acelaşi tip corespunzător noii baze, adică vor fi

calculate, pe baza lemei substituţiei, coordonatele vectorilor coloană în baza

obţinută înlocuind ai cu aj .

După completarea noului tabel cu cantităţile n,..,2,1k,dk = , se testează

optimalitatea noii soluţii. Dacă noua soluţie este optimă algoritmul se opreşte.

Dacă nu, se începe o nouă iteraţie.

În cazul în care testul de optimalitate dă răspuns afirmativ, ultimul tabel

simplex conţine soluţia programului liniar. Componentele din coloana sunt

chiar componentele bazice ale soluţiei optime (celelalte sunt nule), iar

reprezintă valoarea optimă a funcţiei obiectiv.

0X

t C 0X⋅

Ţinând cont de egalitatea min f(x) = - max [-f(x)], se pot rezolva şi

probleme de minimizare.

Exemplul 1. Să se determine soluţia optimă a programului liniar

≥≥≥≥≥

=+++−=−−+−≤−+−

−++−

0x0x0x0x0x

4xxx3xx2

12x3x2x4x3

5x3xx2x2

x3x2x3x

54321

54321

4321

4321

5321

,,,,

)(min

.

Ţinând cont că min (-x1+3x2+2x3-3x5)= -max (x1-3x2-2x3+3x5) şi de faptul că este

indicat ca toţi termenii liberi să fie nenegativi trecem la rezolvarea problemei

≥≥≥≥≥

=+++−=−−+≥+−+−

+−−

0x0x0x0x0x

4xxx3xx2

12x3x2x4x3

5x3xx2x2

x3x2x3x

54321

54321

4321

4321

5321

,,,,

)(max

.

Pentru a obţine un program liniar standard transformăm prima restricţie în ega-

litate folosind variabila de compensare (de ecart) y. Rezultă

57

Page 62: matematici aplicate

≥≥≥≥≥≥

=+++−=−−+

=−+−+−

+−−

0y0x0x0x0x0x

4xxx3xx2

12x3x2x4x3

5yx3xx2x2

x3x2x3x

54321

54321

4321

4321

5321

,,,,,

)(max

.

Matricea sistemului de restricţii conţine numai coloana a treia a matricei unitate

de ordinul 3 deci nu putem obţine o bază admisibilă şi soluţia admisibilă de

bază corespunzătoare (în caz că există). Apelăm la metoda celor două faze

(vezi [1] pag. 147) dar vom introduce atâtea variabile artificiale cât va fi

suficient să putem găsi uşor o bază admisibilă. Vom construi programul

ajutător

≥≥≥≥≥≥≥≥

=+++−=+−−+

=+−+−+−

−−−=+

0z0z0y0x0x0x0x0x

4xxx3xx2

12zx3x2x4x3

5zyx3xx2x2

zzzz

2154321

54321

24321

14321

2121

,,,,,,,

)(max)(min

.

Matricea sistemului de restricţii este

87654321 aaaaaaaa

00011312

10003243

01103122

A

−−−

−−−=

.

Se constată că baza B=(a7, a8, a5) este bază admisibilă pentru care X0=(0, 0, 0,

0, 4, 0, 5, 12) este soluţia admisibilă de bază corespunzătoare. Coordonatele

coloanelor matricei A în baza B sunt chiar componentele lor deoarece B este

chiar baza canonică din 3. Deoarece rangul matricei A este egal cu numărul de

restricţii construim tabelele

cB cj → 0 0 0 0 0 0 -1 -1 ↓ B X0 a1 ⇓a2 a3 a4 a5 a6 a7 a8 -1 ↵a7 5 -2 2 -1 3 0 -1 1 0 -1 a8 12 3 4 -2 -3 0 0 0 1 0 a5 4 2 -1 3 1 1 0 0 0 -17 -1 -6 3 0 0 1 0 0

0 a2 5/2 -1 1 -1/2 3/2 0 -1/2 1/2 0 -1 ↵a8 2 ⇓ 7 0 0 3 0 2 -1/2 1 0 a5 13/2 1 0 5/2 5/2 1 -1/2 1/2 0 -2 -7 0 0 -3 0 -1 1/2 0

0 a2 39/14 0 1 -1/2 27/7 0 -3/14 6/7 0 a2 2/7 1 0 0 3/7 0 2/7 -1/14 1/7 0 a5 87/14 0 0 5/2 29/14 1 -1/14 13/28

58

Page 63: matematici aplicate

0 0 0 0 0 0 0 1 1

Faza II cB cj → 2 3 1 -2 0 0 ↓ B X0 a1 a2 ⇓a3 a4 a5 ⇓a6 3 a2 39/14 0 1 -1/2 3/14 0 -3/14 2 a1 2/7 1 0 0 -9/7 0 2/7 0 ↵a5 87/14 0 0 5/2 53/14 1 -11/14

125/7 0 0 -5/2 1/14 0 -1/14 3 a2 141/35 0 1 0 34/35 1/5 -26/70 2 ↵a1 2/7 1 0 0 -9/7 0 2/7 1 a3 87/35 0 0 1 53/35 2/5 -11/35 104/35 0 0 0 12/35 1 -6/7

3 a2 22/5 13/10 1 0 -3/7 1/5 0 0 a6 1 7/2 0 0 -9/2 0 1 1 a3 98/35 11/10 0 1 1/10 2/5 0 16 3 0 0 57/70 1 0

Din ultimul tabel rezultă că valoarea optimă este –16 iar soluţia optimă este

Xopt=(0, 3, 98/35, 0, 0).

Exemplul 2. Vom rezolva problema dietei corespunzătoare tabelului următor

F1 F2 Necesar biologic (bi) N1 0,1 0,2 0,4 N2 0,3 0,1 0,6 N3 0,1 0,4 0,8 N4 0,2 0,1 1,2

Costuri unitare cj 1,4 1,8

Modelul matematic corespunzător este

≥≥

≥+≥+≥+≥+

+

0x0x

21x10x20

80x40x10

60x10x30

40x20x10

x81x41

21

21

21

21

21

21

,,,,,,,,,,,,,),,(min

.

Trecem la problema echivalentă

≥≥

≥+≥+≥+≥+

+=+

0x0x

12xx2

8xx

6xx3

4x2x

x9x72x18x14

21

21

21

21

21

2121

,

)min()(min

.

Utilizând variabile de compensare (ecart) îi asociem în mod obişnuit programul

liniar standard

59

Page 64: matematici aplicate

≥≥≥≥≥≥

=−+=−+=−+=−+

−−

0u0u0u0u0x0x

12uxx2

8uxx

6uxx3

4ux2x

x9x7

432121

421

321

221

121

21

,,,,,

)max(

.

Matricea sistemului de restricţii nu conţine coloanele matricei unitate de ordinul 4, deci vom folosi metoda celor două faze. Programul liniar standard asociat este:

≥≥≥≥≥≥≥≥≥≥

=+−+=+−+=+−+=+−+

−−−−−=+++

0v0v0v0v0u0u0u0u0x0x

12vuxx2

8vuxx

6vuxx3

4vux2x

vvvvvvvv

4321432121

4421

3321

2221

1121

43214321

,,,,,,,,,

)max()min(

.

Matricea sistemului de restricţii are 10 coloane pentru care B=(a7, a8, a9, a10)

este bază admisibilă a cărei soluţii admisibile de bază corespunzătoare este

X0=(0, 0, 0, 0, 0, 0, 4, 6, 8, 12). Deoarece baza B este baza canonică din 4

coloanele matricei sistemului de restricţii se exprimă în mod evident sub formă

de combinaţii liniare ale bazei B.

Faza I cB cj → 0 0 0 0 0 0 -1 -1 -1 -1 ↓ B X0 ⇓a1 ⇓a2 ⇓a3 ⇓a4 a5 a6 a7 a8 a9 a10 -1 ↵a7 4 1 2 -1 0 0 0 1 0 0 0 -1 a8 6 3 1 0 -1 0 0 0 1 0 0 -1 a9 9 1 4 0 0 -1 0 0 0 1 0 -1 a10 12 2 1 0 0 0 -1 0 0 0 1 -31 -7 -8 1 1 1 1 0 0 0 0

0 a2 2 ½ 1 -½ 0 0 0 ½ 0 0 0 -1 a8 4 5/2 0 ½ -1 0 0 -½ 1 0 0 -1 ↵a9 1 -1 0 2 0 -1 0 -2 0 1 0 -1 a10 10 3/2 0 ½ 0 0 -1 -½ 0 0 1 -15 -3 0 -3 1 1 1 4 0 0 0

0 a2 9/4 1/4 1 0 0 -1/4 0 0 0 1/4 0 -1 ↵a8 15/4 11/4 0 0 -1 1/4 0 0 1 -1/4 0 0 a3 1/2 -½ 0 1 0 -½ 0 -1 0 ½ 0 -1 a10 39/4 7/4 0 0 0 1/4 -1 0 0 -1/4 1 -27/2 -9/2 0 0 1 -½ 1 1 0 3/2 0

0 a2 21/11 0 1 0 1/11 -3/11 0 0 -1/11 0 0 a1 15/11 1 0 0 -4/11 1/11 0 0 4/11 -1/11 0 0 a3 13/11 0 0 1 -2/11 -5/11 0 -1 2/11 0 -1 ↵a10 81/11 0 0 0 7/11 1/11 -1 0 -7/11 -1/11 1

0 0 0 -7/11 -1/11 1 1 18/11 1/11 0 0 a2 6/7 0 1 0 0 -2/7 1/7 0 0 a1 39/7 1 0 0 0 1/7 -4/7 0 0 a3 23/7 0 0 1 0 -3/7 -2/7 -1 0 a4 81/7 0 0 0 1 1/7 -11/7 0 -1 -1/7 0 0 0 0 0 0 0 1 1 1 1

60

Page 65: matematici aplicate

Trecem la Faza II. Renunţăm la coloanele corespunzătoare necunoscutelor arti-

ficiale dar revenim la costurile iniţiale.

Faza 2

cB cj → -7 -9 0 0 0 0 ↓ B X0 a1 a2 a3 a4 a5 a6 -9 a2 6/7 1 0 0 0 -2/7 1/7 -7 a1 39/7 0 1 0 0 1/7 -4/7 0 a3 23/7 0 0 1 0 -3/7 -2/7 0 a4 81/7 0 0 0 1 1/7 -11/7 327/7 0 0 0 0 11/7 19/7

Prin urmare valoarea optimă este 2/10·327/7 iar soluţia optimă este Xopt=(39/7; 6/7).

Construim acum problema dual-simetrică asociată programului analizat mai sus.

≥≥

≤+++≤++++++

0y0y

9yy4yy2

7y2yy3y

y12y9y6y4

21

4321

4321

4321

,

)(max

.

Folosind variabile de compensare obţinem programul standard

≥≥≥≥≥≥

=++++=++++

+++

0z0z0y0y0y0y

9zyy4yy2

7zy2yy3y

y12y9y6y4

214321

24321

14321

4321

,,,,,

)(max

.

Matricea sistemului de restricţii conţine coloanele matricei unitate de ordinul

doi, deci B=(a5, a6) este bază admisibilă cu soluţia admisibilă de bază X0=(0, 0,

0, 0, 7, 9). Construim tabelele

cB cj → 4 6 9 12 0 0 ↓ B X0 a1 a2 ⇓a3 ⇓a4 a5 a6 0 ↵a5 7 1 3 1 2 1 0 0 a6 9 2 1 4 1 0 1 0 -4 -6 -9 -12 0 0

12 a4 7/2 1/2 3/2 1/2 1 1/2 0 0 a6 11/2 3/2 -1/2 7/2 0 -1/2 1 42 2 12 -3 0 6 0

12 a4 18/7 2/7 11/7 0 1 4/7 -1/7 9 a3 11/7 3/7 -1/7 1 0 -1/7 2/7 327/7 23/7 81/7 0 0 39/7 6/7

Exerciţiul 1. Citiţi din ultima linie a problemei duale soluţia problemei primale

şi din ultima linie a problemei primale soluţia problemei duale. Se verifică sau

nu indicaţiile teoretice din [1] pag. 161-162?

Exemplul 3. Vom pregăti pentru rezolvare programul liniar

61

Page 66: matematici aplicate

−<>

≤−+≥+−++−

oarecarex0x0x

2x3xx2

5x5x2x

xxx2

321

321

321

321

,,

)(min

.

Introducem variabilele nenegative y1, y2, y3 prin y1=-x2, x3=y2-y3. Problema se

transformă în

≥≥>>

≤−−−≥−++

−+−−

0y0y0y0x

2yy3yx2

5y5y5y2x

yyyx2

3211

3211

3211

3211

,,,

)(min

.

Utilizând variabilele de compensare z1 şi z2 se trece la problema

≥≥≥≥>>

=+−−−=−−++

+−+

0z0z0y0y0y0x

2zyy3yx2

5zy5y5y2x

yyyx2

213211

23211

13211

3211

,,,,,

)(max

.

Această problemă se rezolvă utilizând metoda celor două faze (Exerciţiu!).

62

Page 67: matematici aplicate

Capitolul V

ELEMENTE DE TEORIA GRAFURILOR

În numeroase domenii de activitate şi mai ales în cercetare se întâlnesc

scheme care pot fi reprezentate prin puncte şi arce (orientate sau nu) care unesc

aceste puncte. Ca exemple cităm: circuitele electrice în fizică, electronică şi elec-

trotehnică, diagramele moleculare în chimie, reţelele de comunicaţii şi transport,

dendogramele şi reţelele neuronice în biologie, diagramele de organizare în

economie, etc..

La început, teoria grafurilor părea a fi un capitol destul de neînsemnat al

matematicii având de a face mai mult cu jocurile şi amuzamentele matematice.

Apariţia în 1736 a primului memoriu de teoria grafurilor, datorat lui L. Euler, a

atras atenţia asupra importanţei acestui domeniu.

În prezent, pe lângă utilizarea în cercetarea matematică, teoria grafurilor

este intens utilizată în biologie, economie, psihologie, etc..

§1. Grafuri orientate 1. Definiţii. Exemple

Grafurile sunt obiectele matematice obţinute abstractizând figurile geome-

trice formate din linii (curbe simple) care unesc o familie de puncte; dacă aceste

linii sunt toate orientate se vorbeşte de grafuri orientate.

Definiţia 1. a) Un graf orientat G este o pereche G = (X,U) formată dintr-o mulţi-

me nevidă X ale cărei elemente se numesc vârfuri şi o mulţime U de perechi

ordonate de elemente din X ale cărei elemente se numesc arce.

b) Pentru un arc u=(x, y)∈U vârful x se numeşte extremitate iniţială (sau origine)

iar vârful y se numeşte extremitate finală (sau extremitate); se mai spune că

vârfurile x şi y sunt adiacente sau că x şi y sunt incidente arcului u. Un vârf

neincident nici-unui arc se numeşte vârf izolat

c) Dacă u = (x, y) ∈ U se spune că u este incident spre exterior din x şi incident

spre interior lui y; se mai spune că muchia u este adiacentă vârfurilor x şi y.

Page 68: matematici aplicate

Exerciţiul 1. Arătaţi că Definiţia 1 este echivalentă cu Definiţia 1 din [1] pag. 178.

Graful format numai din vârfuri izolate se numeşte graf nul.

Dacă X şi U sunt mulţimi finite, vom spune că graful G este graf finit ;

numărul XcardX = se numeşte ordinul grafului. În cele ce urmează ne vom

ocupa numai de grafuri finite.

Un arc pentru care extremităţile coincid se numeşte buclă. Pentru con-

secvenţa prezentării, vom considera pe orice buclă orientarea dată de sensul direct

trigonometric; de obicei bucla este considerată de două ori (odată cu un sens,

odată cu sensul opus) , dar noi vom folosi convenţia făcută mai înainte .

Fiecărui graf i se poate asocia o imagine geometrică obţinută reprezentând

elementele mulţimii X prin puncte sau cerculeţe mici iar mulţimea arcelor prin

curbe fără autointersecţii orientate (prin săgeţi care indică orientarea de la originea

spre extremitatea fiecărui arc). În reprezentarea grafică se caută ca - atât cât este

posibil - arcele să nu se intersecteze, pentru a nu se confunda intersecţiile arcelor

cu vârfuri ale grafului. Grafurile pentru care este posibil acest lucru se numesc

grafuri planare. Grafurile planare sunt utilizate în proiectarea şi realizarea circui-

telor electronice. Există grafuri care nu sunt planare.

Exemplul 1. Considerăm graful G = (X,U) unde X = x1, x2, x3, x4, x5, x6, x7 şi

U = (x1, x1), (x1 ,x2), (x1 ,x3), (x2 ,x1), (x2 ,x3), (x2 ,x4), (x3 ,x1), (x3 ,x2), (x3 ,x4),

(x5 ,x6). Imaginea geometrică a acestui graf este dată în Fig.1.

X6

X5

X7X4

X1

X2

X3

Fig. 1 Exerciţiul 2. Identificaţi în graful de mai sus vârfurile izolate şi câteva perechi de

vârfuri neadiacente.

Răspuns..........................................................................................................................

Definiţia 2. a) Un graf G’ = (X’, U’) se numeşte subgraf al grafului G = (X,U)

74

Page 69: matematici aplicate

dacă X’⊂X, U’ ⊂ U şi U’ este format numai din arce adiacente la vârfuri din X’.

În cazul particular X’=X se spune că G’ este graf parţial.

b) Graful GA=(A, V) unde A⊂X este o submulţime nevidă de vârfuri iar V este

mulţimea tuturor arcelor din U cu extremităţile în A se numeşte subgraful lui G

generat de A.

c) Graful GV=(A, V) unde V⊂U este o submulţime nevidă de arce iar A este

mulţimea tuturor vârfurilor din X adiacente arcelor din V se numeşte subgraful

lui G generat de V.

Exerciţiul 3. În graful din Exerciţiul 1 identificaţi două grafuri parţiale, subgraful

generat de familiile de vârfuri A1= x1, x2, x3, x4 , A2= x5, x6 , A3= x7,

subgraful generat de familia de arce V= (x2 ,x1), (x2 ,x3), (x3 ,x1), (x3 ,x2), (x5 ,x6).

Definiţia 3. a) Un arc u = (x, y)∈U este incident spre exterior mulţimii (nevide)

de vârfuri A X dacă x A şi y A; vom nota cu (A) mulţimea arcelor

incidente spre exterior mulţimii A.

⊂ ∈ ∉ +ω

b) Un arc u = (x, y) ∈ U este incident spre interior mulţimii nevide de

vârfuri A X dacă x A şi y A; vom nota cu ω⊂ ∉ ∈ -(A) mulţimea arcelor

incidente spre interior mulţimii A.

c) Un arc u = (x, y) ∈ U este incident mulţimii (nevide) de vârfuri A ⊂ X

dacă sau x A sau y ∈ ∈ A dar x, y ⊄ A; mulţimea ω (A) = ω (A) (A)

reprezintă mulţimea arcelor incidente mulţimii A.

+ ∪ −ω

Exerciţiul 4. În graful din Exerciţiul 1 determinaţi (A), ω (A) şi +ω − ω (A) pentru

A= x1, x2, x4, x6.

Răspuns....................................................................................................................................

Definiţia 4. a) Se numeşte lanţ de lungime q în graful orientat G = (X, U) o

succesiune ordonată de q arce ( cu proprietăţile : )u,...,u ii q1

• , k uu ii 1kk +≠ ∀ ∈ 1, 2, ... , q –1,

• pentru orice k (2 k ≤ q-1) , una dintre extremităţile arcului u coincide

cu o extremitate a arcului u , iar cealaltă extremitate coincide cu o extremitate a

arcului .

≤ ik

ik 1-

ui 1+k

75

Page 70: matematici aplicate

b) Extremitatea x a arcului u care nu este extremitate a lui u şi

extremitatea y a arcului u care nu este extremitate pentru u se numesc

extremităţile libere ale lanţului. Vom nota cu L

1i 2i

qi 1qi −

x,y un lanţ pentru care x, y sunt

extremităţile libere; îl vom numi şi x,y-lanţ. c) Un lanţ pentru care extremităţile

libere coincid se numeşte ciclu.

Este de remarcat faptul că prima condiţie din Definiţia 7 asigură că într-un

lanţ nu se vor folosi arce care să fie parcurse consecutiv o dată într-un sens şi o

dată în sens contrar .

Definiţia 5.a) Un lanţ se numeşte simplu dacă la parcurgerea sa fiecare arc

este întâlnit o singură dată. b) Un lanţ se numeşte elementar dacă la parcurgerea

sa fiecare vârf este întâlnit o singură dată. c) Un ciclu elementar care conţine toate

vârfurile grafului se numeşte ciclu hamiltonian. d) Un ciclu care foloseşte toate

arcele grafului se numeşte ciclu eulerian.

Definiţia 6. Un lanţ se numeşte drum dacă pentru orice k, 2

k q, extremitatea iniţială a lui coincide cu extremitatea finală a arcului u ;

dacă x şi y sunt extremităţile libere ale drumului, atunci spunem că avem un x,y-

drum şi-l notăm generic cu D

)u,...,u( ii q1

uik

1-≤ ik

x,y . Un drum pentru care extremităţile libere coincid

se numeşte circuit. Drumul Dx,y este simplu sau elementar după cum lanţul

corespunzător este simplu sau elementar. Un drum este hamiltonian sau eulerian

după cum lanţul corespunzător este hamiltonian sau eulerian.

Exemplul 2. Considerăm graful reprezentat în Fig.2.

Lanţul =L (u2, u14, u11, u12,

81xx

u13, u14, u9) este de lungime 7,

are extremităţile libere x1 şi x8

şi foloseşte arcul u14 de două

ori, deci, implicit, foloseşte

vârfurile x4 şi x7 de câte două

ori; în consecinţă, acest lanţ nu

este nici simplu nici elementar. Fig. 2

76

Page 71: matematici aplicate

Lanţul (u=64

xxL 14, u9, u10, u11, u7) este simplu dar nu este elementar pentru că

foloseşte de două ori vârful x7

Un exemplu de lanţ şi simplu şi elementar este lanţul =64

xxL (u14, u9, u8, u6).

Lanţul (u=81

xxL 2, u14, u11, u10) este drum simplu şi elementar pentru că,

începând cu arcul al doilea, originea unui arc este extremitate pentru arcul

precedent. Ca exemplu de ciclu evidenţiem lanţul (u14, u11, u12, u13), iar ca

exemplu de circuit evidenţiem drumul (u6, u8, u9, u5).

Exerciţiul 5. Evidenţiaţi în graful din Fig.2 un lanţ/drum simplu, un lanţ/drum

simplu care nu este elementar, un lanţ/drum care nu este simplu, un ciclu şi un

circuit.

Răspunsuri……………………………………………………………………………

……………………………………………………………………………………

…………...……………………………………………………………………….

Definiţia 7. a) Un graf orientat G = (X, U) se numeşte conex dacă pentru orice

două vârfuri distincte x,y X , există un x,y-lanţ. Orice subgraf conex

maximal al unui graf orientat G = (X, U) se numeşte componentă conexă a

grafului G; se acceptă că vârfurile izolate (neadiacente altor vârfuri) formează

componente conexe.

b) Un graf orientat G = (X, U) se numeşte tare-conex dacă pentru orice două

vârfuri distincte x,y ∈ X , există un x,y-drum .

Definiţia 8. a) Un graf conex, fără cicluri, care are cel puţin două vârfuri se

numeşte arbore. b) Un graf ale cărui componente conexe sunt arbori se numeşte

pădure. c) Un arbore care este graf parţial se numeşte arbore parţial.

Are loc următoarea teoremă de caracterizare a arborilor .

Teorema 1. Fie G = (X, U) un graf finit care are cel puţin două vârfuri şi n =

card X = X ≥2 . Următoarele proprietăţi sunt echivalente:

1°. G este arbore,

2°. G este fără cicluri şi are n-1 arce,

3°. G este conex şi are n-1 arce,

4°. oricare două vârfuri sunt unite printr-un lanţ şi numai unul.

77

Page 72: matematici aplicate

Această teoremă dă posibilitatea să verificăm uşor dacă un graf este sau

nu un arbore.

Teorema 2. Un graf conţine un arbore parţial dacă şi numai dacă este conex.

Definiţia 9. Vârful a X se numeşte rădăcină a grafului G = (X, U) dacă pentru

orice x X (a ≠x) există un drum de la a la x (adică orice vârf diferit de a este

accesibil din a în lungul unui drum).

Definiţia 10. Graful G = (X, U) se numeşte cvasi-tare-conex dacă pentru orice

două vârfuri x,y X, x y, există un vârf z ∈ ≠ ∈ X astfel încât x şi y sunt

accesibile dealungul unor drumuri ce pleacă din z .

Remarca 1. Orice graf cvasi-tare-conex este conex; reciproca nu este adevărată.

Definiţia 11. Orice arbore care are o singură rădăcină se numeşte arborescenţă.

Este nevoie să recunoaştem uşor dacă un graf este sau nu o arborescenţă.

În acest scop prezentăm următorul rezultat.

Teorema 3. Fie G = (X, U) un graf orientat finit care are cel puţin două vârfuri şi

n = card X = | . Următoarele proprietăţi sunt echivalente: |X

1°. G este arborescenţă,

2°. G este cvasi-tare-conex şi fără cicluri,

3°. G este cvasi-tare-conex şi are n-1 arce,

4°. există un vârf a X, care poate fi unit cu oricare alt vârf al grafului

printr-un singur drum ce pleacă din a.

Dacă G = (X, U) este un graf cvasi-tare-conex, atunci lăsând la o parte,

atât cât este posibil, arcele a căror îndepărtare nu modifică proprietatea de cvasi-

tare-conexitate, se obţine o arborescenţă.

§2. Grafuri neorientate

Fie X o mulţime nevidă. Definim perechea neorientată de extremităţi x şi

y ca fiind submulţimea (x, y), (y, x) XX×⊂ ; vom nota cu [x, y] perechea

neorientată de extremităţi x şi y.

Definiţia 12. a) Un graf neorientat G este o pereche G = (X,U) formată dintr-o

mulţime nevidă X ale cărei elemente se numesc vârfuri şi o mulţime U de

perechi neordonate de elemente din X ale cărei elemente se numesc muchii. 78

Page 73: matematici aplicate

b) Pentru muchia u=[x, y]∈U vârfurile x şi y se numesc extremităţi; se mai spune

că vârfurile x şi y sunt adiacente sau că x şi y sunt incidente muchiei u. Un vârf

neincident nici-unui arc se numeşte vârf izolat

Fiecărui graf neorientat i se poate asocia o imagine geometrică obţinută

reprezentând elementele mulţimii prin puncte sau cerculeţe mici iar mulţimea

muchiilor prin arce simple (fără autointersecţii) de curbă.

§3. Probleme de optim în grafuri

Suntem conduşi să asociem unui graf orientat sau nu, G = (X, U), o funcţie

pe care o numim (în mod tradiţional) funcţie lungime sau lungime chiar

şi în cazul în care ia şi valori pozitive şi valori negative. Pentru grafuri dotate cu

funcţie de lungime se pun probleme de optimizare. Astfel de probleme se pot

rezolva şi prin metodele programării liniare, dar abordarea lor cu ajutorul

metodelor teoriei grafurilor este mai eficientă.

→U:l

1. Problema arborelui parţial minimal/maximal

Exerciţiul 6. Revedeţi/ copiaţi algoritmul lui Kruskal ([1], pag. 188).

Exemplul 3. Să rezolvăm problema arborelui parţial minimal pentru graful neori-

entat G = (X, U) din Fig 3 dotat cu lungimi pozitive evidenţiate pe fiecare muchie

(ignoraţi pe moment numerele din paranteze!).

2 o o o

x3x2

4

3

x1

o

3

x1

Pasul 1. Se ia u* = [x6, x

o

o o o

5

38 1

5

4

6 5(7) x4 x6

1

x5

Fig. 3

o o

o

o o o

x3x2

38 1

4

5(7) x4 x6

1

x5

2

Fig. 4

798], v1=u*, V1=[x6, x8] şi se trece

o

1x8

(5)

o x8

(5)

(6)

(6)

1

la Pasul 2.

(3)

(3)

(4)

(4)

(2)

(2)

(1)

(1)

Page 74: matematici aplicate

Pasul 2. - Se ia u* = [x7, x8], v2=u*, V2=[x6, x8], [x7, x8] şi se reia Pasul 2.

- Se ia u* = [x2, x3], v3=u*, V3=[x6, x8], [x7, x8], [x2, x3] şi se reia Pasul 2.

- Se ia u* = [x1, x4], v4=u*, V4=[x6, x8], [x7, x8], [x2, x3], [x1, x4], [x2, x4] şi se

reia Pasul 2.

- Se ia u* = [x2, x4], v5=u*, V5=[x6, x8], [x7, x8], [x2, x3], [x1, x4], [x2, x4] şi se

reia Pasul 2.

- Se ia u* = [x3, x7], v6=u*, V6=[x6, x8], [x7, x8], [x2, x3], [x1, x4], [x2, x4], [x3,

x7] şi se reia Pasul 2.

- Se ia u* = [x5, x6], v7=u*, V7=[x6, x8], [x7, x8], [x2, x3], [x1, x4], [x2, x4], [x3,

x7], [x5, x6] şi se reia Pasul 2.

- De această dată nu mai există u* cu proprietăţile indicate la Pasul 2.ii al algo-

ritmului, deci algoritmul se opreşte. Soluţia obţinută este arborele parţial H =

(X, V7).

Numărul pus între paranteze reprezintă ordinea alegerii muchiilor: prima

muchie aleasă va purta indicele (1), a doua (2), etc.. Îngroşând muchiile alese, se

evidenţiază arborele parţial minimal căutat, reprezentat şi separat în Fig. 4.

O soluţie a problemei arborelui parţial maximal pentru acelaşi graf este

reprezentată în Fig.5.

o o o

x3x2 24 5

3

x1

Şi în rezolvarea problem

fiecare muchie aleasă

numărul alegerii.(vezi F

2. Problema

Exerciţiul 7. Revedeţi/

Exemplul 4. Să rezolvă

(X, U) din Fig 6.

(5)

o

o o o

43 1

5 )

5 x4 x6

1

x5

Fig. 5

ei arborelui parţial maximal se re

şi să se scrie în paranteze lângă

ig. 5).

drumului minim/maxim

copiaţi algoritmul I (Dantzig, [1], pa

m problema drumului minim pent

80

(4)

o x8

(5) 1 (7)

8(1)

com

ea n

g. 1

ru g

(3

(6)

6(2)

andă să

umărul

88).

raful ne

se îngroaşe

care indică

orientat G =

Page 75: matematici aplicate

o o o o o o

7 2

1dc

a 2 4

6

3e

57

f

7

b

Pasul 1. t(a) = 0, X1 = a

Pasul 2. k = 1 : ω+(X1) =

min 0+3, 0+6 = 3 = t(a) + ℓ(a,c), a

k = 2 : ω+(X2) = (a,f),(c,f

ℓ(c,d) = min 0+6, 3 +2, 3 + 7 =

t(f) = 5, X3 = a, c, f.

k = 3 : ω+(X3) = (f,d), (f,h

t(c) + ℓ (c,d) = min 5 +4, 5 + 8,

y* = d, t(d) = 9, X4 = a, c, f, d.

k = 4 : ω+(X4) = (d, e), (d,

+ ℓ(d, g), t(d) + ℓ(d, h), t(f) + ℓ(f, g)

5+8 = 10 = t(d) + ℓ(d, e), adică u* =

k = 5 : ω+(X5) = (d, g), (e,

+ ℓ( e, b), t(e) + ℓ(e, g), t(f) + ℓ(f, g

8, 5 + 8 = 11 = t(e) + ℓ( e, g), adic

f, d, e, g. Evident, eticheta lui g se

k = 6 : ω+(X6) = (e,b),(g,b

+ 7, 11 + 3 = 14 = t(g) + ℓ(g,b),

=a, c, f, d, e, g, b.

k = 7 : ω (X+7) = . ∅

Se trece la Pasul 3 pentru c

Pasul 3. Deoarece b X∈

între a şi b având lungimea

(a,c), (c, f), (f, d), (d, e), (e, g), (g

lui g se putea determina şi pe baza

f), (f, d), (d, g), (g,b) este tot soluţ

*b,aD

o

h8 3

g8

Fig. 6.

.

(a,c),(a,f), min t(

dică u* = (a,c). Deci

),(c,d), min t(a)

5 = t(c) + ℓ (c,f), a

), (f,g),(c,d), min

3 + 7 = 9 = t(f) + ℓ

g), (d, h), (f, g), (f,

, t(f) + ℓ(f, h) = mi

(d, e). Deci y* = e,

b), (e, g), (f, g),(f, h

), t(f) + ℓ(f, h) = m

ă u* = (e, g). Deci y

putea determina şi

), min t(e) + ℓ(e,

adică u* = (g,b). D

ă procedura de etich

7, rezultă că există

= t = 14.

,b). Având în ved

lui (d, g), rezultă că

ie a problemei.

)D( *b,al )b(

81

1

o 3

a) + ℓ (a

y* = c, t(

+ ℓ(a,f),

dică u* =

t(f) + ℓ

(f,d), adi

h), min

n 9 + 1,

t(e) = 10,

), min

in 9+2, 1* = g, t(g

pe baza l

b), t(g) +

eci y* =

etare s-a

drum de

Drumul

ere că la

şi drum

,c), t(a) + ℓ(a,f) =

c) = 3, X2 = a,c.

t(c) + ℓ(c,f), t(c) +

(c,f). Deci y* = f,

(f,d), t(f) + ℓ (f,g),

că u* = (f,d). Deci

t(d) + ℓ (d, e), t(d)

9 + 2, 9 + 7, 5 + 8,

X5 = a, c, f, d, e.

t(d)+ ℓ(d, g), t(e)

0+ 7, 10 + 1, 5 +

) = 11, X6 = a, c,

ui (d, g).

ℓ(g,b) = min 10

b, t(b) = 14, X7 =

încheiat.

lumgime minimă

căutat este =

pasul k=5 eticheta

ul = (a,c), (c,

*b,aD

*b,aD

Page 76: matematici aplicate

În aplicaţiile practice se obişnuieşte să se pună într-un cerc, lângă fiecare

vârf etichetat, eticheta care se calculează pe baza algoritmului şi să se îngroaşe

muchia u* determinată la etapa de lucru respectivă.

Exerciţiul 8. Aplicaţi pe exemplul de mai sus ”algoritmul” obţinut din algoritmul I

înlocuind peste tot operatorul minim cu operatorul maxim. Arătaţi că h nu are

etichetă unică. Se obţine sau nu răspuns la problema drumului maxim pentru

acest graf? Ce explicaţie daţi?

Exemplul 5. Vom rezolva problema drumului minim dintre vârfurile a şi b

pentru graful din Exemplul 4, utilizând algoritmul Bellman-Kalaba. În acest scop,

mai întâi redenumim vârfurile grafului ca în Fig. 7

o o o o o o o o

7 2

1

x7

x3 x2 x4

8 32 4

6

7

3

3

15

7

x6 8x5

x8 x1

Fig. 7

Construim tabelul

x1 x2 x3 x4 x5 x6 x7 x8 x1 0 3 +∞ +∞ 6 +∞ +∞ +∞ x2 +∞ 0 7 +∞ 2 +∞ +∞ +∞ x3 +∞ +∞ 0 1 +∞ 2 7 +∞ x4 +∞ +∞ +∞ 0 +∞ 1 +∞ 7 x5 +∞ +∞ 4 +∞ 0 8 8 +∞ x6 +∞ +∞ +∞ 5 +∞ 0 3 3 x7 +∞ +∞ +∞ +∞ +∞ +∞ 0 +∞ x8 +∞ +∞ +∞ +∞ +∞ +∞ +∞ 0

mi(0) +∞ +∞ +∞ 7 +∞ 3 +∞ 0

mi(1) +∞ +∞ 5 4 11 3 +∞ 0

mi(2) 17 12 5 4 9 3 +∞ 0

mi(3) 15 11 5 4 9 3 +∞ 0

mi(4) 14 11 5 4 9 3 +∞ 0

mi(5) 14 11 5 4 9 3 +∞ 0

Un drum minim de la x1=a la x8=b este Da,b*=(x1, x2), (x2, x5), (x5, x3), (x3, x6), (x6, x8). Exemplul 6. Vom rezolva problema drumului maxim dintre vârfurile x1 şi x8 ale

grafului din Fig. 8.

82

Page 77: matematici aplicate

o o o o o o o o

181

1

x4

x5

x2

4 x

x7

85

3

74

9

1

5

5

x3

x8 x1

Fig. 8

Construim tabelul următor:

x1 x2 x3 x4 x1 0 5 -∞ -∞ x2 -∞ 0 8 -∞ x3 -∞ -∞ 0 1 x4 -∞ -∞ -∞ 0 x5 -∞ -∞ -∞ -∞ x6 -∞ -∞ -∞ 8 x7 -∞ -∞ 5 10 x8 -∞ -∞ -∞ -∞

mi(0) -∞ -∞ -∞ 12

mi(1) -∞ -∞ 13 12

mi(2) 29 26 13 12

mi(3) 32 29 13 12

mi(4) 40 37 13 12

mi(5) 40 37 13 12

Un drum maxim de la x1=a la x8=b este *x

D

x4), (x4, x8).

Exemplul 7. Vom rezolva problema dru

9.a). În acest scop alegem arborescenţa H

arbore parţial minimal.

o o o o o

5

x5

x2

5

x7

-

-

21

5

-

x3

x1

Fig. 9

83

6

x5 x6 x7 x8 3 -∞ 7 -∞

-∞ -∞ 4 -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ 12 0 4 -∞ -∞

-∞ 0 -∞ 11 9 5 0 -∞

-∞ -∞ -∞ 0 -∞ 11 -∞ 0 15 20 22 0 24 20 25 0 24 20 33 0 24 20 33 0 24 20 33 0

(x=81

x 1, x7), (x7, x5), (x5, x6), (x6,

mului minim pentru graful din Fig.

0 reprezentată în Fig. 9.b) care este

o

o

o

7-3

2

x4

x6

-6

8

6

5x8

.a)

3

4

5

2

0

1

Page 78: matematici aplicate

H0 o o o o o o o o

x5

-

x1

-3

-

x4

-x2

x3

-

5 x

x7

7

--

-

5

21

5

6

8

-6

-

-

5x8

-0

Fig. 9.

Arcele neutilizate de H0 sunt (x1, x7), (x

x4), (x7, x5), (x7, x6). Au loc relaţiile:

+−=+<=−+−=+<=−+−=+<=−

+=+<=−

5xxxtxt2

5xxxtxt5

4xxxtxt9

20xxxtxt3

466242

655262

322232

711272

),()()(),()()(),()()(),()()(

l

l

l

l

+−=+<=−+−=+<=−+−=+<=−−−=+>=−

3xxxtxt5

3xxxtxt5

3xxxtxt2

5xxxtxt5

677262

577252

477242

866282

),()()(),()()(),()()(),()()(

l

l

l

l

Alegem u*=(x6, x8) şi construim arboresce

H1 o o o o o

-

x1

x5

x2

x3

-

5

x7

-

-

5

21

5

-

-

0

Fig. 9.

Arcele neutilizate de H1 sunt (x1, x7), (x

x4), (x7, x5), (x7, x6). Au loc relaţiile:

+−=+<=−−−=+<=−+−=+<=−

+=+<=−

5xxxtxt5

2xxxtxt7

4xxxtxt9

20xxxtxt3

655363

844383

322333

711373

),()()(),()()(),()()(),()()(

l

l

l

l

84

6 -

b)

2, x3), (x5, x6

===

=

05

05

15

2

===−=

58

25

36

72

.

nţa H1 reprez

o

o

x4

-

x6

7

-6

8

6

-

-

5

c)

2, x3), (x4, x8

=−=

==

05

53

15

2

), (x6, x4), (x6, x8), (x7,

entată în Fig. 9.c).

o x8 -

-

-3

3

), (x5

3

3

3

4

4

4

4

5

, x6), (x6

5

5

5

5

5 5

2

2

2

2

9

9

7

, x4), (x7,

Page 79: matematici aplicate

=+−=+<=−=+−=+<=−=+−=+<=−=+−=+<=−

583xxxtxt5

253xxxtxt5

363xxxtxt2

055xxxtxt2

677363

577353

477343

466343

),()()(),()()(),()()(),()()(

l

l

l

l

.

Algoritmul se opreşte şi D (x=*

81xx 1, x2), (x2, x7), (x7, x3), (x3, x4), (x4, x6), (x6,

x8) este drumul de lungime minimă egală cu –7.

Exemplul 8. Vom rezolva problema drumului maxim pentru graful din figura 10.

o o o o o o o o

-5 8-6

6

x7

x3 x2 x4

-2 -57

-3

-1

3

-2

-32

-4

x6 7x5

x8 x1

Fig. 10

Conform algoritmului III, se trece la graful din Fig. 11.a) căruia i se aplică

algoritmul II. În acest scop se alege de exemplu arborescenţa H0 reprezentată

în Fig. 11.b) care este arbore parţial minimal.

o o o o o o o o

5 -86

-6

x7

x3 x2 x4

2 5-7

3

1

-3

2

3-2

4

x6 -7x5

x8 x1

Fig. 11.a)

o o o o o o o o

x2

x8 -2x1

3

-3-3

6

x5 3 -4

5 -8

-6

x7

5

x6 -7

x3 -4x4 -10

2 5-7

1

2

3-2

40

Fig. 11.b)

Continuarea o propunem ca exerciţiu. După ce algoritmul de minimizare pentru

graful din Fig. 11.b) se opreşte, conform indicaţiilor algoritmului III, conside-

răm graful obţinut schimbând semnul lungimilor arcelor în ultimul graf.

Eticheta lui x8 va fi lungimea drumului maxim de la x1 la x8.

85

Page 80: matematici aplicate

3. Problema fluxului maxim şi a secţiunii minime Exemplul 9. Să determinăm fluxul maxim pentru reţeaua de transport redusă

reprezentată în Fig.12 ; lângă arce, în paranteze, sunt trecute capacităţile arcelor

corespunzătoare.

Pornim de la fluxul nul . Folosind marcajele construite pe baza algorit-

mului, se aleg pe rând lanţurile şi cantităţile ε corespunzătoare :

1°. L = (x x, x 81 1, x6), (x6, x5), (x5, x8) = , ε = ε+81xxL 1 = min 10 - 0, 4 - 0, 6 - 0 = 4,

2°. L = (x x, x 81 1, x2), (x2, x3), (x3, x8) =L , ε = ε+81xx 1 = min 9 - 0, 6 - 0, 17 - 0 = 6,

3°. L = (x x, x 81 1, x2), (x2, x7), (x7, x8) =L , ε = ε+81xx 1 = min 9 - 6, 5 - 0, 11 - 0 = 3,

4°. L = (x x, x 81 1, x4), (x4, x2), (x2, x7), (x7, x8) = , ε = ε+81xxL 1 = min 7 - 0, 3 - 0,

5 -3, 11 - 3 = 2,

5°. L = (x x, x 81 1, x4), (x4, x7), (x7, x8) = , ε = ε+81xxL 1 = min 7 - 2, 8 - 0, 11 - 5 = 5,

6°. L = (x x, x 81 1, x6), (x6, x7), (x7, x8) = , ε = ε+81xxL 1 = min 10 - 4, 5 - 0, 11 - 10 = 1,

fig.12

X2 X3

X8

X7X6

X4 X5X1

(9)

(7)

(6)

(3)(3)

(5)

(8)

(10)

(5)

(11)

(6)

(4)

(17)

7°. L = (x x, x 81 1, x6), (x6, x7), (x4, x7), (x4, x3), (x3, x8) = ∪ , unde +81xxL −

81xxL

= (x+81xxL 1, x6), (x6, x7), (x4, x3), (x3, x8), = (x+

81xxL 4, x7),

ε1 = min 10 - 5, 5 - 1, 3 - 0, 17 - 6 = 3, ε2 = 8-5 = 3, ε = 3.

Pe graf sunt marcate de această dată noile valori (nenule) ale fluxului. La

fiecare nouă aplicare a algoritmului se adaugă la valorile vechi ale fluxului noile

valori ale acestuia . După cea de a 7-a aplicare se obţine fluxul maxim. În plus,

mulţimea A = x1, x2, x4, x6, x7 determină o secţiune minimă pentru reţeaua de

transport dată.

86

Page 81: matematici aplicate

Capitolul VI

ELEMENTE DE TEORIA

PROBABILITĂŢILOR

Teoria probabilităţilor este acea ramură a matematicii care studiază pro-

prietăţile structurilor care modelizează fenomenele în a căror desfăşurare inter-

vine hazardul. Teoria probabilităţilor este instrumentul de bază în dezvoltarea

şi motivarea principalelor proceduri ale statisticii matematice; în acest sens,

una dintre valenţele ei principale este cea care permite să se precizeze condi-

ţiile în care se poate face extrapolarea la întreaga populaţie a rezultatelor con-

statate pe un eşantion. În fapt, se poate spune că procedurile de lucru din statis-

tica matematică sunt în esenţă reflectarea în planul realităţii a unor rezultate de

teoria probabilităţilor.

Obiectele concrete de studiu ale teoriei probabilităţilor sunt evenimen-

tele. La rândul lor, acestea sunt intrinsec legate de calitatea lor de a se realiza

sau nu; teoria probabilităţilor îşi propune să determine o măsură pentru şansa

de realizare a fiecărui eveniment de interes. În general, se poate spune că pro-

babilitatea unui eveniment este o expresie cuantificată a previziunii de a se

produce acel eveniment.

§1. Experienţe aleatoare. Evenimente aleatoare Experienţă aleatoare. Orice realizare a unui complex de condiţii bine precizate

se numeşte experienţă. Dacă rezultatul unei experienţe nu poate fi unic deter-

minat prin cunoaşterea condiţiilor de definiţie ale experienţei, se spune că ex-

perienţa este aleatoare.

- Orice realizare a unei experienţe se numeşte probă.

87

Page 82: matematici aplicate

- Fiecare dintre rezultatele care pot apare în urma efectuării unei experienţe se

numeşte caz posibil. Mulţimea tuturor rezultatelor posibile ale unei experienţe

E formează spaţiul de selecţie asociat experienţei şi se va nota cu Ω.

Exemplul 1. a) În cazul experienţei aruncării zarului pe o suprafaţă plană ori-

zontală, se va nota cu (i) rezultatul care constă în apariţia feţei cu i puncte la o

efectuare a experienţei. Spaţiul de selecţie asociat acestei experienţe este Ω =

(1),(2),(3),(4),(5),(6).

b) Se încrucişează două Regina nopţii cu flori roz. Plantele obţinute au fie flori

albe, fie roz, fie roşii. Deci spaţiul de selecţie este Ω = alb, roz, roşu.

Evenimente aleatoare. Orice situaţie potenţială legată de o experienţă (aleatoare)

E, despre care putem spune cu certitudine că s-a creat (s-a realizat) sau nu numai

după o efectuare a experienţei se numeşte eveniment aleator sau eveniment.

- Cazurile posibile care asigură realizarea unui eveniment A se numesc cazuri

favorabile evenimentului A. De exemplu, apariţia unei feţe cu un număr impar

de puncte este un eveniment legat de experienţa aruncării cu zarul; cazurile favo-

rabile lui sunt (1), (3) şi (5).

Cu (i) vom nota şi evenimentul apariţiei feţei cu i puncte la o efectuare

a experienţei.

Apariţia unei plante cu flori albe este un eveniment legat de experienţa din

Exemplul 1 b).

Evenimente egale sau echivalente. Două evenimente sunt egale dacă şi numai

dacă toate cazurile favorabile unuia sunt cazuri favorabile şi celuilalt; în acest caz

se foloseşte notaţia A = B.

Evenimentul cert. Evenimentul care se realizează la orice efectuare a experi-

enţei se numeşte evenimentul cert şi se notează cu Ω.

Evenimentul imposibil. Evenimentul care nu se realizează la nici-o efectuare

a experienţei se numeşte evenimentul imposibil şi se notează cu ∅ .

Implicaţia. Dacă realizarea lui A atrage în mod necesar realizarea lui B se

spune că B este implicat de A sau că A implică B; această situaţie se notează cu

B A, respectiv A B. ⊃ ⊂

- De exemplu, evenimentul (3) implică evenimentul A=(1), (3), (5).

88

Page 83: matematici aplicate

- Este util să acceptăm (prin definiţie) că pentru orice eveniment A are loc implica-

ţia ∅ . A⊂

- Implicaţia este o relaţie de ordine pe mulţimea evenimentelor asociate unei

experienţe.

Eveniment elementar. Eveniment compus. Orice eveniment ≠ ∅ care nu

este implicat decât de evenimentul imposibil şi de el însuşi se numeşte eveni-

ment elementar. Orice eveniment care nu este elementar se numeşte eveniment

compus.

Contrarul unui eveniment. Evenimentul care se realizează ori de câte ori nu

se realizează evenimentul A se numeşte contrarul evenimentului A şi se

notează cu A sau cu ¬A.

Reuniunea evenimentelor. Se numeşte reuniunea evenimentelor A şi B eveni-

mentul, notat cu A∪B, care se realizează atunci când, la o efectuare a experi-

enţei, se realizează sau A sau B.

Intersecţia evenimentelor. Se numeşte intersecţia evenimentelor A şi B

evenimentul, notat cu A∩B, care se realizează atunci când, la o efectuare a

experienţei, se realizează şi A şi B.

Diferenţa evenimentelor. Se numeşte diferenţa evenimentelor A şi B eveni-

mentul, notat cu A \ B, care se realizează atunci când, la o efectuare a experi-

enţei, se realizează A dar nu se realizează B.

Evenimente compatibile. Evenimente incompatibile. Două evenimente, aso-

ciate aceleiaşi experienţe E, se numesc compatibile dacă se pot realiza (simul-

tan) la aceeaşi efectuare a experienţei şi se numesc incompatibile în caz con-

trar. Prin urmare, două evenimente sunt incompatibile dacă realizarea unuia

exclude realizarea celuilalt.

Exerciţiul 1. La o fermă de vaci o parte dintre animale suferă de mamită. Se

extrag succesiv două vaci şi se notează cu A1=evenimentul „prima vacă are

mamită”, A2=evenimentul „a doua vacă are mamită”. Să se exprime cu ajutorul

evenimentelor A1 şi A2 evenimentele:

A = evenimentul „prima vacă este sănătoasă”, B = evenimentul “cel puţin o

vacă este bolnavă”, C = evenimentul ”ambele vaci sunt bolnave”, D = eveni-

mentul „o vacă este bolnavă şi una este sănătoasă”.

89

Page 84: matematici aplicate

Pe baza teoremei de reprezentare (teorema lui Stone), fiecare eveniment

se identifică cu mulţimea cazurilor favorabile care îl realizează (de exemplu,

evenimentul A citat în Exemplul 1 se identifică cu (1),(3),(5)). Prin acest

izomorfism evenimentului cert i se asociază mulţimea Ω∈P(Ω) iar evenimen-

tului imposibil i se asociază partea vidă ∅∈ P(Ω) a spaţiului de selecţie (apare

deci şi motivaţia pentru notaţiile folosite pentru aceste evenimente). Este de remar-

cat că dacă evenimentele A şi B se identifică prin acest izomorfism cu submulţimile

corespunzătoare ale spaţiului de selecţie, evenimentele A ∪ B, A ∩ B şi A \ B se

vor identifica corespunzător cu reuniunea, intersecţia şi respectiv diferenţa acestor

submulţimi.

Definiţia clasică a probabilităţii. Presupunem că experienţa E a fost

repetată de n ori şi că evenimentul A s-a realizat de p ori. Numărul p se numeş-

te frecvenţa absolută a evenimentului A în acest set de experienţe şi se mai

notează cu fa(A); numărul fr(A) = p/n se numeşte frecvenţa relativă a eveni-

mentului A.

Exerciţiul 2. Demonstraţi că frecvenţa relativă a evenimentelor legate de expe-

rienţa E are proprietăţile:

1º. fr(Ω) = 1, 2º. 0 ≤ fr(A) ≤ 1, 3º. fr(A∪B) = fr(A)+fr(B) dacă A şi B sunt

incompatibile, 4º. fr(A\B) = fr(A)-fr(B) dacă B implică A , 5º. fr(A\B) = fr(A)-

fr(A ∩ B), 6º. fr(A ∪ B) = fr(A)+fr(B)-fr(A ∩ B), 7º. fr(A) = 1- fr(A).

Experimental s-a constatat că, pentru multe experienţe, atunci când numărul n

de repetări ale experienţei E se măreşte frecvenţele relative se grupează în jurul

unei valori P(A) care dă o măsură a şansei de realizare a evenimentului A numită

şi probabilitatea lui A. S-a constatat că, în cazul când spaţiul de selecţie este

finit iar rezultatele care-l compun au şanse de realizare egale, P(A) este direct

proporţional cu numărul cazurilor favorabile şi invers proporţional cu numărul

cazurilor posibile; de aceea este plauzibil să se considere că P(A) este raportul

dintre numărul elementelor (cardinalul) mulţimii cazurilor favorabile evenimen-

tului A (cu care se identifică evenimentul A) şi numărul elementelor (cardinalul)

spaţiului de selecţie (adică numărul cazurilor posibile); deci

posibilecazurilornumarul

favorabilecazurilornumarul=P(A)

90

Page 85: matematici aplicate

adică, în acest caz, P(A) este chiar frecvenţa relativă de realizare a evenimen-

tului A.

Aceasta este de fapt definiţia clasică a probabilităţii unui eveniment. Din

păcate această definiţie se aplică numai în cazul ideal când rezultatele posibile ale

experienţei au şanse egale de realizare (se spune în acest caz că aceste rezultate

sunt echiprobabile). În situaţiile concrete această definiţie este rareori legal aplica-

bilă; în mod normal, frecvenţa relativă este doar o estimare a şansei de realizare a

evenimentului analizat.

Exemplul 2. Un fermier are 10 vaci din care 3 sunt bolnave. Se aleg aleator

două vaci. Se cere:

a) probabilitatea ca cele două vaci să fie sănătoase,

b) probabilitatea ca cele două vaci să fie bolnave,

c) probabilitatea ca prima vacă să fie sănătoasă şi a doua bolnavă,

d) probabilitatea ca prima vacă să fie bolnavă şi a doua sănătoasă,

e) probabilitatea ca ambele vaci să fie sau sănătoase sau bolnave,

f) probabilitatea ca o vacă să fie sănătoasă iar cealaltă bolnavă.

Vom calcula de fiecare dată numărul cazurilor favorabile şi cel al cazurilor

posibile. Deoarece extragerile sunt aleatorii, perechile de animale au şanse

egale de a fi alese, deci se poate folosi definiţia clasică a probabilităţii. Este util

să reamintim că este numărul de submulţimi (neordonate) formate din K

elemente distincte ale unei mulţimi cu n elemente şi că este numărul de

submulţimi ordonate formate din K elemente distincte ale unei mulţimi cu n

elemente.

knC

knA

a) Fie A1 evenimentul „cele două vaci sunt sănătoase”. În acest caz există

cazuri favorabile şi cazuri posibile; deci P(A21C27 = 45C2

10 = 1)= 157

4521 = .

b) Fie A2 evenimentul „cele două vaci sunt bolnave”. În acest caz există

cazuri favorabile şi cazuri posibile; deci P(A3C23 = 45C2

10 = 1)= 151

453 = .

c) Fie A3 evenimentul „prima vacă să fie sănătoasă şi a doua bolnavă”. În

acest caz există 7·3=21 cazuri favorabile şi cazuri posibile; deci

P(A

90A210 =

3)= 307

9021 = .

91

Page 86: matematici aplicate

d) Fie A4 evenimentul „prima vacă să fie bolnavă şi a doua sănătoasă”. În

acest caz există 7·3=21 cazuri favorabile şi cazuri posibile; deci

P(A

90A210 =

3)= 307

9021 = .

e) Fie A4 evenimentul „vacile sunt ambele sănătoase sau ambele bolnave”.

În acest caz există cazuri favorabile şi cazuri

posibile; deci P(A

24213CC 27

23 =+=+ 45C2

10 =

4)= 158

4524 = .

e) Fie A4 evenimentul „vacile sunt una sănătoasă iar cealaltă bolnavă”. În

acest caz există 2·7·3=42 cazuri favorabile şi cazuri posibile; deci

P(A

45C210 =

4)= 1514

4542 = .

§2. Câmp de evenimente

Fiecărei experienţe E i se asociază spaţiul de selecţie corespunzător Ω

şi mulţimea tuturor evenimentelor. Nu este totdeauna necesar să lucrăm cu

mulţimea tuturor evenimentelor. Ne putem restrânge, în funcţie de problema-

tica de interes, la o submulţime a mulţimii tuturor evenimentelor. O astfel de

submulţime trebuie să satisfacă câteva condiţii care să asigure consistenţa lim-

bajului introdus anterior. Ne vor interesa familiile K de evenimente care conţin

odată cu un eveniment şi contrarul acestuia şi sunt stabile la reuniuni finite

(respectiv, numărabile); perechile (Ω , K) se vor numi câmpuri (resp. σ-câm-

puri) de evenimente.

Pentru orice (Ω , K) se constată imediat că Ω∅, ∈K şi că orice câmp (resp. σ-

câmp) de evenimente este stabil relativ la reuniunile şi intersecţiile finite resp.

numărabile de evenimente (adică orice reuniune sau intersecţie finită resp.

numărabilă de evenimente din K este un eveniment din K).

Convenţie. Vom utiliza sintagma (σ-) câmp de evenimente în afirmaţiile ade-

vărate atât pentru câmpuri de evenimente cât şi pentru σ-câmpuri de eveni-

mente.

Definiţia 1. Se spune că evenimentele familiei (Ai)i∈I din (σ-) câmpul K for-

mează un sistem complet de evenimente pentru K dacă

1°. Ai ≠∅, ∀ i∈I,

2°. sunt incompatibile două câte două, adică Ai ∩ Aj = ∅ dacă i j, ≠

92

Page 87: matematici aplicate

3°. =∪A . Ω∈

iIi

În cazul particular când I este finită se poate considera că I = 1,2,...,n.

Exemplul 3. Un abator achiziţionează porci pentru sacrificare de la fermele F1,

F2, F3 şi F4 pe care îi pune, până la sacrificare, în acelaşi ţarc. Fie Ai (i =

1,2,3,4) evenimentul ca un porc sacrificat (din ţarc) să provină de la ferma Fi.

Familia de evenimente A1, A2 , A3 , A4 formează un sistem complet de

evenimente pentru experienţa care constă în sacrificarea unui porc din ţarc.

Într-adevăr, evenimentele sunt diferite de evenimentul imposibil pentru că se

fac achiziţii efective de la toate fermele. Un porc sacrificat provine de la una şi

numai una dintre ferme, deci cele patru evenimente sunt incompatibile două

câte două. În sfârşit, orice porc sacrificat provine de la una din ferme, deci

reuniunea celor patru evenimente este evenimentul cert.

§3. Funcţie de probabilitate Definiţia 2.a) Se numeşte funcţie de probabilitate pe câmpul de evenimente

(Ω, Κ) orice funcţie P: Κ → + cu proprietăţile:

1°. P(Ω) = 1,

2°. oricare ar fi evenimentele incompatibile A, B∈Κ

P(A ∪ B) = P(A) + P(B).

b) Se numeşte funcţie de probabilitate pe σ-câmpul de evenimente

(Ω,Κ) orice funcţie P: Κ → + cu proprietăţile:

1°. P(Ω) = 1,

2°. , oricare ar fi familia numărabilă de eveni-

mente A

)AP(AP( n

Nn

n

Nn *

= ∑∪∈∈

)*

n∈Κ, n∈ *, incompatibile două câte două (adică Ai ∩ Aj = , ∀

i j).

∅≠

c) Tripletul (Ω,Κ,P) format din (σ-) câmpul de evenimente (Ω, Κ) şi

funcţia de probabilitate P se numeşte (σ-) câmp de probabilitate.

Propoziţia 1. Funcţia de probabilitate a oricărui (σ-) câmp de probabilitate

(Ω,Κ,P) are proprietăţile:

1°. =P( 0,)∅ 2°. P(A),-)A 1=P( ∀ A∈Κ,

93 3°. ∈∀∩ BA, B),P(A-P(B)=A)P(B \ Κ şi, în particular,

Page 88: matematici aplicate

3’. \P A(B ) = P(B) - P(A), A,B cu A B,∀ ∈ ⊂K 4°. P (A) ≤ P (B) dacă A ⊂ B şi A, B∈Κ, 5°. 0 ≤ P(A) ≤ 1, ∀ A∈Κ, 6°. P(A ∪ B) = P (A) + P (B) - P(A ∩ B), ∀ A, B ∈ Κ

7°. 11

11 2 1 2

( ) ( ) ...

( 1) ( ... ), , , ..., .

n n

i i i ji i ji

nn n

P A P A P A A

P A A A A A A= <=

+

= − ∩ + +

+ − ∩ ∩ ∩ ∀ ∈

∑ ∑U

K 8°. ∈∀∩+∆ BA, B),P(A2-P(B)P(A=B) )P(A Κ 9°. ( ) ( ) , ,n n n

n Nn N

P A P A cu A n∈∈

≤ ∈ N∀ ∈∑U K .

Remarca 1. 1°. Se spune că un eveniment diferit de evenimentul cert se realizează

aproape sigur sau că este eveniment aproape sigur dacă are probabilitatea de

realizare 1. 2°. Se spune că un eveniment diferit de evenimentul imposibil este

eveniment aproape imposibil dacă are probabilitatea de realizare 0.

Remarca 2. În cazul particular când Ω = e1,...,en, de obicei se consideră Κ =

Π(Ω) şi se notează cu ei evenimentele elementare ei (i=1,2,...,n). Fie P: Κ →¡+

o funcţie de probabilitate pe (Ω, Κ). Dacă evenimentele elementare ei (i=1,2,...,n)

sunt echiprobabile, adică P(e1) = P(e2) =...= P(en) = p, atunci P(Ω) = 1 = P(e1) +

P(e2) + ... + P(en) = np şi, prin urmare, p=1/n. Rezultă atunci că evenimentul A

= are probabilitatea e,... , e ii k1

)e(P + ... + )e(P = ) A( P ii k1 =

n

1k = pk ⋅⋅ .

Se regăseşte în acest caz definiţia clasică a probabilităţii.

§4. Probabilităţi condiţionate Introducerea noţiunii de probabilitate condiţionată este sugerată de

următoarea problemă.

Problemă. Se consideră o urnă în care sunt n bile identice din care: a bile

marcate cu A, b bile marcate cu B şi c bile marcate şi cu A şi cu B. Dacă A =

evenimentul extragerii unei bile care poartă marca A iar B = evenimentul

extragerii unei bile care poartă marca B, se cere să se determine probabilitatea

de realizare a evenimentului B în ipoteza că A s-a realizat. Această probabilitate

se notează cu PA(B) sau cu P(B / A). In ipoteza că A s-a realizat, vor fi a + c

cazuri posibile dintre care c sunt cazuri favorabile lui B, deci PA(B) = c + a

c . Se

constată imediat că ) A( P

) B A( P = ) (B PA

∩ .

94

Page 89: matematici aplicate

Suntem conduşi să dăm următoarea definiţie care abstractizează situaţia

din problema de mai sus.

Definiţia 2. Fie (Ω, Κ, P) un (σ-) câmp de probabilitate şi A ∈ Κ un eveniment

având P(A) ≠ 0. Se numeşte probabilitatea evenimentului B condiţionată de

evenimentul A numărul notat cu PA(B) (sau cu P(B/A)) definit prin

(1) ) A( P

) B A( P ) A /B ( P = ) B ( PA

∩= .

S-a obţinut în acest fel o funcţie PA : Κ →¡+; se demonstrează că (Ω, Κ,

PA) este un câmp de probabilitate (exerciţiu!).

Din formula (1) se obţine egalitatea

)B(P)A(P = ) B A( P A⋅∩ .

Dacă şi P(B) ≠ 0, au loc egalităţile

. ) B ( P

) B ( P = ) A( P

) A( P ) A( P ) B ( P = ) B ( P ) A( P ABBA ⇒⋅⋅

adică, „frecvenţa relativă” de realizare a evenimentului A în ipoteza că B s-a

realizat este egală cu „frecvenţa relativă” de realizare a evenimentului B în

ipoteza că A s-a realizat.

Exemplul 4. Una dintre experienţele lui Mendel se referă la încrucişarea mazării

homozigote cu flori galbene şi verzi. Se ştie că la prima generaţie s-a obţinut

numai mazăre heterozigotă cu flori galbene. Încrucişând mazărea din prima

generaţie (adică, doi heterozigoţi) s-a ajuns la a doua generaţie la mazăre cu flori

galbene şi la mazăre cu flori verzi. Ne propunem să determinăm probabilitatea p

ca o plantă cu flori galbene din a doua generaţie să fie heterozigotă. Avem deci de

calculat o probabilitate condiţionată. Mai exact, dacă notăm

G = evenimentul că planta are flori galbene,

V = evenimentul că planta are flori verzi,

H = evenimentul că planta este heterozigotă,

atunci p = PG(H). Dacă A şi a sunt cele două alele ale genei legate de culoarea

florii, există în generaţia a doua 4 evenimente elementare echiprobabile: AA, Aa,

aA, aa. Gena A este dominantă şi prin urmare

G = AA, Aa, aA şi H∩G=Aa, aA = H.

Rezultă că P(G)=3/4, P(H∩G)= ½ şi 32

GP

GHP=

∩=

)()(

p .

95

Page 90: matematici aplicate

Definiţia 3. Se spune că evenimentele A şi B sunt independente (sau P-inde-

pendente) dacă . )B(P)A(P = )BA(P ⋅∩

Două evenimente pot fi independente relativ la o funcţie de probabilitate şi

dependente relativ la altă funcţie de probabilitate. Deci independenţa evenimentelor

nu este o noţiune intrinsecă a evenimentelor în discuţie ci este dependentă de

modul de cuantificare a şanselor lor de realizare. Două evenimente independente

nu sunt în mod necesar condiţional independente în raport cu orice eveniment.

Se vede că dacă A şi B sunt independente au loc egalităţile

, )B(P = )B(P = ) B ( P AA . ) A( P = )A(P = )A(P BB

Egalităţi similare au loc şi pentru B şi A. Prin urmare, pentru o pereche de

evenimente independente, şansa de realizare sau nerealizare a unui eveniment

este independentă de realizarea sau nerealizarea celuilalt; aceasta este în

concordanţă atât cu intuiţia cât şi cu sensul uzual al noţiunii de independenţă.

Exemplul 5. Se doreşte să se măsoare valoarea diagnosticului unui examen

clinic E într-o boală B. Acest examen este practicat pe un eşantion de volum n

format din indivizi clasaţi în prealabil în bolnavi (B+) şi sănătoşi (B-) cu ajutorul

unui test de referinţă presupus fără eroare de clasificare. Rezultatele experienţei

sunt trecute în tabelul de mai jos.

B+ prezenţa

B- absenţa

Examen pozitiv E+ a b a+b

Examen negativ E- c d c+d

a+c b+d n=a+b+c+d

Pentru a compara testul E cu testul de referinţă se vor aprecia performan-

ţele sale ca proporţie a celor ale testului de referinţă, adică se va considera

raportul c + a

a care este de fapt P(E+/ B+). Se poate da deci tabloul care dă

distribuţia probabilităţilor rezultatelor examenului E condiţionate de B şi anume

B+ prezenţa

B- absenţa

Condiţia P(B+) P(B-) Examen pozitiv E+ P(E+/ B+) P(E+/ B-)

96

Page 91: matematici aplicate

Examen negativ E- P(E-/ B+) P(E-/ B-) Total 1 1

Se poate considera şi tabloul care dă distribuţia probabilităţilor rezulta-

telor examenului de referinţă condiţionate de E şi anume

Condiţia B+ prezenţa

B- absenţa

Total

Examen pozitiv

E+ P(B+) P(B+/ E+) P(B-/ E+) 1

Examen negativ

E- P(B-) P(B+/ E-) P(B-/ E-) 1

Exemplul 6. Se ştie că efectele secundare ale unui medicament survin la

10 % bolnavi. Un veterinar tratează două animale cu acest medicament. Se pune

problema să se determine probabilitatea ca cele două animale să aibă efecte

secundare. Vom nota cu A = evenimentul ca primul animal tratat să aibă efecte

secundare şi cu B = evenimentul ca al doilea animal tratat să aibă efecte

secundare. In acest caz se poate presupune că cele două evenimente sunt inde-

pendente deoarece nu există nici-un motiv ca apariţia efectelor secundare la unul

dintre animale să justifice apariţia efectelor secundare la celălalt animal. Dacă C

= evenimentul ca ambele animale tratate să aibă efecte secundare, atunci B A= C ∩ . 0,01 = 0,1 0,1 = ) B ( P ) A( P = ) B A( P = ) C ( P ⋅⋅∩

Aici s-a ţinut cont că proporţia de bolnavi care au efecte secundare este p = 0,1 şi

p este chiar probabilitatea ca un animal tratat să aibă efecte secundare.

Exemplul 7. In condiţiile exemplului precedent, ne punem problema să determinăm

probabilitatea ca cel puţin unul din cele două animale să aibă efecte secundare.

Dacă D = evenimentul ca cel puţin unul din cele două animale tratate să aibă

efecte secundare, rezultă că D şi, prin urmare, B A= ∪

0,19=0,1 0,1 - 0,1 + 0,1=)B A(P - ) B ( P + ) A(P = ) B A( P ⋅∩∪ .

Definiţia 4.a) Se spune că evenimentele Ai ∈ Κ (i = 1, 2, ... ,n) sunt independente

(în totalitate dacă pentru orice număr natural K (2 ≤ K ≤ n) şi orice numere

naturale i1, ... , iK cu 1 ≤ i1 < ... < iK ≤ n are loc egalitatea

) A ( P ... ) A ( P = ) A ... A ( P iiii k1k1⋅⋅∩∩ .

b) Două sisteme complete de evenimente (A1, A2,...,Am) şi (B1, B2,...,Bn) sunt

independente dacă

P(Ai∩Bj)=P(Ai)P(Bj), ∀i=1, 2, ... , m, ∀j=1, 2, ..., n. 97

Page 92: matematici aplicate

§5. Probabilitatea evenimentelor dependente.

Inegalitatea lui Boole

Fie (Ω, Κ, P) un (σ-) câmp de probabilitate şi A1,A2,...,An un sistem de

evenimente care nu sunt independente şi pentru care Utilizând

inducţia completă rezultă formula

. 0 ) A ( P i

n

1 = i

≠∩

) A ( P . . . ) A ( P ) A ( P ) A ( P = ) A ( P nAA A3A A2A1i

n

1 = i 1n21211 −∩∩∩∩⋅⋅∩ ...

Această formulă este cunoscută şi sub numele de formula de înmulţire a proba-

bilităţilor.

In practică se preferă deseori să se determine un minorant al numărului

determinat prin inegalitatea lui Boole: ) A ( P i

n

1 = i∩

) 1 - n ( - ) A ( P ) A ( P i

n

1 = ii

n

1 = i∑∩ ≥ .

Exemplul 8. Să comparăm două teste T şi B pentru paratuberculoza bovină. Pe

un lot de 1000 animale s-au obţinut datele :

B+ B- Total

T+ 55 175 230

T- 45 725 770

Total 100 900 1000

Rezultă

9460,1 = 009

751 = ) -B +T ( P 50,5 =

001

55 = ) +B +T ( P

30,2 = 0001

302 = ) +T ( P 0,10 =

0001

001 = ) +B ( P

||;

deoarece P(T+/ B+) şi P(T+/ B-) sunt mult diferite rezultă că rezultatul testului T

depinde de realizarea sau nerealizarea lui B, adică cele două teste nu sunt indepen-

dente. Prin urmare, experienţe realizate independent şi pe care le percepem ca inde-

pendente, nu sunt independente probabilistic (adică între ele există legături care

depăşesc posibilităţile obişnuite de analiză şi apreciere).

98

Page 93: matematici aplicate

§6. Formula probabilităţii totale. Formula lui Bayes

Fie (Ω, Κ, P) un (σ-) câmp de probabilitate şi A1,A2,...,An un sistem

complet de evenimente pentru care 0 ) A ( P i ≠ , i = 1, 2, ... , n. Atunci proba-

bilitatea oricărui eveniment A ∈ Κ se determină cu formula

)A(P)A(P +...+ )A(P)A ( P + ) A( P ) A ( P = ) A( P A nA 2A 1 n21⋅⋅⋅ .

Această formulă se numeşte formula probabilităţii totale.

Elementele unui sistem complet de evenimente se interpretează adesea ca

fiind cauzele care participă la realizarea evenimentului A. Apare atunci în mod

firesc întrebarea: ştiindu-se că evenimentul A s-a realizat, care este contribuţia

(ca proporţie) a cauzei Ai la realizarea lui?

Are loc formula

) A( P ) A ( P

) A( P ) A ( P = ) A ( P

A j

n

1 = j

A ii A

j

i

cunoscută sub numele de formula lui Bayes. Această formulă este baza unei

ramuri a statisticii numită statistica bayesiană, care are importante aplicaţii în

medicină, meteorologie, risc financiar, etc..

Exemplul 9. Reluăm situaţia din Exemplul 3. Pe baza facturilor s-a calculat că

17% din porcii cumpăraţi sunt de la ferma F1, 29% sunt de la ferma F2, 15%

sunt de la ferma F3, 39% sunt de la ferma F4. De asemenea, pe baza informaţiilor

de la achiziţiile anterioare s-a calculat că :

2% din porcii de la ferma F1 au trichiniloză

3% din porcii de la ferma F2 au trichiniloză

1% din porcii de la ferma F3 au trichiniloză

2% din porcii de la ferma F4 au trichiniloză.

Se sacrifică un porc ales la întâmplare. Se cere :

1° să se calculeze probabilitatea ca porcul sacrificat să fie bolnav ,

2° ştiind că porcul sacrificat a fost bolnav, să se calculeze probabilitatea

ca el să provină de la ferma F2.

1° Notăm cu A evenimentul "porcul sacrificat este bolnav". Folosind

formula probabilităţii totale rezultă :

99

Page 94: matematici aplicate

) A A( P ) A ( P + ) A A( P ) A ( P

+ ) A A( P ) A ( P + ) A A( P ) A ( P = ) A( P

4433

2211

||||

⋅⋅+

⋅⋅

deci 0,0214 = 0,02 0,39 + 0,01 0,15 + 0,03 0,29 + 0,02 0,17 = ) A( P ⋅⋅⋅⋅

2° Din formula lui Bayes rezultă

0,4065 = 0,0214

0,29 0,03 = ) A A ( P

) A( P

) A A ( P = ) A A ( P 2

22

⋅∩|,| .

Exemplul 10. Reluăm situaţia din Exemplul 4 a încrucişării mazării cu flori

galbene cu mazăre cu flori verzi şi luăm o plantă cu flori galbene din a doua

generaţie. Pe lângă notaţiile de acolo notăm cu D = evenimentul ca planta să fie

homozigotă. Atunci, PG(D)=1/3, PG(H)=2/3. Vom încrucişa această plantă cu

flori galbene cu o plantă cu flori verzi şi obţinem 5 plante cu flori galbene. Fie A

evenimentul obţinerii acestor 5 plante. Ne propunem să determinăm probabilitatea

ca planta să fie homozigotă. Ţinem cont că dacă planta este homozigotă, cele 5

plante obţinute după încrucişare sunt toate heterozigote şi au florile galbene adică

PD(A)=1; dacă planta este heterozigotă, fiecare descendent are şansa ½ de a avea

flori galbene şi probabilitatea (½)5 ca cei 5 descendenţi să aibă florile galbene.

Atunci

( ) ( ) 94101

1DP

321

32

31

31

A ,)( ≅⋅+⋅

⋅= .

Atât formula probabilităţii totale cât şi formula lui Bayes se extind la σ-

câmpuri de probabilitate (Ω, Κ, P) pentru care există sisteme complete

numărabile de evenimente (An)n∈ù.

Se poate considera că cunoaşterea apriorică a fenomenului studiat este rezumată

în valorile P(A1), P(A2), ... , P(An).

§7. Scheme probabilistice clasice

Prin scheme probabilistice clasice se înţelege o familie de metode de rezol-

vare a unor clase de probleme care apar des în aplicaţiile teoriei probabilităţilor.

Schema lui Poisson

Se aplică la rezolvarea următoarei clase de probleme.

Se consideră o experienţă E care constă în efectuarea a n experienţe

independente E1, E2, ... , En. Fie A1, A2, ... , An evenimente asociate expe-

rienţelor E1, E2, ... , respectiv En, având probabilităţile de realizare p1 = P(A1), p2

100

Page 95: matematici aplicate

= P(A2) ... şi respectiv pn = P(An). Se cere să se determine probabilitatea ca la o

efectuare a experienţei E să se realizeze evenimentul A care constă în realizarea a

exact K (0 ≤ K ≤ n) dintre evenimentele A1, A2, ... , An.

Soluţia acestei problemei este

P(A) = coeficientul lui xK din polinomul (p1x + q1)(p2x + q2)..(pnx + qn)

unde qi=1-pi, i=1, 2, ... , n.

Exemplul 11. În condiţiile Exemplului 9, dacă se sacrifică câte un porc de

la fiecare fermă, care este probabilitatea să fie sacrificaţi 3 porci sănătoşi şi unul

bolnav ? Suntem în cazul schemei Poisson. Deci, dacă notăm cu A evenimentul

"3 porci sunt sănătoşi şi unul bolnav", P(A) este coeficientul lui x3 din polinomul

) 0,02 + x 0,98 ( ) 0,01 + x 0,99 ( ) 0,03 + x 0,97 ( ) 0,02 + x 0,98 ( ,

adică

0,075 = 0,98 0,99 0,97 0,02 + 0,98 0,99 0,03 0,98 +

+ 0,98 0,01 0,97 0,98 + 0,02 0,99 0,97 0,98 = ) A( P

⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅

Schema binomială (Bernoulli)

Este cazul particular al schemei Poisson aplicate experienţei E pentru care

p1 = p2 = ... = pn = p. Notând q = 1 - p rezultă

P(A) = coeficientul lui xK din polinomul (px + q)n = CnKpKqn-K.

Schema lui Bernoulli se aplică des în rezolvarea unor probleme modelate în felul

următor.

Se consideră o urnă care conţine a bile albe şi b bile negre. Din această

urnă se fac n extrageri, punându-se de fiecare dată bila extrasă înapoi în urnă. Să

se determine probabilitatea evenimentului A care constă în obţinerea exact de K

(0 ≤ K ≤ n) ori a unei bile albe în cele n extrageri.

Evident, fiecare din cele n extrageri se poate considera a fi una din cele n

experienţe independente din cazul "schemei Poisson".

Deci P(A) = CnKpKqn-K, unde

b + a

a = p şi

b + a

b = q .

Deoarece după fiecare extragere bila extrasă se repune în urnă, schema

Bernoulli se mai numeşte şi schema bilei revenite sau schema bilei întoarse.

101

Page 96: matematici aplicate

Evident schema binomială se aplică ori de câte ori experienţa de interes

constă în repetarea unei anumite experienţe.

Exemplul 12. Se ştie că o parte dintre vacile unei ferme sunt infectate cu

virusul leucozei bovine enzootice. Se extrag fără revenire trei vaci. Dorim să

determinăm probabilitatea ca numai un singur animal ales să fie infectat, ştiind că

proporţia de animale infectate este de trei ori mai mică decât cea a animalelor

neinfectate.

Dacă p notează proporţia de animale infectate, rezultă că p = 0,25. Notăm

cu A evenimentul ca o singură vacă din cele 4 alese este infectată. Conform

schemei Bernoulli

q p C = ) A( P 2 3

1 adică P . 0,42 0,421875 = 750, 0,25 3 = ) A( 2 ≈⋅⋅

Schema multinomială

Această schemă este o generalizare a schemei binomiale la cazul când

urna conţine bile de m (>2) culori.

O urnă conţine a1 bile de culoarea c1, a2 bile de culoarea c2,..., am bile de

culoarea cm (m>2). Din urnă se extrag n ≤ a1+a2+…+am=N bile punând de

fiecare dată bila extrasă înapoi în urnă. Se cere probabilitatea ca în cele n

extrageri să obţinem n1 bile de culoarea c1, n2 bile de culoarea c2,..., nm bile de

culoarea cm, cu n1+n2+…+nm =n. Dacă A este evenimentul de interes, atunci

răspunsul problemei este

m21 nm

n2

n1

m21ppp

nnn

nAP ...

!!...!!)( =

unde m21iN

aii ,...,,, ==p şi p1+p2+…+pm=1.

Exemplul 13. Se consideră un locus dialelic pentru o populaţie panmictică şi

infinită de animale. Cele două gene A şi a au proprietatea că indivizii AA şi Aa

au fenotip normal iar indivizii aa mor înainte de maturitate. Se ştie că o proporţie

de p=⅛ indivizi au gena a. Se extrag 10 indivizi din populaţie. Care este probabi-

litatea evenimentului B ca în grupa de pui extrasă să fie 5 indivizi AA, 3 indivizi

Aa şi 2 indivizi aa? Se stabileşte uşor că, pentru populaţia de urmaşi, p1 = P(AA)

= (⅞)2, p2=P(Aa) =2·⅛·⅞ şi p3=P(aa)=(⅛)2. Atunci

102

Page 97: matematici aplicate

523

32

51

10652ppp235

10BP −== .,

!!!!)( .

Schema hipergeometrică

Se aplică la rezolvarea următoarei clase de probleme.

Se consideră o urnă U care conţine a bile albe şi b bile negre. Din această

urnă se fac n ( n ≤ a + b) extrageri fără a pune bila extrasă înapoi în urnă. Să se

determine probabilitatea evenimentului A care constă în extragerea a α (0 ≤ α ≤

a) bile albe şi a β = n – α bile negre.

Rezolvare. Având în vedere că o grupă de α bile albe şi β = n - α bile

negre este formată reunind o grupă de α bile albe cu o grupă de β = n - α bile

negre, rezultă că există Caα⋅Cb

β posibilităţi de a extrage o astfel de grupă favorabilă.

Cum există Ca+bn moduri de a extrage o grupă de n bile din urna U, rezultă că

C

C C = ) A( P + b + a

baβα

βα ⋅.

Exemplul 14. La ferma de vaci F cu un efectiv de 1000 de vaci 100 suferă de

mamită. Dacă sunt analizate 5 vaci alese aleator, care este probabilitatea ca două

vaci să fie bolnave iar 3 să fie sănătoase ?

Dacă A este evenimentul ca două vaci din cele 5 să sufere de mamită,

aplicând schema hipergeometrică rezultă

C

C C = ) A( P1000

5900100

2 3⋅ .

§8. Variabile aleatoare

Conceptul de variabilă aleatoare (v.a.) formalizează noţiunea de mărime

care variază în funcţie de rezultatul unei experienţe aleatoare. Variabilele aleatoare

sunt funcţii pentru care nu este suficient să cunoaştem numai valorile ci trebuiesc

cunoscute şi probabilităţile cu care se iau aceste valori. O v.a. cu un număr finit

de valori se numeşte v.a. simplă şi este prezentată cu ajutorul unui tabel de forma

ξ

p ... p p

x ... x x :

n21

n21 sau ξ n , ... , 2 , 1 i p

x :

i

i ∈

pentru care este satisfăcută condiţia (0≤p1 = p i

n

1 = i∑ i≤1, i=1,2,…,n).

103

Page 98: matematici aplicate

V.a. ξ care ia ca valori numărul de puncte care apar la aruncarea unui zar are

tabloul de repartiţie

ξ

61

61

61

61

61

61

654321 : .

Dacă ξ şi η sunt v.a. simple (resp. discrete) având tablourile de repartiţie

ξ

p

x :

i

i şi respectiv

η

q

y :

j

j

cu i = 1, 2, ... , n şi j = 1, 2, ... , m şi cu şi , atunci definim

v.a. ξ + η, ξ - η, ξ ⋅ η, ξ / η (dacă η ≠ 0), ξ + K, Kξ, ξ

1 = p i

n

1 = i∑ 1 = q j

m

1 = j∑

n şi |ξ|α prin :

ηξ

p

y + x : +

j i

ji, , , ,

ηξ

p

y - x : -

j i

ji

⋅η⋅ξ

p

y x :

j i

ji

ηξ

p

y /x : /

j i

ji

ξ

p

k + x : k +

i

i , k , , |

⋅ξ

p

xk :

i

i

ξ

p

x :

i

in

n

ξ

αα

p

x :

i

i |||

unde pij = P((X=xi) ∩(Y=yj)) cu i = 1, 2, ... , n şi j = 1, 2, ... , m.

V.a. ξ şi η sunt independente dacă (X=xi) şi (Y=yj)) sunt independente cu i = 1, 2,

... , n şi j = 1, 2, ... , m.

Funcţia Fξ : ú → ú definită prin Fξ(x) = P(ξ < x), ∀ x ∈ ú se numeşte funcţia de

repartiţie a v.a. ξ. Ea are proprietăţile

P1. F este nedescrescătoare (adică dacă x1 < x2 atunci F(x1) ≤ F(x2) ),

P2. F este continuă la stânga în orice x ∈ ú ( adică F(x) = F(x - 0), ∀ x ∈ ú ),

P3. F , 0 = ) x ( F = ) - ( x −∞→

∞ lim 1 = ) x ( F = ) + ( Fx ∞→

∞ lim ,

P4. P(a ≤ ξ < b) = F(b) - F(a)

P(a < ξ < b) = F(b) - F(a) - P(ξ = a)

P(a < ξ ≤ b) = F(b) - F(a) + P(ξ = b) - P(ξ = a)

P(a ≤ ξ ≤ b) = F(b) - F(a) + P(ξ = b)

P5. F este continuă în x dacă şi numai dacă P(ξ = x) = 0.

Trebuie menţionat că există v.a. care iau o familie numărabilă de valori dar şi v.a.

ale căror valori umplu un interval.

Fie F funcţia de repartiţie a unei v.a. ξ. Dacă există o funcţie nenegativă

ρ : ú → ú, integrabilă pe ú astfel încât

104

Page 99: matematici aplicate

R x t d )(t = ) x ( Fx

-

∈∀ρ∫∞

,

se spune că ρ este densitate de probabilitate sau densitate de repartiţie a v.a. ξ.

b) Dacă v.a. ξ are densitate de probabilitate, se spune că ξ este absolut continuă.

Dacă ρ este densitate de probabilitate a v.a. ξ atunci:

1°. , 2°. . x d ) x ( = ) b < a ( Pb

a

ρξ≤ ∫ 1 = x d ) x (

-

ρ∫∞

Denumirea de densitate de probabilitate este justificată de relaţia

hhxxP

x0h

)(lim)( +<ξ<=ρ

→.

Menţionăm că de obicei ρ(x)≠P(ξ=x).

Spunem că v.a. de tip continuu X are repartiţie (distribuţie) normală de

parametri m şi σ2, sau că X are repartiţie N(m,σ2), dacă are densitatea de repartiţie

e2

1 = )m,(x; 2

2

2

)m-(x-2

σπσσρ .

Se spune că o v.a. are repartiţie normală standard dacă are repartiţie N(0, 1).

Pentru astfel de v.a. au loc egalităţile

(x)+21

= F(x) Φ (a)-(b)=F(a)-F(b)=b)<XP(a ΦΦ≤

unde Φ este funcţia lui Laplace (care este tabelată). Dacă X are repartiţie N(0, 1)

atunci σ−= mXY are repartiţie N(0, 1); se spune că Y este normalizata lui X.

Ţinând cont de procedeul de normalizare rezultă că pentru o v.a. cu repartiţie

N(m, σ2) are loc formula

σ

Φ

σ

Φ

σσ

≤σ

≤m-a

-m-b

= m-b

<m-Xm-a

P = b)<XP(a .

Exemplul 15. Se ştie că greutatea la naştere a unui purcel din rasa Bazna

urmează o distribuţie normală de medie m = 1,5 Kg şi o dispersie . Să

se determine :1) probabilitatea să se nască un purcel cu greutatea mai mică

decât 1,6 Kg , 2) probabilitatea să se nască un purcel cu greutatea între 1,2 Kg

şi 1,6 Kg.

025602 ,=σ

Dacă notăm cu X v.a. care ia ca valori greutatea la naştere a purceilor din rasa

Bazna atunci rămâne să determinăm ),( 61XP < şi ),,( 61X21P << . Cum X are

105

Page 100: matematici aplicate

repartiţie N(1,5 ; 0,0256), variabila normalizată 02560

51XY

,,−

= are repartiţie N( 0,1).

Prin urmare

73401062502

16250YP

02560

5161

02560

51XP61XP ,),(),(

,,,

,,),( =Φ+=<=

−<

−=< .

Similar se obţine că :

703620469610234010875162506250Y8751P

06250

5161

06250

51X

06250

5121P61X21P

,,,),(),(),,(

,,,

,,

,,,),,(

=+=−Φ−Φ=<<−

=

−<

−<

−=<< .

Media unei v.a. simple. Fie ξ o v.a. simplă având tabloul de repartiţie

ξ

p ... p p

x ... x x :

n21

n21 .

Se numeşte media v.a. ξ numărul notat M(ξ) definit prin

x p = x p + ... + x p + x p = ) ( M ii

n

1 = nnn2211 ∑ξ .

Media unei v.a. simple are aceleaşi proprietăţi cu media valorilor unei funcţii.

Pentru v.a. continuă ξ cu densitatea de probabilitate ρ, pentru care inte-

grala este absolut convergentă expresia M se numeşte

media (sau speranţa matematică). Media v.a. continue are exact aceleaşi proprie-

tăţi cu media unei v.a. simple cu condiţia ca mediile care apar în formularea

acestor proprietăţi să existe.

∫+∞

∞−

ρ dxxx )( ∫+∞

∞−

ρ=ξ dxxx )()(

În momentul în care media este definită se pot defini în aceiaşi termeni

toate caracteristicile numerice întâlnite la funcţii.

106

Page 101: matematici aplicate

Capitolul VII

PROCESE STOCHASTICE. LANŢURI MARKOV

Una dintre problemele cele mai fireşti ale vieţii de zi cu zi este studiul

evoluţiei în timp a unor sisteme care, sub influenţa unor condiţii exterioare, îşi

pot schimba starea în mod aleator. Un astfel de sistem este orice ecosistem,

orice populaţie, orice oscilator cu oscilaţii întreţinute, etc..

§1. Procese stochastice. Lanţuri şi procese Markov

Fie I(t)ii (t)sS(t)∈

= mulţimea stărilor posibile ale unui sistem Σ la

momentul t. Deşi, de obicei, familia stărilor posibile ale unui sistem Σ variază

continuu în timp vom presupune că schimbările de stare se produc numai la

momente discrete to, t1, …, tn,…pe care le vom nota pentru simplitate cu 0, 1,

…, n,… . Acceptăm deci că sistemul poate fi în fiecare moment n în una dintre

stările 0,1,2,...S(n) =n,(n)s I(n)ii=∈

, iar I(n) este o mulţime de indici cel mult

numărabilă. Evenimentul care constă în faptul că sistemul Σ se află la momentul

n în starea si(n) îl vom nota tot cu si(n). Având în vedere faptul că la fiecare

moment n (n=0,1,2,…) sistemul Σ va lua una şi numai una dintre stările

mulţimii S(n) rezultă că, pentru fiecare n din 0,1,2,…, familia de evenimente

si(n) | i∈I(n), formează un sistem complet de evenimente. Rezultă că fiecărui

moment n îi putem asocia o v.a. Xn care ia ca valori mulţimea S(n) iar ca

probabilităţi pi(n)=P(si(n)), i∈I(n). Se obţine deci un şir (Xn)n∈ù de v.a..

Vom nota cu xn una dintre stările posibile ale sistemului Σ la momentul

n ∈ 0,1,2,….

107

Orice şir de stări xo, x1,…,xn,…se numeşte proces stochastic. Un proces

stochastic este cunoscut probabilistic dacă, pentru fiecare n ∈ 0, 1, 2, …, se

cunoaşte probabilitatea pn ca xn= si(n), i∈I(n). Este firesc să se accepte că,

pentru n≥1, valoarea lui pn este condiţionată de stările sistemului Σ la momentele

anterioare momentului n, adică ..0,1,2,.n(n)),s(xPp inx...xxn 1n1o===

−∩∩∩ ,

Page 102: matematici aplicate

în ipoteza că 1n0,)x...xP(x 1n10 ≥≠∩∩∩ − . Rezultă că

1nIi

==∑∈

∩∩∩ −)(inx...xx (n))s(xP

1n1o.

Dacă sistemul Σ are proprietatea că starea lui la un moment este

condiţionată numai de starea lui la momentul anterior, indiferent de succesiunea

tuturor stărilor anterioare ale sistemului, se spune că mulţimea S(n)| n=0, 1, 2,

3,… a tuturor stărilor posibile ale sistemului formează un lanţ Markov.

Oricare dintre procesele posibile xo, x1,…,xn,… se numeşte proces Markov.

Aceasta înseamnă că

I(n)i(n)),s(xP(n))s(xP inxinx...xx 1n1n1o∈∀===

−−∩∩∩ .

Prin urmare, un proces Markov este un proces stochastic pentru care

probabilitatea ca sistemul să intre într-o stare depinde numai de starea

precedentă în care s-a aflat, nu de evoluţia anterioară (istoria) a procesului. Prin

urmare, probabilitatea de a trece din starea si în starea sj este aceeaşi fie că se

referă la probele 2 şi 3 fie la probele 121 şi 122.

Exemplul 1. Dacă o urnă conţine 10 bile albe şi 12 bile negre şi se fac

22 extrageri fără revenire, probabilitatea ca la extragerea 7 să obţinem bilă albă

depinde de toate extragerile precedente, deci rezultatul tuturor extragerilor va fi

un proces stochastic dar nu va fi un proces Markov.

Exemplul 2. Într-o populaţie dialelică indivizii sunt clasaţi după

genotipul lor (independent de sex) : AA, Aa, aa. Apariţia unui individ de un

anumit genotip într-o anumită generaţie depinde numai de starea (structura)

populaţiei din generaţia precedentă, deci starea (structura) populaţiei la o

anumită generaţie depinde numai de starea (structura) populaţiei din generaţia

precedentă. Se obţine astfel un exemplu de lanţ Markov asociat mulţimilor

stărilor generaţiilor populaţiei. Considerăm mulţimea formată alegând câte un

singur individ din fiecare generaţie. Mulţimea genotipurilor acestor indivizi

este un exemplu de proces Markov.

Un lanţ Markov (respectiv, un proces Markov) se numeşte finit sau

infinit după cum şirul care-l defineşte are sau nu un număr finit de termeni.

În cele ce urmează ne vor interesa lanţuri şi procese Markov pentru care

fiecare S(n) are un număr finit de elemente. Pentru a simplifica expunerea vom

considera că

108

Page 103: matematici aplicate

S(n)=S=s1,s2,…sr ∀ n ∈ 0, 1, 2, ….

Ca exemplu serveşte lanţul Markov asociat situaţiei din Exemplul 2, în care

fiecare S(n)=AA, Aa, aa, n ∈ 0, 1, 2, ….

Dacă pi(n)=P(xn=si) şi pj(n+1)=P(xn+1=sj) atunci probabilitatea pij(n)

de trecere de la starea si la momentul n la starea sj la momentul n+1 este

. )s(xP(n)p j1nsxij in== +=

Dacă matricea de trecere este independentă de n vom spune că lanţul Markov

este omogen. În caz contrar, lanţul Markov se va numi neomogen.

Pentru un lanţ Markov omogen, matricea de trecere este constantă şi o

vom nota cu [ , adică ]τ

[ ]

nn2n1n

n22221

n11211

ppp

ppp

ppp

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

.......

.......

.

În acest caz

[ ] [ ] [ ] ,...,,,)()( 210n0pnp n =τ⋅= [ ] [ ] 21nn

21 nnnn 12 <τ=τ −),( .

Prin urmare, pentru un lanţ Markov omogen, probabilitatea ca sistemul

să treacă din starea i în starea j după m momente (transformări) este elementul

(i, j) al matricei [ ] . mτ

§7. Aplicaţii în Genetică Se ştie că un caracter (o trăsătură) este guvernat de două gene care apar în două

tipuri (alele): un tip dominant (d) şi un tip recesiv (r). Un individ poate fi de tip

D=dd (pur dominant), H=rd=dr (hibrid) sau R=rr (pur recesiv). Dacă doi

indivizi se încrucişează urmaşii iau câte o genă de la fiecare părinte (reprodu-

cerea diploidă), dar alegerea genelor este aleatoare.

Aplicaţia 1. Încrucişarea continuă cu un hibrid

Presupunem că un individ de genotip arbitrar se încrucişează cu un

hibrid iar urmaşul este încrucişat tot cu un hibrid, ş. a. m. d.. Se obţine deci un

exemplu de proces Markov. Situaţia este descrisă în următoarele diagrame:

109

Page 104: matematici aplicate

dd

½

r r

Rezultă că ma

Deoarece

Frobenius [p]=

2τ][

Se obţine [p]=

iniţiali, 25% d

vor fi dominan

Aplica Realiză

încrucişarea cu

este

Există o clasă

R). Rezultă

numărul de g

matricea funda

dd-d

½ ¼¼

tricea de t

rezu

[p

0>

1 p2 p

[¼ ½ ¼

in urmaş

ţi în dom

ţia 2. Înc

m acelaş

un dom

absorban

că în ti

eneraţii

mentală

M

dr dd

recere a ace

=τ][

ltă că lanţu

3] se determ

==

=

1

2

11

p1

p

p

], adică în

i vor fi pur

inanţă comp

rucişare cu

i experimen

inant pur. M

=τ][

tă (clasa D

mp, urmaşi

după care

=−= −Q1 1)(

r

stui proces Ma

21

21

41

21

41

21

21

0

0

R

H

D

RHD

l Markov est

ină rezolvând

( )++

++

+

32

32121

241

12

pp

ppp

pp

.

timp, indepen

dominanţi, 50

letă) şi 25% v

un dominant

t ca mai sus, d

atricea de trec

010

0

001

R

H

D

RHD

21

21

) şi două clas

i vor fi pur d

urmaşii sunt t

=

R

H

11

0R

H

HRH

12

1

110

½½

rr rd

rkov este

e regulat. V

sistemul

dent de geno

% vor fi hibr

or fi vor fi pu

ar de această

ere a acestui

e de tranziţie

ominanţi. Pe

oţi pur domi

12

02

R

ectorul Perron-

tipul indivizilor

izi (adică 75%

r recesivi.

dată vom face

proces Markov

(clasele H ş

ntru a calcula

nanţi calculăm

dr-d

dr-rr

rr

i

Page 105: matematici aplicate

111

Dacă individul iniţial este hibrid, numărul mediu de generaţii este suma ele-

mentelor primei linii, adică este 2; dacă individul iniţial este recesiv, numărul

mediu este suma elementelor liniei a doua, adică este 3. În ultimul caz va fi în

medie un recesiv şi doi dominanţi înainte ca dominanţa să se instaleze.

Page 106: matematici aplicate

BIBLIOGRAFIE

1. I. Burdujan - Matematici cu aplicaţii în Biologie, Ed. „Ion Ionescu de la

Brad”, 1999

2. I. Burdujan - Elemente de Matematici cu aplicaţii în Biologie, Ed.

„Vasiliana’98”, 2001

3. I. Burdujan - Capitole de Matematici aplicate(pentru biologi), Ed.

„Vasiliana’98”, 2002

4. I. Burdujan - Matematici cu aplicaţii în Biologie, Ediţia a 2-a, Ed. Pim,

2002

5. M. Micula – Matematici aplicate în agronomie, Casa de editură

TRANSILVANIA PRESS, CLUJ-NAPOCA 1997

6. L. Răileanu – Matematici cu aplicaţii în Biologie, Rotaprint Univ. „Al. I.

Cuza” Iaşi, 1978

7. L. Răileanu –Tabele statistice, Rotaprint Univ. „Al. I. Cuza” Iaşi, 1978

8. V. Tamaş, ş.a. – Matematici generale pentru economişti, Ed. Graphix, Iaşi,

1993

9. V. Tamaş, ş.a. – Modele matematic în Economie, Ed. Graphix, Iaşi, 1995

Page 107: matematici aplicate

An univ. 2002-2003 Temă ID-Zootehnie

1. Folosind lema substituţiei, determinaţi soluţia sistemului

=+++−=+

=++−+=+

=++−+

13632567

84365

9432

54321

51

54321

51

54321

xxxxxxx

xxxxxxx

xxxxx

.

Care este valoarea determinantului matricei coeficienţilor necunoscutelor? 2. Folosind lema substituţiei, determinaţi soluţia generală a sistemului

−=+−+−=−+−+−

=−+−+=−+++

134327325

1222142342

54321

54321

54321

54321

xxxxxxxxxx

xxxxxxxxxx

.

3. Folosind lema substituţiei determinaţi

a) inversa matricei ,

−−−

−−−−

=

1111121111111111

A

b) rangul matricei .

−−−−

=

302111311011121110010121

A

4. Determinaţi soluţia optimă a problemei

≥≥≥≥≥

−≤−−=+−≤−−

+++

0,0,0,0,032

232

)2(min

54321

542

543

321

5421

xxxxxxxxxxxxxx

xxxx

.

5. Rezolvaţi problema de transport corespunzătoare tabelului

B1 B2 B3 B4 si F1 4 1 5 6 21 F2 3 5 2 4 29 F3 7 2 1 3 30 bj 14 28 16 20

Folosiţi pe rând ca soluţie iniţială soluţia determinată respectiv prin meto-da colţului de Nord-Vest, metoda minimelor pe linii şi metoda minimului

Page 108: matematici aplicate

pe tabel. Îmbunătăţiţi soluţia atât prin algorimul pe bază de cicluri cît şi prin algoritmul dual. 6. Determinaţi fluxul maxim şi secţiunea minimă în reţeaua de transport redusă desenată mai jos.

x5

(12)

(8)

(14)

(5)

(3)

(9) (11) o (8)

(7) o o

(22)

)(23)

(7)

(4)

(13)

(16)

(17)

o o o o o o

8

7

4

x3

2

6

1 x9

7. Determinaţi un drum de lungime maximă între vîrfurile x1 şi x8 ale grafului:

o o o o o o o o

3 -7

5

8

x7

x3 x2 x4

6-9

2

4

4

45

5

x6 9x5

x8 x1

8. S-au numărat boabele ladin tabelul de mai jos Nr. boabe 51 56 50 Nr. spice 4 9 8 Calculaţi: a) frecvenţele absoluteasimetrie Pearson şi Fisher, c) coecoeficientul de variabilitate Pearso

9. Lungimea corpului xi şi

sunt prezentate în tabelul următor:xi 145 146 148 148 150 150 yi 66 71 67 68 65 65

... 161 161 163 165 69 73 69 69

Să se determine dreapta de regresugerului şi dreapta de regresie a adâDeterminaţi apoi diferenţele dintrbaza dreptelor de regresie.

-

40 sp

54 2

simpleficientun.

adâncim 151 1569 7

1

ie a lunncimii ue valor

-

ice

şil de

ea

1 0

68 71 gimgerile

-

de grâu

59 4

cumula boltire ş

ugerului

154 15567 71

16968

ii corpuului asupmăsurat

-

4

t

e

7

x

x

x

ş

6

x

x

x

(15

i s-au obţinut datele

0 57 58 3 8 2 e, b) coeficienţii de i cel da aplatizare, d)

yi la 22 vaci de lapte

157 158 159 159 71 70 70 73

169 176 74 74 lui asupra adâncimii ra lungimii corpului. şi cele estimate pe

Page 109: matematici aplicate

10. Se dau două urne identice la exterior. Una conţine 3 bile albe şi 4 bile negre, iar cealaltă conţine 5 bile albe şi 2 bile negre. Din una dintre aceste urne, aleasă la întâmplare, se extrage o bilă. Dacă bila extrasă este albă, care este probabilitatea ca ea să provină din urna cu primul tip de compoziţie?