Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Techniques d’Optimisation Abdelkader OUTZOURHIT Master GREEN-BEE UM6P Objectifs

Techniques d’Optimisation Abdelkader OUTZOURHIT Master GREEN-BEE UM6P Objectifs • Reconnaitre, Modéliser et (re)formuler les problèmes d’optimisation • Classer les problèmes d’optimisation (LP, QP, NLP. . . ) • Présenter quelques algorithmes de base – gradient – programmation linéaire – programmation quadratique – Algorithmes génétiques • Aborder leur résolution à l’aide d'Excel, Matlab, ou autres programmes 2 3 Programme 1. Introduction à l’Optimisation 2. Classification des Problèmes d’optimisation 3. Techniques Classiques d’Optimisation 4. Programmation linéaire 5. Programmation non-linéaire avec et sans contraintes 6. Algorithmes génétiques Prérequis: – Matlab, EXCEL.. – Notions d’Analyse Numérique – Matrices, déterminant, valeurs propres, matrice définie positive…. – Résolutions systèmes linéaires – Fonctions à plusieurs variables, gradient, Hessien, – Méthodes des résolution des équations non linéaires: Méthode de Newtons, .. – Méthodes de recherche…. 4 5 Bibliographie Textbooks: 1. Andreas Antoniou Wu-Sheng Lu , PRACTICAL OPTIMIZATION : Algorithms and Engineering Applications . 2. Rao S.S., Engineering Optimization - Theory and Practice, John Wiley & Sons, New York, 903 pp, 1996. 3. Gill P.E., Murray W. and Wright M.H., Practical Optimization, Elsevier, 401 pp., 2004. 4. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.(available at http://www.stanford.edu/~boyd/cvxbook/) Journaux 1. Engineering Optimization 2. International Journal for Numerical Methods in Engineering 3. Structural Optimization 4. Journal of Optimization Theory and Applications 6 Logiciels (outils) d’Optimisation Excel Matlab https://en.wikipedia.org/wiki/List_of_optimization_software Name License Description ADMB BSD a nonlinear optimization framework, using automatic differentiation. ASCEND GPL a mathematical modelling chemical process modelling system. CUTEr GPL a testing environment for optimization and linear algebra solvers. GNU_Octave GPL a software package featuring a high- level programming language, primarily intended for numerical computations; well recognized free alternative to MATLAB. Scilab CeCILL a cross-platform numerical computational package and a high- level, numerically oriented programming language with free numerical optimization framework. 7 Evaluation Assiduité: 5% Travail à la Maison: 10% Examen: 40% Projet: 30% 8 Introduction • L’optimisation est la gestion scientifique des paramètres opérationnels contrôlables (variables de décision) pour maximiser la productivité, la rentabilité et la performance, ou minimiser les coûts (Maximiser ou minimiser un critere), tout en respectant des contraintes internes / externes imposées. • Les méthodes de recherche des solutions optimales sont également appelées techniques de programmation mathématique et sont généralement étudiées dans le cadre de la recherche opérationnelle. • Le but éventuel de la recherche opérationnelle est de trouver la meilleure solution possible à un problème, ce qui améliore ou optimise les performances d’un système. Par exemple • Dans un bâtiment: minimiser la consommation énergétique (isolation, fenêtres, orientation..) • Dans une centrale électrique dans laquelle plusieurs chaudières fonctionnent, l’objectif est de générer l’électricité pour répondre à la demande au moindre coût Problème d’optmisation • L'optimisation consiste à obtenir le meilleur résultat dans des circonstances données • Un problème d’optimisation est tout d’abord défini par les variables de décision: Paramètres sur lesquels on peut agir pour faire évoluer le système considéré et dont on doit déterminer les valeurs; Ces variables définissent l’espace de recherche. • Une méthode d’optimisation vise à trouver dans cet espace la solution, ou l’ensemble de solutions, qui permet de satisfaire au mieux le ou les critère(s) du problème • Chaque critère peut être exprimé comme une fonction des variables du problème appelée fonction objectif, fonction coût , critère d’optimisation, critère de décision, ou indicateur …. • Il est possible d’ajouter au problème un ensemble de contraintes: relations limitant le choix des valeurs possibles des variables de décision et par conséquent l’espace de recherche.. • L’optimisation est le processus de recherche des conditions donnant le maximum ou le minimum d'une fonction ou des fonctions objectifs. 9 Exemples Problème Classique du sac-à-dos (Knapsack problem) • On dispose de n objets de poids wi et de valeurs vi (chacun) • Quels à mettre de le sac-a-dos afin de maximiser la somme emportée tout en ne dépassant pas le poids total W= 15 kg autorisé ? • Un seul type d’objet peut être emporté!! Exemple 2: Un étudiant doit réviser pour ses examens. Il a trois matières à passer et il révise xi heures sur la ieme matière, pour i = 1, 2, 3. Nous supposons que la note ni de la matière i dépend uniquement du temps de révision passé xi comme suit: n1(x1 ) = 3x1 , n2 (x2 ) = x2 2; n3 (x3 ) = x3 (100 − x3) • Cet étudiant veut passer au plus 10 heures au total à réviser et veut optimiser sa moyenne totale. • Bâtiment: – Optimiser la performance énergétique (minimiser), – Minimiser les coûts… Math: Minimiser ou maximiser des fonctions à une ou plusieurs variables!!! 10 https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos Applications • L’optimisation intervient dans de nombreux domaines : • recherche opérationnelle (problème de transport, économie, gestion de stocks...) • analyse numérique (approximation/résolution de systèmes linéaires, non linéaires...) • automatique (contrôle de systèmes, filtrage...) • ingénierie (dimensionnement de structures, conception optimale de systèmes (réseaux, ordinateurs...) 11 Modélisation d’un PO Passage du problème réel en un ensemble d’équations!! 1. Identiﬁcation des variables de décisions, ou inconnues, désignées par le vecteur x=(x1,x2,…xn) ∈Rn 2. Identification d’une (ou plusieurs) fonction (s) coût ou fonction objectif f(x)= f(x1,x2,…xn) permettant d’évaluer l’état du système (ex : rendement, performance, consommation, pertes... . . ). 3. Description des contraintes imposées aux variables de décision (revient à définir un ensemble X de solutions) Le problème d’optimisation consiste alors à déterminer les variables de décision conduisant aux meilleures conditions de fonctionnement du système ce qui revient à minimiser ou maximiser la fonction coût), tout en respectant les contraintes d’utilisation déﬁnis à l’étape 3 12 Identification des variables de décision Définition de la (ou des) fonctions objectifs Définir les Contraintes Recherche de la solution optimale Algorithmes 13 Exemples • Un agriculteur possédé un certain nombre d’hectares(T), et des quantités d’engrais (E) et d’insecticide (I) • Il a la possibilité de planter des superficies (en ha) du maïs (x1 ) ou du blé (x2 ) • Les cultures requièrent des quantités différentes d’engrais et d’insecticide (E1 ,I1 ,E2 ,I2 ) par hectare • Les cultures fournissent un revenu différent (S1 ,S2 ) (par hectare) • Objectif : maximiser le revenu net Modélisation: Variable de décision: superficie cultivées Fonction objectif: f(x1,x2)=S1 x1 + S2 x2 Contraintes: terrain et quantités d’engrais et d’insecticide Formulation du PO: Maximiser f(x1,x2)=S1 x1 + S2 x2 Sous les contraintes (SC) x1 + x2 ≤ T (limite terrain) E1 x1 + E2 x2 ≤ E (limite engrais) I1 x1 + I2 x2 ≤ I (limite insecticide) x1 ≥ 0, x2 ≥ 0 (terrain positif !) Exemples Un étudiant doit réviser pour ses examens. Il a trois matières à passer et il révise xi heures sur la ieme matière, pour i = 1, 2, 3. Nous supposons que la note ni de la matière i dépend uniquement du temps de révision passé xi comme suit: n1(x1 ) = 3x1 , n2 (x2 ) = x2 2; n3 (x3 ) = x3 (100 − x3) • Cet étudiant veut passer au plus 10 heures au total à réviser et veut optimiser sa moyenne totale. Modélisation: • Variables de décision: x = (x1 , x2 , x3 ) • Fonction Objectif: moyenne f(x) =1/3 (n1+n2+n3)=1/3(3x1+ x2 2+x3 (100−x3)) • Contraintes: x1+x2 + x3 ≤10 et x1, x2 , x3 ≥0 Formulation du PO: • Maximiser f(x1 , x2 , x3 )=1/3(3x1 + x2 2 + x3 (100 − x3)) SC: x1+x2 + x3 ≤10 et x1, x2 , x3 >=0 14 Exemples Problème du sac à dos (Knapsack problem) • Quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? • Sachant qu’une seule boite de chaque est disponible!!) Modélisation Variables: 5 boites • x1,x2, x 3,x4,x5 (xi=1, objet i mis dans le sac, 0 si non (laissé) • Fonction objective: somme des valeurs totales emportées • Contrainte: poids total Formulation: 15 Exemples dans le bâtiment • Fonction objectif : consommation d'énergie • Fonction objectif : coût • Variables: taille et emplacement des fenêtres, isolation, orientation, longueur des murs, hauteur du bâtiment, taille de la fenêtre et résistance thermique….. 16 • Optimiser les systèmes énergétiques multi-sources. Un problème d'optimisation impliquant plusieurs fonctions objectives est appelé problème de programmation multiobjectif. Quelque techniques pour optimiser les performances des bâtiments 17 Optimiser les performances énergétiques • Amélioration continue de la performance énergétique • Réduction les impacts environnementaux et économiques liés à la consommation d'énergie des bâtiments. Méthodes d'optimisation des performances énergétiques: -Réduire l'empreinte du bâtiment -Réduire la demande -Disposer de capteurs - Récolte de l’Énergie Orientation du bâtiment Emplacement des fenêtres Ventilation naturelle - Améliorer l'efficacité Conception de CVC (HVAC), l'éclairage et l'enveloppe du bâtiment - Récupérer les pertes/rejets d'énergie Energie de l’air renouvelé Chaleur des eaux grises Cogénération 18 Formulation Mathématique Générale d’un PO • f : Rn  R: est la fonction objectif à minimiser • x=(x1,…..,xn): est le vecteur des variables de décision, de conception ou d'optimisation qui décrivent le problème d'optimisation(inconnues du problème, elles doivent être linéairement indépendantes) • gi : Rn  R: (i=1,…,m): contraintes d’inégalité • hi uploads/Litterature/ 1-techniques-optimisation-ao.pdf