Tema 2 Optimización de Redes Ene-Jun 2023

5to
Semestre
Investigación de
Operaciones II
Tema 2
Optimización de Redes
La Optimización de redes es un tipo especial de

modelo en programación lineal.
Optimización de Redes
Ver el siguiente video como introducción a la Teoría de Redes
Introducción
INVESTIGACIÓN
HERRAMIENTAS PARA DE OPERACIONES
LA TOMA
DE DECISIONES
PROGRAMACIÓN
LINEAL
INVESTIGACIÓN
DE
OPERACIONES OPTIMIZACIÓN
PROGRAMACIÓN
LINEAL
Introducción
ANALISIS DE FLUJO DE REDES

Las técnicas de flujo de redes están orientadas a
optimizar situaciones vinculadas a las redes
de transporte, redes de comunicación,
sistema de vuelos de los aeropuertos, rutas de
navegación de los cruceros, estaciones de
bombeo que transportan fluidos através de
fi n
tuberías, rutas entre ciudades, redes de inicio
conductos y todas aquellas situaciones que
puedan representarse mediante una red
donde los nodos representan las estaciones o
las ciudades, los arcos los caminos, las líneas
aéreas, los cables, las tuberías y el flujo lo
representan los camiones,mensajes y fluidos
que pasan por la red..
Introducción
ANALISIS DE FLUJO DE REDES
Con el objetivo de encontrar la ruta mas

corta si es una red de caminos o enviar
el máximo fluido si es una red de
tuberías.
Cuando se trata de encontrar el camino
más corto entre un origen y un destino, fi n
la técnica, algoritmo o el modelo inicio
adecuado es el de la ruta más corta;

aunque existen otros modelos de redes
como el árbol de expansión mínima,
flujo máximo y flujo de costo mínimo
cada uno abarca un problema en
particular.
.
Introducción
MODELOS DE RED
Los modelos de redes son aplicables a una extensa
variedad de problemas de decisión, los cuales pueden
ser modelados como problemas de optimización de
redes que pueden ser eficiente y efectivamente
resueltos. Algunos de estos problemas de decisión
son realmente problemas físicos, tales como el
transporte o flujo de bienes materiales. Sin embargo,
muchos problemas de redes son mas que una fi n
representación abstracta de procesos o actividades, inicio
tales como el camino crítico en las actividades entre

las redes de un proyecto gerencial. La familia de
redes de los problemas de optimización incluye los
siguientes prototipos de modelos: Problemas de
asignación, camino crítico, flujo máximo, camino
mas corto, transporte y costo mínimo de flujos. Los
problemas son establecidos fácilmente mediante el
uso de arcos de redes y de los nodos.
Introducción
MODELOS DE RED
Los problemas de optimización de redes se

pueden representar en términos generales a
través de uno de estos cuatro modelos:
• Modelo de minimización de redes (Problema fi n

del árbol de mínima expansión). inicio
• Modelo de larutamás corta.
• Modelo del flujo máximo.
• Modelo del flujo del costo mínimo.

Introducción
ü Requieren en forma natural de

soluciones enteras. Al reconocer que
un problema puede formularse como
fin
algún modelo de red nos inicio
permitirá resolver tipos especiales de

problemas de programación entera
aumentando la eficiencia y reduciendo
el tiempo consumido por los algoritmos
clásicos de programación lineal.
Introducción
ü Son intuitivos.
Los modelos de redes proveen un lenguaje
para tratar los problemas, mucho más
intuitivo que "variables, objetivo,
restricciones".
fin
inicio
Obviamente los modelos de redes no son

capaces de cubrir la amplia gama de
problemas que puede resolver la
programación lineal. Sin embargo, ellos
ocurren con suficiente frecuencia como
para ser considerados como una
herramienta importante para una real
toma de decisiones.
CONTENIDO TEMA 2
OPTIMIZACIÓN DE REDES
2.1 2.3 2.4

2.2
Terminología Problema de árbol Problema de
Problema de la
de mínima flujo máximo
ruta mas corta expansión
2.5 2.6 2.7

Problema de flujo Programación Lineal uso de software
de costo mínimo
en teoría de redes
2.1
Terminología
Que es una Red o Grafo?
El término “grafo” proviene de una palabra griega, que
traducido al español significa dibujo o imagen. Un grafo
es una composición entre un conjunto de objetos
conocidos como nodos, y estos están relacionados por
medio de un conjunto de conexiones (o líneas) llamadas
aristas.
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.
N = {1, 2, 3, 4, 5}
A = {(1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 5)}
2.1
Terminología
Que es un Nodo?
Usualmente llamado vértice, o punto. Generalmente
es representado por un círculo.
En las redes de transporte, estos deberían ser las
localidades o las ciudades en un mapa.
N = {1, 2, 3, 4, 5}
2.1
Terminología
Que es un Nodo Fuente?
El nodo fuent e es aquel nodo en el cual t odos sus

ramales se encuentran orientados hacia afuera.
Que es un Nodo Destino?

El nodo dest ino es aquel nodo en el cual t odos sus
ramales se encuent ran orient ados hacia él.
2.1
Terminología
Que es un Arco?
Usualmente llamado borde o flecha. Este podría ser directo o
indirecto. La cabeza es el destino, y la cola el origen. La cabeza y
la cola son nodos que pueden estar tanto al origen como al final.
En las redes de transporte, los arcos podrían ser los caminos, los
canales de navegación en un río, o los patrones de vuelo de un
avión. Los arcos proporcionan la conectividad entre los nodos.
Una calle de una sola dirección podría ser representada por un
arco, mientras que una calle de dos direcciones podría
representarse por un arco sin dirección o por dos arcos que
apuntan a direcciones opuest as. Una red con n nodos podría
tener tantos arcos como n! /[(n-2)! 2!] = n(n-1)/2. Si están
dirigidos, este número pudiese ser doble. Este enorme número
de arcos posibles es una de las razones del porque existen
soluciones de algoritmos especiales para problemas de redes
part iculares.
En el nodo de la red comúnmente encontrarás un número con un
signo positivo o negativo, el cual denota la oferta (+) y la
demanda o requerimient os (-) del nodo.
A = {(1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 5)}
2.1
Terminología
Que es una Cadena?
Una cadena corresponde a una serie de elementos

