Ing. de sistemas e informatica

ICS 1102 (3)
Optimización
Departamento de Ingeniería Industrial y de Sistemas
Pontificia Universidad Católica de Chile

Clase 27 - Flujo en Redes

Prof. Claudio Seebach -

2do Semestre 2006

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

Prof. Claudio Seebach

ICS 1102 – Optimización / Clase 27

Notación y Terminología
• La terminología de redes no está (y jamás lo
estará) estandarizada, pudiendo describirlas
de muchas maneras

Prof. Claudio Seebach

ICS 1102 – Optimización / Clase 27

RedesDirigidas y No-dirigidas

• Redes se usan para transportar “commodities”
• Bienes físicos (productos, liquidos)
• Comunicaciones
• Electricidad

• El campo de la Optimización de Redes se
ocupa de estos problemas

Prof. Claudio Seebach

ICS 1102 – Optimización / Clase 27

Aplicaciones de Optimización en Redes

Prof. Claudio Seebach

ICS 1102 – Optimización / Clase 27

Ejemplo detérminos

Prof. Claudio Seebach

ICS 1102 – Optimización / Clase 27

Más definiciones

Prof. Claudio Seebach

ICS 1102 – Optimización / Clase 27

Problemas 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

Prof. Claudio SeebachICS 1102 – Optimización / Clase 27

Problema de Flujo en Redes a Mínimo Costo
•
•
•
•
•
•
•

Definición del problema
Formulación matemática
Solución al Problema: usamos SIMPLEX?
Formulación dual del modelo
SIMPLEX de redes
Ejemplo
Integralidad?

Prof. Claudio Seebach

ICS 1102 – Optimización / Clase 27

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).
• Se conoce el costo por unidad de flujo que pase por cada
arco de la red
• Se conoce la capacidad máxima de cada arco de la red, así
como el flujo mínimo que debe atravesarlo
• Encontrar la asignación de flujos que emanan desde los
productoreshasta los atractores de modo de, satisfaciendo
las restricciones de capacidad y flujo mínimo por arco,
minimizar el costo total.

Prof. Claudio Seebach

ICS 1102 – Optimización / Clase 27

Asignación a
costo mínimo?

Ejemplo

}
,6
,1
{4
,9 }

{5

,1 2 }

5

7}

7
{4,0,6}
{3,0,8}

}

5

,8 }

{ 5 ,0

,1 ,

0
0 ,1
,

{ 2 ,2

14 ⇒ 4

⇒

{5,1,7},2

6

{8,0,6}

8 ⇒10

5}

{6

⇒

⇒

{7

{7,3,8}

3

{ 3 ,0 ,8 }

7}

3

8}

}

,2 ,

}

,1 ,

{ 5 ,1 ,

0 ,6

{3

,6

{4

8}

}

,0

,0 ,

8}

{4,

{3

7}
,1 ,

{4

{3,0,6}

0 ,6

8⇒ 1

{5

2

{ 5 ,2 ,

7

{3,0,6}

{4,

,
{6

}
2 ,8

12 ⇒
⇒

10

9 ⇒9

A cada arco (i,j) se ha asignado una terna:{costo, flujo mín, capacidad}
Supondremos en esta clase que flujo min (i,j) = 0 y capacidad = inf
Prof. Claudio Seebach

ICS 1102 – Optimización / Clase 27

Formulación Matemática 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 queentrará)
cij: Costo de transportar una unidad de flujo por el arco (i,j)
Variables:
xij: Unidades de flujo enviadas a través del arco (i,j)
Prof. Claudio Seebach

ICS 1102 – Optimización / Clase 27

Formulación Matemática del Problema

• El modelo debe estar balanceado, esto es:

Prof. Claudio Seebach

ICS 1102 – Optimización / Clase 27

Algunas características interesantes...