Optimizacion de Redes

Descargar como docx, pdf o txt
Descargar como docx, pdf o txt
Está en la página 1de 17

MAESTRÍA EN TECNOLOGÍAS

DE LA INFORMACIÓN

5.- OPTIMIZACIÓN DE REDES


 5.1 TERMINOLOGIA
 5.2 PROBLEMA DE LA RUTA MAS CORTA
 5.2.1 REDES CÍCLICAS Y ACÍCLICAS

POR:
DAVID HUERTA ROSALES

21/01/22
Contenido
5.- OPTIMIZACIÓN DE REDES.............................................................................................3
5.1 TERMINOLOGIA...........................................................................................................3
5.2 PROBLEMA DE LA RUTA MAS CORTA...................................................................3
5.2.1 REDES CÍCLICAS Y ACÍCLICAS........................................................................4
Algoritmo Acíclico...............................................................................................................4
Algoritmo cíclico..................................................................................................................7
5.3 Problema árbol expandido mínimo...................................................................................12
Algoritmo de Prim..............................................................................................................13
5.4 Problema de flujo máximo...............................................................................................15
5.5 Problema de flujo de coste mínimo..................................................................................16
5.- OPTIMIZACIÓN DE REDES
Optimización de redes es un tipo especial de modelo en programación lineal. Los modelos de
redes tienen tres ventajas importantes con respecto a la programación lineal.

 Pueden resolverse muy rápidamente. Problemas que con programación lineal


tendrían 1000 filas y 30.000 columnas pueden ser resueltos en segundos. Esto permite
que los modelos de redes sean usados en muchas aplicaciones (tal como la toma de
decisión en tiempo real) para lo cual la programación lineal no es lo ideal.
 Requieren en forma natural de soluciones enteras. Al reconocer que un problema
puede formularse como algún modelo de red nos 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.
 Son intuitivos. Los modelos de redes proveen un lenguaje para tratar los problemas,
mucho más intuitivo que "variables, objetivo, restricciones".
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.

5.1 TERMINOLOGIA
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. Si un arco no tiene dirección normalmente se le
denomina rama. Si todos los arcos en la red son dirigidos, la red se denomina una red dirigida.
Si todos los arcos son no-dirigidos, la red es una red no-dirigida.
Dos nodos pueden estar conectados por un conjunto de arcos. Una trayectoria (path en inglés) es
una secuencia de arcos distintos (con nodos no repetidos) conectando a los nodos. Una
trayectoria dirigida desde nodo i al nodo j es una secuencia de arcos, cada uno de los cuales
apunta al nodo j (si es que hay dirección). Una trayectoria no dirigida puede incluir arcos
dirigidos apuntando en cualquiera de dirección.
Una trayectoria que comienza y que termina en el mismo nodo se denomina ciclo y puede ser ya
sea dirigida o no-dirigida.
Una red está conectada si existe una trayectoria no-dirigida entre cualquier par de nodos. Una
red conectada que no tiene ciclos se denomina árbol.

5.2 PROBLEMA DE LA RUTA MAS 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 través de
una red con arcos que poseen un cierto atributo, el cual puede ser costo, distancia, tiempo, etc.
La Programación Entera permite abordar de forma eficiente este tipo de problemas, en
especial cuando la cantidad de nodos y rutas posibles resulta ser un número significativo.
Utilizar en estos casos un enfoque intuitivo de resolución es tedioso y de no ser exhaustivo no
garantiza la identificación de la mejor alternativa o ruta.
5.2.1 REDES CÍCLICAS Y ACÍCLICAS
Existen dos algoritmos para encontrar la ruta más corta en redes acíclicas y cíclicas. Se dice que
una red es acíclica si no contiene lazos; de otra manera, es cíclica.
Los algoritmos Acíclicos son usados en redes que no tienen ciclos, es decir que no tienen rutas
que partiendo de un nodo lo lleven a él mismo de nuevo. Los ciclos son también llamados
"lazos".
Los algoritmos cíclicos son para las redes que tienen ciclos o lazos... o en español vueltas en
redondo. Un ejemplo de un lazo: Si del nodo "A" puedo ir al nodo "B", y del nodo "B" puedo ir
al "C" y del "C" al "D" y del "D" puedo retornar al "A" de nuevo, ahí hay un lazo o un ciclo.
Las flechas indican en qué sentido está permitido el movimiento.

