Otro de los grandes problemas de optimización se da en la búsqueda del flujo máximo en las redes de distribución. Definición 33.- Llamaremos red a un digrafo simple con dos vértices especiales, un minimal (la fuente) s y un maximal (el pozo) t, y que tiene asignada una capacidad no negativa cij a cada arco (vi, vj ) del digrafo. Un flujo f , es una asignación de un valor fij a cada arco (vi, vj ) del digrafo. Escribiremos f+(v) para denotar el flujo total saliente de un vértice v ; y f−(v) para denotar el flujo total entrante. Es decir f+(vi) = P k fik , la suma de los flujos de los arcos salientes de vi y f−(vi) = P k fki , la suma de los flujos de los arcos entrantes. El flujo debe cumplir dos condiciones (en ocasiones se distingue denominándolo flujo factible o válido):
• el flujo en cada arco debe ser no negativo y no exceder la capacidad del arco, 0 ≤ fij ≤ cij
• en cada vértice v 6= s y v 6= t, distinto de la fuente y el pozo, debe cumplirse que f−(v) = f+(v)
(“Conservación del flujo” o “Ley de Kirchhoff”)
Si bien el teorema del Flujo máximo y corte mínimo es el mas conocido y admirado, no es útil para la obtención de un flujo máximo (en una red de n nodos tendríamos que chequear 2 n−2 conjuntos de corte
y eso sólo para conocer el valor del flujo máximo). El algoritmo se basa en el Teorema 40 anterior, se van buscando recorridos aumentadores del flujo hasta que no sea posible encontrar más. Para la búsqueda del recorrido aumentador, se usan dos procesos que conviene explicar, el etiquetado de un vértice y la exploración de un vértice. Explorar un vértice es buscar los vértices conectados con él mediante un arco, saliente o entrante, y son estos vértices encontrados en la exploración los que son etiquetados; sólo se etiquetan si no lo estaban ya y si tienen margen para aumentar el flujo. En el etiquetado, debe indicarse el vértice desde el que ha sido etiquetado y el margen posible de aumento; también suele indicarse si el arco para llegar a él se recorre “hacia adelante” o “hacia atrás”. Inicialmente, se etiqueta solo s y se explora s, lo que produce el etiquetado de nuevos vértices. Para garantizar que la búsqueda avanza hacia t, se van explorando vértices ya etiquetados previamente –es decir para los que ya tenemos un recorrido aumentador– y no explorados, y se sigue así hasta llegar a t.
Leer más en:http://ma1.eii.us.es/Material/FTG_itis_Tema4.pdf
malisimo
ResponderBorrar