La programación dinámica es una técnica que se utiliza para resolver diversos problemas de optimización. Esta técnica llega a la solución trabajando hacia atrás partiendo del final del problema hacia el principio, por lo que un problema enorme e inmanejable se convierte en una serie de problemas más pequeños y manejables.
Características de los problemas de programación dinámica:
1. El problema se puede dividir en etapas, cada una de las cuales requiere de una política de decisión. Algunos problemas de programación dinámica requieren tomar una serie de decisiones interrelacionadas, cada una de las cuales corresponde a una etapa del problema. 2. Cada etapa tiene cierto número de estados asociados con su inicio. Los estados son las distintas condiciones posibles en las que se puede encontrar el sistema en cada etapa del problema. El número de estados puede ser finito o infinito. 3. El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con el inicio de la siguiente etapa, quizá según una distribución de probabilidad. Los problemas de programación dinámica se pueden interpretar en términos de redes. Cada nodo corresponde a un estado. La red consistiría en columnas de nodos, donde cada columna corresponde a una etapa, en forma tal que el flujo que sale de un nodo sólo puede ir a un nodo de la siguiente columna a la derecha. El valor asignado a cada rama que conecta dos nodos puede interpretarse algunas veces como la contribución inmediata a la función objetivo que se obtiene al tomar esa política de decisión. 4. El procedimiento de solución está diseñado para encontrar una política óptima para manejar el problema completo, es decir, una receta para elaborar la política de decisión óptima para cada etapa en cada uno de los estados posibles.
No hay comentarios:
Publicar un comentario