Investigacion De Operaciones 2
Páginas: 13 (3047 palabras)
Publicado: 24 de julio de 2011
PROGRAMACIÓN DINÁMICA
La programación dinámica es una técnica matemática que a menudo resulta útil a tomar una sucesión de decisiones interrelacionadas. Proporciona un procedimiento sistemático para determinar la combinación de decisiones que maximice la efectividad global.
Contrastando con la programación lineal, no existe un planteamiento matemático estándar "del" problema de programacióndinámica. Más bien, la programación dinámica es un tipo general de enfoque para resolver problemas y las ecuaciones particulares usadas deben desarrollarse para que se ajusten a cada situación individual. Por lo tanto, se requiere un cierto grado de ingenio y de visión de la estructura general de los problemas de programación dinámica, a fin de reconocer cuando un problema se puede resolvermediante los procedimientos de esta programación y cómo se haría. Probablemente se puedan desarrollar mejor estas aptitudes por medio de una exposición de una amplia variedad de aplicaciones de la programación dinámica y de un estudio de las características que son comunes a todas estas.
Por fortuna, la programación dinámica suministra una solución con mucho menos esfuerzo que la enumeración exhaustiva.(Los ahorros de cálculo serían enormes para versiones más grandes de un problema.) La programación dinámica parte de una pequeña porción del problema y encuentra la solución óptima para este problema más pequeño.
Entonces gradualmente agranda el problema, hallando la solución óptima en curso a partir de la anterior, hasta que se resuelve por completo el problema original. En seguida se dan losdetalles involucrados en la implementación de esta filosofía general.
Considérese que las variables de decisión xn (n = 1, 2, 3, 4) son el destino inmediato en la etapa n. Así, la ruta seleccionada sería 1 - XI - X2 - X3 - X4 en donde X4 = 10. Sea fn(s, Xn) el costo total de la mejor política global para las etapas restantes, dado que el vendedor se encuentra en el estado s listo para iniciar laetapa n y se selecciona a XII como el destino inmediato. Dados s y n, denotemos por x el valor de X*n que minimiza al fn(s, Xn) y sea f*(s) el valor mínimo correspondiente de fn(s, Xn) por tanto, f*n(s) = fn(s, Xn). El objetivo es hallar f1*(1) y la pol1tica correspondiente. La programación dinámica hace esto, hallando sucesivamente f4*(s), f3*(s), f2*(s) , a continuación, f1*(1).
PROGRAMACIÓNDINÁMICA DETERMINÍSTICA
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 ventaja en el aspecto de los cálculos es que optimizaremos una sola variable, en vez de subproblemas de n variables. La principal contribución de la PD es el principio de optimalidad, unmarco de referencia para descomponer el problema en etapas.
La programación dinámica determinística se puede describir en forma de diagrama de la siguiente forma:
Una manera de catalogar los problemas de programación dinámica determinística es por la forma de la función objetiva. Por ejemplo, el objetivo podría ser minimizar la suma de contribuciones de las etapas individuales, o bien minimizarun producto de tales términos y así sucesivamente. En un problema de programación dinámica, las temporadas deben ser las 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 queun problema grande y engorroso se convierte en una serie de problemas más pequeños y más tratables.
Características:
* El problema se puede dividir en etapas; cada etapa requiere una decisión. 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.
* Cada etapa tiene...
La programación dinámica es una técnica matemática que a menudo resulta útil a tomar una sucesión de decisiones interrelacionadas. Proporciona un procedimiento sistemático para determinar la combinación de decisiones que maximice la efectividad global.
Contrastando con la programación lineal, no existe un planteamiento matemático estándar "del" problema de programacióndinámica. Más bien, la programación dinámica es un tipo general de enfoque para resolver problemas y las ecuaciones particulares usadas deben desarrollarse para que se ajusten a cada situación individual. Por lo tanto, se requiere un cierto grado de ingenio y de visión de la estructura general de los problemas de programación dinámica, a fin de reconocer cuando un problema se puede resolvermediante los procedimientos de esta programación y cómo se haría. Probablemente se puedan desarrollar mejor estas aptitudes por medio de una exposición de una amplia variedad de aplicaciones de la programación dinámica y de un estudio de las características que son comunes a todas estas.
Por fortuna, la programación dinámica suministra una solución con mucho menos esfuerzo que la enumeración exhaustiva.(Los ahorros de cálculo serían enormes para versiones más grandes de un problema.) La programación dinámica parte de una pequeña porción del problema y encuentra la solución óptima para este problema más pequeño.
Entonces gradualmente agranda el problema, hallando la solución óptima en curso a partir de la anterior, hasta que se resuelve por completo el problema original. En seguida se dan losdetalles involucrados en la implementación de esta filosofía general.
Considérese que las variables de decisión xn (n = 1, 2, 3, 4) son el destino inmediato en la etapa n. Así, la ruta seleccionada sería 1 - XI - X2 - X3 - X4 en donde X4 = 10. Sea fn(s, Xn) el costo total de la mejor política global para las etapas restantes, dado que el vendedor se encuentra en el estado s listo para iniciar laetapa n y se selecciona a XII como el destino inmediato. Dados s y n, denotemos por x el valor de X*n que minimiza al fn(s, Xn) y sea f*(s) el valor mínimo correspondiente de fn(s, Xn) por tanto, f*n(s) = fn(s, Xn). El objetivo es hallar f1*(1) y la pol1tica correspondiente. La programación dinámica hace esto, hallando sucesivamente f4*(s), f3*(s), f2*(s) , a continuación, f1*(1).
PROGRAMACIÓNDINÁMICA DETERMINÍSTICA
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 ventaja en el aspecto de los cálculos es que optimizaremos una sola variable, en vez de subproblemas de n variables. La principal contribución de la PD es el principio de optimalidad, unmarco de referencia para descomponer el problema en etapas.
La programación dinámica determinística se puede describir en forma de diagrama de la siguiente forma:
Una manera de catalogar los problemas de programación dinámica determinística es por la forma de la función objetiva. Por ejemplo, el objetivo podría ser minimizar la suma de contribuciones de las etapas individuales, o bien minimizarun producto de tales términos y así sucesivamente. En un problema de programación dinámica, las temporadas deben ser las 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 queun problema grande y engorroso se convierte en una serie de problemas más pequeños y más tratables.
Características:
* El problema se puede dividir en etapas; cada etapa requiere una decisión. 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.
* Cada etapa tiene...
Leer documento completo
Regístrate para leer el documento completo.