ramales que van de un nodo a ot ro. En el
siguient e caso se resalt a una cadena que va
desde el nodo 1 hasta el nodo 7 y que se
compone por los elementos [1-4, 4-7].
2.1
Terminología
Que es una Ruta?
Una rut a corresponde a los nodos que

constituyen una cadena, en el siguiente caso
[1, 4, 7].
2.1
Terminología
Que es un Ciclo?
Un ciclo corresponde a la cadena que une a un nodo

con sigo mismo, en el siguiente ejemplo el ciclo
está compuesto por la cadena [4-2, 2-5, 5-7, 7-4].
2.1
Terminología
Que es un Ramal Orientado?
Un ramal o arco orientado es aquel que tiene un

sentido determinado, es decir que posee un nodo
fuente y un nodo destino.
2.1
Terminología
Que es una Red o grafo Orientado?
Una red o dibujo orientado es aquel en el cual todos

sus ramales se encuentran orientados.
2.1
Terminología
Que es un Árbol?
Un árbol es una gráfica en la cual no existen ciclos,
como el siguiente ejemplo.
.
Que es un Árbol de expansión?

Un árbol de expansión es aquel árbol que enlaza
todos los nodos de la red, de igual manera no
permite la existencia de ciclos
2.5 Programación Lineal en Teoría de Redes
INTRODUCCIÓN
Técnicas para resolver un problema de IO
“La técnica de IO más importante es la Programación Lineal (PL). La PL está diseñada para modelos
con funciones objetivo y restricciones lineales” (Taha, 2012, p. 5)
Esta técnica es exitosa, pero ¡CUIDADO!, no debe aplicarse a cualquier situación. La tendencia a
utilizarla puede conducirnos a un modelo matemático del todo alejado de la situación real. Por lo
tanto, es imperativo que se analicen primero otras técnicas.
A continuación, haremos un breve resumen de las técnicas más utilizadas para resolver problemas
de IO:
1) Programación Lineal: Función Objetivo y restricciones lineales

2) Programación Entera: Las variables representan números enteros
3) Programación Dinámica: El modelo original se puede descomponer en submodelos.
4) Programación de Red: El problema se modela mediante una red.
5) Programación no lineal: La relación entre las variables del problema son no lineales
2.5
Programación Lineal en Teoría de Redes
Los m odelos de redes tam bién pueden expresarse co m o m odelos de

program ación lineal
La Programación Entera permite abordar de fo rm a eficiente este

tipo de problem as, en especial cuando la cantidad de nodos y rutas
posibles resulta ser u n núm ero significativo. Utilizar en estos casos
u n enfoque intuitivo de resolución es tedioso y de no ser exhaustivo
no garantiza la identificación de la m ejor alternativa o ruta.
2.5
Programación Lineal en Teoría de Redes
Programación Lineal
Modelo abstracto algebráico
Problemas del mundo

industrial, económicos, Análisis, Interpretación,
administrativos, pueden Solución
ser suceptibles a
resolverse como un
problema de PL:
Problemas de Transporte, Matematización:
Asignación, Redes, aplicación de las
Producción, Mezclas, etc Matemáticas a la vida
industrial, economica,
administrativa
2.2
Problema de la Ruta más corta
El Problema del Camino más Corto (o ruta más
barata) consiste en encontrar una ruta o camino
óptimo entre un nodo fuente y un nodo destino,
los cuales est án enlazados a t ravés de una red
con arcos que poseen un cierto atributo, el cual
puede ser costo, distancia, tiempo, etc.
El algoritmo de Dijkstra, también llamado algoritmo de

