Investigacion De Operaciones

PROGRAMACION DINAMICA

HISTORIA

Richard Bellman y George Bernard Dantzig fueron los creadores de la programación dinámica. Sus importantes contribuciones a esta técnica cuantitativa se publicaron por vez primera en la década de 1950. Inicialmente, la programación dinámica se llamo programación lineal estocástica, o bien problemas de programación lineal relacionados con la incertidumbre. Actualmente la programación dinámica se ha desarrollado como una técnica cuantitativa para resolver una amplia gama de problemas.

La programación dinámica puede definirse como una técnica matemática, para la solución de una serie de decisiones en secuencia.

Hay que tomar una secuencia de decisiones, con cada una de ellas que afecte las decisiones futuras.

Programación dinámica

Técnica cuantitativa que permite encontrar las decisiones optimas en un proceso dividido en faces.

Algunos ejemplos podrían se:

La asignación de personas a tareas

El cambio de un catalizador en un coche

Hasta un juego de cartas

Los elementos que definen un problema de programación dinámica son :

 Etapas

 Estados

 Variables de decisión

 Función recurrente

Etapas (n o N)

Las etapas son el periodo de tiempo, el lugar, el contexto, la fase o la situación en donde se produce un cambio debido a una decisión.

Solo puede tomarse una única decisión en cada etapa.

Las etapas se definen con la letra n

Si utilizamos la letra n minúscula empezaremos a contar desde el principio hasta el final

Si utilizamos la letra N mayúscula empezaremos a contar desde el final hasta el principio.

En general utilizaremos la primera opción

Estados (en)

Los estados muestran la situación actual del sistema cuando nos encontramos en la etapa n.

Cada etapa tiene su propio estado

Por ejemplo, la etapa n = 1 tiene el estado e1

Variables de decisión (Xn)

Las variables de decisión hacen referencia a toma de decisiones que se produce en una etapa y que provoca un cambio en el estado actual del sistema.

Cada etapa tiene su propia variable de decisión

Por ejemplo, la etapa n = 1 tiene la variable x1

La cual le permite evolucionar a la etapa n = 2

Función recurrente (fn)

La función de recurrencia refleja el comportamiento del sistema en funcion de los estados y las variables de decisión.

fn (en, xn)

Cada etapa tiene su propia función recurrente

Por ejemplo la etapa n = 1 tiene la función recurrente f1 que depende de x1 y e1 es decir del estado y de la variable de decisión de esa etapa.

Por ejemplo

La función en la cuarta etapa hace referencia a la cuarta etapa.

La función de la tercera etapa hace referencia a la tercera etapa y al resto de etapas que hay hasta el final del sistema

La función de la segunda etapa hace referencia a la segunda etapa y al resto de etapas que hay hasta el final del sistema

La función de la primera etapa hace referencia a la primera etapa y al resto de etapas que hay hasta el final del sistema

La aplicación de la programación dinámica se divide en dos faces

1. El analysis

2. Decision

La fase de análisis se empieza por la ultima etapa.

En este caso se analizan todas las opciones posibles de la cuarte etapa

Después se pasa a la etapa anterior n = 3

Se calculan todas las opciones posibles

Y se agrega a los resultados obtenidos previamente.

Después se pasa a la etapa anterior n = 2

Se calculan todas las opciones posibles

Y se agrega a los resultados obtenidos previamente

Después se pasa a la etapa anterior n = 1

Se calculan todas las opciones posibles

Y se agrega a los resultados obtenidos previamente

Llegando a este punto ya hemos calculado todas las opciones posibles.

Empezamos la fase de decisión

A diferencia de la fase anterior los cálculos a hora se realizan desde el principio hasta el final

Empezamos por la etapa uno y decidimos la mejor opción posible

Pasamos a la etapa dos y decidimos la mejor opción posible

Luego pasamos a la etapa tres y decidimos la mejor opción posible

Y finalmente pasamos a la etapa cuatro y decidimos la mejor opción posible

Unas ves llegado a este punto hemos llegado a la solución del problema.

1.1 CARACTERISTICAS DE LA PROGRAMACION DINAMICA

1. Una de las características esenciales es la toma de decisiones en secuencia.

2. El problema se puede dividir en etapas, las cuales requieren de una política de decisión, en cada una de ellas.

3. Es necesarios conocer pocos datos para describir el problema en cada etapa.

4. La dependencia del resultado de las decisiones de una pequeña cantidad de variables.

5. En cualquier etapa, el resultado de una decisión, altera los valores numéricos de la pequeña cantidad de variables relacionadas con el problema.

6. Cada etapa tiene un cierto número de estados asociados a ella.

Estos son las distintas condiciones posibles en las que se puede encontrar el sistema en cada etapa del problema.

7.- 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.

8. La decisión real no aumenta ni disminuye el número de factores de los que dependen los resultados.

1.2 EJEMPLOS DE MODELOS DE PROGRAMACION DINAMICA

Dentro de los ejemplos de programación dinámica se encuentran:

Modelos determinísticos

-presenta variables discretas

-Presenta variables continuas

Modelos probabilísticos

Son aquellos que toman una característica similar a los procesos markovianos, es decir una evaluación de un evento en un periodo futuro.

1.3 PROGRAMACION DINAMICA DETERMINISTA

Los problemas determinísticos de programación dinámica son aquellos enlos cuales

...