Optimización de Redes y Logística: Conceptos y Problemas Clave

Conceptos y Problemas Clave en la Optimización de Redes y Logística

PERT/CPM

¿Qué significa que una actividad tenga una holgura total (MTIJ) igual a 0?

Significa que cualquier retraso en esa actividad produce un retraso en las actividades posteriores. Sin embargo, esto no implica necesariamente un retraso en el proyecto global, ya que podría haber otras actividades con holgura libre (MLIJ) distinta de cero.

¿Qué es el camino crítico?

Es el camino más largo a través de la red del proyecto y determina la duración mínima necesaria para completarlo. Las actividades que componen el camino crítico se denominan actividades críticas.

¿Qué ocurre cuando la duración de las actividades no se conoce con certeza?

Se realizan tres estimaciones: optimista (a_ij), realista (m_ij) y pesimista (b_ij). Se asume que la duración de las actividades sigue una distribución beta. Además, se supone que los tiempos de las actividades (t_ij) son variables aleatorias independientes. Por el Teorema Central del Límite (TCL), el tiempo total del proyecto sigue una distribución normal, donde:

• T = Σ t_ij críticas (sumatorio de los tiempos de las actividades críticas)
• V(T) = Σ v_ij críticas (sumatorio de las varianzas de las actividades críticas)

Formulación de un PERT

• Minimizar Z = Σ T_i (para i desde 1 hasta n), donde T_i representa el tiempo de inicio del evento i.
• Sujeto a:
  • T_j - T_i ≥ t_ij
  • T_ij ≥ 0

Teoría de Grafos

Nodo

Un nodo es un punto de intersección en un grafo. Se identifica con un número.

Arco

Un arco es la unión entre dos nodos. Se identifica con dos números. Se llama orientado si tiene una dirección determinada. Si todos los arcos están orientados, se habla de una red orientada.

Capacidad de un arco

Es la máxima cantidad de flujo que puede circular por un arco orientado.

¿Cuándo se dice que dos nodos están conectados?

Cuando están unidos mediante un arco no orientado.

Cadena, ruta y ciclo

• Cadena: Conjunto de arcos sucesivos en el que cada arco tiene un nodo en común con el anterior.
• Ruta: Cadena con dirección.
• Ciclo: Ruta que empieza y acaba en el mismo nodo.

Problemas Clásicos en Redes

Problema del camino más corto

Consiste en determinar la ruta más corta entre un origen y un destino conectados por una red con distancias asignadas a cada arco. Se resuelve mediante el algoritmo de Dijkstra.

Problema del árbol de expansión mínima

Consiste en conectar todos los nodos de una red de manera que la distancia total de los arcos que los conectan sea mínima. Un árbol es una expansión de una red de n nodos, y es el conjunto de n-1 arcos.

Problema de flujo máximo

Consiste en transportar la máxima cantidad de flujo posible a través de un punto de partida (fuente) a uno de destino. Consta de los siguientes elementos:

• Fuente y destino
• Arcos con capacidad limitada de flujo
• El objetivo es transportar el máximo flujo posible

Condiciones para que un flujo sea factible

• El flujo por un arco no puede ser negativo ni superar la capacidad del arco.
• El flujo que entra en un nodo i debe ser igual al flujo que sale de i (conservación del flujo).

Logística

Función logística

Es una función que tiene por objetivo proporcionar bienes y servicios donde son demandados, en el momento oportuno y en las condiciones adecuadas. En logística, es importante el diseño de rutas y el dimensionamiento de flotas.

Problema del viajante (TSP)

Consiste en diseñar una ruta cuyo origen y destino coinciden y que pase por todos los puntos requeridos de manera que la distancia total sea mínima.

Programación Entera (PE)

Características del modelo de Programación Entera

• Función objetivo lineal.
• Restricciones lineales.
• Condiciones de no negatividad.
• Algunas de las variables deben ser enteras.

¿Por qué no se puede aplicar el método simplex a un problema de Programación Entera?

Porque la región factible es un conjunto de puntos limitados que ya no es un conjunto convexo.

Tipos de Programación Entera

• Pura: Todas las variables deben ser enteras.
• Mixta: Solo algunas variables deben ser enteras.
• Binaria: Las variables solo pueden valer 0 o 1.

Problema de la mochila

Consiste en llenar la capacidad limitada de una entidad (la"mochil") con una serie de objetos que tienen ciertas características y un valor llamado"utilida" que se quiere maximizar en conjunto. Se usan variables binarias para representar la inclusión o no de cada objeto.

Problema de costes fijos

Es un problema que consiste en decidir qué actividades debe llevar a cabo una empresa, teniendo en cuenta que estas llevan asociado un coste fijo y uno variable.

Método para resolver los problemas de Programación Entera

Se utiliza el método de ramificación y acotamiento.

Problema relajado

Es un problema de programación lineal que resulta de prescindir de la condición de que algunas variables sean enteras. Su solución siempre será mejor o igual que la del problema original.