clase 1

Ingeniera Industrial

Investigacin Operativa 2

TEORIA DE REDES (1)

FACULTAD DE

CIENCIAS E

INGENIERIA

Mg. Eduardo Carbajal Lpez

SESION 01

SESION 01

Teora de redes

Terminologa de redes

Problema del rbol de expansin mnimal

Problema de la ruta mas corta

Teora de redes (1)

1. T

eor

a d

e r

edes

Teora de redes

La modelacin de redes permite la resolucin de

mltiples problemas de programacin matemtica

mediante la implementacin de algoritmos

especiales creados para tal fin, conocidos como

Algoritmos de optimizacin de redes

1.

Teo

ra

de

re

de

s

Teora de redes

Dnde podemos aplicar teora de redes?

Sistemas de

Transporte

1.

Teo

ra

de

re

de

s

Teora de redes


Sistemas de

Comunicacin

1.

Teo

ra

de

re

de

s

Teora de redes


Sistemas de

redes sociales

1. T

eor

a d

e r

edes

Teora de redes


Sistemas

logsticos

1. T

eor

a d

e r

edes

Teora de redes


Planificacin de actividades

SESION 01

Teora de redes




Teora de redes (1)

1.1

. T

erm

inolo

ga

de r

edes

Red

Una red se compone de arcos y nodos.

La notacin empleada para nombrar una red es

(N, A) donde:

N representa el conjunto de nodos.

A representa el conjunto de arcos.

1.1

. T

erm

inolo

ga

de r

edes

Red Ejemplo

N = {1, 2, 3, 4, 5,6,7}

A = {(1, 2), (1, 3), (1,4), (2, 4), (2, 5), (3, 4), (3,6)

(4, 6), (4, 7), (5,7), (6, 7)}

1.1

. T

erm

inolo

ga

de r

edes

Cadena

Una secuencia de arcos tal que cada arco tiene

exactamente un nodo en comn con el arco previo,

se llama cadena.

Trayectoria

Una trayectoria es una cadena en la que el nodo final de cada arco es idntico al nodo inicial del arco siguiente.

1.1

. T

erm

inolo

ga

de r

edes

Cadena / Trayectoria Ejemplo

(1, 2) - (2, 4) - (2, 5)

es una cadena.

(1, 4) - (4, 7)

es una trayectoria.

1.1

. T

erm

inolo

ga

de r

edes

Ciclo

Un ciclo corresponde a la cadena que une a un

nodo con sigo mismo.

1.1

. T

erm

inolo

ga

de r

edes

Arco dirigido

Un arco dirigido es aquel que tiene un sentido

determinado, es decir que posee un nodo fuente y

un nodo destino.

1.1

. T

erm

inolo

ga

de r

edes

Arco no dirigido

Un arco no dirigido es aquel que no tiene un

sentido determinado, es ambos nodos pueden ser

fuentes y destinos a la vez.

1.1

. T

erm

inolo

ga

de r

edes

Variables asociadas a un grafo

i

j

Xij : flujo que pasa a

travs del arco

Cij : costo de envo a travs del arco

Iij : capacidad inferior

del arco.

Sij : capacidad

superior del arco.

SESION 01

Teora de redes




Teora de redes (1)

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.

Qu es un rbol de expansin?

Un rbol de expansin es aquel rbol que enlaza

todos los nodos de la red, de igual manera no

permite la existencia de ciclos.

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.

Problema del rbol de expansin minimal

Objetivo: Buscar el rbol de expansin de mnimo

costo, es decir conectar todos los nodos de la red

con el menor costos de conexin posible, sin

formar ciclos.

Aplicaciones usuales:

Redes de comunicacin. Redes de conexin de agua y desage. Redes de trnsito vial Redes ferroviarias Diseo de rutas martimas

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.

Algoritmo de KRUSKAL

Paso 1.- Inicio

Ordene el conjunto de arcos en forma creciente de acuerdo al costo.

Paso 2.- Aadir arco

Seleccione el arco de menor costo disponible y actvelo, siempre y cuando no forme un circuito cerrado.

Paso 3.- Criterio de terminacin

Si se tienen conectados todos los nodos terminar.

1 2

35

4

1

6

4

5

2

2

42 3

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.

Algoritmo de KRUSKAL Ejemplo

Halle el rbol de expansin mnima de la siguiente red usando el algoritmo de Kruskal.

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


PASO 1:

Arco Valor

(1, 2) 1

(3, 5) 2

(1, 5) 2

(2, 5) 2

(2, 3) 3

(1, 3) 4

(4, 5) 4

(3, 4) 5

(1, 4) 6

1 2

35

4

1

6

4

5

2

2

42 3

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


PASO 2 Y 3:

Arco Valor

(1, 2) 1

(3, 5) 2

(1, 5) 2

(2, 5) 2

(2, 3) 3

(1, 3) 4

(4, 5) 4

(3, 4) 5

(1, 4) 6

1 2

35

4

1

6

4

5

2

2

42 3

1 2

35

4

1

6

4

5

2

2

42 3

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


PASO 2 Y 3:

Arco Valor

(1, 2) 1

(3, 5) 2

(1, 5) 2

(2, 5) 2

(2, 3) 3

(1, 3) 4

(4, 5) 4

(3, 4) 5

(1, 4) 6

1 2

