Model d’examen de problemes

1. a) Siguin A, B, M matrius quadrades d’ordre n tals que AM = B. Si A i B són matrius triangulars superiors i no nul·les, es pot assegurar que M és també triangular superior? Si no és així, quina condició hem d’incloure per garantir que M és triangular superior? Raoneu les respostes.

b) Una matriu quadrada M es diu idempotent quan M^{2} = M. Si A i B són matrius quadrades que verifiquen A = AB i B = BA, proveu que A i B són idempotents.

2. Donada la matriu

A = ( 0 2_{\frac{−1}{4} \frac{3}{2}} )

a) Demostrau que A és invertible i calculau la seva matriu inversa A^{−1}

b) Si M = I − A, Calculau M^{2}

c) Determinau k de manera que es compleixi M^{2} = kM

d) Calculau l’expressió de M^{n} , per tot n ∈ IN

3. Sigui a un nombre real, f_{a} un endomorfisme f_{a} : IR^{3} ⟶ IR^{3} tal que f_{a} està definit per f_{a}(1, 0, 0) = (a, 1, 3), f_{a}(0, 1, 0) = (1, 3, 10) i f_{a}(0, 0, 1) = (−1, 1, 4)

a) Trobau els valors de a en què Nuc f_{a} ≠ {0}.

b) Trobau una base de la Im f_{a} i del nucli per a cada un d’aquests valors.

c) Trobau la matriu de f en la base (1, 1, 1), (0, 1, 2), (0, 2, 1) de IR^{3}.

4. Una empresa farmacèutica multinacional subministra cada mes exactament 130000 vacunes entre els seus filials de París, Roma i Londres, i com a màxim aquest mes ha de subministrar 90000 vacunes a París, 70000 vacunes a Roma i 80000 vacunes a Londres. Determinau el cost mínim del transport, sabent que el cost del transport per vacuna és de 1 u.m. a París, 2 u.m. a Roma i 5 u.m. a Londres, amb unes despeses fixes mensuals de 1950000 u.m.

Cercau la solució gràficament i mitjançant el mètode del símplex.

Solució al model anterior

Problema 1 (a) Si | A |≠ 0, la matriu A té inversa i tindríem:

M = A^{−1} · B

ara bé, com que la inversa d’una matriu triangular superior és triangular superior, i el producte de dues matrius triangulars superiors és triangular superior, deduïm que M és triangular superior (de manera anàloga es faria el mateix raonament en el cas en que les matrius fossin triangulars inferiors). Per altra part, el determinant d’una matriu triangular (superior o inferior) és el producte dels elements de la diagonal principal, aleshores si tots els elements de la diagonal principal són diferents de zero la matriu A tindrà inversa i, per tant, M serà triangular. Però, si hi ha qualque element de la diagonal principal diferent de zero, M no té per què ser triangular. Per exemple:

( \begin{matrix}1 & 1 \\ 0 & 0 \end{matrix} ) · ( \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ) = ( \begin{matrix}2 & 2 \\ 0 & 0 \end{matrix} )

(b) A^{2} = (A · B)^{2} = A · B · A · B. Però com que B = B · A, tenim que A^{2} = A · B · B, i com que A = A · B, substituint tenim A^{2} = A · B = A. De manera totalment anàloga veuríem que B és idempotent.

Problema 2 (a) És invertible ja que | A |= \frac{1}{2} ≠ 0. Per calcular la inversa farem:

( \begin{matrix}0 & 2 \\ − \frac{1}{4} & \frac{3}{2} \end{matrix} ) → (T ransposada) ( \begin{matrix}0 & − \frac{1}{4} \\ 2 & \frac{3}{2} \end{matrix} ) → (Adjunta) ( \begin{matrix}\frac{3}{2} & −2 \\ \frac{1}{4} & 0 \end{matrix} )

per tant, la matriu inversa és

A^{−1} = 2 ( \begin{matrix}\frac{3}{2} & −2 \\ \frac{1}{4} & 0 \end{matrix} ) = ( \begin{matrix}3 & −4 \\ \frac{1}{2} & 0 \end{matrix} )

(b)

M = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) − ( \begin{matrix}0 & 2 \\ − \frac{1}{4} & \frac{3}{2} \end{matrix} ) = ( \begin{matrix}1 & −2 \\ \frac{1}{4} & − \frac{1}{2} \end{matrix} )

i, per tant,

