ruta mas corta

El problema de la ruta mas corta determina la distancia menor entre un punto de origen y un punto de destino.
Un problema  de la ruta mas corta involucra una red conexa con un costo no  negativo asociado a cada rama. A un nodo se le denomina fuente y a otro se le denomina destino. El objetivo es determinar una ruta que una a la fuente con el origen, de manera que la suma de los costos asociados con las ramas en la ruta sea la mínima.

El algoritmo de Dijkstra es útil para determinar la ruta más corta entre el nodo del punto de origen y cada uno de los nodos de la red. Por otra parte, el algoritmo de Floyd es más general porque permite determinar la ruta más corta entre cualquier par de nodos de la red.
El Problema del Camino más Corto (o ruta más barata) consiste en encontrar una ruta o camino óptimo entre un nodo fuente y un nodo destino, los cuales están enlazados a través de una red con arcos que poseen un cierto atributo, el cual puede ser costo, distancia, tiempo, etc.
La Programación Entera permite abordar de forma eficiente este tipo de problemas, en especial cuando la cantidad de nodos y rutas posibles resulta ser un número significativo. Utilizar en estos casos un enfoque intuitivo de resolución es tedioso y de no ser exhaustivo no garantiza la identificación de la mejor alternativa o ruta.

La ruta o camino más corto esta dada por la secuencia 1-3-6-8 con una distancia total de 29[km].
A continuación se formula un modelo de Programación Entera que permite extender este tipo de resultados a un problema de estas características:
Variables de Decisión:
variable-binaria-ruta-mas-c
Función Objetivo: Minimizar la distancia total en [km] dada por la siguiente expresión:
funcion-objetivo-ruta-mas-c


Resultado de imagen para ruta mas corta

Comentarios

Publicar un comentario

Entradas más populares de este blog

compuertas lógicas

Imagen
Las Compuertas Lógicas  son circuitos electrónicos conformados internamente por transistores que se encuentran con arreglos especiales con los que otorgan señales de voltaje como resultado o una salida de forma booleana, están obtenidos por operaciones lógicas binarias (suma, multiplicación). También niegan, afirman, incluyen o excluyen según sus propiedades lógicas. Estas compuertas se pueden aplicar en otras áreas de la ciencia como  mecánica , hidráulica o  neumática . Existen diferentes tipos de compuertas y algunas de estas son más complejas, con la posibilidad de ser simuladas por compuertas más sencillas. Todas estas tienen tablas de verdad que explican los comportamientos en los resultados que otorga, dependiendo del valor booleano que tenga en cada una de sus entradas. Trabajan en dos estado, “1” o “0”, los cuales pueden asignarse a la lógica positiva o lógica negativa. El estado 1 tiene un valor de 5v como máximo y el estado 0 tiene un valor de 0v como míni...
Leer más

lógica matemática

Imagen
  Lógica  proposicional 1.1  El lenguaje  de la lógica proposicional 1.1.1 Proposiciones atómicas y proposiciones moleculares La lógica proposicional trata sobre la verdad o la falsedad de las proposiciones y de cómo la verdad se transmite de unas proposiciones (premisas) a otras (conclusión). Una proposición es la unidad mínima de significado susceptible de ser verdadera o falsa. Una palabra aislada, por sí misma, no nos dice nada. La palabra "perro" tiene una referencia, pero no nos da ninguna  información  si no es en el contexto de una proposición como "El perro está haciendo cosas raras". Por ello una palabra, a menos que constituya una proposición, no es verdadera o falsa. Sólo tienen  valor  de verdad las proposiciones. Debemos distinguir dos tipos de proposiciones: las proposiciones atómicas y las proposiciones moleculares. Las proposiciones atómicas son aquéllas que no se componen de otras proposiciones. La proposición La...
Leer más

ejemplos de aljebra de Boole

Imagen
                                                                                                                                                                                                                                                                                          ...
Leer más