Programación Dinámica

La programación dinámica encuentra la solución óptima de un problema con n variables descomponiéndolo en n etapas, siendo cada etapa un subproblema de una sola variable. Sin embargo, como lanaturaleza de la etapa difiere de acuerdo con el problema de optimización, la programación dinámica no proporciona los detalles de cómputo para optimizar cada etapa

NATURALEZA RECURSIVA DE LOS CALCULOS ENPROGRAMACION DINAMICA
Los cálculos de programación dinámica se hacen en forma recursiva ya que la solución optima de un subproblema se usa como dato para el siguiente subproblema. Para cuando seresuelve el ultimo subproblema queda a la mano la solución optima de todo problema. La forma en la que se hacen los cálculos recursivos dependen de como se descomponga el problema original. En particular,los subproblema se vinculan normalmente mediante restricciones comunes. Al pasar de un subproblema al siguiente se debe mantener la factibilidad de esas restricciones comunes.

Para resolver elproblema con programación dinámica primero se descompone en etapas, delimitadas por las líneas verticales interrumpidas. El concepto general de calcular las distancias (acumuladas) mas cortas a todos losnodos terminales de una etapa, para usarlas a continuación como datos de la etapa inmediata posterior.

PRINCIPIO DE OPTIMALIDAD
Las decisiones futuras para las etapas restantes formaran unapolítica optima independientemente de las políticas adoptadas en las etapas anteriores

RECURSION EN AVANCE Y EN REVERSA
Con las recursiones en avance y en reversa se obtiene la misma solución. Aunque elprocedimiento en avance parece mas lógico, en las publicaciones sobre programación dinámica se usa la recursión en reversa en modo invariable. La razón de esta preferencia es que, en general, larecursión en reversa es mas eficiente, desde el punto de vista computacional.
APLICACIONES DE PROGRAMACION DINAMICA
Elementos básicos de un modelo de programación dinámica:
1. Definición de las...