Algoritmo Acíclico:
Si la red no tiene ciclos, apliquemos el siguiente algoritmo:
Etiquetar cada nodo con el siguiente formato [distancia desde el nodo inicial, Nombre del Nodo
Precedente]. Para el nodo inicial por definición la distancia es cero (la distancia a sí mismo), y
el nodo precedente es vacío (ninguno): [0,]. Después para cada nodo, se analiza los nodos que lo
preceden por las flechas, se escoge aquel cuya distancia al nodo inicial más la distancia al nodo
presente sea mínima. Se etiqueta con la suma, y el nombre del nodo escogido... bueno, esto en
carreta es muy enredador... mejor con un ejemplo, paso a paso.

Los nodos pueden representan sitios (p.e ciudades, facilidades, etc) las flechas (también
llamadas Arcos) indican las trayectorias permitidas y sobre ellas están las distancias (pero
también puede representar el costo de desplazamiento, o el nivel de riesgo, o un producto de
ambos).

Encontremos la distancia más corta entre el nodo "A" y el nodo "G".

1. Rotular el Nodo Inicial: Recordemos el formato del rótulo es: [distancia al primer nodo, nodo
precedente]. La distancia al primer nodo, es la distancia a sí mismo en este caso, por lo tanto, es
cero. El nodo precedente: como no viene de ningún nodo, lo rotulamos vacío: [ 0, ] :
2. Rotular todos los nodos que dependan únicamente del nodo inicial:

A el Nodo B se puede llegar desde el Nodo A, con la ruta A-C-B o con la ruta A-D-C-B. Así
que depende de otros nodos a parte del Nodo inicial. Lo mismo podemos decir del Nodo C.
Pero...

... Pero al Nodo D sólo se puede llegar directamente desde el Nodo A. Este es el nodo que
vamos a rotular, y si hubiera más como él también los rotularíamos, pero en este ejemplo sólo
tenemos el D.

El rótulo del Nodo D, es: [distancia mínima desde el Nodo Inicial, Nodo Precedente]. La
distancia mínima desde el Nodo Inicial al Nodo D es 15: pos no hay otra alternativa, che! y el
Nodo Precedente el "A". Rótulo: [15, "A"]

3. Rotular Todos los Nodos que tengan la información suficiente para rotularlos:

La información necesaria para rotular un Nodo con este algoritmo, es que todos los Nodos de
los que dependa, deben estar ya rotulados. Por ejemplo, el Nodo B: depende del A y del C. El
Nodo A ya está rotulado, pero el C aún no. Así que aún no se puede rotular el Nodo B. El Nodo
C depende del A y del D, y ambos están rotulados, así que si podemos rotularlo. La distancia
desde A es 8, y desde D es: la distancia que tiene en el rótulo (que es la distancia mínima desde
él al Nodo inicial, o sea 15), MAS la distancia entre D y C = 15 +4 = 19: entre 8 y 19 es más
pequeño 8. Así que escogemos el Nodo A como precedente: el rótulo es [ 8 , "A"]
4. Seguir rotulando todos los Nodos que tengan información suficiente hasta llegar al Nodo
deseado:

G. Ahora ya hay información suficiente para rotular los Nodos B y F. Entonces rotulemos el
Nodo B (no importa cuál se haga primero, igual hay que rotularlos todos). El rotulo para el
Nodo B: La distancia desde A es 10, la distancia mínima al Nodo inicial desde C es: el la
distancia del rótulo de C: 8 + la distancia de C a B : 3 => 8 + 3 = 11. El mínimo entre 10 y 11 es
10. Rótulo= [10, "A"].

Rótulo para el F: Desde C : 8 + 4 = 12 y desde D : 15 + 15 = 30. Entonces el Rótulo es [12,


"C" ]
Rótulo para el Nodo E: Desde B : 10 + 20 = 30 y desde C: 8 + 15 = 23 Rótulo : [23,"C"]

Por último, para el Nodo G: la distancia desde E es 23 + 5 = 28 y desde F es 12 + 3 = 15 Rótulo


[15, F]

Ahora se puede leer la trayectoria mínima partiendo del rótulo del Nodo G, dicho rotulo nos
dice que viene del F el de F dice que viene del C y el del C dice que viene del A. Solución:
Distancia Mínima= 15 Ruta Más Corta = A-C-F-G

