Bellman's Principle of Optimality and Dynamic Programming

MemorableOxygen avatar
MemorableOxygen
·
·
Download

Start Quiz

Study Flashcards

5 Questions

Esta será una función ______ sobre el tiempo

aditiva

Cada etapa tiene un número de ______ asociados con ella

estados

La decisión tomada en cualquier etapa indica cómo transforma el estado en la etapa actual en el estado en siguiente etapa. En muchos problemas, una decisión determina con certeza el estado de la siguiente etapa; en ______ ello, la decisión actual solo determina la distribución probabilidad del estado en la etapa siguiente.

lugar

Dado el estado actual, la decisión óptima para cada una de las etapas restantes no debe depender de estados previamente alcanzados o de decisiones previamente ______

tomadas

El problema se puede dividir en etapas; cada etapa requiere una ______. En muchos problemas de programación dinámica, la etapa es la cantidad de tiempo que pasa desde el inicio del problema, en ciertos casos no se necesitan decisiones en cada etapa.

decisión

Study Notes

Introducción a la Programación Dinámica

  • El principio de optimalidad de Bellman (1953) establece que las decisiones óptimas en cada etapa de un problema no dependen de las decisiones óptimas en etapas anteriores.
  • La solución global del problema se obtiene a partir de las soluciones de los subproblemas.

Características de la Programación Dinámica

  • Permite resolver problemas de forma recursiva, dividiendo el problema en subproblemas más simples.
  • Cada subproblema se resuelve independientemente, lo que facilita la incorporación de cambios o imprevistos en la vida real.
  • La técnica puede ser desventajosa cuando el número de cálculos aumenta rápidamente con el número de variables o etapas, conocido como la "maldición de la dimensión".

Componentes de un Problema de Programación Dinámica

  • Variables de decisión: x = (x1,…, xn) ∈ ℝⁿ
  • Función objetivo: ƒ : ℝⁿ → ℝ
  • Restricciones:
    • Restricciones de desigualdad: gi(x) ≤ 0, i ∈ 1,…,m
    • Restricciones de igualdad: hj(x) = 0, j ∈ 1,…,l

Formulación del Problema

  • La formulación del problema de programación matemática se hace mediante la minimización de la función objetivo ƒ(x) sujetada a las restricciones impuestas.
  • La región factible se define como el conjunto de puntos (x1,…,xn) ∈ ℝⁿ que verifican las restricciones impuestas.

Resolución del Problema

  • Se puede resolver el problema de manera global, obteniendo la solución óptima simultáneamente.
  • También se puede resolver de manera secuencial, dividiendo el problema en subproblemas relacionados entre sí y enlazando las soluciones para obtener la solución óptima del problema completo.

Learn about Bellman's principle of optimality and dynamic programming, which states that optimal decisions made at each stage of a problem are independent of previous stages, and the global solution can be obtained from subproblem solutions. Explore how dynamic programming recursively solves subproblems.

Make Your Own Quizzes and Flashcards

Convert your notes into interactive study material.

Use Quizgecko on...
Browser
Browser