PROGRAMACION DINAMICA
La programación dinámica (PD) es un procedimiento matemático diseñado principalmente para mejorar la eficiencia de cálculo de problemas de programa con matemática seleccionados, descomponiéndolos en subproblemas de menor tamaño y por consiguiente, más fáciles de calcular. La programación dinámica comúnmente resuelve el problema en etapas, donde en cata etapa interviene exactamente una variable de optimización. Los cálculos en las diferentes etapas se enlazan a través de cálculos recursivos de manera que se genere una solución óptima factible a todo el problema.
MODELO DEL PD
Una etapa en PD se define como la parte del problema que posee un conjunto de alternativas mutuamente excluyente, de las cuales se seleccionara la mejor alternativa.
La idea básica e PD consiste prácticamente en eliminar el efecto de la interdependencia entre etapas, asociando una definición de estado con cada etapa. Un estado se define normalmente como aquel que refleja la condición de las restricciones que enlazan las etapas.
ECUCACION RECURSIVA DE RETROCESO
Este método de cálculo se conoce como procedimiento de avance porque los cálculos avanzan de la primera hasta la última etapa. Sin embargo, cuando el lector estudie la mayoría de las obras dedicadas a la programación dinámica, advertirá que la ecuación recursiva se construye de manera que los cálculos comienzan en la última etapa y después “regresan” hacia la etapa 1. Este método recibe el nombre de procedimiento de retroceso.
La diferencia principal entre los métodos de avance y de retroceso ocurre en la forma como definimos el estado del sistema.
MAS ACERCA DE LA DEFINICION DEL ESTADO
El estado representa la “liga” entre etapas (subsecuentes) de tal manera que cuando cada etapa se optimiza por separado, la decisión resultante es automáticamente factible para el problema completo. Permite que se hagan decisiones óptimas para las etapas restantes sin tener que comprobar el efecto de decisiones futuras sobre decisiones que se han tomado anteriormente. No existe una forma fácil de definir el estado, pero pueden encontrarse pistas haciendo las dos preguntas siguientes:
1.- ¿Qué relación enlazan las etapas?
2.- ¿Qué información es necesaria para tomar decisiones factibles en la etapa actual sin verificar la factibilidad de decisiones hechas en etapas anteriores?
PROBLEMA DE DIMENSIONALIDAD EN PROGRAMACION DINAMICA
En todos los problemas de programación dinámica, los estados del sistema se han descrito solamente con una variable. En general, estos estados pueden constar de n variables (>=1) en cuyo caso se dice que el modelo de programación dinámica tiene un vector de estados multidimensional. Un aumento en las variables de estado significa un aumento en el número de evaluaciones para las diferentes alternativas en cada etapa. Este problema se conoce como el problema de la dimensionalidad.
TAHA
No hay comentarios:
Publicar un comentario