Algoritmo cíclico

La diferencia principal del algoritmo acíclico y el cíclico es que el cíclico permite trabajar con
lazos mientras el algoritmo acíclico no lo permite. Por lo tanto, el algoritmo cíclico es mucho
más general.

El algoritmo cíclico difiere del algoritmo acíclico en el sentido que permite tantas oportunidades
como sean necesarias para reevaluar un nodo. Cuando resulta evidente que se ha alcanzado la
distancia más corta a un nodo, éste se excluye de cualquier consideración posterior. El proceso
termina cuando se ha evaluado el nodo destino

La idea principal del algoritmo cíclico es muy parecida al del acíclico; pero en este se trabaja
con dos tipos de etiquetas: Etiquetas Temporales y Etiquetas Permanentes. El formato de la
etiqueta es el mismo: [distancia mínima encontrada al nodo inicial, Nombre del Nodo
Precedente]. El algoritmo cíclico es también conocido como algoritmo de Dijkstra.

El Algoritmo se describe así:


Rotular todos los nodos a los que se puede llegar desde el nodo inicial con etiquetas temporales,
la etiqueta que se les pondrá será [distancia desde el nodo inicial, Nombre del Nodo Inicial].
Aquí no nos va a importar que estos nodos tengan caminos desde otros nodos diferentes al nodo
inicial, a diferencia del algoritmo anterior. Sencillamente se rotulan como se describió.

Evaluar de todos los nodos con etiquetas temporales, cual posee la distancia más corta en la
etiqueta. Marcarlo como Etiqueta Permanente (para esto puede usar un asterisco).

Etiquetar todos los nodos a los que se pueda llegar desde el último nodo con etiqueta
permanente, si ya tienen una etiqueta temporal, esta se reevalúa con respecto a la distancia del
nodo permanente con que se está trabajando. Si la distancia que da (o sea la distancia de la
etiqueta permanente + la distancia al nodo evaluado) es menor que la que tiene en la etiqueta
ésta es cambiada por una nueva etiqueta con la distancia calculada a la de la etiqueta
permanente.

Se chequean todas las etiquetas temporales existentes, la que tenga la distancia más pequeña se
marca como etiqueta permanente y se repite el paso anterior hasta que todas las etiquetas sean
permanentes.

Ejemplo:

Supongamos que existen 7 ciudades interconectadas (o sitios cualesquiera: barrios en una


ciudad, departamentos en una fábrica, etc.), cada línea representa la trayectoria permitida de una
ciudad a otra. Las distancias (o costo de transporte) entre ciudades está representado por un
valor sobre la línea. Se pregunta por la secuencia de ciudades que dan la distancia mínima entre
la ciudad A y la ciudad G.

Etiquetar todos los nodos a donde pueda llegar desde el nodo inicial: Es decir los nodos B, C y
D.

Etiqueta para el nodo B: Es distancia desde el nodo que viene = 4, nombre del nodo que viene =
"A"

Etiqueta= [4,"A"] , de manera análoga para el nodo C = [5, "A"] y el nodo D = [3, "A"]
2. Evaluar cual, de todas las etiquetas temporales, tiene la mínima distancia para que sea
convertida en etiqueta permanente. Marquemos como etiqueta permanente, con un asterisco. En
nuestro caso hay tres etiquetas temporales, [4,"A"], [5,"A"] y [3,"A"]. La que tiene la menor
distancia es [3,"A"] en el nodo D. La convertimos en etiqueta permanente.

3. Ahora, con base en la última etiqueta permanente (la del nodo D por supuesto), se etiquetan
todos los nodos a los que se pueda llegar desde el Nodo D (el de la última etiqueta permanente).
En nuestro caso, son los Nodos C y F. La etiqueta para el Nodo F es [3+7=10, "D"], es decir
[10, D], para el Nodo C, se puede colocar la etiqueta [3+2, "D"] = [ 5,"D"]. Da igual dejar la
etiqueta actual, que tiene una distancia de 5, que cambiarla por esta última. Como se dice por
acá: "nos resbala", así que dejemos la que tiene actualmente.
4. De nuevo se evalúa de todas las etiquetas temporales, cual es la que tiene la distancia más
pequeña: [4,"A"], [5,"A"] y [10,"A"]. El nodo B que tiene la etiqueta temporal con la distancia
más pequeña, se pasa a tener una etiqueta permanente.

