Programación dinámica

1. ¿A qué se le llama Programación Dinámica?

La programación dinámica consiste en una técnica que permite determinar de manera eficiente las decisiones que optimizan el comportamiento de un sistema que evoluciona a lo largo de una serie de etapas. En otras palabras, trata de encontrar la secuencia de decisiones que optimiza el comportamiento de un proceso polietápico.

Ciertos problemas de optimización sólo pueden ser resueltos cuando se les descompone en una serie de etapas. La solución secuencial de los problemas de decisión asociados con cada etapa es equivalente a la solución del problema de decisión del sistema original, este procedimiento secuencial se conoce como programación dinámica.

Este Método maneja los casos en forma secuencial, dividiendo un problema grande en varios pequeños, donde cada uno de éstos se irá solucionando tomando la decisión que optimice la función objetivo, la cual a semejanza de la programación lineal puede ser una utilidad sujeta a maximización o bien un costo que busca minimizarse. Cada problema a su vez tendrá sus propios parámetros, los que influirán para la resolución que deba tomarse. Luego se eslabona este problema pequeño con el que sigue en el orden determinado conforme a la secuencia inicial. Con esto lo que se logra es un ahorro en el número de cálculos que deben hacerse para solucionar el problema total, dado que no se ejecutan todas las opciones que puede tener el mismo, puesto que de la parte que ya se ha analizado se toma la mejor decisión que contribuya a la optimización de la función objetivo. La programación dinámica determina la solución óptima de un problema de n variables, descomponiéndola en n etapas, con cada etapa incluyendo un sub-problema de una sola variable.

Para cada etapa debe definirse una variable de decisión xn. Si el sistema tiene k estados en esa etapa, una política será un vector de k componentes, cuya componente e-sima es el valor de la variable de decisión para el estado e en la etapa n.

La esencia de la estrategia de la programación dinámica se expresa mediante el principio de optimalidad. En un modelo de programación dinámica, la política óptima para las etapas que faltan hasta la finalización del proceso es independiente de las políticas adoptadas en las etapas anteriores. Esta propiedad es la esencia de la programación dinámica y tiene dos implicaciones importantes: en primer lugar la evolución futura del sistema a partir de una determinada etapa depende exclusivamente del estado en que nos encontramos en esa etapa. Entonces que todo modelo de programación dinámica debe cumplir la propiedad markoviana, sólo necesitamos conocer la situación del sistema en el momento presente para determinar su evolución en las etapas siguientes. En segundo lugar, un modelo de programación dinámica debe resolverse hacia atrás. Esto admite dos formulaciones, en esencia equivalentes:

Si n son las etapas que ya ha realizado el sistema, conociendo la política óptima para la etapa n + 1, podremos encontrar la política óptima para la etapa n.

Si N son las etapas que faltan para que finalice la evolución del sistema, conociendo la política óptima cuando faltan N – 1 etapas, podremos encontrar la política óptima para cuando falten N etapas. Esta segunda formulación es especialmente útil para problemas de horizonte infinito.

El proceso de solución se inicia al encontrar la política óptima para la última etapa.

La mayor parte de las veces, la programación dinámica obtiene soluciones con un avance en reversa, desde el final de un problema hacia el principio con lo que un problema grande y engorroso se convierte en una serie de problemas más pequeños y más tratables.

La programación dinámica puede ser determinística, es decir, que los parámetros del problema se conozcan exactamente, o bien puede ser probabilística o estocástica, cuando aquellos vienen dados por una función de probabilidad.

Frecuentemente se utiliza para resolver problemas complejos en el cual 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

...