Discussion :

[olibara]

Bonjour
J'ai un problème d'affectation un peu particulier
Je dispose d'une liste de N soldes débiteurs (15 montants) : total 1880
J'ai une autre liste de 29 payements : total 1880
Les 29 payements couvrent donc les soldes débiteurs

Mais j'aimerais trouver l'algorithme qui me permettrait dans ce type de situation d'affecter au mieux les payements afin de couvrir correctement les soldes
Ça pourrait ressembler a un Algorithme de Kuhn, mais je ne vois pas bien comment l'aborder dans le cas présent

Merci pour votre aide

[Flodelarab]

Bonjour

d'affecter au mieux les payements

Que signifie "au mieux" ?

[olibara]

Au mieux signifie qu’idéalement TOUS les payements devraient couvrir les Soldes
Mais si je ne répartis pas biens les affectation je vais avoir des payement non affecté

Exemple simple
3 Solde : 5, 10 et 25
4 Payements : 10, 10, 10, 5 et 5

Si j'affecte les deux payement de 5 pour couvrir le solde de 10 il deviendra impossible de couvrir correctement les soldes de 5 et 25

[anapurna]

salut

je pense qu'il veut lettré ses payement sur les solde existant
tes solde doivent être constitué de facture c'est sur eux que le lettrage doit se faire
le solde n'est que la résultante des facture moins les régularisation effectué (avoir,payement,OD,... )

Petite question est ce que la répartition des payements est exact ?

1°) cas ou la somme de certain payements corresponde a un solde unique
un exemple

Pour les payements
50
75
15
et Pour les soldes
75
65
le résultat seras donc
75 -> 75
50+15 -> 65
2°) cas ou les solde ne correspondent pas exactement a une somme de payement
Un exemple on as toujours
en payement
50
75
15
mais pour les soldes
80
60

donc l'affectation seras
80-(75+50) =-45
60-(45+15) = 0

Pour affecter tes payements au solde
le plus simple est de le trié du plus gros au plus petit et tu retire les éléments pouvant être le constituant du solde

@+ Phil

[olibara]

Merci Anapurna

Tu a bien exposé les cas possible et a priori je ne sais pas si on est dans le cas idéal ou ton cas N°2 (c'est pour cela que j'avais fait l’assertion "Au Mieux"
La solution de tri est évidement celle qui vient rapidement a l'esprit mais je ne suis pas convaincu qu'elle permet de résoudre "Au Mieux" le problème

Comme je le disait, cela ressemble a un problème d'affectation tel que décrit dans algorithme "Hongrois" méthode du Kuhn

Mais entre la ressemblance et la mise en oeuvre il y a une marge...
Donc j'appelle à l'aide :-)

[anapurna]

salut

la methode decrit seras sans null doutes selons le cas le au mieux
avec une petite variante pour le cas deux ou tu peut deja pour chaque somme
chercher la valeur maximal possible a déduire et la seconde passe peut compléter le reste

Je resume ma premier boucle installe le payement entier pour chaque solde
la deuxième fait le complément avec les restes .. il n'y a pas plus simple

cela ressemble au problème du sac a dos

[olibara]

Merci Anapurna
Oui ca ressemble au sac a dos
Et dans la pratique a un tetris


Mais je ne suis pas convaincu que ta méthode en deux passe puisse toujours trouver la meilleure solution
Il me semble que dans certains cas une affectation de première passe devrait plutôt être remplacée par une sommation d’éléments : Ce sont des cas d'affectation que devrait pouvoir (a mon avis) résoudre l’algorithme de Kuhn

Mais d'une part je ne maîtrise pas vraiment cet Algorithme et d'autre part je n'ai pas encore non plus bien conceptualisé comment je pourrais l'appliquer ici

Je vais quand même essayer ta solution simple en deux boucles ne fut-ce que pour avoir une idée du résultat

[tbc92]

Il faut poser le problème précisément. Ensuite, chaque étape aura (ou non) une solution.

