View
227
Download
0
Category
Preview:
Citation preview
7/31/2019 CAPITULO III - DISEO DE REDES
1/56
OPTI MI ZACI ON APLI CADATr im est r e de Ot oo 20 12
Cap t u lo I I I : Di se o de Redes
7/31/2019 CAPITULO III - DISEO DE REDES
2/56
2
Primero veamos problemas
de Flujo en redes
7/31/2019 CAPITULO III - DISEO DE REDES
3/56
3
Problemas de Flujos
Los problemas de flujos se pueden representar atravs de un grafo.
Qu es un grafo? Veamos uno ejemplo.
7/31/2019 CAPITULO III - DISEO DE REDES
4/56
Los puentes de Knigsberg
Es posible cruzartodos los puentes
una sola vez yvolver al mismopunto del quesali?
4
7/31/2019 CAPITULO III - DISEO DE REDES
5/56
Los puentes de Knigsberg
Esta ciudad es atravesada por el ro Pregolya, elcual se bifurca para rodear con sus brazos a la
isla Kneiphof, dividiendo el terreno en cuatroregiones distintas, las que entonces estabanunidas mediante siete puentes llamados Puentedel herrero, Puente conector, Puente verde,Puente del mercado, Puente de madera, Puentealto y Puente de la miel.
El problema fue formulado en el siglo XVIII y
consista en encontrar un recorrido para cruzar apie toda la ciudad, pasando slo una vez por cadauno de los puentes, y regresando al mismo puntode inicio.
5
7/31/2019 CAPITULO III - DISEO DE REDES
6/56
Los puentes de Knigsberg
Este problema fue resueltopor Leonhard Euler en
1735. Consider un representacinabstracta del mapa. Secentra en las regionesterrestres y las conexionesentre ellas.
Cada regin la represent por unpunto, denominados nodos o
vrtices. Mientras, los puentes lo represent
por una lnea que una dos puntos.Las lneas se denominan aristas o
arcos ESTO DIO ORIGEN A LA TEORA DE GRAFOS6
7/31/2019 CAPITULO III - DISEO DE REDES
7/56
Los puentes de Knigsberg
Volviendo a la pregunta:Es posible cruzar todos los
puentes una sola vez y volveral mismo punto del que sali?
7
7/31/2019 CAPITULO III - DISEO DE REDES
8/56
Los puentes de Knigsberg
Volviendo a la pregunta:Es posible cruzar todos los puentes una sola vez y volver al
mismo punto del que sali?
La respuesta es no.
Si lo buscado es un Euler tour (es decir debemos volver al
mismo punto de partida, hay solucin solo si existe untrayecto entre cada par de puntos y cada punto tiene unnmero par de arcos adyacentes.
Si lo buscado es un camino Euler (es decir cubrimos todoslos arcos una vez, pero no volvemos al punto de partida),hay solucin si y slo si, existe un trayecto entre cada par depuntos y hay exactamente dos vertices que incide un
nmero impar de caminos8
7/31/2019 CAPITULO III - DISEO DE REDES
9/56
Ejemplos de grafos
Nodos representan lasestaciones.
Las aristas son las conexionesentre estaciones.
9
7/31/2019 CAPITULO III - DISEO DE REDES
10/56
Ejemplos de grafos: Red de distribucinde gas y petrleo en Europa
Nodos los puntos dedemanda o puntos deextraccin.
Las aristas son caerasde transporte
1 0
7/31/2019 CAPITULO III - DISEO DE REDES
11/56
Ejemplos de grafos: Red de distribucinde gas y petrleo en Europa
Nodos los puntos sonlos elementos de laplaca
Las aristas son lasconexiones.
1 1
7/31/2019 CAPITULO III - DISEO DE REDES
12/56
Definiciones bsicas
Un grafo G(V,E) est compuesto por un conjunto devrtices y un conjunto de aristas. El grafo se
representa por puntos o crculos unidos por lneas. La magnitud de un grafo G se caracteriza por elnmero de vrtices (llamado orden de G) y el nmerode aristas (tamao de G).
NOTA: El tiempo de ejecucin de los algoritmos se mide en trminosdel orden y el tamao.
1 2
7/31/2019 CAPITULO III - DISEO DE REDES
13/56
Definiciones bsicas
Un grafo no dirigido G(V,E) est compuesto por unconjunto de vrtices y un conjunto de aristas. El grafo
se representa por puntos o crculos unidos por lneas. La magnitud de un grafo G se caracteriza por elnmero de vrtices (llamado orden de G) y el nmerode aristas (tamao de G).
NOTA: El tiempo de ejecucin de los algoritmos se mide en trminosdel orden y el tamao.
1 3
7/31/2019 CAPITULO III - DISEO DE REDES
14/56
Definiciones bsicas
Gr af o d i r ig ido . El aristas del grafo es presentadocomo un par ordenado (u,v), donde u , v V. u es el
inicio del vrtice y v es el final del vrtice.2
4
31
V= { 1, 2, 3, 4}, | V| = 4
E= {(1,2), (2,3), (2,4), (4,1), (4,2)}, | E|=5
1 4
7/31/2019 CAPITULO III - DISEO DE REDES
15/56
Definiciones bsicas
Gr af o n o- d i r ig id o . La arista del grafo es presentadocomo un par sin ordenado (u,v)=(v,u), donde u , v
e
V. U es el inicio del vrtice y v es el final delvrtice. 2
4
31
V= { 1, 2, 3, 4}, | V| = 4
E= {(1,2), (2,3), (2,4), (4,1)}, | E|=4
1 5
7/31/2019 CAPITULO III - DISEO DE REDES
16/56
Definiciones bsicas
Gr ad o de u n v r t ice. En un grafo no-dirigido el nmero de aristas que inciden
en el. En un grafo dirigido, se tiene grado de entrada y gradode salida: Grado de entrada. Nmero de arcos que ingresan al vrtice.
Grado de salida. Nmero de arcos que salen del vrtice.
2
4
31
2
4
31
El grado del vrtice 4 es 3 El grado de entrada del vrtice 4 es 1.El grado de salida del vrtice 4 es 21 6
7/31/2019 CAPITULO III - DISEO DE REDES
17/56
Definiciones bsicas
Gr af o pon der ado . Es un grafo donde cada aristatiene asociado un peso. Se dice que es un funcin: w:
E
R 2
4
31
2
4
31
43
2
62
2
1
3 4
7
6
1 7
7/31/2019 CAPITULO III - DISEO DE REDES
18/56
Definiciones bsicas
Un c am i no es una secuencia(v1,v2,v3,,vL), tal que {(v1,v2),
(v3,v4),,(vi,vL)} E, por ejemplo
4
85
4
2
7
v5v4
v3v2
v66
3
v1
4
85
4
2
7
v5v4
v3v2
v66
3
v1
Un cam i no si m p l e es un
camino donde no se repiteningn vrtice, por ejemplo
1 8
7/31/2019 CAPITULO III - DISEO DE REDES
19/56
Definiciones bsicas
Ciclo es un camino donde v1= vL,no se repite ningn vrt ice.
4
85
4
2
7
v5v4
v3v2
v66
3
v1
Un gr afo c c l ico, es aquelcontiene un ciclo.
Un g r a fo acc l i co , es aquel queno tiene ningn ciclo.
1 9
7/31/2019 CAPITULO III - DISEO DE REDES
20/56
Definiciones bsicas
Gra fo b i pa r t i t o . Es un grafo nodirigido G(V,E), donde V puede
ser particionado en dosconjuntos V1 y V2 tal que (u,v) E, implica que:
u V1 and v V2ORv V1 and u V2.
u
v
V1V
2
2 0
7/31/2019 CAPITULO III - DISEO DE REDES
21/56
Definiciones bsicas
Gr afo Com ple t o . Es un grafo elque existe una arista queconecta cada par de vrtices
2 1
7/31/2019 CAPITULO III - DISEO DE REDES
22/56
2 2
Continuemos con
Problemas de Flujos
7/31/2019 CAPITULO III - DISEO DE REDES
23/56
Problema de Asignacin
Un servicio de reparacin de equipos elctricos le hanllegado tres productos a reparar: tostadora, plancha y
microonda. Para realizar la reparacin la empresa cuentacon tres tcnicos. Debido a la experiencia de cada uno, lostiempo que se demoran en reparar un equipo son distintopara cada uno. En la siguiente tabla se muestra un
resumen de los tiempos requerido por cada trabajadorpara reparar cada mquina. Si el costo de hora hombre esde 3000 $, defina un modelo de programacin lineal paraminimizar el costo de reparacin sujeto a la condicin que
cada trabajador puede ser asignado slo a un trabajo.Trab\Equi Tostadora Plancha Microonda
T1 5 [horas] 3 [horas] 11 [horas]
T2 5 [horas] 1 [horas] 8 [horas]T3 9 [horas] 4 [horas] 9 [horas] 2 3
7/31/2019 CAPITULO III - DISEO DE REDES
24/56
2 4
El Problema de Transporte
Un empresa tiene un conjunto de plantas, cuya localizaciones sonconocidas, para la fabricacin de su nico producto. La demanda delproducto se concentra principalmente en un conjunto de tiendas. Se
necesita conocer la cantidad a distribuir desde las plantas a las diferentestiendas, sujeto a la condiciones: satisfacer la totalidad de la demanda delas tiendas y no sobrepasar la capacidad en cada planta.
Plantas(Oferta) Clientes
(Demanda)
a1
a2
b1
b2
b3
Para su presentacin setiene un grafo bi-partito,donde:
V1 Son los nodos ovrtices que representanlas plantas (nodos deoferta)
V2 Son los nodos ovrtices que representanlas tiendas (nodos dedemanda)
Los Arcos representan
las rutas que conecta lasplantas con las tiendas.
7/31/2019 CAPITULO III - DISEO DE REDES
25/56
2 5
El Problema de Transporte
Sea:
V1 = Conjunto de plantas ={1,..,m}
V2 = Conjunto de tienda = {1,..,n}
ai = cantidad mxima que puede fabricar la planta i.
bJ = requerimiento total del artculo en la tienda j.
cij = costo unitario de transporte entre la planta i y la tienda j
7/31/2019 CAPITULO III - DISEO DE REDES
26/56
2 6
Co n sid er em o s la sig u ien t e in st a n cia:
O1 =300 D1 = 600
O2 =600
O3 =500
D2 = 500
D3 = 300
4 $/unidad
76
5 5
5
95
8
El Problema de Transporte
Otot. = 1400 Dtot. = 1400
Describa el modelo de programacinlineal para esta instancia
7/31/2019 CAPITULO III - DISEO DE REDES
27/56
2 7
Caso 1 : Of er t a m ay o q u e d em an d a
O1 =400 D1 = 600
O2 =700
O3 =500
D2 = 500
D3 = 300
4
76
5 5
5
95
8
El Problema de Transporte
Otot. = 1600 Dtot. = 1400
7/31/2019 CAPITULO III - DISEO DE REDES
28/56
2 8
Caso 1 : Of er t a m ay o q u e d em an d a
O1 =400 D1 = 600
O2 =700
O3 =500
D2 = 500
D3 = 300
4
76
5 5
5
95
8
El Problema de Transporte
D4 = 20000
0
Otot. = 1600 Dtot. = 1400
7/31/2019 CAPITULO III - DISEO DE REDES
29/56
2 9
Al resolver el problema obtenemos como solucin:
O1 400 D1 = 600
O2 700
O3 500
D2 = 500
D3 = 300
400 Ton
200 Ton
El Problema de Transporte
7/31/2019 CAPITULO III - DISEO DE REDES
30/56
3 0
Al resolver el problema obtenemos como solucin:
O1 =400 D1 = 600
O2 =700
O3 =500
D2 = 500
D3 = 300
400 Ton
200 Ton
El Problema de Transporte
D4 = 200200 Ton
7/31/2019 CAPITULO III - DISEO DE REDES
31/56
3 1
Caso 2 : Dem an d a m ay or q u e la Of er t a
O1 =400D1 = 700
O2 =600
O3 =400
D2 = 600
D3 = 300
4
76
5 5
5
95
8
El Problema de Transporte
Otot. = 1400 Dtot. = 1600
7/31/2019 CAPITULO III - DISEO DE REDES
32/56
3 2
Caso 2 : Dem an d a m ay or q u e la Of er t a
O1 =400D1 = 700
O2 =600
O3 =400
D2 = 600
D3 = 300
4
76
5 5
5
95
8
El Problema de Transporte
Otot. = 1400 Dtot. = 1600
M
M
M
O4 =200
7/31/2019 CAPITULO III - DISEO DE REDES
33/56
3 3
Una solucin del problema sera:
O1 =400D1 700
O2 =600
O3 =400
D2 600
D3 300
400
300
300
300
100
El Problema de Transporte
Otot. = 1400 Dtot. = 1600
7/31/2019 CAPITULO III - DISEO DE REDES
34/56
3 4
Considerando un nodo oferta ficticio
O1 =400D1 = 700
O2 =600
O3 =400
D2 = 600
D3 = 300
400
300
300
300
100
El Problema de Transporte
Otot. = 1400 Dtot. = 1600
O4 =200
100
7/31/2019 CAPITULO III - DISEO DE REDES
35/56
Problema Transbordo
Una empresa forestal debe satisfacer la demanda demadera aserrada (m3) a sus 5 clientes, suyorequerimientos son: 1200, 1500, 1400, 800 y 700 m3.
Para satisfacer la demanda la empresa cuenta con tresbosques y cuatro aserraderos. La cantidad de troncosdisponibles en cada bosque es de: 1500, 2500 y 1200troncos y la capacidad de cada aserradero es de: 1200,2100, 2900 y 1500 troncos. En la tabla A, se muestran
los rendimientos de los aserraderos y los costos detransporte de madera aserrada. Mientras que la tabla Bmuestra los costos de transporte de troncos desde losbosques a los aserraderos. Se pide determinar un modelo
de programacin lineal que minimice el costo detransporte sujeto a la condicin de satisfacer la demandade los clientes y no exceder la capacidad de cadaaserradero y la disponibilidad de troncos a explotar.
3 5
7/31/2019 CAPITULO III - DISEO DE REDES
36/56
Tabla A
Aser\Clien1 2 3 4 5 Rend.
m3/troncoUS$/m3
1 4 3 5 7 5 1.5
2 3 5 4 6 2 2.4
3 4 2 7 2 3 0.9
4 1 3 4 2 9 1.1
Demanda 1200 1500 1400 800 700
Tabla B
Bosq\Aser1 2 3 4 Capacidad
troncoUS$/Tronco
1 2 4 1 6 1400
2 4 8 9 10 800
3 7 2 1 2 700
Capacidad 1200 2100 2900 1500
Problema Transbordo
3 6
7/31/2019 CAPITULO III - DISEO DE REDES
37/56
3 7
Problema de Transbordo
D5 = 700
D1 = 1200
D2 = 1500
D3 = 1400
D4 = 800
O1 =1500
O2 =2500
O3 =1200
Q1 = 1200
Q2 = 2100
Q3 = 2200
Q4 = 2900
r1 = 1,5
r2 = 2,4
r3 = 0,9
r4 = 1,1
7/31/2019 CAPITULO III - DISEO DE REDES
38/56
3 8
Problema de Transbordo
D5 = 700
D1 = 1200
D2 = 1500
D3 = 1400
D4 = 800
O1 =1500
O2 =2500
O3 =1200
Q1 = 1200
Q2 = 2100
Q3 = 2200
Q4 = 2900
r1 = 1,5
r2 = 2,4
r3 = 0,8
r4 = 0,8
1200 1800 1200
300
300
29401800
1200
1400
340700
7501160 460
700
0
Es la solucin ptima?
7/31/2019 CAPITULO III - DISEO DE REDES
39/56
Problema Transbordo
Cul sera el modelo?
Qu sucede si hay capacidad entre instalaciones?
Cul sera el modelo clase del problema?
Cmo sera el modelo si se define la variable: xijk, cantidadque proviene del bosque i que pasa por aserradero j para llegaral cliente k?
3 9
7/31/2019 CAPITULO III - DISEO DE REDES
40/56
4 0
En el problema de transporte existe un conjunto de nodos ofertasy un conjunto de nodos de demanda. La distribucin del bien oservicio se haca en forma directa desde los nodos oferta hasta los
nodos demanda. La caracterstica del problema de flujo a mnimo costo (PFMC) es
que la distribucin del producto no necesariamente se hace
directamente desde los nodos oferta a los nodos de demanda. Ahora, de un nodo oferta se enva productos que son distribuidosa un conjunto de clientes, en forma secuencial. Por otra parte, uncliente podra recibir productos desde diferentes nodos de oferta.
Se busca satisfacer la demanda de cada cliente de manera deminimizar el costo asociado al flujo que circula, sujeto a lacondicin de no exceder un lmite mnimo y mximo en cada
camino y no sobrepasar la capacidad de cada nodo oferta. Se debe identificar ue caminos utilizar.
Pr ob lem a de Flu j o a Mn im o Cost o
Con j un t o de p lan t as ( nodos o fer t a )
Cla ramen te
7/31/2019 CAPITULO III - DISEO DE REDES
41/56
4 1
Las ins t a laciones es tn conect adasp o r d u ct o s ( a r co s) , t e n ien d o u n a
capac idad m x im a. Cada un a de
los duc tos requ ie re un a can t idad
m n im a que debe ci r cu la r po r
m o t i vo s d e co n t r a t o y u n co st oasociado a f lu j o que c i r cu la
Con j un t o de p lan t as ( nodos o fer t a )
y con ju n t o de c li en tes ( nodos de
d e ma n d a )
Oj
Dii
j
( ; ; )ij ij ij
c l u
n u e s t r o
p r o b lem a se
rep resen t a po ru n g r a f o .
11
7/31/2019 CAPITULO III - DISEO DE REDES
42/56
4 2
2
18
1
17
14
5
3
15
16
4
10
11
9
8
76
13
12
14,18 14,18 14,18( ; ; )c l u
18,14 18,14 18,14( ; ; )c l u
7/31/2019 CAPITULO III - DISEO DE REDES
43/56
4 3
Problema de Flujo a Mnimo Costo
7/31/2019 CAPITULO III - DISEO DE REDES
44/56
4 4
Problema de Flujo a Mnimo Costo
7/31/2019 CAPITULO III - DISEO DE REDES
45/56
4 5
Pr ob lem a de Flu j o a Mn im o Cost o
En la red existe un conjunto de nodos productores u oferta yun conjunto de nodos consumidores o demanda
Se debe decidir como enviar (que arcos utilizar) para enviar losproductos desde los nodos oferta hacia los nodos demanda),
Minimizando los costos de transporte sobre la red.
ANTES DE DESARROLLAR EL
MODELO CLASE DEL PROBLEMA
P bl d Fl j M i C
7/31/2019 CAPITULO III - DISEO DE REDES
46/56
4 6
Pr ob lem a de Flu j o a Mn im o Cost o
2
1
5
3
4
7
6
O1= 1 0
O4= 2 0
D7= 1 5
D5= 1 5D2= O2= 0
D3= O3= 0
D6= O6= 0
D2= O2= 0 ?
P bl d Fl j M i C t
7/31/2019 CAPITULO III - DISEO DE REDES
47/56
4 7
Pr ob lem a de Flu j o a Mn im o Cost o
2
1
5
3
4
7
6
O1= 1 0
O4= 2 0
D7= 1 5
D5= 1 5D2= O2= 0
D3= O3= 0
D6= O6= 0
1 0
1 0
5
2 0
1 5
Cun t o es el f l u j o qu e en t r a
y sa le de l nod o 3?
Cun t o es el f l u j o qu e en t r a
y sa le de l nod o 6?
P bl d Fl j M i C t
7/31/2019 CAPITULO III - DISEO DE REDES
48/56
4 8
Pr ob lem a de Flu j o a Mn im o Cost o
2
1
5
3
4
7
6
O1= 1 0
O4= 2 0
D7= 1 5
D5= 1 5D2= O2= 0
D3= O3= 0
D6= O6= 0
1 0
1 01 5
2 0
2 0
Cun t o es el f l u j o qu e en t r a
y sa le de l nodo 3?
Cun t o es el f l u j o qu e en t r a
y sa le de l nodo 5?
Pr ob lem a de Flu j o a Mn im o Cost o
7/31/2019 CAPITULO III - DISEO DE REDES
49/56
4 9
Pr ob lem a de Flu j o a Mn im o Cost o
2
1
5
3
4
7
6
O1= 1 0
O4= 2 0
D7= 1 5
D5= 1 5D2= O2= 0
D3= O3= 0
D6= O6= 0
1 0
1 01 5
2 0
2 0
Cun t o es el f l u j o qu e en t r a
y sa le de l nodo 4?
1 0
Problemas de Flujo en Redes
7/31/2019 CAPITULO III - DISEO DE REDES
50/56
5 0
Problemas de Flujo en Redes
En r esum en :
Se puede representar el problema sobre una Red o Grafo dirigidoG(N,A), donde Nes el conjunto de nodos y A es el conjunto de arcos.
Se define para cada arco (i,j)
A: cij costo asociado al flujo que circula
Lmite mnimo lij.
Lmite Mximo uij.
Cada nodo ide la red posee una oferta Oi y una demanda Di,
Un n od o i cuya demanda Oi = 0 y ofertaDi= 0 se denomina n od o d et rans fe renc ia .
b(i): oferta en el nodo i . Definiremos que si un nodo i: b(i)> 0 Oferta b(i)< 0 Demanda b(i)= 0 Transferencia
Pr ob lem a de Flu j o a Mn im o Cost o
7/31/2019 CAPITULO III - DISEO DE REDES
51/56
5 1
Pr ob lem a de Flu j o a Mn im o Cost o
2
1
5
3
4
7
6
b(1)=10
b(4)=20
b(7)=-15
b(5)=-15b(2) =0
b ( 3 ) = 0
b(6)=0
Problema de Flujo a Mnimo Costo
7/31/2019 CAPITULO III - DISEO DE REDES
52/56
5 2
Problema de Flujo a Mnimo Costo
Ejemplo
Arco Parmetros
N Cola
Cabe
za
Costo
(cij)
Lmite
inferior(lij)
LmiteSuperior
(uij)
1 1 2 7 0 11
2 1 3 9 0 11
3 1 4 10 4 11
4 2 3 7 0 11
5 2 5 5 0 11
6 3 4 10 5 11
7 3 5 3 0 11
8 3 6 9 0 11
9 4 3 2 0 11
10 4 6 3 6 11
11 5 3 5 0 11
12 5 6 8 0 11
13 5 7 9 0 11
14 6 5 1 5 11
15 6 7 8 0 11
i j
(cij;lij;uij)
Defina el modelo para la
instancia
7/31/2019 CAPITULO III - DISEO DE REDES
53/56
5 3
Se busca determinar la ruta entre dos puntos de unrea, con el objetivo de minimizar, por ejemplo:
distancia o tiempo. Nuevamente, el problema se pude representar por un
grafo.
El Problema de Ruta Ms Corta
El P bl d R t M C t
2426
Las reg i on es se
t d
7/31/2019 CAPITULO III - DISEO DE REDES
54/56
5 4
El objetivo es determinar la ruta entre dos puntos de unrea, con el objetivo de minimizar, por ejemplo:distancia o tiempo.
El Problema de Ruta Ms Corta
16
23
22
212019
18
17
6
1
25
3
15
25
7
1214
4
9
8
10
11
13
26
27
28
28
r ep r esen tan p o r n odos
( N)
Los cam inos qu e conec tan
cada reg in rep r esen t an
los a rcos ( A)
El peso asoc iad o a cada
arco , repr esent a r :
d i s tancia o t i em po .
El P bl d R t M C t
7/31/2019 CAPITULO III - DISEO DE REDES
55/56
5 5
El problema se puede representar por un grafo dirigidoG(N,A), donde N es el conjunto de nodos y A es el
conjunto de arcos. Cada arco (i,j) tiene asociado unpeso cij (distancia o tiempo). Se busca determinar lacamino entre dos nodos s y tcon el objetivo deminimizar la distancia o el tiempo total.
Este problema es un caso particular del problema deflujo a costo mnimo (PFCM). Porqu?
El Problema de Ruta Ms Corta
El P bl d R t M C t
7/31/2019 CAPITULO III - DISEO DE REDES
56/56
5 6
La idea sera considerar: s el nodo de oferta condisponibilidad de una unidad y t el nodo de demanda,
cuyo requerimiento es de una unidad. Porqu la solucin sera un camino?
El Problema de Ruta Ms Corta