Modelos

EL PROBLEMA DE LA RUTA MAS CORTA:
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. El problema se resuelve por el “algoritmo de etiquetado”.

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

DEFINICIÓN DEL PROBLEMA

-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 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 nodosy 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.

PROBLEMA DE LA RUTA MÁS CORTA

¿Cuál es el camino más corto desde la origen (s de “source”) hasta el destino (t) ?
Supuestos:
Existe un camino de la fuente a todos los demás nodos
Todos los largos de los arcosson no negativos
• ¿Cuál es el camino más corto del nodo 1 al 6 ?

• En general la formulación con LP de este problema, desde una origen s a un destino t está dada por:

• Otra formulación, para determinar la ruta más corta a n nodos es enviar “un” paquete a desde s a cada n-1 nodos.

EL PROBLEMA DEL ARBOL DE MINIMA Y EXPANSION

Dado un grafo conexo, no dirigido G. Un árbol de expansiónes un árbol compuesto por todos los vértices y algunas (posiblemente todas) de las aristas de G. Al ser creado un árbol no existirán ciclos, además debe existir una ruta entre cada par de vértices.

Un grafo puede tener muchos arboles de expansión, veamos un ejemplo con el siguiente grafo:

En la imagen anterior se puede observar que el grafo dado posee 3 arboles de expansión, dichos arbolescumplen con las propiedades antes mencionadas como son unir todos los vértices usando algunas aristas.

Árbol de Expansión Mínima
Dado un grafo conexo, no dirigido y con pesos en las aristas, un árbol de expansión mínima es un árbol compuesto por todos los vértices y cuya suma de sus aristas es la de menor peso. Al ejemplo anterior le agregamos pesos a sus aristas y obtenemos los arboles deexpansiones siguientes:

De la imagen anterior el árbol de expansión mínima seria el primer árbol de expansión cuyo peso total es 6.
El problema de hallar el Árbol de Expansión Mínima (MST) puede ser resuelto con varios algoritmos, los mas conocidos con Prim y Kruskal ambos usan técnicas voraces (greedy).

EL PROBLEMA DE FLUJO MAXIMO
En algunas redes circula por los arcos un flujo (envío ocirculación de unidades homogéneas de algún producto: automóviles en una red de carreteras, litros de petróleo en un oleoducto, bits por un cable de fibra óptica) desde el origen o fuente al destino, también denominado sumidero o vertedero. Los arcos tienen una capacidad máxima de flujo, y se trata de enviar desde la fuente al sumidero la mayor cantidad posible de flujo, de tal manera que:
* Elflujo es siempre positivo y con unidades enteras.
* El flujo a través de un arco es menor o igual que la capacidad.
* El flujo que entra en un nodo es igual al que sale de él.
En el caso de que el origen o el destino no existan en el problema, se añaden ficticiamente utilizando arcos unidireccionales de capacidad infinita, como en grafo mostrado a continuación:

Corte: Un corte...