Examen de Dinamica Parte 2

DINAMICA PROBABILISTICA PROBLEMA 4

Richard Bellman

Richard Ernest Bellman (1920–1984) fue un matemático aplicado, cuya mayor contribución fue la metodología denominada programación dinámica.

Bellman estudió matemáticas en la Universidad de Brooklyn, donde obtuvo una diplomatura, y luego en la Universidad de Wisconsin, donde obtuvo su licenciatura. Posteriormente comenzó a trabajar en el Laboratorio Nacional Los Álamos en el campo de la física teórica. En 1946 obtuvo su doctorado en la Universidad de Princeton. También ejerció la docencia en la universidad del sur de California(EE. UU.), fue socio de la Academia Americana de las Artes y las Ciencias(1975) y de la Academia Nacional Americanade Ingeniería (1977). En 1979 el IEEE le otorgó la medalla de honor por su contribución a la teoría de los sistemas de control y de los procesos de decisión, en especial por su contribución con la programación dinámica y por la ecuación de Bellman.

Trabajo
Ecuación de Bellman: Programación Dinámica

Una ecuación de Bellman, también conocida como la ecuación de programación dinámica, es una condición necesaria para la optimalidad asociado con el método de optimización matemática conocida como la programación dinámica. Casi cualquier problema que se puede resolver utilizando la teoría de control óptimo también se puede resolver mediante el análisis de la correspondiente ecuación de Bellman. La ecuación de Bellman se aplicó por primera vez a la teoría de la ingeniería de control y otros temas de matemáticas aplicadas, y, posteriormente, se convirtió en una herramienta importante en la teoría económica.

 

Ecuación de Hamilton-Jacobi-Bellman

La ecuación de Hamilton-Jacobi-Bellman (HJB) es una ecuación diferencial parcial que es fundamental para la teoría de control óptimo. La solución de la ecuación HJB es la "función de valor", que da a la óptima función de los costos un determinado sistema dinámico con una función de costos asociados. Clásicos problemas variacionales, por ejemplo puede resolverse utilizando este método.

La ecuación es el resultado de la teoría de programación dinámica que fue creado en los 50’s por Richard Bellman y compañeros de trabajo. La ecuación correspondiente en tiempo discreto que normalmente se conoce como la ecuación de Bellman. En tiempo continuo, el resultado puede ser visto como una extensión del trabajo anterior en la física clásica en la ecuación de Hamilton-Jacobi por William Rowan Hamilton y Carl Gustav Jacob Jacobi.

Algoritmo de Bellman-Ford

El algoritmo de Bellman-Ford, a veces conocido como el algoritmo de corrección de la etiqueta, calcula un solo proveedor o caminos más cortos en un digrafo ponderado (donde algunos de los valores pueden ser negativos). El algoritmo de Dijkstra logra el mismo problema con un tiempo de baja en ejecución, pero requiere de pesos ventaja de ser no-negativas.

Publicaciones

A lo largo de su carrera ha publicado 619 artículos y 39 libros. Aquí una pequeña selección:

 

1957. Programación Dinámica1959. Comportamiento asintótico de las soluciones de las ecuaciones diferenciales1961. Introducción a las desigualdades1961. Control de Procesos Adaptativos: Un Tour guiado1962. Programación Dinámica Aplicada1967. Introducción a la Teoría Matemática de Control de Procesos1972. Programación Dinámica y Ecuaciones Diferenciales Parciales1982. Aspectos matemáticos de Programación y Aplicaciones1983. Métodos Matemáticos en Medicina1984. Ecuaciones Diferenciales Parciales1984. Ojo del huracán: publicación de una autobiografía, Mundo Científico.1985. Inteligencia Artificial1995. Ecuaciones Diferenciales Elementales modernas1997. Introducción a Análisis de matrices.

 

 

 

La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas, se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados.

Una subestructura óptima significa que se pueden usar soluciones óptimas de subproblemas para encontrar la solución óptima del problema en su conjunto. Por ejemplo, el camino más corto entre dos vértices se puede encontrar calculando primero el camino más corto al objetivo desde todos los vértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor camino de todos ellos.

 En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:

        1.     Dividir el problema en subproblemas más pequeños.

     2.   Resolver estos problemas de manera óptima usando        este proceso de tres pasos     recursivamente.

     3.    Usar estas soluciones óptimas para construir una solución óptima al problema original.

PROGRAMACION DINAMICA DETERMINISTICA

Ejercisios de programacion entera