Programacion dinamica

CAP´
ITULO 6
´
´
PROGRAMACION DINAMICA

Programaci´n Din´mica
o
a

in34a - Optimizaci´n
o

Programaci´n Din´mica
o
a
En muchos casos las decisiones del pasado afectan los escenarios del futuro. En estos
casos se pueden tomar 2 opciones: asumir que el efecto temporal o din´mico es
a
poco relevante y solo considerar modelos de un periodo (PPL) o considerar el efecto
din´micodentro del modelo (programaci´n din´mica).
a
o
a
La programaci´n din´mica nace despu´s de la segunda guerra mundial, donde se
o
a
e
present´ la necesidad de resolver procesos de decisi´n en m´ltiples etapas. Est´ t´cnica
o
o
u
a e
usa funciones recursivas y un principio de optimalidad, desarrollado por Bellman, para
resolver este tipo de problemas.
En este cap´
ıtulo se desarrollar´la teor´ b´sica de programaci´n din´mica, su uso en el
a
ıa a
o
a
modelamiento y resoluci´n de problemas. Adem´s se expondr´n ejemplos que permitan
o
a
a
visualizar de mejor forma su uso y resoluci´n.
o

Programaci´n Din´mica
o
a

1

in34a - Optimizaci´n
o

El Modelo de Programaci´n Din´mica
o
a
La formulaci´n del modelo que se ver´ a continuaci´n corresponde a laformulaci´n
o
a
o
o
backward. Cabe se˜alar que tambi´n existe la formulaci´n forward, pero no se ver´ en
n
e
o
a
este cap´
ıtulo.
El concepto de programaci´n din´mica se basa en el uso de ecuaciones funcionales y
o
a
el principio de optimalidad de Bellman. Las ecuaciones funcionales corresponden a:
Las funciones que dan cuenta de la funci´n objetivo (desde una etapa k hasta el fin
o
delhorizonte de tiempo)
La funci´n de interrelaci´n entre estados de 2 etapas consecutivas.
o
o
Condiciones de borde.

Programaci´n Din´mica
o
a

2

in34a - Optimizaci´n
o

El Modelo de Programaci´n Din´mica
o
a
A continuaci´n se muestra la formulaci´n backward:
o
o
fk (yk ) =

m´x
a
{Hk (yk , xk , fk+1(yk+1))}
xk ∈ Ak (yk )
yk+1 = Tk (yk , xk )
k = n, n − 1, . . . , 1
y1= M
fn+1(yn+1) = F

Describamos cada elemento:
1. Etapas: k
Particiones del problema en los cuales se pueden tomar decisiones que no dependan
de estados anteriores, sino s´lo del estado actual. Ej: d´ meses, a˜os, etapas de
o
ıas,
n
producci´n en una l´
o
ınea, etc. Para su programaci´n debe existir una etapa final
o
(n).
Programaci´n Din´mica
o
a

3

in34a - Optimizaci´n
oEl Modelo de Programaci´n Din´mica
o
a
2. Variables de Estado: yk
Variables que caracterizan la situaci´n en la que se encuentra el sistema en una
o
etapa dada. Est´s variables dan la independencia a la etapa actual de las etapas
a
anteriores, por lo que deben existir tantas variables de estado como las que permitan
establecer en que condiciones comienza (o finaliza) una etapa para suposterior
optimizaci´n.
o
3. Variables de Decisi´n: xk
o
Decisiones cuantificables cuyos valores se intenta determinar por medio de la
resoluci´n del modelo. Su valor determina el valor de las variables de estado de las
o
etapas futuras.
4. Espacio de Soluciones Factibles: Ak (yk )
Espacio de soluciones factibles de las variables de decisi´n. Estos valores pueden
o
depender de lasvariables de estado, es decir, para valores distintos de las variables
de estado pueden haber distintos espacios de soluciones factibles.

Programaci´n Din´mica
o
a

4

in34a - Optimizaci´n
o

El Modelo de Programaci´n Din´mica
o
a
5. Ecuaciones de Recurrencia:
Funci´n de Recursi´n: fk
o
o
Ecuaci´n que indica como se acumula la funci´n de valor desde la etapa k hasta la
o
o
etapafinal.
Funci´n de Transformaci´n: yk+1 = Tk (yk , xk )
o
o
Ecuaci´n que indican como se relaciona las variables de estado y decisi´n de una
o
o
etapa con la variable de estado de la etapa posterior.
6. Funci´n de Valor o Beneficio: (Funci´n Objetivo) Hk
o
o
Criterio de comparaci´n entre distintos valores de las variables de estado. Es el
o
objetivo a alcanzar por la resoluci´n del...