GRAFOS UNI

Vista previa del material en texto

Luis Medina Aquino
CICLO 2014-II
INVESTIGACION DE OPERACIONES II
1
OPTIMIZACION DE REDES 1
Luis Medina Aquino
2
OPTIMIZACIÓN EN REDES
EN ALGUNOS PROBLEMAS DE OPTIMIZACIÓN PUEDE SER ÚTIL REPRESENTAR EL PROBLEMA A TRAVÉS DE UNA GRÁFICA: ruteo de vehículos, distribución de producto, programa de actividades en un proyecto, redes de comunicación, etc.
MODELOS DE REDES: algoritmos especiales
3
GRÁFICA
ES UN CONJUNTO DE NODOS (N) Y ARCOS (A) QUE CONECTAN LOS NODOS. NOTAMOS G=(N,A)
LOS NODOS SE NUMERAN : 1,2,...,n
LOS ARCOS SE DENOTAN (i,j) indicando que une el nodo i al nodo j
i
j
4
CONCEPTOS BÁSICOS
Un arco (i,j) es dirigido si conecta i con j pero no j con i.
Una gráfica G=(N,A) es dirigida si sus arcos están dirigidos. En una gráfica no dirigida (i,j) y (j,i) representan el mismo arco ( no dirigido).
i
j
5
CONCEPTOS BÁSICOS
Gráfica no dirigida
Gráfica dirigida
4
3
2
6
5
7
Nodos
Arcos no
dirigidos
1
1
4
3
2
6
5
7
Nodos
Arcos 
dirigidos
6
CONCEPTOS BÁSICOS
Un Camino o Ruta del nodo i al nodo j es una secuencia de arcos que unen el nodo i con el nodo j: (i,i1), (i1,i2), (i2,i3),...,(ik,j). Ruta de k arcos.
Un Ciclo es un camino que une un nodo consigo mismo:(i,i1), (i1,i2), (i2,i3),...,(ik,i)
7
CONCEPTOS BÁSICOS
1
4
3
2
6
5
7
1
CAMINO DE 4 A 7
CICLO
8
CONCEPTOS BÁSICOS
UNA SUBGRÁFICA G’=(N’,A’) DE UNA GRÁFICA G=(N,A) es un conjunto de nodos y arcos de G: N’ N y G’  G.
UNA GRÁFICA G=(N,A) ES CONEXA si para cada par de nodos i,j  N existe un camino que conecte el nodo i con el nodo j.





GRAFICA G: Conexa



SUBGRÁFICA G’: 
 conexa





SUBGRAFICA G:
 no conexa
9
CONCEPTOS BÁSICOS
UN ÁRBOL de una gráfica G=(N,A) es una subgráfica G’=(N’,A’) de G que es conexa y no contiene ciclos. Si el Árbol contiene todos los nodos de G (N’=N) se dice que es un Árbol Generador.





GRAFICA G





ÁRBOL GENERADOR DE G



