Programación Dinámica en Redes y Cadenas

Programación Dinámica en Problemas de Redes

• La programación dinámica se utiliza para resolver problemas de optimización en la gestión de redes y cadenas de suministro.
• Se relaciona con la asignación de recursos, la planificación de producción y la gestión de inventarios.
• Es una técnica de optimización que divide problemas en subproblemas más pequeños, resolviéndolos de forma recursiva.
• Se usa ampliamente para optimizar redes y cadenas de suministro.

Elementos de la Programación Dinámica

• Etapas: Son los pasos a seguir definidos para alcanzar un objetivo, representados por líneas discontinuas.
• Estados: Son las posibles condiciones del sistema en cada etapa del problema, representados por círculos.
• Política: Es cualquier camino que lleva desde la primera hasta la última etapa.
• Subpolítica: Es un subconjunto de la política.

Fases Fundamentales de la Programación Dinámica

• Definir recursivamente la solución del problema.
• Definir la estructura de datos para memorizar las soluciones de los subproblemas.
• Escribir el algoritmo y calcularlo sin repetir soluciones de subproblemas.

Aplicaciones de la Programación Dinámica

• Se utiliza en áreas con problemas divisibles en subproblemas menores cuyas soluciones sirven para resolver problemas mayores.
• En informática, para resolver problemas de secuencias, gráficos, valores enteros y en programación competitiva.
• En economía, para problemas de optimización en finanzas, producción y asignación de recursos.
• En matemáticas, en teoría de juegos, estadística y probabilidad para resolver problemas de optimización.
• En ingeniería, para 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 se descomponen en subproblemas más pequeños.
• 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.
• 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.
• 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.
• Memorización o tabulación: Se utilizan para almacenar y reutilizar las soluciones de los subproblemas, evitando recalcularlos repetidamente.
• Decisión de caminos: Implica tomar decisiones secuenciales o seleccionar entre múltiples caminos posibles.
• Un ejemplo sería la optimización de rutas de distribución.

Solución de un Problema de Programación Dinámica Necesita

• Creatividad.
• Conocimiento de la estructura general de los problemas de programación dinámica.
• Determinar el planteo de la fórmula de recursividad.

Recursividad

• Es un proceso en el que una función se llama a sí misma repetidamente hasta que se cumple una condición específica.
• Se usa en computaciones repetidas donde cada acción se determina por un resultado anterior.

El Problema de la Mochila (Knapsack)

• Modela la situación de llenar una mochila con capacidad limitada.
• Se escogen objetos con diferentes pesos y valores.
• El objetivo es elegir un subconjunto de artículos, maximizando el beneficio total sin exceder la capacidad de la mochila.

Aplicaciones del Problema de la Mochila

• Logística y transporte: optimizar la carga de vehículos.
• Administración de proyectos: asignar recursos limitados.
• Gestión de inventarios: determinar la combinación óptima de productos a almacenar.
• Planificación de producción: decidir qué productos y en qué cantidad.
• Diseño de redes y telecomunicaciones: optimizar la asignación de recursos de redes de comunicación.

Características del Problema de la Mochila

• La mochila tiene una restricción de capacidad.
• Los elementos tienen un código binario X = (1, 0).
• La suma de los valores es constante.
• Todos los valores son enteros y positivos.
• Es un problema de optimización.

Fórmula del Problema de la Mochila

• Maximizar el beneficio de la mochila sin exceder el peso máximo.
• Maximizar: ∑(desde i=1 hasta n) vᵢxᵢ
• Sujeto a: ∑(desde i=1 hasta n) wᵢxᵢ ≤ W
  • n = número de objetos distintos
  • xᵢ = elementos
  • vᵢ = valor del elemento
  • wᵢ = volumen del elemento
  • W = capacidad total de la mochila

Ejemplo del Problema de la Mochila

• María va de excursión y necesita llevar: comida, short, playeras, cargador de celular, computadora, chanclas y un libro.
• Su mochila tiene un límite de peso de 2000 gramos.

Parámetros

• Capacidad de la mochila es de 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

Indicador de selección

• Si se selecciona el ítem i. Xᵢ = 1

• Xᵢ = 0 En caso contrario

• La función a maximizar sería: 20x₁ + 100x₂ + 50x₃ ≤ 2000

• La restricción de peso es: 10x₁ + 500x₂ + 1700x₃ ≤ 2000

• Para maximizar el beneficio, María solo puede llevar el cargador (x₁ = 1) y la computadora (x₃ = 1).

• La función objetivo es: Z = 10 + 1700 = 1710

Ruta Más Corta

• Según Chopra y Meindl (2016), el concepto de "ruta más corta" es fundamental en la planificación de rutas en las cadenas de suministro.
• Se define como el itinerario que minimiza la distancia total o el tiempo necesario para transportar los productos desde el origen hasta el destino.
• La optimización de rutas no es simplemente 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 Ruta Más Corta

• Un operador de camiones debe entregar cargas desde Cancún a Mérida.
• Se deben determinar las rutas que minimicen la distancia.
• Se identifica el nodo o los nodos más cercanos al origen (nodo A), nodos cercanos (B y C) determinando la ruta mas corta(A B) con una distancia de 250 kilómetros.
• Se va calculando hasta llegar al punto F usando los nodos mas cercanos C y D. D hasta F = 500+200=700 siendo la mejor ruta y se cansela la ruta EF para evitar el ciclo.

La programación dinámica optimiza redes dividiendo problemas en subproblemas y resolviéndolos recursivamente. Se relaciona con la asignación de recursos y gestión de inventarios. Los elementos clave incluyen etapas, estados y políticas.