Universidad de los Andes Facultad de Ciencias Económicas y Sociales
Escuela de Contaduría y Administración Mérida Estado Mérida
Métodos Cuantitativos para la Gerencia II
Teoría de
Teoría de Redes
Algunos Tipos de Problemas de Redes
Teoría de RedesTipos de Problemas de
RedesÁrbol de Expansión Mínima
El algoritmo del árbol de expansión mínima es un modelo de optimización de redes que consiste en enlazar todos los nodos de la red de forma directa y/o indirecta con el objetivo de que la longitud total de los arcos o ramales sea mínima.
N= el conjunto de nodos de la red.Ck= Conjunto de nodos que se han enlazado de forma permanente en la iteración kČko= Conjunto de nodos que hacen falta por enlazarse de forma permanente.
Teoría de RedesTipos de Problemas de
Redes
Características de Árbol de Expansión Mínima
1. Se tienen los nodos de una red pero no las ligaduras. En su lugar se proporcionan las ligaduras potenciales y la longitud positiva para cada una si se inserta en la red.
2. Se desea diseñar la red con suficientes ligaduras para satisfacer el requisito de que haya un camino entre cada par de nodos.
3. El objetivo es satisfacer este requisito de manera que se minimice la longitud total de las ligaduras insertadas en la red.
Teoría de RedesTipos de Problemas de
RedesEjercicio de Árbol de Expansión MínimaLa ciudad de Mérida cuenta con un nuevo plan parcial de vivienda el cual contará con la urbanización de más de 7 proyectos habitacionales que se ubicarán a las afueras de la ciudad. Dado que el terreno en el que se construirá no se encontraba hasta ahora dentro de las zonas urbanizables de la ciudad, el acueducto municipal no cuenta con la infraestructura necesaria para satisfacer las necesidades de servicios públicos en materia de suministro de agua. Cada uno de los proyectos de vivienda inició la construcción de un nodo de acueducto madre, el cual cuenta con las conexiones de las cunidades de vivienda propias de cada proyecto (es decir que cada nodo madre solo necesita estar conectado con un ducto madre del acueducto municipal para contar con su suministro). El acueducto municipal al ver la situación del plan parcial debe de realizar las obras correspondientes a la instalación de ductos madres que enlacen todos los nodos del plan con el nodo Meléndez (nodo que se encuentra con suministro de agua y que no pertenece al plan parcial de .
Teoría de RedesTipos de Problemas de
Redes
vivienda, además es el más cercano al mismo), la instalación de los ductos implica obras de excavación, mano de obra y costos de los ductos mismos, por lo cual optimizar la longitud total de los enlaces es fundamental. Las distancias existentes (dadas en kilómetros) correspondientes a las rutas factibles capaces de enlazar los nodos del plan parcial que se presentan a continuación. Además la capacidad de bombeo del nodo Meléndez es más que suficiente para satisfacer las necesidades de presión que necesita la red madre.El acueducto municipal le contacta a usted para que mediante sus conocimientos en teoría de redes construya una red de expansión que minimice la longitud total de ductos y que enlace todos los nodos del plan parcial de vivienda.
Ejercicio de Árbol de Expansión Mínima
Teoría de RedesRed Madre
Teoría de RedesTipos de Problemas de
RedesSolución
Paso 0: Se definen los conjuntos iniciales Ck={ø} que corresponde al conjunto de nodos enlazados de forma permanente en la iteración indicada en el subíndice y Čko={N =1,2,3,4,5,6,7,8} que corresponde al conjunto de nodos pendientes por enlazar de manera permanente en la iteración indicada en el subíndice.
Paso 1: Se debe definir de manera arbitraria el primer nodo permanente del conjunto Čko, en este caso escogeremos el nodo 1, por ende C1={i}={1} y Čko={N-i}= {2,3,4,5,6,7,8},
Teoría de RedesTipos de Problemas de
Redes
Paso 2: Ahora se debe seleccionar el nodo j del conjunto ČKo-1 (es decir del conjunto del paso 1) el cual presente el arco con la menor longitud y que se encuentre enlazado con uno de los nodos de enlace permanente del conjunto Ck-1 en el cual ahora solo se encuentra el nodo 1 (es decir que se debe de encontrar un nodo que tenga el arco de menor longitud enlazado al nodo 1). Ver Gráfica 1.1Paso 3: Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración. Ahora se seleccionará un nuevo nodo j del conjunto Č2 que presente el enlace (ramal o arco) de menor longitud con los nodos que se encuentran en el conjunto C2. Ver Gráfica 1.2
Solución
Teoría de Redes
Grafica 1.1Árbol de Expansión
Mínima
Al actualizar los conjuntos quedan así: C2 = {1,2} y Č2 = {3,4,5,6,7,8}
Teoría de Redes
Al actualizar los conjuntos quedan así:C3 = {1,2,4} y Č3 = {3,5,6,7,8}
Grafica 1.2Árbol de Expansión
Mínima
Teoría de RedesTipos de Problemas de
Redes
Paso 4: Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración. Ver Gráfica 1.3Al actualizar los conjuntos quedan así:C4 = {1,2,4,5} y Č4 = {3,6,7,8}Paso 5: Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración. Ver Gráfica 1.4Al actualizar los conjuntos quedan así:C5 = {1,2,4,5,7} y Č5 = {3,6,8}Paso 6: Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración. Ver Gráfica 1.5Al actualizar los conjuntos quedan así:C6 = {1,2,4,5,7,6} y Č6 = {3,8}
Solución
Teoría de Redes
Lo que representan los arcos naranja y verde es ya conocido, ahora la línea azul interrumpida irá trazando nuestro árbol de expansión final. Dado a que el arco menor es el de longitud 3, ahora se enlazará de manera permanente el nodo 5.
Grafica 1.3Árbol de Expansión
Mínima
Teoría de Redes
Ahora se enlazará de manera permanente el nodo 7.
Grafica 1.4Árbol de Expansión
Mínima
Teoría de Redes
Ahora se enlazará de manera permanente el nodo 6.
Grafica 1.5Árbol de Expansión
Mínima
Teoría de RedesTipos de Problemas de
Redes
Paso 7: Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración. Ver Gráfica 1.6Al actualizar los conjuntos quedan así:C7 = {1,2,4,5,7,6,3} y Č7 = {8}
Paso 8: Ahora se procede a actualizar k ya que se procede a efectuar la última iteración. Ver Gráfica 1.7 Al actualizar los conjuntos quedan así:C8 = {1,2,4,5,7,6,3,8} = {N} y Č8 = {ø}
Por ende se ha llegado al Árbol de Expansión Mínima
Solución
Teoría de Redes
Se rompen los empates de forma arbitraria, ahora se enlazará de manera permanente el nodo 3
Grafica 1.6Árbol de Expansión
Mínima
Teoría de Redes
Ahora se enlazará de manera permanente el nodo 8.
Grafica 1.7Árbol de Expansión
Mínima
Teoría de Redes
Árbol que presenta una longitud total minimizada de 21 kilómetros de ductos
Árbol de Expansión Mínima Árbol de Expansión
Mínima
Teoría de Redes
Solución por WinQsb
Árbol de Expansión Mínima
Teoría de RedesÁrbol de Expansión
MínimaPaso 1
Teoría de RedesÁrbol de Expansión
MínimaPaso 2
Teoría de RedesÁrbol de Expansión
MínimaPaso 3
Teoría de RedesTipos de Problemas de
RedesFlujo a Costo Mínimo
Flujo de costo mínimo o de los mínimos costos es un algoritmo desarrollado con el objetivo de resolver problema de trasporte o de distribución, arrojando mayores resultados que métodos como el de la esquina noroeste, dado que se enfoca en las rutas que presentan los menores costos.
El objetivo fundamental de este método es minimizar el costo total de enviar el suministro disponible a través de la red
para satisfacer la demanda total
Teoría de Redes La red es una red dirigida y conexa.
Al menos uno de los nodos es un nodo fuente.
Al menos uno de los nodos es un nodo demanda.
El resto de los nodos son nodos de trasbordo.
Se permite el flujo a través de un arco sólo en la dirección que indica la flecha, donde la cantidad máxima de flujo está dada por la capacidad del arco.
La red tiene suficientes arcos con suficiente capacidad para permitir que todos los flujos generados por los nodos fuente lleguen a los nodos demanda.
El costo del flujo a través del arco es proporcional a la cantidad de ese flujo, donde se conoce el costo por unidad.
Cara
cter
ísti
cas
Teoría de RedesTipos de Problemas de
RedesEjercicio de Flujo a Costo MínimoLa Distribuidora Rosal tiene dos fábricas que producen un producto que es necesario enviar a dos bodegas. Algunos detalles son:
La fábrica 1 está produciendo 80 unidades. La fábrica 2 está produciendo 70 unidades.La bodega 1 necesita 60 unidades.La bodega 2 necesita 90 unidades.
(Cada unidad corresponde a un camión lleno del producto.)
Costo por ferrocarril de la fabrica 1 a la Bodega 1 es de 700$ por unidadCosto por ferrocarril de la fabrica 2 a la Bodega 2 es de 900$ por unidad
Teoría de RedesTipos de Problemas de
Redes
FIGURA 1.1Distribución del
problema
F2
B 2
B 1
C D
F1
DEMANDAOFERTA
80 UND.
70 UND.
60 UND.
90 UND.
Ejercicio de Flujo a Costo Mínimo
Teoría de RedesTipos de Problemas de
Redes
Centro de Distribució
nBodega 1 Bodega 2 Producci
ón Fabrica 1 300$ 700$ - 80 und.
Fabrica 2 400$ - 900$ 70 und.
Centro de Distribución - 200$ 400$ -
Asignación - 60 und. 90 und.
Ejercicio de Flujo a Costo Mínimo
Teoría de RedesTipos de Problemas de
Redes
FIGURA 1.2Datos para Distribución del
problema
F2
B2
B1
DC
F1
DEMANDAOFERTA
80 UND.
70 UND.
60 UND.
90 UND.
300 dólares por unidad
700 dólares por unidad
200 dólares por unidad
50 unidades máximas
400 dólares por unidad
50 unidades máximas 50 unidades máximas
400 dólares por unidad
900 dólares por unidad
50 Unidades máximas
Ejercicio de Flujo a Costo Mínimo
Teoría de RedesTipos de Problemas de
Redes
SoluciónCosto total de envío = 30(700 dólares) + 50(300 dólares) + 50(400 dólares) + 50(200 dólares) + 50(400 dólares) + 20(900 dólares) = 104 000 dólares
FIGURA 1.3 Un modelo de red para el problema de la Distribuidora Rosal, como un problema de flujo a costo mínimo.
F2 B 2
B 1
CD
F1
[80]
[70]
[60]
[90]
[50]
[50 ] [ 50]
[50]300
400400
200[0]
Ejercicio de Flujo a Costo Mínimo
[700]
[900]
Teoría de RedesTipos de Problemas de
Redes
SoluciónCosto total de envío = 30(700 dólares) + 50(300 dólares) + 30(400 dólares) + 30(200 dólares) + 50(400 dólares) + 40(900 dólares) = 110 000 dólares
FIGURA 1.4La solución óptima para el problema de la Distribuidora Rosal, donde las cantidades de los envíos se indican entre paréntesis sobre las flechas.
F2 B 2
B 1
C D
F1
[-60]
[-90]
[80]
[70]
[0]
(30)
(50) (30)
(30)
(50)(50)
Ejercicio de Flujo a Costo Mínimo
Teoría de
GRACIAS POR
SU ATENCIÓN