Los problemas de redes surgen de una multitud de situaciones que ocurren de manera cotidiana, como lo es la cantidad de energía que se suministra a una casa habiatación por medio de la red eléctrica, el artículo que llega a las manos de alguien en una ciudad distante por medio de la red logística de alguna empresa de paquetería, la red carretera que una las ciudades de un país, etc. Todas estas redes tienen algo en común, invariablemente llevan un flujo, ya sea eléctrico, de bienes, servicios, recursos monetarios, etc, y están estructuradas de tal manera que forman un entramado complejo, el cual es susceptible de ser estudiado mediante la investigación operativa.
Para comprender adecuadamente los modelos de redes, vamos a observar primero como están constituidas, para lo cual, se cita de manera textual, libro Hamdy A. Taha, la siguiente definición de red: “Una red consiste en una serie de nodos enlazados con arcos (ramas)(Taha, 2004).”
Con cada red se asocia algún tipo de flujo (por ejemplo, flujo de productos petroleros en un oleoducto y flujos de tráfico de automóviles en carreteras). En lo general, el flujo en una red está limitado por la capacidad de sus arcos, que pueden ser finitos o infinitos.
Se dice que un arco es dirigido u orientado si permite un flujo positivo en una dirección, y flujo cero en la dirección opuesta. Una red dirigida tiene todos sus arcos dirigidos.
Una ruta es una sucesión de de arcos distintos que unen dos nodos pasando por otros nodos, independientemente de la dirección de flujo en cada arco. Una ruta forma un ciclo si conecta un nodo consigo mismo, pasando por otros nodos. Un ciclo es dirigido si consiste en una ruta dirigida.
Una red conectada es aquella en que cada dos nodos distintos están enlazados al menos por una ruta. Un árbol es una red conectada que puede consistir sólo en un subconjunto de todos los nodos de ella, donde no se permiten ciclos, y un árbol de expansión es un árbol que enlaza todos los nodos de la red, también sin permitir ciclos (Taha, 2004).
Hay una multitud de situaciones, en investigación de operaciones, que se pueden modelar y resolver como redes (nodos conectados por ramas). Algunas publicaciones actuales informan que hasta el 70% de los problemas de programación matemática en el mundo real se pueden representar como modelos relacionados con redes. Algunos ejemplos de esta situación son los siguientes (Taha, 2004):
La solución de estas situaciones y otras parecidas se logra con una variedad de algoritmos de optimización de redes, que para el caso de esta unidad, serán atendidos mediante programación lineal. Dichos modelos son:
Cada uno de estos algoritmos de irán abordando conforme se avance en la unidad.
Para el caso del Algoritmo de la ruta más corta, se determina ésta entre una fuente u origen y un destino o sumidero, en una red conectada. Dependiendo dela información representada en los arcos, el problema puede ser de maximización o minimización.
El modelo matmático en programación lineal entera se presenta a continuación:
\[Min~z={\sum_{i=1}^{n}{\sum_{j=1}^{m}}{C_{ij}}{x_{ij}}}\] \[sujeto~a\] \[flujo~total~que~entra=flujo~total~que~sale\] \[x_{ij}=[0,1]\] La función objetivo genérica se encarga de minimizar la suma de las distancias de los arcos que unen a un nodo de origen con otro de destino, la restricción general que la suma algebraica de los flujos que entran y salen de un nodo debe ser igual a cero, y además, la variables de decisión es binaria, dado que el algoritmo atiende el problema de decidir por cuáles nodos se debe transitar para llegar del origen al destino recorriendo la menor distancia.
El algoritmo de árbol de mínima expansión enlaza los nodos de la red, en forma directa o indirecta, con la mínima longitud de las ramas enlazantes. Una aplicación común de este algoritmo es la construcción de carreteras pavimentadas que unen varias poblaciones. El camino entre dos poblaciones puede pasar por una o más poblaciones adicionales. El diseño más económico del sistema de caminos indica que se minimice la distancia total de caminos pavimentados.
El modelo matemático en programación lineal entera se define como:
\[Min~z={\sum_{i=1}^{n}{\sum_{j=1}^{m}}{C_{ij}}{x_{ij}}}\] \[sujeto~a\] \[{\sum_{i=1}^{n}}{\sum_{j=1}^{m}}{x_{ij}}={n-1}\] \[x_{ij}=[0,1]\] Donde \(n\) corresponde al número de nodos de la red; en el caso de la variable de decisión, como en el algoritmo anterior, se considera una variable binaria, dado que el objetivo del proceso es decidir cuáles arcos deben seleccionarse para conectar toda la red.
En el algoritmo del flujo máximo, el objetivo es llevar a la red a su máxima utilización, maximizando los flujos que pasan por los arcos. Imagine una red de oleoductos que transportan crudo desde los pozos hasta las refinerías. En las distancias intermedias adecuadas están instaladas estaciones de bombeo, para mover el crudo por la red. Cada segmento de tubo tiene un flujo (o capacidad) máxima de crudo. Un segmento de tubo puede ser uni o bidireccional, dependiendo de su diseño. Un segmento unidireccional tiene una capacidad finita en una dirección, y capacidad cero en la dirección opuesta.
La solución del problema propuesto requiere convertir la red en una que tenga una sola fuente u origen y un solo destino o sumidero.
El modelo matemático en programación lineal requiere maximizar el flujo que circula por cada uno de los arcos, quedando definido de la siguiente manera:
\[Max~z=F\] \[s.a.\] \[flujo~que~entra=flujo~que~sale\] \[l_{ij}{\leq}x_{ij}{\leq}{u_{ij}}\] \[x_{ij}>=0~{\forall}i=1,...,n~{\forall}~j=1,...,m\]
Donde \(F\) corresponde al flujo, ya sea en la fuente o el sumidero, \(l_{ij}\) corresponde al limite inferior de capacidad del arco \(x_{ij}\) y \(u_{ij}\) correponde al límite superior de capacidad del mismo arco.
El problema de flujo capacitado con costo mínimo se basa en las hipótesis siguientes:
El nuevo modelo determina los flujos en los distintos arcos, que minimizan el costo total y a la vez satisfacen las restricciones de flujo y las cantidades de oferta y demanda en los nodos. El modelo matemático que representa esta red se define como:
\[Min~z={\sum_{i=1}^{n}}{\sum_{j=1}^{m}}{c_{ij}}{x_{ij}}\] \[flujo~que~entra-flujo~que~sale=f_i, {\forall}~j{\in}N\] \[l_{ij}{\leq}x_{ij}{\leq}{u_{ij}}\] \[x_{ij}>=0~{\forall}i=1,...,n~{\forall}~j=1,...,m\] Donde \(l_{ij}\) corresponde al limite inferior de capacidad del arco \(x_{ij}\) y \(u_{ij}\) correponde al límite superior de capacidad del mismo arco.