Flujo de redes

2

Modelo de redes
 Modelos de Programación Lineal que poseen una estructura
muy especial
 Se puede usar esta estructura para reducir considerablemente la
complejidad computacional
 Primera aplicación de PL que se difunde tanto en la logística
industrial
 Abarca un gran número de aplicaciones diversas

Flujo en Redes

1

3

Tipos de redes
Red no dirigida

4
Red dirigidaProblemas clásicos de Flujo en Redes
 Problema de flujo de mínimo costo
– Minimum cost flow problem

 Problema de máximo flujo
– Maximum flow problem

 Problema de la ruta más corta
– Shortest path problem

 Redes se usan para transportar “commodities”
– Bienes físicos (productos, líquidos)
– Comunicaciones
– Electricidad

 El campo de la Optimización de Redes se ocupa deestos
problemas

5

Problema de Flujo en Redes a Mínimo Costo

6

 Definición del problema

 Dada una red con topología conocida
– Cada nodo de la red se define como productor o atractor (o
neutro) de viajes de tal modo que el sistema está balanceado
(oferta total=demanda total).

 Formulación matemática
 Solución al Problema: usamos SIMPLEX?

– Se conoce el costo por unidadde flujo que pase por cada arco de la
red

 Formulación dual del modelo

– Se conoce la capacidad máxima de cada arco de la red, así como el
flujo mínimo que debe atravesarlo

 SIMPLEX de redes
 Ejemplo

– Encontrar la asignación de flujos que emanan desde los productores
hasta los atractores de modo de, satisfaciendo las restricciones de
capacidad y flujo mínimo por arco, minimizarel costo total.

 Integralidad?

7

Ejemplo

Definición del Problema

8

Formulación del problema
Parámetros:
 Red G(N,A) en que N es el conjunto de nodos (n=|N|) y A el
de arcos (m=|A|).
 bi: Flujo neto generado (si positivo) o atraído (si negativo) en
nodo i (flujo que saldrá menos flujo que entrará)
 cij: Costo de transportar una unidad de flujo por el arco (i,j)Variables:
 A cada arco (i,j) se ha asignado una terna: {costo, flujo mín,
capacidad}

 xij: Unidades de flujo enviadas a través del arco (i,j)

9

Formulación matemática del problema

min



xij 

Solución al Problema: usamos SIMPLEX ?
 El problema es lineal en función objetivo y restricciones y sus
variables son continuas. Así, se puede usar herramientas de
programaciónlineal: SIMPLEX.

cij xij



10

( i , j ) A

s.a :

j:( i , j ) A

xij  0



x ji  bi

 El método SIMPLEX opera sobre problemas cuyas variables
estén restringidas a tomar valores nonegativos, como es el caso
de este problema.

j:( i , j ) A

(i, j )  A

 SIMPLEX opera sobre una matriz de restricciones de rango
máximo.
 El problema debe estar balanceado:

Esto no ocurre aquí, pues una de las restricciones de
conservación puede expresarse como combinación lineal de las
demás.

b  0
i

i N

 Eliminamos una de ellas, cualquiera. Este nuevo problema se
puede resolver directamente vía SIMPLEX

11

Solución al Problema: usamos SIMPLEX ?
 Problema: La Aplicación del SIMPLEX tradicional puede ser
impracticable:
– La sola formulacióndel problema de flujo en redes como un
LP representa una dificultad, dado el tamaño de las redes
– Las restricciones del LP en este caso representan una matriz
muy grande, que el SIMPLEX debe manipular para
encontrar la solución óptima. (¿eficiencia computacional?)
– El SIMPLEX tradicional no aprovecha la estructura de redes
del problema planteado.

12

Solución al Problema: usamos SIMPLEX?
 Es posible construir una versión SIMPLEX de redes:
– En cada iteración, el SIMPLEX se mueve de una solución
factible a otra.
– En un problema de flujo en redes cada solución factible
representa un árbol de envergadura máxima
– La idea del SIMPLEX de redes es moverse de una árbol de
envergadura máxima a otro, hasta encontrar el óptimo
(solución óptima del problema de LP) sin tener...