miércoles, 15 de junio de 2011

Las redes de flujo son modelos matemáticos aplicables a situaciones tales como: sistemas de tuberías (para uídos como agua, petróleo o gas), redes de cableado eléctrico, sistemas de carreteras, sistemas de transporte de mercancías, etc. La de nición formal es la siguiente:

Una red de flujo es un digrafo G = (V;E) con una función de capacidad c : E ->R+ y dos vértices distinguidos, llamados fuente y sumidero.
La figura 1 muestra una red de ujo, con las capacidades para cada arco. Aquí y en lo sucesivo la fuente se denota con s y el sumidero con t.
Si no existe ningún arco de un vértice u a otro v se asumirá que c(u; v) = 0. De esta manera c queda de nida para cualquier par de vértices.
Las redes que se han de nido tienen una única fuente y un único sumidero. En la práctica pueden presentarse redes con más de una fuente y más de un sumidero; más adelante se verá cómo tratar esos casos.



Características:
  • son dirigidos 
  • tiene una capacidad asociada al arco, c(v,w)
  • se puede hacer pasar un flujo, por esos arcos,un valor necesariamente inferior a la capacidad.
  • tiene necesariamente un vértice-fuente y un vértice-pozo (grado saliente nulo)t.
 Sumideros: es el punto de llegada del flujo total de una red.

Fuentes: punto de partida del flujo total de una red.

 Aplicaciones:

 Redes de agua, de electricidad, cantidad de comida en un ecosistema; sistema de distribución con una fuente de producción, una meta de distribución y un punto intermedio.


 Tipos de flujo:
  • Flujo neto
  • Flujo estable
  • Flujo saliente
  • Flujo entrante
 Teorema de Flujo Máximo:

Teorema
Sea C:n0,n1,..., nk un camino de F=n0 a S=nk en una red R.
Sea f un flujo en R con valores f(i,j).Para las aristas orientadas en forma propia tenemos W(i,j)<f(i,j) y para las no orientadas en forma propia f(i,j)>0.
Definimos f(i,j) para las aristas que no están en el camino.f(i,j)+M si la arista está orientada en forma propia f(i,j)-M si la arista no está orientada en forma propia.
M=min {W(i,j)-f(i,j) si(i,j) esta orientada en forma propia y si f(i,j) no esta en forma propia}
Entonces f+ es un flujo que f precisa en el valor M.



Redes de Flujo de Costo Mínimo:


bi>0 si i es un nodo origen.
bi<0 si i es un nodo destino.
bi=0 si i es un nodo de transbordo.
Una condición necesaria para que el modelo tenga solución factible es que +(bi=0), es decir,que el flujo total generado en los nodos origen  sea igual al flujo total absorbido por los nodos destino.
Cuando esta condición no se cumple(problemas de transporte no balanceado en los que la oferta es diferente a la demanda) se generan nodos ficticios que generen o que absorban flujo. Los costos asociados a los arcos que parten o llegan a estos nodos es cero.
 Con frecuencia bi y uij son valores enteros. Las variables xij son variables enteras y no se requiere agregar esta  condición al modelo.(unimodularidad).
Con este modelo es posible plantear un problema de transporte, de transbordo, de flujo máximo y de camino mas corto.

 
 



Cadena de incremento de flujos:

supongamos que tenemos un camino de s a t un camino legal siguiendo las direcciones de las flechas, tal que en   cada arco del camino el flujo existente no ocupa toda la capacidad del arco que hay margen en cada arco para aumentar el flujo (s=v0!v1!v2!v5=t).
Sumamos  el mínimo de los margenes m al flujo de cada arco del camino el nuevo flujo f0 así construido es valido y tiene mayor valor ,val(f0)=val(f)+m>val(f).
el camino de s a t que hemos tomado sera por tanto un camino aumentador del flujo. pero puede ocurrir que no dispongamos de estos caminos y sin embargo el flujo pueda aumentarse. Con el nuevo flujo obtenido sobre la red no podemos encontrar otro camino aumentador,pues no podemos aumentar yendo desde s por v1, y tampoco con el camino s!v3!v4!.Existe otra posibilidad, que es considerar recorridos"sin tener en cuenta el sentido de las flechas (que serán caminos no legales, pero validos para nuestros propósitos): supongamos que tenemos un recorrido de s a t, sin tener en cuenta las direcciones de las flechas, tal que cada arco de ese camino siguiendo la dirección de las flechas (hacia delante) el flujo existente no ocupa toda la capacidad del arco,y que cada arco del camino en dirección contraria de la flecha(hacia atrás) el flujo existente es mayor que cero,entonces si sumamos el mínimo de los margenes m al flujo de cada arco hacia delante y se lo restamos por detrás, el nuevo flujo  f0 así construido es valido y tiene mayor valor,val(f0)=val(f)+m.


Algoritmo de  Ford Fulkerson:


  1. se etiqueta s con (0;1).(es decir, no proviene de ningun vértice y el margen es total).
  2. Si todos los vértices etiquetados han sido explorados,FIN (no hay recorrido aumentador)
  3. Si busca un vértice etiquetado vi que no haya sido explorado.
  4. Si todo vértice adyacente a vi esta etiquetado o no tiene holgura, se marca vi como explorador y se vuelve al paso 2.
  5. Para todo vértice adyacente vj no etiquetado, Si el arco es (vi;vj) hacia delante y fij<cij, se calcula mj=mnfmi cij i fijg (el margen mínimo acumulado)y se etiqueta vj con (j+mj) Si el arco es (vj;vi) hacia atras y fji>0, se calcula mj=mnfmi; fjig y se etiqueta vj con ji;mj)
  6. Si t no esta etiquetado, se vuelve al paso 2.
  7. Si t esta etiquetado, hemos construido un recorrido aumentador R. recorrer hacia atrás el recorrido R aumentado el flujo existente con mt.
  8. Eliminar todas las  etiquetas y volver al paso 1.

 
CONCLUSIONES:
 El ingeniero de sistemas es un profesional analista de cualquier tipo de sistemas en especial lo que a la tecnologia se refiere, la telecomunicacion se denomina gestion de trafico a diferentes funciones necesarias para planificar,diseñar ,proyectar y desarrollar  en coindiciones optimas de tal manera que es de suma importancia conocer el flujo de informacion en la s mismas.
de esat manera se establece la importancia que posee el conocer este tema de igual forma como opera en una empresa  para ella a continuacion mostrare un grafico.
El vídeo que a continuación se muestra presenta de una manera didáctica y llamativa como funciona el flujo de información en una red.