Discussion :

[ToTo13]

Bonjour,

est ce que quelqu'un saurait où est ce que je peux trouver le code source (C, C++, Java) de la méthode "Simplex" ?
Je souhaite une version où on peut demander une minimisation de la fonction de coût.

J'ai déjà trouvé les choses suivantes :
- Numerical recipes => ne fait que maximiser la fonction et le code n'est vraiment pas clair.
- http://www-fp.mcs.anl.gov/otc/Guide/...et/source.html C'est une applet où le déroulement n'est pas automatique; L'utilisateur doit en permanence choisir ce qu'il veut faire. L'interface rend le code absolument illisible.

Merci par avance...

[pseudocode]

DownHill Simplex (click me)

[sidahmed]

Bonsoir,

j'ai un code en Pascal, si tu es intéressé n'hésite pas.

Cordialement,
Sidahmed.

[ToTo13]

Bonjour,

merci pour les réponses, je vais regarder tout cela.

Sidahmed : peux tu me donner ton code pour que je jète un coup d'oeil ? Soit directement dans le poste, soit par MP si tu ne veux pas qu'il soit diffusé.

[FrancisSourd]

- Numerical recipes => ne fait que maximiser la fonction et le code n'est vraiment pas clair.

Il y a en fait deux méthodes du simplexe. Celle pour une optimisation d'une fonction non dérivable (optimisation sans contraintes) et l'autre pour la programmation linéaire (fonction objectif linéaire et contraintes linéaires). Pour cette dernière, il y a SoPlex, GLPK ou lp_solve en opensource.

[sidahmed]

Je ne suis pas d'accord ! Je ne pense pas qu'on parle de la méthode du Simplex dans la programmation non linéaire mais plutôt des méthodes suivantes :

• Méthode de direction réalisable
• Méthode de Frank-Wolfe
• Méthode de projection

À confirmer !

Cordialement,
Sidahmed.

[FrancisSourd]

Franchement, je ne vois pas l'intérêt de ton message. Tu devrais de douter que si je souligne le fait qu'il existe deux méthodes du simplexe, c'est pas par pur plaisir d'écrire d'écrire n'importe quoi mais bien parce que j'en connais deux et qu'il ne faut pas les confondre car elles n'ont rien à voir. Dans l'une, l'algo se promène sur les sommets du simplexe, dans l'autre, c'est un simplexe qui se déplace dans R^n.

Réf sur la méthode du simplexe en optim non linéaire:
http://en.wikipedia.org/wiki/Nelder-Mead_method

[ToTo13]

Bonjour,

dans mon cas, j'ai une fonction linéaire représentant une erreur et par conséquent je souhaites trouver les coefficients qui minimisent la valeur de ma fonction.

Donc laquelle dois je utiliser ?
Si quelqu'un a du code (C, C++, Java) qui fait cela je suis fortement preneur. Sinon des liens vers du code.

merci...

[ToTo13]

Bonsoir,

petites précisions supplémentaires :
- Je souhaites minimiser une fonction linéaires.
- Je n'ai aucune contraintes sur le problème ou sur les variables.
- Donc les coefficients solutions peuvent (et sont même souvent) négatifs.

J'ajoute cela car la plupart des applets que j'ai trouvé ajoutent comme contraintes que les coefficients solutions doivent être positifs ou nul.

Merci par avance...

[FrancisSourd]

petites précisions supplémentaires :
- Je souhaites minimiser une fonction linéaires.
- Je n'ai aucune contraintes sur le problème ou sur les variables.
- Donc les coefficients solutions peuvent (et sont même souvent) négatifs.

Il doit quand même y avoir des contraintes. Sinon la solution de ton problème est 0 ou "-infini". En effet
min a1.x1 + a2.x2 + ... + an.xn
Si tu as un ai>0, tu prends xj=0 pour j≠i et xi aussi petit que nécessaire.
Si tu as un ai<0, tu prends xj=0 pour j≠i et xi aussi grand que nécessaire.
Sinon, tu as la fonction nulle (et sa minimisation donne 0).

D'une manière générale, le fait de travailler avec des variables positives ne limite pas le problème. En effet, tu peux remplacer une variable x non contrainte en signe par xp - xm où xp et xm sont deux variables positives.