Caracterısticas de un Problema de Programaci´on Din´amica

1. Introducci´on

Muchos problemas de programaci´on matem´atica determinan soluciones que repercuten en

la formulaci´on de los problemas a resolver en el pro’ximo per´ıodo o etapa. Una alternativa

es construir un ´unico modelo completo que tenga un gran conjunto de variables indexadas

por etapas e iternalizar las relaciones entre etapas como una restricci´on del problema.

Sin embargo esto pude agrandar mucho el tama˜no del problema. Surge as´ı Programaci´on

Din´amica (PD) como una alternativa de descomposici´on en que resolvemos subproblemas

mas peque˜nos y luego los ligamos 2. As´ı, programaci´on din´amia consiste en solucionar el

presente suponiendo que en cada etapa futura siempre se tomaran las decisiones correctas.

2. Caracter´ısticas de un Problema de Programaci´on

Din´amica

Para que un problema pueda ser resuelto con la t´ecnica de programaci´on din´amica, debe

cumplir con ciertas caracter´ısticas:

Naturaleza secuencial de las decisiones: El problema puede ser dividido en etapas.

Cada etapa tiene un numero de estados asociados a ella.

La decisi´on ´optima de cada etapa depende solo del estado actual y no de las decisiones

anteriores.

La decisi´on tomada en una etapa determina cual ser´a el estado de la etapa siguiente.

En s´ıntesis, la pol´ıtica ´optima esde un estado s de la etapa k a la etapa final esta constituida

por una decisi´on que transforma s en un estado s0 de la etapa k +1 y por la pol´ıtica ´optima

desde el estado s0 hasta la etapa final.

3. Resoluci´on de un Problema de Programaci´on Din´amica

Para resolver un problema de programaci´on din´amica debemos al menos:

Identificaci´on de etapas, estados y variable de decisi´on:

2Recordemos que mucho de los algoritmos de resoluci´on de problemas lineales (Simplex en particular) son

de orden exponencial por lo que resolver m problemas de tama˜no n es mas r´apido que resolver un problema

de tama˜no m · n

IN34A: Optimizaci´on Pag. 2

• Cada etapa debe tener asociado una o mas decisones (problema de optimizaci´on),

cuya dependencia de las decisiones anteriores esta dada exclusivamente por las

variables de estado.

• Cada estado debe contener toda la informaci´on relevante para la toma de decisi´on

asociada al per´ıodo.

• Las variables de decisi´on son aquellas sobre las cuales debemos definir su valor

de modo de optimizar el beneficio acumulado y modificar el estado de la pr´oxima

etapa.

Descripci´on de ecuaciones de recurrencia: Nos deben indicar como se acumula

la funci´on de beneficios a optimizar (funci´on objetivo) y como var´ıan las funciones de

estado de una etapa a otra.

...