domingo, 31 de marzo de 2013

Ruta más Corta y Árbol Mínimo Expandido (Grupo 1)

Ruta más Corta

Una RED es una gráfica que posee NODOS (ciudades, estaciones de metro, aeropuertos, etc.) que  se encuentran conectados mediante ARCOS (carreteras, líneas de metro, cableados eléctricos, rutas de avión) y que su función es trasferir unidades de un nodo a otro.
  • ·         Una ejemplo de red puede ser: (red de agua potable, red de comunicación, red logística)
  • ·         Los Nodos: representan: la demanda y/u  oferta de cada red.
  • ·         Los Arcos pueden ser: costo, distancia o capacidad.

Un problema de ruta más corta consiste en encontrar el camino  entre el nodo origen y el nodo destino pero a uno longitud mucho menor y eficiente. El problema de ruta más corta no solo se encuentra en redes de comunicaciones y trabas de trasporte sino que también abarca planificación de mantenimiento y reemplazo de maquinaria.

Estos problemas de camino mínimo se pueden resolver usando programación lineal, sin embargo, existe el algoritmo DIJKTRA´S que aprovechan mejor la estructura en red.

Ejemplo.

La empresa Gama AD surte a 7 supermercados con distintas ubicaciones entre Caracas y Miranda. Los administradores desean conocer la distancia más corta entre la empresa Gama AD y el Supermercado 5, según los kilómetros. 


A continuación se muestra cómo resolver el ejemplo usando una herramienta llamada WinQSB:


 





















Árbol de Expansión Mínima

Este problema surge cuando todos los nodos de una red deben conectarse entre ellos, sin formar un loop.
 Es apropiado para problemas en los cuales la redundancia es expansiva o el flujo a lo largo de los arcos se considera instantáneo.

Ejemplo:
La ciudad de Caracas esta planificando el desarrollo de una nueva línea de sistema de transito.
El sistema debe unir distritos, Universidades y centros comerciales.
La Dirección de transito necesita seleccionar un conjunto de líneas que conecten todos los centros a un mínimo costo.
La red seleccionada debe permitir:
      - Factibilidad de las líneas que deban ser construidas.
      - Mínimo costo posible por línea.



Se muestra a continuación como se resuelve el ejercicio con la herramienta WinQSB:

























Para mayor información consultar el siguiente video:







