Programacion dinamica

Índice
Unidad I
Programación Dinámica

Introducción _________________________________________________ 3
1.1 Programación Dinámica ____________________________________ 4
Conclusión __________________________________________________ 9
Bibliografía __________________________________________________ 10


Introducción
En el siguiente trabajo se analizarán que muchos problemas deprogramación matemática determinan soluciones que repercuten en la formulación de los problemas a resolver en el próximo perıodo o etapa. Una alternativa es construir un único modelo completo que tenga un gran conjunto de variables indexadas por etapas e iternalizar las relaciones entre etapas como una restricción del problema. Sin embargo esto pude agrandar mucho el tamaño del problema. Surge asíProgramación Dinámica (PD) como una alternativa de descomposición en que resolvemos subproblemas más pequeños y luego los ligamos. Así, programación dinamia consiste en solucionar el presente suponiendo que en cada etapa futura siempre se tomaran las decisiones correctas.

1.2 Programación Dinámica

Programación dinámica
La programación dinámica es un enfoque general para la solución de problemas enlos que es necesario tomar decisiones en etapas 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óndiná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 etapaantecesora. El análisis de la primera etapa finaliza con la obtención del óptimo del problema.

La programación dinámica toma normalmente uno de los dos siguientes enfoques:
• Top-down: El problema se divide en subproblemas, y estos subproblemas se resuelven recordando las soluciones en caso de que sean necesarias nuevamente. Es una combinación de memorización y recursión.
• Bottom-up: Todos lossubproblemas que puedan ser necesarios se resuelven de antemano y después son usados para resolver las soluciones a problemas mayores. Este enfoque es ligeramente mejor en consumo de espacio y llamadas a funciones, pero a veces resulta poco intuitivo encontrar todos los subproblemas necesarios para resolver un problema dado.
La programación dinámica es una técnica matemática que a menudo resultaútil al tomar una sucesión de decisiones interrelacionadas. Proporciona un procedimiento sistemático para determinar la combinación de decisiones que maximice la efectividad global.
Contrastando con la programación lineal, no existe un planteamiento matemático estándar del problema de programación dinámica. Más bien, la programación dinámica es un tipo general de enfoque para resolver problemas ylas ecuaciones particulares usadas deben desarrollarse para que se ajusten a cada situación individual. Por lo tanto, se requiere un cierto grado de ingenio y de visión de la estructura general de los problemas de programación dinámica, a fin de reconocer cuándo un problema se puede resolver mediante los procedimientos de esta programación y cómo se haría. Probablemente se puedan desarrollar mejorestas aptitudes por medio de una exposición de una amplia variedad de aplicaciones de la programación dinámica y de un estudio de las características que son comunes a todas éstas.
La programación dinámica suministra una solución con mucho menos esfuerzo que la enumeración exhaustiva; los ahorros de cálculo serían enormes para versiones más grandes de un problema. La programación dinámica...