Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 278 vistas

    La Ruta Mas Corta

    Cargado por

    AaronLopezR
    El método de la ruta más corta permite encontrar la ruta óptima entre dos puntos en una red, minimizando la distancia o el costo. Tiene aplicaciones como el transporte, telecomunicaciones y planeación de producción. El problema de la ruta más corta es fundamental en investigación de operaciones e ingeniería, ya que existen métodos eficientes para encontrar soluciones exactas. Como ejemplo, se modela encontrar la ruta más corta entre dos nodos en una red que representa una mina, resolviéndolo mediante programación entera.

    Copyright:

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

    La Ruta Mas Corta

    Cargado por

    AaronLopezR
    278 vistas6 páginas
    El método de la ruta más corta permite encontrar la ruta óptima entre dos puntos en una red, minimizando la distancia o el costo. Tiene aplicaciones como el transporte, telecomunicaciones y planeación de producción. El problema de la ruta más corta es fundamental en investigación de operaciones e ingeniería, ya que existen métodos eficientes para encontrar soluciones exactas. Como ejemplo, se modela encontrar la ruta más corta entre dos nodos en una red que representa una mina, resolviéndolo mediante programación entera.

    Descripción original:

    Metodo de la rutamas corta, INVOPE

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

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

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El método de la ruta más corta permite encontrar la ruta óptima entre dos puntos en una red, minimizando la distancia o el costo. Tiene aplicaciones como el transporte, telecomunicaciones y planeación de producción. El problema de la ruta más corta es fundamental en investigación de operaciones e ingeniería, ya que existen métodos eficientes para encontrar soluciones exactas. Como ejemplo, se modela encontrar la ruta más corta entre dos nodos en una red que representa una mina, resolviéndolo mediante programación entera.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    278 vistas6 páginas

    La Ruta Mas Corta

    Cargado por

    AaronLopezR
    El método de la ruta más corta permite encontrar la ruta óptima entre dos puntos en una red, minimizando la distancia o el costo. Tiene aplicaciones como el transporte, telecomunicaciones y planeación de producción. El problema de la ruta más corta es fundamental en investigación de operaciones e ingeniería, ya que existen métodos eficientes para encontrar soluciones exactas. Como ejemplo, se modela encontrar la ruta más corta entre dos nodos en una red que representa una mina, resolviéndolo mediante programación entera.

    Copyright:

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

    LA RUTA MAS CORTA

    El mtodo de la ruta ms corta es un mtodo de programacin lineal, que permite


    buscar la solucin a un problema de optimizacin que resulte de una combinatoria
    y de diferentes aplicaciones, el objetivo de este mtodo esta en encontrar rutas
    cortas o de menor costo, segn sea el caso, que va desde un nodo especifico
    hasta cada uno de los dems nodos de la red. En este sentido un nodo es una
    representacin grfica en forma de circulo, este nodo es muy importante ya que
    denota los orgenes y destinos del problema que se realice, asimismo una red
    representa un conjunto de puntos y lneas que conectan pares de puntos, estos
    puntos son los que llamaremos nodos y las lneas seran las aristas., por ejemplo:

    APLICACIONES:
    En cuanto a sus aplicaciones este modelo tiene muchas aplicaciones en la
    vida prctica, dentro de las que podemos mencionar:
    Transporte.
    Horarios de operadores telefnicos.
    Planeacin de trfico urbano.
    Trasbordo.
    En las redes elctricas.
    Diseo de rutas de vehculos.
    Telecomunicaciones.
    Planeacin de inventarios.
    Planeacin de produccin, entre otros

    IMPORTANCIA.
    El problema de la Ruta ms Corta es fundamental en muchas reas, como
    son: investigacin de operaciones, ciencia de la computacin e ingeniera.
    Algunas de las razones son:

    I. La amplia variedad de aplicaciones prcticas como es el envo de


    algn material entre dos puntos especficos de la forma ms eficiente,
    econmica o rpida.

    II. Existen mtodos de solucin eficientes, los cuales al ser aplicados a


    una red con caractersticas especficas (a cclica y con costos no
    negativos), proveen una solucin exacta a un tiempo y costo razonables.

    III. Se puede utilizar como inicio en el estudio de modelos complejos


    de redes, esto es, cuando no se conoce la estructura de la red se pueden
    aplicar algoritmos para conocer algunas caractersticas de la red (presencia
    de ciclos negativos).

    IV. Se utiliza frecuentemente como sub-problemas (subrutinas) en la


    solucin de problemas combinatorios y redes, as en el caso de problemas
    para los cuales no existe un algoritmo de solucin exacto (p. e. problemas
    NP-completos), la aplicacin de algoritmos de ruta ms corta, resultan
    auxiliares para encontrar una buena solucin.

    EJERCICIOS DE MINERA.

    1.- Consideremos el siguiente diagrama donde los nmeros asignados a


    cada uno de los arcos representan la distancia en kilmetros de un nodo a
    otro. Se desea encontrar la ruta con la distancia mnima para ir de la
    bocamina principal (nodo1) a la galera 49 (nodo 8) de la mina La
    Viesca.

    El tamao reducido de la red anterior permite encontrar el camino ms corto


    simplemente enumerando las distintas alternativas que comenzando en el
    nodo 1 permita llegar al nodo 8. De esta forma las rutas posibles son:

    Ruta 1-2-5-7-8: 4+8+17+9 = 38[km]


    Ruta 1-3-4-7-8: 3+12+20+9 = 44[km]
    Ruta 1-3-4-6-8: 3+12+2+22 = 39[km]
    Ruta 1-3-4-8: 3+12+15 = 30[km]
    Ruta 1-3-6-8: 3+4+22 = 29[km]

    La ruta o camino ms corto est dada por la secuencia 1-3-6-8 con una
    distancia total de 29[km].

    A continuacin se formula un modelo de Programacin Entera que permite


    extender este tipo de resultados a un problema de estas caractersticas:

    Variables de Decisin:
    Funcin Objetivo: Minimizar la distancia total en [km] dada por la siguiente
    expresin:

    Restricciones:

    La primera restriccin (1) garantiza que slo un nodo (entre el 2 y el


    3) pueda ser el que se visita a continuacin de comenzar en el nodo
    1.
    La restriccin (2) determina que si se visit el nodo 2 despus del
    nodo 1, entonces necesariamente el nodo 5 ser visitado despus
    del nodo 2.
    La restriccin (3) permite verificar que si el nodo 3 fue visitado luego
    del nodo 1, entonces a continuacin se visita el nodo 4 o el nodo 6
    (slo uno de ellos).
    La restriccin (4) establece que si el nodo 5 fue visitado luego del
    nodo 2, entonces el nodo 7 debe ser visitado luego del nodo 5.
    La restriccin (5) garantiza que si el nodo 4 fue visitado luego del
    nodo 3, entonces a continuacin se visita uno de los siguientes
    nodos: 7, 8 o 6.
    La restriccin (6) indica que si el nodo 6 fue visitado inmediatamente
    luego de estar en el nodo 3 o 4, a continuacin se visita el nodo 8.
    La restriccin (7) determina que si el nodo 7 fue visitado
    inmediatamente luego de estar en el nodo 4 o 5, a continuacin se
    visita el nodo 8.
    Finalmente la restriccin (8) asegura que ya sea el nodo 7, 4 o 6 sea
    el ltimo en visitar previo a terminar la ruta en el nodo 8.

    2.- Se tiene la red de ruta de la figura 1. Suponer que se desea determinar


    la ruta ms corta del nodo 1 al nodo 2; esto es, s = 1 y t = 2. La figura 1
    muestra como entra el flujo unitario en el nodo 1 y sale en el nodo 2.

    Figura 1: Insercin de un flujo unitario para determinar la ruta ms corta

    entre el nodo s = 1 y t = 2. El nmero junto a cada camino corresponde a su

    largo respectivo.

    La lista del programa lineal asociado, usando la formulacin 1, se ve a


    continuacin:
    Las restricciones representan la conservacin de flujo en cada nodo. Por
    ejemplo, en el nodo 2 flujo que entra = flujo que sale es x12 + x42 = 1 +
    x23. Ntese que una de las restricciones siempre es redundante. Por
    ejemplo, si se suman las ltimas cuatro restricciones en forma simultanea
    se obtiene x12+x13 = 1, que es igual que la restriccin 1.

    La solucin optima es z = 55, x13 = 1, x34 = 1, x42 = 1.


    Esta solucin expresa la ruta ms corta del nodo 1 al nodo 2 como
    1342, y la distancia asociada es z = 55 (millas).

    También podría gustarte