Modelo de red (investigación de operaciones)

Modelos de red (en la Investigación de operaciones; en inglés: Network models) son una clase de modelos matemáticos que representan un problema en forma de un grafo (red), donde los vértices (nodos) denotan objetos o estados, y las aristas (arcos) representan las conexiones o procesos entre ellos. En el contexto de la optimización, una red a menudo se entiende como un grafo dirigido, que en el análisis de operaciones se llama directamente «red»; los vértices de tal red se denominan nodos y las aristas, arcos.

Los modelos de red son una herramienta poderosa para el análisis y la optimización de sistemas complejos en áreas como la logística, las telecomunicaciones, la gestión de proyectos y las finanzas. Su fortaleza radica en su alto nivel de abstracción: un nodo puede representar una ciudad, un enrutador de computadora o una etapa de un proyecto, mientras que un arco puede representar una carretera, un canal de comunicación o una operación tecnológica.

Definición y terminología

La base de los modelos de red es la teoría de grafos. Los conceptos clave son:

• Red de flujo (en inglés: flow network): un grafo dirigido en el que cada arista tiene una capacidad (capacity) y un flujo (flow). En el grafo se distinguen dos vértices especiales: una fuente (source), de donde emana el flujo, y un sumidero (sink), a donde llega.
• Ley de conservación del flujo: Para cualquier vértice que no sea ni la fuente ni el sumidero, el flujo total entrante debe ser igual al flujo total saliente. Esta condición es un análogo discreto de las leyes físicas de conservación.
• Planificación de redes: Un modelo que representa un proyecto como un conjunto de operaciones (arcos) y eventos (nodos) interconectados. Estas redes son grafos dirigidos acíclicos, lo que refleja el orden de ejecución de las tareas.

Propiedades y teoremas clave

Los modelos de red poseen una serie de propiedades especiales que permiten aplicar algoritmos altamente eficientes para su solución.

• Soluciones enteras: Muchos problemas de optimización de redes (por ejemplo, el flujo máximo o el camino más corto) poseen la propiedad de unimodularidad total en su matriz de restricciones. Gracias a esto, si los parámetros del problema (capacidades, longitudes) son enteros, la solución óptima encontrada mediante métodos de Programación lineal, también será entera sin necesidad de introducir restricciones adicionales.
• Teorema de flujo máximo y corte mínimo: El resultado central de la teoría de flujos. Afirma que el valor máximo del flujo desde la fuente hasta el sumidero es igual a la capacidad mínima de todos los cortes que separan la fuente y el sumidero. Este teorema establece un criterio de optimalidad para el flujo y es la base de muchos algoritmos.
• Principio de optimalidad para caminos más cortos: Si un camino desde el punto A hasta el punto C es el más corto, entonces cualquier subcamino de este (por ejemplo, desde un punto intermedio B hasta C) también es el camino más corto entre los vértices correspondientes. Esta propiedad, que es la base de la Programación dinámica, asegura la corrección de algoritmos como el de Dijkstra.
• Propiedades del árbol de expansión mínimo (AEM):
• Propiedad del corte: Para cualquier corte del grafo, la arista de peso mínimo que cruza el corte pertenece al menos a un AEM.
• Propiedad del ciclo: En cualquier ciclo del grafo, la arista de peso máximo no pertenece a ningún AEM.

En estas propiedades se basa la corrección de los algoritmos «voraces» de Prim y Kruskal.

Problemas principales de optimización de redes

• Problema del camino más corto: Encontrar un camino de longitud (o peso) total mínimo entre dos nodos dados. Se resuelve con el algoritmo de Dijkstra (para pesos no negativos) o el algoritmo de Bellman-Ford (para pesos arbitrarios).
• Problema del flujo máximo: Determinar el flujo máximo posible desde la fuente hasta el sumidero, dadas las capacidades de los arcos. El método clásico de solución es el algoritmo de Ford-Fulkerson.
• Problema del árbol de expansión mínimo: Encontrar un subgrafo que conecte todos los vértices de la red y tenga el costo total mínimo de las aristas.
• Método de la ruta crítica (CPM): En los modelos de planificación de redes, determinar la secuencia más larga de tareas que establece el tiempo mínimo posible para completar todo el proyecto. Las tareas en esta ruta tienen una holgura de tiempo cero.

Ejemplos

• Camino más corto: Búsqueda de la ruta óptima por un sistema de navegación entre dos puntos en un mapa, donde las ciudades son nodos y las carreteras son arcos con pesos iguales a la longitud o al tiempo de viaje.
• Flujo máximo: Determinación de la capacidad máxima de una red de tuberías, donde las estaciones de bombeo son los nodos y las tuberías son los arcos con capacidad limitada.
• Árbol de expansión mínimo: Diseño de una red de comunicaciones (por ejemplo, tendido de cable de fibra óptica) para conectar varias ciudades con la longitud total mínima de cable.
• Ruta crítica: En un proyecto de construcción de una casa, donde las tareas (cimentación, levantamiento de paredes, instalación del techo) tienen una duración y dependencias tecnológicas dadas, la ruta crítica determina el tiempo mínimo de finalización de la construcción. Cualquier retraso en una tarea de esta ruta provocará un retraso en todo el proyecto.

Véase también

• Investigación de operaciones
• Teoría de grafos
• Problema del transporte
• Método de la ruta crítica
• PERT