caminos mínimos, es un algoritmo para la determinación
del camino más corto, dado un vértice origen, hacia el
resto de los vértices en un grafo que tiene pesos en
cada arista. Su nombre alude a Edsger Dijkstra, científico
de la computación de los Países Bajos que lo concibió en
1956 y lo publicó por primera vez en 1959.
2.2
APLICACIONES DEL ALGORITMO DE DIJKSTRA
El algoritmo de Dijsktra se aplica:
• En redes de computadores (donde los routers son los
nodos y las aristas las conexiones entre ellos),
2.2
APLICACIONES DEL ALGORITMO DE DIJKSTRA
•Transporte aéreo (tienen acceso a una base de datos que contiene toda la
información sobre aviones circulando alrededor de ellos, y de la misma manera
se evitan accidentes),
2.2
APLICACIONES DEL ALGORITMO DE
DIJKSTRA
Waze /Google Maps como un
algoritmo de la Ruta más corta
La relación de los grafos con Waze es un
algoritmo que se fundamenta en el
Algoritmo de Dijkstra. Encontrar la ruta
más corta o más rápida entre dos puntos
en un mapa. Este algoritmo se utiliza para
la determinación del camino más corto
desde un vértice (nodo) de origen, y utiliza
el peso de las aristas para relacionarse con
los otros vértices. El algoritmo se detiene al
analizar todos los pesos de las aristas y
encuentra el camino más corto desde el
vértice origen.
2.2 Problema de la Ruta más corta
Ejercicio en clase
Consideremos el siguiente diagrama donde los nťmeros asignados a cada uno de los
arcos representan la distancia en kilómetros de un nodo a otro. Se desea encontrar
la ruta con la distancia mínima para ir del nodo 1 al nodo 8.
8 17
2 5 7
4
INICIO 20 9
1
4 15
12 8 FIN
3
2
3
22
4 6
2.2
8 17
2 5 7
4
20 9
1
4 15
12 8
3
2
3 22
4 6
2.2
El tamaño reducido de la red anterior permite encontrar el camino más corto simplemente
enumerando las distintas alternativas que comenzando en el nodo 1permita llegar al nodo
8. De esta forma las rutas posibles son:
8 17
•Ruta 1-2-5-7-8: 4+8+17+9=38[km] 2 5 7
•Ruta 1-3-4-7-8: 3+12+20+9=44[km] 4
•Ruta 1- 3- 4- 6- 8: 3+12+2+22=39[km] 20 9
•Ruta 1-3-4-8: 3+12+15=30[km] 1
•Ruta 1-3-6-8: 3+4+22=29[km]
4 15
12 8
3
INFORME OCONCLUSIÓN:Laruta o camino máscorto esta 2
3
dada por la secuencia 1- 3- 6- 8con una distancia 22
total de29[km]. 4 6
Programación Lineal (PL)
El modelo de Programación Entera permite extender este tipo de resultados a un
problema con estas características, quedando de la siguiente manera:
Variables de Decisión: 8 17
4 2 5 7
𝑿𝒊-𝒋 ∶ La distancia mínima para ir del nodo i al nodo j 20 9
1
15
12 4
8
3 2
Función Objetivo 3
6 22
Minimizar la distancia total en [km] dada por la siguiente 4
expresión:
𝟒𝑿𝟏-𝟐 + 𝟑𝑿𝟏-𝟑 + 𝟖𝑿𝟐-𝟓 + 𝟏𝟐𝑿𝟑-𝟒 + 𝟒𝑿𝟑-𝟔 + 𝟏𝟕𝑿𝟓-𝟕 + 𝟐𝟎𝑿𝟒-𝟕 + 𝟐𝑿𝟒-𝟔 + 𝟏𝟓𝑿𝟒-𝟖 +𝟐𝟐𝑿𝟔-𝟖 + 𝟗𝑿𝟕-𝟖
Restricciones:
𝑿𝒊-𝒋 : 𝟏 𝑺𝒊 𝒆𝒍 𝒏𝒐𝒅𝒐 𝒋 𝒆𝒔 𝒗𝒊𝒔𝒊𝒕𝒂𝒅𝒐 𝒊𝒏𝒎𝒆𝒅𝒊𝒂𝒕𝒂𝒎𝒆𝒏𝒕𝒆 𝒅𝒆𝒔𝒑𝒖é𝒔 𝒅𝒆𝒍 𝒏𝒐𝒅𝒐 𝒊

𝟎 𝑺𝒊 𝒏𝒐
(1) 𝑿𝟏-𝟐 + 𝑿𝟏-𝟑 = 𝟏 La primera restricción del nodo (1)garantiza que sólo un nodo (entre el 2 y el 3)
pueda ser el que se visita a continuación de comenzar en el nodo 1.
8 17 Nota: En teoría de grafos, una red de flujo es

4 2 5 7
un grafo dirigido donde existen
20 9 dos vértices especiales, uno llamado fuente, al que
1 se le asocia un flujo positivo y otro
15
12 4 llamado sumidero que tiene un flujo negativo y a
8
3 2 cada arista se le asocia cierta capacidad positiva
3
6 22
4
La restricción del nodo (2) determina que si se visitó el nodo 2 después del nodo 1,
(2) 𝑿𝟏-𝟐 − 𝑿𝟐-𝟓 = 𝟎 entonces necesariamente el nodo 5 será visitado después del nodo 2.
Restricciones:

La restricción del nodo (3) permite verificar que si el nodo 3fue visitado
(3) 𝑿𝟏-𝟑 − 𝑿𝟑-𝟒 − 𝑿𝟑-𝟔 = 𝟎 luego del nodo 1, entonces a continuación se visita el nodo 4 o el nodo 6
(sólo uno de ellos).

4 2 5 7
15
8
3
6 22
4
La restricción del nodo (4) garantiza que si el nodo 4 fue visitado luego
(4) 𝑿𝟑-𝟒 − 𝑿𝟒-𝟔 − 𝑿𝟒-𝟕 −𝑿𝟒-𝟖 = 𝟎 del nodo 3, entonces a continuación el nodo 4 visitará uno de los
siguientes nodo: 6, 7u 8.
Restricciones:

La restricción del nodo (5) establece que si el nodo 5 fue visitado luego del nodo 2,
(5) 𝑿𝟐-𝟓 − 𝑿𝟓-𝟕 = 𝟎 entonces el nodo 7debe ser visitado luego del nodo 5.
8 17 Nota: En teoría de grafos, una red de

4 2 5 7
flujo es un grafo dirigido donde existen
20 9
1 dos vértices especiales, uno
15 llamado fuente, al que se le asocia un flujo
12 4
8 positivo y otro llamado sumidero que tiene
3 2
3 un flujo negativo y a cada arista se le asocia
6 22 cierta capacidad positiva
4
La restricción del nodo (6) indica que si el nodo 6 fue visitado
(6) 𝑿𝟑-𝟔 + 𝑿𝟒-𝟔 − 𝑿𝟔-𝟖 = 𝟎 inmediatamente luego de estar en el nodo 3o 4, a continuación se visita el
nodo 8.
Restricciones:

La restricción del nodo (7) determina que si el nodo 7 fue visitado
(7) 𝑿𝟓-𝟕 + 𝑿𝟒-𝟕 − 𝑿𝟕-𝟖 = 𝟎 inmediatamente luego de estar en el nodo 4 o 5, a continuación se visita el
nodo 8.

4 2 5 7
15
8
3
6 22
4
Finalmente la restricción del nodo (8) asegura que ya sea el nodo 7, 4 o 6

