Introduction

Le terme optimisation sera employé dans ce cours sous sous le sens « d'optimisation mathématique ».

En pratique, la résolution d'un problème d'optimisation mathématique consiste à trouver la meilleure solution à un problème qu'on a su préalablement exprimer sous une forme mathématique particulière qui fait intervenir un ou plusieurs critères. Ce ou ces critères sont exprimés sous la forme d'une fonction mathématique, appelée souvent fonction objectif. La solution optimale ou meilleure solution du correspond à trouver une valeur extrême, appelée aussi extremum – c'est à dire un maximum ou un minimum – à cette fonction objectif. L'optimisation se rapproche donc des calculs d'extremum de fonctions.

Dans le cadre de ce cours, on définira un problème d'optimisation comme la détermination mathématique d'un ensemble de paramètres (ou variables de contrôle) afin d'optimiser (c'est-à-dire minimiser ou maximiser) une quantité mathématique donnée, appelée fonction objectif (ou critère). Cette fonction objectif peut être sujette à des contraintes.

Un problème d'optimisation peut par exemple consister à chercher le maximum du rendement d'une unité de production industrielle, la distance maximale parcourue par un véhicule pour un quantité de carburant donnée, le nombre maximal de clients servis à un guichet dans un intervalle de temps fixé, la résistance mécanique maximale d'une pièce produite, etc. Un problème d'optimisation peut également consister à chercher le minimum des coûts de production d'une usine, à minimiser les pertes thermiques d'un procédé industriel, à identifier le temps de fabrication minimal, etc.

Dans tous ces exemples, il est nécessaire d'avoir modélisé (c'est à dire mis en équations) la grandeur qu'on cherche à minimiser ou maximiser. En fait, on retrouve des problèmes d'optimisation dans de nombreuses applications telles que les problèmes de conception, d'optimisation des conditions de fonctionnement de procédés, d'ordonnancement, de planification de production, de transport, de localisation, mais également dans les domaines économiques et financiers, comme la gestion de portefeuilles.

Face à un problème d'optimisation compliqué, soit en raison du grand nombre d'inconnues et/ou soit en raison de la formulation mathématique complexe, il est rare de pouvoir trouver une solution analytique exacte. Il est alors nécessaire de résoudre « numériquement » le problème. La plupart des algorithmes numériques d'optimisation sont itératifs et permettent de s'approcher pas à pas vers la solution. Selon le problème d'optimisation à résoudre, des algorithmes peuvent être efficaces ou au contraire complètement inopérants.

Les objectifs de ce cours vont être :

  • d'apprendre à formuler un problème d'optimisation,

  • de caractériser ce problème,

  • d'identifier l'algorithme numérique le mieux à même pour le résoudre,

  • de vérifier et d'analyser les résultats obtenus.