Programación Dinámica

Capítulo 11:
Programación Dinámica
Samuel Vélez García
Clase: Investigación de Operaciones

• Programación Dinámica es una estrategia de
optimización que transforma un problema
complejo en una secuencia de problemas
simples; su característica principal es que en
proceso de optimización se usa múltiples
escenarios.

11.1 Un ejemplo elemental
• La figura 11.1 representa un mapa queconecta casas con el estacionamiento del
centro de la ciudad. Los arcos son las calles y
los nodos son las intersecciones. Las personas
experimentarán retrasos en las intersecciones,
que están indicados en minutos dentro de los
nodos. Queremos minimizar el retraso total
que cualquier persona incurrirá mientras viaja
de su casa al centro.

Figure 11.1 Street map with
intersection delays.11.1 Un ejemplo elemental
• La figura 11.2 es otra representación del
problema y se discutirá por programación
dinámica. Las casillas son las intersecciones de
la red. Las etapas son las intersecciones.
Programación dinámica reducirá el número de
cómputos moviendo de un lado al otro de
forma sistemática.

Figure 11.2 Compact representation of the
network.

11.1 Un ejemploelemental
• Nos moveremos hacia atrás de izquierda a
derecha. Si estamos en la intersección
resaltada de la figura 11.2, tendremos un
retraso de 3 minutos y luego un retraso de 8 ó
2 minutos en la última intersección.
Dependerá si nos movemos hacia arriba o
abajo. El retraso menor o solución óptima en
esta intersección será 3 + 2 = 5 minutos.

11.1 Un ejemplo elemental
• De igual formapodremos calcular el menor
retraso para cada intersección en esta
columna. La solución está en la figura 11.3.
Las flechas indican la decisión óptima, arriba o
abajo

Figure 11.4 Decisions and delays with two
intersections to go.

• Podemos movernos hacia atrás una columna y
determinar el retraso óptimo y la decisión
óptima con tres intersecciones. De la misma
forma podemos movernos unaetapa a la vez.
• La figura 11.5 resume éstos cómputos. El
menor retraso posible a través de la red es de
18 minutos.

Figura 11.5

• El análisis determina las rutas de menor
tiempo de retraso desde cada casa hasta el
estacionamiento del centro y no a cada
estacionamiento. Tres de las intersecciones
en la última columna no se usarán en este
modelo. Si una persona comienza el laintersección más arriba de la primera columna
tardará 12 minutos si sigue la ruta óptima
trazada.

• En términos de programación dinámica, cada
punto en donde las decisiones son hechas se
llama una etapa. En cualquier etapa
necesitamos conocer en cuál intersección
estamos para hacer decisiones posteriores.
• Un estado es el conocimiento que tenemos
sobre el problema para hacer decisiones,tal
como la intersección en que estamos.

Principio de Optimalidad
• Cualquier política óptima tiene la
propiedad, no importa el estado y
decisión actual, las decisiones que se
harán deben ser óptimas con respecto al
estado resultante de la decisión actual.

Función Valor óptimo
• vn(sn) = Valor óptimo (retraso mínimo) sobre
las etapas actuales y posteriores
(intersecciones), dado queestamos en el
estado sn (en una intersección en particular)
con n etapas (intersecciones) por ir.
• La función valor óptimo en cada etapa en el
proceso de decisión es dado por la columna
apropiada en la figura 11.5(c).

11.2 Formalizando la estrategia de
Programación Dinámica
• Etapas – La característica esencial es la
estructuración de problemas de optimización
en múltiples etapas,las cuales son resueltas
secuencialmente una etapa a la vez.
• Estados – Asociados con cada etapa están los
estados del proceso. Reflejan la información
requerida para acceder a las consecuencias
que la decisión actual tiene en las acciones
futuras.

EJEMPLO
• El problema para determinar el nivel de
inventario de un producto puede ser indicado
como un programa dinámico. La variable de...