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
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.
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEilBdctBzSLMtZZhnNkF7Q2-nlgQ3g5fK94aKTx1-JWUGIq8xdCofzFgGjQoCdx5U4g9RqQJiP_4HpYro1qhaj7IJeGRvtsTBOwxNztgjtfGhtFdWB2ABcQrx4Fd_aKdCb8Q3e9Afzdz9A/s1600/b.bmp)
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.
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. |