Problema de flujo de múltiples productos básicos

El problema del flujo de múltiples productos básicos es un problema de flujo de red con múltiples productos (demandas de flujo) entre diferentes nodos fuente y sumidero.

Dada una red de flujo , donde el borde tiene capacidad . Hay productos básicos , definidos por , dónde y es la fuente y el sumidero de los productos básicos , y es su demanda. La variable define la fracción de flujo a lo largo del borde , en caso de que el flujo se pueda dividir entre múltiples rutas, y de lo contrario (es decir, "ruta de ruta única"). Encuentre una asignación de todas las variables de flujo que satisfaga las siguientes cuatro restricciones: ${\ Displaystyle \, G (V, E)}$ ${\ Displaystyle (u, v) \ in E}$ ${\ Displaystyle \, c (u, v)}$ ${\ Displaystyle \, k}$ ${\ Displaystyle K_ {1}, K_ {2}, \ dots, K_ {k}}$ ${\ Displaystyle \, K_ {i} = (s_ {i}, t_ {i}, d_ {i})}$ ${\ Displaystyle \, s_ {i}}$ ${\ Displaystyle \, t_ {i}}$ ${\ Displaystyle \, i}$ ${\ Displaystyle \, d_ {i}}$ ${\ Displaystyle \, f_ {i} (u, v)}$ ${\ Displaystyle \, i}$ ${\ Displaystyle \, (u, v)}$ ${\ Displaystyle \, f_ {i} (u, v) \ en [0,1]}$ ${\ Displaystyle \, f_ {i} (u, v) \ in \ {0,1 \}}$

(2) Conservación del flujo en los nodos de tránsito: la cantidad de flujo que ingresa a un nodo intermedio es la misma que sale del nodo. ${\ Displaystyle u}$

El equilibrio de carga es el intento de enrutar los flujos de manera que la utilización de todos los enlaces sea uniforme, donde ${\ Displaystyle U (u, v)}$ ${\ Displaystyle (u, v) \ in E}$