MÉTODOS DE SOLUCIÓN PARA CADA TIPO DE MODELO
DE TOMA DE DECISIONES.
Flujo maximo
Hay problemas donde lo importante es la cantidad de flujo que pasa a través de la
red como por ejemplo: en las líneas de oleoductos, redes eléctricas o de
transmisión de datos. Por esta razón en dichos problemas se determina el flujo
máximo que pasa a través de una red.
Definiciones básicas
Flujo: Circulación de unidades homogéneas de un lugar a otro.
Capacidad de flujo: es la capacidad de unidades que pueden entrar por el nodo
fuente y salir por el nodo destino.
Origen o fuente de flujo: nodo por el cual el flujo ingresa.
Destino o Sumidero de flujo: nodo por el cual el flujo sale.
Capacidades residuales: capacidades restantes unas vez que el flujo pasa el arco.
Ford Fulkerson
Para la resolución de problemas de flujo máximo se requiere el uso del método
Ford Fulkerson. Este método propone buscar caminos en los que se pueda
aumentar el flujo hasta que se alcance el flujo máximo, la idea es encontrar una
ruta de penetración con un flujo positivo neto que una los nodos de origen y
destino.
El flujo 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.
Resolución de problema
Para resolver un problema de flujo máximo se debe seguir los siguientes pasos:
Se identifica el nodo origen y destino.
Se parte desde el nodo de origen y se escoge el arco que posea mayor flujo
Se identifica los nodos de transbordo.
Repetir como si el nodo intermediario fuera el nodo origen.
Se calcula "k" y las capacidades nuevas.
Dado el resultado se cambian las capacidades y se repite el mismo procedimiento
desde el inicio.
Formulario
Cij,ji =(Ci-K, Cj+K), donde:
C: capacidad
Ij: índices de los nodos
K: es el minimo flujo que pasa por el nodo, se calcula como k= min(capacidades
de la ruta).
Ejemplo
Hallar el flujo máximo del siguiente problema:
El nodo de origen como se puede observar es el numero 1 de color amarillo, y el
nodo de destino es el numero 5 de color azul.
Se escoge desde el nodo de origen aquel flujo que sea el mayor, en este caso es
30, y va dirigido al nodo numero 3
Se identifica el nodo de transbordo como [30,1], 30 es la capacidad, y 1 es el nodo
del cual proviene la capacidad y luego repetimos todo el proceso, como si el nodo
intermediario fuese el nodo de origen. Se tiene como flujo mayor 20 del nodo
numero 3 al nodo numero 5, con el nodo de transbordo como [20,5].
Ahora que hemos llegado al nodo de destino, procedemos a calcular "k" y las
capacidades nuevas.
K=min(∞,30,20)
K=20
C13,31 =(30-20, 0+20)
C13,31 =(10, 20)
C35,53 =(20-20, 0+20)
C35,53 =(0, 20)
Luego de haber calculado las nuevas capacidades, es necesario reemplazarlas.
Se realiza el proceso otra vez, haciendo la ruta con los mayores flujos.
K=min(∞,20,40,10,20)
K=10
C12,21 =(20-10, 0+10)
C12,21 =(10, 10)
C23,32 =(40-10, 0+10)
C23,32 =(30, 10)
C34,43 =(10-10, 5+10)
C34,43 =(0, 15)
C45,54 =(20-10, 0+10)
C45,54 =(10, 10)
Volvemos a hacer el proceso y escogemos el camino 1,2. Como se puede
observar si se tomara rumbo del nodo 2 al nodo 3 terminaría trancado,
obligándose a volver al nodo origen, por lo que se toma el camino 2,5.
K=min(∞,10,20)
K=10
C12,21 =(10-10, 10+10)
C12,21 =(0, 20)
C25,52 =(20-10, 0+10)
C25,52 =(10, 10)
Se actualizan las capacidades y procedemos a resolver de nuevo. Esta vez
agarraremos el camino de 1,3.
K=min(∞,10,10,10)
K=10
C13,31 =(10-10, 20+10)
C13,31 =(0, 30)
C32,23 =(10-10, 30+10)
C32,23 =(0, 40)
C25,52 =(10-10, 10+10)
C25,52 =(0, 20)
Y por ultimo escogemos el camino 1,4.
K=min(∞,10,10)
K=10
C14,41 =(10-10, 0+10)
C14,41 =(0, 10)
C45,54 =(10-10, 10+10)
C45,54 =(0, 40)
Reemplazando las nuevas capacidades, nos queda de la siguiente forma, las
capacidades del nodo de origen quedan como 0, por lo cual seguimos a sumar a
todas las K y ahi conseguimos el flujo máximo.
Flujo Máximo = Σ K
Flujo Máximo = 20+10+10+10+10
Flujo Máximo = 60
El flujo máximo que puede pasar del nodo origen 1 hasta el nodo destino es de 60.
La ruta más 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 la ruta 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 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.
EJEMPLO
Encontremos la distancia más corta entre el nodo "A" y el nodo "G".
1. Rotular el Nodo Inicial : Recordemos el formato del rótulo es : [distancia al
primer nodo, nodo precedente]. La distancia al primer nodo, es la distancia a sí
mismo en éste caso, por lo tanto es cero. El nodo precedente: como no viene de
ningún nodo, lo rotulamos vacio: [ 0, ] :
2. Rotular todos los nodos que dependan únicamente del nodo inicial:
A el Nodo B se puede llegar desde el Nodo A, con la ruta A-C-B o con la ruta A-D-
C-B. Así que depende de otros nodos a parte del Nodo inicial. Lo mismo podemos
decir del Nodo C. Pero...
... Pero al Nodo D sólo se puede llegar directamente desde el Nodo A. Este es el
nodo que vamos a rotular, y si hubieran más como él también los regalariamos,
pero en este ejemplo sólo tenemos el D.
El rótulo del Nodo D, es : [distancia mínima desde el Nodo Inicial, Nodo
Precedente]. La distancia mínima desde el Nodo Inicial al Nodo D es 15: no hay
otra alternativa, y el Nodo Precedente el "A". Rótulo: [15, "A"]
3. Rotular Todos los Nodos que tengan la información suficiente para rotularlos:
La información necesaria para rotular un Nodo con este algoritmo, es que todos
los Nodos de los que dependa, deben estar ya rotulados. Por ejemplo el Nodo B:
depende del A y del C. El Nodo A ya esta rotulado, pero el C aún no. Así que aún
no se puede rotular el Nodo B. El Nodo C depende del A y del D, y ambos están
rotulados, así que si podemos rotularlo. La distancia desde A es 8, y desde D es:
la distancia que tiene en el rótulo (que es la distancia mínima desde él al Nodo
inicial, o sea 15), MAS la distancia entre D y C = 15 +4 = 19: entre 8 y 19 es más
pequeño 8. Así que escogemos el Nodo A como precedente: el rótulo es [ 8 , "A"]
4. Seguir rotulando todos los Nodos que tengan información suficiente hasta llegar
al Nodo deseado:
G. Ahora ya hay información suficiente para rotular los Nodos B y F. Entonces
rotulemos el Nodo B (no importa cuál se haga primero, igual hay que rotularlos
todos). El rotulo para el Nodo B: La distancia desde A es 10, la distancia mínima al
Nodo inicial desde C es: el la distancia del rótulo de C: 8 + la distancia de C a B : 3
=> 8 + 3 = 11. El mínimo entre 10 y 11 es 10. Rótulo= [10, "A"].
Rótulo para el F: Desde C : 8 + 4 = 12 y desde D : 15 + 15 = 30. Entonces el
Rótulo es [12, "C" ]
Rótulo para el Nodo E: Desde B : 10 + 20 = 30 y desde C: 8 + 15 = 23 Rótulo :
[23,"C"]
Por último para el Nodo G: la distancia desde E es 23 + 5 = 28 y desde F es 12 +
3 = 15 Rótulo [15, F]
Ahora se puede leer la trayectoria mínima partiendo del rótulo del Nodo G, dicho
rotulo nos dice que viene del F el de F dice que viene del C y el del C dice que
viene del A. Solución: Distancia Mínima= 15 Ruta Más Corta = A-C-F-G
Arbol de mínima expansión.
La solución del árbol de mínima expansión es:
Sea N= {1,2,…,n} el conjunto de nodos de la red.
Ck= Conjunto de nodos que han estado conectados de manera permanente en la
iteración k.
Ck= Conjunto de nodos que se construirán permanentemente después de la
iteración k.
1.-Comience seleccionando el arco de menor longitud.
2.-En cada iteración agregue el siguiente arco de menor longitud del conjunto de
arcos disponibles, teniendo la precaución de no formar ningún ciclo.
3.-El algoritmo finalizara cuando todos los arcos estén conectados. Si N= número
de nodos entonces la solución optima debe incluir n-1 arcos.
Ejemplo
Encuentra el borde con el menor peso y resáltalo. Para este gráfico de ejemplo, he
resaltado el borde superior (de A a C) en rojo. Tiene el peso más bajo (de 1):
Encuentre el siguiente borde con el peso más bajo y resáltelo: Continúe
seleccionando los bordes más bajos hasta que todos los nodos estén en el mismo
árbol. Notas :
1. Si tiene más de un borde con el mismo peso, elija un borde con el peso
más bajo.
2. Tenga cuidado de no completar un ciclo (enrutar un nodo de vuelta a sí
mismo). Si su elección completa un ciclo, descarte su elección y pase al
siguiente peso más grande.
El árbol de expansión mínimo terminado para este ejemplo se ve así:
