Lezioni di Ricerca Operativa
Corso di Laurea in Informatica ed Informatica Applicata
Università di Salerno
Lezione n° 3: 10-11 Marzo 2009
Richiami di Algebra vettoriale:
- Matrici ed Operazioni tra matrici
- Inversa di una matrice
- Risoluzione di un sistema di equazioni lineari
- Metodo di Gauss- Jordan
Anno Accademico 2008/2009
Prof. Cerulli – Dott.ssa Gentili
Matrici: Notazione (1/2)
1 4 5

A  2 7 2
3 3 3

2

3
1 
generico elemento aij
della matrice nella riga
i e nella colonna j
A è una matrice (3x4)
num. di righe
num. di colonne
A   aij 
mxn
Matrici: Notazione (2/2)
1 4 5

A  2 7 2
3 3 3

2

3
1 
a1
a2
a3
a1 a2 a3
a4
A si può indicare anche come insieme di vettori riga:
A=(a1,, a2, a3)
Oppure come insieme di vettori colonna:
A=(a1, a2, a3, a4)
Addizione tra matrici
A   aij 
mxn
A B  C
B   bij 
mxn
C   cij 
mxn
cij  aij  bij
i  1,...,m j  1,...,n
Condizione necessaria:
le matrici devono avere le stesse dimensioni
Moltiplicazione per uno scalare
A   aij 
mxn
k
scalare
k A   kaij 
matrice (mxn)
Moltiplicazione tra matrici
A   aij 
mxn
B   bij 
nxp
Condizione necessaria
n
cij   aik bkj
k 1
Ciascun elemento di C è il
prodotto interno di una
riga di A ed una colonna
di B
i  1,...,m j  1,...,p
Moltiplicazione tra matrici
Esempio
 1 -1 1 


A  4 - 2 5
3x 3
2 0 1 


5 0


B  3 0 
3x 2
1 1


3

C  AB  19
3x2
11

1

5
1
Moltiplicazione tra matrici
 
Da ricordare: A  aij
mxn
B   bij 
qxp
1. Il prodotto AB è definito solo se n=q. AB è allora una
matrice mxp
2. Il prodotto BA è definito solo se m=p. BA è allora una
matrice qxn
3. NON necessariamente vale la proprietà COMMUTATIVA
Alcune matrici particolari
 1 0 0 ... 0
 0 1 0 ... 0

I   0 0 1 ... 0
nxn
 ....

 0 0 0 ...1
 a11
 0

A  0
nxn


 0







a12 a13 ... a1n
a 22 a 23... a 2n
0 a 33... a 3n
....
0 0 ... a nn
Matrice Identita’
A I A
mxn nxn
I AA
mxm mxn







Matrice Triangolare
superiore
Trasposta di una matrice
Data una matrice A= { aij } (mxn) , la sua matrice
TRASPOSTA At è una matrice (nxm) ottenuta invertendo le
righe con le colonne:
5 0


A  3 0 
3x 2
1 1


5 3 1
A 

2 x3
0 0 1
t
Trasposta di una matrice
Proprietà
1.
(A )  A
2.
( A  B)  A  B
3.
( AB)  B A
t t
t
t
t
t
t
t
(quando la somma è definita)
(quando il prodotto è definito)
Matrici partizionate
Una matrice A (mxn) possiamo anche vederla partizionata in
sottomatrici.
 a11
a
 21
A 
4x4
 a 31
 a 41
a12 a13 a14 
a 22 a 23 a 24 

a 32 a 33 a 34 
a 42 a 43 a 44 
 A11 A12 
A 

4x4
 A 21 A 22 
A11
 a11
a
 21
A 
4x4
 a 31
 a 41
A21
A11 A12
A21 A22
a12 a13 a14 
a 22 a 23 a 24 

a 32 a 33 a 34 
a 42 a 43 a 44 
A12
A22
hanno dimensione 3x2
hanno dimensione 1x2
Operazioni elementari
Data una matrice A (mxn) è possibile definire alcune operazioni
sulle righe e sulle colonne utili a risolvere un sistema di
equazioni lineari.
Operazioni elementari sulle righe (colonne) di una matrice sono:
- SCAMBIO: scambio della riga i con la riga j
- MOLTIPLICAZIONE: moltiplicazione di una riga per uno scalare
- SOSTITUZIONE: sostituzione della riga i con la somma della
riga i e della riga j moltiplicata per uno scalare
Risolvere un sistema di equaz. Lineari
attraverso operazioni elementari
Dato un sistema di m equazioni lineari ed n incognite
Ax  b
matrice dei coefficienti di
dimensione (mxn)
vettore dei termini noti
di dimensione (mx1)
Vettore delle incognite
di dimensione (nx1)
è equivalente al sistema:
dove la matrice
A' x  b'
( A' , b' )
è ottenuta da
( A, b)
attraverso un numero finito di operazioni elementari
Risolvere un sistema di equaz. Lineari
attraverso operazioni elementari
2 x1  x2  x3  10
 x1  2 x2  x3  8
x1  x2  2 x3  2
1
1
x1  x2  x3  5
2
2
2
26
x2  x3 
3
5
x3  2
2 1 1 10


( A, b)  - 1 2 1 8 
1 - 1 2 2 



1


( A' , b' )  0

0


1 1
2 2
2
1
3
0 1

5

26 

5
2


