Source: http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/teor%C3%ADa-de-redes/
Timestamp: 2014-04-24 18:40:46+00:00

Document:
Teoría de Redes - Ingenieros Industriales
TEORÍA DE REDES La modelación de redes permite la resolución de múltiples problemas de programación matemática mediante la implementación de algoritmos especiales creados para tal fin, conocidos
como Algoritmos de optimización de redes. Dentro de los problemas más comúnmente resueltos mediante la modelación de redes se encuentran los ya vistos
modelos de transporte, transbordo además de los muy conocidos modelos de determinación de cronograma de actividades para proyectos como lo son el PERT y el CPM.
CONCEPTOS BÁSICOS EN TEORÍA DE REDES Gráfica: Una gráfica es una serie de puntos llamados nodos que van unidos por unas líneas llamadas ramales o arcos.
Red: Una red es una gráfica que presenta algún tipo de flujo en sus ramales. Por ejemplo una gráfica cuyo flujo en sus ramales sea la electricidad es una red eléctrica. En las
redes se usa una simbología específica para denotar su tamaño y elementos que la constituyen, dicha notación es la (N, A) donde N representa el número de nodos que contiene la red y A representa
el número de arcos o ramales.
Cadena: Una cadena corresponde a una serie de elementos ramales que van de un nodo a otro. En el siguiente caso se resalta una cadena que va desde el nodo 1 hasta el nodo 7
y que se compone por los elementos [1-4, 4-7].
ALGORITMO DEL ÁRBOL DE EXPANSIÓN MÍNIMA El algoritmo del árbol de expansión mínima es un modelo de optimización de redes que consiste en enlazar todos los nodos de la red de forma directa y/o indirecta con el objetivo de que la
longitud total de los arcos o ramales sea mínima (entiéndase por longitud del arco una cantidad variable según el contexto operacional de minimización, y que puede bien representar una distancia
o unidad de medida).
Definir los conjuntos C0 = {ø} y Č0 = {N}, es decir que antes del paso 1 no se han enlazado de forma permanente nodo alguno, y por ende el conjunto que representa a los
nodos que hacen falta por enlazarse de forma permanente es igual a la cantidad de nodos que existen en la red.
Se debe de escoger de manera arbitraria un nodo en el conjunto Č0 llamado i el cual será el primer nodo permanente, a continuación se debe de actualizar el conjunto
C1 = {i}, que significa que al tiempo en que el conjunto C1 gana el elemento i el conjunto Č0 pierde el elemento i por ende ahora será
igual a Č1 = N - {i}, además se debe actualizar el subíndice de los conjuntos k, el cual ahora será igual a 2.
Se debe de seleccionar un nodo j del conjunto ČK-1 ("k-1" es el subíndice que indica que se está haciendo referencia al conjunto de la iteración inmediatamente anterior)
el cual tenga el arco o ramal con menor longitud con uno de los nodos que se encuentran en el conjunto de nodos de enlace permanente CK-1. Una vez seleccionado se debe de enlazar de
forma permanente lo cual representa que pasa a formar parte del conjunto de enlaces permanentes y deja de formar parte del conjunto que todavía se debe conectar para lograr la expansión. Al
actualizar el algoritmo en este paso los conjuntos deben de quedar de la siguiente forma.
El paso general que define k que al mismo tiempo representa a las iteraciones debe de ejecutarse toda vez que el conjunto ČK no sea vacío, cuando este conjunto sea
igual a vacío se tendrá el árbol de expansión mínima.
La ciudad de Cali cuenta con un nuevo plan parcial de vivienda el cual contará con la urbanización de más de 7 proyectos habitacionales que se ubicarán a las afueras de la ciudad. Dado que el
terreno en el que se construirá no se encontraba hasta ahora dentro de las zonas urbanizables de la ciudad, el acueducto municipal no cuenta con la infraestructura necesaria para satisfacer las
necesidades de servicios públicos en materia de suministro de agua. Cada uno de los proyectos de vivienda inició la construcción de un nodo de acueducto madre, el cual cuenta con las conexiones
de las unidades de vivienda propias de cada proyecto (es decir que cada nodo madre solo necesita estar conectado con un ducto madre del acueducto municipal para contar con su suministro). El
acueducto municipal al ver la situación del plan parcial debe de realizar las obras correspondientes a la instalación de ductos madres que enlacen todos los nodos del plan con el nodo Meléndez
(nodo que se encuentra con suministro de agua y que no pertenece al plan parcial de vivienda, además es el más cercano al mismo), la instalación de los ductos implica obras de excavación, mano de
obra y costos de los ductos mismos, por lo cual optimizar la longitud total de los enlaces es fundamental. Las distancias existentes (dadas en kilómetros) correspondientes a las rutas factibles
capaces de enlazar los nodos del plan parcial se presentan a continuación. Además la capacidad de bombeo del nodo Meléndez es más que suficiente para satisfacer las necesidades de presión que
necesita la red madre.
Problema planteado por, Bryan Antonio Salazar López
El acueducto municipal le contacta a usted para que mediante sus conocimientos en teoría de redes construya una red de expansión que minimice la longitud total de ductos y que enlace todos los
nodos del plan parcial de vivienda.
Se definen los conjuntos iniciales C0 = {ø} que corresponde al conjunto de nodos enlazados de forma permanente en la iteración indicada en el subíndice y Č0 = {N =
1,2,3,4,5,6,7,8} que corresponde al conjunto de nodos pendientes por enlazar de manera permanente en la iteración indicada en el subíndice.
Se debe definir de manera arbitraria el primer nodo permanente del conjunto Č0, en este caso escogeremos el nodo 1 (puede ser cualquier otro), que algebraicamente se representa
con la letra i, se procede a actualizar los conjuntos iniciales, por ende C1 = {i} = {1} y Č0 = {N - i} = {2,3,4,5,6,7,8}, actualizamos k por ende ahora
será igual a 2.
Ahora se debe seleccionar el nodo j del conjunto ČK-1 (es decir del conjunto del paso 1) el cual presente el arco con la menor longitud y que se encuentre enlazado con uno de
los nodos de enlace permanente del conjunto Ck-1 en el cual ahora solo se encuentra el nodo 1 (es decir que se debe de encontrar un nodo que tenga el arco de menor longitud
enlazado al nodo 1).
Los arcos o ramales de color naranja representan los arcos que enlazan el conjunto ČK-1 (es decir del conjunto del paso 1, recordemos que K en este paso es igual a 2, por
ende ČK-1= Č1) con los nodos de enlace permanente del conjunto Ck-1 en el cual ahora solo se encuentra el nodo 1, por ende ahora solo falta escoger el de
menor longitud, que en este caso es el arco cuya longitud es 2, que enlaza de forma permanente ahora el nodo 2.
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración. Ahora se seleccionará un nuevo nodo j del conjunto Č2que presente el
enlace (ramal o arco) de menor longitud con los nodos que se encuentran en el conjunto C2.
Los arcos de color naranja representan los enlaces posibles y dado que existe empate entre las menores longitudes se elige de manera arbitraria, en este caso se representa nuestra elección con un
arco de color verde, enlazando de forma permanente ahora el nodo 4.
Lo que representan los arcos naranja y verde es ya conocido, ahora la línea azul interrumpida irá trazando nuestro árbol de expansión final. Dado a que el arco menor es el de longitud 3, ahora se
enlazará de manera permanente el nodo 5.
Como hemos mencionado en módulos anteriores la existencia de herramientas de resolución de problemas de programación matemática como WinQSB dejan que el aprendizaje de la resolución manual de los
algoritmos de redes se justifique solo para fines académicos o de profundización. Por ende una vez vista la metodología manual de resolución del algoritmo atinente al árbol de expansión mínima se
hace necesario en aras de eficiencia mostrar la resolución de este tipo de problemas mediante WinQSB.
Problema planteado por Bryan Antonio Salazar López
WinQSB - Bryan Antonio Salazar López
Luego debemos seleccionar la opción Minimal Spanning Tree (Árbol de Expansión Mínima). Además en este submenú debemos de especificar el nombre del problema y el número de nodos. En
nuestro caso el número de nodos es igual a 8, luego click en OK.
En esta matriz se deben de consignar los valores de los ramales que unen las conexiones entre los nodos correspondientes, según el contexto de nuestro problema se deben de consignar las
distancias entre los nodos si es que dichas conexiones existen de lo contrario en caso que la conexión no exista se debe dejar la celda en blanco. Hay que tener en cuenta que las distancias entre
los nodos en este caso son exactamente conmutativas, es decir que si el nodo fuente es 2 y el destino es 4 la distancia existente entre estos es exactamente igual a la distancia existente entre
un nodo fuente 4 y un nodo destino 2, sin embargo esta propiedad debe de especificarse en la matriz consignando los valores correspondientes a una conexión dos veces, es decir en la celda [From 1
- To 4] se debe de consignar la distancia 6, además debe de consignarse la misma distancia en la celda [From 4 - To 1].
ALGORITMO DE LA RUTA MÁS CORTA El nombre que distingue este conjunto de problemas de por sí es bastante sugestivo, existen de forma manual algoritmos capaces de resolver tanto problemas de redes que presentan ciclos como de
redes que no, entre los más conocidos se encuentran los algoritmos de Dijkstra y Floyd siendo el segundo más general que el primero. Sin embargo la complejidad de los algoritmos, en la práctica
la complejidad que alcanzan las redes a ser resueltas mediante el algoritmo de la ruta más corta, y las herramientas de resolución de problemas de programación matemática hacen que la enseñanza
de dichos algoritmos manuales sea muy ineficiente.
Ya en un módulo anterior Problema de Transbordo se ha planteado la resolución del algoritmo de la ruta más corta mediante programación lineal, por esta razón
en este espacio nos enfocaremos en efectuar la solución mediante WinQSB con la facilidad que caracteriza al software.
El módulo del WinQSB que permite la resolución del algoritmo de la ruta más corta es el Network Modeling, el cual utiliza una interfaz muy sencilla en forma de matriz en la cual hay que ingresar
el valor de los ramales (dependiendo del contexto este valor puede representar distancias, tiempo, costos etc...) correspondiente a cada relación de un nodo con otro.
Un minero ha quedado atrapado en una mina, la entrada a la mina se encuentra ubicada en el nodo 1, se conoce de antemano que el minero permanece atrapado en el nodo 9, para llegar a dicho nodo
hay que atravesar una red de túneles que van conectados entre sí. El tiempo de vida que le queda al minero sin recibir auxilio es cada vez menor y se hace indispensable hallar la ruta de acceso
al nodo 9 más corta. Las distancias entre nodos de la mina se encuentran en la siguiente gráfica dadas en cientos de metros. Resuelva mediante cualquier paquete de herramientas de investigación
operativa que permita establecer la ruta más corta para poder así auxiliar al minero.
Primero se debe ingresar al módulo Network Modeling del paquete WinQSB, una vez nos encontremos en este aparecerá el menú que se muestra en la siguiente gráfica, menú en el cual tendremos que
seleccionar la opción Shortest Path Problem (Problema de la ruta más corta).
Además en este menú emergente debemos de ingresar la cantidad de nodos que conforman la red del problema y tenemos la posibilidad de asignarle un nombre al mismo, en nuestro caso la cantidad de
nodos de la red es igual a 9; click en OK y aparecerá la siguiente ventana.
Una vez efectuada la selección tendremos la opción de ver el tabulado final y la opción de ver un paso a paso gráfico; para el tabulado final click en SOLVE y para el paso a paso click en SOLVE
AND DISPLAY STEPS.
Podemos cotejar la solución que obtuvimos al plantear este problema como un modelo de transbordo con esta solución. La eficiencia se encuentra determinada en escoger la herramienta adecuada para
resolver el problema planteado.

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución