programacion dinamica


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 lo largo de una serie de etapas. En otras palabras, trata de encontrar la secuencia de decisiones que optimizan el comportamiento de un proceso polietapico.

La naturaleza del razonamiento que se debe realizar en programacióndiná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; una vez conocida la naturaleza de las variables de decisión, y expresadas la función objetivo y las restricciones en función de esas variables, la resolución del modelo puede confiarse, sin mayores problemas, a un programainformático.

Esta no admite una resolución sistemática de este tipo; mas que un modelo concreto, es una estrategia de resolución común a muchas situaciones en principios diferentes entre sí. Además, es frecuente que la resolución del modelo este muy relacionada con la situación que se ha de modernizar. En contrapartida, las simplificaciones que en ocasiones deben realizarse en programación linealpara poder resolver el modelo no son necesarias en programación dinámica, que admite gran variedad de relaciones entre variables.


Características
Una de las características esenciales es la toma de decisiones en secuencia.
El problema se puede dividir en etapas, las cuales requieren de una política de decisión en cada una de ellas.
Es necesario conocer pocos datos para describir el problemaen cada etapa.
La dependencia del resultado de las decisiones de una pequeña cantidad de variables.
En cualquier etapa, el resultado de una decisión, altera los valores numéricos de la pequeña cantidad de variables relacionadas con el problema.
Cada etapa tiene un cierto número de estados asociados a ella, estos son las distintas condiciones posibles en las que se puede encontrar el sistema encada etapa del problema.
El efecto de la política de decisión en cada etapa, es transformar el estado actual en un estado asociado con la siguiente etapa.
La decisión real no aumenta ni disminuye el número de factores de los que dependen los resultados.
El procedimiento de solución está diseñado para encontrar una política de solución óptima, para el problema planteado.
Esta nos permitellegar a decisiones óptimas para periodos o etapas que todavía están en el futuro, a pesar de las decisiones incorrectas que se hayan tomado en el periodo.
Dado el estado actual, una política óptima para las etapas restantes es independientes de la política adoptada en etapas anteriores.
El procedimiento de solución se inicia al encontrar la política óptima para las últimas etapas. Ya que estaprescribe la política óptima de decisión para cada estado posible en esa etapa.
Se establece una función recursiva que identifique la política óptima para la etapa N dada la política óptima para la etapa N+1.
Naturaleza
Fue desarrollada por Richard Bellman y G.B Dantzing, sus importantes contribuciones sobre esta técnica cuantitativa de toma de decisiones se publicaron en 1957 en un libro del primerautor denominado “Dynamic programming”.
Inicialmente se le denomino “programación lineal estocástica o problemas de programación lineal con incertidumbre”. A través de los años, la PD se ha desarrollado como una técnica cuantitativa para resolver una gran variedad de problemas, se basa en el principio de optimilidad, el cual establece que una política óptima consiste de sub políticas óptimas.Así, la PD se define como una técnica matemática que resuelve una serie de decisiones secuenciales, cada una de las cuales afecta las decisiones futuras.
Esto es de vital importancia puesto que rara vez se puede encontrar una situación operacional donde las implicaciones de una decisión no se extienda a futuro. Los métodos se pueden extrapolar a problemas en los cuales el tiempo no es una variable...