Programacion Dinamica

DEPARTAMENTO DE INGENIERIA QUIMICA Y
BIOQUIMICA
SINTESIS Y OPTIMIZACION DE PROCESOS
TITULO DEL TRABAJO. –

“Programación Dinámica”
Docente. – Hugo Renovato González
NOMBRE DE LOS ALUMNOS. - No DE CONTROL. -

ZAMORA GARCIA ROJAS LUIS GUILLERMO 14071482
ROQUE FLORES GILBERTO URIEL
Introducción
1
La programación dinámica es un método de optimización que puede
aplicarse a diferentes y numerosos problemas, algunos de los cuales
ya han sido analizados en programación lineal y programación entera.
Los parámetros usados en la programación dinámica pueden ser
estocásticos o probabilísticos y determinísticos.
La programación dinámica tiene como finalidad encontrar una
solución de un problema de optimización en forma secuencial. A
diferencia de la programación lineal, la programación entera no es un
algoritmo de solución única, sino más bien un método para resolver un
problema grande y único solventando una secuencia de problemas
más pequeños, sin importar el número de ellos. Ahora, la
programación dinámica permite resolver un problema que depende del
tiempo en forma de una continuidad de problemas de un sólo periodo,
en donde los parámetros de cada periodo dependen del periodo que
se considera; es posible que no se conozca la cuantificación de cada
periodo sino hasta que éste llega.
La solución de problemas mediante la programación dinámica se
basa en el llamado principio de óptimo, enunciado por Bellman (1957)
y que dice: “En una secuencia de decisiones óptima toda
subsecuencia ha de ser también óptima”. Sin embargo, se debe
evaluar en cada problema presentado que este principio se esté
cumpliendo y analizar cómo abordar cada uno de los problemas de
acuerdo a sus propias características.
4.1 Generalidades de la 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.
La programación dinámica comenzó a emplearse durante la Segunda
Guerra Mundial. Algunos de los aliados (Alemania, Inglaterra, Estados
Unidos y la U.R.S.S.), conformaron grupos de trabajo consagrados a
la investigación, quienes posteriormente serian la base de muchos de
los inventos que aparecieron durante este tiempo de guerra,
inicialmente diseñados como estrategias militares para la guerra y que
posteriormente contribuirían al desarrollo luego de 1945.
2
La primera disciplina que surgió a partir de la forma como se dio
solución a muchos problemas en la guerra, fue la investigación
operativa.
Después de la guerra los equipos de trabajo dedicados a la
investigación, dieron inicio a nuevos temas que, como resultado final,
arrojaron el planteamiento de diversos problemas que fueron
abordados desde un enfoque netamente matemático y en donde la
programación dinámica se comenzó a aplicar después de 1952.
Posteriormente, Richard Bellman (1920 – 1984), en el año de 1957,
desarrolla el método en el área de los problemas de decisión discretos
y con la ayuda de sus colaboradores se dedicó a formular modelos
matemáticos capaces de solucionar diferentes problemas en los
términos de la programación dinámica que, como resultado, mostraron
que las ideas centrales de los métodos aplicados por ellos, en
particular, las basadas en el Principio de Optimalidad, podrían ser
utilizadas satisfactoriamente en la mayoría de los problemas que se
estaban presentando en aquella época.
Características de un problema de programación dinámica
Para que un problema pueda ser resuelto mediante programación
dinámica, debe cumplir con ciertas características, como:
 El problema puede ser dividido en etapas.
 Cada etapa tiene un número de estados asociados a ella.
 La decisión óptima de cada etapa depende sólo del estado
actual y no de las decisiones anteriores.
 La decisión tomada en una etapa determina cuál será el estado
de la etapa siguiente.
4.2 Resolución de un problema de programación dinámica
Para resolver un problema de programación dinámica se debe:
 Identificar etapas, estados y variable de decisión: Cada etapa
debe tener asociada una o más decisiones (problema de
optimización).
3
- 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 se debe
definir su valor, de modo que se pueda optimizar el beneficio
acumulado y modificar el estado de la próxima etapa.
 Describir las ecuaciones de recurrencia: Se debe indicar cómo
se acumula la función de beneficios a optimizar (función objetivo)
y cómo varían las funciones de estado de una etapa a otra.
 Solucionar: Se debe optimizar cada sub-problema por etapas en
función de los resultados de la resolución del sub-problema
siguiente.
Tipos de programación dinámica
4.3 Terminología
Función de Valor Óptimo: Se puede llamar a la regla que asigna
valores a varios problemas dentro de un problema.
Función de Política Óptima: Es la que asocia la primera mejor
decisión con cada problema.
Relación de recurrencia o relación recursiva: Es el producto que
provoca una fórmula o grupo de fórmulas que pertenecen a varios
valores de S, basado en el principio de optimalidad.
4
Condiciones limitantes: Asumidas como obvias desde el
planteamiento del problema y desde la definición de S con cálculos
necesitados como resultantes de los valores de la función de valor
óptimo S para ciertos argumentos.
4.4 Etapas y estados en programación dinámica
Cuando una variable describe cuántas decisiones han sido tomadas
hasta cierto momento y si el número total de decisiones es fijo, el
número de etapas será igual al número de decisiones.
Las variables de estado, que son las posibles condiciones variadas
en las cuales el procedimiento se encuentra en esa etapa del
problema y el número de estados, pueden ser finitas o infinitas.
La decisión en cada etapa es el resultado de asignar un número de
veces las variables de estado sucesivas Xn, Xn+1 que están unidas
a través de la ecuación recursiva que calcula los valores de Xn+1
usando el valor de Xn y la decisión en el estado dn.
Las variables de estado pertenecen al presente estado con el
anterior y permiten calcular la restante cantidad de recursos
escasos. En programación dinámica existen dos procedimientos:
En retroceso: Caracterizado por tener unas condiciones terminales
fijas y el cálculo de valores numéricos se realiza desde la línea
terminal al punto inicial.
En avance: Caracterizado por tener unas condiciones iniciales fijas
y el cálculo de valores numéricos se realiza desde la línea inicial al
punto final.
5
6
7
8
9
10
11
12
13
14

Programacion Dinamica

Cargado por

Copyright:

Formatos disponibles

Programacion Dinamica

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Programacion Dinamica

Cargado por

Copyright:

Formatos disponibles

DEPARTAMENTO DE INGENIERIA QUIMICA Y

SINTESIS Y OPTIMIZACION DE PROCESOS

TITULO DEL TRABAJO. –

Docente. – Hugo Renovato González

NOMBRE DE LOS ALUMNOS. - No DE CONTROL. -

Tipos de programación dinámica

También podría gustarte