Programacion dinamica

PROGRAMACION DINAMICA
La programación dinámica consiste en una técnica que permite determinar de manera eficiente las decisiones que optimizan el comportamiento de un sistema que evoluciona a lolargo de una serie de etapas. En otras palabras, trata de encontrar la secuencia de decisiones que optimizan el comportamiento de un proceso polietápico.
La naturaleza del razonamiento que se debe derealizar en programación dinámica es muy diferente al de la programación lineal. En programación lineal, intenta describir una determinada situación en términos de un modelo matemático determinado; unavez conocida la naturaleza de las variables, la resolución del modelo puede confiarse, sin mayor problema, a un programa informático, la programación dinámica no admite una resolución sistemática deeste tipo.
La Programación Dinámica no sólo tiene sentido aplicarla por razones de eficiencia, sino porque además presenta un método capaz de resolver de manera eficiente problemas cuya solución hasido abordada por otras técnicas y ha fracasado.
Donde tiene mayor aplicación la Programación Dinámica es en la resolución de problemas de optimización. En este tipo de problemas se pueden presentardistintas soluciones, cada una con un valor, y lo que se desea es encontrar la solución de valor óptimo (máximo o mínimo).
La solución de problemas mediante esta técnica se basa en el llamadoprincipio de óptimo enunciado por Bellman en 1957 y que dice:

“En una secuencia de decisiones óptima toda subsecuencia ha de ser también óptima”.

Hemos de observar que aunque este principio pareceevidente no siempre es aplicable y por tanto es necesario verificar que se cumple para el problema en cuestión. Un ejemplo claro para el que no se verifica este principio aparece al tratar de encontrar elcamino de coste máximo entre dos vértices de un grafo ponderado.

Para que un problema pueda ser abordado por esta técnica ha de cumplir dos condiciones:
• La solución al problema ha de ser...