Teoría de redes
description
Transcript of Teoría de redes
![Page 1: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/1.jpg)
Teoría de redesTeoría de redes
Problema de la Ruta más corta Problema del Árbol de expansión mínima Problema del Flujo máximo Problema de Flujo de costo mínimo
Problema de la Ruta más corta Problema del Árbol de expansión mínima Problema del Flujo máximo Problema de Flujo de costo mínimo
UNIVERSIDAD DE MANAGUA
Al más alto nivel
Maestro
Ing. Julio Rito Vargas Avilés II Cuatrimestre 2012
![Page 2: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/2.jpg)
Introducción• Grafo: Serie de puntos llamados nodos (nudos) unidos
por arcos o aristas.
• Red: Es una grafo con algún tipo de flujo en sus ramales. Ejemplo: Eléctrica, transporte.
![Page 3: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/3.jpg)
Introducción• Cadena: Serie de elementos que van de un nodo a
otro. Ejemplo: 1- 2, 2 -5, 5 -7.• Ruta: Serie de elementos que conforman una cadena.
Ejemplo: Para el anterior 1 - 2 - 5 - 7.• Ciclo: Es la cadena que une un nodo consigo mismo.
Ejemplo: 3 -5, 5 -2, 2 -4, 4 -7, 7- 6, 6 -3.• Gráfica conectada: Aquella en la cual al menos todos
los nodos están conectados. Ejemplo: El de la gráfica.
![Page 4: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/4.jpg)
Introducción• Ramal(arco) orientado(dirigido): Es aquel que
tiene un sentido determinado, o sea, que tiene un nodo origen y un nodo destino. Ejemplo:
![Page 5: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/5.jpg)
Introducción
• Gráfico orientada(dirigido): Aquella en la cual todos sus ramales están orientados. Ejemplo:
![Page 6: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/6.jpg)
Introducción• Árbol: Gráfica sin ciclos. Ejemplo:
• La capacidad de flujo de un ramal es el límite superior de la ruta de flujo en dicho ramal en un sentido determinado.
![Page 7: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/7.jpg)
Introducción• Nodo fuente: Aquel en el cual todos sus
ramales están orientados hacia afuera. Ejemplo:
• Nodo receptor: Aquel en el cual todos sus ramales están orientados hacia él.
• Ejemplo
1
9
![Page 8: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/8.jpg)
Algunas Aplicaciones• Diseño de redes de telecomunicaciones
– Redes de fibra óptica– Redes de computadoras– Redes telefónicas– Redes de Internet o TV por cable, etc.
• Diseño de redes de transporte– Vías ferroviarias, carreteras, etc.
• Diseño de una línea de transmisión eléctrica de alto voltaje.• Diseño de una red de tubería para conectar varias localidades.
![Page 9: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/9.jpg)
PROBLEMA DE LA RUTA MAS CORTA• Por medio de la aplicación del algoritmo de este problema podemos
conocer la menor distancia entre un nodo origen y un nodo destino. Pasos a seguir:• Primer paso: Elaborar un cuadro con todos los nodos y los ramales que
salen de él.• Segundo paso: Partiendo del origen, debemos encontrar el nodo más
cercano a él.• Tercer paso: Anular todos los ramales que entren al nodo más cercano
elegido.• Cuarto paso: Comenzando en el origen se debe encontrar el nodo más
cercano a él, por intermedio del(los) nodo(s) ya elegido(s) y volver al tercer paso hasta llegar al destino. Ejemplo:
![Page 10: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/10.jpg)
Algoritmo• Definición de algoritmo: es un conjunto de reglas que permiten
obtener un resultado determinado a partir de ciertas reglas definidas.
• Definición de algoritmo: es una secuencia finita de instrucciones, cada una de las cuales tiene un significado preciso y puede ejecutarse con una cantidad finita de esfuerzo en un tiempo finito.
• Todo algoritmo ha de tener las siguientes características: legible, correcto, modular, eficiente, estructurado, no ambiguo y a ser posible se ha de desarrollar en el menor tiempo posible.)
![Page 11: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/11.jpg)
Algoritmo de Edsger Dijkstra Nació en Alemania en 1930, su padre era Químico y su madre Matemática. En 1956, Dijkstra anunció su algoritmo. Algoritmo de caminos mínimos, propuso el algoritmo del camino más corto y el algoritmo del
árbol generador minimal. A principios de la década de los 60, Dijkstra aplicó la idea de la exclusión mutua a las comunicaciones entre una computadora y su teclado. Su solución de exclusión mutua ha sido usada por muchos procesadores modernos y tarjetas de memoria desde 1964, cuando IBM la utilizó por primera vez en la arquitectura del IBM 360.
El algoritmo de Dijkstra para ruta más corta, en términos generales, encuentran la ruta más
corta entre dos nodos, inicial a y final z, de la siguiente manera Los nodos de la red son etiquetados con números. Al principio, todos tienen la etiqueta 00
excepto el nodo inicial a que tiene la etiqueta 0. Los arcos tienen un peso dij que representa la distancia del enclace (i, j). El algoritmo de Dijkstra renumeran los nodos, de manera que cuando el nodo z tiene una etiqueta permanente, se ha obtenido la solución final.
![Page 12: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/12.jpg)
Ejemplo 2:• La administración de Seervada Park necesita determinar
los caminos bajo los cuales se deben tender las líneas telefónicas para conectar las estaciones con una longitud total mínima de cable.
• Se describirá paso a paso la solución de este problema, en base a los datos que se proporcionan en la figura siguiente. Los nodos y distancias se muestran en la red, en donde las líneas delgadas representan ligaduras potenciales.
![Page 13: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/13.jpg)
Aplicación del algoritmo de la ruta más corta al problema de Seervada Park
NNodos resueltos, conectados
directamente a nodos no resueltos
Nodos no resueltos más
cercanos conectados
Distancia total
involucrada
N-ésimo nodo más cercano
Distancia mínima
Última conexión
1 O A 2 A 2 OA
2,3 OA
CB
42+2=4
CB
44
OCAB
4 ABC
DEE
2+7=94+3=74+4=8
E 7 BE
5 ABE
DDD
2+7=94+4=87+1=8
DD
88
BDED
6 DE
TT
8+5=137+7=14
T 13 DT
![Page 14: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/14.jpg)
O
A D
B
C E
T
2
7
5
2
4
4
1
4
3
1
5
7
RED SEERVADA PARK
![Page 15: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/15.jpg)
O
A D
B
C E
T
2
7
5
2
4
4
1
4
3
1
5
7
En forma arbitraria, se selecciona el nodo O como inicio. El nodo no conectado más cercano a O es A. Se conecta el nodo O con A . OA
![Page 16: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/16.jpg)
O
A D
B
C E
T
2
7
5
2
4
4
1
4
3
1
5
7
El nodo no conectado más cercano a los nodos O o A es el nodo B (más cercano a A). Se conecta el nodo B con el nodo A.- AB
![Page 17: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/17.jpg)
O
A D
B
C E
T
2
7
5
2
4
4
1
4
3
1
5
7
El nodo no conectado más cercano a los nodos O o A o B es el nodo C (más cercano a B),. Se conecta el nodo C con el nodo B.- BC
![Page 18: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/18.jpg)
O
A D
B
C E
T
2
7
5
2
4
4
1
4
3
1
5
7
El nodo no conectado más cercano a los nodos O o A o B o C, es el nodo E (más cercano a B),. Se conecta el nodo E con el nodo B.- BE
![Page 19: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/19.jpg)
O
A D
B
C E
T
2
7
5
2
4
4
1
4
3
1
5
7
El nodo no conectado más cercano a los nodos O, A, B, C o E, es el nodo D (más cercano a E),. Se conecta el nodo D con el nodo E.- ED
![Page 20: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/20.jpg)
O
A D
B
C E
T
2
7
5
2
4
4
1
4
3
1
5
7
El único nodo no conectado es el nodo T. Esta más cercano al nodo D. Se conecta el nodo T con el nodo D.- DT : SOLUCIÓN: OA-AB-BE-ED-DT=13
SOLUCION: OA-AB-BD-DT = 13
![Page 21: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/21.jpg)
Usando WinQSB
![Page 22: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/22.jpg)
Usando WinQSB
![Page 23: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/23.jpg)
Análisis de la solución• Todo los nodos han quedado conectado por
que ésta es la solución óptima que se buscaba. La longitud total de las ramas es 13 millas.
• El objetivo es diseñar la red más apropiada para el problema dado.
![Page 24: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/24.jpg)
Ejemplo 2 de red13 19
16
11
24
22
18
27
30
11
![Page 25: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/25.jpg)
Ruta más corta
![Page 26: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/26.jpg)
Solución• Es decir, la ruta más corta corresponde a la
ruta ABFJ, la cual suma 30 unidades.
A
B
FJ
![Page 27: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/27.jpg)
![Page 28: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/28.jpg)
Árbol de expansión mínima Este problema surge cuando todos los nodos de
una red deben conectar entre ellos, sin formar un loop.
El árbol de expansión mínima es apropiado para problemas en los cuales la redundancia es expansiva, o el flujo a lo largo de los arcos se considera instantáneo.
![Page 29: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/29.jpg)
![Page 30: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/30.jpg)
![Page 31: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/31.jpg)
![Page 32: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/32.jpg)
EL TRANSITO DE LA CAPITAL La ciudad de Managua esta planificando el desarrollo de una nueva
línea en sistemas de tránsito. El sistema debe unir 5 distritos, Universidades y centros
comerciales. La Dirección de transito necesita seleccionar un conjunto de líneas
que conecten todos los centros a un mínimo costo. La red seleccionada debe permitir:
- Factibilidad de las líneas que deban ser construidas.- Factibilidad de las líneas que deban ser construidas.- Mínimo costo posible por línea.- Mínimo costo posible por línea.
![Page 33: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/33.jpg)
RED QUE REPRESENTA
EL ARBOL EXPANDIDO
5
2 6
4
7
81
3
Zona Oeste
Zona Norte Universidad
DistritoComercial
Zona EsteCentroComercial
Zona Sur
Zona Centro
33
5030
55
34
2832
35
39
45
38
43
44
41
3736
40
![Page 34: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/34.jpg)
Solución Solución - Analogía con un problema de redes
- El algoritmo que resuelve este problema es un procedimiento muy fácil (“trivial”).- El algoritmo que resuelve este problema es un procedimiento muy fácil (“trivial”).- Corresponde a una categoría de algoritmos “ávidos”.- Corresponde a una categoría de algoritmos “ávidos”.- Algoritmo:- Algoritmo:
* Comience seleccionando el arco de menor longitud.* Comience seleccionando el arco de menor longitud.* En cada iteración, agregue el siguiente arco de menor * En cada iteración, agregue el siguiente arco de menor longitud longitud del del
conjunto de arcos disponibles , tomando la conjunto de arcos disponibles , tomando la precaución de no formar ningún loop.precaución de no formar ningún loop.* El algoritmo finaliza cuando todos los nodos están * El algoritmo finaliza cuando todos los nodos están conectados.conectados.
Solución mediante el computador- Los entrada consiste en el número de nodos, el largo de los arcos y la descripción de la red.- Los entrada consiste en el número de nodos, el largo de los arcos y la descripción de la red.
![Page 35: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/35.jpg)
SoluciónSolution for Minimal Spanning Tree Problem PROBLEMA DE TRANSITO MANAGUA
From Node Connect To Distance/Cost From Node Connect To Distance/Cost1 Zona Oeste Zona Centro 28 5 Zona Sur Centro Comercial 362 Zona Centro Zona Norte 30 6 Zona Centro Zona Sur 373 Zona Centro Distrito Comercial 32 7 Universidad Zona Este 384 Zona Centro Universidad 35
Total Minimal Connected Distance or Cost = 236
Solución óptima mediante WINQSB Solución óptima mediante WINQSB
![Page 36: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/36.jpg)
RED QUEREPRESENTA LASOLUCIÓN ÓPTIMA
CentroComercial
Loop
5
2 6
4
7
81
3
Zona Oeste
Zona Norte
Universidad
DistritoComercial
Zona Este
Zona Sur
ZonaCentro
33
5030
55
34
28
32
35
39
45
38
43
44
41
3736
40
Costo Total = C$236 millones
![Page 37: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/37.jpg)
![Page 38: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/38.jpg)
![Page 39: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/39.jpg)
PROBLEMA DEL FLUJO MAXIMO
• Nos permite conocer(calcular) la máxima cantidad de cualquier artículo o información que podemos transportar desde un origen hasta un destino.
• Pasos a seguir : • Primer paso: Elegir una ruta arbitraria.• Segundo paso: En dicha ruta escoger aquel ramal de menor flujo en
ese sentido y transportar por esa ruta la cantidad escogida.• Hacer esto repetitivamente hasta que no sea posible encontrar una
ruta con capacidad de flujo.
![Page 40: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/40.jpg)
Algunas AplicacionesAlgunas Aplicaciones• Maximizar el flujo a través de la red de distribución de
una compañía desde sus fábricas hasta sus clientes.• Maximizar el flujo a través de la red de suministros de
una compañía de proveedores a las fábricas.• Maximizar el flujo de petróleo por tuberías.• Maximizar el flujo de agua a través de un sistema de
acueductos.• Maximizar el flujo de vehículos por una red de transporte.
• Maximizar el flujo a través de la red de distribución de una compañía desde sus fábricas hasta sus clientes.
• Maximizar el flujo a través de la red de suministros de una compañía de proveedores a las fábricas.
• Maximizar el flujo de petróleo por tuberías.• Maximizar el flujo de agua a través de un sistema de
acueductos.• Maximizar el flujo de vehículos por una red de transporte.
![Page 41: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/41.jpg)
Ejemplo 1 Problema de flujo máximo de Seervada Park.• Tiene varias fábricas y múltiples clientes. Se
trata de aumentar la red original que incluya una fuente ficticia y un destino ficticio y algunos arcos nuevos.
![Page 42: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/42.jpg)
Problema de flujo máximo de Seervada Park
O
A D
B
C E
T
5
3
7
1
4
4
2
4
51
9
6
![Page 43: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/43.jpg)
Red residual del problema de flujo máximo de Seervada Park
O
A D
B
C E
T
5
3
7
1
4
42
4
51
9
6
0
0
0
0
0
00
0
0
0
0
0
![Page 44: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/44.jpg)
Iteracción 1: Una de las trayectorias de aumento es O→B →E →T que tiene capacidad residual igual al mín{7,5,6}=5si se asigna un flujo de 5 a esta trayectoria, la red resultante es:
O
A D
B
C E
T
5
3
2
1
4
42
4
01
9
1
0
0
0
5
0
00
0
5
5
50
05
![Page 45: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/45.jpg)
O
A D
B
C E
T
2
0
2
1
4
42
4
01
6
1
3
0
0
5
3
30
0
5
5
8
Iteracción 2: Una de las trayectorias de aumento es O→A →D →T que tiene capacidad residual igual al mín{5,3,9}=3, si se asigna un flujo de 3 a esta trayectoria, la red resultante es:
0
08
![Page 46: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/46.jpg)
O
A D
B
C E
T
1
0
2
0
4
42
3
01
5
1
4
0
0
5
4
31
0
5
5
9
Iteracción 3: Una de las trayectorias de aumento es O→A →B →D →T que tiene capacidad residual igual al mín{2,1,4,6}=1, si se asigna un flujo de 1 a esta trayectoria, la red resultante es:
1
09
![Page 47: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/47.jpg)
O
A D
B
C E
T
1
0
0
0
4
42
1
01
3
1
4
0
0
7
6
33
0
5
5
11
Iteracción 4: Una de las trayectorias de aumento es O→B→D →T que tiene capacidad residual igual al mín{2,3,5}=2, si se asigna un flujo de 2 a esta trayectoria, la red resultante es:
1
011
![Page 48: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/48.jpg)
O
A D
B
C E
T
1
0
0
0
3
32
1
00
2
1
4
0
1
7
7
33
1
5
5
12
Iteracción 5: Una de las trayectorias de aumento es O→C →E →D →T que tiene capacidad residual igual al mín{4,4,1,3}=1, si se asigna un flujo de 1 a esta trayectoria, la red resultante es:
1
112
![Page 49: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/49.jpg)
O
A D
B
C E
T
1
0
0
0
2
22
1
00
2
0
4
0
2
7
7
33
1
6
513
Iteracción 6: Una de las trayectorias de aumento es O→C →E →T que tiene capacidad residual igual al mín {3,3,1}=1, si se asigna un flujo de 1 a esta trayectoria, la red resultante es:
1
2
13
![Page 50: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/50.jpg)
O
A D
B
C E
T
1
0
0
0
1
12
0
10
1
0
4
0
3
7
8
34
1
6
414
Iteracción 7: Una de las trayectorias de aumento es O→C →B → D→T que tiene capacidad residual igual al mín {2,2,5,1,2}=1, si se asigna un flujo de 1 a esta trayectoria, la red resultante es:
1
3
14
Ya no existe trayectoria de aumento, por lo que el patrón actual es óptimo
![Page 51: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/51.jpg)
Maximal Flow Problem
![Page 52: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/52.jpg)
Solución WinQSB
![Page 53: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/53.jpg)
Ejemplo 2• Encontrar el flujo máximo, en la red,, dado
que la capacidad a través del arco que va del nodo i al nodo j es el número más cercano al nodo i del arco entre estos nodos.
![Page 54: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/54.jpg)
6
3
41
1
4
9
4
43
RED DE FLUJO MAXIMO
I
A
B
C
T
D
E
Origen
Final
![Page 55: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/55.jpg)
2
3
41
1
0
9
0
43
Iteracción 1: Una de las trayectorias de aumento es I→A →D →T que tiene capacidad residual igual al mín{6,4,4}=4si se asigna un flujo de 4 a esta trayectoria, la red resultante es:
4 4
44
4I
A
B
C
T
D
E
Origen
Final
![Page 56: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/56.jpg)
2
0
41
1
0
6
0
13
Iteracción 2: Una de las trayectorias de aumento es I→B →E →T que tiene capacidad residual igual al mín{4,3,9}=3si se asigna un flujo de 3 a esta trayectoria, la red resultante es:
4 4
47
73 33
I
A
B
C
T
D
E
Origen
Final
![Page 57: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/57.jpg)
2
0
31
1
0
5
0
02
Iteracción 3: Una de las trayectorias de aumento es I→B →C →E → T que tiene capacidad residual igual al mín{1,3,4,6}=1, se asigna un flujo de 1 a esta trayectoria, la red resultante es:
4 4
48
84 34
1 1
I
A
B
C
T
D
E
Origen
Final
![Page 58: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/58.jpg)
2
0
20
1
0
4
0
02
Iteracción 4: Una de las trayectorias de aumento es I→C →E → T, que tiene capacidad residual igual al mín{1,3,5} =1, se asigna un flujo de 1 a esta trayectoria, la red resultante es:
4 4
49
94 35
1 21
I
A
B
C
T
D
E
Origen
Final
![Page 59: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/59.jpg)
Maximal flow problem
![Page 60: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/60.jpg)
Solución WinQSB
![Page 61: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/61.jpg)
Solución final
I A
B
TD
E
C
![Page 62: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/62.jpg)
Problema del flujo máximoProblema del flujo máximo Este modelo se utiliza para reducir los embotellamientos Este modelo se utiliza para reducir los embotellamientos
entre ciertos puntos de partida y destino en una red.entre ciertos puntos de partida y destino en una red. Existe un flujo que viaja desde un único lugar de origen hacia Existe un flujo que viaja desde un único lugar de origen hacia
un único lugar destino a través de arcos que conectan nodos un único lugar destino a través de arcos que conectan nodos intermediosintermedios
Cada arco tiene una capacidad que no puede ser excedidaCada arco tiene una capacidad que no puede ser excedida La capacidad no debe ser necesariamente la misma para cada La capacidad no debe ser necesariamente la misma para cada
dirección del arco.dirección del arco.
![Page 63: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/63.jpg)
Definición del ProblemaDefinición del Problema
- Existe un nodo origen (con el número 1), del cual los flujos emanan.- Existe un nodo origen (con el número 1), del cual los flujos emanan.
- Existe un nodo terminal (con el número n), en el cual todos los flujos - Existe un nodo terminal (con el número n), en el cual todos los flujos de la red son depositados.de la red son depositados.
- Existen n-2 nodos (númerados del 2, 3,....,n-1), en el cual el flujo que - Existen n-2 nodos (númerados del 2, 3,....,n-1), en el cual el flujo que entra es igual al flujo que sale.entra es igual al flujo que sale.
- La capacidad C- La capacidad Cij ij que transita del nodo i al nodo j, y la capacidad Cque transita del nodo i al nodo j, y la capacidad C jiji para la dirección opuesta.para la dirección opuesta.
![Page 64: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/64.jpg)
El objetivo es encontrar la máxima El objetivo es encontrar la máxima cantidad de flujo que salga del nodo 1 al cantidad de flujo que salga del nodo 1 al nodo n sin exceder la capacidad de los nodo n sin exceder la capacidad de los
arcos.arcos.
![Page 65: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/65.jpg)
COMPAÑÍA QUIMICA UNIDACOMPAÑÍA QUIMICA UNIDA Química unida produce pesticidas y otros productos de control Química unida produce pesticidas y otros productos de control
agrícola.agrícola. El veneno químico necesario para la producción es depositado en El veneno químico necesario para la producción es depositado en
grandes tambores.grandes tambores. Una red de tubos y válvulas regula el flujo del químico de los Una red de tubos y válvulas regula el flujo del químico de los
tambores a las diferentes áreas de producción.tambores a las diferentes áreas de producción. El departamento de seguridad debe diseñar un procedimiento El departamento de seguridad debe diseñar un procedimiento
que vacíe los tambores de la forma más rápida posible dentro de que vacíe los tambores de la forma más rápida posible dentro de los tubos del área de depósito, usando la misma red de tubos y los tubos del área de depósito, usando la misma red de tubos y válvulas.válvulas.
El procedimiento debe determinar:El procedimiento debe determinar:- Qué válvulas deben abrirse y cerrarse- Qué válvulas deben abrirse y cerrarse- Estimar el tiempo total de descarga.- Estimar el tiempo total de descarga.
![Page 66: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/66.jpg)
Tambores con químico
Tubo de Seg.
1 7
42
3
6
5
10
0
80
0
0
0
0
0
0
10
61
12
1 4
4 2
2 8
3
3
7
2
El máximo flujo de 2 a 4 es 8
No se permite flujo de 4 a 2.
![Page 67: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/67.jpg)
Solución - Analogía de un problema de programación linealSolución - Analogía de un problema de programación lineal– Variables de decisiónVariables de decisión
XXijij - Flujo que viaja desde el nodo i hacia el nodo j a través del arco que - Flujo que viaja desde el nodo i hacia el nodo j a través del arco que conecta ambos nodos.conecta ambos nodos.
– Función Objetivo - Maximizar el flujo que sale del nodo 1Función Objetivo - Maximizar el flujo que sale del nodo 1Max X12 + X13Max X12 + X13– RestriccionesRestricciones
• [Flujo total que sale del nodo 1] = [Flujo total que entra en el nodo 7][Flujo total que sale del nodo 1] = [Flujo total que entra en el nodo 7]X12 +X13 = X47 + X57 + X67X12 +X13 = X47 + X57 + X67
• [Para cada nodo intermedio: Flujo que entra = flujo que sale][Para cada nodo intermedio: Flujo que entra = flujo que sale]Nodo 2: X12 + X32Nodo 2: X12 + X32 = X23 +X24 + X26 = X23 +X24 + X26 Nodo 3:Nodo 3: X13 +X23 + X63X13 +X23 + X63 = X32 +X35 + X36= X32 +X35 + X36Nodo 4:Nodo 4: X24 +X64X24 +X64 = X46 + X47= X46 + X47Nodo 5:Nodo 5: X35 +X65X35 +X65 = X56 + X57= X56 + X57Nodo 6:Nodo 6: X26 +X36 + X46 +X56 X26 +X36 + X46 +X56 = X63 +X64 +X65 + X67= X63 +X64 +X65 + X67
![Page 68: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/68.jpg)
• EL flujo no puede exceder la capacidad de los arcosEL flujo no puede exceder la capacidad de los arcos• X12 10; X13 10; X23 1; X24 8; X26 6; X32 1; X12 10; X13 10; X23 1; X24 8; X26 6; X32 1;
X35 15; X36 4; X46 3; X47 7; X56 2; X57 8; X35 15; X36 4; X46 3; X47 7; X56 2; X57 8; X63 4; X64 3; X65 2; X67 2; X63 4; X64 3; X65 2; X67 2;
• Los flujos no pueden ser negativos: Todos XLos flujos no pueden ser negativos: Todos X ijij >= 0 >= 0
Se debe tener presente que este problema es relativamente pequeño Se debe tener presente que este problema es relativamente pequeño y la solución puede ser obtenida rápidamente usando el modelo de y la solución puede ser obtenida rápidamente usando el modelo de programación lineal.programación lineal.
Sin embargo para problemas de mayor envergadura se aconseja usar Sin embargo para problemas de mayor envergadura se aconseja usar el modelo de redes.el modelo de redes.
![Page 69: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/69.jpg)
Solución-Analogía con un problema de redesSolución-Analogía con un problema de redes
- La idea básica es la siguiente:- La idea básica es la siguiente:
* Encontrara un sin capacidad en cada uno de sus arcos.* Encontrara un sin capacidad en cada uno de sus arcos.* Aumentar el flujo de esos arcos por la mínima capacidad * Aumentar el flujo de esos arcos por la mínima capacidad de uno de de uno de
los arcos de la ruta.los arcos de la ruta.* Repetir este procedimiento hasta completar la ruta de * Repetir este procedimiento hasta completar la ruta de manera manera
tal que todos los arcos tengan una capacidad tal que todos los arcos tengan una capacidad residual positiva.residual positiva.*Designar un nodo origen y un nodo de flotación*Designar un nodo origen y un nodo de flotación* Definir las capacidades de todos los arcos en la red ( en * Definir las capacidades de todos los arcos en la red ( en ambos ambos
sentidos)sentidos)* A continuación se muestra la solución obtenida usando * A continuación se muestra la solución obtenida usando WINQSB.WINQSB.
![Page 70: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/70.jpg)
El máximo flujo obtenido por WINQSB El máximo flujo obtenido por WINQSB
Tambores con químico
Tubo de Seg.
1 7
42
3
6
5
8
8
2
77
10
7
8
2
Flujo Máximo= 17
![Page 71: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/71.jpg)
Problema del flujo del costo mínimoProblema del flujo del costo mínimo• El problema del flujo del costo mínimo tiene una posición central
entre los modelos de optimización de redes; 1) abarca una clase amplia de aplicaciones 2) su solución es muy eficiente
• Igual que el problema de flujo máximo, toma en cuenta un flujo en una red con capacidades de arcos limitadas. Igual que el problema de la ruta más corta, considera un costo o distancia del flujo a través de un arco. Al igual que el problema del transporte o el de asignación se pueden manejar varios orígenes y varios destinos del flujo con costos asociados. En realidad estos cuatro problemas son casos especiales del problema del flujo de costo mínimo.
![Page 72: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/72.jpg)
Método simplex de redesMétodo simplex de redes• A continuación se describe el problema de del flujo de
costo mínimo.1. La red es red dirigida y conexa2. Al menos uno de los nodos es un nodo fuente3. Al menos uno de los nodos es un nodo demanda.4. El resto de los nodos son nodos transbordo.5. Se permite el flujo a través de un arco sólo en la dirección
indicada por la flecha, donde la cantidad máxima de flujo está dada por la capacidad del arco.(si el flujo puede ocurrir en ambas direcciones, debe representarse por un par de arcos con direcciones opuestas.
![Page 73: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/73.jpg)
Método simplex de redes• A continuación se describe el problema del flujo de
costo mínimo (cont.).6. La red tiene suficientes arcos con suficiente capacidad para
permitir que todos los flujos generados por los nodos fuente lleguen a los nodos demanda.
7. El costo del flujo a través del arco es proporcional a la cantidad de ese flujo, donde se conoce el costo por unidad.
8. El objetivo es minimizar el costo total de enviar el suministro disponible a través de la red para satisfacer la demanda dada. (un objetivo alternativo es maximizar la ganancia total del envío)
![Page 74: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/74.jpg)
Aplicaciones comunes del problema del flujo de costo mínimo
Tipo de aplicación Nodos fuentes Nodos de transbordo Nodos demanda
Operación de una red de distribución
Fuentes de bienes Almacenes intermedios clientes
Administración de desechos sólidos
Fuentes de desechos sólidos
Instalaciones de procesamiento
Rellenos
Operación de una red de suministros
Agentes de ventas Almacenes intermedios Instalaciones de procesamiento
Coordinación de mezclas de productos en plantas
Plantas Productos de un artículo específico
Mercado del producto específico
![Page 75: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/75.jpg)
Formulación del modeloFormulación del modelo• Considere una red conexa dirigida en la que
los n nodos incluyen al menos un nodo origen y un nodo destino. Las variables de decisión son:
i nodopor generado neto flujo b
ji arco del capacidad
ji arco del travésa flujo de unidadpor costo
incluye dadan informació lay
arco del travésa
i
ij
ij
ij
U
C
jiflujoX
![Page 76: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/76.jpg)
Formulación del modelo• El valor de bi depende de la naturaleza del nodo i,
donde:
• El objetivo es minimizar el costo total de mandar los recursos disponibles a través de la red para satisfacer la demanda.
o transbordde nodoun es si 0
demanda nodoun es si 0 b
fuente nodoun es si 0
i
ib
i
ib
i
i
![Page 77: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/77.jpg)
Formulación del modelo• La formulación de programación lineal de este problema es:
• El objetivo es minimizar el costo total de mandar los recursos disponibles a través de la red para satisfacer la demanda.
jiuy
bXX
XC
ij
n
jijiij
n
i
n
jijij
arco cada para X0
i nodo cada para
:a sujeto
ZMinimizar
ij
1
n
1j
1 1
![Page 78: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/78.jpg)
PropiedadesPropiedades• No se garantiza que el problema tenga soluciones factibles,
pues todo depende en parte de qué arcos están presentes en la red y de sus capacidades.
• De cualquier manera, para una red diseñada en forma razonable, la condición necesaria más importante es la siguiente.
“El flujo total generado por los nodos origen es igual al flujo total absorbido por los nodos destino.
n
iib
1
0
![Page 79: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/79.jpg)
Ejemplo 1
X12
X25
X53
X35
X45
X13
X34
X23
X24
Flujo de Mínimo Costo
costo, capacidad
![Page 80: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/80.jpg)
Como PPL
Capacidad de los nodos
Nodo fuenteNodo de transbordoNodo demanda
![Page 81: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/81.jpg)
Solución• La solución óptima es: X12 = 12X13 = 8 X23 = 8 X24 = 4 X34 = 11 X35 = 5 X45 = 10Todos los demás Xij = 0. El costo óptimo es $150.
![Page 82: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/82.jpg)
WinQSB-PPL
![Page 83: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/83.jpg)
Solución óptima
X12=12
X25
X53
X35=5
X45=10
X13=8
X34=11
X23=8
X24=4
Flujo de Mínimo Costo
Costo óptimo=U$ 150.00
![Page 84: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/84.jpg)
Ejemplo 2
![Page 85: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/85.jpg)
ABx ACXADX
ACX
ABX
BCXCEX
EDXDEX
Ejemplo 2
![Page 86: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/86.jpg)
EDDECEBCADACAB xxxxxxxZ 233942
50 ADACAB xxx
40 BCAB xx
0 CEBCAC xxx
30 EDDEAD xxx
60 EDDECE xxx
10ABx
80CEx
0xij
Minimizar
Sujeto a:
Ejemplo 2
![Page 87: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/87.jpg)
Solución
ABx ACX10ADX
ABX
40ACX
40BCX
80CEX
20EDXDEX
![Page 88: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/88.jpg)
Modelo PPL
![Page 89: Teoría de redes](https://reader036.fdocumento.com/reader036/viewer/2022062314/568141cc550346895dada838/html5/thumbnails/89.jpg)
Salida PPL