Pregrado
Semana 11
Modelos de Redes
LOGRO DE LA SESIÓN
● Resuelve problemas de árbol de expansión mínima, flujo
mínimo y flujo máximo.
● Resuelve problemas de redes de forma analítica y
usando software especializados
Introducción
● Las redes sirven para modelar una amplia gama de
problemas.
● En la unidad anterior vimos los problemas de transporte,
trasbordo y asignación modelados como redes.
● Se utilizó programación lineal para resolverlos y se
presentaron también otras técnicas.
INTRODUCCION
La Teoría de Grafos nace del análisis sobre una inquietud presentada en la
isla Kueiphof en Koenigsberg (Pomerania) ya que el río que la rodea se
divide en dos brazos.
Sobre los brazos estaban construidos siete puentes y para los habitantes
era motivo de distracción descubrir un itinerario de manera que pudieran
regresar al punto de partida, después de haber cruzado por los siete
puentes pero pasando sólo una vez por cada uno de ellos.
4
EL PROBLEMA DE LOS PUENTES DE KONIGSBERG
http://youtube.com/watch?v=3kU6671KCNI&ab_channel=EleanorAbernathy
EL PROBLEMA DE LOS PUENTES DE KONIGSBERG
https://www.youtube.com/watch?v=m_IT0RNZRw8&ab_channel=math2me
GRAFO: DEFINICIÓN
✓ Es un conjunto de vértices o nodos y un conjuntos de arcos. Se
representa por G = (V, A). G, grafo; V, vértice y A, arco.
✓ Es una estructura no lineal que representa un conjunto de objetos
donde no hay restricción a la relación entre ellos.
✓ Es un concepto matemático que se utiliza para representar circuitos
eléctricos, redes transporte, de alcantarillado, redes de comunicaciones,
mapa de carreteras, etc.
✓ Los grafos se clasifican en dirigidos y no dirigidos.
EJEMPLO
Bogotá 1.500 kms
800 Brasilia
kms
Lima
900
Montevid
kms
eo
Santiag
o
2.000 Buenos Aires
kms
G = (V, A)
V(G) = nodos o A(G) = arcos o aristas
vértices (ciudades) (medio de
conexión)
CONCEPTOS IMPORTANTES
Vértice: también es llamado nodo.
Arista: es la conexión de un nodo con otro adyacente.
Camino: secuencia de aristas recorridas para ir desde un nodo origen
hasta uno destino.
Un camino simple es un camino desde un nodo a otro en el que ningún
nodo se repite (no se pasa dos veces). Si el camino simple tiene como
primer y último elemento al mismo nodo se denomina bucle.
Longitud de un camino: es el número de arcos que componen el
camino.(es la suma de los valores numéricos asociados a los arcos que lo
constituyen)
Bucle: camino que une un nodo consigo mismo. Comienza y termina en
el mismo nodo.
Orden: es el número de nodos (vértices) del grafo.
VERTICES
● Son los puntos o nodos
con los que esta
conformado un grafo.
● Llamaremos grado de
un vértice al número de
aristas de las que es
extremo. Se dice que
un vértice es `par' o
`impar' según lo sea su
grado.
CONCEPTOS IMPORTANTES
Nodos Adyacentes: dos nodos son adyacentes si comparten
la misma arista.
Grado de un nodo x: en un grafo no dirigido, es el número de
aristas que contiene a x. En un nodo dirigido grado de
entrada, es el número de arcos que llegan a x, y grado de
salida es el número de arcos que salen de x.
Grafo valorado: cuando los arcos tienen asociados un factor
de peso.
Grafo conexo: es un grafo no dirigido tal que para cualquier
par de nodos existe al menos un camino que los une.
CONCEPTOS IMPORTANTES
● Arista
○ Es un arco de un grafo no dirigido
9
● Vertices adyacente Chiclayo Lambayeque
○ Vertices unidos por un arco 8
7
● Factor de Peso
○ Valor que se puede asociar con un Pátapo
Pomalca
arco 5
7
○ Depende de lo que el grafo
represente
○ Si los arcos de un grafo tienen F.P. 5
■ Grafo valorado
Mocupe
Grafo completo, disperso y denso.
Según el número de aristas que contiene, un grafo es completo si cuenta
con todas las aristas posibles (es decir, todos los nodos están conectados
con todos), disperso si tiene relativamente pocas aristas y denso si le
faltan pocas para ser completo.
El número de distintos pares de vértices (v(i), v(j)), con v(i) <> v(j), en un
grafo con n vértices es n*(n-1)/2. Este es el número máximo de arcos en
un grafo no dirigido de n vértices. Un grafo no dirigido que tenga
exactamente n*(n-1)/2 arcos se dice que es un grafo completo.
En el caso de un grafo dirigido de n vértices el número máximo de arcos
es n*(n-1).
TIPOS DE GRAFOS
● Dirigidos: Cada arco está ● No dirigidos: El par de
representado por un par vértices que representa
ordenado de vértices. un arco no está ordenado.
Grafos dirigidos.
Un grafo es dirigido si los pares de nodos que forman los
arcos son ordenados,
es decir, un nodo puede ser
apuntado por otros nodos,
se representa con u v
El conjunto de vértices
V = {C,D,E,F,H} y
el conjunto de arcos
A = { (C,D), (D,F),
(E,H), (H,E), (E,C) }
forman el grafo dirigido G = {V, A}.
Grafos no dirigidos.
Un grafo no dirigido es el que tiene los arcos
formados por pares de nodos no ordenados, un nodo
está relacionado con otro nodo, se representa con u
v
El conjunto de vértices
V = {1,4,5,7,9}
y el conjunto de arcos A = { (1,4),
(5,1), (7,9), (7,5), (4,9), (4,1),
(1,5), (9,7), (5,7), (9,4) } forman
el grafo no dirigido
G = {V, A}.
TIPOS DE GRAFOS
C E ● Grafos dirigidos
○ Si los pares de nodos que
forman arcos
F ○ Son ordenados. Ej.: (u->v)
D H
1 4
V = {C, D, E, F, H}
A= {(C,D), (D,F), (E,H), (H,E),
(E,C)} 5
Grafos no dirigidos 7 9
Si los pares de nodos de los arcos
Grafo del ejemplo
No son ordenados Ej.: u-v anterior
Ejemplos de grafos
Grafo conexo: es un grafo no dirigido tal que para cualquier par
de nodos existe al menos un camino que los une.
Grafo fuertemente conexo: es un grafo dirigido tal que para
cualquier par de nodos existe un camino que los une.
Ejemplos de grafos
Grafo valorado: cuando los arcos tienen asociados un
factor de peso.
Grafo valorado dirigido: cuando los arcos tienen
asociados un factor de peso.
19
EJEMPLO
Los nodos c y e tienen grado 4, el nodo d tiene
a b grado 6 y los demás nodos tiene grado 5
Existe un lazo o bucle en el nodo d
Es multigrafo ya que existen dos aristas que unen
los vértices a y b
Existen varios caminos que unen el nodo a y el
nodo d Ej. a-b-c-d-a, a-e-d , a-d o a-c-d
El camino a-c-d-a es un camino cerrado
El camino a-c-d-a es un camino simple, mientras
que a-c-b-d-c no lo es.
e c
El camino a-c-d-a es un camino cíclico
No es un Grafo conexo ya que todos los nodos no
tienen un camino a otro nodo
d No es un Grafo completo ya que todos los nodos
f no se conectan con los demás
El nodo f es un nodo aislado
PROBLEMA DEL ÁRBOL DE EXPANSIÓN
MÍNIMA
Árbol
Problema del árbol de expansión mínima
● La técnica del árbol de expansión mínima implica conectar todos los
puntos de una red, al tiempo que minimiza la distancia entre ellos.
● Se aplica, por ejemplo, en las compañías telefónicas para conectar
entre sí varios teléfonos minimizando la longitud total del cable
La técnica del árbol de expansión
mínima conecta los nodos con una
distancia mínima
Aplicaciones
Pasos para la técnica del árbol de expansión mínima
1. Seleccionar cualquier nodo en la red.
2. Conectar este nodo con el nodo más cercano que minimice la
distancia total.
3. Considerar todos los nodos que están conectados, encontrar y
conectar el nodo más cercano que no esté conectado.
Si hay un empate en el nodo más cercano, seleccionar uno de
manera arbitraria. Un empate sugiere que existe más de una
solución óptima.
4. Repetir el paso 3 hasta que todos los nodos estén conectados.
Ejemplo
Considere la compañía Lauderdale Construction, que desarrolla un proyecto
habitacional de lujo en Panama City Beach, Florida. Melvin Lauderdale, dueño y
presidente de Lauderdale Construction, tiene que determinar la forma menos
costosa de suministrar agua y electricidad a cada casa.
Paso 1:
● Seleccionar el nodo 1:Comenzamos con la selección arbitraria del nodo 1.
Segunda y tercera iteraciones
● Paso 2: Como el nodo más cercano es el nodo 3, a una distancia de 2 (200
pies), conectamos el nodo 1 al nodo 3.
● Consideramos los nodos 1 a 3 y buscamos el siguiente nodo más cercano.
Es el nodo 4, que es el más cercano al nodo 3. La distancia es 2 (200 pies).
Cuarta y quinta iteraciones
● Paso 3. Continuamos buscando el nodo más cercano entre los nodos no
conectados 1, 3 y 4. Son el nodo 2 o el nodo 6, ambos a una distancia de 3
del nodo 3. Elegimos el nodo 2 y lo conectamos al nodo 3
Iteraciones sexta y séptima (final)
● En este punto, quedan tan solo dos nodos sin conectar. El nodo 8 es el más
cercano al nodo 6, con una distancia de 1 y lo conectamos.
Resumen de los pasos en el problema del árbol de expansión mínima
Con POM QM
Ejemplo Adicional..
Ejemplo Adicional…
Ejemplo Adicional….
● Roxie LaMothe es dueña de una granja
grande donde cría caballos cerca de
Orlando. Está planeando instalar un
sistema de agua integral que conecte
todos los establos y graneros. La
ubicación de las instalaciones y las
distancias entre ellas se dan en la red
mostrada en la figura. Roxie tiene que
determinar la forma menos costosa de
suministrar agua a cada instalación. ¿Qué
recomendaría usted?
Solución
Se trata de un problema típico del árbol de expansión mínima que es posible
resolver a mano. Se elige el nodo 1 y se conecta con el nodo más cercano, que
es el nodo 3. Los nodos 1 y 2 son los siguientes que se conectan, seguidos de
los nodos 1 y 4. Ahora se conecta el nodo 4 al nodo 7, y el nodo 7 al nodo 6.
En este punto, los únicos puntos restantes para conectar son el nodo 6 al nodo
8, y el nodo 6 al nodo 5.
Solución
PROBLEMA DE LA RUTA MÁS CORTA
Problema de la ruta más corta
● El objetivo del problema de la ruta más corta es encontrar la menor distancia
para ir de un lugar a otro.
● En una red, esto suele implicar la determinación de la ruta más corta de un
nodo a cada uno de los otros nodos. Este problema se resuelve con la
técnica de la ruta más corta, o bien, planteándolo como un programa lineal
con variables 0–1.
● Se presentará un ejemplo para demostrar primero la técnica de la ruta más
corta y, luego, se desarrollará un programa lineal.
Técnica de la ruta más corta
● Todos los días, Ray Design debe transportar camas, sillas y otros
muebles de la fábrica al almacén;
● necesita pasar por varias ciudades y Ray desea encontrar la ruta con la
distancia más corta.
Pasos de la técnica de la ruta más corta
1. Encontrar el nodo más cercano al origen (planta). Colocar la distancia en un
cuadro al lado del nodo.
2. Encontrar el siguiente nodo más cercano al origen (planta) y poner la
distancia en un cuadro al lado del nodo. En algunos casos, deberán revisarse
varias rutas para encontrar el nodo más cercano.
3. Repetir este proceso hasta que se haya revisado la red completa. La última
distancia en el nodo final será la distancia de la ruta más corta. Debería
observar que la distancia colocada en el cuadro al lado de cada nodo será la
distancia de la ruta más corta a ese nodo. Tales distancias se usan como
resultados parciales para encontrar el siguiente nodo más cercano.
Pasos de la técnica de la ruta más corta
● Si observa la figura se obcerva que el nodo más cercano a la planta es el nodo 2,
con una distancia de 100 millas. Se conectan entonces los dos nodos.
● Ahora se busca el siguiente nodo más cercano al origen. Verificamos los nodos 3,
4 y 5. El nodo 3 es el más cercano, pero existen dos trayectorias posibles. La ruta
1–2–3 es la más cercana al origen, con una distancia total de 150 millas.
● Repetimos el proceso. El siguiente nodo más cercano es el nodo 4 o el 5. El nodo
4 está a 200 millas del nodo 2, y el nodo 2 está a 100 millas del nodo 1.
Entonces, el nodo 4 está a 300 millas del origen. Hay dos trayectorias para el
nodo 5, 2–5 y 3–5, desde el origen.
● Advierta que no tenemos que regresar hasta el origen, porque ya conocemos la
ruta más corta de los nodos 2 y 3 al origen.
Iteraciones
Iteraciones
● Las distancias mínimas se colocan en cuadros al lado de estos nodos. La
ruta 2–5 tiene 100 millas y el nodo 2 está a 100 millas del origen. Entonces,
la distancia total es de 200 millas. De manera similar, determinamos que la
trayectoria del nodo 5 al origen por el nodo 3 tiene 190 millas (40 entre el
nodo 5 y el 3 más 150 del nodo 3 al origen). Así, elegimos el nodo 5 que
pasa por el nodo 3 desde el origen
● El siguiente nodo más cercano será el nodo 4 o el 6, como los últimos nodos
que quedan. El nodo 4 está a 300 millas del origen. El nodo 6 está a 290
millas del origen. El nodo 6 tiene la menor distancia y como es el nodo final,
el proceso termina (véase la figura 11.14). La ruta más corta es 1–2–3–5–6,
con una distancia mínima de 290 millas.
Solución
Programación lineal para el problema de la ruta más corta
● El problema de la ruta más corta se puede ver como un tipo especial de
problema de trasbordo con un origen que tiene oferta de 1, un destino con
demanda 1 y varios puntos de trasbordo. Esta clase de problemas se
modela como un programa lineal con variables 0-1. Las variables indicarán
si se elige un arco específico como parte de la ruta tomada.
● Para el ejemplo de Ray Design, el objetivo es minimizar la distancia total
(costo) de inicio a fin.
● Las variables se definen como:
Restricciones
● Como el punto de inicio es el nodo 1, no se incluye una variable que vaya del
nodo 2 o 3 de regreso al 1. De manera similar, como el nodo 6 es el destino
final, no se incluyen variables que comiencen en el nodo 6.
● Al considerar este como un problema de trasbordo, el nodo origen (nodo 1)
debe tener una unidad que se envía desde ahí:
● El nodo destino final (nodo 6) debería tener una unidad enviada ahí y esto se
escribe como:
● Cada nodo intermedio tendrá una restricción que requiere que la cantidad que
llega al nodo sea igual a la cantidad que sale del nodo. Para el nodo 2, esto
sería
Restricciones
● Las otras restricciones se construyen de forma similar. El modelo completo es:
Modelo Compacto
Ejemplo Adicional
● La red de la figura ilustra las carreteras y las ciudades cercanas a Leadville,
Colorado. Leadville Tom, un fabricante de cascos para bicicleta, debe
transportar sus artículos a un distribuidor en Dillon, Colorado.
● Para hacerlo, tiene que pasar por varias ciudades. Tom quiere encontrar la
ruta más corta para ir de Leadville a Dillon. ¿Qué le recomendaría?
Solución
El nodo más cercano al origen (nodo 1) es el nodo 2. La distancia de 8 se coloca en
un cuadro junto al nodo 2. Después, considere los nodos 3, 4 y 5, ya que hay un
arco a cada uno desde el nodo 1 o el 2, y ambos tienen sus distancias establecidas.
El nodo más cercano al origen es el nodo 3, por lo que la distancia que se coloca en
un cuadro al lado del nodo 3 es 14 (8 -6). Entonces, considere los nodos 4, 5 y 6. El
nodo más cercano al origen es el nodo 4, con una distancia de 18 (directamente del
nodo 1). Luego, considere los nodos 5 y 6. El nodo con la menor distancia desde el
origen es el nodo 5 (que pasa por el nodo 2) y esta distancia es 22. Ahora vea los
nodos 6 y 7 y se selecciona el nodo 6,ya que la distancia es 26 (pasando por el nodo
3). Por último, se toma en cuenta el nodo 7 y la distancia más corta desde el origen
es 32 (pasando por el nodo 6). La ruta que da la distancia más corta es 1-2-3-6-7 y
la distancia es 32.
Solución
Ejemplo Adicional
Ejemplo Adicional
Usando Solver
Conclusiones
● Se enseñaron dos problemas de redes importantes: el árbol de
expansión mínimay la ruta más corta.
● Todos ellos se representaron como redes y se mostraron
técnicas de solución específicas. La ruta más corta se
consideran casos especiales del problema de trasbordo, y
ambos se modelaron usando programación lineal con variables
que deben ser enteras o 0 1
● Los dos problemas de redes tienen una amplia gama de
aplicaciones; existen muchos otros tipos de problemas de redes.
Referencias bibliográficas
• Vargas (2009), Presentación, Investigación de Operaciones II,
Universidad Nacional de Ingeniería.
• Macias (2005), Presentación, Grafos, Estructura de datos.
• Taha H.A. (2012). Investigación de Operaciones. México: Pearson.
• Bazaraa M.S., Jarvis J.J. & Sherali H.D. (2011). Programación lineal y flujo
en redes. México: Limusa.
• Hillier F.S. & Liberman G.J. (2010). Introducción a la Investigación de
Operaciones. México: McGraw-Hill..
