Simplex
Un article de Wikibot.
Cette méthode qui n'est pas particulièrement issue de l'Intelligence artificielle mais plutôt de l'optimisation linéaire, est une méthode qui permet de rechercher des optimums dans un espace de plusieurs variables contraintes. Il est nécessaire de disposer de :
- une fonction coût ou objectif souvent notée Z.
- des fonctions de contraintes impliquant une ou plusieurs variables.
La méthode consiste alors à se placer à l'intérieur du polygone ou polyèdre des solutions admissibles.(C'est à dire un point particulier dans l'espace satisfaisant toutes les conditions de contrainte). Puis de glisser sur les arêtes de ce polygone (resp. polyèdre) vers le sommet solution. Plusieurs déplacement sont souvent nécessaire pour atteindre le somment recherché.
La théorie (à vérifier) assure que l'optimum se trouve sur un sommet du polygone (resp. polyèdre) ou à défaut directement sur une arête ou une face ou Z à une valeur constante.
Le problème peut devenir un peu plus long si la solution de départ (dite solution admissible) n'est pas triviale (du type (0,0,0,0..) Dans ce cas de figure il existe une méthode tout à fait similaire qui permet de réaliser la recherche de solution admissible puis d'entamer la résolution.
Les différentes opérations composant l'algorithme du Simplex sont d'autant plus simple à suivre que l'on dispose les calculs dans une matrice (tableau). Je vous renvois à un cours d'optimisation pour plus de détails. (A commencer par : http://fr.wikipedia.org/wiki/Algorithme_du_simplexe)
Dans tous les cas c'est un algorithme qui se code très facilement dès lors que l'on travaille dans un espace pratique (permettant d'éliminer très vite des cas particuliers)
On comprend l'idée assez simplement de manière graphique sur un cas simple.
Considérons X et Y deux variables, Z = 2*X + 4*Y ainsi que les contraintes X> 0, Y>0 ,X < 4 et Y +X = 6 On peut alors tracer dans le plan l'ensemble des contraintes, remarquer que 0,0 est solution admissible Puis d'appliquer l'algorithme du simplex afin d'atteindre le sommet maximum.
