Programación Dinámica en Redes: Ejemplos y Aplicaciones PDF

Unidad 1 1.3 La programación dinámica aplicada a problemas de redes. 1.3.1 El problema de la mochila de Knapsack. 1.3.2 Ruta más corta. Docente: Edith Toscano Velázquez La programación dinámica Se aplica en la gestión de redes y cadenas de suministro para reso...

Unidad 1 1.3 La programación dinámica aplicada a problemas de redes. 1.3.1 El problema de la mochila de Knapsack. 1.3.2 Ruta más corta. Docente: Edith Toscano Velázquez La programación dinámica Se aplica en la gestión de redes y cadenas de suministro para resolver problemas de optimización relacionados con la asignación de recursos, la planificación de la producción, la gestión de inventarios, entre otros. (Montero, 2015) La programación dinámica  Es una técnica de optimización que resuelve problemas dividiéndolos en subproblemas más pequeños y resolviéndolos de manera recursiva. Se utiliza ampliamente en la optimización de redes y cadenas de suministro. (Pérez, 2010) Elementos que intervienen en un problema de programación dinámica 1.- ETAPAS: 2.- ESTADOS: Se pueden Son las 3.- definir como diversas POLÍTICA: 4. cada uno de condiciones SUBPOLÍTICA: los pasos que Es cualquiera posibles en la se deben de los caminos Es un que el sistema seguir para que llevan de subconjunto podría estar en llegar al la primera a la de la política. esa etapa del objetivo las última etapa. problema se representamos representan por líneas por círculos. discontinuas. Fases fundamentales de programación dinámica  1. Definir recursivamente la solución del problema.  2. Definir la estructura de datos para memorizar las soluciones de los subproblemas y escribir el algoritmo que va calculando los valores de esa estructura de datos siguiendo la caracterización de la solución definida en la fase 1, pero sin repetir el cálculo de soluciones de subproblemas. ¿Dónde y por qué se utiliza la programación dinámica?  se usa en áreas donde tenemos problemas que se pueden dividir en subproblemas más pequeños, y sus soluciones se usan para resolver problemas más grandes.  ¿Dónde y por qué se utiliza la programación dinámica? Informática: se utiliza para resolver problemas que involucran secuencias, gráficos y valores enteros y en programación competitiva. Economía: se utiliza para resolver problemas de optimización en finanzas, producción y asignación de recursos. Matemáticas: se utiliza en teoría de juegos, estadística y probabilidad, donde se utiliza para resolver problemas de optimización. Ingeniería: se utiliza para resolver problemas de asignación de recursos, programación, fabricación, comunicación y sistemas de control. Características de un problema de programación dinámica  Subestructura óptima: Los problemas de cadena de suministros pueden descomponerse en subproblemas más pequeños, donde la solución óptima del problema global se construye a partir de las soluciones óptimas de estos subproblemas. Por ejemplo: en la gestión de inventarios Características de un problema de programación dinámica  Superposición de subproblemas: Los problemas de cadena de suministros a menudo implican la repetición de decisiones similares a lo largo del tiempo o en diferentes partes de la cadena. Características de un problema de programación dinámica  Optimalidad de las Subestructuras: La solución óptima de un problema de cadena de suministros contiene la solución óptima de sus subproblemas. Por ejemplo: en la planificación de la producción. Características de un problema de programación dinámica  Memorización o Tabulación: Se utiliza para almacenar y reutilizar las soluciones de los subproblemas, evitando así recalcularlos repetidamente. Características de un problema de programación dinámica  Decisión de caminos: Implica tomar decisiones secuenciales o seleccionar entre múltiples caminos posibles. Por ejemplo, en la optimización de rutas de distribución.  Para dar solución a un problema se requiere: Un grado de creatividad Conocimiento de la estructura general de los problemas de programación dinámica Determinar el planteo de la formula de recursividad Ejemplo problema de programación dinámica Recursividad  Proceso mediante el que una función se llama a sí misma de forma repetida, hasta que se satisface alguna determinada condición.  El proceso se utiliza para computaciones repetidas en las que cada acción se determina mediante un resultado anterior. Recursividad El problema de la mochila de Knapsack. ¿Qué es el problema de la mochila de Knapsack? Es un problema que modela la situación de llenar una mochila, limitada a cierta capacidad de peso y con cierta cantidad de objetos con diferentes pesos y valores cada uno. El problema consiste:  Elegir un subconjunto de n artículos maximizando el beneficio obtenido considerando el peso total de los artículos seleccionados, sin exceder la capacidad de la mochila. La mochila Knapsack se aplica: Logística y transporte: para optimizar la carga de vehículos de transporte. Administración de proyectos: para asignar recursos limitados Gestión de inventarios: determinar la combinación optima de productos almacenar. Planificación de producción: decidir que productos y en que cantidad. Diseño de redes y telecomunicaciones: optimizar la asignación de recursos de redes de comunicación.  El problema de la mochila Knapsack La mochila siempre tendrá una restricción Los elementos utilizan un código binario X=(1, 0) Suma constante de los valores Todos los valores son enteros y positivos Problema de optimización Formula de la mochila Knapsack Maximizar el beneficio de la mochila sin pasar del peso máximo de la mochila Ejemplo del problema de la mochila Knapsack María se va de excursión al campo requiere llevar cierta cantidad de productos como:  Comida  Short  Playeras  Cargador de celular  Computadora  Chanclas  Libro Su mochila tiene un limite de peso de 2000 gramos  Parámetros Num. Articulo Peso Beneficio (gramos) 1 Cargador 10 20 2 Comida 500 100 3 Computadora 1700 50 Capacidad de la mochila Limite de peso: 2000 gramos Variables Binarias (dos valores)  Comida 0 1  Short 0 1  Playeras 0 1  Cargador de celular 0 1  Computadora 0 1  Chanclas 0 1  Libro 0 1 Variables Binarias 1 si se selecciona el i Xi = 0 en caso contrario No. Variable Articulo Peso Beneficio (gramos) 1 X1 Cargador 10 20 2 X2 Comida 500 100 3 X3 Computadora 1700 50 Maximizar 20x1 + 100x2 + 50x3 ≤ 2000 Peso 10x1 + 500x2 + 1700x3 ≤ 2000 Maximizar Beneficio 20x1 + 100x2 + 50x3 Peso 10x1 + 500x2 + 1700x3 ≤ 2000 X1 = 1 X2 = 0 X3 = 1 Maximizar Beneficio 20x1 + 100x2 + 50x3 Peso 10x1 + 500x2 + 1700x3 ≤ 2000 Función objetivo z= 10+1700 z=1710 María solo puede llevar en su mochila el cargador y la computadora RUTA MÁS CORTA  Según Chopra y Meindl (2016), el concepto de la “ruta más corta” es fundamental en la planificación de rutas en las cadenas de suministro. RUTA MÁS CORTA  Esta ruta se define como el itinerario que minimiza la distancia total recorrida o el tiempo necesario para transportar los productos desde el punto de origen hasta el punto de destino. RUTA MÁS CORTA  optimización de rutas no es simplemente una cuestión de elegir el camino más corto, sino que implica la aplicación de técnicas sofisticadas para encontrar la combinación óptima de rutas.  Ejemplo de la ruta mas corta  Un operador de una flotilla de camiones, ha aceptado un contrato para entregar varias cargas de material de un origen Cancún, a un destino Mérida.  En la siguiente red mostramos las posibles rutas que los camines pueden tomar junto con las distancias en kilómetros entre cada uno de los nodos  Se identifican el nodo o los nodos mas cercano al origen (nodo A), nodos cercanos (B y C)  La rama (A B) es la mas corta  Indicamos arriba del B que la distancia corta es de 250 kilómetros 250  Nodo B, desde D=250+300=500  Nodo B, desde C=250+100=350  Se cancela la ruta AC que forma un ciclo. 250 350  Dos formas de llegar a D  Nodo B =250+300=550  Nodo C =350+150=500 es la ruta mas corta  Se cancela la ruta BD que forma un ciclo. 250 500 350  Los nodos mas cercano al origen son C y D  Nodo D hasta E = 500+100=600 la ruta más corta  Nodo C hasta E=350+275= 625  Se cancela la ruta CE que forma un ciclo. 250 500 600 350  Vamos al nodo F  Nodo D hasta F = 500+200=700  Nodo E hasta F=600+150= 750  Se cancela la ruta EF para evitar el ciclo. 250 500 700 600 350