On a N Soldes , Et P Paiements ; P est supérieur à N ; On sait que la somme des N soldes est égale à la somme des P paiements. Si ce n'est pas le cas, le programme s'arrête.
Chacun des N soldes peut (ou pas) s'écrire comme une somme de x paiements.
- On cherche une solution parfaite (chaque solde est décomposé en x paiements). Si on trouve cette solution parfaite, fin du traitement. Succès.
- Si on ne trouve pas... on fait quoi ? Faut-il essayer de dire voici la meilleure décomposition ....
Et dans ce cas, une piste pour dire qu'une solution est meilleure qu'une autre, c'est , pour chaque solution, compter le nombre K de Soldes qu'on a réussi à matcher avec x paiements, et la solution qu'on retient, c'est celle pour laquelle K est le plus élevé ?

Si on veut une solution parfaite uniquement, si on ne s'intéresse pas à la 2ème partie : rechercher la moins mauvaise solution, ça simplifie grandement les choses.

Dans les 2 cas, la démarche peut commencer comme ça :
-Etape 0 : Si j'ai la valeur V pour un Solde, et cette même valeur V pour un paiement, je les rattache, j'affecte ce paiement à ce solde. J'ai l'assurance que cette décision va mener à la meilleure solution.
-Etape 1 : Je classe les Soldes du plus petit au plus gros. Pour les soldes les plus petits, j'ai a priori peu de façons de les associer à des paiements. En commençant par les soldes les plus petits, on réduit beaucoup le nombre total de cas à tester.

[olibara]

merci tbc2
Tu a asser bien reformulé le problème ainsi que la solution proposée par Anapurna

Néanmoins e suis maintenant dans la situation 2 que tu décris
N=15
P=29

Or aucun N ne correspond directement a un P

L'algorithme de Kuhn résouds le problème d'affectation d'une matrice a deux dimensions

Mais dans mon cas, je ne sais pas si je peux dériver cet algorithme pour éviter la combinatoire de toues les sommes possibles de P
Ou si un autre algorithme le permet

[Wachter]

Bonjour,

Mais dans mon cas, je ne sais pas si je peux dériver cet algorithme pour éviter la combinatoire de toues les sommes possibles de P
Ou si un autre algorithme le permet

Une autre piste : tu pourras regarder du côté de la programmation linéaire en nombres entiers, notamment l'algorithme du simplexe qui pourrait être adapté à partir de la méthode hongroise.

[dourouc05]

Une autre piste : tu pourras regarder du côté de la programmation linéaire en nombres entiers, notamment l'algorithme du simplexe qui pourrait être adapté à partir de la méthode hongroise.

Sauf que le simplexe ne permet pas de travailler en nombre entiers (sauf cas très spécifique, du type matrice totalement unimodulaire). Sinon, il existe pas mal de solveurs préexistants pour de la programmation linéaire en nombres entiers (CPLEX, Gurobi côté commercial, CBC, GLPK côté libre, SCIP entre les deux).

[Wachter]

Sauf que le simplexe ne permet pas de travailler en nombre entiers (sauf cas très spécifique, du type matrice totalement unimodulaire). Sinon, il existe pas mal de solveurs préexistants pour de la programmation linéaire en nombres entiers (CPLEX, Gurobi côté commercial, CBC, GLPK côté libre, SCIP entre les deux).

Certes, l'algorithme du simplexe n'est pas dédié à la programmation en nombres entiers mais résout bien les problèmes d'affectation.

[Michel.Priori]

Je sais que le problème est ancien mais j'aimerai apporter un éclairage à la problématique.

Le sujet du post est "Affectation de nombres à des sommes" or tout de suite on parle de paiements

La notion de paiement embarque la notion de date (du moins en première intention).
Les listes de débits et de crédits doivent donc être considérées comme ordonnées par défaut ; Ce qui simplifie la résolution selon un principe d’intentionnalité (en payant 15 j'ai soldé 10 et le dernier reliquat de 5)
Il me semble aussi que la gestion des soldes débiteurs peuvent donner lieu à des intérêts.
Or pour le calcul de celui-ci il faut en permanence solder tout ou partie du débit le plus ancien.

Donc avant de chercher un algo abstrait valide bien qu'il entre dans le cas d'usage.