Introduction à l'optimisation

« RI CI CHAPITRE 1 HE INTRODUCTION À L’OPTIMISATION Sommaire Problème d’optimisation .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. 1 2 Terminologie .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. 2 3 Classification de problème d’optimisation .

.

.

.

.

.

.

.

.

.

.

. 4 .N ad aK 1 4 3.1 Optimisation Continue, Optimisation Discrète et Combinatoire 4 3.2 Optimisation avec et sans contraintes .

.

.

.

.

.

.

.

.

.

.

.

.

. 5 3.3 Optimisation mono ou multi-objectifs .

.

.

.

.

.

.

.

.

.

.

.

.

. 5 Domaines d’applications d’Optimisation Combinatoire .

.

.

. 5 Introduction Dr Avant de parler d’optimisation combinatoire, il faut définir d’abord le domaine d’optimisation.

Les problèmes d’optimisation cherchent le meilleur rendement possible.

Selon la nature de l’espace de recherche, des contraintes et des objectifs, on définit plusieurs types d’optimisation.

Ce chapitre explique les notions de bases de l’optimisation (Blum et Roli, 2003), (Urli, 2014), (Walter, 2015), (Ouaarab, 2015), (Layeb, 2010), (Belhoul, 2014), (Solnon, 2010). 1 Problème d’optimisation L’optimisation est un nom féminin qui définit une action du verbe optimiser.

C’est la démarche consistant à rendre optimal le fonctionnement d’un système : Donner à quelque 1 2.

TERMINOLOGIE RI CI chose (à une machine, à une entreprise, etc.) le rendement optimal en créant les conditions les plus favorables ou en tirant le meilleur parti possible. L’optimisation appartient au domaine de la Recherche Opérationnelle qui représente la science de prise de décision.

Un problème d’optimisation en mathématique consiste à trouver la meilleure solution possible pour un problème donné. HE Définition 1.

Problème d’optimisation Soit n ∈ N∗ un entier strictement positif, X ⊂ Rn un sous-ensemble non vide f : X → R une fonction à valeur réelle. Un problème d’optimisation consiste à trouver la meilleure solution x ∈ X appelée solution globale. 2 .N ad aK La meilleure solution du problème varie selon l’objectif.

On parle d’une minimisation ou une maximisation de la fonction f sur l’ensemble X.

On note : x = minx∈X f (x) ou x = maxx∈X f (x). Terminologie Variables de décision : Le vecteur x ∈ X est appelé vecteur de décision.

Les éléments formants le vecteur de décision sont appelés variables de décision.

Ce sont les variables recherchées dans le problème. Dimension de problème : La dimension du problème est représentée par le nombre entier n ∈ N∗ .

Elle représente le nombre de variables de décision.

Une solution à un problème de 3 dimensions est un vecteur de 3 éléments (3-uplet). Dr Espace de recherche et Solution admissible : L’ensemble X de dimension n contient les valeurs que le vecteur x peut prendre.

Ces dernières sont appelées solutions admissibles ou faisables (ou encore solutions candidates).

Une solution admissible est une affectation de toutes les variables de décision , qui répond aux contraintes du problème. L’ensemble X est connu sous différentes appellations : ensemble admissible, espace de solution, espace de recherche, domaine de recherche etc. Contraintes : L’espace de recherche X est limité par quelques règles.

Une contrainte est une condition que doivent respecter les vecteurs de décision du problème. Solution optimale : C’est la meilleure solution x ∈ X du problème.

.

Elle est appelée solution globale ou optimale. Optimisation Combinatoire, M1 GADM, Dr.

N.

KHERICI, UBMA, 2020/2021 2 CHAPITRE 1.

INTRODUCTION À L’OPTIMISATION RI CI Fonction objectif : la fonction f , à valeur scalaire, sert de critère pour déterminer la meilleure solution du problème.

Elle est appelée fonction d’objectif (fonction fitness, critère, etc).

Elle attribue à chaque solution x ∈ X de l’espace de recherche, un nombre réel indiquant sa valeur (son score). Minimisation : Une minimisation revient à trouver un élément x de X tel que : ∀x ∈ X : f (x) 6 f (x).

On dit qu’on cherche à minimiser la fonction f sur l’ensemble X.

Dans ce cas la fonction d’objectif f est connue comme une fonction de coût .

Le vecteur x est une borne inférieure de l’ensemble X. HE Maximisation : Une maximisation revient à.... »