Metodos Dinamicos De Programacion

Métodos dinámicos de programación

A pesar de todas las dinámicas de programación (DP), los problemas tienen una estructura similar, el procedimientos de cálculo utilizados para encontrar soluciones a menudo son muy diferentes. A diferencia lineal y programación entera, donde las convenciones estándar se utilizan para describir los parámetros y coeficientes, no hay una estructura de datos común que unifica todas las AD. Los modelos son un problema específico, y en su mayor parte, están representados por las fórmulas recursivas en lugar de algebraica expresiones. Por esta razón, es difícil crear un código de ordenador general que va a resolver todos los problemas. Generalmente es necesario para escribir un propio código para resolver un determinado

aplicación. Esta es una de las razones por programación dinámica es mucho menos popular que, por ejemplo la programación lineal, donde los modelos pueden ser creados de forma independiente del software

dejando la codificación de algoritmos para los profesionales.

Programación dinámica es, sin embargo, mucho más general que la programación lineal con respecto a la clase de problemas que puede manejar. Como muestran los ejemplos en el capítulo anterior sugieren, no hay dificultad con las restricciones enteros sobre las variables de decisión, y no hay ningún requisito de que cualquiera de las funciones ser lineal o continuo, incluso .También hay Nunca ninguna cuestión de los óptimos locales, por un problema correctamente formulado, una dinámica

algoritmo de programación siempre se informará de un óptimo global cuando se termina.

Hay una cierta ambigüedad en cuanto a los orígenes de la DP, pero las ideas se remontan al menos a el trabajo de Massé, a mediados de la década de 1940. Massé fue un ingeniero francés que desarrolló y aplica una versión bastante analítico de DP a la generación de energía hidroeléctrica. La literatura estándar ,sin embargo, atribuye Richard Bellman con el desarrollo de los fundamentos teóricos del campo

y la propuesta de los primeros algoritmos. Sus primeras investigaciones, publicadas en la década de 1950, tenía como objetivo a resolver los problemas que surgen en el control de sistemas continuos, tales como las aeronaves en vuelo

y circuitos electrónicos. La mayoría de las exposiciones tradicionales siguen las ideas originales de Bellman y describir lo que se llama recursión hacia atrás en el espacio de estados exhaustiva. Este es quizás el más amplio de las metodologías de solución, pero el menos eficiente en muchos casos. Nosotros comenzar con una descripción completa de la recursividad hacia atrás y luego pasar a remitir la recursividad

y alcanzar. Cerramos el capítulo con un análisis limitado de modelos estocásticos en el que los resultados de las decisiones se ven como sucesos aleatorios rige por probabilidad conocida distribuciones

2 0. 1 Componentes de algoritmos de solución

El requisito central de un modelo de programación dinámica es que la secuencia óptima de las decisiones de cualquier estado es independiente de la secuencia que conduce a ese estado.

Todos los procedimientos de cálculo se basa en este requisito se conoce como el principio de óptimo para que el modelo debe ser formulada en consecuencia. Si se considera el único equipo problema de programación, con fechas de vencimiento discutidos en la sección 19.6 del capítulo DP modelos,

ver que la decisión óptima en un estado particular no depende de la orden del

trabajos programados, pero sólo en sus tiempos de procesamiento. Para el cálculo de la función objetivo

componente c (d, t) dada en la Tabla 22 de ese capítulo, es necesario primero calcula

t = Pnj=1sjp(j)) + p(d)

para cualquier decisión d I D (s). Este cálculo no es dependiente de la secuencia de modo que el principio

se aplica.

Consideremos ahora una extensión de este problema que involucra un costo de cambio o(i, j), que

se incurre cuando la máquina cambia de trabajo i al trabajo j. La nueva función objetivo

componente es c (d, t) + O (i, d), donde i es el último trabajo en la secuencia óptima asociada con

el estado actual. Esta modificación anula la formulación de DP en la Tabla 22, porque el decisiones actuales y futuras dependen de la secuencia de las decisiones del pasado. Sin embargo, si modificar la definición de un estado para incluir un componente adicional que corresponde a la última trabajo en la corriente de secuencia, se obtiene un modelo válido similar a la de la viaja