35

4

1

6

4

5

2

2

42 3

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


Como todos los nodos han sido conectados se

finaliza. El costo del rbol es 1+2+2+4 = 9

Arco Valor

(1, 2) 1

(3, 5) 2

(1, 5) 2

(2, 5) 2

(2, 3) 3

(1, 3) 4

(4, 5) 4

(3, 4) 5

(1, 4) 6

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.

Algoritmo de PRIM

Paso 1.- Inicio

Elegir un nodo arbitrario.

Paso 2.- Aadir arco

Activar el arco subyacente de mnimo costo al rbol activado que no forme ciclos cerrados.


Si se tienen todos los nodos conectados terminar.

1 2

35

4

1

6

4

5

2

2

42 3

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.

Algoritmo de PRIM Ejemplo

Halle el rbol de expansin mnima de la siguiente red usando el algoritmo de Prim.

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


PASO 1:

1 2

35

4

1

6

4

5

2

2

42 3

Se selecciona el

nodo 1 como nodo

inicial.

NODOS ACTIVOS:

1

1 2

35

4

1

6

4

5

2

2

42 3

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


PASO 2 y 3:

El arco de menor

costo adyacente a

1 es (1,2).

NODOS ACTIVOS:

1,2

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


PASO 2 y 3:

El arco de menor

costo adyacente a

1 2 es (2,5)

1 2

35

4

1

6

4

5

2

2

42 3

NODOS ACTIVOS:

1,2,5

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


PASO 2 y 3:

El arco de menor

costo adyacente a

1, 2 o 5 es (3,5)

NODOS ACTIVOS:

1,2,3,5

1 2

35

4

1

6

4

5

2

2

42 3

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


PASO 2 y 3:

El arco de menor

costo adyacente a

1, 2, 3 o 5 es (4,5)

NODOS ACTIVOS:

1,2,3,4,5

1 2

35

4

1

6

4

5

2

2

42 3

1 2

35

4

1

6

4

5

2

2

42 3

Como todos los nodos han sido conectados se

finaliza. El costo del rbol es 1+2+2+4 = 9

SESION 01

Teora de redes




Teora de redes (1)

1.2

. Pro

ble

ma d

e l

a r

uta

mas c

ort

a.


Objetivo: Encontrar el camino mas corto desde un

nodo de origen a un nodo de destino.

Consideraciones importantes:

El coeficiente del arco puede definirse como costo, tiempo o distancia.

Los coeficientes deben ser no negativos.

Algoritmo de DIJKSTRA

Paso 1.- Inicio

Definir el nodo de origen y destino

Paso 2.- Aadir arco

Activar el arco de menor costo acumulado respecto al nodo de origen que conecte a un nodo no incluido previamente.


Repetir el paso 2 hasta incluir en la seleccin al nodo de destino

1.2

. Pro

ble

ma d

e l

a r

uta

mas c

ort

a.

Algoritmo de DIJKSTRA Ejemplo

Un vuelo de Aerolnea Veloz est a punto de despegar de Lima sin escalas a Londres. Existe cierta flexibilidad para elegir la ruta precisa, segn las condiciones del clima. La siguiente red describe las posibles rutas consideradas donde LI y LO son Lima y Londres, respectivamente; y los otros nodos representan varios lugares intermedios. El viento a lo largo de cada arco afecta de manera considerable el tiempo de vuelo, y por ende, el consumo de combustible. Con base en el informe meteorolgico actual, junto a los arcos se muestran los tiempos de vuelo (en horas). Debido al alto costo de combustible, la administracin ha adoptado la poltica de elegir la ruta que minimiza el tiempo total de vuelo.

1.2

. Pro

ble

ma d

e l

a r

uta

mas c

ort

a.


1.2

. Pro

ble

ma d

e l

a r

uta

mas c

ort

a.

LI

A

B

C

D

E

F

LO

4.6

4.7

4.2

3.5

3.4

3.2

3.4

3.5

3.4

3.6

3.8

3.6

3.3

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


PASO 1:

El origen es

el nodo LI.

El destino es

el nodo LO.

LI

A

B

C

D

E

F

LO

4.6

4.7

4.2

3.5

3.4

3.2

3.4

3.5

3.4

3.6

3.8

3.6

3.3

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


PASO 2 y 3:

El arco de menor

costo es (LI,C)

NODOS ACTIVOS:

LI,C

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


PASO 2 y 3:

El arco de menor

costo es (LI,A)

NODOS ACTIVOS:

LI,A,C

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


PASO 2 y 3:

El arco de menor

costo es (LI,B)

NODOS ACTIVOS:

LI,A,B,C

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


PASO 2 y 3:

El arco de menor

costo es (C,F)

NODOS ACTIVOS:

LI,A,B,C,F

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


PASO 2 y 3:

El arco de menor

costo es (B,E)

NODOS ACTIVOS:

LI,A,B,C,E,F

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


PASO 2 y 3:

El arco de menor

costo es (LI,C)

NODOS ACTIVOS:

LI,A,B,C,D,E,F

1.2

. Pro

ble

ma d

el rb

ol de e

xpan

si

n m

inim

al.


PASO 2 y 3:

El arco de menor

costo es (E,LO)

NODOS ACTIVOS:

LI,A,B,C,D,E,F,LO

clase 1

Documents