Remerciez-le!

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

0 Recherche opérationnelle Avancée Cours & Exercices Authored by: Abdesslem LAY

0 Recherche opérationnelle Avancée Cours & Exercices Authored by: Abdesslem LAYEB Chapitre1 : IŶtƌoductioŶ à l’optiŵisatioŶ ŵathéŵatiƋue Module TAO M1 STIC 1 Enseignant : A. LAYEB 1.1 Introduction L'optimisation est une branche des mathématiques consistant à rechercher des conditions ou des configurations optimales pour des systèmes variés. Ce mot nous vient du latin optimum qui signifie le meilleur. Elle est très importante en analyse numérique et dans les mathématiques appliquées, fondamentales pour l'industrie et l'ingénierie. En effet, lorsqu’un phénomène économique, physique, chimique... est exprimé par des équations, il est nécessaire d'optimiser le système afin d'obtenir un rendement maximal ou une configuration idéale. Pour cela on utilise des outils mathématiques. Aujourd'hui, tout est optimisé : Le fonctionnement d'un moteur, la gestion des lignes ferroviaires, les investissements économiques, les réactions chimiques... etc. Les exemples sont multiples, il est donc crucial de posséder les outils pour résoudre ces problèmes. L’objectif consiste à maximiser une fonction f appelée la fonction objectif. Les éléments de l’espace de définition de la fonction f sont appelées les solutions admissibles. Dans le cas où les solutions admissibles appartiennent à l’ensemble des entiers N, on parle de l’optimisation combinatoire. L'optimisation combinatoire est un outil indispensable combinant diverses techniques des mathématiques discrètes et de l'informatique afin de résoudre des problèmes de la vie réelle. D’une manière simple, résoudre un problème d’optimisation combinatoire consiste à trouver l’optimum d’une fonction, parmi un nombre fini de choix, souvent très grand. Il s’agit, en général, de maximiser (problème de maximisation) ou de minimiser (problème de minimisation) une fonction objectif sous certaines contraintes. Le but est de trouver une solution optimale dans un temps d’exécution raisonnable. Néanmoins, ce but est loin d’être concrétisé pour plusieurs problèmes vu la leurs complexités grandissantes. La théorie de la NP-complétude a permis de classifier les problèmes d’optimisation selon leurs complexités et elle fournit des informations pertinentes sur le genre de méthodes à choisir en fonction de la difficulté intrinsèque des problèmes. Lorsqu’une solution est associée à une seule valeur, on parle de problèmes mono-objectifs, et lorsqu’elle est associée à plusieurs valeurs, on parle de problèmes multi-objectifs (ou multi-critères). Il faut noter que, l’optimisation d’un problème multi-objectif est souvent plus difficile que l’optimisation des problèmes mono-objectifs. En effet, L’optimisation multi-objectif permet de modéliser des problèmes réels faisant concourir de nombreux critères (souvent conflictuels) et contraintes. Dans ce contexte, la solution optimale recherchée n’est plus un simple point, mais un ensemble de bons compromis satisfaisant toutes les contraintes. Bien que les problèmes d'optimisation combinatoire soient souvent faciles à définir, ils sont généralement pénibles à résoudre. En effet, la plupart de ces problèmes appartiennent à la classe des problèmes NP-difficiles et ne possèdent pas encore de solutions algorithmiques efficaces et acceptables pour toutes les données. Les techniques pour résoudre les problèmes mathématiques dépendent de la nature de la fonction objectif de l'ensemble contraint. Les sous-domaines majeurs suivants existent : Chapitre1 : IŶtƌoductioŶ à l’optiŵisatioŶ ŵathéŵatiƋue Module TAO M1 STIC 2 Enseignant : A. LAYEB La programmation linéaire étudie les cas où la fonction objectif et les contraintes sont linéaires. La programmation linéaire en nombres entiers étudie les programmes linéaires dans lesquels certaines ou toutes les variables sont contraintes à prendre des valeurs entières. La programmation quadratique concerne les problèmes dont la fonction objectif contient des termes quadratiques ( ex :f(x)= x2+x), tout en conservant les contraintes linaires . La programmation non-linéaire étudie le cas général dans lequel la fonction objectif ou les contraintes (ou les deux) contiennent des parties non-linéaires. La programmation stochastique concerne les problèmes avec des contraintes dépendant de variables aléatoires. La programmation dynamique ce type de méthodes est utilisé dans le cas où les le problème est décomposables en petites entités facilement résolubles. Elle n’est utilisable que lorsque la fonction objectif est monotone croissante. De ce fait, la résolution d’un problème en programmation dynamique est basée sur une décomposition du problème en sous-problèmes plus simples. A chaque sous-problème correspond un ensemble d’options, représentant chacune un coût en terme de fonction objectif. Un ensemble de choix doit donc être effectué pour les différents sous-problèmes dans le but d’arriver à une solution optimale. 1.2 La théorie de la complexité La théorie de la complexité consiste à estimer la difficulté ou la complexité d'une solution algorithmique d’un problème posé de façon mathématique. Elle se concentre sur les problèmes de décision qui posent la question de l’existence d’une solution comme le problème de satisfiabilité booléenne. La théorie de la complexité repose sur la notion de classes de complexité qui permettent de classer les problèmes en fonction de la complexité des algorithmes utilisés pour les résoudre. Parmi les classes les plus courantes, on distingue:  La classe P (Polynomial time) qui englobe les problèmes pour lesquels il existe un algorithme déterministe de résolution en temps polynomial,  La classe NP (Nondeterministic Polynomial time) qui contient des problèmes de décision pour lesquels la réponse oui peut être décidée par un algorithme non-déterministe en un temps polynomial par rapport à la taille de l’instance. Les problèmes NP-complets sont définis comme suit: Définition 1.1 (Problème NP-complet) Un problème de décision п est NP-complet s’il satisfait les deux conditions suivantes : п ∈ NP, et tout problème NP se réduit à п en temps polynomial. L’une des questions ouvertes les plus fondamentales en informatique théorique est vraisemblablement la question si « P=NP ? » (Figure 1.1). Ceci revient à trouver un algorithme polynomial pouvant résoudre un problème NP-complet. Trouver un tel algorithme, pour un seul problème appartenant à la classe NP-complet, signifierait que tous les problèmes de cette classe pourraient être résolus en temps polynomial (voir Définition 1.1) et en conséquence, que P=NP. Chapitre1 : IŶtƌoductioŶ à l’optiŵisatioŶ ŵathéŵatiƋue Module TAO M1 STIC 3 Enseignant : A. LAYEB Cependant, il est commun de penser que P≠NP, mais aucune preuve n’a encore été trouvée jusqu’à aujourd’hui. Il est important de préciser que tous les problèmes d’optimisation ne peuvent pas être classifiés comme problèmes NP-complets, puisqu’ils ne sont pas tous des problèmes de décision, même si pour chaque problème d’optimisation on peut définir un problème de décision qui a une complexité équivalente. Définition 1.2 (Problème NP-difficile) Un problème P quelconque (de décision ou non) est NP- difficile si et seulement s’il existe un problème NP-complet P′ qui est réductible à lui polynomialement. La définition d’un problème NP-difficile est donc moins étroite que celle de la NPcomplétude. De cette définition on peut observer que pour montrer qu’un problème d’optimisation est NP- difficile, il suffit de montrer que le problème de décision associé à lui est NP-complet. De cette façon un grand nombre de problèmes d’optimisation ont été prouvés NP-difficiles. C’est notamment le cas des problèmes du Voyageur de Commerce, de Partitionnement de Graphes et d’Affectation Quadratique. Figure.1.1 ‒ classe P, NP, NP-complet, NP-difficile. 1.3 Formulation mathématique des problèmes d’optimisation Les problèmes d’optimisation combinatoire peuvent être formulés comme suit : Définition 1.3 (Problèmes mono-objectifs) : Un problème d’optimisation est généralement formulé comme un problème de minimisation ou de maximisation, et écrit sous la forme suivant: minx f(x), Tel que, gi(x) ≤0 , i = 1, . . . ,m , (1.1) hj(x) = 0 , j = 1, . . . , p , x ∈ S ⊂ Rn, P=NP P=NP= NP-Complet NP-difficile NP-difficile NP-Complet P P≠NP Chapitre1 : IŶtƌoductioŶ à l’optiŵisatioŶ ŵathéŵatiƋue Module TAO M1 STIC 4 Enseignant : A. LAYEB Où f est la fonction (scalaire) à minimiser, appelée fonction coût ou fonction objectif, x représente le vecteur des variables d’optimisation, gi sont les contraintes d’inégalité et hj les contraintes d’égalité, et S est l’espace des variables (appelé aussi espace de recherche). S indique quel type de variables sont considérées : réelles, entières, mixtes (réelles et entières dans un même problème), discrètes, continues, bornées, etc. Un point xA est appelé un point admissible si xA ∈ S et si les contraintes d’optimisation sont satisfaites : gi(xA) ≤0 , i = 1, . . . ,m et hj(xA) = 0 , j = 1, . . . , p. La solution de (1.1) est l’ensemble des optima {x*}. x* est un minimum global de f si et seulement si f(x*)≤f(x) ∀ x ∈ S, et x*est un minimum local de f si et seulement si f(x*)≤ f(x) ∀ x ∈ S / ||x − x*|| ≤ ɛ, ɛ > 0. La Figure 1.2 présente un exemple d’une fonction à une variable, avec des minima locaux et un minimum global. Parmi les minima locaux, celui qui possède la plus petite valeur de f est le minimum global. Par ailleurs, une fonction multimodale présente plusieurs minima (locaux et globaux), et une fonction unimodale n’a qu’un minimum, le minimum global. La Figure 1.3 montre une fonction multimodale à deux variables. Figure 1.2 ‒ Minima locaux et minimum global d’une fonction à une variable. Figure 1.3 ‒ Une fonction multimodale à deux variables. Chapitre1 : IŶtƌoductioŶ à l’optiŵisatioŶ ŵathéŵatiƋue Module TAO M1 STIC 5 Enseignant : A. LAYEB Définition 1.4 (Problèmes multi-objectifs) : D’un point de vue mathématique, un problème d’optimisation multi-objectif, se présente, dans uploads/Management/ recherche-operationnelle-avancee-cours-a.pdf