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 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.

La programación dinámica se aplica cuando la subdivisión de un problema conduce la:

• Una enorme cantidad de subproblemas.

• Subproblemas cuyas soluciones parciales si solapan.

• Grupos de subproblemas de muy distinta complejidad.

Existen diversos tipos de programación dinámica existentes:

Programación dinámica no homogénea, frente a programación dinámica homogénea en el tiempo. Para este último caso, podremos plantearnos encontrar la solución para horizonte finito o para horizonte infinito.

Programación dinámica determinista, frente a programación dinámica aleatoria. En este caso, es interesante destacar que las cadenas de Markov con remuneración y decisión son un caso particular de programación dinámica aleatoria homogénea en el tiempo.

La programación dinámica fue desarrollada por Richard Bellman y G. B. Dantzing. Sus importantes contribuciones sobre esta técnica cuantitativa de toma de decisiones se publicaron en 1957 en un libro del primer autor denominado “Dynamic Programming” (Princeton University Press, Princeton, New Jersey). Inicialmente a la programación dinámica se le denominó programación lineal estocástica ó problemas de programación lineal con incertidumbre.

2. Características de la Programación Dinámica.

Las características de la programación dinámica se emplean para formular e identificar la estructura de los problemas de este tipo. Las características básicas que distinguen a los problemas de programación dinámica son:

1

El problema se puede dividir en etapas que requieren una política de decisión en cada una de ellas. En muchos problemas de programación dinámica, la etapa es la cantidad de tiempo que pasa desde el inicio del problema, en ciertos casos no se necesitan decisiones en cada etapa.

Cada etapa tiene un cierto número de estados asociados a ella. Por estado se entiende la información que se necesita en cualquier etapa para tomar una decisión óptima.

El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con la siguiente etapa (tal vez de acuerdo a una distribución de probabilidad).

El procedimiento de solución está diseñado para encontrar una política óptima para el problema completo, es decir, una receta para las decisiones de la política óptima en cada etapa para cada uno de los estados posibles.

Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores, (este es el principio de óptimalidad para la programación dinámica). En general en los problemas de programación dinámica el conocimiento del estado actual del sistema expresa toda la información sobre su conocimiento anterior, y esta información es necesario para determinar la política óptima de ahí en adelante.

El procedimiento de solución se inicia al encontrar la política óptima para la última etapa. La política óptima para la última etapa prescribe la política óptima de decisión para cada estado posible en esa etapa.

Se dispone de una relación recursiva que indica la política óptima para la etapa dada la política óptima para la etapa (n+1).

A pesar de esta característica, los problemas que pueden ser atacados con la programación dinámica tienen otras dos propiedades adicionales:

Sólo un número reducido de variables se debe conocer en cualquier etapa con el fin de describir al problema. En efecto, los problemas de la programación dinámica se caracterizan por la dependencia de los resultados redivados de decisiones sobre un número reducido de variables.

El resultado de una decisión en cualquier etapa altera los valores numéricos de un número reducido de variables relevantes al problema. La decisión actual ni incremente ni decrementa el número de factores sobre los cuales depende el resultado. Así, para la siguiente decisión en la secuencia, el mismo número de variables se considera.

2

Conclusiones

La programación dinámica es una técnica muy útil para tomar decisiones interrelacionadas. Requiere del planteamiento de una relación recursiva apropiada para cada problema individual. Sin embargo, da lugar a un gran ahorro de cálculos comparando con el uso de la enumeración exhaustiva para hallar la mejor combinación de decisiones, en especial para problemas grandes.

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.

3

Bibliografía

Sallán Leyes J. M., Fonollosa Guardie J., Suñé Torrents A., 2002, Métodos cuantitativos de organización industrial II, Edicions UPC, Barcelona.

Hamdy A., 2004, Investigación de operaciones, Pearson educación, México. Izar Landeta J. M., 1996, Fundamentos de investigación de operaciones para

administración, Editorial universitaria potosina, México.

4