UNIDAD I: Análisis de Redes

Análisis de Redes

Los problemas de redes surgen en una gran variedad de situaciones. Las redes de transporte, eléctricas y de comunicaciones predominan en la vida diaria. La representación de redes se utiliza ampliamente en áreas tan diversas como producción, distribución, planeación de proyectos, localización de instalaciones, administración de recursos y planeación financiera, para nombrar sólo unos ejemplos. De hecho, una representación de redes proporciona un panorama general tan poderoso y una ayuda conceptual para visualizar las relaciones entre los componentes del sistema, que se usa casi en todas las áreas científicas, sociales y económicas.

Problema del Camino Mas Corto

El problema de la ruta más corta incluye un juego de nodos conectados donde sólo un nodo es considerado como el origen y sólo un nodo es considerado como el nodo destino. El objetivo es determinar un camino de conexiones que minimizan la distancia total del origen al destino.

Se trata de encontrar la ruta de menor distancia, o costo, a entre el punto de partida o nodo inicial y el destino o nodo final.

Se aplica mucho para problemas de redes de comunicaciones.

Este tipo de problemas pueden ser resueltos por el método del Simplex, sin embargo existen otros métodos más eficientes como por ejemplo el algoritmo de Dijkstra o el de Bellman-Ford.

Algoritmo de Dijkstra 

Pasos a seguir

1.     Elaborar un cuadro con todos los nodos y los ramales que salen de él.

2.     Partiendo del origen, debemos encontrar el nodo más cercano a él.

3.     Anular todos los ramales que entren al nodo más cercano elegido.

4.     Comenzando en el origen se debe encontrar el nodo más cercano a él, por intermedio del nodo(s) ya elegido(s) y volver al tercer paso hasta llegar al destino.

Ejemplo: La administración de Seervada Park necesita determinar los caminos bajo los cuales se deben tender las comunicaciones para conectar todas las estaciones con una longitud total mínima de cable. Dada la red indicada en el paso a, se selecciona O como nodo inicial.Encontrar la ruta mas corta entre O y T, los números sobre los arcos se miden en millas.

Problema de Flujo Máximo

En términos generales, el problema de flujo máximo se puede describir de la siguiente manera:

1.     Todo flujo a través de una red conexa dirigida se origina en un nodo, llamado fuente, y termina en otro nodo llamado destino.

2.     Los nodos restantes son los nodos de trasbordo

3.     Se permite el flujo a través de un arco solo en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dada por la capacidad del arco. En la fuente, todos los arcos señalan hacia afuera. En el destino, todos señalan hacia el nodo.

4.     El objetivo es maximizar la cantidad total de flujo de la fuente al destino. Esta cantidad se mide en cualquiera de las dos maneras equivalentes, esto es, la cantidad que sale de la fuente o la cantidad que entra al destino.

Ejemplo: En la siguiente red determine el flujo máximo

El origen puede despachar 28 unidades y el destino puede recibir 22 unidades, pero por las restricciones, el destino solo puede recibir 19 unidades en la ruta AB- BC – CD – DF – FG.

Problema del Árbol de Expansión Mínima

El árbol de expansión mínima se refiere a utilizar las ramas o arcos de la red para llegar a todos los nodos de la red, de manera tal que se minimiza la longitud total.

Árbol de máximo alcance cuyo valor es mínimo, es decir, la suma de aristas es mínima.

Si n = número de nodos, entonces la solución óptima debe incluir n-1 arcos.

Algoritmo de Kruskal

Nos permite hallar el árbol mínimo de cualquier grafo valorado. 

Pasos a seguir

1.       Se marca la arista con menor valor. Si hay más de una se elige cualquiera de ellas.

2.       De las aristas restantes, se marca la que tenga menor valor, si hay más de una se elige cualquiera de ellas.

3.       Repetir el paso anterior siempre que la arista elegida no forme un ciclo con las ya marcadas.

4.       El proceso termina cuando tenemos todos los nodos del grafo en alguna de las aristas marcadas, es decir, cuando tenemos marcados n-1 arcos, siendo n el número de nodos del grafo.

Ejemplo 1: 

Ejemplo 2: 

1.     Tenemos un grafo como observamos las aristas son los conectores entre dos vértices o nodos ( bolitas de color ámbar y están enumeradas del 1 al 8) estas contienen un peso. luego elegimos la arista con menor peso (marcada de rojo)

