Programación Dinámica y Procesos Estocásticos: Optimización de Decisiones

Programación Dinámica: Fundamentos y Aplicaciones

La Programación Dinámica es una técnica matemática utilizada para tomar una secuencia de decisiones interrelacionadas. Requiere la formulación de una relación recursiva y ofrece grandes ahorros computacionales para problemas de gran escala.

Características Clave de los Problemas de Programación Dinámica

1. El problema se puede dividir en etapas, y en cada etapa se requiere decidir sobre una política.
2. Cada etapa tiene una serie de estados asociados con el comienzo de la misma.
3. La decisión de la política en cada etapa transforma el estado actual en un estado asociado con el comienzo de la siguiente etapa.
4. El procedimiento de solución está diseñado para encontrar una política óptima para el problema general.
5. Dado el estado actual, una política óptima para las etapas restantes es independiente de las decisiones de política de las etapas anteriores.
6. El procedimiento de solución comienza al encontrar la política óptima para la última etapa.
7. Se puede definir una relación recursiva que identifique la política óptima para la etapa n, dada la política óptima para la etapa n + 1 (ejemplo: f_n*(s) = min_Xn{C_sXn + f*_n+1(Xn)}).
8. Usando la relación recursiva, el procedimiento de solución comienza al final y trabaja hacia atrás.

Procesos Estocásticos y Cadenas de Markov

Los Procesos Estocásticos evolucionan en el tiempo de una manera probabilística.

Cadenas de Markov

Las Cadenas de Markov son un tipo específico de proceso estocástico con una propiedad especial:

• Cómo evolucionará el proceso en el futuro depende solo del estado actual.
• Pueden ser de tiempo continuo o de tiempo discreto.

Tipos de Políticas en Procesos de Decisión

• Política Estacionaria

  Ocurre siempre que, cuando el sistema está en el estado i, la regla para tomar la decisión es siempre la misma.

• Política Determinística

  Ocurre siempre que, cuando el sistema está en el estado i, la regla para tomar la decisión elige definitivamente una decisión particular.

Procesos de Decisión de Markov (PDM)

Los Procesos de Decisión de Markov son una herramienta potente para optimizar el desempeño de los procesos estocásticos que se pueden modelar como una cadena de Markov discreta.

Un objetivo común es encontrar una política para cada estado del sistema que minimice el coste promedio esperado por unidad de tiempo.