Investigacion De Operaciones
Enviado por Eibdy • 14 de Noviembre de 2012 • 2.175 Palabras (9 Páginas) • 405 Visitas
PROGRAMACION DINAMICA
HISTORIA
Richard Bellman y George Bernard Dantzig fueron los creadores de la programación dinámica. Sus importantes contribuciones a esta técnica cuantitativa se publicaron por vez primera en la década de 1950. Inicialmente, la programación dinámica se llamo programación lineal estocástica, o bien problemas de programación lineal relacionados con la incertidumbre. Actualmente la programación dinámica se ha desarrollado como una técnica cuantitativa para resolver una amplia gama de problemas.
La programación dinámica puede definirse como una técnica matemática, para la solución de una serie de decisiones en secuencia.
Hay que tomar una secuencia de decisiones, con cada una de ellas que afecte las decisiones futuras.
Programación dinámica
Técnica cuantitativa que permite encontrar las decisiones optimas en un proceso dividido en faces.
Algunos ejemplos podrían se:
La asignación de personas a tareas
El cambio de un catalizador en un coche
Hasta un juego de cartas
Los elementos que definen un problema de programación dinámica son :
Etapas
Estados
Variables de decisión
Función recurrente
Etapas (n o N)
Las etapas son el periodo de tiempo, el lugar, el contexto, la fase o la situación en donde se produce un cambio debido a una decisión.
Solo puede tomarse una única decisión en cada etapa.
Las etapas se definen con la letra n
Si utilizamos la letra n minúscula empezaremos a contar desde el principio hasta el final
Si utilizamos la letra N mayúscula empezaremos a contar desde el final hasta el principio.
En general utilizaremos la primera opción
Estados (en)
Los estados muestran la situación actual del sistema cuando nos encontramos en la etapa n.
Cada etapa tiene su propio estado
Por ejemplo, la etapa n = 1 tiene el estado e1
Variables de decisión (Xn)
Las variables de decisión hacen referencia a toma de decisiones que se produce en una etapa y que provoca un cambio en el estado actual del sistema.
Cada etapa tiene su propia variable de decisión
Por ejemplo, la etapa n = 1 tiene la variable x1
La cual le permite evolucionar a la etapa n = 2
Función recurrente (fn)
La función de recurrencia refleja el comportamiento del sistema en funcion de los estados y las variables de decisión.
fn (en, xn)
Cada etapa tiene su propia función recurrente
Por ejemplo la etapa n = 1 tiene la función recurrente f1 que depende de x1 y e1 es decir del estado y de la variable de decisión de esa etapa.
Por ejemplo
La función en la cuarta etapa hace referencia a la cuarta etapa.
La función de la tercera etapa hace referencia a la tercera etapa y al resto de etapas que hay hasta el final del sistema
La función de la segunda etapa hace referencia a la segunda etapa y al resto de etapas que hay hasta el final del sistema
La función de la primera etapa hace referencia a la primera etapa y al resto de etapas que hay hasta el final del sistema
La aplicación de la programación dinámica se divide en dos faces
1. El analysis
2. Decision
La fase de análisis se empieza por la ultima etapa.
En este caso se analizan todas las opciones posibles de la cuarte etapa
Después se pasa a la etapa anterior n = 3
Se calculan todas las opciones posibles
Y se agrega a los resultados obtenidos previamente.
Después se pasa a la etapa anterior n = 2
Se calculan todas las opciones posibles
Y se agrega a los resultados obtenidos previamente
Después se pasa a la etapa anterior n = 1
Se calculan todas las opciones posibles
Y se agrega a los resultados obtenidos previamente
Llegando a este punto ya hemos calculado todas las opciones posibles.
Empezamos la fase de decisión
A diferencia de la fase anterior los cálculos a hora se realizan desde el principio hasta el final
Empezamos por la etapa uno y decidimos la mejor opción posible
Pasamos a la etapa dos y
...