Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 538 vistas

    3.3.-Arbol de Expansion Minima

    Cargado por

    Javier Yescas
    El documento describe el algoritmo del árbol de expansión mínima para conectar nodos de una red de manera óptima minimizando la longitud total de los enlaces. Explica los pasos iniciales de definir conjuntos de nodos enlazados y pendientes, y el paso general de seleccionar el nodo pendiente con el enlace más corto a un nodo ya enlazado y agregarlo al árbol. También presenta un ejemplo de aplicar el algoritmo para diseñar una red de ductos de agua conectando proyectos habitacionales de manera

    Copyright:

    © All Rights Reserved
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd

    3.3.-Arbol de Expansion Minima

    Cargado por

    Javier Yescas
    538 vistas32 páginas
    El documento describe el algoritmo del árbol de expansión mínima para conectar nodos de una red de manera óptima minimizando la longitud total de los enlaces. Explica los pasos iniciales de definir conjuntos de nodos enlazados y pendientes, y el paso general de seleccionar el nodo pendiente con el enlace más corto a un nodo ya enlazado y agregarlo al árbol. También presenta un ejemplo de aplicar el algoritmo para diseñar una red de ductos de agua conectando proyectos habitacionales de manera

    Título original

    3.3.-Arbol de expansion minima.pptx

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PPTX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El documento describe el algoritmo del árbol de expansión mínima para conectar nodos de una red de manera óptima minimizando la longitud total de los enlaces. Explica los pasos iniciales de definir conjuntos de nodos enlazados y pendientes, y el paso general de seleccionar el nodo pendiente con el enlace más corto a un nodo ya enlazado y agregarlo al árbol. También presenta un ejemplo de aplicar el algoritmo para diseñar una red de ductos de agua conectando proyectos habitacionales de manera

    Copyright:

    © All Rights Reserved
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    538 vistas32 páginas

    3.3.-Arbol de Expansion Minima

    Cargado por

    Javier Yescas
    El documento describe el algoritmo del árbol de expansión mínima para conectar nodos de una red de manera óptima minimizando la longitud total de los enlaces. Explica los pasos iniciales de definir conjuntos de nodos enlazados y pendientes, y el paso general de seleccionar el nodo pendiente con el enlace más corto a un nodo ya enlazado y agregarlo al árbol. También presenta un ejemplo de aplicar el algoritmo para diseñar una red de ductos de agua conectando proyectos habitacionales de manera

    Copyright:

    © All Rights Reserved
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    de 32

    ALGORITMO DEL ÁRBOL DE

    EXPANSIÓN MÍNIMA
    Nombre de la clase: Investigación de Operaciones II
    Profesor: Ing. Javier Humberto Yescas Parra
    Grupo: 562
    ALGORITMO DEL Á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 (entiéndase por longitud del arco una
    cantidad variable según el contexto operacional de minimización, y que
    puede bien representar una distancia o unidad de medida).
    ALGORITMO DEL ÁRBOL DE EXPANSIÓN MÍNIMA

    Sean

    N = {1,2,3,...,n} el conjunto de nodos de la red.


    Ck= Conjunto de nodos que se han enlazado de forma permanente en la
    iteración k
    Čk= Conjunto de nodos que hacen falta por enlazarse de forma
    permanente.
    PASO CERO (0): CONCEPTUALIZACIÓN DEL
    ALGORITMO

    Definir los conjuntos C0 = {ø} y Č0 = {N}, es decir que antes del paso 1 no
    se han enlazado de forma permanente nodo alguno, y por ende el
    conjunto que representa a los nodos que hacen falta por enlazarse de
    forma permanente es igual a la cantidad de nodos que existen en la red.
    PASO 1:

    Se debe de escoger de manera arbitraria un nodo en el conjunto


    Č0 llamado i el cual será el primer nodo permanente, a continuación se
    debe de actualizar el conjunto C1 = {i}, que significa que al tiempo en
    que el conjunto C1 gana el elemento i el conjunto Č0 pierde el
    elemento i por ende ahora será igual a Č1 = N - {i}, además se debe
    actualizar el subíndice de los conjuntos k, el cual ahora será igual a 2.
    PASO 2: PASO GENERAL "K"

    Se debe de seleccionar un nodo j del conjunto ČK-1 ("k-1" es el subíndice que


    indica que se está haciendo referencia al conjunto de la iteración
    inmediatamente anterior) el cual tenga el arco o ramal con menor longitud con
    uno de los nodos que se encuentran en el conjunto de nodos de enlace
    permanente CK-1. Una vez seleccionado se debe de enlazar de forma
    permanente lo cual representa que pasa a formar parte del conjunto de
    enlaces permanentes y deja de formar parte del conjunto que todavía se debe
    conectar para lograr la expansión. Al actualizar el algoritmo en este paso los
    conjuntos deben de quedar de la siguiente forma:

    CK = CK-1 + {j} mientras que ČK = ČK-1 - {j}


    PASO 2: PASO GENERAL "K"

    El paso general que define k que al mismo tiempo representa a las


    iteraciones debe de ejecutarse toda vez que el conjunto ČK no sea vacío,
    cuando este conjunto sea igual a vacío se tendrá el árbol de expansión
    mínima.

    El entendimiento del algoritmo desde el punto de vista algebraico no es


    quizá el más simple, sin embargo mediante el ejemplo gráfico se verá
    que es un algoritmo muy sencillo de elaborar.
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA

    La ciudad de Cali 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 unidades 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).
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA
    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
    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 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.
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA

    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.
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA

    • PASO 0:
    Se definen los conjuntos iniciales C0 = {ø} que corresponde al conjunto
    de nodos enlazados de forma permanente en la iteración indicada en el
    subíndice y Č0 = {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.
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA

    • PASO 1:
    Se debe definir de manera arbitraria el primer nodo permanente del
    conjunto Č0, en este caso escogeremos el nodo 1 (puede ser cualquier
    otro), que algebraicamente se representa con la letra i, se procede a
    actualizar los conjuntos iniciales, por ende C1 = {i} = {1} y Č0 = {N - i} =
    {2,3,4,5,6,7,8}, actualizamos k por ende ahora será igual a 2.
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA

    • PASO 2:
    Ahora se debe seleccionar el nodo j del conjunto ČK-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).
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA
    RESOLUCIÓN DEL PROBLEMA DEL ÁRBOL
    EXPANSIÓN MÍNIMA MEDIANTE WINQSB
    El primer paso para resolver un problema de transporte mediante WinQSB es ingresar al módulo Network Modeling.

    Luego debemos seleccionar la opción Minimal


    Spanning Tree (Árbol de Expansión Mínima).
    Además en este submenú debemos de
    especificar el nombre del problema y el número
    de nodos. En nuestro caso el número de nodos
    es igual a 8, luego click en OK.
    RESOLUCIÓN DEL PROBLEMA DEL ÁRBOL
    EXPANSIÓN MÍNIMA MEDIANTE WINQSB
    Una vez se realiza el paso anterior se abrirá una ventana en la cual aparecerá la siguiente matriz:
    RESOLUCIÓN DEL PROBLEMA DEL ÁRBOL
    EXPANSIÓN MÍNIMA MEDIANTE WINQSB

    En esta matriz se deben de consignar los valores de los


    ramales que unen las conexiones entre los nodos
    correspondientes, según el contexto de nuestro problema
    se deben de consignar las distancias entre los nodos si es
    que dichas conexiones existen de lo contrario en caso que
    la conexión no exista se debe dejar la celda en blanco.

    Hay que tener en cuenta que las distancias entre los nodos
    en este caso son exactamente conmutativas, es decir que si
    el nodo fuente es 2 y el destino es 4 la distancia existente
    entre estos es exactamente igual a la distancia existente
    entre un nodo fuente 4 y un nodo destino 2, sin embargo
    esta propiedad debe de especificarse en la matriz
    consignando los valores correspondientes a una conexión
    dos veces.
    RESOLUCIÓN DEL PROBLEMA DEL ÁRBOL
    EXPANSIÓN MÍNIMA MEDIANTE WINQSB
    Luego damos click en Solve and Analize y tendremos la siguiente ventana solución inmediatamente.
    PROBLEMAS
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA
    EJERCICIOS:
    •La siguiente red representa una serie de
    poblados que se encuentran comunicados
    a través de caminos rurales o
    empedrados. El Gobernador del Estado al
    que pertenecen ha aprobado se
    pavimenten los caminos que permitan unir
    a todos los poblados, buscando que la
    distancia a pavimentar sea la mínima
    posible. ¿Cuáles caminos son los que se
    deben de pavimentar?
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA

    •La siguiente red representa una serie de


    nuevas colonias que se han establecido en
    una localidad, la compañía de Luz desea
    suministrar el servicio correspondiente,
    para ello se requiere instalar el cableado
    eléctrico. Determine la cantidad de km de
    cable mínimo que debe de instalarse de tal
    forma que se proporcione el servicio a
    todas las colonias?
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA

    •Dada la siguiente
    red obtenga el árbol
    de expansión
    mínima.
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA
    •Un minero ha quedado atrapado en una
    mina, la entrada a la mina se encuentra
    ubicada en el nodo 1, se conoce de
    antemano que el minero permanece atrapado
    en el nodo 9, para llegar a dicho nodo hay
    que atravesar una red de túneles que van
    conectados entre sí. El tiempo de vida que le
    queda al minero sin recibir auxilio es cada
    vez menor y se hace indispensable hallar la
    ruta de acceso al nodo 9 más corta. Las
    distancias entre nodos de la mina se
    encuentran en la siguiente gráfica dadas en
    cientos de metros.
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA
    • Determinar el árbol de mínima expansión para el siguiente grafo:
    RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE
    EXPANSIÓN MÍNIMA

    También podría gustarte