Pdinamica

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

Programaci´n Din´mica o a
Marcel Goic F.1

IN34A: Clase Auxiliar

Esta es una versi´n bastante preliminar por lo que puede contar con numerosas faltas de ortografia y o errores no forzados. Si encuentran alguno favor de denunciarlo a mgoic@ing.uchile.cl

1

IN34A: Optimizaci´n oPag. 1

1.

Introducci´n o

Muchos problemas de programaci´n matem´tica determinan soluciones que repercuten en o a la formulaci´n de los problemas a resolver en el pro’ximo per´ o ı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 una restricci´n del problema. oSin embargo esto pude agrandar mucho el tama˜o del problema. Surge as´ Programaci´n n ı o Din´mica (PD) como una alternativa de descomposici´n en que resolvemos subproblemas a o mas peque˜os y luego los ligamos 2 . As´ programaci´n din´mia consiste en solucionar el n ı, o a presente suponiendo que en cada etapa futura siempre se tomaran las decisiones correctas.

2.

Caracter´ ısticas de unProblema de Programaci´n o Din´mica a

Para que un problema pueda ser resuelto con la t´cnica de programaci´n din´mica, debe e o a 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´n ´ptima de cada etapa depende solo del estado actual y no de las decisiones o oanteriores. La decisi´n tomada en una etapa determina cual ser´ el estado de la etapa siguiente. o a En s´ ıntesis, la pol´ ıtica ´ptima esde un estado s de la etapa k a la etapa final esta constituida o por una decisi´n que transforma s en un estado s de la etapa k + 1 y por la pol´ o ıtica ´ptima o desde el estado s hasta la etapa final.

3.

Resoluci´n de un Problema de Programaci´n Din´mioo a ca

Para resolver un problema de programaci´n din´mica debemos al menos: o a ´ ´ Identificacion de etapas, estados y variable de decision:
2 Recordemos que mucho de los algoritmos de resoluci´n de problemas lineales (Simplex en particular) son o de orden exponencial por lo que resolver m problemas de tama˜o n es mas r´pido que resolver un problema n a de tama˜o m · n n

IN34A:Optimizaci´n o

Pag. 2

• Cada etapa debe tener asociado una o mas decisones (problema de optimizaci´n), o cuya dependencia de las decisiones anteriores esta dada exclusivamente por las variables de estado. • Cada estado debe contener toda la informaci´n relevante para la toma de decisi´n o o asociada al per´ ıodo. • Las variables de decisi´n son aquellas sobre las cuales debemos definir su valor o demodo de optimizar el beneficio acumulado y modificar el estado de la pr´xima o etapa. ´ Descripcion de ecuaciones de recurrencia: Nos deben indicar como se acumula la funci´n de beneficios a optimizar (funci´n objetivo) y como var´ las funciones de o o ıan estado de una etapa a otra. ´ Resolucion Debemos optimizar cada subproblema por etapas en funci´n de los resulo tados de la resoluci´n delsubproblema siguiente. Notar que las para que las recurrencias o est´n bien definidas requerimos de condiciones de borde. e

4.
4.1.

Problemas
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´ para hacerlo, con M ≥ n. La familia ıas desea saber cuantos d´ permanecer en cada ciudad de modo demaximizar la satisfacci´n ıas o total de sus vacaciones sabiendo que para cada ciudad i existe una funci´n de satisfacci´n gi o o que es funci´n del n´mero de d´ de permanencia. o u ıas 1. Plantee un modelo de programaci´n din´mica para resolver la planificaci´n de las o a o 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 )...