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

...