ÁRBOL DE G
10
CONCEPTOS BÁSICOS
Una RED es una gráfica con uno o mas valores asignados a los nodos y/o a los arcos:
Nodos: (ai)demanda, oferta, eficiencia, confiabilidad.
Arcos: (cij) costo, distancia, capacidad
Ejemplos: representar a través de una red : red de agua potable, red de comunicación, red logística.
11
PROBLEMAS Y MODELOS DE REDES
PROBLEMAS: encontrar la ruta más corta de la planta al centro de distribución pasando por ciudades intermedias. Problemas de transbordo. Política de reemplazo de equipo.
MODELO de la RUTA MÁS CORTA: dada una red dirigida G=(N,A) con distancias asociadas a los arcos (cij), encontrar la ruta más corta del nodo i al nodo j, donde i,jN
12
PROBLEMAS: transportar la mayor cantidad de producto posible a través de una red de distribución: ductos, tráfico vehicular.
MODELO de FLUJO MÁXIMO: dada una red dirigida G=(N,A) con capacidades en los arcos (cij) encontrar la mayor cantidad de flujo total de un nodo fuente a un nodo destino
PROBLEMAS Y MODELOS DE REDES
13
PROBLEMAS: programar las actividades de un proyecto y determinar el tiempo requerido para terminar el proyecto así como las actividades “críticas”
MODELO: CPM, PERT (RUTA MAS LARGA)
PROBLEMAS Y MODELOS DE REDES
14
PROBLEMAS: redes de comunicaciones. Conectar todos los nodos con el mínimo costo.
MODELO DEL ÁRBOL GENERADOR MINIMAL: dada una red conexa no dirigida G=(N,A) con costos cij en cada arco (i,j)  A, encontrar el Árbol Generador de costo mínimo
PROBLEMAS Y MODELOS DE REDES
15
Problema del Agente Viajero: encontrar el camino más corto saliendo de un nodo y regresando al mismo.
MODELO DEL AGENTE VIAJERO: encontrar un ciclo en una red (dirigida o no dirigida ). Un (camino) ciclo que no repite nodos es un (camino) o ciclo Hamiltoniano.
NO SIEMPRE EXISTE
PROBLEMAS Y MODELOS DE REDES
16
OTROS CASOS ESPECIALES
RED PLANA: que puede representarse en el plano sin cruzar arcos. Útil en ruteo
CICLO DE EULER: UN CICLO QUE INCLUYE CADA ARCO SOLO UNA VEZ. (Solo existe en una gráfica si esta tiene un número par de arcos incidentes en cada vértice (Euler). Útil en ruteo.
17
OTRAS APLICACIONES A II
LAYOUT: distribución física de instalaciones
MANUFACTURA CELULAR: separa componentes en familias de partes y máquinas en células de manufactura
PROGRAMACIÓN DE LA PRODUCCIÓN EN EL TIEMPO
18
RED DE FLUJO DE COSTO MÍNIMO
	Los problemas de transporte, transbordo, camino mas corto, flujo máximo, red de proyectos(CPM) son casos especiales del modelo de FLUJO DE COSTO MÍNIMO EN UNA RED y pueden resolverse con una forma especial del Simplex .
19
MCNFP: Minimum Cost Network Flow
20
ALGORITMO DE DIJKSTRA
	Encuentra la ruta mas corta de un nodo de la red (nodo origen) a cualquier otro nodo, cuando los costos en los arcos (distancias) son no negativos. Los nodos se marcan con marcas Temporales y Permanentes, comenzando por el nodo origen. Un nodo tiene una marca Permanente si se ha encontrado la menor distancia a ese nodo. Un nodo j tiene marca temporal si existe el arco (i, j) y el nodo i tiene marca Permanente. 
21
	La marca del nodo j es de la forma [uj,i]=[ui+cij,i], donde ui es la distancia mas corta del nodo origen al nodo i con marca Permanente y cij el costo del arco (i,j). Los nodos que no pueden alcanzarse directamente a partir de un nodo con marca Permanente tendrán marca Temporal igual a .
ALGORITMO DE DIJKSTRA
22
Sea i=1 el nodo origen
Paso 0: marcar el nodo origen con [0,0], i=1, P={1}, T={2,3,…n}.
Paso 1:  jT marcar [uj,,i]=[ui+cij,i]. Si el nodo j tiene marca temporal [uj,k] y ui+cij<uj reemplazar [uj,k] por [ui+cij,i].
Paso 2:hallar kT tal que cik=min{cij,jT}, hacer, T=T-{k}, P=P+{k}. Marcar el nodo k en forma permanente. Si T=Ø parar, sino pasar al Paso 1.
ALGORITMO DE DIJKTRA’S
23
EJEMPLO
	Los nodos de la red representa las estaciones de transbordo de un sistema de transporte en una ciudad. Los arcos representan las rutas posibles y las distancias representan el tiempo de recorrido que depende de las paradas. El origen está en el nodo 1 y en el nodo 6 se encuentra el final del recorrido. Se quiere encontrar la ruta mas corta del origen a cada nodo de transbordo y en particular la ruta mas corta al destino final.
24
RED
1
4
2
5
3
6
3
2
10
1
9
2
3
4
8
6
4
3
1
25
SOLUCIÓN
26
SOLUCIÓN
	Para determinar la ruta mas corta desde el nodo origen a cualquier otro nodo se procede como sigue:
Partiendo del nodo terminal escogido (k) buscar en la marca el nodo adyacente [uk,j], es decir el nodo j. Proceder de igual manera hacia atrás en la red. La distancia mínima es uk 
27
SOLUCIÓN
 En el ejemplo, la ruta más corta del nodo origen al nodo 6 tiene una distancia igual a 11 y la ruta es:
	1,4,5,3,6.
	La ruta mas corta al nodo 3 es:
	1, 4,5,3 con distancia igual a 8
28
EJEMPLO: reemplazo de equipo
 Se desea determinar la política óptima de sustitución de equipo para cierto horizonte de tiempo, de 2000 a 2005. Al principio de cada año se toma una decisión acerca de si se debe mantener el equipo en operación o si se debe reemplazar. La tabla muestra la estrategia posible de reemplazo y el costo de reemplazo del equipo en función del año en el que se adquiere. 
29
EJEMPLO: continua
 
30
EJEMPLO: reemplazo de equipo
 Cada arco de la red indica una compra en el año i (nodo i) y su sustitución en el año j (nodo j).
1
2
3
4
5
100
150
200
6
80
120
700
340
200
150
300
400
500
31
EJEMPLO: continua
32
ÁRBOL GENERADOR MINIMAL
	En una red de n nodos un árbol generador es un conjunto de n-1 arcos que conecta todos los nodos y no contiene ciclos.
 	El algoritmo GLOTÓN (Greedy method) parte de un nodo cualquiera y conecta cada vez el nodo que se encuentra a menor distancia de cada nodo conectado
33
ALGORITMO
Notemos C el conjunto de nodos conectados y NC el conjunto de nodods no conectados de la red.
Paso 0: comenzar en cualquier nodo de la red y colocar ese nodo en N.Los restantes nodos estarán en NC.
Paso 1: escoger el nodo de NC mas cercano a un nodo de C. Colocar ese nodo en C y quitar de NC. Repetir hasta que NC=
34
EJEMPLO: 
	Una pequeña empresa cuenta con 5 computadoras que deben ser conectadas en red. Se desea determinar la longitud mínima de cableado requerido para realizar esta conexión. Las distancias se muestran en la tabla.
35
EJEMPLO: continua
 
3
2
5
1
4
36
arco
cada
para
U
x
nodo
cada
para
b
x
x
a
s
x
x
ij
ij
j
k
i
ki
ij
ij
ij
 
 
 
L
 
 
 
 
 
.
c
 
min
j)
(i,
 
arco
 
el
en 
 
capacidad
 
de
superior 
 
cota
U
j)
(i,
 
arco
 
el
en 
 
capacidad
 
de
inferior 
 
cota
L
salida)
-
(entrada
 
i
 
nodo
 
el
en 
 
neto
 
flujo
b
j)
(i,
 
arco
 
el
en 
ación 
 transport
de
 
unitario
 
costo
c
j)
 
