Este tipo de problemas busca encontrar la ruta más corta entre dos nodos de una red, en la cual la longitud o arco tiene un costo positivo y así minimizar el costo total. Este tipo de problemas es fundamental en áreas como investigación de operaciones, ciencia de la computación e ingeniería. El por qué de su importancia es:
- Aplicaciones prácticas como el envío de algún material entre dos puntos específicos de forma eficiente, económica o rápida.
- Al ser aplicados a una red con características especificas como acíclica y costos positivos, los resultados que arroja son exactos a un tiempo y costo razonables.
- Se puede usar como inicio en un estudio de modelos complejos de redes, que es cuando no se conoce la estructura de la red.
- Se utiliza como subproblemas en la solución de problemas combinatorios y redes, resultan auxiliares para encontrar una buena solución.
Ruta más corta en programación lineal: Se puede plantear como el envío de una unidad de flujo del nodo origen al nodo destino al mínimo costo. Se pueden presentar de diferentes formas:
- Para que exista solución, debe existir una trayectoria. Además de que no existen circuitos negativos.
- Debe existir rutas del nodo origen a los nodos de la red.
- Entre cada par de nodos debe existir al menos una trayectoria.
- Nodo origen, comienza de la ruta.
- Arco, línea que une los nodos.
- Nodo adyacente, nodos conectados por un arco.
- Nodo destino, finaliza la ruta.
- Etiquetas, estas nos van indicando la longitud de un arco otro y de qué nodo viene, se representa entre corchetes [distancia del nodo, nodo del que parte]
A continuación se presenta un vídeo de cómo se resuelve un problema de ruta corta.
Bibliografía
http://www.academia.edu/17257056/PROBLEMA_DE_LA_RUTA_M%C3%81S_CORTA
Por qué no ir de e a t, así nos quedaríamos con 15 y no 16 :v
ResponderEliminarCorrecto
Eliminar