M^{2} = ( \begin{matrix}1 & −2 \\ \frac{1}{4} & − \frac{1}{2} \end{matrix} ) · ( \begin{matrix}1 & −2 \\ \frac{1}{4} & − \frac{1}{2} \end{matrix} ) = ( \begin{matrix}\frac{1}{2} & −1 \\ \frac{1}{8} & − \frac{1}{4} \end{matrix} )

(c) És immediat veure que k = \frac{1}{2}.

(d) Tenim que M^{2} = \frac{1}{2}M multiplicant els dos membres per M tenim

M^{3} = \frac{1}{2}M^{2} = \frac{1}{2} · \frac{1}{2}M = ( \frac{1}{2})^{2} M

i si repetim aquest procés tindrem:

M^{4} = ( \frac{1}{2})^{3} M,  M^{5} = ( \frac{1}{2})^{4} M,  …

en definitiva

M^{n} = (\frac{1}{2})^{n−1} M = (\frac{1}{2})^{n−1} ( \begin{matrix}1 & −2 \\ \frac{1}{4} & − \frac{1}{2} \end{matrix} ) = ( \begin{matrix}(\frac{1}{2})n−1 & − (\frac{1}{2})^{n−2} \\ (\frac{1}{2})n+1 & − (\frac{1}{2})^{n} \end{matrix} )

Problema 3

(a) Cercarem primer la matriu associada a f_{a} respecte a la base canònica i que és:

A = ( \begin{matrix}a & 1 & −1 \\ 1 & 3 & 1 \\ 3 & 10 & 4 \end{matrix} )

El nucli està format per tots els vectors (x, y, z) que compleixen l’equació:

( \begin{matrix}a & 1 & −1 \\ 1 & 3 & 1 \\ 3 & 10 & 4 \end{matrix} ) · ( \begin{matrix}x \\ y \\ z \end{matrix} ) = ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} )

i aquesta equació tindrà solució única si i només si el rang de la matriu és 3. Per tant, Nuc f_{a} ≠ {0} quan rangA < 3, i això es compleix quan

| \begin{matrix}a & 1 & −1 \\ 1 & 3 & 1 \\ 3 & 10 & 4 \end{matrix} | = 2a − 2 = 0

és a dir, quan a = 1.

(b) Cerquem primer una base de Nuc f_{1} per això resoldrem per Gauss l’equació matricial anterior per a = 1:

( \begin{matrix}1 & 1 & −1 \\ 1 & 3 & 1 \\ 3 & 10 & 4 \end{matrix} ) ∼ ( \begin{matrix}1 & 1 & −1 \\ 0 & 2 & 2 \\ 0 & 7 & 7 \end{matrix} ) ∼ ( \begin{matrix}1 & 1 & −1 \\ 0 & 2 & 2 \\ 0 & 0 & 0 \end{matrix} )

i ens queden les equacions x + y − z = 0, 2y + 2z = 0 que té per solucions x = 2z i y = −z. Per tant, un element de Nuc f_{1} tindrà la forma

(2z, −z, z) = z(2, −1, 1)

i Nuc f_{1} =< (2, −1, 1) >. Un sistema generador de Im f_{1} estarà format per les imatges dels elements de la base canònica: Im f_{1} =< (1, 1, 3), (1, 3, 10), (−1, 1, 4) >. Per cercar els vectors linealment independents triangularitzarem la matriu formada per aquest vectors

( \begin{matrix}1 & 1 & 3 \\ 1 & 3 & 10 \\ −1 & 1 & 4 \end{matrix} ) ∼ ( \begin{matrix}1 & 1 & 3 \\ 0 & 2 & 7 \\ 0 & 2 & 7 \end{matrix} ) ∼ ( \begin{matrix}1 & 1 & 3 \\ 0 & 2 & 7 \\ 0 & 0 & 0 \end{matrix} )

que ens dóna per resultat que Im f_{1} =< (1, 1, 3), (0, 2, 7) > essent {(1, 1, 3), (0, 2, 7)} una base de Im f_{1}.

(c) La matriu de f_{1} respecte a la nova base serà:

A′ = P^{−1} · A · P

on P és la matriu de canvi de base de les antigues (base canònica) a les noves.

P = ( \begin{matrix}1 & 0 & 0 \\ 1 & 1 & 2 \\ 1 & 2 & 1 \end{matrix} ) i P^{−1} = −\frac{1}{3} ( \begin{matrix}−3 & 0 & 0 \\ 1 & 1 & −2 \\ 1 & −2 & 1 \end{matrix} )

Aleshores

