Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 31 vistas

    CONCEPTOS BÁSICOS Redes

    Cargado por

    Usuario Gratis
    El documento describe conceptos básicos de redes como nodos, arcos y sus valores asociados. Luego presenta varios problemas comunes en redes como encontrar la ruta más corta o el flujo máximo, y los modelos matemáticos como el problema de la ruta más corta o el flujo máximo para resolverlos. Finalmente, menciona otros casos especiales como redes planas o ciclos de Euler, y el algoritmo de Dijkstra para encontrar la ruta más corta en una red cuando los costos son no negativos.

    Copyright:

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

    CONCEPTOS BÁSICOS Redes

    Cargado por

    Usuario Gratis
    31 vistas14 páginas
    El documento describe conceptos básicos de redes como nodos, arcos y sus valores asociados. Luego presenta varios problemas comunes en redes como encontrar la ruta más corta o el flujo máximo, y los modelos matemáticos como el problema de la ruta más corta o el flujo máximo para resolverlos. Finalmente, menciona otros casos especiales como redes planas o ciclos de Euler, y el algoritmo de Dijkstra para encontrar la ruta más corta en una red cuando los costos son no negativos.

    Descripción original:

    REDES

    Título original

    CONCEPTOS BÁSICOS redes

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El documento describe conceptos básicos de redes como nodos, arcos y sus valores asociados. Luego presenta varios problemas comunes en redes como encontrar la ruta más corta o el flujo máximo, y los modelos matemáticos como el problema de la ruta más corta o el flujo máximo para resolverlos. Finalmente, menciona otros casos especiales como redes planas o ciclos de Euler, y el algoritmo de Dijkstra para encontrar la ruta más corta en una red cuando los costos son no negativos.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    31 vistas14 páginas

    CONCEPTOS BÁSICOS Redes

    Cargado por

    Usuario Gratis
    El documento describe conceptos básicos de redes como nodos, arcos y sus valores asociados. Luego presenta varios problemas comunes en redes como encontrar la ruta más corta o el flujo máximo, y los modelos matemáticos como el problema de la ruta más corta o el flujo máximo para resolverlos. Finalmente, menciona otros casos especiales como redes planas o ciclos de Euler, y el algoritmo de Dijkstra para encontrar la ruta más corta en una red cuando los costos son no negativos.

    Copyright:

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

    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.
    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
    PROBLEMAS Y MODELOS DE
    • REDES
    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
    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
    • 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
    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
    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.
    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
    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 .
    MCNFP: Minimum Cost Network
    Flow

    xij  número de unidades de flujo en el arco (i, j)


    c ij  costo unitario de transportación en el arco (i, j)
    b i  flujo neto en el nodo i (entrada - salida)
    L ij  cota inferior de capacidad en el arco (i, j)
    U ij  cot a superior de capacidad en el arco (i, j)
    min  c ij xij
    todoslos arcos

    s.a  xij   xki  bi para cada nodo


    j k

    L ij  xij  U ij para cada arco


    ALGORITMO DE DIJKTRA’S
    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.
    ALGORITMO DE DIJKTRA’S

    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 DIJKTRA’S
    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.
    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.

    También podría gustarte