Programacion dinamica

UNIDAD 1: PROGRAMACION DINAMICA

Técnica de programación matemática que proporciona un procedimiento sistemático para determinar la combinación óptima de una serie de decisiones interrelacionadas.

CONCEPTUALIZACIÓN DE PROGRAMACIÓN DINÁMICA

1. En contraste con la programación lineal, no se cuenta con una formulación matemática estándar para “el” problema de Programación dinámica.
2. Setrata de un enfoque de tipo general para la solución de problemas y las ecuaciones específicas que se usan se deben desarrollar para que representen cada situación individual.
3. Se necesita un cierto grado de creatividad y un buen conocimiento de la estructura general de de los problemas de Programación Dinámica para reconocer cuándo y cómo se puede resolver un problema por medio de estosprocedimientos.

CARACTERÍSTICAS DE PROGRAMACIÓN DINÁMICA
1. Etapas: El problema se puede dividir en etapas que requieren una política de decisión en cada una de ellas.
2. Estados asociados: Cada etapa tiene cierto número de estados asociados con su inicio.
3. Política de decisión: El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con el iniciode la siguiente etapa.
4. Diseño de solución: El procedimiento de solución está diseñado para encontrar una política óptima para el problema completo, es decir, una receta para la política de decisión óptima en cada etapa para cada uno de los estados posibles.
5. Principio de optimalidad:
a. Dado el estado actual, una política óptima para las etapas restantes es independiente de la políticaadoptada en etapas anteriores.
b. La decisión inmediata óptima depende sólo del estado actual y no de cómo se llegó ahí.
6. Inicio de solución: El procedimiento de solución se inicia al encontrar una política óptima para la última etapa.
7. Relación recursiva: 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.
8.Retroceso: Cuando se use esta relación recursiva, el procedimiento de solución comienza al final y se mueve hacia atrás etapa por etapa – encontrando cada vez la política óptima para esa etapa – hasta que se encuentra la política óptima desde la etapa inicial.

Procedimiento de solución

1. Se construye una relación recursiva que identifica la política óptima para cada estado en la etapa n, dadala solución óptima para cada estado en la etapa n + l.

2. Se encuentra la decisión óptima en la última etapa de acuerdo a la política de decisión establecida. Comúnmente la solución de esta última etapa es trivial, es decir, sin ningún método establecido, tomando en cuenta solamente la "contribución" de la última etapa.

3. La idea básica detrás de la relación recursiva es trabajar "haciaatrás", preguntándose en cada etapa: ¿qué efecto total tendría en el problema si tomo una decisión particular en .t:5Ll etapa y actúo óptimamente en todas las etapas siguientes?

Si se resolviera el problema "hacia adelante", es decir, de la primera etapa hacia la sería necesario realizar una enumeración exhaustiva de todas las alternativas, que resolviéndolo "hacia atrás" reducimos el número dealternativas a analizar, simplificando la solución del problema. Cuando se llega a la etapa inicial se encuentra la solución óptima.

Nomenclatura

n: número de etapa n = 1, 2, 3, ...

Xn decisión tomada en la etapa n.

Xn* Valor óptimo de Xn.

S: estado actual en la etapa n

C(Xn): contribución al objetivo dada la decisión Xn y el estado Sn.

fn (S, Xn): contribución al objetivo enla etapa n y etapas siguientes si el sistema se encuentra en el estado S y las decisiones son óptimas en las etapas n + 1, n + 2, … es decir, contribución inmediata en la etapa n más la contribución futura de las etapas n + l en adelante, considerando que nos encontramos en el estado S.

fn*(S) = fn (S, Xn*) = máximo o mínimo fn (S, Xn*): máximo o mínimo de la función objetivo fn (S,Xn)...