Algo pour choisir des effets pour avoir un minimum d'agios

**taupin** · 17/08/2007, 13h50

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** · 17/08/2007, 14h09

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** · 17/08/2007, 14h32

Envoyé par 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.

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.

Envoyé par FrancisSourd

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** · 17/08/2007, 15h21

Envoyé par taupin

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** · 17/08/2007, 15h23

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

**taupin** · 17/08/2007, 15h31

Envoyé par FrancisSourd

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** · 17/08/2007, 15h41

Envoyé par FrancisSourd

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** · 17/08/2007, 16h36

Envoyé par taupin

Euh, ou intervient le temps ?!

En raison des dates de paiements, j'avais peur qu'on soit obliger de calculer les agios en fonctions du temps mais si ce n'est pas le cas, c'est tant mieux!

**taupin** · 17/08/2007, 16h40

Envoyé par FrancisSourd

En raison des dates de paiements, j'avais peur qu'on soit obliger de calculer les agios en fonctions du temps mais si ce n'est pas le cas, c'est tant mieux!

Euh, si, les agios varient effectivement en fonction de la date de paiement ...

En plus, des équations au dessus, il faut aussi considérer le plafond d'escompte :
E0 : escompte en cours et Emax : escompte max
Il faut que :

Code :

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

E0 + sum_i,j m_i x[i,j] < Emax

**FrancisSourd** · 17/08/2007, 16h44

Envoyé par taupin

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...

**FrancisSourd** · 17/08/2007, 16h50

Envoyé par taupin

Euh, si, les agios varient effectivement en fonction de la date de paiement ...

D'accord, mais apparemment, ils se calculent bien et peuvent être considérés comme des constantes connues (a[i,j]) pour le problème d'optimisation.

J'avais peur qu'il fait déterminer aussi les moments où faire les versements.

**taupin** · 17/08/2007, 16h51

Envoyé par FrancisSourd

J'avais peur qu'il fait déterminer aussi les moments où faire les versements.

Non effectivement, le moment ou doivent etre effectué les versements sont fixes dans l'échéancier.

**taupin** · 17/08/2007, 16h54

Envoyé par FrancisSourd

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...

J'avais pensé a faire ca ... sauf qu'il faut savoir arreter la recherche de solution. Ca me parait tout a fait faisable sur le 1er paiement ... mais j'arrive pas a trouver comment intégrer le 2nd paiement avec cette méthode.

**FrancisSourd** · 17/08/2007, 18h10

On peut essayer d'échanger un effet initialement affecté au 1e paiement avec un autre affecté au second paiement.

**taupin** · 17/08/2007, 18h12

Je vais m'orienter vers l'utilisation de la librairie glpk et voir si ca me résoud deja ce que je veux.

Je verrais ensuite comment le rendre compatible avec le dev php que je veux faire.

**FrancisSourd** · 17/08/2007, 18h55

Pour tester glpk, c'est bien de passer par MathProg (livré avec) où il suffit d'entrer les équations dans un langage proche du formalisme mathématique.