(i,
 
arco
 
el
en 
 
flujo
 
de
 
unidades
 
de
 
número
ij
arcos
 
los
 
todos
ij
ij
ij
i
ij
£
£
=
-
=
=
=
=
=
å
å
å
NODO
1
2
3
4
5
6
T={1,2,3,4,5,6},P={
Æ
}
Iter 1
[0,0]
p
¥
¥
¥
¥
¥
T={2,3,4,5,6},P={1}
Iter 2
[0,0]
p
[3,1]
¥
[2,1]
p
¥
¥
T={2,3,5,6},P={1,4}
Iter 3
[0,0]
p
[3,1]
p
¥
[2,1]
p
[6,4]
¥
T={3,5,6},P={1,4,2}
Iter 4
[0,0]
p
[3,1]
p
[13,2]
[2,1]
p
[6,4]
p
¥
T={3,6},P={1,4,2,5}
Iter 5
[0,0]
p
[3,1]
p
[8,5]
p
[2,1]
p
[6,4]
p
¥
T={6},P={1,4,2,5,3}
Iter 6
[0,0]
p
[3,1]
p
[8,5]
p
[2,1]
p
[6,4]
p
[11,3]
p
T={
Æ
},P={1,4,2,4,3}
NODO
1
2
3
4
5
6
T={1,2,3,4,5,6},P={(}
Iter 1
[0,0]p
(
(
(
(
(
T={2,3,4,5,6},P={1}
Iter 2
[0,0]p
[3,1]
(
[2,1]p
(
(
T={2,3,5,6},P={1,4}
Iter 3
[0,0]p
[3,1]p
(
[2,1]p
[6,4]
(
T={3,5,6},P={1,4,2}
Iter 4
[0,0]p
[3,1]p
[13,2]
[2,1]p
[6,4]p
(
T={3,6},P={1,4,2,5}
Iter 5
[0,0]p
[3,1]p
[8,5]p
[2,1]p
[6,4]p
(
T={6},P={1,4,2,5,3}
Iter 6
[0,0]p
[3,1]p
[8,5]p
[2,1]p
[6,4]p
[11,3]p
T={(},P={1,4,2,4,3}
Año de 
adquisición 
Costo de reemplazo por años 
de operación 
 1 2 3 4 5 
2000 100 200 340 700 
2001 150 300 400 500 
2002 200 
2003 80 150 
2004 120 
 
	Año de adquisición
	Costo de reemplazo por años de operación
 1 2 3 4 5 
	2000
	100
	200
	340
	
	700
	2001
	150
	300
	400
	500
	
	2002
	200
	
	
	
	
	2003
	80
	150
	
	
	
	2004
	120
	
	
	
	
DISTANCIA ENTRE CADA OFICINA 
NODOS 1 2 3 4 5 
1 0 1 4 6 2 
2 1 0 3 X 2 
3 4 3 0 5 2 
4 6 X 5 0 4 
5 2 2 2 4 0 
 
	DISTANCIA ENTRE CADA OFICINA
	NODOS
	1
	2
	3
	4
	5
	1
	0
	1
	4
	6
	2
	2
	1
	0
	3
	X
	2
	3
	4
	3
	0
	5
	2
	4
	6
	X
	5
	0
	4
	5
	2
	2
	2
	4
	0