Investigación individual sobre programación Dinámica

Universidad Americana

Facultad de Ingeniería y Arquitectura

[pic 1]

INVESTIGACIÓN DE OPERACIONES II

Actividad de aprendizaje número 5:

Investigación individual sobre programación Dinámica

Nombre de la estudiante y CIF:

Cora Oliveth Jarquin Bermúdez                18020256

Catedrático:

Johana de los Angeles Núñez Sevilla

18 de marzo de 2022

Managua, Nicaragua

índice

1.        Introducción        3

2.        Desarrollo        4

A.        Ilustre y describa el algoritmo de la Programación Dinámica        4

B.        Características de la PD. Mínimo cinco características        5

C.        Elementos de un problema de PD: Describa brevemente todos los elementos de un problema de PD        5

D.        Modelos de la programación dinámica: A través de una ilustración presente y describa los modelos de PD        6

E.        Metodología o técnica de la programación dinámica: Ilustre y explique la metodología de la programación dinámica        7

F.        Aplicaciones o usos más comunes de la PD: Describe como mínimo tres aplicaciones de la PD        7

G.        Diferencias entre la Programación Lineal y programación Dinámica, mínimo cuatro diferencias        8

3.        Conclusiones        9

4.        Referencias bibliográficas        10

1. Introducción

La programación dinámica, o Dynamic Programming (DP), fue introducida por primera vez por Richard E. Bellman en la década de 1950. El término «dinámica» significa que el problema tiene componentes secuenciales o temporales, y «programación» se refiere a una política de optimización. (TORRES.AI, 2021)

Se puede decir que, la programación dinámica proporciona un marco general para problemas dinámicos complejos dividiéndolos en subproblemas, esta es una de las características de la PD que más resalta.

La programación dinámica proporciona un marco fundamental para aprender a interactuar con el MDP de forma incremental, ya que la mayoría de los algoritmos de aprendizaje por refuerzo intentan aproximarse de esta manera a la resolución del problema.

Una ecuación de Bellman, llamada así por Richard E. Bellman, es una condición necesaria para la optimización asociada con el método de optimización matemática conocido como programación dinámica. Escribe el "valor" de un problema de decisión en un determinado momento en términos de la recompensa de algunas elecciones iniciales y el "valor" del problema de decisión restante que resulta de esas elecciones iniciales. Rompe un problema de optimización dinámica en una secuencia de subproblemas más simples, como prescribe el "principio de optimización" de Bellman. (hmong.wiki, s/f)

En tiempo discreto, cualquier problema de optimización de múltiples etapas se puede resolver analizando la ecuación de Bellman apropiada. La ecuación de Bellman adecuada se puede encontrar introduciendo nuevas variables de estado (aumento de estado). (hmong.wiki, s/f)

La programación dinámica tiene una gran importancia en el ámbito de la ingeniería y economía, esta evita calcular varias veces la misma información, mantiene una tabla de resultados conocidos o recopilados, la tabla se va llenando a medida que se van resolviendo los subcproblemas.

La programación dinámica no solamente se aplica por razones de eficiencia, sino porque permite resolver de manera eficiente problemas que son difíciles de resolver por otras metodologías como la lineal y la entera.

1. Desarrollo

1.  Ilustre y describa el algoritmo de la Programación Dinámica

[pic 2]

El algoritmo de la Programación Dinámica proporciona un procedimiento sistemático para encontrar la combinación de decisiones que maximice la efectividad total, al descomponer el problema en etapas, las que pueden ser completadas por una o más formas (estados), y enlazando cada etapa a través de cálculos recursivos.

Según lo indicado en clases, el algoritmo de la Programación Dinámica es muy diferente a las anteriores programaciones, es decir, la Programación Dinámica es la que se realizan los ejercicios para maximizar sus utilidades, además estos se realizan de atrás para adelante, se va haciendo distribuciones y programaciones de distinta manera a como lo señala la imagen.

1. Características de la PD. Mínimo cinco características

• Cada uno de los problemas que se proponen con la Programación Dinámica se pueden dividir en etapas que requieren una política de decisión en cada una.
• Cada una de las etapas tienen cierto número de estados asociados a ellas.
• El procedimiento de la solución está diseñado para encontrar una política óptima para el problema completo.
• El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con la siguiente etapa.
• El procedimiento de solución se inicia al encontrar la política óptima para la última etapa.
•  Dado un estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en las etapas anteriores (principio de optimalizad).
• Se dispone de una relación recursiva que identifica la política optima par la etapa n dada la política óptima para la etapa (n+1).

1. Elementos de un problema de PD: Describa brevemente todos los elementos de un problema de PD

1. Etapas:

Se pueden definir como cada uno de los pasos que se deben seguir para llegar al objetivo. Las representamos por líneas discontinuas.

1. Estados:

Son las diversas condiciones posibles en la que el sistema podría estar en esa etapa del problema. Se representan por círculos.

...