Mi Amor

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 alternativaes 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 estopude 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´onDin´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 serdividido 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 enuna 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 sen 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 deprogramaci´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
deorden 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...