REDES

Investigación Operativa
•Modelo de Redes
Ing. Romina Miccige

Bibliografía
 Taha, H. Investigación de Operaciones. Quinta Edición.
Alfaomega Grupo Editor(2004)
Modelo de Redes
 Una red consiste en un conjunto de
puntos y un conjunto de líneas que
unen ciertos pares de líneas que unen
ciertos pares de puntos.
PUNTOS = NODOS
LINEAS = RAMAS
A B D
C
Modelo de Redes
 En general el flujo de una red esta
limitado por la capacidad de sus ramas,
que pueden ser finitos o infinitos.
 Se dice que un arco esta dirigido u
orientado si permite un flujo positivo en
una dirección y un flujo cero en la
dirección opuesta
A B A B
5 5
A B A B
Modelo de Redes
NODOS ARCOS / RAMAS FLUJO
CIUDADES CAMINOS/RUTAS AUTOS/CAMIONES
AEROPUERTOS LINEAS AÉREAS AVIONES
ESTACIONES DE TUBERIAS FLUIDOS
BOMBEO
CENTROS DE WO / HOJAS DE TRABAJOS
TRABAJOS RUTA DE TRABAJO
PUNTOS DE CABLES/TUBERIAS MENSAJES
COMUNICACIÓN
Modelo de Redes
 Modelo de árbol de extensión mínima.
 Modelo de ruta más corta.
 Modelo de flujo Máximo.
 Modelo de red capacitada de costo mínimo.
 Ford
 Hamilton
 Floyd
Arból de extensión mínima
 Objetivo: Determinar el árbol extenso
que proporciona la suma mínima de
ramas conectadas.
 Consiste en encontrar las conexiones
más “eficientes” entre todos los nodos
de la red
No conectados : (1; 2; 3; 4; 5; 6)
Conectado ()
Conectados : (1)
No conectados : ( 2; 3; 4; 5; 6)
Conectados (1; 2)
No conectados : ( 3; 4; 5; 6)
Conectados (1; 2; 5)
No conectados : ( 3;4; 6)
Conectados (1; 2; 5; 4)
No conectados : ( 3; 6)
Conectados (1; 2; 5; 4; 6)
No conectados : ( 3)
Conectados (1; 2; 5; 4; 6; 3)
Rta: 1+3+5+4+3 =
16 km
Arból de extensión mínima
1+ 3 + 4 + 3 + 5 = 16 Km.
Ruta más corta
 Objetivo:determinar las ramas
conectadas de una red de transporte,
que constituyen, en conjunto, la
distancia más corta entre una fuente y
un destino.
Algoritmo acíclico
Algoritmo cíclico (de Dijkstra)

Ruta más corta
Uj = Distancia más corta entre el nodo 1 y el nodo J
La distancia ui más corta a un nodo

i inmediatamente anterior
Uj = minj +
La distancia dij entre el nodo j y su predecesor i
Ui + dij
U1= 0 por definición, los valores u2, u3, u4, un, se calculan
en forma recursiva
Ruta más corta
Algoritmo acíclico
[2, 1]
[7, 2]
[0, -1] [7, 3]

[13, 5]
[5, 3]
[4, 1]
Ruta más corta
Algoritmo cíclico
[100, 1] [55, 4]
[0, -1]
[40, 3]
[90, 4]
[30, 1]
[90, 3]
FORD
FORD
 Permitecalcular la distancia mínima
que existe entre dos puntos en una red,
y por consiguiente el camino mínimo
que los une.
FORD
7
2 15
13
13
10
7 14
14
4
5
17
7
7 45 17 35
25 34 49
0 25
9 9 29
29
5 20
5 20
1-5-7-8 = 29 KM
Flujo MAXIMO
 Un nodo fuente y Un nodo destino
 Red de ramas de capacidad finita
 La red es unidireccional.
 Una rama puede tener dos capacidades
distintas.
Para ello determinamos caminos de flujo creciente de la fuente origen al
destino, viendo el incremento del flujo neto que aporta cada camino.
El algoritmo terminara cuando no sea posible construir ningún camino
de flujo creciente, en cuyo caso se habrá determinado el flujo máximo.
Comenzamos con un flujo neto xij=0 sobre cada arco dela red y, por
tanto, flujo total F = 0. Definimos kij como la capacidad de cada arco.
Donde xij kij

Flujo MAXIMO Ford Furkelson
3 12 3
6
15 2 5
1 7 9
10 7 63 14 26 23 20 17
18 11
15 3 4 12 9 6 3
6
15
Iteración 1: 1-2-5-6 Max: (15;12;9) = 9
Iteración 2 : 1-2-5-4-6 = Max (6;3;6;26;12)= 3
Iteración 3: 1 -2 -3-5-4-6 = (3;10;6;23;9) = 3
Iteración 4: 1-3-5-4-6= (18; 3;20;6)= 3
Iteración 5: 1-3-6= (15; 15;)= 15 FLUJO MAX = 33
8 4 1
4
6 3 12
4
10 3
0
6 10 7 4
3
S-V1-V3-T MIN(16;12;20) = 12
S-V1-V2-V4-V3-T MIN (4;10;9;8) =4
S-V2-V4-V3-T MIN (13;10;3;4) = 3
S-V2-V4-T MIN (10; 7;4)= 4 Flujo Max = 23
CAMINOS HAMILTONIANOS
 Un camino Hamiltoniano es aquel que
pasa una vez y sólo una por cada nodo
de la red.
 Por ejemplo, el recorrido de un cartero,
micro escolar, etc.
1 2
4
3
 Para la busqueda de caminos
Hamiltonianos aplicamos la
multiplicación latina:
 Si A2=(a,b,c) y B2(c,d,e) = (a,b,c,d,e)
1 2
4
3
ALGORITMO DE FLOYD
 Encuentra la distancias y caminos
mínimos entre todos los posibles pares
de nodos de la red.
El valor de los arcos los denotaremos como Cij que nos indicará el
valor del arco que va del nodo i al nodo j.
Si el arco de i a j no existe Cij es ∞
Formamos una matriz C, cuyos elementos son los Cij y otra matriz
D cuyos elementos son los nodos del grafo.
ALGORITMO DE FLOYD
 Pasos a dar:
 Formamos las matrices C y D.
 Se selecciona la fila 1 y la columna 1 de C
Para todo i, j ≠ 1
Cij = min [Cij, (Ci1 + C1j)]
Si (Ci1 + C1j) ˂ Cij entonces dij = d1j
 Reiteramos el proceso anterior seleccionando la fila K y la
columna K
 Terminamos el algoritmo cuando k coincide con el número de
nodos del gráfo
ALGORITMO DE FLOYD
1 1 2
7
8 6
3
5
3 4
2

REDES

Cargado por

Copyright:

Formatos disponibles

REDES

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

REDES

Cargado por

Copyright:

Formatos disponibles

Investigación Operativa

Ing. Romina Miccige

Algoritmo cíclico (de Dijkstra)

La distancia ui más corta a un nodo

[0, -1] [7, 3]

Donde xij kij

También podría gustarte