38
Chapitre 4.Modélisation du problème
posé
Les méthodes heuristiques se divisent en deux:
· Les heuristiques de constructions : le principe est la
construction progressif d'une solution initiale par une suite d'instruction
gloutonne en démarrant de rien. Exemple : plus proche voisin,
heuristique d'insertion.
· Les heuristiques de d'amélioration : contrairement
aux heuristiques de constructions, les heuristiques d'améliorations
démarrent d'une solution réalisable puis l'améliorer de
proche en proche. Exemple : transformation admissible, méthode de
descente.
Les Méta-heuristiques
Une Méta-heuristique peut être définie
comme une méthode algorithmique qui a pour stratégie de
dévier et orienter le processus de recherche dans un espace de solution
(souvent très grand) vers des régions riches en solutions
optimales dans le but de s'approcher de cette dernière afin de
déterminer des solution (presque) optimales en un temps raisonnable.
Parmi les méta-heuristiques les plus utilisées,
nous trouvons :
· Recuit simulé,
· Recherche tabou,
· Algorithme génétiques,
· Algorithme de colonies de fourmis.
L'organigramme suivant résume quelques méthodes de
résolutions:
Méthodes de résolution
|
Méthodes exactes
|
Méthodes approchées
|
|
Séparation et évaluation
|
Programmation dynamique
|
Heuristiques
|
Méta-heuristiques
|
FIGURE 4.2 - Organigramme récapitulatif
des méthodes de résolutions
Chapitre 4.Modélisation du problème
posé
4.5 La modélisation avec solveur CPLEX
4.5.1 Présentation du solveur CPLEX
CPLEX est un outil informatique d'optimisation
commercialisé par IBM depuis son acquisition de l'entreprise
française ILOG en 2009. Son nom fait référence au langage
C et à l'algorithme du simplexe. Il est composé d'un
exécutable (CPLEX interactif) et d'une bibliothèque de fonctions
pouvant s'interfacer avec différents langages de programmation: C, C++,
Java et Python.[20]
CPLEX Optimizer fournit des solveurs de programmation
mathématique flexibles et hautes performances pour les problèmes
de programmation linéaire, de programmation mixte en nombres entiers, de
programmation par contraintes et de programmation à contraintes
quadratiques. Ces solveurs incluent un algorithme parallèle
distribué pour la programmation mixte en nombres entiers afin de tirer
parti de plusieurs ordinateurs pour résoudre des problèmes
difficiles.[21]
4.5.2 Le modèle en CPLEX
La résolution d'un modèle mathématique de
programmation linéaire (petite taille) se fait en utilisant plusieurs
méthodes, la plus connue est l'algorithme du Simplex qui a
été utilisé dans plusieurs domaines. La figure suivante
représente le modèle sous CPLEX :
39
FIGURE 4.3 - Modélisation du
problème sous CPLEX
40
| 