2.     A este proceso de aristas se le suma el siguiente arista que sea menor(obviamente diferente al que habíamos elegido) con peso en este caso 29

3.     Elegimos a otra que tenga el menor peso (en este caso 31)

4.     Nos ubicamos el los vértices 2 y 8 , si en la arista que los conecta hubiera 32 como peso no se debe elegir ya que  debe ser un árbol que es un grafo no cíclico (no forma un ciclo o una cerradura de vértices). por lo tanto y en este ejemplo el 32 esta en el vértice 2 y 5.

5.     Seguimos tomando las aristas y que no formen un ciclo, estas tratan de conectar todos los vértices

6.     En este punto del proceso vemos que como caso especial que habíamos visto, no tomamos la arista de los vértices 2 y 3, pues formaría un ciclo

7.     Finalmente se han unido los vertices, sin formar un cilco en las aristas

Algoritmo de Prim

Pasos a seguir

Nos permite hallar el árbol minimal de cualquier grafo valorado (con capacidades).

1.     Se marca un nodo cualquiera, será el nodo de partida.

2.     Seleccionamos la arista de menor valor incidente en el nodo marcado anteriormente y marcamos el otro nodo en el que incide.

3.     Repetir el anterior paso siempre que la arista elegida enlace un nodo marcado y otro que no lo esté.

4.      El proceso termina cuando tenemos todos los nodos del grafo marcados.

Ejemplo:Determinar el árbol de mínima expansión para el siguiente grafo:

Siguiendo el algoritmo de Prim, tenemos:

1.     Elegimos, por ejemplo, el nodo 1 y lo marcamos.

2.     Elegimos la arista con menor valor incidente en 1, la (1, 3) = 1 la marcamos y marcamos el otro nodo en el que incide, el 3.

3.     Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (1, 2) = 3 la marcamos y marcamos el nodo no marcado, el 2.

4.     Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (2, 5) = 5 la marcamos y marcamos el nodo no marcado, el 5.

5.     Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 6) = 1 la marcamos y marcamos el nodo no marcado, el 6.

6.     Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 7) = 2 la marcamos y marcamos el nodo no marcado, el 7.

7.     Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 4) = 6 la marcamos y marcamos el nodo no marcado, el 4.

8.     FIN. Finalizamos dado que tenemos marcados los 7 nodos del grafo.

Por tanto el árbol de mínima expansión resultante sería:

Ruta Crítica 

(PERT-CPM)

El método PERT (Program Evaluation and Review Technique) desarrollado por la armada de los Estados Unidos de América en 1957, para controlar los tiempos de ejecución de las diversas actividades integrantes de los proyectos espaciales, por la necesidad de terminar cada una de ellas dentro de los intervalos de tiempo disponibles. Fue utilizado originalmente por el control de tiempos del proyecto Polaris.

El Método CPM (Critical Path Method), el segundo origen del método actual fue desarrollado también en 1957 en los Estados Unidos de América, por un centro de investigación de operaciones para las firmas Dupont y Remington Rand, buscando el control y la optimización los costos mediante la planeación y programación adecuadas de las actividades componentes del proyecto. Ambos métodos aportaron los elementos administrativos necesarios para formar el método de ruta crítica actual, utilizando el control de los tiempos de ejecución y los costos de operación, para buscar que el proyecto total sea ejecutado en el menor tiempo y al menor costo posible. 

El método de Ruta Crítica es un proceso administrativo (planeación, organización, dirección y control) de todas y cada una de las actividades componentes de un proyecto que debe desarrollarse durante un tiempo crítico y al costo óptimo.

Por ejemplo iniciamos con la revisión de izquierda a derecha (hacia adelante) y se prosigue a los nodos siguientes.

Si concurren en un evento dos o más flechas, 
se toma la mayor como representativa. 

Ahora prosigue el cálculo en sentido contrario de derecha a izquierda (hacia atrás). Cuando de un evento parten varias cadenas de actividades o flechas,  se tomará la menor como representativa. La ruta crítica se encuentra como aquella ruta para la cual todas sus  actividades tienen holgura igual a cero.Generalmente se marca en la red la ruta crítica. En este caso la Ruta Critica es: Inicio – A – C – E – Fin