analisis
Teoría de Redes
2009
JJMG
Tipos de redes
1
Modelos de Redes
Optimización de redes es un tipo especial de modelo en la
Investigacion de Operaciones.
Pueden resolverse muy rápidamente. Esto permite que modelos de
redes sean usados en muchas aplicaciones para lo cual la
programación lineal no es lo ideal (toma de decisión en tiempo real).
Al reconocer que unproblema de programación entera puede
formularse como algún modelo de red nos entregará soluciones
enteras sin necesidad de restricciones adicionales, aumentando la
eficiencia y reduciendo el tiempo consumido por los algoritmos
clásicos de programación lineal.
Problemas de redes pueden ser resueltos por pequeños algoritmos,
no importando el tamaño del problema, dada su estructura
matemática.Terminología
Una red o grafo consiste en un conjunto de puntos y un conjunto de
líneas que conectan pares de puntos. Los puntos se llaman nodos o
vértices y las líneas se llaman arcos o aristas, estos pueden tener una
dirección asociada, en este caso se denominan arcos dirigidos.
Arcos dirigidos
Nodos
Arcos
2
Terminología
Se denomina flujo al valor que se le asigna a unarco que conecta dos
nodos.
Para nombrar el arco se pone primero el nodo de donde viene, y luego el
nodo hacia donde va. Por ejemplo, si el flujo sólo va desde el nodo C
hacia al nodo D, entonces el arco se llama CD y no DC
4
6
B
Flujo
D
A
3
7
2
Arco CD
E
3
C
G
6
5
4
F
Terminología
Una trayectoria entre 2 nodos es una sucesión de arcos distintosque
conectan estos nodos. Por ejemplo, una trayectoria que conecta al nodo
A con el nodo G es AC - CE - EG.
4
6
B
D
A
3
7
2
E
3
C
5
Trayectoria
G
6
F
4
3
Terminología
Una trayectoria dirigida desde el nodo i al nodo j es una sucesión de
arcos cuya dirección (si la tienen) es hacia el nodo j, de manera que el
flujo del nodo i al nodo j a travésde esta trayectoria es factible.
Una trayectoria no dirigida del nodo i al nodo j es una sucesión de arcos
cuya dirección (si la tienen) puede ser hacia o desde el nodo j.
4
6
B
D
A
3
7
2
GA
Trayectoria
no dirigida
E
3
C
AG
Trayectoria
dirigida
G
6
5
4
F
Terminología
Un ciclo es una trayectoria que comienza y termina en un mismo nodo,
sedenomina ciclo dirigido cuando está formado por una trayectoria
dirigida y ciclo no dirigido cuando la trayectoria que lo conforma es no
dirigida
4
AC - CD - DB - BA
es un ciclo dirigido
6
B
D
A
3
7
2
E
3
C
5
G
6
F
4
GE - EC - CF - FG es
un ciclo no dirigido
4
Ejemplo
Terminología
Dos nodos se encuentran conectados si la red contiene almenos una
trayectoria no dirigida entre ellos. Una red conexa es una red en la que
cada par de nodos está conectado.
Red Conexa
A
Red No Conexa
A
B
B
E
C
E
C
D
D
5
Terminología
La cantidad máxima de flujo que puede circular en un arco dirigido es
llamada capacidad del arco.
El nodo que tiene la propiedad de que su flujo que sale es mayor que el
flujo queentra en él se le llama nodo fuente (o nodo origen). Por el
contrario, si su flujo que sale es menor que el flujo que entra a él se le
llama nodo demanda (o nodo destino). Si el flujo que entra es igual al
flujo que sale, entonces se le llama nodo de trasbordo (o nodo
intermedio)
4
Nodo Fuente
A
Nodo de Transbordo
B
4
3
C
Nodo Demanda
Terminología
Un árbol es una seriede nodos conectados que no contiene ciclos. Un
árbol de expansión es un árbol que conecta todos los nodos de la red
(contiene n -1 arcos, donde n es el número de nodos)
A
B
Árbol ABC
E
C
D
Árbol de Expansión
Árbol ACD
6
Problema del
Árbol de Expansión Mínima
Primer Semestre 2009
JJMG
Problema del Árbol de Expansión Mínima
Este problema considera una red no...
Regístrate para leer el documento completo.