Programacion dinamica
Páginas: 9 (2098 palabras)
Publicado: 16 de mayo de 2011
Facultad de Ingenieria
E.A.P. Ingeniería de sistemas
TEMA: Programación Dinámica
CURSO: Investigación de Operaciones II
DOCENTE: Ing. Alcibiades Sosa Palomino
CICLO: VII
ALUMNOS:
* Asencios Gonzales Héctor
* Bellón Pacheco Jorge Armando
* Chacpi Ostos Omar
* Natividad CalderónEduardo
HUACHO – PERÚ
2010
PROGRAMACION DINAMICA
Muchos problemas de programación matemática determinan soluciones que repercuten en la formulación de los problemas a resolver en el próximo periodo 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 delproblema.
Sin embargo esto pude agrandar mucho el tamaño del problema. Surge así la Programación Dinámica (PD) como una alternativa de descomposición en que resolvemos subproblemas más pequeños y luego los ligamos. Así, la programación dinamia consiste en solucionar el presente suponiendo que en cada etapa futura siempre se tomaran las decisiones correctas.
El comportamiento de losparámetros de cada etapa pueden ser determinístico o probabilístico; teniendo en cuenta este comportamiento los modelos de Programación Dinámica pueden ser Determinísticos y Probabilísticos.
CARACTERISTICAS
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 serdividido en etapas.
* Cada etapa tiene un número 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.
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 quetransforma s en un estado s0 de la etapa k +1 y por la política óptima desde el estado s0 hasta la etapa final.
Pasos Para Resolución De Un Problema De Programación Dinámica
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 más 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ónasociada 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ónDebemos 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.
PROCEDIMIENTO GENERAL
1. Identificar las etapas.
2. En cada etapa identificar
dn: Variable de decisión
f nx n: variable de estado x n+1
Función recursiva
r n: rendimiento resultado
x n: Situación actual antes de tomar la decisión
d n: Decisión a tomar en...
E.A.P. Ingeniería de sistemas
TEMA: Programación Dinámica
CURSO: Investigación de Operaciones II
DOCENTE: Ing. Alcibiades Sosa Palomino
CICLO: VII
ALUMNOS:
* Asencios Gonzales Héctor
* Bellón Pacheco Jorge Armando
* Chacpi Ostos Omar
* Natividad CalderónEduardo
HUACHO – PERÚ
2010
PROGRAMACION DINAMICA
Muchos problemas de programación matemática determinan soluciones que repercuten en la formulación de los problemas a resolver en el próximo periodo 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 delproblema.
Sin embargo esto pude agrandar mucho el tamaño del problema. Surge así la Programación Dinámica (PD) como una alternativa de descomposición en que resolvemos subproblemas más pequeños y luego los ligamos. Así, la programación dinamia consiste en solucionar el presente suponiendo que en cada etapa futura siempre se tomaran las decisiones correctas.
El comportamiento de losparámetros de cada etapa pueden ser determinístico o probabilístico; teniendo en cuenta este comportamiento los modelos de Programación Dinámica pueden ser Determinísticos y Probabilísticos.
CARACTERISTICAS
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 serdividido en etapas.
* Cada etapa tiene un número 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.
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 quetransforma s en un estado s0 de la etapa k +1 y por la política óptima desde el estado s0 hasta la etapa final.
Pasos Para Resolución De Un Problema De Programación Dinámica
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 más 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ónasociada 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ónDebemos 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.
PROCEDIMIENTO GENERAL
1. Identificar las etapas.
2. En cada etapa identificar
dn: Variable de decisión
f nx n: variable de estado x n+1
Función recursiva
r n: rendimiento resultado
x n: Situación actual antes de tomar la decisión
d n: Decisión a tomar en...
Leer documento completo
Regístrate para leer el documento completo.