Programación dinámica (PD)
Enviado por wil_1993 • 23 de Abril de 2015 • 734 Palabras (3 Páginas) • 271 Visitas
Programación dinámica (PD)
La PD 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 primer autor denominado “Dynamic Programming” (Princeton University Press. Princeton, New Jersey) (Domínguez, 2000).
Inicialmente a la PD se le denominó programación lineal estocástica ó problemas de programación lineal con incertidumbre.
La programación dinámica (PD) determina la solución óptima de un problema de
n variables descomponié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 optimalidad, el cual establece que una política óptima consiste de subpolíticas ó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 de optimizació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 más 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, cada una de las cuales afecta las decisiones futuras. Proporciona un procedimiento sistemático para determinar la combinación de decisiones que maximiza la efectividad total (Taha, 2004).
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ón individual.
Características de los problemas de 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 presentarán estas características básicas que 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 cada una de ellas. En muchos problemas de programación dinámica, la etapa 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 de decisión en cada etapa es transformar el estado actual en un estado asociado con 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
...