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únque 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 razonespor 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 elcapí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 setermina.
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 delcampo
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ásen 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 comosucesos 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 queel 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 laTabla 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...