Programación dinámica determinística



Investigación de operaciones II
Programación dinámica determinística

Lic. FátimaGutiérrezMéndez

Presenta:

Grupo: II6NA.


8 de Agosto del 2013





Lugar: Tijuana, Baja California.



PROGRAMACION DINAMICA DETERMINISTICA


La programación dinámica (PD) determina la solución óptima de un problema de
nvariables descomponiéndola en n etapas, con cada etapa incluyendoun
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, un marco de
referencia para descomponer el problema en etapas.
La programación dinámica es una técnica que se puede aplicar para resolver
muchos problemas deoptimizació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 que un problema grande y
engorroso se convierte en una serie de problemas más pequeños y más
tratables.





























Índice

ReseñaHistórica…………………………………………………………
La Programación Dinámica.……………………………………………………………………………………….
Cuando Aplicar……………………………………………………………………………………………………………
Principio de Optimalidad de la Programación Dinámica o de Bellman ………………….….…
Procesos de Decisión de “n” Etapas. ……………………………………………………………………….…
Relación Recursiva (hacia atrás) …………………………………………………………………………………
DP hacia atrás (backward DP) ………………………………………………………………………………….…
DP hacia adelante (forwardDP) ……………………………………………………………………………….…
Programación Dinámica en contraste con la Programación Lineal………………………….….
Ejemplos
* Problema del viajero o de la diligencia…………………………………………….
* Problema de la Mochila……………………………………………………………………
* Programación de Producción e Inventarios………………………………………
Modelo Matemático. …………………………………………………………………………………………………..
La Formulación con ProgramaciónDinámica. ………………………………………………………………
Resolución de un Problema de Programación Dinámica. ………………………………………………
Tipos de programación dinámica…………………………………………………………………………………..
* Programación dinámica homogénea y no homogénea. …………………….
* Programación dinámica determinista y aleatoria……………………………….
Conclusión…………………………………………………………………………………………………………………….Bibliografía…………………………………………………………………………………………………………………...


Historia
La primera gran disciplina que surgió a partir del abordaje matemático de los problemas específicos de la Segunda Guerra Mundial fue, seguramente, la Investigación Operativa1. El término Operations Research fue utilizado por primera vez en Inglaterra, en 1941.

Rápidamente se hizo evidente que las mismas técnicas utilizadas en el ámbito militar podían servir en otras áreas de aplicación. En los años posteriores a la Guerrase abrieron nuevos temas de investigación y se plantearon nuevos problemas, que fueron abordados desde una perspectiva matemática. Entre estos nuevos temas se encontraba la teoría de los Procesos de Decisión en Múltiples Pasos, que Richard Bellman (1920 - 1984) abordó alrededor de 1952, y para los cuales fue pensada originalmente la Programación Dinámica.
Después de desarrollar el método en elárea específica de los problemas de decisión discretos, Bellman y sus colaboradores se dedicaron a la ardua tarea de formular diferentes problemas en los términos de la Programación Dinámica. Como resultado de esta labor, encontraron que las ideas centrales del método, en particular, el Principio de Optimalidad, podían ser aplicadas satisfactoriamente en muchos de los problemas abordados.Descubrieron también las limitaciones de esta técnica y hallaron modos de sobreponerse a ellas, para algunos problemas puntuales.
La Programación Dinámica es, hoy en día, un recurso imprescindible de Matemática Aplicada y, también, una importante herramienta teórica.

La Programación Dinámica
La programación dinámica es un enfoque...