(8) 𝑿𝟕-𝟖 + 𝑿𝟒-𝟖 + 𝑿𝟔-𝟖 = −𝟏 sea el ť ltimo en visitar previo a terminar la ruta en el nodo 8.
2.2 Tarea 1: Problema de la Ruta más corta
• Encuentra el modelo matemático de Programación lineal que
representa a la red del dibujo (Variables de decisión, Función
Objetivo,Restricciones)
• Encuentra la ruta más corta entre el Nodo 1 y el nodo 8 utilizando
Solver de Excel.
• Reporta tu resultado en el Informe Administrativo
8 17
4 2 5 7
20 9
1
15
12 4
8
3 2
3
6 22
4
Video de apoyo Uso de Solver
https://youtu.be/62-m5QFNEWU
2.4
Introducción Problema de Flujo Máximo
En la sociedad actual se encuentran múltiples ejemplos en los que se
puede comprobar que está regida por redes:
• Redes de comunicación, • Redes de telefonía,

2.4
La prestación de servicios a través de estas redes requiere grandes
inversiones en recursos.
Normalmente la asignación de estos recursos se hace mediante un modelo
matemático de forma que se permita economizar al máximo ofreciendo una
calidad suficiente de servicio al usuario final.
• Redes de transporte, • Redes de energía eléctrica,

2.4
El problema de modelar un
determinado servicio y asignar
los mínimos recursos posibles
manteniendo un nivel de calidad,
tiene muchas aplicaciones en
diferentes áreas.
Las redes de flujo son una

herramienta adecuada para
abordar este tipo de problemas.
2.4
Problema de Flujo Máximo
Definición:
Existe un flujo que viaja
desde un único lugar de
origen hacia un único
lugar de destino a travéz de Origen Destino
arcos que conectan nodos
intermediarios. Los arcos
tiene una capacidad
máxima de flujo, y se trata
de enviar desde la fuente al
destino la mayor cantidad
posible de flujo.
2.4
La aplicación en al vida real de las redes de flujo normalmente son usadas para modelar
líquidos (agua, aceite, petróleo)) que fluyen a través de tubos o la corriente eléctrica
que se transmite a través de redes eléctricas,datos que se transmiten por redes
informáticas, en definitiva, simulan transferencias entre nodos de una red.
2.4
Definicines Básicas:
Flujo: Envío o circulación de unidades homogéneas de algún producto:

automóviles en una red de carreteras, litros de petróleo en un oleoducto, bits por
un cable de fibra óptica) desde el origen o fuente al destino, también
denominado sumidero o vertedero, que atraviesa una superficie en una unidad de
tiempo.
Capacidad de Flujo: Cantidad máxima de flujo que puede ingresar a travéz
del nodo de fuente y salir por el nodo destino
Origen o fuente del flujo : Es el nodo por el cuál el flujo ingresa
Destino, sumidero o vertedero del flujo : Es el nodo por el cuál el flujo sale
Capacidades Residuales: Capacidades restantes del arco, una vez pasado
algún flujo por él.
2.4
Para encontrar el flujo máximo en una red, el Algoritmo es el siguiente:
3 1. Prepara el grafo (Sentido del flujo, Nodo

A D 9 Inicial, Final, cuáles son los valores de flujo que
pasan entre los arcos)
8
4 2. Identificar los valores más altos del
I 7 5 T
flujo ( Esto se hace, para que el algoritmo siga
B los valores máximos de flujo, de nodo en nodo ,
6 2 Terminal hasta encontrar el flujo máximo en la red)
Inicio E
3 3. Tener claro el flujo máximo y la
2 ruta de ese flujo (No exceder la
C capacidad del instrumento físico que
transportará el flujo)
4. Actualizar el grafo (Regresar al punto
inicial y seguir las iteraciones del algoritmo)
5. Regresar al punto 2
2.4 Problema de Flujo Máximo
Ejercicio en clase
Encontrar el Flujo máximo que pueda pasar por la siguiente red, esta red
supondremos que representa el agua que pasa por los tubos de PVC
para surtir de agua a las casa representadas por los nodos, donde el
nodo I es el inicio y el nodo T es el nodo sumidero:
0 A 3 0 Paso 1: Poner 0 a todos los nodos sumideros,
D 9
0 0 indicando que de inicio no se ha pasado nada
8 de flujo.
0
I 7 0 4 T
5 0
B
6 2 Terminal
Inicio
0 E
0 3 0
2
C
Ejercicio en clase
3-3=0
0+3=3 A 0+3=3 Paso 2: Definir la primera ruta de flujo
D 9-3=6
0 Máximo,
0+3=3
8-3=5 iniciando en I.
4 0 T
I 7 0 5
B 0 De I, el flujo máximo que sale es 8.
6 2 Terminal
Inicio 0 E Ruta : I – A – D – T = 3 (Actualizamos sistema)
0 3 0
2
C
Nota: El camino A – D queda cancelado, ya
no se puede usar
Ejercicio en clase
3-3=0
0+3=3 A 0+3=3 Paso 3: Volvemos al punto 2 del algoritmo,
D 9-3=6
0 Identificar la segunda ruta de flujo Máximo,
0+3=3
8-3=5 iniciando nuevamente en I.
7-5=2 4 0+5=5 T
I 0+5=5 5-5=0
B 0 De I, el segundo flujo máximo que sale es 7.
6
Inicio 2 Terminal
0 E Ruta : I – B – T = 5 (Actualizamos sistema)
0 3 0
2
C Nota: El camino B – T queda cancelado, ya
no se puede usar.
Ejercicio en clase
3-3=0
D 9-3=6-3=3
0+3=3 0+3=3+3=6
Identificar la siguiente ruta de flujo Máximo,
7-5=2 4-3=1 0+5=5 T
I 0+5=5 5-5=0
B 0 De I, el siguiente flujo máximo que sale en
6-3=3
2 Terminal esta ocasión es 6.
Inicio 0+3=3 E
3-3=0 0 Ruta : I – C – B – D - T = 3 (Actualizamos
0+3=3 2 sistema)
C
Nota: El camino C – B queda cancelado, ya

