• Author / Uploaded
• EdgardoLopez

• Categories
• Programación dinámica
• Investigación de operaciones
• Toma de decisiones
• Matemática aplicada
• Áreas de la informática

Citation preview

UNIVERSIDAD NACIONAL DE INGENIERIA (UNI) Recinto Universitario Pedro Arauz Palacios. Facultad de la Tecnología de la Industria.

Investigación de operaciones II TEMA: PROGRAMACION DINAMICA ELABORADO POR:    

Br. Jonathan Salvador Aguirre Muñoz 2014-0160u Br. Armando Joel Cerrato Ruiz. 2014-0039u Br. Edgardo de Jesús López Barrera. 2014-0899u Br. Edwin Abraham Vaughan Marín 2014-0727u

CARRERA: Ingeniería Industrial DOCENTE: Ing. ¿?????????? GRUPO:

4T2-IND

Managua, Nicaragua 2017

Indice

PROGRAMACIÓN DINÁMICA

DEFINICIÓN La programación dinámica es una técnica que se usa para determinar si hay posibilidades de modificar las decisiones durante cierto período. La programación dinámica se ocupa también de los problemas en los que el tiempo no es una variable significativa; ejemplo: Hay que tomar una decisión en la distribución de una cantidad fija de recursos entre cierto número de usos alternativos. Este problema puede resolverse descomponiéndolo en varias etapas y de ese modo la decisión final se maneja como si fuera una serie de decisiones dependientes en el transcurso del tiempo.

TIPOS DE MODELOS DE PROGRAMACIÓN DINÁMICA modelos deterministicos - presenta variables discretas - presenta variables continuas

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

modelos determinísticos: objetivo: consiste en profundizar sobre el enfoque del tipo de problema; donde el estado en la siguiente etapa está completamente determinado por el estado y la política de decisión de la etapa actual. Una forma de clasificar los problemas de programación dinámica determinística es por la forma de la función objetivo. también podemos decir que su objetivo es minimizar la suma de las contribuciones de cada una de las etapas individuales o maximizar esas sumas o bien minimizar el producto de los términos.

Otra forma de clasificar los problemas determinísticos es en términos de la naturaleza del conjunto de estados, en las respectivas etapas.

PARÁMETROS ESENCIALES EN LA FORMULACIÓN DE CUALQUIER PROBLEMA Notación: n = número de etapas n = las etapas son las diferentes fuentes canalizadoras de los recursos a asignar. e(n)=son las disponibilidades que se poseen para asignar recursos en la etapa n. xn= son las diferentes asignaciones realizadas en cada etapa n xn*=variable optima de xn dado e(n) fn(en,xn)= contribución a la función objetivo de las etapas n, n+1,.....,n. si el sistema se encuentra en el estado e(n) en la etapa n, la decisión inmediata es xn y en adelante se toman decisiones óptimas. definición de la función recursiva fn(en,xn) = min. [ c(en,xn) + fn-1(xn)]

RUTA MAS CORTA

La empresa Flower maker desea distribuir su producto a distribuidores que pueden comercializar el producto a un costo menor que el que incurre la misma empresa, pero para minimizar costos de transporte la empresa está considerando tomar una sola ruta que minimice costo puesto que por el momento no puede cubrir a todos los distribuidores. Solución:

Metodología de resolución Para resolver este problema por medio de programación dinámica, se tiene que seguir los siguientes pasos mostrados a continuación: 1. Dividir la red inicial en etapas, la primera etapa está constituida con el origen

Luego evaluar las ramas Distancia más corta del nodo 1 al nodo 2 5 7 millas (desde el nodo 1) Distancia más corta del nodo 1 al nodo 3 5 8 millas (desde el nodo 1) Distancia más corta del nodo 1 al nodo 4 5 5 millas (desde el nodo 1) 2. Asignamos el valor a los nodos terminales como parte de la solución inicial para la segunda etapa.

En esta segunda etapa, el objetivo es determinar las distancias acumulativas que correspondan al menor costo. Por ejemplo para el caso del nodo 2 su acumulativa es 7+12=19 pero existen muchas formas de llegar al nodo 5 por lo tanto tenemos que evaluar las diferentes formas de llegar al nodo y elegir la de menor costo. Para evaluar el nodo 5 tenemos tres opciones 7+12=19, 8+8-16, 5+7=12, por lo tanto se elige el acumulativo menor que es 12 proveniente del nodo 4, así sucesivamente se sigue el algoritmo hasta dar con los siguientes resultados mostrados en la etapa 3. 3. En la etapa 3 se muestran los nodos finales con el nodo destino donde se deberá tomar la decisión según el costo acumulativo menor.

Ahora finalmente se toma la decisión para el valor que deberá tener el nodo destino lo cual será el valor de nuestro costo minimo que se puede obtener en la ruta. Se tiene que 17+6=23, 12+9=21