Programacion dinamica

INTRODUCCIÓN

Muchos problemas de programación matemática determinan soluciones que repercuten en la formulación de los problemas a resolver en el próximo período o etapa. Una alternativa es construir un único modelo completo que tenga un gran conjunto de variables indexadas por etapas e internalizar 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 subproblemas más pequeños y luego los ligamos. Así, programación dinamia consiste en solucionar el presente suponiendo que en cada etapa futura siempre se tomaran las decisiones correctas.

La programación dinámica (PD) determina la solución óptima de un problema de n-variables descomponiéndolo en n-etapas mediante el criterio del principio de optimalidad.

Dependiendo del problema de optimización, la naturaleza de las etapas difiere, por lo que la metodología de los cálculos para optimizar cada etapa también difiere. Quien resuelve un problema de programación dinámica utiliza su ingenio, improvisa y diseña los detalles

PROGRAMACIÓN DINÁMICA

El método de programación dinámica sirve para resolver problemas combinando las soluciones de sub-problemas. Normalmente es usada para resolver problemas de optimización, donde una solución está formada por una serie de decisiones. Sin embargo, la programación dinámica no utiliza recursividad, sino que almacena los resultados de los sub-problemas en una tabla, calculando primero las soluciones para los problemas pequeños.

Con esto se pretende evitar la repetición de cálculos para problemas más pequeños.

La programación dinámica, por el contrario, es un método ascendente: Resolvemos primero los problemas pequeños (guardando las soluciones en una tabla) y después vamos combinando para resolver los problemas más grandes.

CARACTERÍSTICAS BÁSICAS

• El problema se puede dividir en etapas, con una decisión xt que se debe tomar en cada etapa.

• Existe un cierto número de estados “s” asociados a cada etapa “t”, y la decisión realizada en una etapa afecta el estado del sistema en la siguiente etapa.

• Iniciando con la última etapa, un sub-problema de una etapa puede ser resuelto dando las decisiones óptimas para cada estado en la última etapa.

• Pueden encontrarse relaciones recursivas que permiten la solución de subproblemas de una etapa que sean empleadas para encontrar las soluciones a mayores y mayores subproblemas hasta que el último sub-problema es el problema original.

¿CUÁNDO USAR PROGRAMACIÓN DINÁMICA?

Hay dos condiciones que se deben cumplir antes de comenzar a pensar en una solución a un problema de optimización usando programación dinámica.

• Sub-estructura optima. Un problema tiene sub-estructura ´optima cuando la solución óptima a un problema se puede componer a partir

...