no se puede usar.
Ejercicio en clase
3-3=0
D 9-3=6-3=3
0+3=3 0+3=3+3=6
Identificar la siguiente ruta de flujo Máximo,
7-5=2 4-3=1 0+5=5 T
I 0+5=5 5-5=0
B De I, el siguiente flujo máximo que puede
6-3=3 0+2=2
salir sin tener rutas bloqueadas es el 3
Inicio 3-2=1 0+3=3 E
Terminal
3-3=0 2-2=0
Ruta : I – C – E – T = 2 (Actualizamos sistema)
0+3=3 0+2=2
3+2=5 C
2-2=0 Nota: El camino C – E - T queda cancelado,
ya no se puede usar.
Ejercicio en clase
3-3=0
D 9-3=6-3=3-1=2
0+3=3+1=4 0+3=3+3=6+1=7 Identificar la siguiente ruta de flujo Máximo,
7-5=2-1=1 4-3=1-1=0 0+5=5 T
I 0+5=5+1=6 5-5=0
6-3=3 B De I, el siguiente flujo máximo que puede
0+2=2
3-2=1 salir sin tener rutas bloqueadas es el 2
Inicio 0+3=3 Terminal
E 2-2=0
3-3=0 Ruta : I – B – D – T = 1 (Actualizamos sistema)
0+3=3 0+2=2
3+2=5 C
2-2=0 Nota: El camino B – D - T queda cancelado,
ya no se puede usar.
Ejercicio en clase
0+3=3
3-3=0
0+3=3 El Flujo Máximo que se puede enviar es:
A D 9-3=6-3=3-1=2
0+3=3+1=4 0+3=3+3=6+1=7 Ruta : I – A – D – T = 3
8-3=5
7-5=2-1=1 4-3=1-1=0 0+5=5
Ruta : I – B – T = 5
I T
0+5=5+1=6 5-5=0 Ruta : I – C – B – D - T = 3
6-3=3 B
0+2=2
3-2=1 Terminal Ruta : I – C – E – T = 2
Inicio 0+3=3 E
3-3=0 2-2=0
0+3=3 0+2=2
Ruta : I – B – D – T = 1
3+2=5 C
2-2=0 Informe administrativo:
El FM para esta red es la suma de todos
los flujos de las rutas encontradas:
FM= 14 unidades de flujo
2.4 Problema de Flujo Máximo Manual
Video Explicación Algoritmo de Flujo Máximo
https://youtu.be/fDZEwnucLOQ
Determinar la Capacidad máxima que puede circular por la red, utilizando PL
Red ferroviaria, de carreteras,
flujo de líquidos, gases, electricidad
Paso 1: Definir Variables de Decisión:
𝑿𝒊-𝒋: Cantidad de flujo en el arco i,j para todo i y j factibles
𝑪𝒊-𝒋: Capacidad de flujo en el arco i,j para todo i y j factibles
𝑿 𝟏-𝟐 𝑿 𝟏-𝟑 𝑿 𝟏-𝟒 𝑿 𝟐-𝟑 𝑿 𝟐-𝟓 𝑿 𝟑-𝟒 𝑿 𝟑-𝟓 𝑿 𝟒-𝟑 𝑿 𝟒-𝟓
Paso 2: Definir la Función Objetivo

Maximizar la cantidad de flujo que se traspasa de un nodo de origen a un nodo destino, ya sea de
los arcos salientes del nodo de origen o de los arcos entrantes al nodo de origen:
𝑴𝒂𝒙 𝒁 𝑵𝒐𝒅𝒐 𝒐𝒓𝒊𝒈𝒆𝒏: 𝑿 𝟏-𝟐 + 𝑿 𝟏-𝟑 + 𝑿 𝟏-𝟒
𝑴𝒂𝒙 𝒁 𝑵𝒐𝒅𝒐 𝒅𝒆𝒔𝒕𝒊𝒏𝒐: 𝑿 𝟐-𝟓 + 𝑿 𝟑-𝟓 + 𝑿 𝟒-𝟓

Paso 3: Definir Restricciones: Las restricciones se construyen con la fórmula de
conservación de flujo
Flujo total que entra = Flujo total que sale
Características del problema de Flujo máximo:
1. No hay ecuaciones o restricciones de flujo para el nodo inicial y el nodo final
2. El objetivo es maximizar el flujo de salida total en el nodo inicial y de forma equivalente
maximizar el flujo de entrada al nodo final
(Nodo 2) 𝑿 𝟏–𝟐 = 𝑿 𝟐–𝟑 +𝑿 𝟐–𝟓
(Nodo 3) 𝑿 𝟏–𝟑 + 𝑿 𝟐–𝟑 + 𝑿 𝟒–𝟑 = 𝑿 𝟑-𝟒 + 𝑿 𝟑-𝟓
(Nodo 4) 𝑿 𝟏–𝟒 = 𝑿 𝟒–𝟑 + 𝑿 𝟒–𝟓

Por lo tanto el modelo final será:
𝑴𝒂𝒙𝒊𝒎𝒊𝒛𝒂𝒓 𝒁 ∶ 𝑿 𝟏-𝟐 + 𝑿 𝟏-𝟑 + 𝑿 𝟏-𝟒

Sujeto a:
(Nodo 2): 𝑋1-2 − 𝑋2-3 − 𝑋 2-5 = 0

(Nodo 3): 𝑋1-3 + 𝑋2-3 + 𝑋4-3 − 𝑥 3-4 − 𝑋 3-5 = 0
(Nodo 4): 𝑋1-4 − 𝑋234 − 𝑋 0 = 5 -4
𝑿 𝟏–𝟐 ,𝑿 𝟏–𝟑 ,𝑿 𝟏–𝟒 ,𝑿 𝟐–𝟑 ,𝑿 𝟐–𝟓 ,𝑿 𝟑–𝟓 ,𝑿 𝟑–𝟒 ,𝑿 𝟒–𝟑 ,𝑿 𝟒–𝟓 ≥𝟎

