ClubEnsayos.com - Ensayos de Calidad, Tareas y Monografias
Buscar

Programación Dinámica


Enviado por   •  9 de Diciembre de 2014  •  769 Palabras (4 Páginas)  •  208 Visitas

Página 1 de 4

MARCO TEÓRICO

INTRODUCCIÓN A LA PROGRAMACIÓN DINÁMICA

Introducción

La Programación Dinámica es un térmico que utilizó el matemático Richard Bellman en los 1940’s para resolver problemas complejos que pueden ser discretizados y secuencializados. La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas

Una subestructura óptima significa que se pueden usar soluciones óptimas de subproblemas para encontrar la solución óptima del problema en su conjunto. Por ejemplo, el camino más corto entre dos vértices de un grafo se puede encontrar calculando primero el camino más corto al objetivo desde todos los vértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor camino de todos ellos. En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:

Dividir el problema en subproblemas más pequeños.

Resolver estos problemas de manera óptima usando este proceso de tres pasos recursivamente.

Usar estas soluciones óptimas para construir una solución óptima al problema original.

Desarrollo 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:

Cada etapa debe tener asociado una o más decisiones (problema de optimización), cuya dependencia de las decisiones anteriores está 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: 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.

Función Recursiva

Es la relación que interconecta una etapa con otra, relacion que asocia la política óptima para cada estado de la etapa n (n = 1, 2, 3…. N), con la política óptima de cada estado de la etapa n+1.

Princicio de Optimalidad

Tiene la propiedad de que independientemente de las decisiones tomdas para llegar a un estado particular en una etapa particular, las decisiones restantes deben constituir una política òptima, para

...

Descargar como (para miembros actualizados)  txt (5.1 Kb)  
Leer 3 páginas más »
Disponible sólo en Clubensayos.com