Discussion :

[Fluxe]

Bonjour à tous,

Je suis confronté à un problème d'optimisation et je ne vois pas du tout comment partir dans mon algorithme pour le résoudre.
En plus je pense que c'est quelque chose d'assez classique et pas compliqué, mais je n'ai rien trouvé de satisfaisant sur le net.

Mon problème est le suivant:
J'ai 5 variables (A B C D E pour simplifier) qui ont chacune un poids (Aw Bw Cw Dw Ew)
Chaque poids peut varier de 0 à 100% avec comme contrainte que la somme de tous les poids fassent 100%

Je voudrais stocker dans une matrice tous les résultats des combinaisons de tous les poids possibles avec un pas de X% (par exemple avec un pas de 5%)

Il faudrait donc que je teste toutes les situations:
100 - 0 - 0 - 0 - 0
95 - 5 - 0 - 0 - 0
95 - 0 - 5 - 0 - 0
.....
20 - 20 -20 -20 -20
.....
0 - 0 - 0 - 0 - 100


Ca fait pas mal de combinaisons mais vu que je travaille en petite dimension ca devrait tourner dans des temps raisonnables.

Là où j'ai besoin de votre aide c'est pour me guider sur la façon d'organiser les boucles afin d'être sûr de ne pas rater une combinaison


D'avance merci

[Alexis.M]

Il faudrait voir quel est exactement la fonction que tu veux optimiser, notamment si elle est convexe, vu tes contraintes, il y a des algorithmes plus efficaces que la force brute pour trouver la solution.

Sinon il suffit de boucler sur toutes tes variables :

Code :

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

1
2
3
4
5
6
7
8
9
10
for (i1=0;i1<=20;i1++){
  a = 20*i1;
  for (i2=0;i2<=20;i2++){
    b = 20*i2;
    for (i3=0;i3<=20;i3++){
      c = 20*i3;
     .....
   }
  }
}

[Fluxe]

Il faudrait voir quel est exactement la fonction que tu veux optimiser, notamment si elle est convexe, vu tes contraintes, il y a des algorithmes plus efficaces que la force brute pour trouver la solution.

Sinon il suffit de boucler sur toutes tes variables :

Code :

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

1
2
3
4
5
6
7
8
9
10
for (i1=0;i1<=20;i1++){
  a = 20*i1;
  for (i2=0;i2<=20;i2++){
    b = 20*i2;
    for (i3=0;i3<=20;i3++){
      c = 20*i3;
     .....
   }
  }
}

Le soucis c'est qu'avec mes contraintes, pour une résolution en continu ca ne fonctionne pas.
Je sais que ce n'est pas la solution optimale ni la plus jolie, mais au moins j'aurai un résultat rapidement (et je vais continuer à chercher une meilleure façon pour résoudre)

En tout cas merci pour l'idée des boucles for imbriquées, c'est exactement ça que je cherchais !

[Nebulix]

for i1:=0 to 20
for i2:=0 to 20-i1
for i3:=0 to 20-i1-i2
...

[Aleph69]

Bonjour,

as-tu essayé la méthode du simplexe? Elle est disponible dans la plupart des tableurs (Excel, ...).

[Franck Dernoncourt]

Bonjour,

as-tu essayé la méthode du simplexe? Elle est disponible dans la plupart des tableurs (Excel, ...).

+1 pour la méthode du simplexe !

[Fluxe]

Bonjour,

as-tu essayé la méthode du simplexe? Elle est disponible dans la plupart des tableurs (Excel, ...).

Bonjour,

Oui j'ai essayé par le solveur excel, cela a même était ma 1ère idée.

Cependant, avec mes contraintes, le solveur n'arrive pas à résoudre toutes les situations.
C'est pour cela que j'avais besoin d'une méthode un peu "bourrine" pour tester toutes les combinaisons avec un pas paramétrable.
Comme celà je fais solveur excel et si j'ai un soucis alors je fais l'autre méthode.

[Franck Dernoncourt]

A part

Chaque poids peut varier de 0 à 100% avec comme contrainte que la somme de tous les poids fassent 100%

quelles sont tes autres contraintes ?