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 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 de programació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 las alternativas 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 el problema. La forma de los cálculos recursivos depende de la descomposición del problema original. En general, los sub-problemas se unen a través de algunas restricciones comunes. A medida que se avanza de un sub-problema a otro, hay que dar la razón de la viabilidad de estas restricciones. Los problemas de la programación dinámica ocupan recursiones tanto hacia adelante como hacia atrás, las que deben producir la misma solución. Aún cuando el procedimiento hacia delante parece más lógico, la programación dinámica utiliza generalmente la recursión hacia atrás, puesto que es más eficiente en los cálculos.

CONCEPTOS BÁSICOS

• Etapa: es un periodo o fase perfectamente identificable del problema, en el cual es necesario tomar una decisión de acuerdo a una política establecida.

• Estado: es el conjunto de alternativas posibles que se encuentran dentro de una etapa.

• Políticas de decisión: es la mecánica para elegir una alternativa que nos llevará a i estado en la siguiente etapa.

• Objetivo: es la meta a alcanzar tomando las decisiones de acuerdo a la política de decisión establecida en cada etapa del problema.

• Principio de optimalidad de Bellman: la política de decisión óptima en cualquier etap2 depende solamente del estado en esa etapa, y no de las decisiones tomadas en etapas anteriores.

Un problema de programación dinámica puede representarse mediante una red en la cual los nodos representen los diferentes estados en una etapa, y las ramas representan las decisiones que se toman para ir a la siguiente etapa.

Es muy importante hacer notar que no se pueden tomar dos decisiones ni simultáneamente ni sucesivamente dentro de una misma etapa, por lo tanto, los estados dentro de una misma etapa nunca se podrán conectar entre sí, pues al elegir una decisión, las deben de quedar automáticamente excluidas.

...