Programacion dinamik

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´mico dentro delmodelo (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 deprogramaci´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 la formulaci´n o a o o backward. Cabe se˜alar quetambi´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 del horizonte de tiempo) La funci´n de interrelaci´n entre estados de2 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 problemaen 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 o

El Modelo de Programaci´n Din´mica o a
2. Variables de Estado: yk Variables que caracterizan lasituaci´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 su posterior optimizaci´n. o 3. Variables de Decisi´n: xk o Decisiones cuantificables cuyos valores se intentadeterminar 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 las variables de estado, es decir, para valores distintos de las variables de estado pueden haber distintos espacios de solucionesfactibles.

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 etapa final. 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 unao 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 problema en cada etapa. o 7. Condiciones de Borde: y1 = M y fn+1(yn+1) = F Limitaciones que deben imponerse al problema, corresponden a condiciones...