2.4 Tarea 2: Problema de Flujo Máximo
• Encuentra el modelo matemático que representa a la red del dibujo.
• Encuentra el Flujo máximo que puede pasar entre el Nodo AI y el nodo
GT utilizando Solver de Excel.
• Reporta tu resultado en el Informe Administrativo
0 4
B 0
6 0 E 4
0
AI 1 GT
4
0 0
C 3
Origen/ 1 Destino/
Inicio 3 Termino
0 9
F
0
0
0 D 4
2.5 Problema de Flujo Máximo Programación Lineal (PL)
Video de apoyo Problema de Flujo Máximo resuelto utilizando Solver de excel
https://youtu.be/q08CBOVybIA
2.3
Problema de Árbol de Mínima Expansión
•Árbol: Es un grafo en el que existe un

V1
único nodo desde el que se puede
acceder a todos los demás y cada nodo
V2
tiene un único predecesor, excepto el V4
primero, que no tiene ninguno.

También podemos definir un árbol V3
como: V6
V5
• Un grafo conexo y sin ciclos.
• Un grafo sin ciclos y con
• n-1 aristas, siendo n el número de
vértices o nodos.
2.3
•Se denominan hojas en un árbol a los
nodos finales (v3, v5 y v6). V1
•Un árbol de máximo alcance es aquel V2 V4

que obtenemos en un grafo conexo y
sin ciclos.
V3
•Árbol de mínima expansión: Árbol de V5 V6
máximo alcance cuyo valor es mínimo,

es decir, la suma de s u s aristas es
mínima.
2.3
1
5
5
Este problema surge cuando 4 4

6
todos los nodos de una red 5 6 8
deben conectarse entre ellos, 2
2 4
sin formar un loop o ciclo. 2

3 6
2.3
El algoritmo del árbol de expansión
mínima es un modelo de 1
5
5
optimización de redes que consiste
4 4
en enlazar todos los nodos de la red 6
de forma directa y/o indirecta con el 5 6 8
objetivo de que la longitud total de
2 4
los arcos o ramales sea mínima 2
(entiéndase por longitud del arco 2
3 6
una cantidad variable según el
contexto operacional de
minimización, y que puede bien
representar una distancia o unidad
de medida).
2.3
1
5
5
La aplicación de este 4
4
modelo 6
tiene como finalidad 5 6 8
conectar todos los 2 4
2
nodos de un sistema de
redes con la mínima 2
3 6
distancia de conexión
posible.
2.3
Su aplicación en al vida real es en instalaciones de cable, tuberías,
carreteras, entre otros.
2.3
Ejercicio en clase:
Se tiene la siguiente red, que representa una colonia Residencial
8 9
4
1 3
8 12 Los nodos representan
casas y se quiere
11 20 5 instalar una red
19
16
eléctrica que de
9
10 energía a todas ellas
2
17 6
20 7
2.3
Paso 1: Hacer una tabla
Nodos no Nodos Distancia entre

8 9
1 3 4 conectados Conectados nodos
conectados
8 12
1,2,3,4,5,6 - -
11 20 5
19
16
9
10
2
17 6
20 7
2.3
Paso 2: Elegir un nodo de inicio
Se le dice al algoritmo que el nodo 3 es por el que hay que iniciar:

8 9 conectados Conectados nodos
1 3 4
conectados
8 12
1,2,3,4,5,6,7 - _
11 20 5 1,2,4,5,6,7 3 -
19
16 9
10
2
17 6
20 7
2.3
Paso 3:
Una vez elegido el nodo inicial Nodos no Nodos Distancia entre
en este caso el nodo 3, el conectados Conectados nodos
algoritmo empieza a trazar conectados
una ruta, hacia donde pueden 1,2,3,4,5,6,7 _ _
ir las conecciones y que este
camino sea el de menor 1.2.4.5.6.7 3 _
distancia 1,2,4,6,7 3,5 8
8 9 4
1 3
8 12
20 El algoritmo elige el nodo 5
11 5
16 19
9 10
2
17 6
20 7
2.3
Paso 4:
Ahora el algoritmo elige el Nodos no Nodos Distancia entre
nodo 1, saliendo del nodo 3, conectados Conectados nodos
ya que eran los dos caminos conectados
con menor distancia de ese 1,2,3,4,5,6,7 _ _
nodo (3). 1.2.4.5.6.7 3 _
8 9 4 1,2,4,6,7 3,5 8
1 3
8 12
2,4,6,7 3,5,1 8
20
11 5
16 19
9 10
2
17 6
20 7
2.3
Paso 5:
Ahora el algoritmo elige otro Nodos no Nodos Distancia entre
nodo que se conecte al nodo conectados Conectados nodos
inicio, elige el nodo 4, que conectados
falta conectarlo y a su vez es 1,2,3,4,5,6,7 _ _
la distancia más corta. 1.2.4.5.6.7 3 _
8 9 4 1,2,4,6,7 3,5 8
1 3
8 12
2,4,6,7 3,5,1 8
20
11 5 2,6,7 3,5,1,4 9
16 19
9 10
2
6
17
20 7
2.3
Paso 6: Nodos no Nodos Distancia entre

Ahora se elige el nodo 6, a conectados Conectados nodos
conectados
partir del nodo 5
1,2,3,4,5,6,7 _ _
8 1.2.4.5.6.7 3 _
9 4
1 3
12 1,2,4,6,7 3,5 8
8
20 2,4,6,7 3,5,1 8
11 5
16 19
9 2,6,7 3,5,1,4 9
10
2 2,7 3,5,4,1,6 9
17 6
20 7
2.3