10 comentarios:

  1. Formulación de un problema de Ruta mas Corta como problema de Programacion Lineal:

    El modelo de PL de la ruta más corta se construye de la siguiente manera:

    Cada variable corresponde a un arco.
    Cada restricción corresponde a un nodo.

    Por lo tanto, si representa la cantidad de flujo en el arco (i,j), el modelo de la ruta más corta con n nodos está dado como:

    Z= ∑IJ∑i8 [dijxij]

    Minimizar

    Sujeto a:

    ∑(ij)[xij]=1 (fuente)

    ∑(ik)[xik] = ∑(kj)[xkj] para toda k 1 o n

    ∑(in)[xin]=1 (destino)

    Xij =>0 para toda i y j.

    La primera y última restricción señala que el flujo total (suma de variables) que sale del nodo 1 es igual a 1 y que flujo total que se recibe en el nodo n también es igual a 1. En cualquier nodo intermedio, el flujo total que entra al nodo es igual al flujo total que sale del mismo nodo. La función objetivo requiere que se minimice la distancia total que recorre la unidad del flujo.

    Información tomada de: http://alejandra090290.wordpress.com/problema-de-la-ruta-mas-corta/

    ResponderEliminar
  2. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  3. Algunas Aplicaciones

    La aplicación de estos problemas se ubica en las redes de comunicación eléctrica, telefónica, carretera, ferroviaria, aérea, marítima, etc. En donde los nodos representan un consumo eléctrico, teléfonos aeropuertos, computadoras,etc

    También se puede observar en en sistemas distribuidos, interpretación de datos climatológicos, visión artificial, análisis de imágenes, extracción de rasgos de parentesco, plegamiento de proteínas, reconocimiento de células cancerosas, entre otros.

    A continuación se proporciona una lista de algunos tipos importantes de aplicaciones de este problema.

    - Diseño de redes de telecomunicación (redes de fibra óptica, de computadores, telefónicas, de televisión por cable, etcétera). En una red de telecomunicaciones, sólo es necesario insertar suficientes ligaduras para que proporcionen una trayectoria entre cada par de nodos, de modo que el diseño de tales redes es una aplicación clásica del problema del árbol de expansión mínima. Debido a que algunas redes de comunicación ahora cuestan muchos millones de dólares, es muy importante optimizar su diseño encontrando el árbol de expansión
    mínima.

    Un ejemplo seria si una compañía de televisión por cable desea instalar en un vecindario sus cables pero estos solamente pueden recorrer por patrones o caminos específicos, seria útil saber cuales caminos son los mas cortos para así ahorrar la mayor cantidad de cable posible.

    Una aplicación similar a las redes de telecomunicación es la utilizada en redes de información entre servidores y computadoras cliente, para disminuir la distancia, aumentar la velocidad de transmisión de información y reducir los costos.

    - Diseño de redes de transporte para minimizar el costo total de proporcionar las ligaduras (vías ferroviarias, carreteras, etc.). Una aplicación característica es en la construcción de carreteras pavimentadas que unen varias poblaciones. El camino entre dos poblaciones puede pasar por uno o más poblaciones adicionales. El diseño más económico del sistema de caminos indica que se minimice la distancia total de caminos pavimentados, resultado que se obtiene implementando el algoritmo de árbol de expansión mínima.

    - Diseño de una red de líneas de transmisión de energía eléctrica de alto voltaje.

    - Diseño de una red de cableado en equipo eléctrico (como sistemas de cómputo) para minimizar la longitud total de cable

    - Diseño de una red de tuberías para conectar varias localidades.

    Referencias:

    - http://algoritmoshade.blogspot.com/2010/03/el-problema-que-yo-elegi-es-arbol-de.html
    - http://www.monografias.com/trabajos-pdf4/optimizacion-redes/optimizacion-redes.pdf

    ResponderEliminar
  4. Utilizando el algoritmo DIJKTRA'S de forma manual se puede observar en este video http://www.youtube.com/watch?v=yrNAtAIUhJA

    ResponderEliminar
  5. Aparte de las aplicaciones nombradas en los comentarios anteriores La Ruta más Corta también puede ser aplicada en la Sustitución de Equipo. En la siguiente link se da una explicación del problema, donde se Lisa Carr está a cargo de buscar el reemplazo de la maquinas fotocopiadoras para el servicio secretarial de PROTRAC, tomando en consideración aspectos como los costos de alquiler, costos de mantenimiento, entre otros aspectos que se explican con mayor claridad en el siguiente libro extraído de Google Book:
    G. D AUTOR EPPEN (2000).Business & Economics. Una aplicación de la ruta más corta (pp. 246). Extraído el 7 de abril de 2013: http://books.google.co.ve/books?id=DW-vtFYqh0YC&printsec=frontcover&source=gbs_ge_summary_r&cad=0#v=onepage&q&f=false

    ResponderEliminar
  6. El problema de la ruta más corta incluye un juego de nodos conectados donde sólo un nodo es considerado como el origen y sólo un nodo es considerado como el nodo destino. El objetivo es determinar un camino de conexiones que minimizan la distancia total del origen al destino.

    Se trata de encontrar la ruta de menor distancia, o costo ,a entre el punto de partida o nodo inicial y el destino o nodo terminal.

    Definición en un problema de la ruta mas corta

    -Se tienen n nodos, partiendo del nodo inicial 1 y terminando en el nodo final n.

    -Arcos bi-direccionales conectan los nodos i y j con distancias mayores que cero, dij

    -Se desea encontrar la ruta de mínima distancia que conecta el nodo 1 con el nodo n.

    Por medio de la aplicación del algoritmo etiquedato de este problema podemos conocer la menor distancia entre un nodo origen y un nodo destino.

    Pasos a seguir:

    Primer paso: Elaborar un cuadro con todos los nodos y los ramales que salen de él.

    Segundo paso: Partiendo del origen, debemos encontrar el nodo más cercano a él.

    Tercer paso: Anular todos los ramales que entren al nodo más cercano elegido.

    Cuarto paso: Comenzando en el origen se debe encontrar el nodo más cercano a él, por intermedio del(los) nodo(s) ya elegido(s) y volver al tercer paso hasta llegar al destino.

    Dicha Información fue extraída del siguiente link http://analisisderedes.wordpress.com/unidad-ii/problema-de-la-ruta-mas-corta/ hay se podrán visualizarlo mejor a través de imágenes para que así se puedan ayudar con las imagenes

    Así por medio de este Algoritmo podemos resolver este problema. Sin Embargo por excel también se puede resolver dicho problema a travez de su aplicación de Solven. Encontré un documento maravilloso que nos habla Modelos de Optimización de Redes ahí podemos encontrar Terminología de Redes,Problema de la Ruta Más Corta,Problema del Árbol de Expansión Mínima,Problema de Flujo Máximo,Problema del Flujo de Costo Mínimo todo eso y mas lo podran visualizar a travez del siguiente link http://www.monografias.com/trabajos-pdf4/optimizacion-redes/optimizacion-redes.pdf

    ResponderEliminar
  7. En el problema de ruta más corta es aplicado un algoritmo llamda DJKTRA'S pero a manera de completación, existe otro algoritmo. El algoritmo de Floyd consiste en mostrar la distancia entre dos nodos que se encuentren en la red.

    Para empezar muestra todos los caminos que puedan comunicar dos nodos y evalúa cada uno de ellos hasta encontrarse con esa distancia óptima. El algoritmo se presenta en matrices, que contienen diversas filas y columnas donde señalan el número infinito de nodos y la distancia.

    Para tomar un ejemplo suponemos existen tres nodos i, j y k. La distancia se representa en los arcos de la manera Dij, es decir, la distancia entre el nodo i y el nodo j y así sucesivamente en todos los arcos.

    Se puede decir, que la distancia más corta para llegar de el nodo i al nodo k es Dik. Pero, sí la distancia entre Dij + Dik< Dik no es correcta esa suposición. Así, se presenta el concepto de un algoritmo directo, donde se busca un óptimo tomando ya sea rutas directas o indirectas.

    A su vez, existe un programa llamado TORA que te permite resolver problemas de programación lineal. Incluye el resolver modelo de redes, por lo que funciona para ruta más corta. De igual manera, trae diversas opciones para resolverlo usando tanto el algoritmo DIJKTRA'S como el algoritmo Floyd.

    Más información para resolver problema de Ruta más corta con el algoritmo Floyd o aprender usar TORA en el siguiente link:

    http://books.google.co.ve/books?id=3oHztjMSuL8C&pg=PA220&lpg=PA220&dq=ruta+mas+corta+aplicaciones&source=bl&ots=nLEG3d0SzT&sig=mpUuAUAZ9jErCjEjihVTlOwThDg&hl=es&sa=X&ei=pw1iUbrpKpCo8ASDxIHQDA&ved=0CCoQ6AEwAA#v=onepage&q=ruta%20mas%20corta%20aplicaciones&f=false


    ResponderEliminar
  8. Este tipo de algoritmos y técnicas están asociadas a aplicaciones que tenemos hoy en día en nuestros aparatos móviles, estas son las aplicaciones que contienen mapas, y nos muestran rutas por la cuales transitar de un lado a otro, estas aplicaciones nos ayudan a llegar a un destino de la forma mas corta posible, estas técnicas son útiles para nuestra vida cotidiana, ya que al crearnos una ruta mas corta de llegada, nos ahorraría dinero de la gasolina y nuestro valioso tiempo, optimizar es vivir de la mejor manera posible.

    ResponderEliminar
  9. También, es importante saber que no todas las aplicaciones del problema de la ruta más corta involucran minimizar la distancia recorrida de un origen a un destino. De hecho, es posible que ni siquiera se refieran a un viaje. Los arcos pueden representar actividades de otro tipo, por lo que escoger una trayectoria a través de la red corresponde a seleccionar la mejor secuencia de actividades. Así, los números que indican las "'longitudes" de los arcos quizá sean, por ejemplo, los costos de las actividades, en cuyo caso el objetivo sería determinar qué secuencia de actividades minimiza el costo total.

    ResponderEliminar
  10. También podemos usar algoritmos de grafos para hallar el "Camino o Circuito de Euler". En estos grafos, cada nodo representa un punto del dibujo y una arista entre dos nodos indica que existe una línea entre los dos puntos correspondientes, ¿es posible dibujar una figura con un bolígrafo, pintando cada línea una sola vez, sin levantar el bolígrafo y acabando en el mismo punto donde se empezó?. Un
    camino de Euler es un camino que visita todas las aristas exactamente una vez, es un ciclo, no necesariamente simple. Es
    decir, los nodos se pueden visitar varias veces, pero las aristas se tienen que visitar una y solo una vez. Así que dado un grafo, tenemos que decidir si existe un circuito de Euler, verificando si existen algunas condiciones necesarias para que exista.
    Esta información y más la podemos encontrar en:
    http://dis.um.es/~ginesgm/files/doc/aed/sec5.6.3-5.8.pdf

    ResponderEliminar