Optimización en redes y asignación de recursos

En una red dirigida finita, cada arco e tiene capacidad finita cₑ≥0 y una cantidad enviada fₑ con 0≤fₑ≤cₑ. En cada nodo intermedio, suma de entradas=suma de salidas: no produce ni consume cantidad. Las unidades deben ser compatibles, por ejemplo litros por minuto en todos los arcos.

El valor del flujo es la salida neta de la fuente s: sumamos lo que sale y restamos lo que entra. Por conservación coincide con la entrada neta al sumidero t. Sumar cantidades de todos los arcos contaría varias veces lo que atraviesa varios nodos. Un arco puede tener capacidad libre y otro estar saturado.

Una cantidad enviada por un camino utiliza cada arco del recorrido. Su aumento máximo es el menor espacio disponible entre esos arcos. Al usarlo actualizamos todos ellos. No elegimos el mayor tramo e ignoramos el que no soporta la misma cantidad.

Si dos rutas comparten un arco, comparten su capacidad. No se cuenta una vez para cada ruta. Rutas sin arcos compartidos pueden sumar sus aportaciones si no hay otro límite común del modelo; un límite de procesamiento en un nodo también tendría que representarse si existiera.

Para un arco original a→b de capacidad c y flujo f, la residual hacia delante permite c−f y la inversa b→a permite f. Usar la inversa reduce el flujo original; no añade un conducto físico nuevo. Si también existe un arco original b→a, son decisiones distintas y hay que conservar su identidad.

Un camino residual desde s hasta t ajusta todos sus arcos: aumenta los originales recorridos hacia delante y disminuye los recorridos al revés. Las correcciones conservan balances y elevan el valor neto. Buscar solo caminos físicos que no se hayan usado puede quedarse atascado antes del máximo.

Elegimos un conjunto S con s dentro y t fuera. Al sumar los balances de sus nodos, los arcos internos aparecen una vez entrando y otra saliendo y se cancelan. El valor es flujo saliente de S menos flujo entrante. La salida no supera su capacidad y las entradas se restan.

Así el valor es como máximo la suma de cₑ para arcos originales que salen de S. No sumamos los entrantes ni todos los que tocan un nodo de S. El corte es una cota para cualquier flujo factible, aunque ese flujo use otras rutas diferentes de las que dibujamos primero.

El teorema de flujo máximo y corte mínimo iguala el mayor flujo factible con la menor capacidad de corte en una red finita de capacidades no negativas. Para construir el certificado, cuando no queda camino residual a t tomamos S como los nodos alcanzables desde s.

Todo arco original que sale de S está saturado; todo original que entra tiene flujo cero, pues su inversa permitiría salir de S. Por tanto el valor coincide con la capacidad del corte.

Con capacidades enteras y flujo inicial cero, cada aumento residual conserva integridad y eleva el valor al menos uno. Como la capacidad total que sale de s es una cota finita, hay a lo sumo esa cantidad de aumentos exitosos. Es una garantía sencilla dependiente de magnitudes, no una cota polinómica en sus cifras binarias.

Para capacidades reales arbitrarias no se extiende ese argumento sin otra regla o análisis.

En flujo de coste mínimo, cada arco tiene coste unitario kₑ y se minimiza Σkₑfₑ sujeto a capacidades y balances de oferta o demanda. Sin una cantidad requerida, un modelo con todos los costes positivos podría preferir no transportar nada. Maximizar cantidad y minimizar coste son objetivos diferentes.

Las capacidades siguen comprobándose aunque cambie el objetivo. Una corrección residual inversa de un arco tiene coste −kₑ porque deshace una contribución anterior. No se interpreta como una oportunidad física ilimitada de ganar coste negativo: está limitada por el flujo que se pueda cancelar y por el resto de la corrección.

En el caso cuadrado, xᵢⱼ=1 significa que el agente i realiza la tarea j. Exigimos xᵢⱼ∈{0,1}, Σⱼxᵢⱼ=1 para cada agente y Σᵢxᵢⱼ=1 para cada tarea. El objetivo es minimizar Σcᵢⱼxᵢⱼ. Elegir el menor coste de cada fila puede repetir una columna.

Una cota inferior se construye con números rᵢ y sⱼ tales que rᵢ+sⱼ≤cᵢⱼ. En cualquier asignación, cada rᵢ y cada sⱼ se suma exactamente una vez, así el coste total es al menos Σrᵢ+Σsⱼ. Una asignación que alcance esa cota queda certificada.

En redes de capacidades enteras, el algoritmo de aumentos desde cero construye un flujo máximo entero. Para asignación, una matriz no negativa con filas y columnas de suma uno es combinación convexa de matrices de permutación. Una justificación usa Hall sobre sus entradas positivas: cualquier conjunto de filas suma su tamaño y necesita al menos ese número de columnas vecinas.

Existe una asignación con entradas positivas; tomamos el mínimo ε de ellas.

Si ε<1, restamos ε veces su matriz y dividimos el resto por 1−ε: las sumas vuelven a uno y desaparece al menos una entrada positiva. Repetir termina porque el soporte se reduce, y da la combinación de asignaciones.

Un objetivo lineal sobre esa combinación no puede ser menor que el menor coste de sus asignaciones, así existe un óptimo entero. Esto no convierte todos los puntos factibles u óptimos en enteros. La comprobación final revisa además límites, balances, exclusividad y valor, con un corte o una cota apropiada al objetivo.