Optimizacion de Redes
Optimizacion de Redes
Optimizacion de Redes
DE LA INFORMACIÓN
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.
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.
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).
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"].
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.
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:
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.
Este problema surge cuando todos los nodos de una red deben conectar entre ellos, sin formar
un loop.
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
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.
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
Parámetros
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.
Problema de transporte
Problema de transbordo
• 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
• La minimización del coste hace que se envíe la mayor cantidad posible de flujo por los arcos
de la red existente