Programación dinámica

Programación dinámica (PD; en inglés, dynamic programming, DP) es un método para resolver problemas complejos de optimización que se basa en dividir el problema original en una secuencia de subproblemas más simples. El método se aplica a procesos de toma de decisiones de múltiples etapas, donde la solución óptima del problema completo puede construirse a partir de las soluciones óptimas de sus subproblemas.

El término fue introducido por el matemático estadounidense Richard Bellman en la década de 1950. En este contexto, la palabra «programación» se utiliza en el sentido de «planificación» o «elaboración de un plan de acción óptimo», y no en el de escribir código informático.

Propiedades clave y teoremas

La aplicabilidad de la programación dinámica a un problema se determina por la presencia de dos propiedades fundamentales.

Principio de optimalidad de Bellman

El concepto central del método es el principio de optimalidad de Bellman (en inglés, Bellman's principle of optimality). Este establece que: independientemente del estado inicial y de la decisión inicial, las decisiones posteriores deben constituir una estrategia óptima con respecto al estado resultante de la primera decisión.

En otras palabras, cualquier parte de una trayectoria óptima es, en sí misma, óptima. Esta propiedad permite descomponer el problema general en una secuencia de subproblemas más simples y resolverlos de forma recursiva.

Subproblemas superpuestos

Un problema tiene la propiedad de subproblemas superpuestos (en inglés, overlapping subproblems) si, al resolverlo de forma recursiva, los mismos subproblemas surgen en repetidas ocasiones. La PD permite evitar cálculos redundantes al guardar las soluciones de los subproblemas ya resueltos (una técnica conocida como memoización o tabulación), lo que aumenta significativamente la eficiencia en comparación con un enfoque recursivo ingenuo por fuerza bruta.

Ecuación de Bellman

Del principio de optimalidad se deriva la relación de recurrencia fundamental del método: la ecuación de Bellman. Esta ecuación relaciona el «valor» (la ganancia o costo óptimo) del estado actual con los valores de los estados posteriores. En su forma general para un proceso determinista de múltiples etapas con una función objetivo aditiva, se expresa como:

$V_{k-1}(x)=\underset{y\in U(x)}{\max }\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

donde:

• $k$ — es el número de la etapa (de $m$ a 1);
• $x$ — es el estado del sistema en la etapa $k-1$;
• $y$ — es la decisión de control tomada en la etapa $k$;
• ${\phi }_k(x,y)$ — es la ganancia (o costo) en la k-ésima etapa;
• $f_k(x,y)$ — es la función que define el nuevo estado del sistema;
• $V_k(s)$ — es el valor óptimo de la función objetivo para el subproblema que comienza en la etapa $k$ en el estado $s$.

La ecuación se resuelve secuencialmente, por lo general, «hacia atrás», avanzando desde la última etapa hasta la primera.

Ejemplos de aplicación

• Problema del camino más corto en un grafo: Este problema posee la propiedad de subestructura óptima, ya que cualquier segmento de un camino más corto es, a su vez, un camino más corto. Los algoritmos de Bellman-Ford y Floyd-Warshall son ejemplos clásicos de la aplicación de la PD para resolver este problema.
• Problema de la mochila: Consiste en llenar de forma óptima una mochila de capacidad limitada con objetos de diferente valor y peso. La PD permite resolver este problema considerando los objetos secuencialmente y calculando en cada etapa el valor máximo para todas las capacidades restantes posibles.
• Problema de asignación de recursos: Consiste en distribuir un recurso limitado (por ejemplo, inversiones) entre varios proyectos para maximizar el beneficio total.

Limitaciones

La principal limitación del método es la maldición de la dimensionalidad (en inglés, curse of dimensionality), un término acuñado por Bellman para describir el crecimiento exponencial del número de estados y, en consecuencia, de la complejidad computacional, a medida que aumenta el número de variables que describen el estado del sistema. Esto restringe la aplicación práctica de la PD exacta a problemas de muy alta dimensionalidad.

Conceptos relacionados

• Investigación de operaciones
• Teoría del control óptimo
• Proceso de decisión de Márkov (generalización estocástica)
• Ecuación de Hamilton-Jacobi-Bellman (análogo para tiempo continuo)