Programacion Dinamica

Programación Dinámica

PROGRAMACIÓN DINÁMICA
M.C. ALFONSO CRUZ HERRERA

Características de PD
 La programación dinámica ( PD ) es un enfoque de tipo general para la solución de problemas conalgunas características bien precisas, y las ecuaciones en un problema específico que se usan se deben desarrollar para que representen ese problema en particular; por ello se requiere de creatividad yde conocimiento de la estructura general de los problemas de PD para reconocer cuándo un problema se puede resolver por medio de estos procedimientos de la PD y cómo se puede llevar a cabo. Unasolución estándar no existe. En su lugar, PD es una aproximación o procedimiento general para solución de problemas. La PD no cuenta con una formulación matemática estándar para "el" problema de PD, comoocurre en Programación Lineal; por lo anterior se dice que su formulación es “un arte”. La programación dinámica es una técnica matemática que se utiliza para la solución de problemas matemáticosseleccionados, en los cuales se toma una serie de decisiones en forma secuencial. Proporciona un procedimiento sistemático para encontrar la combinación de decisiones que maximice la efectividad total, aldescomponer el problema en etapas, las que pueden ser completadas por una o más formas (estados), y enlazando cada etapa a través de cálculos recursivos. PD tiene una estrategia basada en la filosofía“DIVIDE Y CONQUISTARAS”. Página 1









MC. Alfonso Cruz Herrera

Programación Dinámica Definiciones
 Etapa: es la parte del problema que posee un conjunto de alternativasmutuamente excluyentes, de las cuales se seleccionará la mejor alternativa. No hay una forma única para establecerlas. Estado: es el que refleja la condición o estado de las restricciones que enlazan lasetapas. Representa la “liga” entre etapas de tal manera que cuando cada etapa se optimiza por separado la decisión resultante es automáticamente factible para el problema completo.



Esquema de...