4 topicosavanzados 03 201502
DESCRIPTION
metodos de optimizacionTRANSCRIPT
![Page 1: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/1.jpg)
Semestre Primavera 2015
Tudela, Woywood
Métodos de Optimización
Tópicos Avanzados
![Page 2: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/2.jpg)
Contenido
• Programación entera
• Optimización flujo en redes
• Optimización multiobjetivo
• Programación dinámica
• Metaheurísticas
![Page 3: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/3.jpg)
Programación Dinámica
3
Motivación
Considere una familia que está planificando sus vacaciones y
desea viajar a través de Chile. Para ello, ha elegido n
ciudades para visitar en un orden predeterminado, donde el
número de días dedicados a visitar cada ciudad debe ser
determinado previamente.
![Page 4: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/4.jpg)
Programación Dinámica
4
Motivación (cont.)
La familia dispone de M días para sus vacaciones. De
acuerdo al interés turístico y las preferencias familiares, a
cada ciudad i se le ha asignado una función de utilidad g(xi) ,
que representa el grado de satisfacción de la familia cuando
se dedican xi días a esa ciudad. Este valor debe ser un valor
entero.
![Page 5: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/5.jpg)
Programación Dinámica
5
Motivación (cont.)
Se asume que:
• el tiempo de viaje entre ciudades es despreciable
• los días son dedicados completamente a una sola ciudad
• el orden de las ciudades que se visitarán corresponde al
índice asignado, es decir, la ciudad i-ésima está en el lugar i-
ésimo.
Formular el programa de visitas de tal manera de maximizar
la utilidad total de las vacaciones
![Page 6: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/6.jpg)
La programación dinámica es un enfoque
general para la solución de problemas en los
que es necesario tomar decisiones en etapas
sucesivas.
Objetivo
![Page 7: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/7.jpg)
Ejemplo
¿Cuánta agua extraer desde un embalse en
cada periodo con tal de minimizar los impactos
totales, considerando que se conocen los
aportes hídricos a éste?
![Page 8: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/8.jpg)
Vt Vt+1
Qet ¿Qst?
It
![Page 9: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/9.jpg)
Ejemplo
QQVV
a.s
)Q;Q;V(Imin
stett1t
stettt
t
![Page 10: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/10.jpg)
Ejemplo
En el problema anterior se conoce el estado
inicial del embalse (V0) y el estado deseado al
final de un cierto número de periodos (Vn).
![Page 11: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/11.jpg)
V0
Vn
Vt
ttnt0
![Page 12: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/12.jpg)
Programación Dinámica
Permite abordar procesos de decisión
secuenciales, donde se debe optimizar lo que
ocurre en cada periodo.
![Page 13: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/13.jpg)
Trabajo personal (en casa u otro sitio)
Identifique diferentes problemas del tipo
secuencial, señalando qué se desea optimizar
y cuál sería la variable de decisión.
![Page 14: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/14.jpg)
Programación Dinámica y
Control Óptimo
P.D. C.O.
Bellman (50’s) Pontryagin (50’s)
Análisis Discreto Análisis Continuo
![Page 15: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/15.jpg)
Programación Dinámica: definiciones
Variable de estado: variable que informa la situación del
sistema en un instante
Variable de control, instrumental o decisión: variables
sobre las cuales actúa el tomador de decisión y que afectan el
estado y la función de costos
Función de costo o retorno: objetivo general del problema
de planificación
![Page 16: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/16.jpg)
Programación Dinámica:
definiciones
En el problema del embalse y su regulación
Variable de estado: volumen del embalse
Variable de control, instrumental o decisión:
volumen de agua a extraer
Función de costo o retorno: impacto
![Page 17: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/17.jpg)
xn
yn yn-1
rn
n
yn: Variable de Estado periodo n
xn: Variable de Control o Decisión periodo n
rn: Función de Costo o Retorno periodo n
![Page 18: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/18.jpg)
Decisiones secuenciales
xn
yn yn-1
rn
n
xj
yj yj-1
rj
j
x1
y1 y0
r1
1. . . . . .
![Page 19: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/19.jpg)
Cada decisión xj, para un estado yj del
sistema, genera un costo rj y modifica el
estado del mismo, dando origen a yj-1.
Decisiones secuenciales
![Page 20: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/20.jpg)
xn
yn yn-1
rn
n
yn: Variable de Estado periodo n
xn: Variable de Control o decisión periodo n
rn: Función de Costo periodo n
![Page 21: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/21.jpg)
Las relaciones funcionales entre las variables de
estado, control y costo corresponden a
yj-1 = Tj(xj, yj) j = 1, … , n
rj = rj(xj, yj) j = 1, … , n
Decisiones secuenciales
![Page 22: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/22.jpg)
xn
yn yn-1
rn
n
T
![Page 23: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/23.jpg)
min Ψ(x) = Ψ(r1(x1, y1), … , rn(xn, yn))
s.a
yj-1 = Tj(xj, yj) j = 1, … , n
n variables de decisión, n+1 variables de
estado y n restricciones
Problema de optimización Tipo 1
![Page 24: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/24.jpg)
min Ψ(x) = Ψ(r1(x1, y1), … , rn(xn, yn))
s.a
yj-1 = Tj(xj, yj) j = 1, … , n
Este problema se puede resolver aplicando
Lagrange y las condiciones de optimalidad ya
vistas en la asignatura.
Problema de optimización Tipo 1
![Page 25: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/25.jpg)
Aplicando recursividad
yj = Tj+1(xj+1, yj+1) = Tj+1(xj+1, Tj+2(xj+2, yj+2))
yj = hj(xj+1, xj+2, … , xn, yn)
…
y0 = h0(x1, … , xn, yn) = h0(x, yn)
El estado del sistema en el periodo j depende de
las decisiones anteriores y la información inicial.
Problema de optimización Tipo 2
![Page 26: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/26.jpg)
min Ψ(x1, … , xn, yn) = Ψ(x, yn)
s.a
h(x) = h0(x, yn) - y0 = 0
n variables de decisión, y 1 restricción
Problema de optimización Tipo 2
![Page 27: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/27.jpg)
min Ψ(x1, … , xn, yn) = Ψ(x, yn)
s.a
h(x) = h0(x, yn) - y0 = 0
Este tipo de problemas se puede transformar en
uno tipo 1 agregando variables artificiales, a
través de la redefinición de las variables de
estado.
Problema de optimización Tipo 2
![Page 28: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/28.jpg)
fn(yn) = minx Ψ(r1(x1, y1), … , rn(xn, yn))
s.a
yj-1 = Tj(xj, yj) j = 1, … , n
Si la FO es separable, es decir,
Ψ(x) = r1(x1, y1) + … + rn(xn, yn) = Σi(ri(xi, yi))
Entonces fn(yn) se puede re-escribir como:
Problema de optimización Tipo 1
![Page 29: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/29.jpg)
fn(yn) = minxn{rn(xn, yn) + fn-1(yn-1)}
s.a
yj-1 = Tj(xj, yj) j = 1, … , n
donde
fn-1(yn-1) = minxi[r1(x1, y1) + … + rn-1(xn-1, yn-1)]
Problema de optimización Tipo 1
fn-2 (yn-2) = min …
![Page 30: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/30.jpg)
El problema anterior se puede re-escribir como:
fj(yj) = minxjΩj(xj, yj) j = 1, … , n
donde
Ω1(x1, y1) = r1(x1, y1)
Ωj(xj, yj) = rj(xj, yj) + fj-1(Tj(xj, yj)) j = 2, … , n
Problema de optimización Tipo 1
![Page 31: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/31.jpg)
El conjunto de ecuaciones anteriores es del tipo
recursivo, comenzando desde j = 1 (el estado
futuro), retrocediendo hacia j = n (el estado
actual conocido), realizando una optimización
en cada retroceso.
Problema de optimización Tipo 1
![Page 32: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/32.jpg)
xn
yn yn-1
rn
n
xj
yj yj-1
rj
j
x1
y1 y0
r1
1. . . . . .
Problema de optimización Tipo 1
![Page 33: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/33.jpg)
Principio de Optimalidad de Bellman
Una solución óptima tiene la propiedad que
cualquiera que sea el estado inicial, yn, y la
decisión inicial, xn, las decisiones restantes, (xn-1,
xn-2, … , x1), deben constituir una solución óptima
con respecto al estado resultante de la primera
decisión, yn-1 (Bellman, 1957).
![Page 34: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/34.jpg)
Principio de Optimalidad de Bellman
(alternativamente)
Las decisiones xn-1, xn-2, … , x1 deben optimizar el
sistema a partir de la decisión inicial xn,
independiente de cual haya sido esta decisión.
![Page 35: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/35.jpg)
![Page 36: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/36.jpg)
Ejemplo
0x
0y
xyy
a.s
]x1.0y10[Vmax
t
0
tt1t
4
0t
2tt
rt
Tt
Condición inicial
Nota: en este caso t = 0 es el presente
![Page 37: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/37.jpg)
Ejemplo
y0
x0
y1
r0
0
x1
y2
r1
1
x2
y3
r2
2
x3
y4
r3
3
x4
r4
4
![Page 38: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/38.jpg)
fj(yj) = minxjΩj(xj, yj) j = 1, … , n
donde
Ω1(x1, y1) = r1(x1, y1)
Ωj(xj, yj) = rj(xj, yj) + fj-1(Tj(xj, yj)) j = 2, … , n
Ejemplo
![Page 39: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/39.jpg)
Ejemplo
0x
a.s
x1.0y10max
4
244
t= 4
Puesto que V disminuye para todo x4, salvo para
x4 nulo, entonces x4* = 0
f4 = 10y4
![Page 40: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/40.jpg)
fj(yj) = minxjΩj(xj, yj) j = 1, … , n
donde
Ω1(x1, y1) = r1(x1, y1)
Ωj(xj, yj) = rj(xj, yj) + fj-1(Tj(xj, yj)) j = 2, … , n
Ejemplo
![Page 41: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/41.jpg)
Ejemplo
0x
xyy
y10f
a.s
fx1.0y10max
3
334
44
4233
t= 3
![Page 42: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/42.jpg)
Ejemplo
0x
a.s
)xy(10x1.0y10max
3
33233
t= 3
Resolviendo para x3, x3* = 10/0.2 = 50
f3 = 20y3 + 250
![Page 43: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/43.jpg)
Ejemplo
0x
xyy
250y20f
a.s
fx1.0y10max
2
223
33
3222
t= 2
![Page 44: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/44.jpg)
Ejemplo
0x
a.s
250)xy(20x1.0y10max
2
22222
t= 2
Resolviendo para x2, x2* = 20/0.2 = 100
f2 = 30y2 + 1.250
![Page 45: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/45.jpg)
Ejemplo
0x
xyy
250.1y30f
a.s
fx1.0y10max
1
112
22
2211
t= 1
![Page 46: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/46.jpg)
Ejemplo
0x
a.s
250.1)xy(30x1.0y10max
1
11211
t= 1
Resolviendo para x1, x1* = 30/0.2 = 150
f1 = 40y1 + 3.500
![Page 47: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/47.jpg)
Ejemplo
0x
xyy
500.3y40f
a.s
fx1.0y10max
0
001
11
1200
t= 0
![Page 48: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/48.jpg)
Ejemplo
0x
a.s
500.3)xy(40x1.0y10max
0
00200
t= 0
Resolviendo para x0, x0* = 40/0.2 = 200
f0 = 50y0 + 7.500 = 7.500
![Page 49: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/49.jpg)
Ejemplo
0
2002
00
-4.000
0
150
35
0
-250
1
100
45
0
2500
2
50
50
0
4.250
3
0
5.000
4
![Page 50: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/50.jpg)
Ejemplo
0x
0y
xyy
a.s
]x1.0y10[Vmax
t
0
tt1t
4
0t
2tt
t x y r f
0 200 0 -4.000 7.500
1 150 200 -250 11.500
2 100 350 2.500 11.750
3 50 450 4.250 9.250
4 0 500 5.000 5.000
![Page 51: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/51.jpg)
Más para revisar o leer: aplicaciones
http://www.sciencedirect.com/science/article/pii/S0968090X13000570
http://link.springer.com/article/10.1007%2Fs11269-014-0862-1
http://www.tandfonline.com/doi/abs/10.3846/13923730.2014.893909
http://ascelibrary.org/doi/10.1061/%28ASCE%29WR.1943-5452.0000342
http://ascelibrary.org/doi/10.1061/%28ASCE%29WR.1943-5452.0000361
http://www.sciencedirect.com/science/article/pii/S0968090X15000091
![Page 52: 4 TopicosAvanzados 03 201502](https://reader034.vdocumento.com/reader034/viewer/2022051316/5695d3de1a28ab9b029f77c4/html5/thumbnails/52.jpg)
Semestre Primavera 2015
Tudela, Woywood
Métodos de Optimización
Tópicos Avanzados