Optimización de Redes
INVESTIGACIÓN OPERATIVA II
Mag. Miguel Sierra
MODELOS DE
OPTIMIZACION DE REDES
Introducción
Terminología. Representación general
Problema del árbol de expansión mínima
Problema del flujo de costo mínimo
Problema de la ruta más corta
Problema del flujo máximo
INTRODUCCION
Una red es una colección de nodos y arcos
Una red podría representar innumerables aplicaciones,
por ejemplo, sistemas de inventarios, sistemas
fluviales, sistemas de distribución, precedencia y orden
de eventos, flowcharts, etc..
Muchas aplicaciones tienen características de flujo, por
ello se llaman “Modelos de flujo en redes”
Representación de modelos de flujo en redes
[0]
2 4
(3,5) (4,-1)
4 nodos: i= 1..4
3
5 arcos: k= 1..5
bi =[3] 1
(10,4) Los arcos pueden ser
1 4 [-5]
dirigidos o no dirigidos
2 5
El arco 5 se puede
(1,1) denotar como arco
(3,3)= (Fmax, Costo)
{3,4}, (3,4), 34, 34
3
[2]
[bi] : Producción del nodo i
[bi]= (suma de flujos que salen del nodo i –
suma de flujos que entran al nodo i)
Para cada arco ij hay: (Fmax,Costo), realmente: (Fmaxij,Costoij)
Fmax (o Fmaxij) es la capacidad máxima de flujo en cada arco
Costo (Cij) es el costo unitario del flujo en cada arco
Xij es el flujo que pasa por el arco k: Xij<=Fmaxij
Costo total en la red: Cij*Xij
Problema del árbol de expansión mínimo
Se tienen como datos las longitudes de los arcos potenciales.
Se desea diseñar una red, seleccionando los arcos adecuados, de
tal forma que haya un camino entre cada par de nodos.
El objetivo es lograr lo anterior minimizando la longitud total de los
arcos elegidos.
Ejemplos de aplicación:
Diseño de redes de telecomunicación (fibra óptica)
Diseño de redes de transporte, minimizando el costo
Diseño de una red de tubería entre varias localidades
Diseño de una red de cableado eléctrico
EL ALGORITMO:
Seleccionar cualquier nodo y conectarlo al mas cercano
Se identifica el nodo no conectado mas cercano a un nodo
conectado y conectarlo.
Repetir el paso anterior hasta unir todos los nodos. Si hay
empate, romperlo en forma arbitraria.
Ejemplo del árbol de expansión mínimo
2
1
4
4
1 3
4
5
5
2
3
Longitud total = 10
Problema de Flujo a costo mínimo
Red dirigida
Hay nodos fuente ([bi]> 0)
Hay nodos demanda ([bi]< 0)
El resto de los nodos son nodos de transbordo ([bi]= 0)
Los flujos solo pasan en dirección de las flechas
Se busca minimizar el costo total de enviar, a través de la
red, el suministro disponible para satisfacer la demanda.
Ejemplos de aplicaciones
Aplicación Nodo fuente Nodo transbordo Nodo demanda
F
Distribucion plantas de almacenes consumidores
L
de productos producción
U
Deshechos fuentes de tratamientos rellenos J
sólidos deshechos O
Programación lugares de escalas lugares de S
de vuelos partida llegada ?
Problema de Flujo a costo mínimo.
Equivalencia en Programación Lineal
Clase general de problema, que comprende, como casos especiales,
a los problemas de transporte, de transbordo, de asignación, de ruta
mas corta y de flujo máximo.
En este problema se define:
Xij = número de unidades de flujo enviadas del nodo i al nodo j, a
través del arco ij.
Fmaxij = cota superior del flujo en el arco ij
Min Z = i jCij*Xij
s.a.:
j Xij - k Xki = bi una restricción para cada nodo i
flujos que salen de i - flujos que entran a i = producción del nodo i
Xij <= Fmaxij una restricción para cada arco ij
Xij>=0
Caso: Problema de Flujo a costo mínimo
Un agricultor desea enviar todos los productos de su cosecha
hacia la ciudad D. Posee dos haciendas de producción, la A y la B.
Es posible usar la localidad intermedia C. La hacienda A ha
producido 3 Toneladas y la B solo 2 Toneladas de producto.
Las capacidades de transporte entre localidades, se encuentran en
la tabla superior y las costos de transportar en la tabla inferior:
De .. a: A B C D
A - 3 1 -
B - - 10 4 Capacidades
C - - - 3
D - - - -
De .. a: A B C D
A - 5 1 -
B - - 4 -1 Costos
C - - - 3
D - - - -
Determinar como debe distribuir sus envíos, de tal manera que se
minimicen los costos.
Formulación gráfica del Problema de Flujo a costo mínimo
Nodos: 1=A 2=B 3=C 4=D
[0]
2 4
(3,5) (4,-1)
3
bi=[3] 1
(10,4)
1 4 [-5]
(1,1) (3,3)= (Lk, Ck)
5
3
3
[2]
Formulación como Programación Lineal:
Min Z = 5X12 + X13 + 4X23 – X24 + 3X34
s.a.: X12+X13 = 3
X24+X23-X12 = 2
X34-X13-X23 = 0
-X24-X34 = -5
X12 <= 3
X13 <= 1
X23 <= 10
X24 <= 4
X34 <= 3
Xij >=0 Resolver con Solver de Excel
Problema de la ruta mas corta
Se tienen como datos las longitudes de los arcos.
Hay dos nodos especiales, el origen y el destino.
El objetivo es encontrar el camino mas corto del origen al destino.
Ejemplos de aplicación:
Minimizar la distancia total recorrida entre dos ciudades.
Minimizar el tiempo total de una secuencia de actividades.
Minimizar el costo total de una secuencia de actividades.
LA FORMULACION:
Se puede formular como un problema de flujo de costo mínimo:
El origen tendría una producción de bi=1
El destino tendría una producción de bi = -1
Si la red es no dirigida, se reemplaza cada arco no dirigido por
dos arcos dirigidos.
No hay que considerar los arcos que llegan al origen, ni los que
salen del destino.
Las distancias entre los nodos ij se convertirán en unidades de
costo Cij para el flujo Xij
Ejemplo del problema de la ruta más corta
2
1
4
Encontrar la ruta mas 4
corta desde el nodo 1 1 2
5
al nodo 5
7
5
2
3
2
Como 1
4
problema de [1]
1
4
Flujo de costo 1 2 2
mínimo 5
[-1]
quedaría: 7
5
2
3
Problema del Flujo Máximo
El flujo se origina en un solo nodo (nodo fuente), y termina en otro
nodo (nodo destino).
Los nodos restantes son nodos de transbordo.
Los flujos solo pasan en dirección de las flechas
Se busca maximizar la cantidad total de flujo desde la fuente al
destino.
Ejemplos de aplicación:
Maximizar la distribución de productos a los clientes
Maximizar el flujo de petróleo a través de tuberías.
Maximizar el flujo de vehículos por una red de transporte.
LA FORMULACION:
Se puede formular como un problema de flujo de costo mínimo:
El origen tendría una producción de bi=V, donde V es una constante,
una cota superior segura para el flujo total.
El destino tendría una producción de bi = -V
Se crea un arco ficticio que va desde el nodo inicial al nodo final.
El costo del arco ficticio es M, una cantidad constante y grande, el
costo de los demás arcos es 0.
Formular como Problema del Flujo Máximo
4
2 4
2
3 3
1 6
4
2 3
3 5
2
Los valores en los arcos son las
capacidades de transporte.
Problema del Transporte
El flujo se origina en mas de un nodo (nodos ofertas, [bi]>0), y
termina en mas de un nodo (nodos demanda, bi<[0]).
La suma de las ofertas es igual a la suma de las demandas.
Todos los arcos están dirigidos desde algún nodo oferta hacia algún
nodo destino.
Se tienen como datos los costos unitarios del flujo por cada arco.
Se busca minimizar el costo de transporte, de tal manera que se
cumplan con las demandas, sin superar las ofertas.
LA FORMULACION:
Se puede formular como un problema de flujo de costo mínimo:
Para los nodos ofertas, todos sus arcos salen.
Para los nodos ofertas, todos sus arcos entran.