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 pudeagrandar 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 den-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 deprogramació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 losproblemas 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, conuna 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 encontrarserelaciones 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 de soluciones óptimas de su sub-problema.
• Superposición de Problemas. El cálculo de la solución ´optima implica resolver muchas veces un mismo sub-problemas. La cantidad de sub-problema es “pequeña”.

MÉTODO GENERAL

Aspectos a definir en un algoritmo deprogramación dinámica:

• Ecuación recurrente, para calcular la solución de los problemas grandes en función de los problemas más pequeños.
• Determinar los casos base.
• Definir las tablas utilizadas por el algoritmo, y cómo son rellenadas.
• Cómo se recompone la solución global a partir de los valores de las tablas.
• Definición de las etapas
• Definición de lasalternativas en cada etapa
• Definición de los estados para cada etapa

NATURALEZA RECURSIVA EN LOS CÁLCULOS DE LA PD

Los cálculos de la programación dinámica se hacen recursivamente, en el sentido de que la solución óptima de un sub-problema se utiliza como una entrada para el siguiente sub-problema. Al momento de resolver el último sub-problema, se tendrá la solución óptima para todo...