Programación Dinámica

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 abandonar ese estado.

Este principio puede ser aplicado comenzando por la primera etapa o por la última dependiendo de la naturaleza del problema (mucho autores recomiendan que se inicie de la última etapa del proceso). Si se inicia desde la última etapa, se determina para cada estado la mejor política para abandonar ese estado y completar el proceso considerando que todas las etapas precedentes se han concluido. Después de continúa hacia atrás a lo largo del proceso etapa por etapa. En cada etapa se determina la mejor política para abandonar cada estado y concluir el proceso, considerando que todas las etapas precedentes han sido concluidas y empleando los resultados ya obtenidos para la etapa subsiguiente.

f_n^* (Sn)= g[Rn(Dn,S_(n+1) )+ f_(n+1)^* (S_(n+1) ) ]

RESUMEN EJECUTIVO DE LA EMPRESA

NOMBRE DE LA EMPRESA

“GRUPO UNIÓNC.C.G. SAC.” - SULLANA

DESCRIPCIÓN DE LA EMPRESA

La Embotelladora Grupo Unión C.C.G. SAC., es una empresa fundada en la provincia de Sullana

...