Sujet Précédent Sujet Suivant

Optimisation et programmation linéaire

Fermé
Jean-Philippe - 13 févr. 2012 à 04:04
KX Messages postés 16754 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 - 13 févr. 2012 à 08:17
Bonjour,

J'ai deux questions qui sont à la fois liées mais qui concerne deux domaines bien différent:

- Je travaille sur un problème de plus court chemin sur un graphe non orienté. J'ai déterminé le programme linéaire associé et je cherche quelqu'un pour m'aider à coder l'algo associé afin de trouver la solution optimale. On m'a parlé du Cplex mais j'en sais pas plus!

- J'ai explicité ce même problème sur excel pour utiliser le solver mais il répond que ce n'est pas linéaire. Je pense que c'est du au fait que j'ai utilisé la INDEX. Est-ce bien ça?

Cdt,
jean-philippe


A voir également:

3 réponses

Réponse 1 / 3
KX Messages postés 16754 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 020
13 févr. 2012 à 07:10
- CPLEX est payant (mais la version d'essai est peut-être suffisante), en revanche on peut utiliser des outils gratuits comme GLPK qui sait manipuler le format CPLEX.
- Je ne connais pas le solver d'Excel, mais peut-être que ton programme n'est effectivement pas linéaire, il faudrait voir pour ça...
0
Réponse 2 / 3
Jean-Philippe
13 févr. 2012 à 07:38
Cplex est donc un outil qui exécute l'algo du simplexe à partir d'un format Cplex?
Vous connaissez un bon tutoriel? il me faudra manipuler une variable Xij (i et j allant de 1 à 100, nombre de noeud)
0
KX Messages postés 16754 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 020
13 févr. 2012 à 08:05
Le format "CPLEX LP" a été créé pour le logiciel 'IBM ILOG CPLEX Optimizer", mais vu sa simplicité il a été repris dans les outils libres comme GLPK (GNU Linear Programming Kit)
Je pense que le lien que j'ai mis tout à l'heure (que je remets ici), est suffisant pour comprendre comment : 1) éditer le fichier d'entrée et 2) exécuter glpsol (le solveur de GLPK)
Sinon il doit y avoir une documentation complète fournie avec GLPK (un gros PDF de mémoire), mais c'est vraiment naturel comme écriture, je ne sais pas si t'en auras besoin ^^
0
KX Messages postés 16754 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 020
13 févr. 2012 à 08:17
Mais il n'y a pas que CPLEX non plus. Un format de fichier qui irait surement bien pour ce que tu veux, c'est Math Prog (qui est également utilisable avec GLPK), c'est moins naturel mais ton programme est surement très régulier et ça permettrait d'être plus concis.
0
Réponse 3 / 3
Tchweizz Messages postés 1 Date d'inscription lundi 13 février 2012 Statut Membre Dernière intervention 13 février 2012
13 févr. 2012 à 07:12
slt.tu programme ça sur un IDE et c'est tout
-1
KX Messages postés 16754 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 020
13 févr. 2012 à 07:25
On parle ici de programme linéaire, c'est à dire un système d'équations mathématiques de la forme :

a11.x1+a12.x2+a13.x3... = b1
a21.x1+a22.x2+a23.x3... = b2
a31.x1+a32.x2+a33.x3... = b3
...

En se demandant comment trouver (x1,x2,x3...) tels que z = c1.x1+x2.x2+c3.x3... soit minimal.
Cela se repose sur le seul (ou presque) algorithme que l'on connaisse : le simplexe
0