Manera de Clasificar los Problemas de Programaci n Din mica
Forma de la función objetiva. Minimizar la suma de las contribuciones en cada una de las etapas individuales, o maximizar esa suma, obien minimizar el producto de los términos, etc.
Naturaleza del conjunto de estados en las respectivas etapas. Los estados si pueden estar representados por:
1- Una variable discreta
2- Una variable deestado Continua
3- O un vector de estado (más de una variable)
Para resolver un problema de programación dinámica debemos al menos: Identificación de etapas, estados y variable de decisión:
Cadaetapa debe tener asociado una o más decisiones (problema de 0ptimizacion), cuya dependencia de las decisiones anteriores está dada exclusivamente por las variables de estado.
Cada estado debe contenertoda la información relevante para la toma de decisión asociada al período.
Las variables de decisión son aquellas sobre las cuales debemos definir su valor de modo de optimizar el beneficio acumuladoy modificar el estado de la próxima etapa.
Descripción de ecuaciones de recurrencia: Nos deben indicar como se acumula la función de beneficios a optimizar (función objetivo) y como varían lasfunciones de estado de una etapa a otra.
Resolución Debemos optimizar cada subproblema por etapas en función de los resultados de la resolución del subproblema siguiente.
Notar que las para que lasrecurrencias estén bien definidas requerimos de condiciones de borde.
Se puede suponer que alguien debe viajar entre los puntos A y Z indicados en la red mostrada continuación.
Puede seguirse cualquiertrayectoria entre los puntos extremos, pero la distancia total recorrida debe minimizarse. En la red están anotadas las distancias entre puntos adyacentes.
La trayectoria entre A y Z consta de cuatrospasos, cada uno con una longitud asignada. Por tanto, el objetivo es minimizar la suma de los cuatros pasos seleccionados.
En el problema de viajero que debe recorrer la menor distancia posible...
Regístrate para leer el documento completo.