Discussion :

[taupin]

Salut

Voila, je suis en train de developper une application qui a partir d'un échéancier ou sont indiqués les futurs paiements a effectuer et d'un portefeuille d'effets, a connaitre les effets a mettre a l'escompte afin d'avoir le minimum d'agios et en respectant le plafond d'escompte.

J'ai fait quelques recherches et pour l'instant, je prends la 1ere date, je fais toutes les combinaisons possible des effets qui permettent de payer cette 1ere échéance et je prends la combinaison ayant les agios les moins élevés.

Et ainsi de suite pour les dates suivantes.

Le probleme que j'ai constaté c'est que lorsque 2 paiements sont proches (2/3 jours), cette facon de faire n'est plus bonne ... car on aurait pu choisir un effet d'un montant suppérieur pour le 1er paiement ce qui fait qu'au 2nd, l'effet a choisir serait différent.

Je cherche donc s'il n'y aurait pas un algorithme permettant de palier ce probleme.

J'ai bien pensé aussi au lieu de prendre en compte que la 1ere date, de faire toutes les combinaisons possibles sur toutes les dates, mais je me dis qu'il doit bien avoir une autre solution ... donc si vous avez des idées, je suis preneur.

Merci

[FrancisSourd]

J'ai l'impression que cela ressemble a un problème de sac à dos puisque pour chaque "effet", on a l'option de prendre ou de ne pas prendre.

Je n'y connais pas grand chose en finance mais j'ai l'impression que ce que tu dis ne se traduit pas par des équations linéaires. Existe-t-il des équations pour traduire tout cela, contraintes et fonction à minimiser (agios).

Je dirais qu'il faut introduire pour chaque effet "i" une variable x[i] qui vaut 1 si l'effet est mis à l'escompte et 0 sinon. Il faut donc tout exprimer en fonction de ces x[i] à déterminer (à moins qu'il y ait d'autres choses à déterminer que je n'ai pas saisies).

[taupin]

J'ai l'impression que cela ressemble a un problème de sac à dos puisque pour chaque "effet", on a l'option de prendre ou de ne pas prendre.

Ca y ressemble en partie ... Je vais analyser le lien plus en détail.
Par rapport au probleme du sac a dos, je dirais que le poids du sac serait le montant du 1er paiement ... et les effets avec leurs agios, les poids avec leur valeur.
Sauf qu'au lieu d'avoir le minimum pour pas dépasser le poids max du sac, il faudrait le minimum pour dépasser le poids du sac.

Mais le probleme, c'est aussi le 2eme paiement ...
Ce qui fait qu'il y aurait un 2eme sac avec une valeur des poids différents ... et le remplissage du 1er sac impacte celui du 2nd.

Je n'y connais pas grand chose en finance mais j'ai l'impression que ce que tu dis ne se traduit pas par des équations linéaires. Existe-t-il des équations pour traduire tout cela, contraintes et fonction à minimiser (agios).

Je suis en train d'essayer de voir s'il y a moyen de mettre tout ca en équation.

En tout cas, merci pour le lien, qui me fait avancer un peu plus sur mon alogorithme.

[FrancisSourd]

Sauf qu'au lieu d'avoir le minimum pour pas dépasser le poids max du sac, il faudrait le minimum pour dépasser le poids du sac.

On appelle cela des contraintes de couvertures.

En reprenant les x[î] de mon précédent message cela donne des équations du style (b_i est le montant de l'effet)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

\sum_i b_i x[i] ≥ B

Puisqu'il semble qu'il faille distinguer les paiements, on peut dire que tout paiement j doit être couvert

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

\sum_i b_i x[i,j] ≥ B[j]  (pour tout j)

Pour dire qu'un effet est utilisé au plus une seule fois

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

\sum_j x[i,j] ≤ 1 (pour tout i)]

Si cela reste linéaire comme cela, le bon réflexe est de s'orienter vers la programmation linéaire en nombres entiers

[FrancisSourd]

Ce que je n'ai pas bien compris, c'est le rôle du temps dans le modèle.

[taupin]

Ce que je n'ai pas bien compris, c'est le rôle du temps dans le modèle.

Euh, ou intervient le temps ?!

[taupin]

On appelle cela des contraintes de couvertures.

En reprenant les x[î] de mon précédent message cela donne des équations du style (b_i est le montant de l'effet)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

\sum_i b_i x[i] ≥ B

Puisqu'il semble qu'il faille distinguer les paiements, on peut dire que tout paiement j doit être couvert

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

\sum_i b_i x[i,j] ≥ B[j]  (pour tout j)

Pour dire qu'un effet est utilisé au plus une seule fois

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

\sum_j x[i,j] ≤ 1 (pour tout i)]

Si cela reste linéaire comme cela, le bon réflexe est de s'orienter vers la programmation linéaire en nombres entiers

Effectivement il y a tes 2 équations et on cherche a minimiser la somme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

\sum_i sum_j a[i,j] x[i,j] (pour tout i et j)

avec a[i,j] le montant des agios des traites i lors du paiement j

[FrancisSourd]

Effectivement il y a tes 2 équations et on cherche a minimiser la somme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

\sum_i sum_j a[i,j] x[i,j] (pour tout i et j)

avec a[i,j] le montant des agios des traites i lors du paiement j

Si j'ai bien compris, les x[i,j] ne doivent valoir que 0 et 1. Dans ce cas, le mieux est certainement de résoudre le problème par un solveur de programmation linéaire en nombre entier (par exemple glpk). On peut tout de même facilement obtenir de bonnes solutions par des méthodes de recherche locale ou des méta-heuristiques. En gros, on part d'une solution pas trop mauvaise et on essaie de la modifier: si ca améliore, on garde, sinon on essaie autre chose...