0% encontró este documento útil (0 votos)
116 vistas3 páginasFundamentos de Programación Dinámica
1. Programación dinámica
La programación dinámica parte de una pequeña porción del problema y encuentra la solución óptima para este problema más pequeño. Entonces gradualmente agranda el problema, hallando la solución óptima en curso a partir de la anterior, hasta que se resuelve por completo el problema original.
1.1 Características de los problemas de programación dinámica: etapas, estados, fórmula recursiva, programación en avance y en retroceso.
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 número de estados asociados a ella.
La decisión ´optima 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.
En síntesis, la política óptima es de un estado s de la etapa k a la etapa final esta constituida por una decisión que transforma s en un estado s0 de la etapa k +1 y por la política óptima desde el estado s0 hasta la etapa finalETAPAS. El problema puede dividirse en etapas, con una decisión de la política requerida en cada etapa. Las etapas a considerar van a depender del tipo de problema a resolver.
Para resolver un problema de programación dinámica debemos al menos:
Identificación de etapas, estados y variable de decisión:
Recordemos que mucho de los algoritmos de resolución de problemas lineales (Simplex en particular) son de orden exponencial por lo que resolver m problemas de tamaño n es mas rápido que resolver un problema de tamaño m • n
Cada etapa debe tener asociado una o mas decisiones (problema de optimización), cuya dependencia de las decisiones anteriores esta dada exclusivamente por las variables de estado.
• Cada estado debe contener toda la información relevante para la toma de decisión asociada al periodo.
• Las variables de decisión son aquellas sobre las cuales debemos definir su valor de modo de optimizar el beneficio acumulado y 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 las funciones 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 las recurrencias estén bien definidas requerimos de condiciones de borde.
VARIABLES Consideremos que las variables de decisión Xn (n = 1, 2, 3, 4) son el destino inmediato en la etapa n.
ESTADOS. Cada etapa tiene cierto número de estados asociados a ella.
FUNCION DE EFECTIVIDAD. Se dispone de una relación recursiva que identifica la política óptima para cada estado en la etapa n, dada la política óptima para cada estado en la etapa (n + 1).
OBJETIVO. Minimizar los costos totales
ETAPA 1 2 3 4 RUTA X1 X2 X3 X4
COSTO TOTAL. Sea fn (S, Xn) el costo total de la mejor política global para las etapas restantes, dado que el vendedor se encuentra en el estado S listo para iniciar la etapa n y selecciona a Xn como destino inmediato.
• Dados s y n, denotemos por X*n el valor de Xn que minimiza a fn (s, Xn) y sea f*n (s) el valor mínimo correspondiente de fn (s, Xn).
• Por tanto, f*n (s) = fn (s, X*n )
EJEMPLO
Hallar f*1 (1) y la política correspondiente.
El proceso de calculo es de atrás hacia adelante
ETAPA 4 (CUANDO QUEDA UNA ETAPA)
f*4(s, X4) = Csx4 + f*5(X4)
10 f*4(S) X*4
8 3 + 0 = 3 3 10
9 4 + 0 = 4 4 10
ETAPA 3 (CUANDO QUEDAN 2 ETAPAS)
f*3(s, X3) = Csx3 + f*4(X3)
8 9 f*3(S) X*3
5 1+ 3 = 4 4 +4 = 8 4 8
6 6+ 3 = 9 3 + 4 = 7 7 9
7 3 +3 = 6 3 + 4 = 7 6 8
ETAPA 2 (CUANDO QUEDAN TRES ETAPAS)
f*2(s, X2) = Csx2 + f*3(X2)
5 6 7 f*2S) X*2
2 7+ 4 = 11 4 + 7 = 11 6 + 6 = 12 11 5 ó 6
3 3 + 4 = 7 2 + 7= 9 4 + 6 = 10 7 5
4 4 + 4 = 8 1 + 7 = 8 5
Cargado por
crystelita31Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como TXT, PDF, TXT o lee en línea desde Scribd
0% encontró este documento útil (0 votos)
116 vistas3 páginasFundamentos de Programación Dinámica
1. Programación dinámica
La programación dinámica parte de una pequeña porción del problema y encuentra la solución óptima para este problema más pequeño. Entonces gradualmente agranda el problema, hallando la solución óptima en curso a partir de la anterior, hasta que se resuelve por completo el problema original.
1.1 Características de los problemas de programación dinámica: etapas, estados, fórmula recursiva, programación en avance y en retroceso.
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 número de estados asociados a ella.
La decisión ´optima 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.
En síntesis, la política óptima es de un estado s de la etapa k a la etapa final esta constituida por una decisión que transforma s en un estado s0 de la etapa k +1 y por la política óptima desde el estado s0 hasta la etapa finalETAPAS. El problema puede dividirse en etapas, con una decisión de la política requerida en cada etapa. Las etapas a considerar van a depender del tipo de problema a resolver.
Para resolver un problema de programación dinámica debemos al menos:
Identificación de etapas, estados y variable de decisión:
Recordemos que mucho de los algoritmos de resolución de problemas lineales (Simplex en particular) son de orden exponencial por lo que resolver m problemas de tamaño n es mas rápido que resolver un problema de tamaño m • n
Cada etapa debe tener asociado una o mas decisiones (problema de optimización), cuya dependencia de las decisiones anteriores esta dada exclusivamente por las variables de estado.
• Cada estado debe contener toda la información relevante para la toma de decisión asociada al periodo.
• Las variables de decisión son aquellas sobre las cuales debemos definir su valor de modo de optimizar el beneficio acumulado y 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 las funciones 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 las recurrencias estén bien definidas requerimos de condiciones de borde.
VARIABLES Consideremos que las variables de decisión Xn (n = 1, 2, 3, 4) son el destino inmediato en la etapa n.
ESTADOS. Cada etapa tiene cierto número de estados asociados a ella.
FUNCION DE EFECTIVIDAD. Se dispone de una relación recursiva que identifica la política óptima para cada estado en la etapa n, dada la política óptima para cada estado en la etapa (n + 1).
OBJETIVO. Minimizar los costos totales
ETAPA 1 2 3 4 RUTA X1 X2 X3 X4
COSTO TOTAL. Sea fn (S, Xn) el costo total de la mejor política global para las etapas restantes, dado que el vendedor se encuentra en el estado S listo para iniciar la etapa n y selecciona a Xn como destino inmediato.
• Dados s y n, denotemos por X*n el valor de Xn que minimiza a fn (s, Xn) y sea f*n (s) el valor mínimo correspondiente de fn (s, Xn).
• Por tanto, f*n (s) = fn (s, X*n )
EJEMPLO
Hallar f*1 (1) y la política correspondiente.
El proceso de calculo es de atrás hacia adelante
ETAPA 4 (CUANDO QUEDA UNA ETAPA)
f*4(s, X4) = Csx4 + f*5(X4)
10 f*4(S) X*4
8 3 + 0 = 3 3 10
9 4 + 0 = 4 4 10
ETAPA 3 (CUANDO QUEDAN 2 ETAPAS)
f*3(s, X3) = Csx3 + f*4(X3)
8 9 f*3(S) X*3
5 1+ 3 = 4 4 +4 = 8 4 8
6 6+ 3 = 9 3 + 4 = 7 7 9
7 3 +3 = 6 3 + 4 = 7 6 8
ETAPA 2 (CUANDO QUEDAN TRES ETAPAS)
f*2(s, X2) = Csx2 + f*3(X2)
5 6 7 f*2S) X*2
2 7+ 4 = 11 4 + 7 = 11 6 + 6 = 12 11 5 ó 6
3 3 + 4 = 7 2 + 7= 9 4 + 6 = 10 7 5
4 4 + 4 = 8 1 + 7 = 8 5
Cargado por
crystelita31Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como TXT, PDF, TXT o lee en línea desde Scribd