Flujo de productos múltiples

Acabo de trabajar en capítulos de preguntas del libro de texto DPV para la preparación de mi examen. Para uno de ellos, estoy teniendo algunos problemas pero he hecho algunos progresos:

Mi solución:

Usaré programación lineal para maximizar x donde SUM {flow_i(s_i, v) para todos los i donde v son nodos que se conectan a la fuente s_i} >= x * d_i

sujeto a las restricciones

• para cada arista e, f1+..fk <= c_e


• para cada arista e, flow_e >= 0


• y algunas limitaciones más de las que no estoy seguro

Creo que estoy en el camino correcto, pero necesito ayuda para avanzar un poco más. ¿Debería considerar intentar usar un supernodo para reducir esto a un problema de flujo máximo regular?

¡Cualquier ayuda sería genial! Gracias.

Solución del problema

Sí, un enfoque típico para los problemas de flujo de mercancías de múltiples fuentes y múltiples sumideros es introducir una súper fuente y un súper sumidero. A continuación, conecte todas las fuentes s1...sk a la superfuente. Conecte cada sumidero t1,...tk al súper sumidero.

Importante: Dé una capacidad muy grande a todos los bordes que salen o entran de cualquiera de los supernodos.

Objetivo: maximizar el rendimiento total. (Suma de flujos sobre todos los bordes que salen de las fuentes 1..k)

Restricciones:

Restricciones de capacidad perimetral:

Ya lo entendiste bien.

• para cada arista e, f1+..fk <= c_e

*Conservación de caudal (Flow-in == Flow_out):*

• para cada vértice v, suma del flujo hacia v = suma del flujo que sale de v

Satisfacción de la demanda:

• para cada sumidero t_i, suma del flujo en t_i (todos los bordes terminan en t_i) >= demand_i

Flujos distintos de cero, que ya tienes.

Aquí hay un folleto de conferencia accesible que hace referencia a su problema específico. Específicamente, eche un vistazo al Ejemplo 2 en el folleto.