égalisation des flux rentrants et sortants sur des noeuds d'

[coinroad]

Bonjour,

J'ai une question intéressante à vous poser qui est la suivante :

Imaginons un graphe de transaction dans lequel les noeuds sont les agents et les arcs sont les transactions.

On met une contrainte dans ce graphe de transaction qui oblige chaque agent à égaliser ses flux rentrants et sortants de valeurs avec tous les autres agents au terme d'une période (ex : un an) afin que les soldes des balances des paiements de tous les noeuds soient nuls à la fin de la période et permette de clôturer le graphe.

Cette contrainte revient à poser une loi de conservation de flux dans laquelle on stipule que la somme des flux entrants et sortants de chaque agent doit toujours être égale à zéro à la fin de la période.
∑Fijk = 0

Soit un groupe de trois agents économiques i, j, k.
Soit des soldes de flux rentrants et sortants : i=x, j=y, k=z.
Alors, la loi de conservation des flux stipule que :
Fix + Fjy + Fkz = 0

Cela revient donc à poser le principe que si les agents i, j, k ont des balances de paiement créditrices ou débitrices, ils doivent trouver une solution transitive qui va augmenter ou diminuer certains flux entrants ou sortants entre les agents pour égaliser leurs balances de paiement et annuler tous les soldes.

La question est la suivante :

1. L'algorithme qui permettrait de trouver la solution de rééquilibrage la plus économique des flux rentrants et sortants de tous les noeuds relève-t-il selon vous d'un problème NP-Hard ? Et si oui peut-on le rattacher à une catégorie de problème NP-Hard existant ? Et dans un tel cas lequel en particulier ?
2. Auriez-vous un algorithme à me proposer pour calculer le nombre minimum de flux de valeur à rajouter à une situation de flux rentrants et sortants déséquilibrée pour parvenir à annuler tous les soldes ? Voire pour classer les principales solutions d'égalisation des flux par ordre d'économie décroissante.

L'objectif de ce travail est de proposer des modèles d'échanges stables et équilibrés basés sur la solidarité des agents et maximisant les capacités d'échange de tous en ne permettant pas que certains agents soient créditeurs (ou excédentaires) au détriment d'autres agents qui seraient débiteurs (ou déficitaires).

Cas pratique :
Supposons qu'il y ait trois agents économiques A, B et C.
Agent A :
Flux entrant : 10
Flux sortant : 15
Agent B :
Flux entrant : 15
Flux sortant : 10
Agent C :
Flux entrant : 5
Flux sortant : 5
Pour égaliser les flux rentrants et sortants des trois agents, nous devons appliquer la relation de transitivité mathématique.
Pour l'agent A :
Flux entrant (A → B) = 15
Flux sortant (B → A) = 10
Donc, pour égaliser les flux rentrants et sortants de l'agent A, nous devons augmenter le flux sortant de l'agent B vers l'agent A de 5.
Pour l'agent B :
Flux entrant (B → A) = 10
Flux sortant (A → B) = 15
Donc, pour égaliser les flux rentrants et sortants de l'agent B, nous devons augmenter le flux entrant de l'agent A vers l'agent B de 5.
Pour l'agent C :
Flux entrant (C → C) = 5
Flux sortant (C → C) = 5
Donc, pour égaliser les flux rentrants et sortants de l'agent C, aucune modification n'est nécessaire.
Après avoir appliqué la relation de transitivité mathématique, les flux rentrants et sortants des trois agents sont égalisés :
Agent A :
Flux entrant : 15
Flux sortant : 15
Agent B :
Flux entrant : 15
Flux sortant : 15
Agent C :
Flux entrant : 5
Flux sortant : 5

Je vous remercie pour vos lumières.

[coinroad]

Alors la communauté des génies, 99 vues et pas une seule réponse ? Ce forum n'est plus aussi vif qu'avant ! Mais où sont donc passés Lyceen69 et FatalError ? Lol

[coinroad]

Comme personne sur ce forum ne m'a répondu j'ai posé la question à Chat-GPT4. Et voici sa réponse :

Peut-on utiliser la relation de transitivité mathématique pour égaliser les flux rentrants et sortants différents de tous les agents économiques d'un groupe d'échange ?

Rédige un code en javascript complet permettant d'égaliser les flux rentrants et sortants de tous les noeuds en faisant le plus petit nombre de transactions possibles. Le code devra permettre de calculer et de classer les dix meilleures solutions d'égalisation des flux rentrants et sortants.

La relation de transitivité mathématique ne peut pas être directement utilisée pour égaliser les flux rentrants et sortants différents de tous les agents économiques d'un groupe d'échange.
Cependant, il existe des algorithmes qui peuvent résoudre ce problème, comme l'algorithme de Tarjan ou l'algorithme de Ford-Fulkerson.
Voici un exemple de code en JavaScript utilisant l'algorithme de Ford-Fulkerson pour égaliser les flux rentrants et sortants de tous les noeuds d'un graphe. Ce code suppose que les données d'entrée sont fournies sous forme d'un tableau d'objets, chaque objet représentant un noeud du graphe avec les attributs suivants :
https://fr.wikipedia.org/wiki/Algorithme_de_Tarjan


id : l'identifiant du noeud
inputs : un tableau contenant les identifiants des noeuds qui envoient des flux vers ce noeud
outputs : un tableau contenant les identifiants des noeuds vers lesquels ce noeud envoie des flux
inputFlow : la quantité de flux entrant dans ce noeud
outputFlow : la quantité de flux sortant de ce noeud
Le code utilise la bibliothèque fastpriorityqueue pour trier les solutions par ordre décroissant de nombre de transactions nécessaires.


const PriorityQueue = require('fastpriorityqueue');

function equalizeFlows(nodes) {
const graph = {};
const capacities = {};
const flow = {};

// Build the graph and capacities
for (const node of nodes) {
graph[node.id] = [];
capacities[node.id] = 0;
flow[node.id] = node.outputFlow - node.inputFlow;
for (const input of node.inputs) {
graph[input] = graph[input] || [];
graph[input].push(node.id);
capacities[`${input}->${node.id}`] = Infinity;
}
for (const output of node.outputs) {
graph[node.id].push(output);
capacities[`${node.id}->${output}`] = Infinity;
}
}

// Calculate the maximum flow using Ford-Fulkerson algorithm
while (true) {
const parent = {};
const visited = new Set();
const queue = [Object.keys(graph)[0]];
let bottleneck = Infinity;

// Find a path from source to sink
while (queue.length > 0) {
const current = queue.shift();
visited.add(current);
if (current === Object.keys(graph)[1]) {
break;
}
for (const neighbor of graph[current]) {
if (!visited.has(neighbor) && capacities[`${current}->${neighbor}`] > 0) {
parent[neighbor] = current;
queue.push(neighbor);
bottleneck = Math.min(bottleneck, capacities[`${current}->${neighbor}`]);
}
}
}

if (Object.keys(parent).length === 0) {
break; // No more augmenting paths found
}

// Update the flow and capacities along the path
let current = Object.keys(graph)[1];
while (current !== Object.keys(graph)[0]) {
const prev = parent[current];
flow[prev] -= bottleneck;
flow[current] += bottleneck;
capacities[`${prev}->${current}`] -= bottleneck;
capacities[`${current}->${prev}`] += bottleneck;
current = prev;
}
}

// Generate a list of solutions
const solutions = new PriorityQueue((a, b) => b.numTransactions - a.num