Modelo de redes

MODELOS DE REDES
La familia de redes de los problemas de optimización incluye los siguientes prototipos de modelos: Problemas de asignación, camino crítico, flujo máximo, camino más corto, transporte y costo mínimo de flujos. Los problemas son establecidos fácilmente mediante el uso de arcos de redes y de los nodos.
Los modelos de redes son aplicables a una extensa variedad de problemas dedecisión, los cuales pueden ser modelados como problemas de optimización de redes que pueden ser eficiente y efectivamente resueltos.

DEFINICION DE COMPONENTES:
Nodo: usualmente llamado vértice, o punto y es representado por un círculo.
Arco: llamado borde o flecha, el cual podría ser directo o indirecto. La cabeza es el destino, y la cola el origen. La cabeza y la cola son nodos que puedenestar tanto al origen como al final.
Una red con n nodos podría tener tantos arcos como n! /[(n-2)! 2!] = n(n-1)/2. Si están dirigidos, este número pudiese ser doble. Este enorme número de arcos posibles es una de las razones del porque existen soluciones de algoritmos especiales para problemas de redes particulares.
1. MODELO DE LA RUTA MÁS CORTA
El objetivo del modelo es determinar la rutamás corta a través de una red, aquí existe dos nodos especiales llamados uno llamado origen y el otro destino en donde el costo del camino es la suma de los costos
Formulación como un PL de problema de la ruta más corta
El modelo de PL de la ruta más corta se construye de la siguiente manera:
1. Cada variable corresponde a un arco.
2. Cada restricción corresponde a un nodo.
Por lotanto, si Xij representa la cantidad de flujo en el arco (i,j), el modelo de la ruta más corta con n nodos está dado como:
Min Z=i jCijXij
Sujeto a:
ORIGEN
i,jXij=1
INTERMEDIO
(i,k)xik=(k,j)xkj
Para toda k ≠ 1 o n
DESTINO
i,nXin=1
Xij≥0 Para toda i y j.
Con:
cij como la distancia en el Arco del nodo i al nodo j.
n : nodo final

Algoritmo (ETIQUETADO)

[Pa ; na]
Nodo precedenteDistancia acumulada desde el nodo inicial

Pasos a seguir
a. Asignar al nodo origen el rótulo permanente [0 , na]
b. Determinar rótulos tentativos para los nodos a los que se puede llegar en forma directa desde el nodo origen 1
c. Identificar el nodo con la etiqueta tentativa que tenga el menor valor de distancia, y hacer rótulo permanente.
d. En caso que hay coincidencia enel etiquetado, en un mismo nodo con igual o menor valor en el primer elemento se hace permanente ambos, en caso fuera mayor será descartado.
e. Repetir las secuencias b y c.
f. Identificar el primer elemento que tenga menor valor en el nodo destino, hacer permanente y retroceder por las redes que se conectan y por aquellas que tengan rótulo permanente, encontrando así la distancia o laruta mas corta desde el origen hasta el destino.
2. MODELO DE FLUJO MÁXIMO
Muchos problemas pueden ser modelados mediante una red en la cual se considera que los arcos tienen la capacidad de limitar la cantidad de un producto que se puede enviar a través del arco. En estas situaciones, frecuentemente se desea transportar la máxima cantidad de flujo desde un punto de partida llamado fuente haciaun punto final denominado pozo.
Programacion lineal
Max Z=f
Sujeto a:
ORIGEN
i,jXij=f
INTERMEDIO
(i,k)xik=(k,j)xkj
Para toda k ≠ 1 o n
DESTINO
i,nXin=f
CANTIDAD DE FLUJO
Xij≤cij
CONDICION DE NO NEGATIVIDAD
Xij≥0 Para toda i y j.
Con:
cij como la distancia en el Arco del nodo i al nodo j.
n : nodo final

Algoritmo de Saturación
Pasos a seguir
a. Elegir cualquier rutadel nodo de entrada, de preferencia el de mayor valor (capacidades residuales mayores que cero en todos los arcos ó CR>0).
b. Encontrar la menor capacidad de flujo de la rama, sobre el camino elegido desde el nodo de entrada.
c. Restar el flujo obtenido, con el valor de todos los arcos de la ruta elegida, y asignarle el nuevo valor a cada arco.
d. El arco que obtiene el valor cero, es...