Upload
roberto-escoto
View
219
Download
0
Embed Size (px)
Citation preview
8/15/2019 Tópicos Avanzados de Optimización
1/212
Tópicos Avanzados deOptimización
Dr. Manuel Rodríguez Medina
8/15/2019 Tópicos Avanzados de Optimización
2/212
Fases de un Estudio deInvestigación deOperaciones
1. La defnición del problema.
2. La construcción del modelo.
3. La solución del modelo.
4. La validación del modelo.
. La implementación de la solución.
8/15/2019 Tópicos Avanzados de Optimización
3/212
Construcción de
ModelosLos Modelos simbólicos son
conceptualizaciones abstractas delproblema real a base del uso de
letras! n"meros! variables #ecuaciones
8/15/2019 Tópicos Avanzados de Optimización
4/212
Construcción de
modelos $%emplo 1. &mpacto '.(.! puede anunciar sus productos
en estaciones locales de radio o )*. $l presupuestopara publicidad se limita a +1,,,, mensuales. -ada
minuto de un anuncio en la radio cuesta +1! # cadaminuto de comercial en )* cuesta +3,,. ( &mpacto legusta usar al menos el doble de publicidad por la radioue por )*. (l mismo tiempo! no es pr/ctico usar masde 4,, minutos de anuncios radio0ónicos cada mes. La
eperiencia indica ue se estima ue la publicidad por )* es 2 veces m/s e0ectiva ue por la radio. a -onstru#a el modelo de rogramación Lineal b Determine la asignación óptima del presupuesto
para publicidades por radio # )*
8/15/2019 Tópicos Avanzados de Optimización
5/212
Construcción de
modelos $%emplo 2. Modelos (l0a 0abrica camisas # blusas para las )iendas
eta! ue aceptan toda la producción de (l0a. $n el proceso deproducción intervienen el corte! costura # empacado. (l0a emplea2 traba%adores en el departamento de corte! 3 en eldepartamento de costura # en el departamento de empaue. $sa0abrica traba%a un turno de 5 6oras! días por semana. $n la tablasiguiente se muestran los tiempos necesarios # las utilidadesunitarias para cada prenda.
777777777777777777777777777777777 Minutos por unidad renda -orte -ostura $mpaue 8tilidad 9+
77777777777777777777777777777777777777777777777 -amisas 2, :, 12 5.,, lusas ;, ;, 4 12.,,
77777777777777777777777777777777777777777777777 a Determine el programa de producción semanal óptimo para (l0a.
8/15/2019 Tópicos Avanzados de Optimización
6/212
Construcción de modelos
$%emplo 3. $l ingenio La rimavera produce az"car morena!az"car blanca! az"car glas # melaza! a partir de guarapoconcentrado. La empresa compra 4,,, toneladas semanalesde ese guarapo! # se le contrata para entregar al menos 2
toneladas semanales de cada clase de az"car. $l proceso deproducción comienza 0abricando az"car morena # melaza apartir del guarapo. 8na tonelada de guarapo concentradoproduce ,.3 toneladas de az"car morena # ,.1 toneladas demelaza. ( continuación se produce el az"car blancaprocesando el az"car morena. 'e necesita una tonelada deaz"car morena para producir ,.5 toneladas de az"car blanca.or "ltimo! el az"car glas se produce a partir de az"car blancamediante un proceso especial de molienda ue tiene unaefciencia de producción del
8/15/2019 Tópicos Avanzados de Optimización
7/212
Construcción de modelos $%emplo 4. 8n 0abricante produce tres modelos! &! && # &&& de cierto producto! usando las
materias primas ( # . La tabla siguiente muestra los datos del problema? Reuerido por unidad 777777777777777777777 Materia prima & && &&& Disponibilidad
( 2 3 4,,, 4 2 : ;,,, Demanda mínima 2,, 2,, 1,
8tilidad por unidad 3, 2, , $l tiempo de mano de obra para el modelo & es el doble ue para el && # el triple del &&&. )odo
el personal de la 0/brica puede producir el euivalente de 1,, unidades del modelo &.Las necesidades del mercado especifcan las relaciones 3?2? de las producciones de lostres modelos respectivos. >ormule el modelo de programación lineal.
8/15/2019 Tópicos Avanzados de Optimización
8/212
Construcción de modelos $%emplo . 8n 0abricante de pl/sticos tiene en eistencia! en una de sus
0/bricas! 12,, ca%as de envoltura transparente # otras 1,,, ca%as en susegunda 0/brica. $l 0abricante tiene ordenes para este producto por partede tres di0erentes distribuidores! en cantidades! 1,,,! :,, # ,, ca%as!respectivamente. Los costos unitarios de envío 9en dólares por ca%a de las
0/bricas a los detallistas son los siguientes? 777777777777777777777777777777777777777777777 Distribuidor 1 Distribuidor 2 Distribuidor 3 77777777777777777777777777777777777777777777777777777777777777 >/brica 1 14 13 11 >/brica 2 13 13 12 77777777777777777777777777777777777777777777777777777777777777 -onstru#a el modelo de programación de costo mínimo! para
satis0acer la demanda con el inventario actual.
8/15/2019 Tópicos Avanzados de Optimización
9/212
Construcción de modelos $%emplo ;. 8na tienda de autoservicio ue 0unciona
las 24 6oras tiene los siguientes reuerimientosmínimos para los ca%eros?
$l período 1 sigue inmediatamente del período ;.8n ca%ero traba%a 5 6oras consecutivas! empezandoal inicio de uno de los seis períodos. Determíneseue grupo diario de empleados satis0ace lasnecesidades con el mínimo de personal.
eriodo 1 2 3 4 ;
@orario 3A: :A11 11A1 1A1< 1
8/15/2019 Tópicos Avanzados de Optimización
10/212
Análisis de Sensibilidad $%emplo :. @iDec produce dos modelos de artículos
electrónicos! donde se usan resistores! capacitores# c6ips. La tabla siguiente es un resumen de los
datos en este caso?Reuerimientos del recurso por unidadRecurso Modelo 1 Modelo 2 Disponibilidad m/imaResistor 2 3 12,,-apacitor 2 1 1,,,-6ips , 4 5,,8tilidad9+ 3 4
7777777777777777777777777777777777777777777777777
8/15/2019 Tópicos Avanzados de Optimización
11/212
Ejemplo !
Continuación 'ean x 1 # x 2 las cantidades producidas
de los modelos 1 # 2! respectivamente. (continuación se tiene el modelo de
programación lineal # su tabla simpleóptima asociada? Maimizar z = 3x 1 + 4x 2 su%eta a
2x 1 + 3x 2 ≤ 1200 2x 1 + x 2 ≤ 1000 4x 2 ≤ 800 x 1, x 2 ≥ 0
8/15/2019 Tópicos Avanzados de Optimización
12/212
8/15/2019 Tópicos Avanzados de Optimización
13/212
Ejemplo !
Continuacióna Determine el estado de cada recurso
b $n 0unción de la utilidad óptima determine elvalor de un resistor! de un capacitor # de un c6ip.
c Determine el intervalo de aplicabilidad de losprecios duales para cada recurso.
d 'i la cantidad disponible de resistores aumenta a13,, unidades determine la nueva solución
óptima.e 'i se reduce la cantidad de c6ips disponibles a
3, unidades! Bpodría usted determinar la nuevasolución óptimaC
8/15/2019 Tópicos Avanzados de Optimización
14/212
Algoritmo simple#
modi/cado
6 54321
6 54321
6
5
4
3
2
1
T 6 54321
ccccccC :objetivo funciónladeesCoeficient
0 x , x , x , x , x , x
2
1
6
24
x
x
x
x
x x
100010
010011-
001021
000146
a Sujeta
x x x x x x 000045 !axi"ia#
=
≥
=
=
8/15/2019 Tópicos Avanzados de Optimización
15/212
Algoritmo simple#
modi/cado Iteración )!
{ } $4 ,5% $c ,c% $ & , & % 'C c
$0 ,0 ,0 ,0% 'C
:d o(ti"alidadeC)lculos
0 * C , $2 ,1 ,6 ,24% b ' * +
' , & , & , & , & '
0 ,0 ,0 ,0C , x , x , x , x *
21211
0 '2 ,1 j j j
10 '
' 'T 1
0 '
106 5430
'6 543 '
0
0
000
00
=
=
=
=
=
8/15/2019 Tópicos Avanzados de Optimización
16/212
Algoritmo simple#
modi/cado Cálculos de factibilidad:
{ }
baseladesale.uevecto# el es & +
4 , ,6 ,4"in , ,1
6 ,
6
24"in x ,0 ,1 ,1 ,6 & '
$2 ,1 ,6 ,24% x , x , x , x *
3
1T
11
0
T T 6 543 '0
=
=
8/15/2019 Tópicos Avanzados de Optimización
17/212
Algoritmo simple#
modi/cado Iteración ,!
20 * C , $2 ,5 ,2 ,4% b ' *
1000
010
001
000
'
1000
0101
0011
0006
$ & , & , & , & % '
0 ,0 ,0 ,5 C , $ x , x , x , x % *
111
11
' 'T 1
1 '
6
16 1
6 1
11
6 5 411
'T
6 5 41 '
=
=
=
=
8/15/2019 Tópicos Avanzados de Optimización
18/212
Algoritmo simple#
modi/cado
{ }
& esent#a.uevecto# el +
$0 ,% $0 ,4%
01
01
02
14
$0 ,0 ,0 ,%
c ,c $ & , & % 'C c
$0 ,0 ,0 ,%
1000
010
001
000
$0 ,0 ,0 ,5% 'C
:d o(ti"alidadeónCo"(#obaci
2
32
6
5
32321
1 '3 ,2 j j j
6
5
6 1
6 1
6 1
1
1 '
1
1
=
=
=
=
8/15/2019 Tópicos Avanzados de Optimización
19/212
Algoritmo simple#
modi/cado
{ }
baseladesale & +
2
32 ,3 , ,6 "in
1
2 ,
5 ,
2 ,
4"in x
11
1
2
4
1000
010
001
000
& '
$2 ,5 ,2 ,4% x , x , x , x *
:ad factibilid deónCo"(#obaci
4
2
3
35
34
322
3
53432
6 16 1
6 1
21-
1
T T 6 541 '1
=
=
=
=
=
8/15/2019 Tópicos Avanzados de Optimización
20/212
Algoritmo simple#
modi/cado
21 * C , $ , , ,3% b ' *
10
01
00
00
'
1010
0111
0021
0046
$ & , & , & , & % '
0 ,0 ,4 ,5C , $ x , x , x , x % *
112
22
' 'T
2
1
2
5
2
312 '
4
3
/
14
5
/
34
3
/
121
41
12
6 5212
'T
6 521 '
=
=
=
=
8/15/2019 Tópicos Avanzados de Optimización
21/212
Algoritmo simple#
modi/cado
{ }
c)lculosloste#"inan +ó(ti"oes * s
$ ,% $0 ,0%
00
00
10
01
$0 ,0 , ,%
c ,c $ & , & % 'C c
$0 ,0 , ,%
10
01
00
00
$0 ,0 ,4 ,5% 'C
:d o(ti"alidadeónCo"(#obaci
2
2
2
'
21
43
21
43
43431
2 '4 ,3 j j j
2
1
4
3
4
3
/1
45/3
43
/1
21
41
1
2 '
=
=
=
=
=
8/15/2019 Tópicos Avanzados de Optimización
22/212
Algoritmo del puntointerior de 0armar1ar
2,34&5 Idea 6undamental del algoritmo del punto interior
Maimizar z = x 1
su%eta a , 1 2
'i se usa x 2 como variable auiliar! el problema puedeser representado como?
Maimizar z = x 1 su%eta a
1 E 2 F 2
x 1, x 2 0
8/15/2019 Tópicos Avanzados de Optimización
23/212
Algoritmo del puntointerior de 0armar1ar
2,34&5 &dea gr/fca del concepto general delalgoritmo de GarmarHar
2
2
(
-
D
$
Iradiente de z
$spacio desoluciones?'egmento de recta(.
8/15/2019 Tópicos Avanzados de Optimización
24/212
&dea b/sica del algoritmo La dirección de aumento de z es la dirección
positiva de x 1.
'ea C un punto interior 9no etremo en elespacio 0actible 9línea (. $l gradiente de la0unción ob%etivo en C es la del aumento m/sr/pido de z . 'i se ubica un punto arbitrario alo largo del gradiente # a continuación se
pro#ecta perpendicularmente sobre elespacio 0actible! se obtiene el nuevo punto, con me%or valor ob%etivo. 'i se repite elprocedimiento en ! se determinar/ unnuevo punto ! m/s cercano al óptimo.
8/15/2019 Tópicos Avanzados de Optimización
25/212
Algoritmo del puntointerior
Minimizar z = CX
su%eto a
AX = 0 1X = 1
X ,
)odas las restricciones son ecuaciones6omogeneas! a ecepción de la restricción 1X =1! ue defne un simple n dimensional.
8/15/2019 Tópicos Avanzados de Optimización
26/212
7alidez del algoritmo
La validez del algoritmo consiste
en satis0acer dos condiciones?1. X = "1#n, 1#n,$,1#n% satis0ace AX
F )
2. min z F ,
8/15/2019 Tópicos Avanzados de Optimización
27/212
Ejemplo 'ea el problema
+ + +
efiniendo
2 + +2 +
tieneseolu#a,deva#iableunando nt#oducie
0 + , +
2 +2 +
asujeta
+ + !axi"ia#
321
321
21
21
21
≤
=
≥
≤
8/15/2019 Tópicos Avanzados de Optimización
28/212
Ejemplo Donde & es lo bastante grande para no
eliminar algunos puntos 0actibles en elespacio de soluciones. $n este caso & = '.
@omogeneizando la restricción?
0 +2 +3 +/ +3
+2 +2 +2 +2 +5 +10 +5
5
+ + + +
2 + +2 +
5 + + + +
4321
4321321
4321
321
4321
=
=
=
8/15/2019 Tópicos Avanzados de Optimización
29/212
Ejemplo
Defniendo una nueva variable
4 ,3 ,2 ,1 j ,0 x
1 x x x x
0 x 2 x 3 x / x 3
a sujeta
x 5 x 5 i"ia# "ax
4 ,3 ,2 ,1i 5
+
x
j
4321
4321
21
i
i
=
=
=
=
8/15/2019 Tópicos Avanzados de Optimización
30/212
Ejemplo
'e puede asegurar ue el centro X = "1#n,1#n,$,1#n% es un punto 0actible para
ecuaciones 6omogJneas! restando del ladoizuierdo de cada ecuación! una variableartifcial cu#o coefciente sea igual a lasuma algebraica de todos los coefcientes
de restricción en el lado izuierdo? así auí! 3 E 5 E 3 K 2 F 12
8/15/2019 Tópicos Avanzados de Optimización
31/212
Ejemplo
$l nuevo sistema ser/?
5 ,---,2 ,1 j ,0 x
1 x x x x x
0 x 12 x 2 x 3 x / x 3
a sujeta
!x x 5 x 5 !axi"ia#
j
54321
54321
521
=
=
=
8/15/2019 Tópicos Avanzados de Optimización
32/212
$l modelo de rogramaciónLineal
Defnición? 'e entiende por rogramaLineal auel ue optimiza
0 *
b *
asujeta
c*
≥
≤
=
8/15/2019 Tópicos Avanzados de Optimización
33/212
El m8todo Simple#
n ,,1i 0 *
" ,,1 j b * a
a Sujeta
* c 7(ti"ia#
i
i i
n
1i ji
i
n
1i i
=
=
∑
=
=
8/15/2019 Tópicos Avanzados de Optimización
34/212
Teoremas "ásicos de la9rogramación :ineal
)eorema 1. $l con%unto de todas las soluciones 0actibles de unprograma de programación lineal es un con%unto conveo.
emostración? 'i X es una solución 0actible! satis0ace lassiguientes condiciones
AX ≤ b X ≥ 0 )eorema 1.1 8n semiespacio cerrado cX ≤ b 9 o bien abierto cX <
b es un con%unto conveo. (r)eba* 'ean X 1 # X 2 dos puntos cualesuiera del semiespacio
cerrado o abierto. $s decircX 1 ≤ b ó cX 1 < b
cX 2 ≤ b ó cX 2 < b 'ea X = X 1 + (1- )X 2 0 < < 1. $ntonces cX = c! X 1 + (1- )X 2 " = cX 1 + (1- )cX 2 = b + (1- )
b = b
or tanto X est/ en el subespacio cerrado o abierto.
8/15/2019 Tópicos Avanzados de Optimización
35/212
Teoremas "ásicos de la9rogramación :ineal
)eorema 2. La 0unción ob%etivo de unprograma lineal obtiene su valor m/imo 9omínimo en un punto etremo del con%untoconveo de soluciones 0actibles.
(r)eba. -onsidJrese la 0orma canónica. 'ea# el con%unto de todos los puntos etremosdel con%unto conveo generado por todas lasrestricciones del ..L. sea
# = $X i %i &' ' denota los índices de lospuntos etremos
8/15/2019 Tópicos Avanzados de Optimización
36/212
8/15/2019 Tópicos Avanzados de Optimización
37/212
El procedimiento tradicionalde ;ram-Sc
8/15/2019 Tópicos Avanzados de Optimización
38/212
El procedimiento tradicionalde ;ram-Sc
8/15/2019 Tópicos Avanzados de Optimización
39/212
El procedimiento tradicionalde ;ram-Sc
8/15/2019 Tópicos Avanzados de Optimización
40/212
>escomposiciones ?= Teorema clave@ 'ea una matriz de - de
rango . $ntonces?
a% puede escribirse en su descomosición / no
normalizada como /00! en donde?1. /0 es - # tiene columnas ortogonales 9de las
cuales son di0erentes de cero # - son cero uegeneran el espacio columna de .
2. 0 es - -! triangular superior unitaria # no
singular.
3. La norma 2 de la iAJsima columna de /0 es igual a ladistancia de la iAJsima columna de al espaciogenerado por las primeras i1 columnas de .
8/15/2019 Tópicos Avanzados de Optimización
41/212
>escomposiciones ?=
b puede escribirse en su descomosición /normalizada como =/! en donde?
1. es
- # tiene columnas ortonormales uegeneran el espacio columna de .
2. es triangular superior de - # tiene rango .
3. 'i = -! entonces N=iiN es igual a la
distancia desde la iAJsima columna de 6asta elespacio generado por las primeras i1 columnasde (.
8/15/2019 Tópicos Avanzados de Optimización
42/212
>escomposiciones ?=!Ejemplo
00
4
343
4
34
9
0
3
22
1
4
9
4
1
0
;
8/15/2019 Tópicos Avanzados de Optimización
43/212
>escomposiciones ?=!Ejemplo
ara obtener # ! se eliminar/ la terceracolumna de 0 # el tercer renglón de 0! # sea%ustar/n las escalas de las columnas de 0 #
los renglones de 0.
8/15/2019 Tópicos Avanzados de Optimización
44/212
>escomposiciones usando trans6ormaciones
ouse
8/15/2019 Tópicos Avanzados de Optimización
45/212
>escomposiciones usando trans6ormaciones
ouse
8/15/2019 Tópicos Avanzados de Optimización
46/212
=eDe#iones deouse
8/15/2019 Tópicos Avanzados de Optimización
47/212
=eDe#iones deouse
8/15/2019 Tópicos Avanzados de Optimización
48/212
=eDe#iones deouseescomposición . Descomposición / de la matriz
T T
T T
T T
1
1
62?9 0 ,62?9 0 ,459? 05925 1
1 ,1 ,?321 0u
0 ,0 ,131 ,1 ,1
0 ,0 ,131 ,1 ,1
e + +
e + +u
22 21
/2 11
26 11
*
=
=
=
=
= D i d
8/15/2019 Tópicos Avanzados de Optimización
49/212
=eDe#iones deouseescomposición . btención de la matríz de @ouse6older[ ]
=
=
=
2114 0?//6 05??2 0
?//6 02114 05??2 0
5??2 05??2 05??4 0
?//6 0?//6 05??2 0
?//6 0?//6 05??2 0
5??2 05??2 04226 0
100
010
001
uu2 =
?//6 0?//6 05??2 0
?//6 0?//6 05??2 0
5??2 05??2 04226 0
62?9 062?9 0459? 0
62?9 0
62?9 0
459?
2uu2
T
11u
T 11
1
= D i d
8/15/2019 Tópicos Avanzados de Optimización
50/212
=eDe#iones deouseescomposición .
[ ]
=
=
=
=
0634 03504 00
03504193? 0
000
031? 01?52 00
1?52 096/5 00
000
21?/0 09/41 00
1?/0 0
9/41 0
0
2uu2
1?/0 09/41 00u
3422 1
0106/20 023// 063// 00u
023//-0
063//-0
30601?321
22 21
/2 11
26 11
2114 0?//6 05??2 0
?//6 02114 05??2 0
5??2 05??2 05??4 0
* = *
T 2
T
2
T
2
u1 1
= D i d
8/15/2019 Tópicos Avanzados de Optimización
51/212
=eDe#iones deouseescomposición .
=
=
=
=
=
=
00
6/2 00
06 3?321 1
22 21
/2 11
26 11
4?43 0/12? 033/4 0
664/ 000?/240?431-
05??205??205??4
* = = ;
4?43 0/12? 033/4 0
664/ 000?/240?431-
05??205??205??4
2114 0?//6 05??2 0
?//6 02114 05??2 0
5??2 05??2 05??4 0
09366 03504-0
03504-093? -0
001
= =
09366 03504-003504-093? -0
001
0634 03504 00
3504 093? 10
000
100
010
001
uu2 =
12
12
2
uu
uu
T 22u
= D i d
8/15/2019 Tópicos Avanzados de Optimización
52/212
=eDe#iones deouseescomposición .=2121 uu
T u
T u = = = = <
11
1111
T 11
T
@ ;A @A ; 6/2 00
06 3?321 1 ;
664/ 00?/24 0?431 0
5??2 05??2 05??4 0
8/15/2019 Tópicos Avanzados de Optimización
53/212
El Modelo de =egresión:ineal
$l modelo
= X E
supuestos? /() = ,
/() F X
(dicionalmente! suponiendo normalmente distribuido
*arP Q F $P , Q F 2'
8/15/2019 Tópicos Avanzados de Optimización
54/212
El Modelo de =egresión:ineal
$ntonces! la 0unción de densidad con%unta deprobabilidad para dado # 2! es
La 0unción de verosimilitud! l" ! 2N#! para #
es idJntico en 0orma a la densidad de probabilidadcon%unta! ecepto ue l" ! 2N# es consideradacomo una 0unción de los par/metros condicionalsobre los datos observados! en lugar de una0unción de las respuestas condicional sobre losvalores de los par/metros.
=
=
2
2
2
2
T 22
2
x +ex(2
2
x + x +ex(2 , + (
2 B
2 B
σ
β
πσ
σ
β
πσ
8/15/2019 Tópicos Avanzados de Optimización
55/212
8/15/2019 Tópicos Avanzados de Optimización
56/212
El Modelo de =egresión:ineal
$l estimador de m/ima verosimilitud esel valor de el cual minimiza 6" %. $stees llamado el estimador de mínimos
cuadrados! el cual puede obtenerseconsiderando ue el vector residual - ser/ ortogonal! o normal! al plano esperado.$uivalentemente! el vector residual deber/ser ortogonal a todas las columnas de lamatriz X ! tal ue
A
A
0A x + * T
=β
8/15/2019 Tópicos Avanzados de Optimización
57/212
8/15/2019 Tópicos Avanzados de Optimización
58/212
El Modelo de =egresión:ineal
tra manera de epresar el estimador de mínimoscuadrados! # una m/s estable de calcular involucradescomponer X en el producto de una matríz
ortogonal # una matríz 0acilmente invertible. 8sandola descomposición se tiene X =
con la matríz de # la matríz de (
construida tal ue es ortogonal 9esto es ,
=, = ' # es cero aba%o de la diagonal principal.$scribiendo
=
0
; ;
1
8/15/2019 Tópicos Avanzados de Optimización
59/212
El Modelo de =egresión:ineal
donde 1 es una matríz triangularsuperior de ( (, #
= !1N2 "
con 1 las primeras ( columnas # 2 las "ltimas ( columnas de !
tenemos
X = = 11
8/15/2019 Tópicos Avanzados de Optimización
60/212
8/15/2019 Tópicos Avanzados de Optimización
61/212
&nterpretación geomJtrica or e%emplo! trans0ormemos el vector respuesta a = ,
con componentes
1 = 1,
# 2 = 2,
La pro#ección de sobre el plano esperado es entonces
en las coordenadas #
en el sistema de coordenadas original.
0
@1
111
@<0
@
8/15/2019 Tópicos Avanzados de Optimización
62/212
btención del estimador
11
11
1111
@ ;A
A ;@
A ; i ió
8/15/2019 Tópicos Avanzados de Optimización
63/212
>escomposición envalores singulares
Teorema clave 'ea , -.
a $iste una matriz unitaria 9ortogonal
si es real! una matriz unitaria ! - - 9ortogonal si es real # una matriz - diagonalS T con Ti%F, para i7 #Ti%FUiV, siendo U1VU2VWVUs en donde s =
min 9 , -%! tal ue la descomposición envalores singulares
= &9: ;
es v/lida.
> i ió
8/15/2019 Tópicos Avanzados de Optimización
64/212
>escomposición envalores singulares
b Los n"meros U12 con
igualmente! las U12 con
8/15/2019 Tópicos Avanzados de Optimización
65/212
>escomposición en
8/15/2019 Tópicos Avanzados de Optimización
66/212
>escomposición envalores singulares *ectores característicos
[ ]
[ ]
=
=
=
=
=
=
=
=
2
2
2
2
2
2
2
2T
2
2
2
2
2
1
2
12
222221
21
21
2
1
T
2
2
2
2
2
1
2
11
221121
21
21
2
1
v
2 $1% 1 * 11 * 1 x 1 x
0
0
x 9 x 9
x 9 x 9
x
x
099
909
v
211 * 1 ,1 * 1 x 1 x
x 9 x 9
x 9 x 9
0
0
x
x
1/99
91/9
>escomposición en
8/15/2019 Tópicos Avanzados de Optimización
67/212
>escomposición envalores singulares
0 0 1/ 0 $1/% 1/
03216 232 D 4 E 4 D 4 E 4 D 16 $E 2%
0 $D /% 432 E 4 D 32 $/ $% 4 E% 4 D 64/ E 2
0/4
/44
/4
/44
//
//2
//4
//4
442
//4
//4
442
321223
3222
2
T
=
=
=
=
=
=
λ
λ
λ
λ
λ
λ
λ
λ
λ
λ
>escomposición en
8/15/2019 Tópicos Avanzados de Optimización
68/212
>escomposición envalores singulares
00
00023
0
2
2
2
2
22
22
15
5
32
15
54
5
5
32
15
52
5
52
3
1
T =
=
>escomposición en valores
8/15/2019 Tópicos Avanzados de Optimización
69/212
>escomposición en valoressingulares pseudoinversas mGnimos cuadrados
'ea el siguiente sistema de mínimoscuadrados
T
2
1
C #sa &seudoinve
30
15 15
x
x
22
2211
=
≈
>escomposición en valores
8/15/2019 Tópicos Avanzados de Optimización
70/212
>escomposición en valoressingulares pseudoinversas mGnimos cuadrados
−−=
−
=
=
=
=Σ
+
+
−−
−
−
+
6
5
65
9
1
9
1
18
1
91
91
181
9
1
9
1
18
1
9
1
9
1
18
1
15
5
15
54
15
52
5
5
5
52
3
2
3
2
3
1
2
2
2
2
2
2
2
2
30
15
15
0
000
0023
1
x
:ecuacionesdesistemadelSolución
0
A
AU V T
=egresión :ineal Simple
8/15/2019 Tópicos Avanzados de Optimización
71/212
=egresión :ineal Simple $%emplo. -oncentración de bi0enil
policlorinado en un lago como una0unción de la edadEdad2aHos5 Conc!
9C"2ppm5Edad2aHos5 Conc! 9C"2ppm5
, )! %!&
, ,! 4!
, )!( 4!, ,!$ &!)
$ $!) (!(
$ ,!% ,)!(
$ $!( 4 ,!(
% $!$ 4 ,%!&
% $!& 4 &!(
% ,!$ 3 %)!&
& %!( ,, ,$!&
& &!, ,$ ,%!&
& (!, ,$ $!$
( (! ,$ !&
C t ió 9C"
8/15/2019 Tópicos Avanzados de Optimización
72/212
Concentración 9C" vsEdad
Edad2aHos5
C o n c !
9 C " 2 p p m 5
121,5;42,
3,
2
2,
1
1,
,
Scatterplot o6 Conc! 9C"2ppm5 vs Edad2aHos5
E t bili ió d l
8/15/2019 Tópicos Avanzados de Optimización
73/212
Estabilización de lavarianza
Edad2aHos5
l n 2 9 C " 5
121,5;42,
4
3
2
1
,
Scatterplot o6 ln29C"5 vs Edad2aHos5
8/15/2019 Tópicos Avanzados de Optimización
74/212
8/15/2019 Tópicos Avanzados de Optimización
75/212
8/15/2019 Tópicos Avanzados de Optimización
76/212
8/15/2019 Tópicos Avanzados de Optimización
77/212
8/15/2019 Tópicos Avanzados de Optimización
78/212
8/15/2019 Tópicos Avanzados de Optimización
79/212
8/15/2019 Tópicos Avanzados de Optimización
80/212
8/15/2019 Tópicos Avanzados de Optimización
81/212
Má#imos mGnimos de 6unciones
8/15/2019 Tópicos Avanzados de Optimización
82/212
de varias variables sinrestricciones
$%emplo 1. 'ea
8/15/2019 Tópicos Avanzados de Optimización
83/212
de varias variables sinrestricciones
'egundasderivadas?
04 $2% $2 $% 4%
2F *
f
41$ f%0,es funciónlade")xi"ovalo# Gl 02F
f
1$%0,en")xi"ountienesetantolo &o# 04 *
f
2
1 ,0
2
1 ,02
2
$1 ,0% 2
2
>
∂
∂
=
∂
∂
<
∂
∂
Má#imos mGnimos de 6unciones
8/15/2019 Tópicos Avanzados de Optimización
84/212
de varias variables sinrestricciones
$%ercicios a resolver?
1. f(X ) = X 2 + 2 - 2X + 7 + 8
2. f(X ) = X 2 + 2X
3. f(X ) = 9X 2 + 8 2 - X
8/15/2019 Tópicos Avanzados de Optimización
85/212
8/15/2019 Tópicos Avanzados de Optimización
86/212
Derivadas arciales
Dada una 0unción de n variables @ 1, @ 2,$, @ n denotada por E :A
8/15/2019 Tópicos Avanzados de Optimización
87/212
TEO=NA C:SICA >E :AO9TIMIPACIQR
9=O":EMAS RO =EST=IR;I>OS 8n punto etremo de una 0unción
8/15/2019 Tópicos Avanzados de Optimización
88/212
8/15/2019 Tópicos Avanzados de Optimización
89/212
Má#imos MGnimos
Teorema! 'ea
8/15/2019 Tópicos Avanzados de Optimización
90/212
Má#imos MGnimos emostración. 'uponga ue ∇f 9 X ^ F ) # ue
9 X es positiva defnida. 'e prueba ue X esun mínimo local. De la epansión de )a#lor se
tiene < 9 XE; F< 9 XE∇f 9 X ); E91_2;P ̀XE91A`9 XE;Q; )
'i ; ; )[, entonces
< 9 XE; A< 9 XF91_2; ; )
o sea < 9 XE; [< 9 X
para cualuier valor de ;! ecepto ; F,! # por lotanto X es un mínimo local
8/15/2019 Tópicos Avanzados de Optimización
91/212
EEM9:O
'ea
3 * ,2 * ,2 *
0
0
0
24 * /
12 * 6
/ * 4
* f
24 * /
12 * 6
/ * 4
*
* f
*
* f *
* f
* f
10 * 24 * 12 * / * 4 * 3 * 2 * f
321
3
2
1
3
2
1
3
2
1
32123
22
21
=
=
=
=
∂
∂
∂
∂
∂
∂
=
8/15/2019 Tópicos Avanzados de Optimización
92/212
EEM9:O # el @essiano ser/
$sta ecuación es positiva para todo valor de X ! ecepto para X F)! porlo cual se puede decir ue el punto es un mínimo.
0 * / * 6 * 4 * *
*
/0006 0
004
* * * *=*
/0006 0
004
*
f
* *
f
* *
f
* *
f
*
f
* *
f
* *
f
* *
f
*
f
=
2
3
2
2
2
1
3
2
1
321
T
2
3
2
23
2
13
232
2
22
2
12
231
2
21
2
2
1
2
>
=
=
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
=
:OS METO>OS >E
8/15/2019 Tópicos Avanzados de Optimización
93/212
:OS METO>OS >E;=A>IERTE
ara alcanzar el punto alto deuna monta]a se necesitan tres
elementos?a 8n punto conocido de partida
b 8na dirección de caminata
c 8na longitud de caminata
8/15/2019 Tópicos Avanzados de Optimización
94/212
8/15/2019 Tópicos Avanzados de Optimización
95/212
MJtodos de Iradiente &niciando desde el punto
(vance en el sentido de x 1 6ace decrecer el nivel de
8/15/2019 Tópicos Avanzados de Optimización
96/212
Longitud de (vance
*ector de avance?
2//,6 f 6 ,/ $5%/2 ,/ *
5 0
12/
648 0648 12/
8
f
128 648 64
8 /2/8 /2/8 /24/? * , * f
8 /2 ,/ * , * *
1
2
2221
12
11
1
=
=
∂
∂
8/15/2019 Tópicos Avanzados de Optimización
97/212
'egunda &teración
$valuación del gradiente # la dirección# longitud de avance
25 30 $6 ,5 6 % f
$6 ,5 6 % $6 ,8 3/% * , * *
058 098 1/8
6 ,8 3/ f
2/8 9-98
6 $8 3/% $6 $% 8 3/% $6 % 4 $8 3/% ? 6 ,8 3/ f
0
3
$6 % 2/4
$/% 26 ? * f
22
21
2
2
22
1
=
=
=∂
=
=
8/15/2019 Tópicos Avanzados de Optimización
98/212
O9TIMIPACIOR >E FRCIORES>IFE=ERCIA":ESM:TI7A=IA":ES
>r! Manuel Arnoldo =odrGguezMedina
M8todo de ascenso o
8/15/2019 Tópicos Avanzados de Optimización
99/212
M8todo de ascenso odescenso acelerado
'ea
8/15/2019 Tópicos Avanzados de Optimización
100/212
M8todo de ascenso odescenso acelerado
$ncontrar un punto m/imo local de
=
=
/1/
0
4
$2% 4 $3% 6
$0% 2
$1% 4
* 4 * 6
* 2
* 4
* f
33 $2% 2 $3% 30 $1% 2 * f
2301 * * * * *
* 2 * 3 * * 2 * f
4
3
2
1
0
22220
0
4
0
3
0
2
0
1
0
24
23
22
21
M8todo de ascenso o
8/15/2019 Tópicos Avanzados de Optimización
101/212
M8todo de ascenso odescenso acelerado
$l nuevo puntoser/
2
1
2
1
2
11
0
1
01
1
1
1
4
1
3
1
2
1
1
0
1
01
/221/330412
* f * f * f !axi"ia#
/
1/
04
2
3
01
*
*
* *
* f * *
∇
=
∇
M8todo de ascenso o
8/15/2019 Tópicos Avanzados de Optimización
102/212
M8todo de ascenso odescenso acelerado $l nuevo punto óptimo ser/
ε
α
α
α
α
α
<
=
=
=
=
=
H $ * % f * f H
:alo#it"odel nte#"inaciódeC#ite#io
24 549 0240 030?6 12 * f
49 0
40 0
0
?6 1
/
1/
0
4
1/91 0
2
3
0
1
*
*
*
*
*
1/91 02136
404
02136 -404
//241/1/36 4414d
d
8 18
22221
14
13
12
11
1
1
1
111
1
1
8/15/2019 Tópicos Avanzados de Optimización
103/212
Ejemplo! M8todo de
8/15/2019 Tópicos Avanzados de Optimización
104/212
Ejemplo! M8todo deReUton $ncontrar un mínimo local de
=
=
∂
∂
∂
∂
∂
∂
=
=
93 2?9
91 259
94 139
* f
* 20 * 40 * * *
40
* 10 * 40 * * *
40
* 20 * 10 * * *
40
*
f
*
f
*
f
* f
33 920 * f 5 46 *
* * 20 * * 10 * * 40 * * *
40 * , * , * f
0
*
122
321
13
3
2
1
32
32
2
1
* 3
2
1
0
0T 0
312132
321
321
0
2
0
Ejemplo! M8todo de
8/15/2019 Tópicos Avanzados de Optimización
105/212
Ejemplo! M8todo deReUton
$l @essiano ser/
00101
01
2321
23
21
22
21
2213
2213
22
22
213
2232
31
0
* f * = * *
006 0013 0025 0
012 0025 0050 0
025 0050 0100 0
$ * % =
02? 0020 40010 20
020 40042 0010 10010 20010 1001/ 0
* * *
/040
* * *
4020
* * *
40
40 * * *
40
* * *
/010
* * *
40
20 * * *
4010
* * *
40
* * *
/0
* =
23
3221
321
∇
=
=
=
8/15/2019 Tópicos Avanzados de Optimización
106/212
8/15/2019 Tópicos Avanzados de Optimización
107/212
Má#imos mGnimos de 6unciones devarias variables con restricciones!M8todos de Optimización por:agrangeanos
$l problema a resolver es? ptimizar
8/15/2019 Tópicos Avanzados de Optimización
108/212
M8todos de Optimización por:agrangeanos
'e defne una nueva 0unción ob%etivo! llamadael Dagrangeano*
E"@ 1,@ 2,$,@ n, λ 1, λ 2,$, λ m % =
8/15/2019 Tópicos Avanzados de Optimización
109/212
8 odos de Op ac ópor :agrangeanos
La venta%a del Dagrangeano es ue setiene una 0unción sin restricciones! aunuecon m/s variables! pudiendose resolverpor medio de derivadas parciales # del
Yacobiano.
∂
∂
∂
∂
∂
∂
000000 F , *
2
F , * 2
2
F , * 2
2
F *
f
F
f
*
f
Condiciones de 0u
8/15/2019 Tópicos Avanzados de Optimización
110/212
Tuc1er
La condición necesaria para un óptimolocal! es ue el gradiente delDagrangeano sea igual a cero! es decir
* * f *, I
donde 0 , * I
i
"
1i i i
i
∑
=
=
λ
λ
Multiplicadores de
8/15/2019 Tópicos Avanzados de Optimización
111/212
p:agrange
]
* F b * f F , *, I
esola#anean Gl
0F bF * "1,,i b *
a Sujeto asujeto
* f "in * f "in
i i i
"
1i i i i
i
i i i i i
≥
=
∑
=
λ
Multiplicadores de
8/15/2019 Tópicos Avanzados de Optimización
112/212
p:agrange La condición necesaria para un
mínimo local es
0
I
F
I *
I
F , , * I
i
i
i i =
∂
∂
∂
∂
∂
∂
=
λ
λ
8/15/2019 Tópicos Avanzados de Optimización
113/212
FRCIORES COR7E'AS 'ea < 9 @ una 0unción di0erenciable! con @ ! n . 'ea @9 el @essiano! entonces losmenores principales de @! denotados
por1! 2! 3!W! n donde cada uno deestos determinantes son?
cóncavaes * f funciónla
(ositivos,son , , , (a#es"eno#eslos +neativosson
, , ,nones"eno#eslossi .ue"ient#asconvexa,es
* f entonces0,0,,0,si .eindica"Jtodo Gl
,,
* *
f
* *
f
* *
f
* *
f
, * *
f
6 42
531
n21
n
22
2
12
221
2
11
2
2
21
2
1
∇
∇
>
∇
∂
∂
∂
∂
∂
∂
∂
∂
=
∂
∂
=
FRCIORES COR7E'AS!
8/15/2019 Tópicos Avanzados de Optimización
114/212
Ejemplo
Optimización de 6uncionesmultimodales de una sola variable
8/15/2019 Tópicos Avanzados de Optimización
115/212
multimodales de una sola variableen problemas no restringidos
M8todo de Interpolación Cbica -Reuiere ue la 0unción sea di0erenciable A-onsiste en encontrar un valor óptimo de una
variable ! denominada ^! tal ue la 0unción g9 F < 9 X E s
obtenga un mínimo local! donde X # s sonvalores iniciales arbitrarios.
A X es el )nto de artida s es la dirección de bGs-)eda
8/15/2019 Tópicos Avanzados de Optimización
116/212
M8todo de InterpolaciónCbica
'ea
>ase 1. Dados valores arbitrarios de @ # s eval"e g9 F < 9 X E s .
>ase 2. $val"e g 9 # gHH 9 para valores de igual a ,! 1! 2! 4!W!1;! a, b, donde b es elprimer valor para el cual gHH 9 es negativo óg9 no 6a decrecido. $s decir! el valor óptimo^ se encuentra en el rango a IJ ≤ b.
α
α
d
d $% K =
M8todo de Interpolación
8/15/2019 Tópicos Avanzados de Optimización
117/212
M8todo de InterpolaciónCbica
>ase 3. 'e a%usta un polinomio c"bicotomando en consideración los valores g"a%,g"b%, gH"a% # gH"b%. $l valor mínimo ^ se
representa en esta iteración por e donde
21
$$b% K $a% K % L
+
$b% K $a% K ab
$b% $a% 3
$ab% L 2 $a% K $b% K
L $b% K b
2
e
=
M8todo de Interpolación
8/15/2019 Tópicos Avanzados de Optimización
118/212
pCbica
'i g"a% ó g"b% no son menores a g" e %!entonces se acepta ue ^F e "aloraroximado%.
'i g"a%I g" e %! ó g"b%I g" e %! ! entonces?
a% gH" e %K0, se repite el mismo procedimiento enel intervalo a≤ ^b! donde a=a # b= e
Regrese a la 0ase 3.b 'i g"a%I0! se repite el mismo procedimiento
en el intervalo a≤ ^b! donde a= e # b=b. Regrese a la 0ase 3.
M8todo de InterpolaciónCbi
8/15/2019 Tópicos Avanzados de Optimización
119/212
Cbica
Ejemplo! $ncuentre un mínimo local de la 0unción unimodalde una sola variable
8/15/2019 Tópicos Avanzados de Optimización
120/212
Cbica
Ejemplo! >ase 2. g" gH" % Lbseraciones
, A24 A;
1 A24 2 rimer alor donde gH" % K0
(or lo tanto b=1 a=0. 6e tiene -)e 0≤J≤1.
Ease 3.
426 0-1
2424-3
$b% K $a% K ab
$b% $a% 3
=
=
M8todo de InterpolaciónCbica
8/15/2019 Tópicos Avanzados de Optimización
121/212
Cbica
Ejemplo!
-25 f%*M$ +39 0M entonces
$b% $ % + $% $ % Co"o 25 $39 0% $%
39 0 $01% $29 5% 26 2
429 521
$ab% L 2 $a% K $b% K
L $b% K b
29 5 $1216 % $$2 $% 6 % $4%%
$$b% K $a% K % L
e
eee
e
e
2
2
21
21
21
=
<
=
=
8/15/2019 Tópicos Avanzados de Optimización
122/212
M8todo de ReUton-=ap
8/15/2019 Tópicos Avanzados de Optimización
123/212
M8todo de ReUton-=ap
8/15/2019 Tópicos Avanzados de Optimización
124/212
8/15/2019 Tópicos Avanzados de Optimización
125/212
M8todo de ReUton-=ap
8/15/2019 Tópicos Avanzados de Optimización
126/212
El M8todo de ;auss-ReUton
Iauss sugiere usar aproimaciones linealesa la 0unción esperada para iterativamenteme%orar un valor inicial o para #
mantener me%orando los estimados 6astaue no 6a#a cambio. $sto es! epandir la0unción esperada
8/15/2019 Tópicos Avanzados de Optimización
127/212
ReUton
&ncorporando todos los casos! escribimos
" % " , % E 09A , donde , es la matriz de derivadas de
( con elementos n. $sto eseuivalente a aproimar los residuales! 9 F - " % ! mediante
9
P
9
)
E ,
Q F ,
K ,
donde , F A " ) % # F - )!
El M8todo de ;auss-
8/15/2019 Tópicos Avanzados de Optimización
128/212
ReUton $ntonces calculamos el incremento de Ma)ss ,
para minimizar la suma de cuadrados de losresiduales aproimada N , K ,N! usando
,
F F 11 1 = 1, ,
0011
10
1
111
A
(unto Gl
@ ;
as +
@
8/15/2019 Tópicos Avanzados de Optimización
129/212
ReUton
$ste punto deber/ ser m/s cercano a ue 9 ,! # así nos movemos al
me%or valor del par/metro,
F )
E ) # llevamos cabo otra iteraciónmediante el c/lculo de un nuevoresidual 1 F A 9 1! una nuevamatríz de derivadas 1! # un nuevoincremento.
El M8todo de ;auss-
8/15/2019 Tópicos Avanzados de Optimización
130/212
ReUton Ejemplo! $l modelo Mic6aelisAMenten para
cinJtica de las enzimas relaciona lavelocidadS inicial de una reacciónenzim/tica con la concentración de sustrato
x a travJs de la ecuación
22
1
2
11
21
2
1
$ x %
x f
x
x f
tienese +a#es(ectocon f ndodife#encia
x
x , x f
∂
∂
∂
∂
θ
θ
θ
θ
θ
θ
θ
θ
El M8todo de ;auss-
8/15/2019 Tópicos Avanzados de Optimización
131/212
ReUton dado ue ambas derivadas involucran al menos
uno de los par/metros! el modelo es considerado nolineal.
Concentración
> a t o s
1.21.,,.5,.;,.4,.2,.,
22
2,,
1:
1,
12
1,,
:
,
Scatterplot o6 >atos vs Concentración
El M8todo de ;auss-
8/15/2019 Tópicos Avanzados de Optimización
132/212
ReUton $stimados de inicio?) F 92,! ,.,5 )
-/lculo de n,?
n x n n n, z n
0 : n10 : n2
0
1 0.02 NO 41 3' 0.2 410.0
2 0.02 4N 41 O 0.2 410.0
3 0.0O PN 8N.8O P.14 0.428O
O2N.'
'
4 0.0O 10N 8N.8O 1P.14 0.428O
O2N.'
'
' 0.11 123 118.O8 4.32 0.'N8P
O24.'
'
O 0.11 13P 118.O8 20.32 0.'N8P O24.''
N 0.22 1'P 1'0.33 8.ON 0.N333
'01.1
1
8 0.22 1'2 1'0.33 1.ON 0.N333
'01.1
1
2n
02
n01
1
n02n
n02
n
1
n0
1n
22
2102
12
1101
$ x %
x , x f deC)lculo
x
x , x f
deC)lculo
/6 /? 06 00/ 0
$06 0% 205
x
x
4102 00/ 0
$02 0% 205
x
x
0
0
∂
∂
=
∂
∂
=
=
=
θ
θ
θ
θ
θ
θ
θ
θ
η
θ
θ
η
θ
θ
El M8todo de ;auss-
8/15/2019 Tópicos Avanzados de Optimización
133/212
ReUton
(grupando las derivadas en la matríz dederivadas ,! # desarrollando unadescomposición ! de la cual
generamos 1 = 1, 0 # resolvemos para) usando 1) F 1. (uí! ) F 95.,3!A,.,1: ) # la suma de cuadrados en , F ) E ) es 69, F 12,; la cual es
muc6o m/s peue]a ue 69) F 31! #por lo tanto nos movemos a , 2213.,3! ,.,;3 ).
Datos para e%emplo deI t
8/15/2019 Tópicos Avanzados de Optimización
134/212
IaussAeton
Datos sobre demanda biouímica de oigeno9D 0ueron obtenidos por MarsHe 91
8/15/2019 Tópicos Avanzados de Optimización
135/212
IaussAeton
)abla. Demanda iouímica de ígeno vs tiempo
)iempo
9Días
D
9mg_l
)iempo
9Días
D
9mg_l1 5.3 4 1;.,
2 1,.3 1.;
3 1
8/15/2019 Tópicos Avanzados de Optimización
136/212
p %constante como
Tiempo2>Gas5
" O > 2 m g * l 5
;4321
2,.,
1:.
1.,
12.
1,.,
Scatterplot o6 "O>2mg* l5 vs Tiempo2>Gas5
$e1% $ , x % f x
12
θ
9roblemas coni i
8/15/2019 Tópicos Avanzados de Optimización
137/212
restricciones
=estricciones de igualdad QRtodo acobiano. QRtodo de deriadas
restringidas
Minimizar z =
8/15/2019 Tópicos Avanzados de Optimización
138/212
restringidas 2jacobiano5
Desarrollo matem/tico del mJtodoX
8/15/2019 Tópicos Avanzados de Optimización
139/212
Cadenas de Mar1ov
$n esencia! una cadena es unproceso en tiempo discreto en el
ue una variable aleatoria @ n vacambiando con el paso deltiempoS
8/15/2019 Tópicos Avanzados de Optimización
140/212
7ECTO=ES >E 9=O"A"I:I>A>
8n vector renglón ) = ")1, )2,$,)n % recibe elnombre de vector de probabilidad si suscomponentes son no negativas # su suma
es igual a 1. $%emplo 1.
2
1
4
1
4
1
4
1
2
1
4
3
2
1
4
1
4
3 0@ 0v 0u =
8/15/2019 Tópicos Avanzados de Optimización
141/212
Matrices Estocásticas
8/15/2019 Tópicos Avanzados de Optimización
142/212
Matrices Estocásticas
8na matriz cuadrada ( = "i8 % es estocSstica si cada una de sus flas esun vector de probabilidad.
$%emplo 2.
0
010
0
32
31
31
6 1
21
31
31
43
41
31
31
31
41
21
43
32
31
Matrices EstocásticasTeorema ,
8/15/2019 Tópicos Avanzados de Optimización
143/212
Teorema ,
'i ( # son matrices estoc/sticas!entonces el producto ( es una
matríz estoc/stica. $ntonces! enparticular! todas las potencias (n son matrices estoc/sticas.
Matrices estocásticasregulares
8/15/2019 Tópicos Avanzados de Optimización
144/212
regulares >e/nición! 8na matríz estoc/stica ( es
regular si todos los elementos de algunapotencia (m son positivos.
$%emplo 3.
#eula#noes tanto, (o# #enlón>
(#i"e# el en0 +1tienese (otenciatoda &a#a
01
01
01
ele"entotodo (a#a (ositivaes.ue +a#eula# es
1010
10
"
16 1
16 15
4
21
21
2
21
21
43
41
21
21
21
21
21
21
2
21
21
=
=
=
=
=
=
9untos /jos dematrices cuadradas
8/15/2019 Tópicos Avanzados de Optimización
145/212
matrices cuadradas 8n vector renglón no nulo ) = ")1, )2,$,)n %
es un )nto o de una matríz cuadrada ( si) permanece f%o! es decir! no cambia!
cuando se multiplica por (? ) = )
$%emplo 4.
12
es fijo (untoel .ue facil"enteobse#va Se
x -1 x -13 x x x 12 x 2 x -1 x D x -13 x x 12 x 2 E
x -1 x 32
12 x -1 x
32
12
=
=
=
=
untos f%os # matricesestoc/sticas regulares. )eorema
8/15/2019 Tópicos Avanzados de Optimización
146/212
estoc/sticas regulares. )eorema
2 'ea ( una matríz estoc/stica regular.$ntonces?
1% ( tiene un vector de probabilidad f%o "nico t !
# las componentes de t son todas positivasX2 La sucesión (, ( 2, ( 3,$ de potencias de ( se
aproima a la matríz 5 ! cu#os renglones soncada una el punto f%o t .
3 'i es cualuier vector de probabilidad!entonces la sucesión de vectores (, (2, (3,$ se aproima al punto f%o t .
9roceso estocástico
8/15/2019 Tópicos Avanzados de Optimización
147/212
9roceso estocástico
8n proceso estoc/stico se defnecomo una colección indizada deariables aleatorias T@
t T, en donde el
s)bUndice t toma alores de )ncon)nto 5 dado.
5 ? -on%unto de enteros no negativos @ ? -aracterística de interJs medible
en el tiempo t.
Cadenas de Mar1ov
8/15/2019 Tópicos Avanzados de Optimización
148/212
Cadenas de Mar1ov Las cadenas de MarHov tienen la siguiente
propiedad esencial? se dice ue un procesoestoc/stico tiene la roiedad maroiana
si { } { }
1t 10
t 1t t 1t 1t 11001t
8 ,---,8 ,8 , j ,i sucesióntoda + ,---1 ,0t (a#a
i * j * & i * ,8 * ,---,8 * ,8 * j * &
=
=
Cadenas de Mar1ov
8/15/2019 Tópicos Avanzados de Optimización
149/212
Cadenas de Mar1ov $sta propiedad es euivalente a
establecer ue la probabilidad
condicional de cualuier eventoS0uturo dados cualuier eventoSpasado # el estado actual @ t = i! esindeendiente del evento pasado #sólo depende del estado actual delproceso.
robabilidades detransición
8/15/2019 Tópicos Avanzados de Optimización
150/212
transición Las probabilidades condicionales
se llaman probabilidades de transición. 'i para cada i #
entonces se dice ue las probabilidades detransición de 9un paso son estacionarias #
por lo general se representan por i8
{ }i * j * & t 1t =
{ } { }
,1 ,0t toda (a#ai * j * & i * j * & 01t 1t =
robabilidades detransición
8/15/2019 Tópicos Avanzados de Optimización
151/212
transición
La eistencia de probabilidades de transición9de un paso estacionarias tambiJn implicaue! para cada i, , # n 9n = 0, 1,$
$stas probabilidades condicionales se
representan por # se llamanprobabilidades de transición de n pasos.
{ } { }i * j * & i * j * & 0nt nt =
nij (
8/15/2019 Tópicos Avanzados de Optimización
152/212
>e/nición de Cadenas deMar1ov
8/15/2019 Tópicos Avanzados de Optimización
153/212
Mar1ov
'e dice ue un proceso estoc/stico
es una cadena de Qaro de estado nito si tienelas siguientes características?
1. &n nGmero innito de estados.
2. Da roiedad maroiana.
3. (robabilidades de transición estacionarias4. &n con)nto de robabilidades iniciales (T@ 0 = iT
ara toda i.
,1 ,0t * t =
CA>ERAS >E MA=0O7
8/15/2019 Tópicos Avanzados de Optimización
154/212
$%emplo 1. 8na persona puede escoger entreconducir su automóvil o tomar el tren para ir altraba%o cada día. 'upongamos ue la personanunca toma el tren dos días seguidosX pero si
conduce 6asta el traba%o! entonces al díasiguiente puede mane%ar de nuevo o tomar eltren.
$l espacio de estados del sistema es t 9tren! c
9conducir. $ste proceso estoc/stico es unacadena de MarHov! porue el resultado decualuier día depende "nicamente de lo ue 6asucedido el día anterior
EEM9:O ,! MatrGz deTransición del Sistema
8/15/2019 Tópicos Avanzados de Optimización
155/212
Transición del Sistema
t c
t , 1
c
Ejemplo $
8/15/2019 Tópicos Avanzados de Optimización
156/212
Ejemplo $
)res muc6ac6os (! # - se pasanuna bola. ( siempre le pasa la bola
a # siempre le pasa la bola a -Xpero - puede! de igual manera!pasarle la bola a o a (. 'ea @ n lanAJsima persona ue recibe labola. $l espacio de estados delsistema es (! ! -
$%emplo 2
8/15/2019 Tópicos Avanzados de Optimización
157/212
$%emplo 2.
Matríz de )ransición del 'istema
A -
( , 1 ,
, , 1
- ,
Ejemplo $
8/15/2019 Tópicos Avanzados de Optimización
158/212
Ejemplo $! 'upongamos ue C 0ue la primera persona
con la bola! es decir! "0% = "0, 0, 1% es ladistribución inicial de la probabilidad.
$ntonces
esC .uede +deesbolalatena '.uede ,deesbolala
tena .uedead (#obabilid la (ases,t#esdedes(uJs s,
0
100
010
0 & ( (
0
0
100
010
0 & ( (
00100
010
100 & ( (
21
41
41
21
41
41
21
21
21
2123
21
21
21
21
21
2112
2
1
2
1
21
21
01
=
=
=
=
=
=
Ejemplo %
8/15/2019 Tópicos Avanzados de Optimización
159/212
Ejemplo %! $l territorio de un vendedor consta de tres
ciudades (! # -. unca vende en la mismaciudad en días sucesivos. 'i el vendedortraba%a en la ciudad (! entonces al díasiguiente traba%ar/ en la ciudad . 'inembargo! si traba%a en o en -! entonces laprobabilidad de ue traba%e en la ciudad ( esel doble de la probabilidad de ue lo 6aga en
cualuiera de las otras dos ciudades. ( lalarga! Bcon uJ 0recuencia traba%a elvendedor en cada una de las ciudadesC
Ejemplo %! La matríz de transición es?
010
C '
8/15/2019 Tópicos Avanzados de Optimización
160/212
La matríz de transición es?
uscamos un vector f%o "nico t de la matríz (.
=
0C
0 ' &
3132
31
32
Cen15Nel + 'en45N ,en40Nel t#abajala#a,la
15 045 040 0t
39/u3 39/u3 13u
x 3, +1, si
+
+ x
x +
+ x
0
0
010
+ x u
20
3
20
9
52
201
39/1
3
/
3
/
3
13132
32
31
32
3
1
3
2
=
=
=
=
=
=
=
=
ESTA>OSA"SO="ERTES
8/15/2019 Tópicos Avanzados de Optimización
161/212
A"SO="ERTES
$l estado ai de una cadena deMarHov se llama absorbente si elsistema permanece en el estado ai una vez ue entra en Jl. $ntonces unestado ai es absorbente si # solo si laiAJsima fla de la matríz de transición
( tiene un 1 en la diagonal principal #ceros en los dem/s sitios.
Cadenas de Mar1ov!Ejemplos
8/15/2019 Tópicos Avanzados de Optimización
162/212
je p os 1. 8na compa]ía de servicio para etinguidores de 0uego traba%a ba%o
contrato para dar servicio a todos los etinguidores en grandes 0/bricas #edifcios de ofcinas. -ada etinguidor tiene un nivel de presión reueridaue deber/ mantenerse para su operación apropiada. La compa]ía deservicio envia a sus 6ombres periodicamente a cada cliente parainspeccionar # recargar todos los etinguidores en el edifcio. La compa]íatiene un problema de precios? ara cada nuevo cliente potencial! se deber/
proponer un contrato el cual deber/ especifcar tanto el periodo deinspección como el servicio de carga! dado el tipo de etinguidores # eln"mero presente. La decisión de precio est/ basada sobre la estimación deue el valor para el cliente es de +,.2, por dia para cada etinguidor ueestJ arriba de la presión reuerida! pero es euivalente a +,.5, de pJrdidapor día para cada etinguidor ue estJ aba%o de la presión reuerida. $lproceso de pJrdida de presión es un proceso MarHov. -ada etinguidor est/en cualuiera de arriba 9estado ( o aba%o 9estado de su presión
reuerida. 8n etinguidor el cual est/ en el estado ( al inicio de unasemana tiene probabilidad de ,., de estar aba%o de la presión durante unasemana. 8na vez ue el est/ en presión ba%a el permanecer/ aba%o. )odoslos etinguidores est/n en el estado ( al terminar el periodo de inspección.-onsidere un gran edifcio de ofcinas con 1,, etinguidores. $l cargo totalpara una inspección # servicio debería ser +1,,. BuJ periodo deinspección 9en semanas podría maimizar el valor neto para el clienteC
Cadenas de Mar1ov!Ejemplos
8/15/2019 Tópicos Avanzados de Optimización
163/212
Ejemplos
'olución? $l proceso de MarHov tienedos estados? ( # . La condición deinicio es ue 9(, F 1. La matriz de
probabilidades condicionales es
(n n
(nA1
,.
8/15/2019 Tópicos Avanzados de Optimización
164/212
Ejemplos La ecuación ue relaciona
9(n a 9(nA1 es
9(n F ,.
8/15/2019 Tópicos Avanzados de Optimización
165/212
Ejemplos 8n criterio para seleccionar el periodo de
inspección es maimizar el valor neto esperadopor semana. $l valor esperado de la primersemana es
h91FE91,,9:P,.2,9,.
8/15/2019 Tópicos Avanzados de Optimización
166/212
j p
$l benefcio neto por semana para elcliente es maimizado mediante unperiodo de inspección de 3 semanas.
$l valor esperado del cliente es+21;.
8/15/2019 Tópicos Avanzados de Optimización
167/212
Ejemplos
2. $n una comunidad 6a# tres lec6erías lascuales proveen toda la lec6e consumida?Lec6ería (bott! roductos de Lec6e ranc6 #roductos de Lec6e de MarH. or simplicidadnos re0eriremos a ellos como (! # -. -adauna de las lec6erías conoce ue losconsumidores cambia de lec6ería debido ainstis0acción con el servicio # algunas otras
razones. ara simplifcación adicional de lasmatem/ticas necesarias! asumimos ue nientran clientes nuevos al mercado ni salen losactuales durante este periodo.
Cadenas de Mar1ov!Ejemplos
8/15/2019 Tópicos Avanzados de Optimización
168/212
Ejemplos -onsidere a6ora los datos del Ou%o de los clientes para cada una
de las compa]ías lec6eras como 0ue determinada por suspropios Departamentos de &nvestigación de peraciones?
>lu%o de -lientes Yunio 1 Ianancias Jrdidas Yulio 1
De De De a a aLec6ería -lientes ( - ( - -lientes ( 2,, , 3 2 , 2, 2, 22, ,, 2, , 2, 3 , 1 4
8/15/2019 Tópicos Avanzados de Optimización
169/212
Ejemplos
-/lculo de las probabilidades detransición? La lec6ería observa uepierde , clientes este mesX es decir! su
probabilidad de retener a los clientes esde ,.
8/15/2019 Tópicos Avanzados de Optimización
170/212
Ejemplos
Yunio 1 Lec6ería -lientes Jrdidas Retenidos robabilidad ( 2,, 4, 1;, 1;,_2,, F ,.5, ,, , 4, 4,_,, F ,.
8/15/2019 Tópicos Avanzados de Optimización
171/212
Ira0os
a1
a2 a3
)eoría del MJtodo 'imple
8/15/2019 Tópicos Avanzados de Optimización
172/212
)eoría del MJtodo 'imple
'e considera ue el programa lineal ensu 0orma canónica
1"decolu"navecto# unesb n1de#enlónvecto# unes *
n"o#dendees :donde
0 *
b *
asujeta
c* !ax
×
×
×
≥
≤
=
8/15/2019 Tópicos Avanzados de Optimización
173/212
>e/nición de MTS
8/15/2019 Tópicos Avanzados de Optimización
174/212
M)' es una tJcnica de an/lisis demodelos! la cual es usada para 6acerpredicciones a travJs de una escalade medición multivariable. Losmodelos son di0íciles de representaren tJrminos cuantitativos # son
etremadamente sensibles a lascorrelaciones entre las variables.
FruFruto dulceto dulce
-osec6a de los >rutos de'i 'igma
8/15/2019 Tópicos Avanzados de Optimización
175/212
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Diseño para los Desafíos de Fabricación, Diseño para Six Sigma
Volumen deVolumen de f f rurutoto
Caracterización proceso
optimación
Fruto colgandoFruto colgando bajobajo
Siete !erramientas b"sicas
FruFruto en el sueloto en el suelo
#ógica e int$ición
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Bo sabe"os lo .ue no sabe"os Bo (ode"os ob#a# en lo .ue no conoce"os
Bo sab#e"os asta .ue bus.ue"os
Bo busca#e"os (o# lo .ue no nos (#eunta"os
Bo (#eunta"os lo .ue no "edi"os
&o# lo tanto, si"(le"ente no sabe"os
3 σ Pared, Sacudir Abastecedores3 σ Pared, Sacudir Abastecedores
4 σ Pared, Mejorar Procesos4 σ Pared, Mejorar Procesos
5 σ Pared, Mejorar Diseños5 σ Pared, Mejorar Diseños
© 1994 Dr. Mikel . !arr" - #4.$
' ' g a
8/15/2019 Tópicos Avanzados de Optimización
176/212
:a distancia deMa
8/15/2019 Tópicos Avanzados de Optimización
177/212
Ma
8/15/2019 Tópicos Avanzados de Optimización
178/212
>istancia Euclidiana La distancia euclidiana entre dos puntos
# es el espacio dimensional defnido por $ x , , x , x % * (%&
$ + , , + , +% + (%& (
ℜ
$ + x % $ + x % $ + x % $ + x % $ + , x % d T
( ( G %%
&&
x x $ x % $ x % x $0 , x % d T 2
(2
1 G =
"
s la &or'a euclidia&a de x
>istancia Euclidiana
8/15/2019 Tópicos Avanzados de Optimización
179/212
>istancia Euclidiana
$n la distancia euclidiana todos loscomponentes de una observación x
contribu#en igualmente a la distancia
de x del centro.
x
>istancia Euclidiana
8/15/2019 Tópicos Avanzados de Optimización
180/212
>istancia Euclidiana
'in embargo en estadística se prefere una distanciaue para cada componente 9de variables tome lavariabilidad de esa variable dentro de ladeterminación de su distancia del centro.
(sí! componentes con alta variabilidad deberíanrecibir menos peso ue componentes con ba%avariabilidad. $sto puede ser obtenido reescalando loscomponentes.
=
=
(
(
(
(
s
+ , ,
s
+
s
x , ,
s
x
&
&
&
& y
8/15/2019 Tópicos Avanzados de Optimización
181/212
$ntonces defnimos la distancia entre# como
x +
$ + x % $ + x % s
+ x
s
+ x $ , % d $ + , x % d
T
(
( (
G
=
&
%%
&
&&
Do&de
$s , ,s% diao (%%
&
8/15/2019 Tópicos Avanzados de Optimización
182/212
x x s
x
s
x $ , % d $ , x % d
T
(
(
G
&
%
&
&''
=
=
x / todos los )u&tos co& la 'is'a dista&cia del orie&
satisace&
%
%%
&
& cs
x
s
x
(
(=
0a cual es la ecuaci& del eli)soide ce&trado e& el
orie& co& ejes )ri&ci)ales iuales a los ejes
coorde&ados. x
8/15/2019 Tópicos Avanzados de Optimización
183/212
La distancia de Ma6alanobis es usadaentre otras cosas para?
Detectar datos atípicos 9outliers enan/lisis multivariantes! encontrando ladistancia de los puntos con respecto a
su centroide 9vector de medias
Etapa I@ Construcción de una escalade medición con un espacio deMa
8/15/2019 Tópicos Avanzados de Optimización
184/212
re6erencia! >e/na las variables Jue determinan la 6alta desalud de una entidad*paciente! En una aplicaciónde diagnóstico m8dico el doctor tendrá Jueconsiderar las variables de todas lasen6ermedades para constituir un grupo saludable!
Coleccione los datos sobre todas las variables delgrupo saludable!
Calcule los valores estandarizados de lasvariables del grupo saludable!
Calcule los M>Vs de todas las observaciones! se este espacio como el punto de re6erenciapara la escala de medición!
Etapa II@ Asegure laapro#imación de la escala demedición
8/15/2019 Tópicos Avanzados de Optimización
185/212
medición &dentifue las condiciones anormales.. -alcule los MDjs correspondientes a estas
condiciones anormales siendo normalizadasusando la media # las desviaciones est/ndar delas variables correspondientes en el gruposaludable. La matriz de correlación 9o con%unto decoefcientes vectoriales IramA'c6midt! si elmJtodo de IramA 'c6midt es usadocorrespondiente al grupo saludable es usado paraencontrar los MDjs de condiciones anormales.
'i la escala es buena! los MDjs correspondientes alas condiciones anormales deber/n tener valoresm/s altos. De esta manera la aproimación de laescala es asegurada.
Etapa III@ Identi/car el conjuntode variables tiles 2etapa dedesarrollo5
8/15/2019 Tópicos Avanzados de Optimización
186/212
desarrollo5
$ncontrar el con%unto de variables"til usando arreglos ortogonales 9(js # razones '_. La razón '_!obtenida de los MDjs anormales! esusada como la respuesta para cadacombinación de (. $l con%unto "til
de variables se obtiene mediante lagananciaS en razón '_.
?5oceso deo5to>o4aliaci@4 de 5a6-
8/15/2019 Tópicos Avanzados de Optimización
187/212
Bc;6idt.
0u si 0 +0u si
.8 2 uuvu
uuuvu
uuvu
uvu
vu
v ,,v ene#ado# conjunto un ado
j j8 j u ,u
v ,u
j8
18 8 ,18 18 18 8
33422411444
22311333
11222
11
.1
j j
8 j =
≤
=
α
α
α
α
α
8/15/2019 Tópicos Avanzados de Optimización
188/212
Resumen estadistico para1
Summar 6or ',
8/15/2019 Tópicos Avanzados de Optimización
189/212
;,,44,3
Median
Mean
2,454;44424,
(ndersonADarling ormalit# )est
*ariance 3.43
'Heness A,.13;,3
Gurtosis A,.;34423
1
Minimum 34.,,,
(A'uared
1st uartile 41.,,,
Median ,.,,,
3rd uartile 2.,,,
Maimum
8/15/2019 Tópicos Avanzados de Optimización
190/212
:.4:.2:.,;.5;.;
Median
Mean
:.2,:.1:.1,:.,:.,,;.
8/15/2019 Tópicos Avanzados de Optimización
191/212
4.44.34.24.14.,3.<
Median
Mean
4.3,4.24.2,4.14.1,4.,4.,,
(ndersonADarling ormalit# ) est
* ariance ,.,254
'Heness A,.2::,3
Gurtosis A1.2:,,; 1
Minimum 3.
8/15/2019 Tópicos Avanzados de Optimización
192/212
1.,,,.
8/15/2019 Tópicos Avanzados de Optimización
193/212
Matriz de -orrelación del grupo saludableS
1 2 3 4
1 1.,,,,, A,.3;54: A,.255; A,.,55,, 2 A,.3;54: 1.,,,,, ,.1
8/15/2019 Tópicos Avanzados de Optimización
194/212
Matriz &nversa
1 2 3 4
1 1.3;54 ,.;423 ,.3
8/15/2019 Tópicos Avanzados de Optimización
195/212
Datos grupo saludableS estandarizado1.:
8/15/2019 Tópicos Avanzados de Optimización
196/212
Datos'o. 1 2 3 4 1 3, 5., 4., ,.< 2 4; :., 3.3 ,.45
3 22 :.2 3.5 ,.2 4 31 :., 3.5 ,.: 33 ;.: 3.4 ,.1 ; 35 :.1 3.5 ,.;1 : 34 5., 3.: ,.;2
5 42 ;.: 3.2 ,.4 < 3, :.4 3.< ,.34 1, 25 :.3 3.; ,.3
Datos grupo (normalS
8/15/2019 Tópicos Avanzados de Optimización
197/212
Datos (normalesS estandarizados1 2 3 4
-.4$536 3.13$ -1.1$$1 -3.149
-$.16 -$.1546 -5.631 -4.4$31
-3.49$ $.61 -.9496 -3.95$69-.669 -$.1546 -.9496 -3.36
-1.99535 -1.314 -4.664 -4.$651$
-1.31$1 $.3$ -.9496 -.91$6
-1.569 3.13$ -.43 -.$666-$.6534 -1.314 -5.559 -3.19
-.4$536 1.3911 -1.$14 -6.$$995
-.669 1.$$541 -3.419$ -3.369
>istancia de Ma
8/15/2019 Tópicos Avanzados de Optimización
198/212
La distancia de Ma6alanobis 9MD es calculadamediante la siguiente ecuación?
nco##elacióde !at#iC
vecto# del aT#ans(uest T
ablesticasva#i ca#acte#sde BO"e#o 8 ticaca#acte#sJsi"a-i ladeest)nda# esviacións