Programacion dinamica

Optimización entera y dinámica Programación dinámica Programación dinámica

La programación dinámica es una técnica que se utiliza para resolver diversos problemas de optimización. Esta técnicallega 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 ymanejables. 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óndiná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 dedecisió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 sepueden 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 deun 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ónobjetivo 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 paraelaborar la política de decisión óptima para cada etapa en cada uno de los estados posibles. A esto se debe que la decisión real que se toma al llegar a un estado en particular se llama política de...