Cómo desenredar matemáticamente múltiples compañías que están enredadas en préstamos

Answer 1

Asumiendo que está preguntando lo que creo que es: si está dispuesto a que las empresas se endeuden, el orden no importa [a menos que tenga algún requisito para ser “óptimo”].

De lo contrario, puede que ni siquiera haya una solución. Tome tres compañías que se deben un dólar (en un círculo), pero ninguna de ellas tiene dinero. Por lo tanto, debe asegurarse, como mínimo, de que no haya circuitos cerrados sin dinero.

Si todos tienen dinero, simplemente identifique los bucles de ese tipo (usando la teoría de grafos) y haga circular el dinero alrededor de todos esos bucles hasta que el bucle “se rompa” (así que fluya solo la cantidad de la deuda más pequeña en ese bucle). Una vez que no le quedan bucles, tiene un “árbol” de dinero que puede pagar directamente, lo mejor que pueda. [La única suposición aquí es que nadie se queda completamente sin dinero en ninguna etapa en el medio, tampoco.]

[Por supuesto, si desea la menor cantidad de transacciones posible, entonces ese es un problema más difícil, y no tengo una respuesta para eso].

Answer 2

A2A, gracias.

Si entiendo correctamente que el problema se centra en un conjunto de participantes (empresas), y para cada par de empresas ordenadas (C1, C2), podemos decir que la cantidad neta que C1 debe a C2. Por lo tanto, estamos buscando un modelo matemático de flujos (en este caso, transferencias de dinero) entre pares de participantes. Tal modelo es una red Flow – Wikipedia.

Utiliza el concepto de un gráfico, que se presenta en un nivel muy introductorio en mi blog: Gráficos y árboles.

Espero que esto sea lo que estabas buscando.