Algebra lineal y conjuntos convexos 1
1 Solucin de sistemas.
2 Espacios vectoriales.
3 Conjuntos convexos.4 Soluciones bsicas puntos extremos.
OpenCourseWare, UPV/EHU. Algebra lineal
Rango de una matriz 2
A R mn.
Reducir A a una matriz escalonada U algoritmo de Gauss.
Las filas que no tienen pivote en U son nulas.
rang A= nmero de pivotes de U.
OpenCourseWare, UPV/EHU. Algebra lineal
Ejemplo 3Clculo del rango
A =
1 2 3 4 11 2 2 5 43 2 5 2 42 0 6 9 7
1 2 3 4 10 0 1 9 30 4 14 14 10 4 12 17 5
1 2 3 4 10 4 14 14 10 0 1 9 30 4 12 17 5
1 2 3 4 10 4 14 14 10 0 1 9 30 0 2 3 4
1 2 3 4 10 4 14 14 10 0 1 9 30 0 0 21 10
= U
rang A = 4.OpenCourseWare, UPV/EHU. Algebra lineal
Solucin de sistemas lineales 4
Ax = b.
A R mn, rang A = r , b R m.
Casos:
1. rang A 6= rang (A b) no solucin.2. rang A = rang (A b) = r solucin.
2.1. r = nmero incognitas solucin nica.2.2. r < nmero incognitas infinitas soluciones.
OpenCourseWare, UPV/EHU. Algebra lineal
Ejemplo 1 5No solucin
2x1 x2 + 3x3 = 2x1 + x2 x3 = 4
3x1 + 2x3 = 5
A =
2 1 31 1 1
3 0 2
(A b) =
2 1 3 21 1 1 4
3 0 2 5
2 1 3 21 1 1 4
3 0 2 5
; 2 1 3 20 32 52 3
0 32 52 2
; 2 1 3 20 32 52 3
0 0 0 1
rang A = 2 < 3 = rang (A b) no solucin.OpenCourseWare, UPV/EHU. Algebra lineal
Ejemplo 2 6Solucin nica
2x1 + x2 = 3x1 + x2 = 4
A =(
2 11 1
) (A b) =
(2 1 31 1 4
)
(2 1 31 1 4
)
(2 1 30 12
52
)
rang A = rang (A b) = 2 = nmero de incgnitas.Solucin nica: x1 = 1, x2 = 5.
OpenCourseWare, UPV/EHU. Algebra lineal
Ejemplo 3 7Infinitas soluciones
2x1 x2 + 3x3 = 2x1 + x2 x3 = 4
3x1 + 2x3 = 6
A =
2 1 31 1 1
3 0 2
, (A b) =
2 1 3 21 1 1 4
3 0 2 6
2 1 3 21 1 1 4
3 0 2 6
2 1 3 20 32 52 3
0 32 52 3
2 1 3 20 32 52 3
0 0 0 0
rang A = rang (A b) = 2 < nmero de incgnitas infinitassoluciones.
OpenCourseWare, UPV/EHU. Algebra lineal
Soluciones bsicas 8
Ax = b, A R mn, m < n.
rang A = rang (A b) = m.
B submatriz base m m.N el resto de columnas de A.
(B N)(
xBxN
)= b BxB + NxN = b BxB = b NxN .
Infinitas soluciones en funcin de las variables xN .Si xN = 0 :
BxB = b solucin nica .
xB solucin bsica.
OpenCourseWare, UPV/EHU. Algebra lineal
Clculo de soluciones bsicas 9
2x1 x2 + 3x3 = 2x1 + x2 x3 = 4(
2 1 3 21 1 1 4
)
(2 1 3 20 32
52 3
)
(2 1 3 20 32
52 3
)Infinitas soluciones.Nmero mximo de bases:
(32
)= 3!2! (32)! = 3.
B =(
2 11 1
)(
2 11 1
)(x1x2
)=
(24
)
xB =
(22
) solucin bsica.
OpenCourseWare, UPV/EHU. Algebra lineal
Espacios vectoriales 10Combinacin lineal
Espacio vectorial R m, v1, v2, . . . , vn R m.Combinacin lineal:
1v1 + 2v2 + + nvn, 1, . . . , n R .
Ejemplo.
v1 =
(10
), v2 =
(1
1
)
Combinacin lineal de v1 y v2:
2(
10
)+ 5
(1
1
)
OpenCourseWare, UPV/EHU. Algebra lineal
Espacios vectoriales 11Dependencia e independencia lineal
v1, . . . ,vn Rm
, son linealmente independientes si paracualquier combinacin lineal,
1v1 + + nvn = 0se tiene necesariamente
1 = = n = 0.
v1, . . . ,vn de R m, son linealmente dependientes si es posibleencontrar una combinacin lineal
1v1 + + nvn = 0con algn escalar i distinto de cero.
OpenCourseWare, UPV/EHU. Algebra lineal
Ejemplo 12Dependencia e independencia lineal
11
2
, 301
, 93
5
1
11
2
+ 2
301
+ 3
93
5
=
00
0
1 3 91 0 3
2 1 5
1 3 90 3 6
0 7 13
1 3 90 3 6
0 0 1
Nmero de pivotes=3 1 = 2 = 3 = 0.Los vectores son linealmente independientes.
OpenCourseWare, UPV/EHU. Algebra lineal
Espacios vectoriales 13Conjunto generador
S = {v1, . . . ,vn} R m es un conjunto generador de R m sipara cualquier v R m exiten 1, 2, . . . , n R tal que
v = 1v1 + + nvn.
S =
11
1
, 31
0
, 21
1
, 22
2
1 3 2 2 v11 1 1 2 v2
1 0 1 2 v3
1 3 2 2 v10 4 3 0 v2 + v1
0 3 1 0 v3 v1
1 3 2 2 v10 4 3 0 v2 + v1
0 0 54 0 v3 14v1 +
34v2
rang A = rang (A b)=3
conjunto generador .OpenCourseWare, UPV/EHU. Algebra lineal
Espacios vectoriales 14Bases y dimensin
B = {v1, . . . ,vm} R m es base de R m si los vectores sonlinealmente independientes y B es un conjunto generador.
B =
12
0
,
01
0
,
11
2
1 0 12 1 1
0 0 2
1 0 10 1 1
0 0 2
l. i.
1 0 1 v12 1 1 v2
0 0 2 v3
1 0 1 v10 1 1 v2 2v1
0 0 2 v3
generador.
B es una base de R 3.OpenCourseWare, UPV/EHU. Algebra lineal
Teorema cambio de base 15
B = {v1, . . . ,vm} una base de R m.Cualquier vector v R m se puede expresar en combinacinlineal de v1, . . . ,vm.Los coeficientes de la combinacin lineal son nicos coordenadas del vector.
TeoremaDada una base B del espacio vectorial R m y un vector v R m,v 6 B y v 6= 0, siempre es posible conseguir otra basesustituyendo algn vector de B por el vector v
Este teorema es un resultado central en el algoritmo simplexpara pasar de una solucin bsica a otra mejor hasta obtenerla solucin ptima.
OpenCourseWare, UPV/EHU. Algebra lineal
Clculo de nuevas bases 16Condicin de los vectores
B =
v1 =
12
0
,v2 =
01
0
,v3 =
11
2
, v =
31
0
31
0
= 1
12
0
+ 2
01
0
+ 3
11
2
Coordenadas de v : 1 = 3 , 2 = 5 , 3 = 0.
1 6= 0 B = {v,v2,v3} es base.2 6= 0 B = {v1,v,v3} es base.3 = 0 el vector v3 no se puede sustituir por v.
OpenCourseWare, UPV/EHU. Algebra lineal
Semiespacios, hiperplanos y conjuntos convexos 17
El plano Euclideo pares ordenados de nmeros reales.
R2 =
{(x1x2
), x1 y x2 nmeros reales
}
x1
x2
(3,2)
Figura: Plano Euclideo
OpenCourseWare, UPV/EHU. Algebra lineal
Rectas 18
Ecuacin de una recta en R 2: a1x1 + a2x2 = c, a1,a2, c R .
Representacin de la recta 2x1 + 3x2 = 6.
x1
x2
2x1 + 3x2 = 62
3
Figura: Recta en el plano
OpenCourseWare, UPV/EHU. Algebra lineal
Semiespacios 19
Semiespacio cerrado de R 2:
a1x1 + a2x2 c a1x1 + a2x2 c.Representacin del semiespacio 2x1 + 3x2 6.
x1
x2
2x1 + 3x2 6
Figura: Semiespacio en el plano
OpenCourseWare, UPV/EHU. Algebra lineal
Generalizacin 20
R3 =
8>>>>:
0BBB@
x1x2.
.
.
xn
1CCCA , x1, x2, . . . xn nmeros reales
9>>>=>>>;
En R n a1x1 + a2x2 + + anxn = c es un hiperplano.
Semiespacio cerrado de R n:
a1x1 + a2x2 + + anxn c a1x1 + a2x2 + + anxn c.
OpenCourseWare, UPV/EHU. Algebra lineal
Conjuntos convexos 21
C R n es un conjunto convexo si es el vacio, si tiene un slopunto o si para cada dos puntos distintos del conjunto elsegmento que los une est contenido en el conjunto.(a), (b) y (c) son convexos.(d) no es convexo.
(a) (b)
(c) (d)
Figura: Conjuntos convexos y no convexos
OpenCourseWare, UPV/EHU. Algebra lineal
Resultados de conjuntos convexos 22
Un hiperplano es un conjunto convexo.Un semiespacio cerrado es un conjunto convexo.La interseccin de un nmero finito de conjuntos convexoses un conjunto convexo.
Aplicacin a la programacin lineal.Los conjuntos convexos que aparecen en el estudio demodelos lineales son los hiperplanos, los semiespacioscerrados y la interseccin de un nmero finito. Estos conjuntosson del tipo (a), donde los vrtices del conjunto se llamanpuntos extremos.
OpenCourseWare, UPV/EHU. Algebra lineal
Puntos extremos y soluciones bsicas 23Variables mayores o iguales que cero
x1 + 4x2 4x1 x2 3
O
A
B
C x1
x2
x1 + 4x2 = 4
x1 x2 = 3
Figura: Conjunto convexo y puntos extremos
OpenCourseWare, UPV/EHU. Algebra lineal
Conjunto convexo puntos extremos 24
Vertices puntos extremos.
O =(
00
)origen de coordenadas.
A =(
01
)interseccin de x1 + 4x2 = 4 con el eje OX2.
B =( 16
373
)interseccin de x1 + 4x2 = 4 y x1 x2 = 3.
C =(
30
)es interseccin de x1 x2 = 3 con el eje OX1.
OpenCourseWare, UPV/EHU. Algebra lineal
Generalizacin 25
En el plano Euclideo la interseccin de un nmero finito desemiespacios cerrados es un conjunto convexo, unpolgono con un nmero finito de puntos extremos.
En el espacio Euclideo de dimensin 3 la interseccin deun nmero finito de semiespacios cerrados es un conjuntoconvexo, un poliedro con un nmero finito de puntosextremos.
En el espacio Euclideo de dimensin n la interseccin deun nmero finito de semiespacios cerrados es un conjuntoconvexo llamado poltopo.
Los puntos extremos se calculan resolviendo sistemas deecuaciones lineales.
OpenCourseWare, UPV/EHU. Algebra lineal
Inecuaciones ecuaciones 26Puntos extremos Soluciones bsicas
Considerar todas las variables no negativas.Sumando x3 y x4 (no negativas) sistema de ecuaciones.
x1 + 4x2 4x1 x2 3
x1 + 4x2 + x3 = 4
x1 x2 + +x4 = 3
Sistema de inecuaciones.Infinitas soluciones puntos de la Figura.
Sistema de ecuaciones.Infinitas soluciones.Soluciones bsicas, variables no negativas puntosextremos.
OpenCourseWare, UPV/EHU. Algebra lineal
Clculo de soluciones bsicas 271. Columnas primera y segunda, x3 = x4 = 0.
x1 + 4x2 = 4x1 x2 = 3
Solucin: x1 = 163 y x2 = 73 punto B.2. Columnas primera y tercera, x2 = x4 = 0.
x1 + x3 = 4x1 = 3
Solucin: x1 = 3 y x3 = 7 punto C.3. Columnas primera y cuarta, x2 = x3 = 0.
x1 = 4x1 + x4 = 3
Solucin: x1 = 4 y x4 = 7 ningn punto extremo.OpenCourseWare, UPV/EHU. Algebra lineal
Clculo de soluciones bsicas 28
4. Columnas segunda y tercera, x1 = x4 = 0.4x2 + x3 = 4x2 = 3
Solucin: x2 = 3 y x3 = 16 ningn punto extremo.5. Columnas segunda y cuarta, x1 = x3 = 0.
4x2 = 4x2 + x4 = 3
Solucin: x2 = 1 y x4 = 4 punto A.6. Columnas tercera y cuarta, x1 = x2 = 0.
x3 = 4x4 = 3
Solucin: x3 = 4 y x4 = 3 punto O.OpenCourseWare, UPV/EHU. Algebra lineal