A′ = −\frac{1}{3} ( \begin{matrix}−3 & 0 & 0 \\ 1 & 1 & −2 \\ 1 & −2 & 1 \end{matrix} ) · ( \begin{matrix}1 & 1 & −1 \\ 1 & 3 & 1 \\ 3 & 10 & 4 \end{matrix} ) · ( \begin{matrix}1 & 0 & 0 \\ 1 & 1 & 2 \\ 1 & 2 & 1 \end{matrix} ) = ( \begin{matrix}1 & −1 & 1 \\ \frac{28}{3} & \frac{32}{3} & \frac{40}{3} \\ −\frac{8}{3} & −\frac{7}{3} & −\frac{11}{3} \end{matrix} )

Problema 4 Plantegem el problema. Per això diguem x al nombre de vacunes subministrades a la sucursal de París, y a Roma i z a Londres. Les restriccions són

x +y +z = 130000
x  ≤ 90000
y  ≤ 70000
z ≤ 80000

amb totes les variables no negatives. La funció a optimitzar(minimitzar) és

Cost = x + 2y + 5z + 1950000

Una de les restriccions és una igualtat. Per tant, podem posar una de les variables, z per exemple, en funció de les altres dues. Així aconseguirem un problema de programació lineal amb dues variables que podem resoldre gràficament. Vegem com queda el problema:

Minimitzar

Cost = x + 2y + 5(130000 − x − y) + 1950000 = −4x − 3y + 1300000

amb les restriccions

x  ≤ 90000
y  ≤ 70000
z ≤ 80000 ⟺ 130000 − x − y ≤ 80000 ⟺ x + y ≥ 50000
z ≥ 0  ⟺ 130000 − x − y ≥ 0  ⟺ x + y ≤ 130000

amb totes les variables no negatives.

Per resoldre’l, representem-ho gràficament

[figure: y = 70000; x + y = 50000; x + y = 130000; x = 90000; P; Q; R; S; T; U]

La zona factible de solucions és la zona ratllada. Sabem que la solució es troba en un dels vèrtexs P(0,50000), Q(0,70000), R(50000,0), S(90000,0), T(90000,40000) o U(60000,70000). Com que es tracta d’un mínim amb valors positius, calculem on es troba aquest mínim

C_{P} = 4 · 0 − 3 · 50000 + 1300000 = 1150000
C_{Q} = 4 · 0 − 3 · 70000 + 1300000 = 1090000
C_{R} = 4 · 50000 − 3 · 0 + 1300000 = 1100000
C_{S} = 4 · 90000 − 3 · 0 + 1300000 = 940000
C_{T} = 4 · 90000 − 3 · 40000 + 1300000 = 820000
C_{U} = 4 · 60000 − 3 · 70000 + 1300000 = 850000

El mínim es troba, doncs, en el punt U, amb valor 850000. Llavors, caldria subministrar 90000 vacunes a París, 40000 a Roma i z = 130000 − 90000 − 40000 = 0 vacunes a Londres perquè tingui el mínim cost, que és de 820000 u.m. en el problema equivalent. En el problema original el mínim s’agafa en els mateixos valors però amb valor

z = 90000 + 2 · 40000 + 5 · 0 + 1950000 = 2120000 u.m.

Facem ara el problema mitjançant el mètode del símplex. Podem usar el planteig del problema amb tres variables. En primer lloc transformem el problema en un problema de programació lineal en forma estàndard. Per això diguem x_{1} a x, x_{2} a y i x_{3} a z. La funció a optimitzar és trobar el mínim de z = x_{1} + 2x_{2} + 5x_{3} + 1950000, que, a l’efecte d’aplicació del mètode del símplex, ens és suficient usar z = x_{1} + 2x_{2} + 5x_{3}.

Vegem les restriccions. La primera restricció és una igualtat; per tant, no cal afegir, de moment, cap variable nova. Afegim-hi les variables compensatòries a la resta de restriccions. A la segona, tercera i quarta inequació hem d’afegir una variable x_{4}, x_{5} i x_{6} sumant, perquè tenim un “menor o igual” a totes elles. Ens queda:

Minimitzar: z = x_{1} + 2x_{2} + 5x_{3}
amb restriccions: x_{1}+ x_{2} +x_{3}  = 130000
x_{1}+  +x_{4}  = 90000
x_{2}  +x_{5}  = 70000
x_{3}  +x_{6} = 80000

