Programación Dinámica

República Bolivariana de Venezuela
Ministerio del Poder Popular para la Educación Universitaria
I.U.P “Santiago Mariño”
Barinas Edo. Barinas


















Integrantes:
Barazarte Jesus
C.I: 20.865.616



Barinas, 15 de julio de 2015
INTRODUCCION

La PD fue desarrollada por Richard Bellmany G B. Dantzing. Sus importantes contribuciones sobre esta técnica cuantitativa de toma de decisiones se publicaron en 1957 en un libro del primer autor denominado “Dynamic Programming”. Inicialmente a la PD se le denomino programación lineal estocástica o problemas de programación lineal con incertidumbre.
La programación dinámica determina la solución óptima de un problema de n. variablesdescomponiéndola en n. etapas, con cada etapa incluyendo un subproblema de una sola variable. La principal contribución de la PD es el principio de la optimalidad, el cual establece que una política óptima consiste de subpoliticas óptimas, un marco de referencia para descomponer el problema en etapas.
La programación dinámica es una técnica que se puede aplicar para resolver muchos problemas deoptimización. La mayor parte de las veces, la programación dinámica obtiene soluciones con un avance en reversa, desde el final de un problema hacia el principio con lo que un problema grande y engorroso se convierte en una serie de problemas pequeños y más tratables.
Así, la programación dinámica se puede definir como una técnica matemática útil que resuelve una serie de decisiones secuenciales, cadauna de las cuales afecta las decisiones futuras. Proporciona un procedimiento sistemático para determina la combinación de decisiones que maximiza la efectividad total.
En contraste para el problema de programación dinámica, trata de un enfoque de tipo parcial para la solución de problemas y las ecuaciones específicas que se usan se deben desarrollar para que represente cada situaciónindividual.










Características de la Programación Dinámica

Las características de la programación dinámica se emplean para formular e identificar la estructura de los problemas de este tipo.
A continuación se presentaran estas características básicas que se distinguen a los problemas de programación dinámica.
1. El problema se puede dividir en etapas que requieren una política de decisión en cadauna de ellas. En muchos problemas de programación dinámica, las etapas es la cantidad de tiempo que pasa desde el inicio del problema, en ciertos casos no se necesitan decisiones en cada etapa.
2. Cada etapa tiene un cierto número de estados asociados a ella. Por estado se entiende la información que se necesita en cualquier etapa para tomar una decisión óptima.
3. El efecto de la política dedecisión en cada etapa es transformar el estado actual en un estado asociado en la siguiente etapa (tal vez de acuerdo a una distribución de probabilidad).
4. El procedimiento de solución está diseñado para encontrar una política óptima para el problema completo, es decir, una receta para las decisiones de la política optima en cada etapa para cada uno de los estados posibles.
5. Dado el estadoactual, una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores. (este es el principio de optimalidad para la programación dinámica). En general en los problemas de PD, el conocimiento del estado actual de sistema expresa toda la información sobre su comportamiento anterior, y esta información es necesaria para determinar la política óptima de ahí enadelante.
6. El procedimiento de solución se inicia al encontrar la política óptima para la última etapa. La política óptima para la última etapa prescribe la política óptima de decisión para cada estado posible en esa etapa.
7. Se dispone de una relación recursiva que indica la política óptima para la etapa dada la política óptima para la etapa (n+1)

A pesar de esta característica, los...