Investigación
Operativa
Sesión N°21: Modelo de Redes
Prof. Vania Quezada L.
Ejercicio Desafío
Una empresa está considerando satisfacer las necesidades de 4 clientes empleando
los artículos que tiene disponibles en 3 almacenes. La cantidad de artículos que tiene
en cada almacén son 10, 40 y 20 unidades respectivamente. Los clientes necesitan
12, 15, 30 y 20 unidades respectivamente. El costo unitario de embarque desde los
almacenes hasta el cliente se encuentran en la siguiente tabla:
Solución Desafío
MÉTODO ESQUINA NOROESTE
1 2 3 4
1 27 45 37 30 10
10
2 2 29 15 40 23 36 28
40
3 31 28 7 50 40
13 20
4 0 0 0 0
7 7
12 15 30 20
Solución Desafío
MÉTODO COSTO MINIMO
1 2 3 4
1 10 27 45 37 30 10
2 29 40 36 28
2 18 20 40
3 31 15 28 50 40
5 20
4 0 0 0 0
7 7
12 15 30 20
Solución Desafío
MÉTODO APROXIMACIÓN DE VOGEL
1 2 3 4
1 27 45 37 30 10 30-27=3 30-27=3 30-27=3 30-27=3
7 3
2 29 40 23 36 28 29-28=1 29-28=1 29-28=1
17 40 29-28=1
3 31 28 50 40
5 15 20 31-28=3 40-31=9
4 0 0 0 0
7 7 0 0 0 0
12 15 30 20
29-27=2 40-28=12 37-36=1 30-28=2
29-27=2 37-36=1 30-28=2
29-27=2 37-36=1 30-28=2
37-36=1 30-28=2
Definiciones de red
Una red se compone de un conjunto de NODOS unidos por ARCOS (o ramas). La
notación para describir una red es (N,A) donde N es el conjunto de nodos y A es el
conjunto de arcos.
• Asociado con cada red hay un flujo (por ejemplo, los productos de petróleo
fluyen por un oleoducto y el tráfico de automóviles fluye por las
carreteras).
• El flujo máximo en una red puede ser finito o infinito, según la capacidad
de sus arcos.
• Se dice que un arco está dirigido u orientado si permite el flujo positivo
sólo en una dirección.
• Una red dirigida tiene todos los arcos dirigidos. Una ruta es un conjunto de
arcos que unen dos nodos distintos, y que pasan a través de otros nodos
en la red.
• Se dice que una red está conectada si cada dos nodos distintos están
conectados en al menos una ruta.
• Un árbol es una red conectada libre de ciclos compuesta de un
subconjunto de todos los nodos, y un árbol de expansión es un árbol que
une todos los nodos de la red.
Modelo de redes
red
Algoritmo del árbol de
mínima expansión
● Este árbol vincula los nodos de una red valiéndose de la longitud mínima
total de las ramas de conexión. Una aplicación común se presenta en la
pavimentación de carreteras que unen poblaciones, o de forma directa, o
que pasan por otras poblaciones. La solución del árbol de mínima
expansión proporciona el diseño del sistema de carreteras.
Pasos del algoritmo del árbol de mínima
expansión
Los siguientes pasos describen al algoritmo del árbol de mínima expansión:
Paso 0. Establezca
Paso 1.
En resumen:
Suponga que cada arco (i,j) en una red tiene una longitud asociada y que el arco (i,j)
representa una forma de conectar el nodo i al nodo j. Por ejemplo, si cada nodo de una red
representa una computadora, entonces el arco (i,j) podría representar un cable que
conecta la computadora i con la computadora j. En muchas aplicaciones, se desea
determinar el conjunto de arcos de una red que conecta los nodos tal que se minimiza la
suma de la longitud de los arcos.
EJEMPLOS DE APLICACIÓN
✓ Determinación de la ruta más corta entre dos ciudades en una red
existente de carreteras.
✓ Determinación del cronograma (fechas de inicio y terminación) para
las actividades de un proyecto de construcción.
✓ Determinación del itinerario de flujo de costo mínimo desde campos
petroleros hasta refinerías a través de una red de oleoductos
Ejemplo 1:
En el campus Saucache de la UTA, se tienen 5 microcomputadores. La distancia
entre cada par de computadoras (en cuadras) se muestra en la red. Las
computadoras deben estar conectadas mediante un cable subterráneo. ¿Cuál es
la longitud mínima de cable requerido?
1
1 2
4 2
2 3
2
5 3
4
5
4
1
Ejemplo 1: 1 2
Iteración 1:
1
𝐶 = 1,2
𝐶ҧ = 3,4,5 1 2
El arco (1,2) será el árbol
de expansión mínima 4 2
2 3
6
2
5
3
4
5
4
1
Ejemplo 1: 1 2
2
Iteración 2 :
5
𝐶 = 1,2,5 1
𝐶ҧ = 3,4 1 2
El arco (2,5) se incluye en el árbol
de expansión mínima 4 2
2
6 3
5
2
4
3
4
1
Ejemplo 1: 1 2
Iteración 3 :
5
1 2
𝐶 = 1,2,5,3
𝐶ҧ = 4 1 2
3
El arco (5,3) se incluye en el árbol
de expansión mínima 4 2
2
6 3
5
2
4
3
4
1
Ejemplo 1: 1 2
Iteración 4 :
1 5
El nodo 5 es el más próximo 2
1 2
al nodo 4 así que se agrega el 4
arco (5,4) al árbol de 3
4 2
expansión mínima.
4
2
6 3
La longitud del árbol de expansión mínima es
1+2+2+4 = 9 cuadras
5
2
4
3
4
Desafío
Midwest TV Cable Company va a proporcionar servicio de cable a cinco desarrollos
habitacionales. La figura ilustra las posibles conexiones de TV a las cinco áreas, con las
millas de cable anexadas a cada arco. El objetivo es determinar la red de cables más
económica. El algoritmo se inicia en el nodo 1 (en realidad, cualquier otro nodo puede ser un
punto de inicio), el cual da por resultado.
Ejemplo 2:
