Remerciez-le!

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

L’optimisation MultiObjectif Cours et Exercices Auteur: Wassila DRICI & Lamia Z

L’optimisation MultiObjectif Cours et Exercices Auteur: Wassila DRICI & Lamia ZERFA Institut: Université M’Hamed Bougara de Boumerdès Date: Mai 24, 2021 Version: 1.00 Master I: Recherche Opérationnelle Victory won’t come to us unless we go to it. Sommaire 1 Introduction à l’optimisation Multiobjectif 1 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Concepts de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Cônes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Caractérisation d’une solution eﬃcace . . . . . . . . . . . . . . . . . . . . . . 8 Chapitre 1 Introduction à l’optimisation Multiobjectif Dans ce chapitre nous présentons loptimisation mathématique multiobjectif et nous intro- duisons les concepts fondamentaux tels que la dominance et la surface de compromis. 1.1 Introduction La programmation mono-objective consiste à trouver parmi un ensemble de solutions re- spectant des contraintes une solution qui optimise une fonction objectif. Par optimiser, on entend trouver la plus petite valeur (problème de minimisation) ou la plus grande valeur (problème de maximisation) de la fonction. La principale diﬃculté que lon rencontre en optimisation monobjectif vient du fait que modéliser un problème sous la forme dune équation unique peut être une tâche diﬃcile. Avoir comme but de se ramener à une seule fonction objectif peut aussi biaiser la modélisation. Loptimisation multiobjectif autorise ces degrés de liberté qui manquaient en optimisation mono-objectif. La plupart des problèmes doptimisation réels sont décrits à laide de plusieurs objectifs ou critères souvent contradictoires ou conﬂictuels devant être optimisés simultanément. Il nexiste généralement pas de solution qui optimise tous les critères en même temps, le concept de solution optimale devient alors plus diﬃcile à déﬁnir. En eﬀet, en considérant deux critères contradictoires "a" et "b", améliorer "a" détériore forcement "b" et inversement, il faut donc trouver un compromis. Dans ce cas, la solution optimale cherchée nest plus un point unique, mais un ensemble de compromis. Résoudre un problème comprenant plusieurs critères, consiste donc à calculer le meilleur ensemble de solutions compromis : le front Pareto. (Travaux de Koopmans [50], Kuhn et Tucker [51], [82], [73] [55], [56], [33], [19] [76]). Exemples d’application: De nombreuses situations pratiques nécessitent la considération simultanée de plusieurs objectifs contradictoires, tels que : 1. La sélection d’un itinéraire/routage dans un réseau: durée; coût; sécurité/ﬁabilité. 2. La planiﬁcation de production: coût; consommation; 1.2 Concepts de base – 2 – production. 3. Le choix d’un candidat à un poste: formation; motivation; âge; salaire demandé. 1.2 Concepts de base 1.2.1 Formulation mathématique Un problème d’optimisation multiobjectif est un problème de décision qui consiste à opti- miser (minimiser ou maximiser) simultanément k(k > 1) fonctions objectifs souvent contradic- toires sur un ensemble de solution S. Il se déﬁnit de la façon suivante : (MOP)      Max Z(x) = (z1(x), z2(x), ..., zk(x)) sc x ∈S (1.1) où S ⊂Rn, est l’ensemble des solutions réalisables de (MOP), zi(x) : Rn →R est la iime fonction objectif, i = 1, ..., k. C’est la fonction de préférence partielle du décideur. La résolution de (MOP) consiste à déterminer un ou plusieurs "bons compromis". 1.2.2 Espace des décisions- Espace des critères Déﬁnition 1.1. Espace des décision ♣ L’espace des décisions est l’espace de Rn dont lequel se situe l’ensemble des solutions réalisables S. Déﬁnition 1.2. Espace des critères ♣ L’espace des critères est l’espace de Rn contenant l’ensemble des images des solutions S par Z noté ZS avec : ZS = {Z(x) = (z1(x), z2(x), ..., zk(x))|x ∈S} = {y ∈Rk : y = Z(x), x ∈S}. Achaquesolution réalisable x dans S, onassocie sonimageZ(x) = (z1(x), z2(x), ..., zk(x)) Remarque Si les fonctions zi(x) i = 1, ..., k et les contraintes sont toutes linéaires alors le prob- lème est dit linéaire multiobjectif MOLP. Ce problème peut être formulé mathématiquement comme : 1.2 Concepts de base – 3 – Figure 1.1: Espace de décision-Espace des critères (MOLP)      Max zi(x) = cix i = 1, ..., k sous x ∈S = {x ∈Rn | Ax ≤b, x ≥0} (1.2) A: m × n-matrice réelle, b: m × 1-vecteur réel, x: n × 1-vecteur réel, ci: 1 × n-vecteur réel,i = 1, ...k. Théorème 1.1 ♡ Comme S est un polyèdre convexe de Rn et si les critères sont linéaires, alors ZS est aussi un polyèdre convexe de Rk, dont les sommets correspondent aux images des sommets de S . Preuve Z(D) est bien un polyèdre car il est déﬁni par un système linéaire d’équations et d’inéquations :            y = Z(x) x ∈S x ≥0, y réel (1.3) De plus, il est convexe car ∀y1, y2 ∈Z(S) et ∀α ∈[0, 1], ∃x1, x2 ∈S | y1 = Z(x1) et y1 = Z(x1), et on a: αy1 + (1 −α)y2 =αZ(x1) + (1 −α)Z(x2) = Z(αx1) + Z((1 −α)x2) = Z(αx1 + (1 −α)x2) = Z(x), avec x = αx1 + (1 −α)x2 ∈S. (1.4) Donc, (αy1 + (1 −α)y2) ∈Z(S) ⇒Z(S) est convexe. Montrons, par contraposée, que si y ∈Z(S) est un sommet, alors ∃x ∈S|y = Z(x), x sommet de S. 1.2 Concepts de base – 4 – Soit A un point de S qui n’est pas un sommet, alors: ∃x1 ∈S, ∃x2 ∈S, x1 ̸= x2, ∃α ∈ ]0, 1[ | A = αx1 + (1 −α)x2. Alors, Z(A) ∈Z(S) et Z(A) = Z (αx1 + (1 −α)x2) ⇒Z(A) = αZ (x1) + (1 −α)Z (x2) car Z linéaire ⇒Z(A) = αy1 + (1 −α)y2, y1, y2 ∈Z(D), y1 ̸= y2 ⇒Z(A) n’est pas un sommet de Z(S) Exemple1.1 Considérons le problème d’optimisation bi-objectif suivant :                                      max z1 = x1 −x2 max z2 = −x1 sc x1 + x2 ≤5 x1 ≤3 x1, x2 ≥0 . (1.5) L’ensemble des décisions correspondant au problème (1.5) est représenté dans la ﬁgure suivante: Figure 1.2: Espace de décisions. Pour représenter l’espace des critères, dans le cas général, nous devons formuler le problème (1.5) en fonction des fonctions objectifs z1 et z2. On commence par déduire les variables de décisions en fonction des fonctions objectifs comme suit : x1 = −z2 et x2 = −z1 −z2. Puis on remplace les variables de décision xi, i = 1, .., 2 par les fonctions objectifs zi,i = 1, 2 dans chaque contrainte, y compris les contraintes de signes. Dans notre exemple, puisqu’il s’agit de problème d’optimisation linéaire, il suﬃt de calculer les images des sommets a = (0, 0), b = (3, 0), c = (3, 2), d = (0, 5) en fonction des fonctions objectifs. On trouve Z(a) = (0, 0), Z(b) = (3, −3), Z(c) = (1, −3), d = (−5, 0). Ensuite, nous 1.2 Concepts de base – 5 – relions ces images pour obtenir l’espace des critère. Notons que l’ordre dans lequel nous relions ces points doit être le même que dans l’espace des décision. L’espace des critères correspondant au problème (1.5) est représenté dans la ﬁgure suivante: Figure 1.3: Espace des critères. 1.2.3 Dominance et eﬃcacité Dans tous ce qui suit, on considère que toutes les fonctions objectifs sont à "Maximiser". Déﬁnition 1.3. La dominance ♣ On dit qu’un vecteur Z = (z1, z2, ..., zk) domine un vecteur Y = (y1, y2, ..., yk), si ∀i = 1...k, zi ≥yi et ∃i ∈{1...k} tel que zi > yi. Déﬁnition 1.4. L’eﬃcacité ♣ Une solution réalisable x∗∈S est eﬃciente (ou eﬃcace) s’il n’existe pas une autre solution x ∈S telle que Z(x) domine Z(x∗). Note A partir d’un point eﬃcace, il est impossible d’augmenter la valeur d’un des critères sans diminuer la valeur d’au moins un autre critère. Résoudre le problème (MOP) revient à trouver, soit l’ensemble des solutions eﬃcaces SE dans l’espace des décisions, soit l’ensemble des solutions non dominées ZD dans l’espace des critères. Exercice1.1 Soit le problème dans R2 suivant : (MOP)                          Max Z(x) = (z1(x) = x1 + 2x2, z2(x) = 3x1 −2x2, z3(x) = −x1 + 2x2) sc x1 + x2 ≤7 2x1 ≤3 2x2 ≤7 x1 ≥0, x2 ≥0 uploads/Management/ cours-1-optimisation-multiobjectif 1 .pdf