La programación dinámica es un método de optimización que puede aplicarse a diferentes y numerosos problemas, algunos de los cuales ya han sido analizados en programación lineal y programación entera. Los parámetros usados en la programación dinámica pueden ser estocásticos o probabilísticos y determinísticos.

La programación dinámica tiene como finalidad encontrar una solución de un problema de optimización en forma secuencial. A diferencia de la programación lineal, la programación entera no es un algoritmo de solución única, sino más bien un método para resolver un problema grande y único solventando una secuencia de problemas más pequeños, sin importar el número de ellos. La programación dinámica permite resolver un problema que depende del tiempo en forma de una continuidad de problemas de un sólo periodo, en donde los parámetros de cada periodo dependen del periodo que se considera; es posible que no se conozca la cuantificación de cada periodo sino hasta que éste llega.

Objetivo general

Solucionar problemas que puedan resolverse a través de la programación dinámica.

Objetivos específicos

• Identificar las generalidades de la programación dinámica y cómo aplicar la metodología para la resolución de problemas en donde se deban tomar decisiones por fases.

• Aplicar algoritmos como el problema de la mochila, el cálculo de los números de Fibonacci y el cálculo de los coeficientes binomiales, entre otros, para la resolución de problemas.

• Diferenciar los métodos que se pueden emplear en la resolución de problemas, asimilando conceptos como programación dinámica determinista, estocástica y programación lineal.

La programación dinámica corresponde a una técnica para resolver problemas, a partir de la solución a subproblemas y la combinación de esas soluciones.

Durante la Segunda Guerra Mundial empezó a emplearse la programación dinámica a partir de los trabajos de investigación y los inventos que se produjeron y que se pusieron en funcionamiento durante la guerra, lo que también contribuyó al desarrollo de la matemática después de 1945.

En los años posteriores a la guerra se abrieron nuevos temas de investigación y se plantearon diversos problemas, que fueron abordados desde una perspectiva matemática. Entre estos nuevos temas se encontraba la Teoría de los Procesos de Decisión en Múltiples Pasos, que Richard Bellman (1920 - 1984) abordaba alrededor de 1952 y para los cuales fue pensada la programación dinámica.

Después de desarrollar el método en el área de los problemas de decisión discretos, Bellman y sus colaboradores se dedicaron a formular diferentes problemas en los términos de la programación dinámica. Como resultado de todo lo anterior se encontró, por ejemplo, que el Principio de Optimalidad podía ser aplicado satisfactoriamente en muchos de los problemas que se estaban presentando en la década de los años 50.

Solucionar un problema de programación dinámica requiere tener en cuenta tres pasos claves como son:

• Identificar etapas, estados y variable de decisión.
• Describir las ecuaciones de recurrencia.
• Solucionar.

La programación dinámica se aplica, generalmente, para resolver problemas de optimización, como por ejemplo:

• Problemas con diversas soluciones.
• Cada solución tiene asociado un valor.
• Se busca una solución con un valor óptimo (máximo o mínimo), entre las muchas soluciones con valor óptimo que pueden encontrarse.

Dentro de la programación dinámica algunos términos cobran relevancia, como por ejemplo:

La regla que asigna valores a varios subproblemas se denomina Función de Valor Óptimo.

La regla que asocia la primera mejor decisión con cada problema (la función P) es llamada Función de Política Óptima.

El principio de optimalidad produce o genera una fórmula o conjunto de fórmulas que relacionan varios valores de S. Esta fórmula es llamada relación de recurrencia o relación recursiva.

El valor de la función de valor óptimo S para ciertos argumentos es asumido como obvio desde el establecimiento del problema y desde la definición de S con cálculos requeridos. Estos valores obvios son llamados condiciones limitantes.

Una variable describe cuántas decisiones, hasta cierto punto, han sido tomadas y, en ese caso, si el número total de decisiones es fijo, entonces el número de etapas será igual al número de decisiones.

Las variables de estado, que son las posibles condiciones variadas en las cuales el procedimiento se encuentra en esa etapa del problema y el número de estados, pueden ser finitas o infinitas.

La decisión en cada etapa es qué tanto asignar. Las variables de estado sucesivas Xn, Xn+1 están unidas a través de la ecuación recursiva que calcula los valores de Xn+1 usando el valor de Xn y la decisión en el estado dn.

Consulte los procedimientos relacionados con la programación dinámica.

Para realizar el análisis de problemas que se pueden resolver a través de la técnica de la programación dinámica, existen varios algoritmos de solución.

Entre ellos se encuentran:

• El problema de la mochila
• Cálculo de los números de Fibonacci
• Cálculo de los coeficientes binomiales
• La subsecuencia común máxima
• El problema del camino de mínimo costo
• Problema de camino simple
• Asignación de recursos
• Multiplicación de una secuencia de matrices
• Planificación de trabajos

Frente a una serie de problemas cuyas soluciones pueden ser expresadas recursivamente en términos matemáticos, posiblemente la manera más natural de resolverlos es mediante un método recursivo. Sin embargo, el tiempo de ejecución de una solución, normalmente de orden exponencial, puede mejorarse mediante la programación dinámica.

Para resolver un problema se pueden hacer muchas divisiones y obtener subproblemas independientes, de esta manera se puede llegar más fácil a la solución del problema original, sin embargo no todos los problemas se pueden resolver de esta forma, ya que cuando los subproblemas obtenidos no son independientes sino que existe solapamiento entre ellos, la solución no resulta ser eficiente por la repetición de cálculos que conlleva. En estos casos es cuando la programación dinámica ofrece una solución aceptable.