Inversa di una matrice
Sia
A
una matrice quadrata, se esiste
nxn
B
matrice quadrata tale che
nxn
AB  I
BA  I
B è detta matrice inversa di A
Ricorda:
- l’inversa di una matrice A (se esiste) è UNICA ed è indicata con A-1
- se una matrice ammette un’inversa allora è detta matrice
NON SINGOLARE
- una matrice è non singolare se e solo se le rige sono linearmente
indipendenti o equivalentemente se e solo se le colonne sono
linermente indipendenti
Calcolo dell’inversa di una matrice
L’inversa di una matrice quadrata A può essere calcolata
attraverso un numero finito di operazioni elementari nel seguente
modo:
1. Si considera la nuova matrice (A,I)
2. Si effettuano una serie di operazioni elementari sulle
righe e sulle colonne di questa nuova matrice in modo
tale che:
A diventa la matrice identità I
I diventa la matrice inversa A-1
Calcolo dell’inversa di una matrice
esempio (1/3)
2 1 1 


A  - 1 2 1 
 1 -1 2 


 2 1 1 1 0 0


- 1 2 1 0 1 0 
 1 -1 2 0 0 1 


Considero la nuova matrice
Divido la prima riga per 2.
Aggiungo la nuova riga ottenuta
alla seconda.
Sottraggo la riga ottenuta dalla
terza

1


0


0

1
2
5
2
3
2
1
2
3
2
3
2
1

0 0 
2

1

1 0 
2

1

- 0 1 
2

Calcolo dell’inversa di una matrice
esempio (2/3)

1


0


0
1
2
5
2
3
2
1
2
3
2
3
2
1

0 0 
2

1

1 0 
2

1

- 0 1 
2


1


0


0
1
0
5
3
1
5
12
0
5
2 1

- 0 
5 5

1 2

0 
5 5

1

0 1 
5

Moltiplico la seconda riga per 2/5.
Moltiplico la nuova riga ottenuta per -1/2 e la aggiungo alla
prima riga.
Moltiplico la nuova riga ottenuta per 3/2 e la aggiungo alla
terza riga.
Calcolo dell’inversa di una matrice
Esempio (3/3)

1


0


0

1
2
1

0
0 
5
5
5

3
1
2

1
0 
5
5
5

12 1

0
0 1 
5 5


1


0


0
5
3
1 
0 0
12 12 12 

3
3
3 
1 0

12 12 12 
1
3 5 
0 1 12 12 12 
Moltiplico la terza riga per 5/12.
Moltiplico la nuova riga ottenuta per -3/5 e la aggiungo alla
seconda riga.
Moltiplico la nuova riga ottenuta per -1/5 e la aggiungo alla
prima riga.
Quindi l’inversa in questo caso esiste
Inversa di una matrice
Proprietà:
1. Se A è non singolare  At è non singolare e vale:
(At)-1 = (A-1)t
2. Se A e B sono matrici quadrate (nxn) non singolari allora AB
è matrice non singolare e
(AB)-1= B-1A-1
Rango di una matrice
Rango di riga: numero massimo di righe lin. indipendenti
Rango di colonna: numero massimo di colonne lin. indipendenti
Teorema: Rango di riga = Rango di colonna
Rango (A)  min (m,n)
Se rango (A) = min (m,n) A è una matrice a rango pieno
Rango di una matrice e sistema di
equazioni lineari (1/2)
Cercare una soluzione ad un sistema di equazioni lineari
A xb
m xn
Significa cercare quei valori x1, x2, …, xn tali che il vettore b può
essere espresso come combinazione lineare delle colonne della
matrice.
Per la soluzione di un sistema di equazioni lineari valgono le seguenti:
1. Rango(A,b) > Rango(A)
 il sistema non ha soluzione
2. Rango(A,b) = Rango(A)
 il sistema ha soluzione
Rango di una matrice e sistema di
equazioni lineari (2/2)
Rango(A,b) = Rango(A)
m>n :
Rango(A) ≤ min(m,n)
Rango(A) ≤ n <m
Se Rango(A) = n  il sistema ha soluzione unica
Se Rango(A) < n  il sistema ha infinite soluzioni
m<n :
Rango(A) ≤ min(m,n)
Rango(A) ≤ m <n
Se Rango(A) = m  il sistema ha infinite soluzioni
Se Rango(A) < m  il sistema ha infinite soluzioni
m=n:
Rango(A) ≤ min(m,n)
Rango(A) ≤ n =m
Se Rango(A) = n  il sistema ha soluzione unica
Se Rango(A) < n  il sistema ha infinite soluzioni
Risolvere un sistema di equazioni lineari
x1  2 x2  x3 - 2 x4  10
 x1  2 x2  x3  x4  6
x 2  x3
La matrice dei coefficienti
ha rango =3 < 4
2
il sistema ha infinite
soluzioni
Metodo di Gauss-Jordan:
ridurre la matrice dei coefficienti ad una matrice
triangolare superiore attraverso un numero finito
di operazioni elementari
Risolvere un sistema di equazioni lineari
Metodo di Gauss-Jordan
x1  2 x2  x3 - 2 x4  10
 x1  2 x2  x3  x4  6
x 2  x3
2
Aggiungi la prima riga alla
seconda riga.
Dividi la seconda riga per 4.
Sottrai la nuova riga ottenuta
alla terza riga.
 1 2 1 - 2 10 


- 1 2 - 1 1 6 
0 1 1 0 2 


 1 2 1 - 2 10 


 0 4 0 - 1 16 
0 1 1 0 2 




 1 2 1 - 2 10 


1


4 
0 1 0 4


1


0
0
1
2


4
Risolvere un sistema di equazioni lineari
Metodo di Gauss-Jordan
x1  2 x2  x3 - 2 x4  10
 x1  2 x2  x3  x4  6
x 2  x3
2
infinite soluzioni al sistema:
x4  
1
x 3  2  
4
1
x2  4  
4
7
x1  10  2  2 x2  x3  4  
4


 1 2 1 - 2 10 


1


0
1
0
4


4


1


0
0
1
2


4