PROGRAMACIÓN DINAMICA

Programación Dinámica

La programación dinámica.

Frecuentemente para resolver un problema complejo se tiende a dividir este en subproblemas, más pequeños, resolver estos últimos (recurriendo posiblemente a nuevas subdivisiones) y combinar las soluciones obtenidas para calcular la solución del problema inicial. Puede ocurrir que la división natural del problema conduzca a un gran número de subejemplares idénticos. Si se resuelve cada uno de ellos sin tener en cuenta las posibles repeticiones, resulta un algoritmo ineficiente; en cambio si se resuelve cada ejemplar distinto una sola vez y se conserva el resultado, el algoritmo obtenido es mucho mejor.
Esta es la idea de la programación dinámica: no calcular dos veces lo mismo y utilizar normalmente una tabla de resultados que se va rellenando a medida que se resuelven los subejemplares.
La programación dinámica es un método ascendente. Se resuelven primero los subejemplares más pequeños y por tanto más simples. Combinando las soluciones se obtienen las soluciones de ejemplares sucesivamente más grandes hasta llegar al ejemplar original.

Ejemplo:

    Consideremos el cálculo de números combinatorios. El algoritmo sería:

    funcion C(n, k)

        si  k=0 o k=n entonces devolver 1

        si no devolver C(n-1, k-1) + C(n-1, k)

    Ocurre que muchos valores C(i, j), con i<n y j<k se calculan y recalculan varias veces.

Un fenómeno similar ocurre con el algoritmo de Fibonacci.

La programación dinámica se emplea a menudo para resolver problemas de optimización que satisfacen el principio de optimalidad: en una secuencia óptima de decisiones toda subsecuencia ha de ser también óptima.

Ejemplo: Si el camino más corto de Madrid a Barcelona pasa por Zaragoza, la parte del camino de Madrid a Zaragoza ha de ser necesariamente el camino mínimo entre estas dos ciudades.

Podemos aplicar esta técnica  en:

•     Camino mínimo en un grafo orientado
•     Arboles de búsqueda óptimos

·         La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema, afectando a las situaciones en las que el sistema se encontrará en el futuro (denominadas estados), y a las decisiones que se plantearán en el futuro.

·         Conviene resaltar que a diferencia de la programación lineal, el modelado de problemas de programación dinámica no sigue una forma estándar. Así, para cada problema será necesario especificar cada uno de los componentes que caracterizan un problema de programación dinámica.

·         El procedimiento general de resolución de estas situaciones se divide en el análisis recursivo de cada una de las etapas del problema, en orden inverso, es decir comenzando por la última y pasando en cada iteración a la etapa antecesora. El análisis de la primera etapa finaliza con la obtención del óptimo del problema.

 MODELOS DE PROGRAMACIÓN DINÁMICA

Existen tres modelos diferentes manejados por WINQSB

.

* Problema de la diligencia (Stagecoach Problem)

* Problema de la mochila (Snapsack Problem)

* programación de producción e inventarios (Production and Inventory Scheduling)

Es una técnica que parte del principio de no calcular dos veces la misma información, por lo tanto se utilizan estructuras de almacenamiento como vectores, tablas, arreglos, archivos, con el fin de almacenarlos resultados parciales, que contribuyan a la solución final.

Este algoritmo evita calcular dos veces la misma información, manteniendo una tabla de resultados conocidos, la cual se va llenando a medida que se resuelven los subcasos. Es una técnica ascendente que normalmente, empieza por los subcasos más pequeños y más sencillos.Combinando sus soluciones, obtenemos las respuestas para los subcasos cada vez mayores, hasta que llegamos a la solución del caso original.

La programación dinámica se aplica no solo por razones de eficiencia, sino porque permite resolver de manera eficiente problemas que no se pueden resolver por otras metodologías.

El mayor número de aplicaciones se encuentra en problemas que requieren optimización, ya que se pueden hallar múltiples soluciones y así evaluarlas para hallar la óptima.

Características de un Problema de Programación Dinámica

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 sede un estado s de la etapa k a la etapa final está constituida por una decisión que transforma s en un estado s' de la etapa k + 1 y por la política óptima desde el estado si hasta la etapa final.

Resolución de un Problema de Programación Dinámica

Para resolver un problema de programación dinámica debemos al menos:

IDENTIFICACIÓN DE ETAPAS, ESTADOS Y VARIABLE DE DECISIÓN:

Cada etapa debe tener asociado una o más decisiones (problema de optimización),cuya dependencia de las decisiones anteriores está dada exclusivamente por las variables de estado.  

Cada estado debe contener toda la información relevante para la toma de decisión asociada al periodo.

Las variables de decisión son aquellas sobre las cuales debemos definir su valor de modo de optimizar el beneficio acumulado y modificar el estado de la próxima etapa.

DESCRIPCIÓN DE ECUACIONES DE RECURRENCIA: 

Nos deben indicar como se acumulala función de beneficios a optimizar (función objetivo) y como varían las funciones de estado de una etapa a otra.

RESOLUCIÓN Debemos optimizar cada subproblema por etapas en función de los resul­tados de la resolución del subproblema siguiente. Notar que las para que las recurrencias estén bien definidas requerimos de condiciones de borde.