Questions and Answers
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 ______
Signup and view all the answers
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.
Signup and view all the answers
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.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
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.
