Optimisation et programmation linéaire
Jean-Philippe
-
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
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
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:
- Programmation linéaire avec excel pdf
- Lire le coran en français pdf - Télécharger - Histoire & Religion
- Liste déroulante excel - Guide
- Word et excel gratuit - Guide
- Save as pdf office 2007 - Télécharger - Bureautique
- Déplacer colonne excel - Guide
3 réponses
- 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...
- 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...
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)
Vous connaissez un bon tutoriel? il me faudra manipuler une variable Xij (i et j allant de 1 à 100, nombre de noeud)
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 ^^
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 ^^
slt.tu programme ça sur un IDE et c'est tout
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
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