Guia Programacion Dinamica M



Universidad de Chile
Facultad de Ciencias F´ısicas y Matem´aticas
Departamento de Ingenier´ıa Industrial


















IN34A: Clase Auxiliar
Programaci´on Din´amica



Marcel Goic F.1






























1Esta es una versi´on bastante preliminar por lo que puede contar con numerosas faltas de ortografia y errores no forzados. Si encuentran alguno favor de denunciarlo amgoic@ing.uchile.cl
IN34A: Optimizaci´on Pag. 1

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 index-adas por etapas e iternalizar las relaciones entre etapas como unarestricci´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 unProblema 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 decisionesanteriores.

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´ami-caPara resolver un problema de programaci´on din´amica debemos al menos:

Identificacion´ de etapas, estados y variable de decision:´

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


1• Cadaetapa 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.

2• Cada estado debe contener toda la informaci´on relevante para la toma de decisi´on asociada al per´ıodo.

3• Las variables de decisi´on son aquellas sobre las cuales debemos definir su valor de modo de optimizar elbeneficio acumulado y modificar el estado de la pr´oxima etapa.

Descripcion´ 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.

Resolucion´ Debemos optimizar cada subproblema por etapas en funci´on de los resul-tados de la resoluci´on del subproblema siguiente. Notar quelas para que las recurrencias est´en bien definidas requerimos de condiciones de borde.


4. Problemas


4.1. Problema 1

La familia Sampsons va a salir de vacaciones desde su ciudad natal Sprangfield. La familia desea visitar n ciudades y dispone de un total de M d´ıas para hacerlo, con M ≥ n. La familia desea saber cuantos d´ıas permanecer en cada ciudad de modo de maximizar la satisfacci´ontotal de sus vacaciones sabiendo que para cada ciudad i existe una funci´on de satisfacci´on gi que es funci´on del n´umero de d´ıas de permanencia.


1. Plantee un modelo de programaci´on din´amica para resolver la planificaci´on de las vacaciones de los Sampsons.

2. Suponga que n = 3 y M = 5 y que las funciones de beneficio gk(xk) vienen dadas por:


g1(x1)
g2(x2)
g3(x3)
xk = 0
0
0
0
xk = 1...