Paso 7: conectados Conectados nodos
Ahora se elige el nodo 7, a conectados
parir del nodo 5 1,2,3,4,5,6,7 _ _
1.2.4.5.6.7 3 _
8 9 1,2,4,6,7 3,5 8
1 3 4
8 12 2,4,6,7 3,5,1 8
20
11 5 2,6,7 3,5,1,4 9
16 19
9 10 2,7 3,5,1,4,6 9
2 2 3,5,1,4,6,7 10
17 6
20 7
2.3
Paso 8:
Ahora el algoritmo elige el conectados Conectados nodos
nodo 2, escogiendo el conectados
nodo de menor distancia 1,2,3,4,5,6,7 _ _
que lleguea él
1.2.4.5.6.7 3 _
8 9 1,2,4,6,7 3,5 8
1 3 4
8 12 2,4,6,7 3,5,1 8
20
11 5 2,6,7 3,5,1,4 9
16 19
9 10 2,7 3,5,1,4,6 9
2 2 3,5,1,4,6,7 10
17 6
20 7
-
2.3
Paso 9: conectados Conectados nodos
El algoritmo ya conectó todos conectados
los nodos, realiza el conteo 1,2,3,4,5,6,7 _ _
de la distancia mínima para 1.2.4.5.6.7 3 _
conectar todos los nodos
1,2,4,6,7 3,5 8
8 2,4,6,7 3,5,1 8
9 4
1 3
8 12 2,6,7 3,5,1,4 9
20 2,7 3,5,1,4,6 9
5
11 16 19
9 2 3,5,1,4,6,7 10
10
2 - 3,5,1,4,6,7,2 11
17 6
20 7 Total 55
2.3
Solución al problema de Árbol de
mínima Expansión trazada:
conectados Conectados nodos
conectados
La mínima expansión de esta red es
1,2,3,4,5,6,7 _ _
de 55 unidades de distancia,
conectando todos los nodos, sin 1.2.4.5.6.7 3 _
que exista un ciclo entre ellos.
1,2,4,6,7 3,5 8
Distancia Total: 55 2,4,6,7 3,5,1 8
1 3 4 2,6,7 3,5,1,4 9
2,7 3,5,1,4,6 9
5
2 3,5,1,4,6,7 10
2 3,5,1,4,6,7,2 11
6 7
Total 55
2.3
Tarea Problema de Árbol de Mínima Expansión
El problema
La ciudad de Chihuahua cuenta con un nuevo plan parcial de vivienda el cual contará con la
urbanización de más de 7 proyectos habitacionales que se ubicarán a las afueras de la
ciudad. Dado que el terreno en el que se construirá no se encontraba hasta ahora dentro de
las zonas urbanizables de la ciudad, el acueducto municipal no cuenta con la infraestructura
necesaria para satisfacer las necesidades de servicios públicos en materia de suministro de
agua. Cada uno de los proyectos de vivienda inició la construcción de un nodo de acueducto
madre, el cual cuenta con las conexiones de las unidades de vivienda propias de cada
proyecto (es decir que cada nodo madre solo necesita estar conectado con un ducto madre del
acueducto municipal para contar con su suministro). El acueducto municipal al ver la
situación del plan parcial debe de realizar las obras correspondientes a la instalación de
ductos madres que enlacen todos los nodos del plan con el nodo Chuviscar (nodo que se
encuentra con suministro de agua y que no pertenece al plan parcial de vivienda, además es
el más cercano al mismo), la instalación de los ductos implica obras de excavación, mano de
obra y costos de los ductos mismos, por lo cual optimizar la longitud total de los enlaces es
fundamental. Las distancias existentes (dadas en kilómetros) correspondientes a las rutas
factibles capaces de enlazar los nodos del plan parcial se presentan a continuación. Además
la capacidad de bombeo del nodo Chuviscar es más que suficiente para satisfacer las
necesidades de presión que necesita la red madre.
2.3
Tarea Problema de Árbol de Mínima Expansión
Encuentra la distancia existente (en kilómetros) correspondiente a las rutas mas
factibles, capaz de enlazar los nodos del plan, utiliza el método de la tabla de nodos no
conectados, nodos conectados y distancia entre nodos conectados, visto en clase.
3 5
4 4 2
7
6 4 7
4
2 6 3
1 Chuviscar 2
5
4
9
5
4
8
3
3
2.3 Video de apoyo Árbol de expansión Mínima
Tema 2 C onclusión: Optimización de redes
Diferencias entre los Modelos de Optimización de redes

Modelo Característica Aplicación
Ruta más corta Que la red esté unida con la Minimizar tiempo, dinero,
mínima distancia entre los distancias, ect.
nodos
Árbol de Expansión Mínima Consiste en encontrar el Dotar de tuberíauna unidad
mínimo conjunto de enlaces habitacional, esa tubería
en una red, considerando un puede transportar drenaje,
nodo cualquiera que conecte agua potable, etc.
todos los nodos de la red Dotar de cableado eléctrico
una casa, colonia, etc.
Flujo máximo Pasar atravéz de la red una Agua que circula por
capacidad máxima de flujo tuberías, Datos de internet,
corriente que pasa por
cableado,
2.6
Uso de Sofware en Optimización de redes
Algunos Software utilizados son: Winqsb y Solver de excel, nosotros utilizaremos Solver de excel
USO DE SOFTWARE EN OPTIMIZACIÓN DE REDES

TIPOS DE PROBLEMAS DONDE SE PUEDE USAR ALGÚN SOFTWARE
Flujo de redes o modelo de trasbordo
Problema de Transporte
Problema de Asignación
Problema de la Ruta más Corta

Arbol de mímima expansión

Problema del Agente Viajero

Tema 2 Optimización de Redes Ene-Jun 2023

Cargado por

Copyright:

Formatos disponibles

Tema 2 Optimización de Redes Ene-Jun 2023

Cargado por

Información del documento

Descripción original:

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