Després, hem d’afegir una variable artificial, x_{7}, a la primera equació per tenir una solució bàsica factible. Per tant, el problema en forma estàndard, reordenant les equacions, serà

Minimitzar: z = x_{1} + 2x_{2} + 5x_{3} + Mx_{7}
amb restriccions: x_{1}+  +x_{4}  = 90000
x_{2}  +x_{5}  = 70000
x_{3}  +x_{6}  = 80000
x_{1}+ x_{2} +x_{3}  x_{7} = 130000

Ara ja estem en disposició de fer la primera taula del símplex. Aquesta és

c_{1}  c_{2}  c_{3}  c_{4} c_{5} c_{6} c_{7}
c^{B} x^{B}(×10^{4})  y_{1}  y_{2}  y_{3}  y_{4} y_{5} y_{6} y_{7} Qc.(×10^{4})
0  x_{4} = 9  1  0  0  1 0 0 0  \frac{9}{1} = 9 → x_{4}
0  x_{5} = 7  0  1  0  0 1 0 0  \frac{7}{0} = ∞
0  x_{6} = 8  0  0  1  0 0 1 0  \frac{8}{0} = ∞
M x_{7} = 13  1  1  1  0 0 0 1  \frac{13}{1} = 13
z = 13M M − 1 M − 2 M − 3 0 0 0 0
↑ x_{1}

on

c_{1} = 1 c_{2} = 2 c_{3} = 5 c_{4} = 0 c_{5} = 0 c_{6} = 0 c_{7} = M

Primer ens hem d’assegurar que aquesta solució és millorable, ja que si no és així ja hem acabat el problema. Veiem que els elements de l’última fila positius no tenen la resta de la columna negativa o zero; per tant, es pot millorar la solució.

El valor major de l’última fila és M − 1. Llavors entra la variable x_{1}. El valor menor dels quocients de l’última columna correspon a \frac{90000}{1}. Per tant, surt x_{4}. Pivotarem, doncs, sobre l’element a_{11} = 1, que és

l’element requadrat.

La primera passa per obtenir la següent taula del símplex és dividir tota la fila de l’element que surt per l’element pivot per obtenir un 1. Com que ja ho és, ho deixem així. Després aconseguirem zeros (usant les operacions de Gauss, per exemple) a tota la columna de l’element que entra. Per això farem les operacions següents: 4a fila - 1a fila i 5a fila-1a fila·(M − 1). La taula queda:

c^{B} x^{B} (×10^{4}) y_{1}  y_{2}  y_{3}  y_{4}  y_{5} y_{6} y_{7} Qc.(×10^{4})
1  x_{1} = 9  1  0  0  1  0 0 0  \frac{9}{0} = ∞
0  x_{5} = 7  0  1  0  0  1 0 0  \frac{7}{1} = 7
0  x_{6} = 8  0  0  1  0  0 1 0  \frac{8}{0} = ∞
M  x_{7} = 4  0  1  1  −1  0 0 1  \frac{4}{1} = 4 → x_{7}
z = 4M + 9 0 M − 2 M − 3 −M + 1 0 0 0
↑ x_{2}

Veiem que z_{2} −c_{2} > 0 i z_{3} −c_{3} > 0 amb les components de la resta de la columna no negatives, la qual cosa significa que la solució obtinguda és millorable. Llavors procedirem a obtenir la següent taula del símplex. La major d’aquestes diferències és z_{2} − c_{2}, per tant entra x_{2}. Vegem que surt x_{7} perquè és la variable que té quocient mínim. Això significa que pivotem sobre l’element requadrat. Per obtenir la tercera taula només farem 2a fila - 4a fila i 5a fila - 4a fila·(M − 2), perquè ja tenim un 1 a l’element pivot. La taula queda

c^{B}  x^{B}  y_{1} y_{2} y_{3} y_{4} y_{5} y_{6}  y_{7}
1 x_{1} = 90000 1 0 0  1 0 0  0
0 x_{5} = 30000 0 0 −1 1 1 0  −1
0 x_{6} = 80000 0 0 1 0 0 1 0
2 x_{2} = 40000 0 1 1 −1 0 0  1
z = 170000 0 0 −1 −1 0 0 −M + 2

que, pel teorema de la solució òptima del mètode del símplex, ja ens dóna la solució del problema. Així, agafant les variables reals del problema, la solució és x_{1} = 90000 vacunes subministrades a París, x_{2} = 40000 vacunes subministrades a Roma i cap a Londres. El cost mínim serà de 170000 + 1950000 = 2120000 u.m.