Investigacion De Operaciones

Modelos de Redes: Árbol
rbol
de expansión mínima
de
M. En C. Eduardo Bustos Farías

Objetivos
Objetivos
Conceptos y definiciones de redes.
Conceptos
Importancia de los modelos de redes
Importancia
Modelos de programación lineal, representación en
Modelos
en
redes y soluciones usando el computador para:
redes
* Modelos de asignación
* Modelo del vendedor viajero
* Modelos de laruta mas corta
* Modelos de la rama mas corta
Y otros.

6

8

Un problema de redes es aquel que puede
Un
redes es
representarse por:

10

9

7

Nodos

10

Arcos

Funciones en los arcos

Introducción
Introducci
La importancia de los modelos de redes:
La
* Muchos problemas comerciales pueden ser resueltos a través
de modelos redes
de
* El resultado de un problemade redes garantiza una solución
entera, dada su estructura matemática. No se necesitan
entera,
tica.
restricciones adicionales para obtener este tipo de solución.
restricciones
* Problemas de redes pueden ser resueltos por pequeños
os
algoritmos , no importando el tamaño del problema, dada su
algoritmos
del
estructura matemática.
estructura

Terminología de Redes
Terminolog
*Flujo: Corresponde a la cantidad que debe transportarse
Flujo: Corresponde
desde un nodo i a un nodo j a través de un arco que los
conecta. La siguiente notación es usada:

Xij= cantidad de flujo
Uij= cota mínima de flujo que se debe transportar
Lij= cota maxíma de flujo que se puede transportar.
* Arcos dirigidos /no dirigidos: Cuando el flujo puede
Arcos
Cuando
transportarse en una soladirección se tiene un arco dirigido (la
flecha indica la dirección). Si el flujo puede transportarse en
ambas direcciones existe un arco no dirigido (sin flecha).
* Nodos adyacentes: Un nodo j es adyacente con un nodo i si
Nodos
existe un arco que une el nodo j con el nodo i.

Rutas/Conexión entre nodos
Rutas/Conexi
*Ruta: Una colección de arcos formados por una serie de
Una
nodosadyacentes
* Los nodos están conectados si existe una ruta entre ellos.

Ciclos / Arboles /Arboles expandidos
Ciclos
* Ciclos : Un ciclo se produce cuando al partir de un nodo por
un cierto camino se vuelve al mismo nodo por otra ruta.
* Arbol : Una serie de nodos que no contienen ciclos.
*Arbol expandido: Es un árbol que conecta todos lo nodos de
expandido: Es
la red (contiene n-1 arcos).Árbol de expansión mínima

7

Árbol de expansión mínima
Este problema surge cuando todos los nodos de una
Este
red deben conectar entre ellos, sin formar un loop.
Ell árbol de expansión mínima es apropiado para
E
nima
problemas en los cuales la redundancia es
expansiva, o el flujo a lo largo de los arcos se
considera instantáneo.
considera

8

Árbol de expansión mínima
Esteproblema se refiere a utilizar las ramas o arcos de
Este
la red para llegar a todos los nodos de la red, de manera
tal que se minimiza la longitud total.
La aplicación de estos problemas de optimización se
La
se
ubica en las redes de comunicación eléctrica, telefónica,
ubica
nica,
carretera, ferroviaria, aérea, marítima, etc.; donde los
carretera,
tima,
nodos representan puntos deconsumo eléctrico,
nodos
ctrico,
teléfonos, aeropuertos, computadoras.
tel
Y los arcos podrían ser de alta tensión, cable de fibra
los
n,
óptica, rutas aéreas, etc.
Sii n = numero de nodos, entonces la solución óptima
S
ptima
debe incluir n-1 arcos.
debe
9

Algoritmo de Kruskal
Algoritmo
Kruskal

10
10

Algoritmo de Kruskal
Algoritmo
Kruskal
1.

2.

3.

Comenzar enforma arbitraria en cualquier
Comenzar
nodo y conectarlo con el mas próximo (menos
nodo
ximo
distante o costoso).
distante
Identificar el nodo no conectado que esta más
cera o menos costoso de alguno de los nodos
conectados. Deshacer los empates de forma
arbitraria. Agregar este nodo al conjunto de
nodos conectado.
nodos
Repartir este aso hasta que se hayan
Repartir
conectado...