programacion dinamica

UNIVERSIDAD NACIONAL FEDERICO VILLAREA
FACULTAD DE INGENIERÍA INDUSTRIAL


CURSO: INVESTIGACION OPERATIVA II

TEMAS : PROGRAMACION DINAMICA

PROFESOR :ING.



PROGRAMACIÓN DINÁMICA
Introducción
La Programación Dinámica es un método de optimización de extraordinaria versatilidad. Si bien fue desarrollada especialmente para la resolución de problemas en Procesos de Decisión enMúltiples Pasos, diferentes investigaciones han mostrado que las mismas ideas pueden utilizarse en otro tipo de problemas de matemática aplicada, e incluso pueden ser útiles en el planteo de algunas cuestiones teóricas. Habiendo surgido en los inicios de la época de las computadoras, la Programación Dinámica fue, además, concebida con un ojo puesto en esta potente herramienta. La Ecuación Funcionalque se obtiene, para cada problema, a través del uso del Principio de Optimalidad de Bellman permite, con mayor o menor esfuerzo dependiendo del caso, establecer una recurrencia que es, en sí misma, un algoritmo que resuelve el problema en cuestión.
El objetivo de esta monografía es brindar un panorama relativamente amplio de las aplicaciones de la Programación Dinámica, de manera que resulteaccesible para cualquier estudiante de Licenciatura, incluso para aquellos que no estén familiarizados con las áreas específicas de dichas aplicaciones. Persiguiendo este fin , procuramos, en la medida en que el espacio lo permitió, exponer todos los pasos de cada razonamiento y los elementos teóricos básicos para su comprensión.

Definición.
La programación dinámica es una técnica matemática útilpara la toma de una serie de decisiones interrelacionadas. Proporciona un procedimiento sistemático para determinar la combinación óptima de decisiones.
En contraste con la programación lineal, no cuenta con una formulación matemática estándar “del” problema de programación dinámica, sino que se trata de un enfoque de tipo general para la solución de problemas; además, las ecuaciones específicasque se usan se deben desarrollar para que representen cada situación individual. Por lo tanto, es necesario cierto grado de creatividad y un buen conocimiento de la estructura general de los problemas de programación dinámica para reconocer cuándo y cómo se puede resolver un problema por medio de estos procedimientos. Es posible desarrollar mejor estas habilidades mediante la exposición de unagran variedad de aplicaciones de programación dinámica y con el análisis detallado de las características comunes de todas estas situaciones. Con este fin, se presentará un gran número de ejemplos ilustrativos.

CARACTERÍSTICAS DE LOS PROBLEMAS DE PROGRAMACIÓN DINÁMICA

A continuación se presentan y estudian estas características básicas que distinguen a los problemas de programación dinámica.El problema se puede dividir en etapas, cada una de las cuales requiere de una política de decisión.
Cada etapa tiene cierto número de estados asociados con su inicio.
El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con el inicio de la siguiente etapa quizá según una distribución de probabilidad.
El procedimiento de solución estádiseñado para encontrar una política óptima para manejar el problema completo, es decir, una receta para elaborar la política de decisión óptima para cada etapa en cada uno de los estados posibles.
Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores. Por lo tanto, la decisión inmediata óptima depende sólo del estado actual yno de cómo se llegó ahí. Éste es el principio de optimalidad de la programación dinámica.
El procedimiento de solución inicia cuando se determina la política óptima para la última etapa.
Se dispone de una relación recursiva que identifica la política óptima para la etapa n, dada la política óptima para la etapa n + 1.
Entonces, para encontrar la política óptima de decisión cuando se comienza...