Flujo de costo mínimo

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 22 de enero de 2017; las comprobaciones requieren 6 ediciones .

El problema del flujo de costo mínimo consiste en encontrar la forma más económica de transferir un flujo de cierta cantidad a través de una red de transporte .

Definiciones

Dada una red de transporte con fuente y sumidero , donde los bordes tienen capacidad , flujo y precio . El costo de reenvío de flujo para el borde es igual a . Es necesario encontrar un flujo con un valor de unidades. $G(V,E)$ $s \ en V$ $t\en V$ ${\ estilo de visualización e \ en E}$ ${\ estilo de visualización c (e)}$ ${\ estilo de visualización f (e)}$ ${\ estilo de visualización a (e)}$ $mi$ $f(e)\cdot a(e)$ $d$

La esencia del problema es encontrar un flujo f ( u , v ) que minimice su costo total :

\sum _{{u,v\in V}}a(u,v)\cdot f(u,v)

Se aplican las siguientes condiciones:

Límite de ancho de banda :	$0\leqslant f(u,v)\leqslant c(u,v)$ . La transmisión no puede exceder el ancho de banda.
Antisimetría :	$\f(u,v)=-f(v,u)$ . El flujo de a debe ser opuesto al flujo de a . $tu$ $v$ $v$ $tu$
Ahorro de flujo :	$\ \sum _{{w\in V}}f(u,w)=0$ .
Flujo requerido :	$\sum _{w\in V}f(s,w)=d$

Relación con otras tareas

Otra variante de este problema es encontrar el flujo máximo que tiene el precio mínimo entre los máximos.

Un problema más general es la circulación del flujo de costo mínimo , que se puede utilizar para resolver este problema. Establecemos el límite inferior para todos los bordes igual a cero y dibujamos un borde adicional desde el sumidero hasta la fuente con una capacidad y un límite inferior . $t$ $s$ $c(t,s)=d$ $l(t,s)=d$

Es de destacar que para , el problema de encontrar el flujo de costo mínimo corresponde al problema de encontrar el camino más corto . En el caso de que el costo sea para todos los bordes del gráfico, el problema se puede resolver mediante algoritmos adaptados para encontrar el flujo máximo: ${\ estilo de visualización d = 1}$ ${\ estilo de visualización a (e) = 0}$

Tan pronto como la primera vez, detenga el algoritmo. ${\ estilo de visualización | f | \ geqslant d}$
Sea el valor del último complemento de la corriente. $pags$
Reemplace el último flujo con un flujo con valor . ${\ estilo de visualización pag-(|f|-d)}$

También hay una solución alternativa al problema con costo de borde cero:

Cree un nuevo vértice fuente . $s'$
Agregue un borde con capacidad . $e'=(s',s)$ ${\ estilo de visualización c (e') = d}$
De esta forma se limitará el caudal máximo . $d$

Decisiones

El problema de flujo de costo mínimo se puede resolver usando programación lineal .
Encuentre cualquier flujo de un valor dado, luego elimine todos los ciclos de costos negativos en el gráfico residual. Para deshacerse del ciclo, debe dejar que fluya lo máximo posible a través de él. Los ciclos se buscan mediante el algoritmo de Bellman-Ford . Para probar el funcionamiento del algoritmo, mostramos que el flujo del grafo no es un flujo de costo mínimo siempre que la red residual del grafo contenga un ciclo negativo . Sea un flujo gráfico tal que y, por lo tanto, ambos flujos son diferentes entre sí. Para todos los bordes , denotamos y obtenemos : un flujo cíclico. Como está formado por un máximo de ciclos , es cierto lo siguiente: , lo que significa que existe tal que . Para optimizar el algoritmo, puede elegir cada ciclo de iteración con el costo promedio mínimo . Para probar el tiempo de ejecución del algoritmo, dividimos el curso de su ejecución en fases, cada una de las cuales consistirá en iteraciones separadas. Sea el flujo al comienzo de la -ésima fase. La fase se considera completada cuando se encuentra un flujo tal que o , donde . En , el algoritmo termina. Además, sea - el valor al comienzo de la primera fase y - el valor al comienzo de la -ésima fase ( ). Así de hecho: , y también . Por la propiedad de integralidad se sigue que y . Las iteraciones se pueden dividir condicionalmente en varios tipos: Tipo 1: el ciclo contiene solo aristas con un costo negativo y Tipo 2: el ciclo contiene al menos una arista con un costo positivo. En cada iteración del primer tipo, al menos un borde se "saturará" y eliminará. En este caso, todos los bordes formados tendrán un costo positivo (ya que tienen la dirección opuesta en la red residual). Por lo tanto, el algoritmo terminará después de al menos iteraciones consecutivas del primer tipo. Si la fase contiene más de iteraciones, después del máximo de iteraciones, se realizará una iteración del segundo tipo. Demostremos, sin embargo, que esto es imposible: Sea un flujo de la primera iteración del segundo tipo. Tenga en cuenta que, de hecho , es decir, no hay nuevos bordes con costo negativo. Sea un ciclo en con mínimo y sean aristas con costo negativo en : . De sigue . Por lo tanto Una contradicción: ya hemos llegado al final de la fase, lo que significa que no hay iteraciones del segundo tipo, y cada fase termina después de las iteraciones del primer tipo. El ciclo con el peso promedio mínimo se puede encontrar en . Prueba: Sea el costo de la ruta más rentable para atravesar exactamente los bordes, entonces, de hecho, y . Resulta que todos los valores se pueden calcular mediante programación dinámica . Lema: El valor del ciclo con el mínimo coste medio es . Sea el ciclo con el costo promedio mínimo. Si aumenta el costo de todos los bordes en , entonces sigue siendo un ciclo con el costo promedio mínimo, pero el valor del ciclo aumenta en . por lo tanto, es posible aumentar todos los costos de borde para que . Demostremos que : Elija cualquier vértice y camino que termine en y tenga un costo . debe contener un bucle . Sea un camino que no contiene un ciclo y tiene longitud . Luego hay aristas en el ciclo. Porque de es verdadero y para cada vértice existe tal que . Demostremos que : Para hacer esto, demostramos que hay un vértice para el cual es cierto para todo . Sea el vértice del ciclo con el costo promedio mínimo , sea el camino más corto que termina y no contiene un ciclo. Sea el número de vértices en . También introducimos un vértice que se encuentra a la distancia de los vértices de . Llamemos a la ruta desde hasta . Sea un camino desde hasta , y sea un camino de longitud mínima desde la fuente del gráfico hasta . Entonces es cierto lo siguiente: , y también de ellos se sigue que . El camino tiene un costo de 0, porque . Así para todos . Teniendo en cuenta el lema, obtenemos . El tiempo de ejecución de dichos algoritmos será , ya que durante la ejecución del algoritmo pasarán fases, en cada una de las cuales hay iteraciones que requieren tiempo. Con base en la anterior estimación de tiempo, se puede realizar lo siguiente: . $F$ $GRAMO$ $G_f$ $C$ ${\ estilo de visualización f ^ {*}}$ $GRAMO$ $l(f^{*})<l(f)$ ${\ estilo de visualización e \ en E}$ $f'(e)=f^{*}(e)-f(e)$ $F'$ $F'$ ${\ estilo de visualización m'<m}$ ${\ Displaystyle f'_ {i}}$ $(1\leqslant i\leqslant m')$ $l(f')=l(f^{*})-l(f)=\sum _{1\leqslant i\leqslant m'}l(f'_{i})$ $j$ ${\ estilo de visualización l (f'_ {j}) <0}$ ${\overline {l}}(C)={\frac {l(C)}{|C|}}={\frac {\sum_e\in C}l(e)}{| C|}}$ $F$ $i$ $i$ $gramo$ ${\ estilo de visualización \ mu (g) \ leqslant (1-1/n) \ cdot \ mu (f)}$ ${\ estilo de visualización \ mu (g) \ leqslant 0}$ $\mu (f)=-{\overline {l))(C)$ ${\ estilo de visualización \ mu (g) \ leqslant 0}$ $\mu_{0}$ $\mu$ $\mu _{i}$ $\mu$ $i$ $1\leqslant i\leqslant T$ $\mu _{i}\leqslant (1-1/n)\cdot \mu _{i-1}\leqslant {\frac {\mu _{i-1}}{e^{1/n }}}$ $\mu _{0}\leqslant L=\sum _{e\in E}|l(e)|$ ${\ estilo de visualización \ mu _ {T-1} \ geqslant 1/n}$ $T-1\leqslant \log _{e^{1/n}}(nL)={\frac {\ln(nL)}{\ln(e^{1/n}})))= n \ln(nL)$ $T\leqslant n\ln(nL)+1$ $C$ $C$ $metro$ $metro$ $m-1$ $gramo$ $\forall e\in E(G_{g}):l(e)\geqslant -\mu (f)$ $C$ ${\ Displaystyle G_ {g}}$ ${\overline{l}}(C)$ $H$ $C$ $\mu (g)=\sum _{e\in C}{\frac {-l(e)}{|C|}}\leqslant \sum _{e\in H}{\frac {- l(e)}{|C|}}\leqslant |H|\cdot {\frac {\mu (f)}{|C|}}$ $|H|\leqslant |C|-1$ $|H|/|C|\leqslant 1-1/|C|\leqslant 1-1/n$ ${\ estilo de visualización \ mu (g) \ leqslant (1-1/n) \ cdot \ mu (f)}$ $m-1$ ${\ estilo de visualización O (| V || E |)}$ $d_{k}(v)$ $v\en V$ $k$ $d_{0}(v)=0$ $d_{k+1}(v)=\min _{e=(w,v)\in E_{f))(d_{k}(w)+l(e))$ $d_{k}(v)$ $En M)$ ${\overline{l}}(C)$ $\alpha =\min _{v\in V}\max _{j=0}^{n-1}({\frac {d_{n}(v)-d_{j}(v)} {Nueva Jersey)))$ $C$ $\delta$ $C$ $\delta$ ${\overline{l}}(C)=0$ $\alpha \geqslant 0$ $v$ $PAGS$ $v$ ${\ estilo de visualización d_ {n} (v)}$ $PAGS$ $C$ $PAGS'$ $PAGS$ $C$ $j$ ${\ estilo de visualización nj}$ ${\ estilo de visualización l (C) \ geqslant 0}$ $d_{n}(v)=l(P)=l(C)+l(P')\geqslant l(P')\geqslant d_{j}(v)$ $v$ ${\ estilo de visualización j \ en \ {1,..., n-1\))$ $d_{n}(v)\geqslant d_{j}(v)$ ${\ estilo de visualización \ alfa \ leqslant 0}$ $w$ $d_{n}(w)\leqslant d_{j}(w)$ ${\ estilo de visualización j \ en \ {1,..., n-1\))$ $v$ $C$ $PAGS$ $v$ ${\ estilo de visualización p<n}$ $PAGS$ $w$ $C$ ${\ estilo de visualización np}$ $v$ $v$ $w$ $q$ $R$ $w$ $v$ $S$ $j$ $w$ $d_{n}(w)\leqslant l(P)+l(Q)=d_{p}(v)+l(Q)$ $d_{p}(v)\leqslant d_{j+r}(v)\leqslant d_{j}(w)+l(R)$ $d_{n}(w)\leqslant d_{j}(w)+l(R)+l(Q)$ $Q\odot R$ ${\ estilo de visualización l (C) = 0}$ $d_{n}(w)\leqslant d_{j}(w)$ ${\ estilo de visualización j \ en \ {1,..., n-1\))$ ${\ estilo de visualización \ alfa \ leqslant 0}$ $O(m^{2}\cdot n^{2}\cdot \log(nL))$ $n\log(nL)+1$ $metro$ $En M)$ $O(m^{3}\cdot n^{2}\cdot \log(n))$
Utilice una modificación del algoritmo de Ford-Fulkerson , en el que se elige una ruta incremental del precio mínimo en cada paso. Para seleccionar la ruta, puede usar el algoritmo Bellman-Ford.
Mejora del algoritmo anterior: utilizando potenciales, se puede reducir el problema a un problema sin aristas negativas, tras lo cual, en lugar del algoritmo de Bellman-Ford, se utiliza el algoritmo de Dijkstra . El algoritmo Bellman-Ford deberá aplicarse solo en el primer paso.

Enlaces

Visualizador del algoritmo para encontrar el flujo máximo de costo mínimo

Véase también

Problema de flujo máximo

Literatura

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmos: construcción y análisis = Introducción a los Algoritmos / Ed. I. V. Krasikova. - 2ª ed. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .