Optimización de redes.

Los problemas de redes surgen en una gran variedad de situaciones como por
ejemplo las redes de transporte, redes eléctricas en fin una inmensa lista que
predominan en la vida diaria

¿Qué es?
Una representación de redes nos proporciona un panorama general poderoso y una
ayuda conceptual para visualizar las relaciones entre los componentes del sistema
que se utiliza casi en todas las áreas científicas, sociales y económicas.

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 representación abstracta
de procesos o actividades, tales como el camino crítico en las actividades entre las
redes de un proyecto gerencial.

Las redes son rutas invisibles sobre las cuales se van a mover los recursos o las
entidades. Para que una red cumpla con su función debe estar unidad a las
locaciones por medio de interfaces. Una red puede estar conformada por muchos
tramos, los cuales están separados por nodos y cada nodo debe tener su respectiva
interfaz. Cuando una red cambia de dirección que no está conectado a una locación,
se habla de punto de quiebre.

Terminología.
Una red o grafo consiste de puntos, y líneas que conectan pares de puntos. Los
puntos se llaman nodos o vértices. Las líneas de llaman arcos. Los arcos pueden
tener una dirección asociada, en cuyo caso se denominan arcos dirigidos.
 Red: Conjunto de puntos y líneas que unen ciertos pares de puntos.
 Nodo: Es un circulo en un diagrama de redes que representan un aspecto
importante de un problema.
 Arcos: Es una línea que conecta dos nodos en un diagrama esquemático
que representa una relación entre dos nodos Líneas, ligaduras, aristas o
ramas. Se etiquetan para dar nombre a los nodos en sus puntos terminales.
  Arco dirigido: Si el flujo a través de un arco se permite sólo en una dirección.
La dirección se indica agragando una cabeza de flecha al final de la línea que
representa el arco.
 Arco no dirigido: Si el flujo a través de un arco se permite en ambas
direcciones.
 Red dirigida: Red que tiene sólo arcos dirigidos.
 Red no dirigida: Todos sus arcos son no dirigidos.
 Trayectoria: Sucesión de arcos distintos que conectan nodos.
 Ciclo: Trayectoria que comienza y termina en el mismo nodo.
 Red conexa: Red en la que cada par de nodos esta conectado.
 Árbol: Red conexa (para algún subconjunto de n nodos) que no contiene
ciclos no dirigidos.

Aplicación.

 Diseñar el trazado de una red de fibra óptica de manera que se cubran ciertos
puntos de la manera más económica posible. Árbol generador de coste
mínimo.

 Determinar la ruta más corta entre dos ciudades. Camino más corto.

 Determinar la cantidad máxima de electricidad que se puede enviar a través

de una red eléctrica. Problema de flujo máximo.

 Decidir el programa de fechas en el que deben iniciarse y terminarse una

serie de tareas para llevar a cabo un proyecto. Camino crıtico (CPM).

 Diseño de una red oleoductos para gas natural a una determinada distancia
de la costa para determinar los cabezales de los pazos en el golfo de México
a un punto de distribución costero con el objetivo de minimizar el costo de
construcción.

 Determinación del itinerario de flujo de costo mínimo desde campos

petroleros hasta una refinería atreves de una red.

 En algunos problemas de optimización puede ser útil representar el problema

a través de una gráfica: ruteo de vehículos, distribución de producto,
programa de actividades en un proyecto, redes de comunicación, etc.
Ejemplo.
Encuentre el flujo máximo de la red que se le muestra a continuación, donde el nodo
inicial es (AI) y el terminal es (GT).

B
4
el
6

1 E 4
AI 4
E C 3 GT
el el
flu
3 F 9
1 jo
m el
áx
D 4
im
o
d
Los problemas de flujos máximos consisten en tratar de llevar desde el Nodo AI la
e
mayor cantidad flujo posible al Nodo destino GT. Tomando en cuenta que los arcos
la
o aristas tienen capacidades diferentes.
re
Este problema se resuelve d por pasos o Iteraciones: En cada paso o iteración
elegimos un camino cualquiera y enviamos la cantidad que permite el arco con
q
menor capacidad de ese camino y vamos reduciendo la capacidad de cada arco
restando lo enviado. u
e
iteración 1: elegimos el camino AI –B –E-GT,en este camino encontramos los
se
arcos AIB, BE, EGT ahora encontramos el mínimo de la capacidad de los arcos:
min {6,4,4} = 4Puede ver que le el mínimo es 4.Puede ver que la red ha a reducido
su capacidad en los arcosm que hemos utilizado.
u
es
tr
a
a
co
nti
 B 0
el
2
6
1 E 0
AI 4 4
E C GT
3
el el
3 9
1 F
el
D 4

Iteración 2: elegimos un nuevo camino AI-C-F-GT,en este camino encontramos los

arcos AIC, CF y FGT, obtenemos el mínimo de la capacidad de los arcos: min
{4,3,9}=3

B 0
el
2
6
1 E 0
AI 1 7
E C GT
0
el el
3 6
1 F
el
D 4

Iteración 3: Puede verse que después de dos iteraciones, hay arcos cuyas
capacidades ya no permite enviar por esas vías, es decir se han agotados; BE=0;
EGT=0; CF=0, pero todavía hay caminos para enviar de AI a GT. Uno es AI-C-D-
F-GT, en este camino encontramos los arcos: AIC, CD, DF,FGT, obtenemos el
mínimo de la capacidad de los arcos: min {1,3,4,6}=1

B 0
el
2
6
1 E 0
AI 1 8
E C GT
0
el el
2 5
1 F
el
D 3

Iteración 4: Puede ver cómo han quedado las capacidades se van reduciendo con
cuatro arcos con capacidad cero. Pero aún hay un camino AI-D-F-GT con
capacidad de enviar: min {1,3,5}

B 0
el
2
6
1 E 0
AI 0 9
E C GT
0
el el
3 4
0 F
el
D 2

Puede ver que solo logramos enviar 9 unidades al nodo destino GT a pesar que
en AI tengo 2 unidades en el arco AIB pero como el arco BE no tiene capacidad
(BE=0) se quedan sin enviarse. Por lo tanto, hemos llegado al flujo máximo de la
red con capacidad de 9.