Programación Dinámica y sus Características
Programación Dinámica
La programación dinámica es un enfoque general para la
solución de problemas en los 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.
El modelado de problemas de programación diná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.
La programación dinámica es un método de optimización que se puede emplear para la resolución de problemas de matemática aplicada y para darle estructura a una solución óptima, definiendo el camino más adecuado para hallarla.
Es utilizada en compiladores que cosiste en solucionar ciertos problemas dividiéndolos en subproblemas mas sencillos, calculando sus resultados y almacenándolos. Estos resultados se utilizan posteriormente parea la solución final. Cada decisión transforma la actual situación en una nueva situación. El valor de la secuencia de decisiones es generalmente igual a la suma de valores de las decisiones individuales y las situaciones en la secuencia.
• Puede
utilizarse en problemas lineales o no lineales, determinísticos o estocásticos,
uní o multivariados.
• Es
útil para resolver un problema donde se debe tomar una serie de decisiones
interrelacionadas.
• Formato
general: A diferencia de la Programación Lineal, la Programación Dinámica no
tiene formulación matemática estándar. Se trata de un enfoque tipo general para
la solución de problemas y las ecuaciones se derivan de sus condiciones
individuales.
• El
problema no se puede dividir por etapas que requieren una decisión en cada una
de ellas.
• Cada
etapa tiene cierto numero de estados asociados a su inicio. Estados son las
diferentes condiciones posibles en las que se puede encontrar el sistema en
cada etapa.
• El
efecto de la decisión en cada etapa es transformar el estado actual en un
estado asociado con el INICIO de la siguiente etapa
• Para
que un problema pueda ser resuelto con la técnica de Programación Dinámica,
debe cumplir con ciertas características:
• Naturaleza secuencial de las decisiones: El
problema puede ser dividido en etapas.
• Cada
etapa tiene un numero de estados asociados a ella.
• La
decisión óptima de cada etapa depende solo del estado actual y no de las
decisiones anteriores.
• La decisión tomada en una etapa determina cual
será el estado de la etapa siguiente.
Características importantes:
- El problema se puede dividir por etapas, y cada una de las etapas requiere de una política de decisión.
- Cada etapa tiene cierto número de estados, los estados son las distintas condiciones posibles en las que se puede encontrar el sistema en cada etapa.
- El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con el inicio de la siguiente 0etapa, entonces podemos decir que un estado es una columna de nodos, cada nodo representa un estado y cada rama una política de decisión.
- El procedimiento de resolución de la programación dinámica está diseñado para encontrar una política óptima para cada etapa logrando así la política óptima general.
- Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores, por ende, la decisión inmediata óptima solo depende del estado actual y no de cómo se llegó ahí, esto es el principio de optimalidad de la programación dinámica.
- 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.
- Cuando se hace uso de la relación recursiva, el procedimiento de solución comienza al final se mueve hacia atrás etapa por etapa hasta encontrar la política óptima en cada etapa hasta la etapa inicial.
Resolución de un problema de programación
dinámica:
Solucionar un problema de programación dinámica requiere tener en cuenta tres pasos claves como son:
- Identificar etapas, estados y variable de decisión.
- Describir las ecuaciones de recurrencia.
- Solucionar.
*http://virtual.umng.edu.co/distancia/ecosistema/ovas/ingenieria_civil/investigacion_de_operaciones_ii/unidad_4/DM.pdf
Comentarios
Publicar un comentario