Tema 2 Optimización de Redes Ene-Jun 2023

Cargado por

Copyright:

Formatos disponibles

5to

La Optimización de redes es un tipo especial de

ANALISIS DE FLUJO DE REDES

Con el objetivo de encontrar la ruta mas

la técnica, algoritmo o el modelo inicio

adecuado es el de la ruta más corta;

representación abstracta de procesos o actividades, inicio

tales como el camino crítico en las actividades entre

Los problemas de optimización de redes se

• Modelo de minimización de redes (Problema fi n

• Modelo de larutamás corta.

• Modelo del flujo máximo.

• Modelo del flujo del costo mínimo.

ü Requieren en forma natural de

permitirá resolver tipos especiales de

Obviamente los modelos de redes no son

2.1 2.3 2.4

2.5 2.6 2.7

Que es un Nodo Fuente?

El nodo fuent e es aquel nodo en el cual t odos sus

Que es un Nodo Destino?

Que es una Cadena?

Una cadena corresponde a una serie de elementos

Que es una Ruta?

Una rut a corresponde a los nodos que

Un ciclo corresponde a la cadena que une a un nodo

Que es un Ramal Orientado?

Un ramal o arco orientado es aquel que tiene un

Que es una Red o grafo Orientado?

Una red o dibujo orientado es aquel en el cual todos

Que es un Árbol de expansión?

1) Programación Lineal: Función Objetivo y restricciones lineales

Los m odelos de redes tam bién pueden expresarse co m o m odelos de

La Programación Entera permite abordar de fo rm a eficiente este

Problemas del mundo

El algoritmo de Dijkstra, también llamado algoritmo de

𝑿𝒊-𝒋 : 𝟏 𝑺𝒊 𝒆𝒍 𝒏𝒐𝒅𝒐 𝒋 𝒆𝒔 𝒗𝒊𝒔𝒊𝒕𝒂𝒅𝒐 𝒊𝒏𝒎𝒆𝒅𝒊𝒂𝒕𝒂𝒎𝒆𝒏𝒕𝒆 𝒅𝒆𝒔𝒑𝒖é𝒔 𝒅𝒆𝒍 𝒏𝒐𝒅𝒐 𝒊

8 17 Nota: En teoría de grafos, una red de flujo es

𝑿𝒊-𝒋 : 𝟏 𝑺𝒊 𝒆𝒍 𝒏𝒐𝒅𝒐 𝒋 𝒆𝒔 𝒗𝒊𝒔𝒊𝒕𝒂𝒅𝒐 𝒊𝒏𝒎𝒆𝒅𝒊𝒂𝒕𝒂𝒎𝒆𝒏𝒕𝒆 𝒅𝒆𝒔𝒑𝒖é𝒔 𝒅𝒆𝒍 𝒏𝒐𝒅𝒐 𝒊

8 17 Nota: En teoría de grafos, una red de flujo es

𝑿𝒊-𝒋 : 𝟏 𝑺𝒊 𝒆𝒍 𝒏𝒐𝒅𝒐 𝒋 𝒆𝒔 𝒗𝒊𝒔𝒊𝒕𝒂𝒅𝒐 𝒊𝒏𝒎𝒆𝒅𝒊𝒂𝒕𝒂𝒎𝒆𝒏𝒕𝒆 𝒅𝒆𝒔𝒑𝒖é𝒔 𝒅𝒆𝒍 𝒏𝒐𝒅𝒐 𝒊

8 17 Nota: En teoría de grafos, una red de

𝑿𝒊-𝒋 : 𝟏 𝑺𝒊 𝒆𝒍 𝒏𝒐𝒅𝒐 𝒋 𝒆𝒔 𝒗𝒊𝒔𝒊𝒕𝒂𝒅𝒐 𝒊𝒏𝒎𝒆𝒅𝒊𝒂𝒕𝒂𝒎𝒆𝒏𝒕𝒆 𝒅𝒆𝒔𝒑𝒖é𝒔 𝒅𝒆𝒍 𝒏𝒐𝒅𝒐 𝒊

8 17 Nota: En teoría de grafos, una red de flujo es

Finalmente la restricción del nodo (8) asegura que ya sea el nodo 7, 4 o 6

• Redes de comunicación, • Redes de telefonía,

• Redes de transporte, • Redes de energía eléctrica,

Las redes de flujo son una

Flujo: Envío o circulación de unidades homogéneas de algún producto:

3 1. Prepara el grafo (Sentido del flujo, Nodo

Nota: El camino C – B queda cancelado, ya

𝑿𝒊-𝒋: Cantidad de flujo en el arco i,j para todo i y j factibles

𝑪𝒊-𝒋: Capacidad de flujo en el arco i,j para todo i y j factibles

𝑿 𝟏-𝟐 𝑿 𝟏-𝟑 𝑿 𝟏-𝟒 𝑿 𝟐-𝟑 𝑿 𝟐-𝟓 𝑿 𝟑-𝟒 𝑿 𝟑-𝟓 𝑿 𝟒-𝟑 𝑿 𝟒-𝟓

Paso 2: Definir la Función Objetivo

𝑴𝒂𝒙 𝒁 𝑵𝒐𝒅𝒐 𝒅𝒆𝒔𝒕𝒊𝒏𝒐: 𝑿 𝟐-𝟓 + 𝑿 𝟑-𝟓 + 𝑿 𝟒-𝟓

(Nodo 2) 𝑿 𝟏–𝟐 = 𝑿 𝟐–𝟑 +𝑿 𝟐–𝟓

(Nodo 3) 𝑿 𝟏–𝟑 + 𝑿 𝟐–𝟑 + 𝑿 𝟒–𝟑 = 𝑿 𝟑-𝟒 + 𝑿 𝟑-𝟓

(Nodo 4) 𝑿 𝟏–𝟒 = 𝑿 𝟒–𝟑 + 𝑿 𝟒–𝟓