Unidad Uno

Programación Dinámica

 

Richard Ernest Bellman

El matemático Richard Bellman inventó la programación dinámica en 1953 que se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados.

Muchos problemas de programación matemática determinan soluciones que repercuten en la formulación de los problemas a resolver en el próximo periodo o etapa. Una alternativa es construir un único modelo completo que tenga un gran conjunto de variables indexadas por etapas e iternalizar las relaciones entre etapas como una restricción del problema. Sin embargo esto pude agrandar mucho el tamaño del problema. Surge así Programación Dinámica (PD) como una alternativa de descomposición en que resolvemos sub-problemas más pequeños y luego los ligamos. Así, la programación dinámica consiste en solucionar el presente suponiendo que en cada etapa futura siempre se tomaran las decisiones correctas.

La Programación Dinámica no sólo tiene sentido aplicarla por razones de eficiencia, sino porque además presenta un método capaz de resolver de manera eficiente problemas cuya solución ha sido abordada por otras técnicas y ha fracasado.

Donde tiene mayor aplicación la Programación Dinámica es en la resolución de problemas de optimización. En este tipo de problemas se pueden presentar distintas soluciones, cada una con un valor, y lo que se desea es encontrar la solución de valor óptimo (máximo o mínimo).

La solución de problemas mediante esta técnica se basa en el llamado principio de óptimo enunciado por Bellman en 1957 y que dice:

“En una secuencia de decisiones óptima toda subsecuencia ha de ser también óptima”.

Hemos de observar que aunque este principio parece evidente no siempre es aplicable y por tanto es necesario verificar que se cumple para el problema en cuestión. Un ejemplo claro para el que no se verifica este principio aparece al tratar de encontrar el camino de coste máximo entre dos vértices de un grafo ponderado.

Para que un problema pueda ser resuelto con la técnica de programación dinámica, debe cumplir con ciertas características:

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

Ø  Cada etapa tiene un número de estados asociados a ella.

Ø  La decisión óptima de cada etapa depende solo del estado actual y no de las decisiones anteriores.

Ø  La decisión tomada en una etapa determina cual será el estado de la etapa siguiente.

En síntesis, la política óptima es de un estado s de la etapa k a la etapa final esta constituida por una decisión que transforma s en un estado s0 de la etapa k +1 y por la política óptima desde el estado s0 hasta la etapa final.

En grandes líneas, el diseño de un algoritmo de Programación Dinámica consta de los siguientes pasos:

1.    Planteamiento de la solución como una sucesión de decisiones y verificación de que ésta cumple el principio de óptimo.

2.    Definición recursiva de la solución.

3.    Cálculo del valor de la solución óptima mediante una tabla en donde se almacenan soluciones a problemas parciales para reutilizar los cálculos.

4.    Construcción de la solución óptima haciendo uso de la información contenida