Chapitre 4
Méthode de résolution
4.1 Introduction
A l'heure actuelle, il est généralement admis de
considérer la résolution de problèmes comme un processus
complexe de modélisation mathématique. Ce processus complexe peut
se traduire par la mise en oeuvre d'une démarche de résolution
impliquant plusieurs phases. Résoudre des problèmes après
la formulation mathématique nécessite un questionnement sur la
nature du modèle. Ceci consiste à comprendre
l'énoncé et à construire une modélisation, puis
mettre en oeuvre des stratégies et des procédures de
résolution. Ces phases sont indissociables, la démarche
considérée pour analyser et résoudre un système est
illustrée dans le schéma suivant:
FIGURE 4.1 - Le processus de l'analyse du
système
63
4.2. LA PROGRAMMATION NON LINÉAIRE MIXTE EN NOMBRES
ENTIERS
4.2 La programmation non linéaire mixte en
nombres entiers
Les problèmes d'optimisation sont classés en
grandes catégories, linéaire(LP), non li-néaire(NLP),
programmation linéaire mixte en nombres entiers (MILP), en fonction de
leurs caractéristiques mathématiques. La formulation la plus
complexe, rencontrée fréquemment à l'ingénierie,
relève des problèmes non linéaires mixte en nombres
entiers « Mixed Integer
Non Lineair
Programming».
4.2.1 Qu'est ce qu'un programme MINLP?
Un programme non linéaire mixte en nombres entiers
MINLP est un problème d'op-timisation consiste à minimiser une
fonction objectif non linéaire à n variables mixtes,
discrètes et continues soumises à un ensemble de contraintes non
linéaire exprimées sous forme d'équations ou
d'inéquations.
La formulation générale d'un problème MINLP
est donnée par:
? ? ???????????????
???
???????????????????
Où
Min f (x,y) S.C :
h(x,y) = 0 g(x,y) 0
x ? X
y ? Y entier
- f (x,y) : fonction objectif.
- h(x,y) : Ensemble des contraintes
égalité.
- g(x,y) : Ensemble des contraintes
inégalité.
- X : Ensemble des variables continues.
- Y : Ensemble des variables entières.
64
4.2. LA PROGRAMMATION NON LINÉAIRE MIXTE EN NOMBRES
ENTIERS
La variable x correspond généralement aux
variables physiques (débit, pression, température, etc). Et la
variable y correspond aux variables qui traduisent l'existence ou non d'une
opération unitaire, le nombre d'unités d'une entité,
etc.
4.2.2 Technique de résolution
La programmation non linéaire mixte en nombre entier
combine la difficulté de l'opti-misation combinatoire sur des ensembles
de variables entières avec la difficulté de la manipulation d'une
fonction objectif non linéaire et des contraintes non linéaires.
L'exécution des méthodes dites exactes (programmation dynamique,
séparation et évaluation) pour la résolution de ce
problème risque de prendre un temps de calcul considérable.
Afin d'éviter ce genre de situation, on se contente
souvent d'une solution dite approchée données par certaines
méthodes appelées « méthodes approchées»
et dont la valeure de la fonction objectif correspondante se rapproche de celle
de la solution exacte.
Vu qu'on est en présence d'un problème non
linéaire en variables mixtes assez complexe, nous proposons d'utiliser
une heuristique pour obtenir une solution réalisable et de
l'amé-liorer avec deux métaheuristiques : Algorithme
génétique et recuit simulé.
65
4.3. LES MÉTHODES APPROCHÉES
| 
