programacion dinamica











Instituto Tecnológico de Mexicali
Nombre:
Francisco Javier leal Rodeles
Matricula:
11490099
Grupo:
Ingeniería industrial (trabajadores)
Fecha de entrega:
25/02/13








Introducción
Existe una serie de problemas matemáticos cuya solución se puede dar mediante el empleo de un algoritmo recursivo o mediante la implementación de una resolución por etapas,empleando una serie de sub problemas a partir del problema principal.
En ambos casos podemos agrandar el problema o simplemente o convertirse en impracticable. Esto puede mejorarse mediante la programación dinámica.





















PROGRAMACIÓN DINÁMICA
La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones enetapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema, afectando a las situaciones en las que el sistema se encontrará en el futuro (denominadas estados), y a las decisiones que se plantearán en el futuro.
Conviene resaltar que a diferencia de la programación lineal, el modelado de problemas de programación dinámica no sigue una forma estándar. Así,para cada problema será necesario especificar cada uno de los componentes que caracterizan un problema de programación dinámica.
El procedimiento general de resolución de estas situaciones se divide en el análisis recursivo de cada una de las etapas del problema, en orden inverso, es decir comenzando por la última y pasando en cada iteración a la etapa antecesora. El análisis de la primera etapafinaliza con la obtención del óptimo del problema.






Etapas de la programación dinámica
La programación dinámica comúnmente resuelve el problema en etapas, donde en cata etapa interviene exactamente una variable de optimización. Los cálculos en las diferentes etapas se enlazan a través de cálculos recursivos de manera que se genere una solución óptima factible a todo el problema.CARACTERISTICAS BASICAS:
1.- El problema se puede dividir en etapas que requieren una política de decisión en cada una de ellas.
2.- Cada etapa tiene cierto número de estados asociados con su inicio. Los estados son las distintas condiciones posibles en las que se puede encontrar el sistema en cada etapa del problema.
3.- El efecto de la política de decisión en cada etapa es transformar elestado actual en un estado asociado con el inicio de la siguiente etapa.
4.- El procedimiento de solución está diseñado para encontrar una política óptima para el problema completo.
5.- Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores. Este es el principio de optimizar para programación dinámica.
6.- Elprocedimiento de solución se inicia al encontrar la política óptima para la última etapa.
7.- 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.
La forma precisa de relación recursiva difiere de un problema a otro de programación dinámica, pero usaremos una notación análoga a la siguiente:
N = número de etapas.
n =etiqueta para la etapa actual (n = 1,2,…, N)
sn = estado actual para la etapa n
xn = variable de decisión para la etapa n
xn* = valor óptimo de xn (dado sn)
fn(sn,xn) = contribución a la función objetivo de las etapas n, n+1,…,N, si el sistema se encuentra en el estado sn en la etapa n, la decisión inmediata es xn y en adelante se toman decisiones óptimas.
fn*(sn) = fn(sn,xn*)
La relaciónrecursiva siempre tendrá la forma:
fn*(sn) = mín fn(sn,xn) ó fn*(sn) = max fn(sn,xn)
8.- Cuando se usa esta relación recursiva, el procedimiento de solución comienza al final y se mueve hacia atrás etapa por etapa, hasta que encuentra la política óptima desde la etapa inicial.
La programación dinámica (PD) es un procedimiento matemático diseñado principalmente para mejorar la eficiencia de...