vendedor problema en la Tabla 23. Los nuevos rangos variable de estado desde 1 hasta n lo que el precio del modificación es una orden n aumento en el tamaño del espacio de estados.

El modelo de estructura general que se da en la Tabla 4 en la sección 19,2 implica que muchos problemas de optimización se puede formular como programas dinámicos. En esta sección,

introducir los conceptos básicos asociados con algoritmos de solución. Aunque los algoritmos

Aunque los algoritmos son apropiados para la mayoría de los modelos en el capítulo 19, su complejidad computacional puede

varían de funciones polinómicas simples del número de variables de estado n para impracticablemente

funciones exponenciales grandes de n.El Princ e ipl de la exclusión proximal i dad

Para dinámicos métodos de programación de la solución para trabajar, es necesario que los estados, las decisiones, y la función objetivo se define por lo que el principio

optimalidad de queda satisfecho. Muy a menudo un problema modelado en estos términos en un manera aparentemente razonable, no cumplir con este requisito. En tales casos,

la aplicación de los procedimientos de cálculo probablemente producirá soluciones que sean

ya sea subóptima o no factible. Afortunadamente, es posible modelar más

problemas de manera que el principio es válido. A medida que nuestra discusión de la única

problema de la máquina indica la programación, la obtención de un modelo válido de un

válido un muy a menudo implica definir un espacio de estado más complejo.

Teóricamente, no hay ninguna dificultad en hacer esto, pero el analista debe tener en

importa que como el tamaño del espacio de estados crece, la carga de cálculo puede

llegan a ser prohibitivos.

El principio de optimalidad, primero articulado por Bellman, puede ser

se indica en un número de maneras. Se proporcionan varias versiones en un intento para

aclarar el concepto.

1. La ruta óptima desde cualquier estado a un estado final depende sólo de

la identidad del estado dado, y no en la ruta utilizada para llegar a él.

2. Una política óptima tiene la propiedad de que cualquiera que sea el estado inicial y

decisión son, las decisiones restantes deben constituir una política óptima

con respecto al estado resultante de la primera decisión.

3. Una política óptima debe contener sólo subpolicies óptimas (Kaufmann

1967). Componentes de 3 algoritmos de solución

4. Una política es óptima si en un período determinado, independientemente de lo anterior

decisiones pueden haber sido, las decisiones tomadas todavía no se constituyen un

política óptima cuando el resultado de las decisiones anteriores se incluye.

El principio de optimalidad parece tan obvia que no requiere

prueba. De hecho, la prueba es, simplemente, que si una solución contiene un no óptimo

secuencia, no puede ser óptimo, ya que podría mejorarse mediante la incorporación

la secuencia óptima parcial en lugar de la no óptima una. El peligro es

que en la formulación de un modelo de programación dinámica no hay manera clara de

ver o comprobar que es o no el principio se cumple. Mucho depende de la

la creatividad y las ideas de el modelador. Alternativamente, una extremadamente

modelo complejo podría proponer que se ajusta al principio, pero es

demasiado elaborado para ser de algún valor práctico.

La Red de la Decisión acíclicos

Los modelos dinámicos de programación con variables de decisión discretas y un

espacio de estado discreto tienen las características de una decisión dirigido acíclico

red. Esto significa que una secuencia de decisiones no puede encontrar el

mismo estado (nodo) dos veces. La red no tiene ciclos y los estados se dice

a ser parcialmente ordenado. Por lo tanto si tenemos en cuenta dos estados, o bien no hay

relación entre ellos o una puede ser identificado como que precede a la otra. nosotros

escribir la relación entre dos estados si y sjas si« sj

Para un problema acíclico es imposible que tanto

si« sj y sj» si

mantenga. No todos los estados deben estar relacionados con la manera que acabamos de describir lo que llamamos

trata de un orden parcial en lugar de un pedido completo.

Para ilustrar este concepto consideremos la red se muestra en la decisión

Fig. 1 para un problema del camino. Los números en los nodos se utilizan para identificar los estados.

La relación es transitiva en que si s

también es

cierto. Tenga en cuenta que varios pares de estados de la figura no están relacionados, tales como

.

Un orden parcial implica que algunos estados deben ser estados finales denota

por el conjunto F de los nodos correspondientes no tienen origen los

...