5. Etiquetar todos los nodos a los que se puede llegar desde el nodo con la última etiqueta
permanente, es decir el B. Estos nodos son el C y el E. La etiqueta probable para el nodo C sería
[4+3, “B”]= [7,”B”], pero como ya tiene una etiqueta temporal de [5,”A”], que tiene una
distancia menor, ¡¡¡pues ni soñamos con cambiarla!!! Dejémosla quietecita y miremos el Nodo
E. La etiqueta para el Nodo E es [4+6, "B"] = [10, "B"]
6. Evaluar de todas las etiquetas temporales, cual es la que tiene la distancia más corta: [10,"B"],
[5,"A"] y [10,"D"]. La de menor distancia es la [5,"A"]. La marcamos como etiqueta
permanente. Ahora etiquetar todos los nodos a los que se puede llegar desde el Nodo C y que no
tengan ya, una etiqueta permanente. Estamos hablando del Nodo E, F y G. Para el Nodo E la
etiqueta sería [5+4,"C"] =[9,"C"], que nos da una distancia menor que la que tiene ([10,"B"]).
Por lo tanto, la cambiamos. Para el Nodo F nos da [5+5,"C"]=[10,"C"], como ya tiene una
etiqueta con 10, nos es indiferente y no la cambiamos. Para el Nodo G la etiqueta es [5+25,
"C"]=[30,"C"].

7. Evaluar cuál de las etiquetas temporales tiene la distancia más corta: [9,"C"], [10, "D"] y
[30,"C"]. Gana el nodo E. Lo marcamos como etiqueta permanente y desde él evaluamos para
rotular a todos los nodos a los que pueda llegar, con etiquetas temporales: F y G. Para el Nodo
F, lo dejamos como esta porque la distancia nos da 9+6 = 15 que es mayor que el que tiene
actualmente 10, pero para el Nodo G el rotulo es [9+7,"E"] = [16, "E"].

Quedan como rótulos temporales el del nodo F y G. El menor es el del Nodo F, se marca como
permanente... no hay más rótulos temporales excepto el del Nodo G y el Nodo G quedaría como
[10+8, "G"]=[18,"G"] que es mayor que el que ya tiene, así que mejor dejémoslo quietico y por
último marquémoslo como etiqueta permanente.

5.3 Problema árbol expandido mínimo


Árbol de expansión mínima

Este problema surge cuando todos los nodos de una red deben conectar entre ellos, sin formar
un loop.

El árbol de expansión mínima es apropiado para problemas en los cuales la redundancia es


expansiva, o el flujo a lo largo de los arcos se considera instantáneo.

EL TRANSITO DEL DISTRITO METROPOLITANO

• La ciudad de Vancouver está planificando el desarrollo de una nueva línea en sistemas


de tránsito.
• El sistema debe unir 8 residencias y centros comerciales.
• El distrito metropolitano de tránsito necesita seleccionar un conjunto de líneas que
conecten todos los centros a un mínimo costo.
• La red seleccionada debe permitir:

Factibilidad de las líneas que deban ser construidas.

Mínimo costo posible por línea.


Algoritmo

Los algoritmos que pueden dar solución a este problema son:

 Algoritmo de Dijkstra

 Algoritmo de Kruskal

 Algoritmo de Prim

En este artículo trataremos el algoritmo de Prim como forma de solución para la cobertura
mínima, debido a la simplicidad que este algoritmo conlleva puede ser aprovechado sin
necesidad de ser un gran experto en programación.

Algoritmo de Prim
El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera
independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por
Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo
DJP o algoritmo de Jarnik.Consiste en un algoritmo de la teoría de los grafos para encontrar un
árbol de cobertura mínimo en un grafo conexo (grafo que para cada par de nodos está conectado
por un camino, o sea, si para cualquier par de nodos A y B, existe al menos un camino posible
desde B hacia A), no dirigido y cuyas aristas están etiquetadas. En otras palabras, el algoritmo
encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso
total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el
algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que
forman dicho grafo no conexo (grafo donde hay nodos que no pueden ser conectados por medio
de un camino).

