investigacion operativa 1 redes
Páginas: 17 (4191 palabras)
Publicado: 27 de noviembre de 2014
Curso para Ingeniería Civil Informática
Modelo de Redes
Dra. Virna Ortiz Araya
Segundo semestre 2014
Definición del problema.
Ruta más corta.
Pert y CMP.
Estudio de casos.
Aplicaciones.
Muchos problemas importantes de optimización se
analizan mejor por medio de una representación
gráfica o de red.
Una gráfica o red se define mediante dosconjuntos
de símbolos: nodos y arcos.
Un arco consiste en un par ordenado de puntos
extremos y representa una posible dirección de
movimiento que podría ocurrir entre puntos
extremos (o vértices).
Para cada arco existe un nodo inicial y un nodo final.
Una secuencia de arcos tal que cada arco tiene
exactamente un vértice en común con el arco previo,
se llama una cadena.
Unatrayectoria es una cadena en la que el
nodo terminal de cada arco es idéntico al
nodo inicial del arco siguiente.
Ejemplo:
1
4
2
3
El problema de la ruta más corta tiene que ver
con la determinación de los caminos
conectados en una red de transporte que
constituyen en conjunto la distancia más
corta entre una fuente y un destino.
Una compañía arrendadora deautomóviles
está desarrollando un plan de reemplazo de
su flotilla para los próximos cinco años. Un
automóvil debe estar en servicio cuando
menos un año antes de que se considere ser
reemplazado. La tabla siguiente resume el
costo de reemplazo por unidad (en miles de
unidades monetarias) como función del
tiempo y el número de años en operación. El
costo incluye la compra, prima de seguro,operación y mantenimiento.
1
1
Año
2
3
4
2
4,0
3
4
5
5,4
9,8
13,7
4,3
6,2
8,1
4,8
7,1
4,9
Cada año está representado por un nodo. La “longitud” de un
arco que une dos nodos es igual al costo de reemplazo
asociado que se da en la tabla 1. Dibuje la red asociada a este
problema.
La solución óptima producirá la ruta 1 2 5,
con un costototal de 4 + 8,1 =12,1 (miles de
unidades monetarias) Esto quiere decir que cada
automóvil debe reemplazarse al segundo año de
uso y desecharse al quinto año (2 y 5).
Supongamos que deseamos seleccionar la ruta por
carretera más corta entre la ciudad de inicio en el nodo
1 y la ciudad destino en el nodo 7. Las rutas pasan por
ciudades intermedias designadas por los nodos 2 a 6.
2
71
8
12
8
3
5
4
9
7
13
5
6
9
6
7
Descomponer en etapas, trazando líneas
verticales.
Se realizan los cálculos por separados para
cada etapa.
La idea general para determinar la ruta más
corta a todos los nodos terminales de una
etapa y, luego utilizarlos como datos de
entrada a la etapa inmediatamente
subsiguiente.
f1
7
f0
0
12
7
8
5
8
f1
f2
7
2
12
8
3
3
5
5
4
4
8
9
7
13
f2
12
12
5
5
17
17
6
6
f3
9
6
21
7
Los cálculos en cada etapa son una función
de las rutas factibles de dicha etapa, y sólo
de esa etapa.
Una etapa actual está conectada a la etapa
inmediatamente precedente, considerando
sólo las distancias máscortas de la ruta más
inmediata precedente.
Resuelva el siguiente problema, suponiendo
que se utilizan las siguientes rutas:
El nodo 7 (x4=7) está conectado a los nodos 5 y
6 (x3=5 y 6) exactamente con una ruta cada
uno.
d(x3, x4)
Solución óptima
x3
x4=7
f3(x3)
x4*
5
9
9
7
6
6
6
7
Suponga que cuando se envía potencia de laplanta 1 (nodo 1) a la ciudad 1 (nodo 6), ésta debe
pasar por subestaciones de retransmisión (nodos
2 a 5). Para cualquier par de nodos entre los que
se puede transportar la potencia, la figura
siguiente da la distancia (en millas) entre los
nodos. Así, las subestaciones 2 y 4 están
separadas tres millas, y la potencia no se puede
enviar entre las subestaciones 4 y 5. Powerco
quiere que la...
Modelo de Redes
Dra. Virna Ortiz Araya
Segundo semestre 2014
Definición del problema.
Ruta más corta.
Pert y CMP.
Estudio de casos.
Aplicaciones.
Muchos problemas importantes de optimización se
analizan mejor por medio de una representación
gráfica o de red.
Una gráfica o red se define mediante dosconjuntos
de símbolos: nodos y arcos.
Un arco consiste en un par ordenado de puntos
extremos y representa una posible dirección de
movimiento que podría ocurrir entre puntos
extremos (o vértices).
Para cada arco existe un nodo inicial y un nodo final.
Una secuencia de arcos tal que cada arco tiene
exactamente un vértice en común con el arco previo,
se llama una cadena.
Unatrayectoria es una cadena en la que el
nodo terminal de cada arco es idéntico al
nodo inicial del arco siguiente.
Ejemplo:
1
4
2
3
El problema de la ruta más corta tiene que ver
con la determinación de los caminos
conectados en una red de transporte que
constituyen en conjunto la distancia más
corta entre una fuente y un destino.
Una compañía arrendadora deautomóviles
está desarrollando un plan de reemplazo de
su flotilla para los próximos cinco años. Un
automóvil debe estar en servicio cuando
menos un año antes de que se considere ser
reemplazado. La tabla siguiente resume el
costo de reemplazo por unidad (en miles de
unidades monetarias) como función del
tiempo y el número de años en operación. El
costo incluye la compra, prima de seguro,operación y mantenimiento.
1
1
Año
2
3
4
2
4,0
3
4
5
5,4
9,8
13,7
4,3
6,2
8,1
4,8
7,1
4,9
Cada año está representado por un nodo. La “longitud” de un
arco que une dos nodos es igual al costo de reemplazo
asociado que se da en la tabla 1. Dibuje la red asociada a este
problema.
La solución óptima producirá la ruta 1 2 5,
con un costototal de 4 + 8,1 =12,1 (miles de
unidades monetarias) Esto quiere decir que cada
automóvil debe reemplazarse al segundo año de
uso y desecharse al quinto año (2 y 5).
Supongamos que deseamos seleccionar la ruta por
carretera más corta entre la ciudad de inicio en el nodo
1 y la ciudad destino en el nodo 7. Las rutas pasan por
ciudades intermedias designadas por los nodos 2 a 6.
2
71
8
12
8
3
5
4
9
7
13
5
6
9
6
7
Descomponer en etapas, trazando líneas
verticales.
Se realizan los cálculos por separados para
cada etapa.
La idea general para determinar la ruta más
corta a todos los nodos terminales de una
etapa y, luego utilizarlos como datos de
entrada a la etapa inmediatamente
subsiguiente.
f1
7
f0
0
12
7
8
5
8
f1
f2
7
2
12
8
3
3
5
5
4
4
8
9
7
13
f2
12
12
5
5
17
17
6
6
f3
9
6
21
7
Los cálculos en cada etapa son una función
de las rutas factibles de dicha etapa, y sólo
de esa etapa.
Una etapa actual está conectada a la etapa
inmediatamente precedente, considerando
sólo las distancias máscortas de la ruta más
inmediata precedente.
Resuelva el siguiente problema, suponiendo
que se utilizan las siguientes rutas:
El nodo 7 (x4=7) está conectado a los nodos 5 y
6 (x3=5 y 6) exactamente con una ruta cada
uno.
d(x3, x4)
Solución óptima
x3
x4=7
f3(x3)
x4*
5
9
9
7
6
6
6
7
Suponga que cuando se envía potencia de laplanta 1 (nodo 1) a la ciudad 1 (nodo 6), ésta debe
pasar por subestaciones de retransmisión (nodos
2 a 5). Para cualquier par de nodos entre los que
se puede transportar la potencia, la figura
siguiente da la distancia (en millas) entre los
nodos. Así, las subestaciones 2 y 4 están
separadas tres millas, y la potencia no se puede
enviar entre las subestaciones 4 y 5. Powerco
quiere que la...
Leer documento completo
Regístrate para leer el documento completo.