TÉCNICAS DE OPTIMIZACIÓN
Maestría en Ingeniería
Optimización En el análisis y diseño óptimo
de sistemas complejos en ingeniería las tareas de optimización juegan un rol esencial
La mayoría de los problemas en el mundo real tienen varias soluciones y algunos tienen infinitas soluciones
El propósito de la optimización es encontrar o identificar la mejor solución posible, entre todas las soluciones potenciales para un problema dado
Optimización Casi siempre el interés en la
optimización se centra en la solución de problemas reales, los cuáles deben ser representados matemáticamente
Formulación del Modelo Matemático
Aplicación de Técnicas de Solución
Interpretación de Resultados
Optimización Los procesos y
sistemas en ingeniería son generalmente complicados y deben ser simplificados mediante idealizaciones y aproximaciones para poder resolver el problema planteado
Modelado: Proceso de simplificación del problema, para que pueda ser representado en términos de un sistema de ecuaciones o a través de un arreglo físico
Optimización Modelo: Arreglo físico o conjunto de ecuaciones que
sirven para representar algún sistema o proceso
Optimización Modelo Descriptivo: Se usan
para explicar los mecanismos y principios que interactúan en un sistema.
Modelo Predictivo: Son los que se emplean en el diseño y optimización de sistemas en ingeniería.
Modelos análogos
Modelos Matemático Modelos físico Modelos numéricos
Optimización Un modelo matemático representa
el desempeño y comportamiento de un sistema dado en términos de ecuaciones matemáticas, ofreciendo resultados cuantitativos.
Pueden estar basados en el entendimiento físico de un sistema ó por construcción de modelos a partir de datos.
Las ecuaciones que gobiernan el sistema pueden ser algebraicas, ecuaciones diferenciales ordinarias y/o parciales, ecuaciones integrales ó combinación de varias de ellas
OptimizaciónProblema Matemático de Optimización
Consisten en la maximización o minimización de funciones algebraicas de una o más variables
La selección de las variables pueden estar restringidas por ecuaciones o inecuaciones algebraicas llamadas restricciones, de forma tal que el objetivo no es encontrar el mejor valor posible sino el mejor valor permitido por las restricciones
OptimizaciónTipos de Problema Matemático de Optimización
OptimizaciónTipos de Problema Matemático de Optimización
OptimizaciónTipos de Problema Matemático de Optimización
TÉCNICAS DE OPTIMIZACIÓN
Generalidades de Algebra Lineal
Sistemas de Ecuaciones Lineales
Sistema de m ecuaciones con n incognitas
a11x1 a12x2 a1nxn b1
a21x1 a22x2 a2n xn b2
am1x1 am2 x2 amn xn bm
Sistemas de Ecuaciones Lineales
Comentarios
Si un sistema tiene una solución, se denomina consistente Si un sistema no tiene una solución, se denomina inconsistente Si en el sistema se denomina
homogéneo. Un sistema homogéneo tiene siempre la solución trivial:
Si dos sistemas tienen la misma solución, se les denomina equivalentes.
La estrategia de solución para sistemas lineales es transformar el sistema a través de una serie de sistemas equivalentes hasta que la solución sea evidente
b1 b2 bm 0
x1 x2 xn 0
Vectores
Un vector en el plano es un arreglo de tamaño2 x 1, el cual es representado como:
donde “x” y “y” son números reales Los números “x” y “y” en la definición de un
vector son llamados los componentes del vector v.
Dos vectores y son iguales si x1=x2 y y1 = y2
xy
v
1
1
xy
v 2
2
xy
u
Vectores
Un vector bidimencional tiene varias interpretaciones geométricas1) Un punto ( x,y ) en el plano 2) Un segmento lineal dirigido desde el
origen a el punto ( x,y ) 3) Un segmento lineal dirigido desde el
punto ( x1,y1 ) a el punto ( x2,y2 ). Entonces x = x2 - x1, y = y2 - y1
Para aplicaciones en geometría y física, algunas de las operaciones más importantes son: 1) Suma de Vectores2) Multiplicación Escalar3) Resta de Vectores
xy
v
Vectores
Suma de Vectores
Sea y . Se define: 1
2
uu
u 1
2
vv
v 1 1
2 2
u vu v
u v
x
y
u1
u2
v2
v1
u1,u2
v1, v2
u1 v1,u2 v2
u
v
uv
Vectores
Suma de Vectores u + v puede ser determinado
geometricamente por adición de un vector de la Cola a la Cabeza
x
y
u
v
uv
v
Vectores
Multiplicación Escalar Sea c un escalar(e.g. un número real) y
un
vector. La Multiplicación Escalar c u of u por c está definida como el vector defined as the vector
1
2
uu
u
1
2
cucu
x
y
c 0
c 0
c 1
c 1
0 c 1
Vectores
Resta de Vectores Se define u - v como u + (-1) v La relación geometrica entre u,v, u + v y u -
v
u
v
uv
u v
Vectores
Descripción Parametrica de una Linea Sea P1 y P2 puntos. La linea que pasa
através de ellos puede ser descrita como:
1 2 1 1 21t t t t P P P P P P
P1
P2
P2 P1
t 0
t 1
t 1
t 0
0 t 1
Vectores
Vectores en Tres Dimensiones Un vector en tres dimensiones es una
matriz de tamaño 3 x 1,
donde “x”, “y” y “z” son numeros reales La Suma, Multiplicación Escalar y Resta de
Vectores, son definidas analogamente a vectores en dos dimensiones
xyz
Vectores
Propiedades Básicas de Vectores en R2 ó R3 Teorema - Si u, v y w son vectores en R2 ó
R3 y c y d son escalares reales, entonces: a) u + v = v + ub) u + (v + w) = (u + v) + wc) u + 0 = 0 + u = ud) u + (-u) = 0 e) c (u + v) = c u + c vf) (c + d) u = c u + d u g) c (d u) = (c d ) uh) 1 u = u
Vectores
Vectores en n Dimensiones Un vector en n dimensiones es una matriz
de tamaño n x 1,
donde “x1”, “x2” … “xn” son numeros reales La Suma, Multiplicación Escalar y Resta de
Vectores, son definidas analogamente a vectores en dos dimensiones
1
2
n
xx
x
Vectores Sea v1 y v2 vectores en un espacio vectorial V.
El conjunto de todos los vectores de la forma a1v1 + a2 v2 , para a1 and a2 números reales, forman un subespacio de V
Sea A una matriz de tamaño m x n y considere el sistema homogéneo Ax = 0 donde x ϵ Rn. Si se define W = {x ϵ Rn | Ax = 0 }., W es un subespacio de Rn llamado el Espacio Nulo de A.
Sea x y y soluciones del sistema homogéneo, i.e. Ax = 0 y Ay = 0, entonces A( x + y ) = Ax + Ay = 0 + 0 = 0.
Sea c un escalar, entonces A( c x ) = c( Ax ) = c
0 = 0 (c x ϵ W y W es un subespacio de Rn)
Vectores
Sea S = { v1, v2, …, vk } un conjunto de vectores en un espacio vectorial V. Un vector v ϵ V es llamado Combinación Lineal de vectores en S si: v = a1 v1 + a2 v2 + … + ak vk para cualquier número reales a1, a2 , …, ak
v1
a1v1
v 2
a2v2
a1v1 a2v2
v1
v 2
a1 0,a2 0
a1 0,a2 0
a1 0,a2 0
a1 0,a2 0
Vectores
Sea S = { v1, v2, …, vk } un conjunto de vectores en un espacio vectorial V. Entonces S es visto como linealemente dependiente si existen constantes, a1, a2 , …, ak , no todos ceros, tal que:
a1 v1 + a2 v2 + … + ak vk = 0
Sea S = { v1, v2, …, vk } un conjunto de vectores distintos en un espacio vectorial V. Si S no es linealmente dependiente entonces S es visto como linealmente independiente. Que es:
a1 v1 + a2 v2 + … + ak vk = 0
para a1 = a2 = … = ak = 0
Matrices Sistema de m ecuaciones con n incognitas
Si se define la matriz A de tamaño m x n , como:
11 12 1
21 22 2
1 2
n
n
mnm m
a a aa a a
a a a
A
a11x1 a12x2 a1nxn b1
a21x1 a22x2 a2n xn b2
am1x1 am2 x2 amn xn bm
Matrices El sistema m x n puede ser escrito como
ó AX = B
Si los valores de b1 = b2 = … = bm = 0, el sistema es denominado homogeneo y puede ser escrito como AX = 0
11 12 1 1 1
21 22 2 2 2
1 2
n
n
mn n mm m
a a a x ba a a x b
a a a x b
Matrices i - esima fila de A
j - esima columna de A
Lo que se puede escribir como: A = [ aij ]
ó ( A )ij for aij
ai1 ai2 ain 1i m
1
2 1
j
j
mj
a
aj n
a
MatricesComentarios:
a) Si m = n entonces A es denominado una Matriz Cuadrada
b) Para una Matriz Cuadrada, los elementos a11, a22, …, ann constituyen la Diagonal Principal de A
c) Dos matrices, A = [ aij ] y B = [ bij ], son iguales si aij = bij para 1 ≤ i ≤ m, 1 ≤ j ≤ n
MatricesSuma de Matrices
Sea A = [ aij ] y B = [ bij ] dos matrices de tamaño m x n, entonces C = A + B es una matriz C = [ cij ] tal que cij = aij + bij i, j
Multiplicación de una Matriz por un Escalar
Sea A = [ aij ] y r Î R. Entonces C = r A, donde C = [ cij ] es definida como cij = r aij i, j
MatricesMultiplicación de una Matriz por un Vector
Si A es una matriz de tamaño m x n y X es un vector de tamaño n x1, entonces:
11
21
1
n
k kkn
k kk
n
mk kk
a x
a x
a x
AX
11 12 1
21 22 2
1 2
n
n
mnm m
a a aa a a
a a a
A
MatricesMultiplicación de una Matriz por un Vector
Si A es una matriz de tamaño m x n y X es un vector de tamaño n x1, AX puede también ser expresado como:
Lo cual se denomina como una combinación lineal de las columnas de A. los coeficientes son los elementos de X
11 12 1
21 22 21 2
1 2
n
nn
mnm m
a a aa a a
x x x
a a a
AX
MatricesMultiplicación de Matrices
Sea A = [ aij ] una matriz de tamaño m x n y sea B = [ bij ] una matriz de tamaño n
x p. El producto de A por B es igual a una matriz C de tamaño m x p (AB=C = [ cij ]), definida por:
cij aikbkjk1
n
ai1b1 j ai2b2 j ainbnj
for i 1,2,,m j 1,2,, p
MatricesMultiplicación de Matrices
Comentarios
BA es definida si sólo si p = m Si p = m tal que BA es definida, entonces BA es
una matriz de tamaño n x n y AB es una matriz de tamaño m x m, i.e. diferentes tamaños
Si AB y BA son del mismo tamaño, estas pueden no ser iguales, i.e. lo que muestra que no es comutativa
MatricesSistemas de Ecuaciones
Considere
Defina
Exprese el sistema como AX = B
a11x1 a12x2 a1nxn b1
a21x1 a22x2 a2n xn b2
am1x1 am2 x2 amn xn bm
11 12 1 1 1
21 22 2 2 2
1 2
n
n
mn n mm m
a a a x ba a a x b
a a a x b
A X B
MatricesSistema de Ecuaciones
Donde la solución del sistema involucra los valores de a y b unicamente, por lo cual se podría trabajar con la matriz aumentada
11 12 1 1
21 22 2 2
1 2
n
n
mn mm m
a a a ba a a b
a a a b
MatricesMatriz Transpuesta
Sea A = [ aij ] una matriz de tamaño m x n. La Matriz Transpuesta de A, denotada por AT , es AT = [ aij
T ] una matriz de tamaño n x
m definida por aijT = aji
MatricesTeorema (Suma de Matrices) Sea A, B y C matrices de tamaño m x n
1) A + B es una matriz de tamaño m x n
2) A + (B + C) = (A + B) + C
3) Sea m0n una matriz nula de tamaño m x n tal que A + m0n = m0n + A = A para cualquier matriz A
4) Para cualquier matriz A de tamaño m x n, D es una matriz unica de tamaño m x n tal que A + D = D + A = m0n
5) A + B = B + A
MatricesTeorema (Multiplicación de Matrices)
a) Si A, B y C son matrices de tamaños apropiados, entonces A ( BC ) = ( AB ) C
b) Si A, B y C son matrices de tamaño apropiados, entonces ( A + B ) C = AC + BC
c) Si A, B y C son matrices de tamaño apropiado, entonces C ( A + B ) = CA + CB
MatricesPropiedades de Multiplicación de una Matriz por un Escalar
Si r y s son números reales y A y B son matrices,
Entonces: r ( sA ) = ( rs ) A ( r + s ) A = rA + sA r ( A + B ) = rA + rB A ( rB ) = r ( AB ) = ( rA ) B
MatricesPropiedades de la Matriz Transpuesta
Si r es un escalar y A y B son matrices, entonces:
( AT
)T = A
( A + B )T = AT + BT
( AB )T = BTAT
( rA )T = rAT
MatricesMatrices Especiales
Una matriz A = [ aij ] de tamaño n x n es llamada una Matriz Diagonal si aij = 0 para i ≠ j, i.e. los términos de la diagonal principal son todos cero
Una Matriz Escalar es una Matriz Diagonal cuando los elementos de la diagonal son todos iguales
La matriz Escalar In = [ aij ], donde aii = 1 y aij = 0 para i ≠ j es llamada Matriz Identidad de tamaño n x n. Sea A una matriz cualquiera de tamaño m x n, entonces:A In = A y Im A = A
MatricesMatrices Especiales
Matriz Potencia: Si A es una matriz de tamaño n x n y p es un entero positivo, puede definirse:
Si A es una matriz de tamaño n x n y p=0, adopte la conversión:
factors
p
p
A AA A
A0 In
MatricesMatrices Especiales
Las siguientes son leyes de exponentes para valores de p y q no negativos y una matriz A de tamaño n x n
1 ) Ap Aq = Ap + q
2 ) ( Ap ) q = Apq
Precausión.
1 ) ¿Esta definida Ap para enteros negativos de p? 2 ) ¿Se puede afirmar que ( AB )
p = Ap B p
?
MatricesMatrices Especiales
Matriz Triangular Superior: Una matriz A = [ aij ] de tamaño n x n es llamada Matriz Triangular Superor si aij = 0 para i > j
Matriz triangular Inferior: Una matriz A = [ aij ] de tamaño n x n es llamada Matriz Triangular Inferior si aij = 0 para i < j
Nota: Una matriz diagonal es triangular superior e
inferior La matriz nula de tamaño n x n es triangular
superior e inferior
MatricesMatrices Especiales
Matriz Simetrica: Una matriz A es llamada simetrica si AT= A
Matriz Simetrica : Una matriz A es llamada skew-simetrica si AT= -A
Comentario - si A es skew-simetrica, entonces los elementos de la diagonal de A son cero
Comentario - hay matrices cuadradas A puede escribirse como la suma de una matriz simetrica y una matriz skew-simetrica
T T
symmetric skew-symmetric
1 12 2
A A A A A
MatricesMatrices Especiales
Matriz No – Singular: Una matriz A de tamaño n x n es llamada no singular ó invertible si existe una matriz B de tamaño n x n tal que AB = BA = In
Comentarios
Si B existe, entonces B es llamada la inversa de A Si B no existe, entonces A es llamada singular ó
no invertible
MatricesMatrices Especiales
Teorema – Si la inversa de una matriz existe, entonces la inversa es única
Notación - Si A es una matriz no singular. La inversa de A es denotada por A-1
Comentario – ¿Para matrices no singulares, A, puede definirse A elevada a una potencia negativa, como A-k = ( A-1
) k para k >
0?
MatricesMatrices Especiales
Teorema - Si A y B son ambas matrices singulares, entonces el producto AB es no singular y ( AB ) -1 = B-1A-1
Teorema - Si A1, A2, …, Ar son matrices no singulares, entonces A1 A2 • • • Ar es no singular y
A1A2Ar 1Ar
1Ar1 1 A2
1A1 1
MatricesMatrices Especiales
Teorema - Si A es una matriz no singular, entonces A-1 es no singular y ( A-1
) -1 = A
Teorema - Si A es una matriz no singular, entonces AT es no singular y ( AT
) -1 = ( A-1
) T
MatricesSistemas Lineales y Matriz inversa
Un sistema de n ecuaciones lineales con n incógnitas puede ser escrito como AX = B, donde A es una matriz de tamaño n x n. Si A es no singular, entonces A-1 existe y el sistema puede ser resuelto al multiplicar ambos lados por A-1
A-1( AX ) = A-1B ( A-1A )X = A-1B X = A-1B
Determinante
Método de Expansión
Sea A = [ aij ] una matriz de tamaño n x n. El Determinante de A es definido como
donde la sumatoria son todas las permutaciones j1 j2 … jn de S = { 1, 2, …, n }. El signo es + si j1 j2 … jn es una permutación par y es – si j1 j2 … jn es una permutación impar
1 21 2det
nnjj ja a a A
Determinante
Comentarios
det( A ) es una función desde el conjunto de matrices de tamaño n x n en los números reales
Cada término de det( A ) subíndices de filas en el orden de los Naturales y subíndices de columna en el orden de j1 j2 … jn . Así cada término es un producto de n elementos de A, con exactamente una entrada de cada fila de A y exactamente una entrada de cada columna de A.
det( A ) en también escrito como
1 21 2 nnjj ja a a
A
Determinante
Ejemplo
Sea A = [ a11 ] una matriz de tamaño 1x1, entonces el det( A ) = a11
Sea una matriz de tamaño 2x2,
entonces el det( A ) = a11 a22 - a12 a21
11 12
21 22
a aa a
A
a11 a12
a21 a22
Determinante
Ejemplo
Sea una matriz de tamaño 3x3,
entonces el det( A ) = a11 a22 a33 + a12 a23 a31 + a13 a21 a32
- a11 a23 a32 - a12 a21 a33 + a13 a22 a31
11 12 13
21 22 23
31 32 33
a a aa a aa a a
A
a11 a12 a13 a11 a12
a21 a22 a23 a21 a22
a31 a32 a33 a31 a32
Determinante
Método de Cofactor
Sea A = [ aij ] una matriz de tamaño n x n. Sea Mpq una submatriz de A de tamaño ( n – 1 ) x ( n – 1 ) obtenida al borrar la p-esima y la q-esima columna de A. El determinante det( Mpq ) es llamado determinante menor de apq
Sea A = [ aij ] una matriz de tamaño n x n. El cofactor Apq de apq es definido como Apq = (–1)
p+q det( Mpq )
Determinante
Método de Cofactor
Teorema – Sea A = [ aij ] una matriz de tamaño n x n. Entonces:
det( A ) = ai1A i1+ ai2A i2 + … + ain A in (expansión del det( A ) con respecto a la fila i )ó
det( A ) = a1j A 1j+ a2j A 2j + … + anj A nj (expansión del det( A ) con respecto a la columna j )
Determinante
Comentario
Examine patron de los signos del término ( –1 ) p+q
Cuando usamos cofactores, no tenemos que evaluar evaluate ( –1 )p+q , sólo recordar el patron
n = 3 n = 4
Determinante Teorema – Sea una matriz cuadrada A.
Entonces el det( A ) = det( AT )
Teorema – Si la matriz B es obtenida desde la matriz A por intercambio de dos filas (columnas) de A, entonces det( B ) = - det( A )
Teorema – Si dos filas (columnas) de A son iguales, entonces det( A ) = 0
Teorema – Si una fila (columna) de A consiste completamente de ceros, entonces det( A ) = 0
Determinante Teorema – Si B es obtenida desde A por
multiplicación de una fila (columna) de A por un número c, entonces det( B ) = c det( A )
Teorema – Si B = [ bij ] es obtenida desde A = [ aij ] por adicionar a cada elemento de la r-esima fila (columna) de A, c veces el elemento correspondiente de la s-esima fila (columna), con r ≠ s, de A, entonces det( B ) = det( A )
Teorema - Sea A = [ aij ] una matriz triangular superior (inferior), entonces det( A ) = a11a22 … ann. Que es, el producto de los elementos de la diagonal principal
Determinante Teorema – Sea E una matriz elemental.
Entonces det(EA) = det( E )det( A ) y det( AE ) = det( A )det( E )
Teorema – Sea A una matriz de tamaño n x n. Entonces A es no singular si y sólo si det( A ) ≠ 0
Teorema – Sea A una matriz de tamaño n x n, entonces Ax = 0 tiene una solución no trivial si y sólo si det( A ) = 0
Teorema – Si A y B son matrices de tamaño n x n, entonces det( AB ) = det( A )det( B )
Determinante Teorema – Si A es no singular, entonces
det(A–1) = 1 /det( A )
Teorema – Si A y B son matrices similares, entonces det( A ) = det( B ). A y B son similares si existe una matriz no singular P tal que B = P–1
A P
Top Related