Pseudocódigo
Traza

Siguiendo el algoritmo de Prim, se tiene:

 Se elige, por ejemplo, el nodo 1 y se marca.

 Se elige la arista con menor valor incidente en 1, la (1, 3) = 1 se marca y se marca el
otro nodo en el que incide, el 3.

 Se elige la arista con menor valor incidente en un nodo marcado y otro que no lo esté,
la (1, 2) = 3 se marca y se marca el nodo no marcado, el 2.

 Se elige la arista con menor valor incidente en un nodo marcado y otro que no lo esté,
la (2, 5) = 5 se marca y se marca el nodo no marcado, el 5.

 Se elige la arista con menor valor incidente en un nodo marcado y otro que no lo esté,
la (5, 6) = 1  se marca y se marca el nodo no marcado, el 6.

 Se elige la arista con menor valor incidente en un nodo marcado y otro que no lo esté,
la (5, 7) = 2 se marca y se marca el nodo no marcado, el 7.

 Se elige la arista con menor valor incidente en un nodo marcado y otro que no lo esté,
la (5, 4) = 6 se marca y se marca el nodo no marcado, el 4.

 FIN. Se finaliza dado que se tiene marcados los 7 nodos del grafo.

 Por tanto, el árbol de mínima expansión resultante sería:


5.4 Problema de flujo máximo
En algunas redes circula por los arcos un 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. Los arcos tienen una capacidad máxima de flujo, y se trata
de enviar desde la fuente al sumidero la mayor cantidad posible de flujo, de tal manera que:
 El flujo es siempre positivo y con unidades enteras.
 El flujo a través de un arco es menor o igual que la capacidad.
 El flujo que entra en un nodo es igual al que sale de él.
En el caso de que el origen o el destino no existan en el problema, se añaden ficticiamente
utilizando arcos unidireccionales de capacidad infinita, como en grafo mostrado a continuación:

 Corte: Un corte define una serie de arcos cuya supresión de la red causa una
interrupción completa del flujo entre el origen y el destino. La capacidad de corte es
igual a la suma de las capacidades de los arcos asociados. Entre todos los cortes
posibles en la red, el corte con la menor capacidad proporciona el flujo máximo en la
red.
 
El siguiente grafo ilustra 3 cortes: el Corte 1 con capacidad 60, el Corte 2 con capacidad 110 y
el Corte 3 con capacidad 70. Todo lo que podemos obtener de los 3 cortes es que el flujo
máximo en la red no excede de 60 unidades. No podemos saber cuál es el flujo máximo hasta
que se hayan enumerado todos los cortes en la red:
Las capacidades se identifican como sigue: por ejemplo, para el arco (3,4), el límite de flujo es
de 10 unidades de 3 a 4 y de 5 unidades de 4 a 3

5.5 Problema de flujo de coste mínimo


Hipótesis:

• Red conexa dirigida con n nodos

• Al menos un origen y un destino

Parámetros

 Balance o conservación del flujo en cada nudo i


Se supone que la oferta es igual a la demanda del producto

Propiedad de soluciones enteras: Si b iy i j u son enteros todas las variables básicas en cada
solución básica son enteras.

Casos particulares del problema de flujo de coste mínimo

Problema de transporte

Problema de asignación de tareas

 Número de nodos de generación (personas) = número de nodos de demanda (tareas)


 Demanda en cada nodo consumidor = 1 •
 Generación en cada nodo generador = 1

Problema de transbordo

• Problema de flujo de coste mínimo sin restricciones de capacidad en los arcos.

Problema de camino mínimo

• Origen: nodo generador con generación = 1


• Destino: nodo consumidor con demanda = 1
• Red no dirigida: red dirigida con arcos en ambos sentidos
• Distancia: coste por unidad de flujo independiente del sentido
• Arcos no acotados (acotados con límite 1)

Problema de flujo máximo

• Anular los costes del flujo c ij de los arcos existentes

• Seleccionar una cantidad F (cota superior del máximo flujo posible) y asignarlo como
generación en el nudo origen y demanda en el nodo destino

• Añadir un arco entre O y D con coste c ijelevado y capacidad ilimitada

• La minimización del coste hace que se envíe la mayor cantidad posible de flujo por los arcos
de la red existente

También podría gustarte