CAPITULO I PROBLEMAS DE FLUJO EN REDES PARTE I 2

EII 410
Investigación Operaciones
1º semestre 2015
Capítulo I:
Modelación de Problemas de Flujo en Redes

Introducción y Conceptos Básicos
• Muchos problemas se desarrollan sobre redes...
– Generación y transmisión eléctrica
– Sistemas hidráulicos
– Transporte de carga y pasajeros
– Cadenas logísticas (Supply Chain)
– …

• Muchos otros “pueden” ser modelados mediante redes y
grafos
– Sistemas deproducción e inventario
– Asignación de recursos
– Programación secuenciación y asignación de tareas
– Planificación y programación de proyectos
– …
2

Introducción y Conceptos Básicos
• Algunos problemas operan en grafos con arcos dirigidos y
otros con arcos no dirigidos...

• Algunos problemas consisten en la búsqueda de grafos y
sub-grafos con características especiales…
– Se necesita una redque conecte dos subconjuntos de ...
– Se busca una red que posea una ruta dirigida para cada ...
– Se debe construir una red con al menos dos nodos
adyacentes...
3

Introducción y Conceptos Básicos
• Se asumirá una red o grafo
G(N,A), que está compuesta
por un “conjunto” de nodos
(N) conectados por un
“conjunto” de arcos (A)
(dirigidos y/o no dirigidos)

A

• Cada arco poseerá
información decostos,
tiempos, distancias,
capacidades, dirección, etc.
• Otros: población, seguridad,
probabilidad de accidentes,
riesgo, etc.

N

4

Introducción y Conceptos Básicos
• Algunos ejemplos:
– Enviar el máximo flujo de agua posible desde un origen
(fuente) a un destino (sumidero), disponiendo de una
red de cañerías con capacidades.
Ductos con
capacidades
(arcos)

Fuente

Sumidero

5

Introducción yConceptos Básicos
• Algunos ejemplos:
– Identificar las rutas más cortas para alcanzar o visitar
un conjunto de puntos destinos (clientes), a partir de
un único origen (depot)

Depot

6

3
1

8
5
2

4

7

6

Introducción y Conceptos Básicos
• Algunos ejemplos:
– Identificar diferentes parejas de elementos (asignación
de salas, recursos, conformación de equipos, etc.).
E

2

2
5

C

F

3

3

3

43

6
A

5

3

D
5

8

H

4

2
3
B
5

4
G

– Se indican sólo las parejas factibles de seleccionar, con
el respectivo costo de asignación o emparejamiento
7

Introducción y Conceptos Básicos
• Algunos ejemplos:
– Identificar El conjunto de actividades críticas de un proyecto
(aquella que entregue la duración del proyecto).
– Esta secuencia de actividades posee los cuellos de botella.
– En la redcada arco representa una actividad, y los nodos
indican el sentido de precedencia de dichas actividades.

2

11

8
5

Inicio

12

1

14

Término

10

4

7

3
6

9

13

8

Introducción y Conceptos Básicos
REPRESENTACION DE GRAFOS
• Representación gráfica-visual
• Representación numérica-computacional
D: Matriz de Adyacencia

1
Dij  
0

• El anterior es un caso dirigido

si  i, j   A

•¿qué pasa con una red no
dirigida?

si  i, j   A

EJEMPLO:
a b c
a

b

b 0 0 1

• ¿qué representa una matriz
triangular (superior o
inferior)?

c 0 1 0

• ¿0`s en la diagonal?

a 0 1 1



c

• ¿qué pasa con una red bidireccional?



9

Introducción y Conceptos Básicos
¿Qué representa la suma de los elementos de una fila de D?

¿Qué representa la suma de los elementos de una columna de D?¿Qué representa la suma de los elementos de una fila de D2?

¿Qué representa la suma de los elementos de una columna de D2?

10

Introducción y Conceptos Básicos
Ejemplo:
a

b

c

d

a
a
b
2
D 
c
d
D ij 
k
D ij 
2

0
0

0

0

a
b
D 
c
d
b
1
0
0
0

c
0
0
0
0

a

b

c

d

0
0

0

0

1
0
1
0

1
0
D
0
0

1a
1b

1 c

0d

a

b

c

d

0
0

0

0

1
0
1
0

1
0
0
0

1
1 1

0

d
2
0 
1

0

?

entrega el número de rutas de 2 arcos que conectan a cada par de nodos (i,j)
entrega el número de rutas de k arcos que conectan a cada par de nodos (i,j)

11

Introducción y Conceptos Básicos
B.- Matriz de Incidencia (Nodo – Arco).
si i es origen o inicio del arco j
1

Bij  1
si i es destino o termino del arco j
0
e.o.c.

EJEMPLO:
a1

a2

a3

a4

a5 a6...