UNIVERSITÉ SIDI MOHAMED BEN ABDELLAH

ECOLE NATIONALE DES SCIENCES APPLIQUÉES FÈS ENSAF

Optimisation
Filières : GI
Pr : Mhamed SAYYOURI
[Link]@[Link]

Année universitaire 2024-2025 1

ENSAF Informations générales sur le module

❑ Processus stochastique et Optimisation

▪ 2 éléments du module :

o Processus stochastique (24H de cours et TD)

o Optimisation (24H de cours, TD et TP)

2
ENSAF Optimisation
❑ Introduction à l’optimisation
• Définition et importance de l'optimisation
• Applications de l'optimisation dans divers domaines
• Types de problèmes d'optimisation

❑ Optimisation Combinatoire
• Complexité des problèmes Combinatoires
• Méthodes de résolution exactes et approchées

❑ Optimisation métaheuristique
• Classifications des Métaheuristique

• Métaheuristiques à solution unique

• Métaheuristiques à population de solution

3
ENSAF Introduction à l’optimisation
❑ Définition
▪ Euler dit : « Il n’y a rien au monde qui ne se réalise sans la volonté de
minimiser ou maximiser quelque chose »

L'optimisation est une branche des mathématiques et de l'informatique, en tant que disciplines,
cherchant :
➢ à modéliser,
➢ à analyser et
➢ à résoudre analytiquement ou numériquement
les problèmes réels :
➢ qui consistent à déterminer quelles sont la ou les solutions (inconnues) satisfaisant un
objectif quantitatif tout en respectant d'éventuelles contraintes.
➢ Cela revient à résoudre un problème d'optimisation.
4
ENSAF Introduction à l’optimisation
❑ Domaine d’utilisation
L'optimisation est omniprésente dans la vie quotidienne et dans divers domaines, où elle vise à maximiser ou
minimiser des objectifs sous certaines contraintes:
➢ Optimisation des itinéraires de transport : Les applications de navigation comme Google Maps utilisent
des algorithmes d'optimisation pour trouver l'itinéraire le plus rapide ou le plus court entre deux points,
en tenant compte de la circulation, des travaux et d'autres contraintes.
➢ Gestion financière et investissements : Les investisseurs cherchent à maximiser leurs rendements tout en
minimisant les risques en choisissant des portefeuilles d'investissements optimaux en fonction de leurs
objectifs et de leur tolérance au risque.
➢ Planification de la production dans les usines : Les fabricants optimisent les processus pour maximiser la
production tout en minimisant les coûts liés aux matériaux, à la main-d'œuvre et aux délais.
➢ Optimisation énergétique : Les systèmes de gestion de l'énergie dans les bâtiments cherchent à minimiser
la consommation d'énergie tout en maintenant un confort optimal pour les occupants.

5
ENSAF Introduction à l’optimisation
❑ Domaine d’utilisation

➢ Planification des emplois du temps : Les écoles, universités et entreprises optimisent les emplois du
temps pour minimiser les conflits d'horaires, maximiser l'efficacité du travail et satisfaire les
préférences des utilisateurs.
➢ E-commerce et tarification dynamique :Les plateformes d'achat en ligne optimisent leurs prix en temps
réel en fonction de la demande, de la concurrence et du comportement des consommateurs pour
maximiser les ventes et les profits.
➢ Conception des réseaux de télécommunications : Les opérateurs de réseaux cherchent à maximiser la
couverture réseau et à minimiser les coûts d'installation et d'exploitation tout en respectant les
contraintes d'infrastructure.
➢ Optimisation des ressources humaines : Les entreprises utilisent des techniques pour allouer le
personnel de manière optimale, réduire les coûts, maximiser la productivité et améliorer la satisfaction
des employés.
6
ENSAF Introduction à l’optimisation
❑ Formulation
➢ Un problème d'optimisation est un modèle mathématique (formel) d'un problème réel.
➢ L'objectif est de minimiser (ou maximiser) une fonction objectif sous des contraintes :

➢ Formulation :

7
ENSAF Introduction à l’optimisation
❑ Quelques définitions de base en optimisation

1. Variables de décision: Les variables de décision représentent les informations inconnues

dans un problème d'optimisation.

• Vecteur X : x1,x2,x3,...,xn

• Domaines des variables

2. Contraintes
Une contrainte est une condition d'un problème d'optimisation que les solutions doivent
satisfaire.

8
ENSAF Introduction à l’optimisation
❑ Quelques définitions de base en optimisation

3. Espace de recherche
Un espace de recherche est l'ensemble de tous les points possibles d'un problème d'optimisation
qui satisfait toutes les contraintes.

4. Solution réalisable
•Une solution réalisable x′ est un membre d'un ensemble
de solutions possibles.
•Elle se trouve dans l'ensemble qui satisfait toutes les
contraintes

9
ENSAF Introduction à l’optimisation
❑ Quelques définitions de base en optimisation
4. Fonction objectif
La fonction objectif est une équation mathématique écrite en fonction des variables de décision.
Permet de mesurer la qualité d'une solution donnée x′ pour un problème donné.
L'objectif est de minimiser (ou maximiser) cette fonction.

Soit

Un problème de minimisation peut être noté :

Transformation d'un problème de maximisation en problème de minimisation :

10
 ENSAF Introduction à l’optimisation
❑ Quelques définitions de base en optimisation

6. Optimum global (Solution optimale): Est une solution réalisable qui donne la valeur maximale
(minimale) de la fonction objectif dans tout l'espace de recherche.

7. Optimum local: Est une solution réalisable qui donne la valeur maximale (minimale) de la
fonction objectif dans le voisinage de cette solution.

11
 ENSAF Introduction à l’optimisation
❑ Quelques définitions de base en optimisation

8. Valeur optimale : Est la valeur minimale (ou maximale) de la fonction objectif sur toute
la région réalisable d'un problème d'optimisation.

12
ENSAF Introduction à l’optimisation
❑ Illustration graphique
Voici une illustration de l'optimisation montrant des minima et maxima locaux pour une fonction
représentative f(x)=sin(x)+0.1x.

Les points rouges indiquent

les minima locaux et les
points verts montrent les
maxima locaux.

13
ENSAF Introduction à l’optimisation

Exemple : Une entreprise fabrique des composants pour ordinateur.

Pour une quantité x, exprimée en milliers de composants, le coût total en milliers d'euros est :
C(x) = 0,2x^2 + 24x + 20 avec x∈[0;30]
La recette est alors égale à : R(x)=30x
Le bénéfice est la différence entre la recette et le coût total.
Objectif : Déterminer le bénéfice maximal et le nombre de composants correspondants à produire.

14
ENSAF Introduction à l’optimisation
❑Types des PO

Les problèmes d'optimisation peuvent être classés selon les critères suivants :

➢ Le type de contraintes

➢ La nature des variables de décision

➢ La structure physique du problème

➢ La nature des équations impliquées

➢ La nature déterministe du problème

➢ Le nombre d'objectifs

➢ ... etc

15
ENSAF Introduction à l’optimisation
❑Types des PO

16
ENSAF Introduction à l’optimisation
❑Types des PO
Les problèmes d'optimisation peuvent être :
➢ Déterministes ou stochastiques
• Problèmes d'optimisation déterministes : Les données du modèle sont connues avec
précision et ne supposent aucune probabilité ou incertitude.
• Problèmes d'optimisation stochastiques : Modèles qui ont un caractère aléatoire, pouvant
inclure soit des fonctions objectifs aléatoires soit des contraintes aléatoires.
Exemple de PO déterministe : la planification de la production dans une usine. L'objectif est de
minimiser les coûts de production tout en satisfaisant une demande fixe et connue à l'avance.
•Fonction objectif : Min C(x)=cx+f, où c est le coût unitaire, x est le nombre d'unités produites, et f est un
coût fixe.
•Contraintes : La production doit satisfaire la demande D, telle que x≥D, et respecter des limites de capacité.

Dans ce problème, toutes les données (coûts, demande, capacité) sont connues avec certitude.
17
ENSAF Introduction à l’optimisation
❑Types des PO
Exemple de PO stochastique : Prenons le même problème de planification de la production, mais
avec une demande incertaine qui suit une distribution de probabilité (par exemple, une
distribution normale avec une moyenne et un écart type donnés). L'usine doit minimiser ses
coûts de production tout en satisfaisant cette demande incertaine.
•Fonction objectif : Minimiser l'espérance des coûts totaux, par exemple E[C(x,D)], où D est une
variable aléatoire représentant la demande.
•Contraintes : La production doit satisfaire la demande avec une certaine probabilité (par
exemple, P(x≥D)≥0.95.

Dans ce cas, l'optimisation tient compte de l'incertitude en modélisant les données comme des variables
aléatoires et utilise des techniques spécifiques pour prendre des décisions robustes face à ces incertitudes.

18
ENSAF Introduction à l’optimisation
❑Types des PO
➢ Statiques et dynamiques :
• Problèmes d'optimisation statiques : La fonction objectif et les contraintes ne changent pas
avec le temps.
• Problèmes d'optimisation dynamiques : La fonction objectif ou les contraintes changent avec
le temps.
Elle montre également une formulation générale des problèmes d'optimisation dynamique :

19
ENSAF Introduction à l’optimisation
❑Types des PO
Exemple : PO statique
•Fonction objectif : Minimiser C(x)=cx+s où ccc est le coût par unité produite, x est la quantité
produite, et s est le coût de stockage.
•Contraintes : Capacité maximale de production, disponibilité des matières premières.

Exemple : PO dynamique
•Fonction objectif : Minimiser les coûts sur une période avec des fonctions dépendant du temps
C(x,t)=c(t)x+s(t).
•Contraintes : Capacité qui peut changer selon les périodes de maintenance ou d'autres
contraintes de production évolutives.

Cet exemple montre comment la prise en compte du facteur temps rend le problème dynamique,
modifiant la façon de trouver une solution optimale. 20
ENSAF Introduction à l’optimisation
❑Classification des méthodes d’optimisation

21
ENSAF Introduction à l’optimisation
❑Classification des méthodes d’optimisation
Parmi les méthodes d’optimisation on trouve aussi :
➢ Méthodes déterministes : Pour les mêmes entrées, ils produisent toujours la même sortie, en
passant toujours par la même séquence d'états d'exécution.

➢ Méthodes stochastiques : Ils utilisent le caractère aléatoire comme stratégie (par exemple, via
des décisions probabilistes), ce qui peut entraîner des variations de sortie pour les mêmes
entrées.

22
ENSAF Introduction à l’optimisation
❑Classification des méthodes d’optimisation
➢ Méthodes à objectif unique : Ces méthodes cherchent
à trouver la meilleure solution correspondant à la
valeur optimale d'une fonction objectif unique, notée
minf(x). Il existe une solution optimale unique qui
maximise ou minimise la fonction donnée.

➢ Objectif multiple : Ces méthodes considèrent plusieurs objectifs,

souvent conflictuels, notés minf1(x) et minf2(x), par exemple. Il
n'existe généralement pas de solution optimale unique. Au lieu de
cela, on recherche un ensemble de solutions dites Pareto-optimales
où aucune amélioration de l'un des objectifs ne peut être obtenue
sans dégrader un autre objectif.
23
ENSAF Introduction à l’optimisation
❑Classification des méthodes d’optimisation
➢ Optimisation unimodale : Ces méthodes cherchent à trouver
une solution globalement optimale pour un problème donné.
Le graphique montre un cas où il existe un minimum
global, et la méthode ignore les minima locaux pour se
concentrer sur la meilleure solution possible.

➢ Optimisation multimodale : Ces méthodes visent à

identifier un ensemble de bonnes solutions plutôt qu'une
seule solution optimale. Le graphique illustre plusieurs
solutions à intérêt, ce qui permet d'explorer différents
minima locaux tout en cherchant à maintenir un bon
compromis parmi les solutions.

24
ENSAF Introduction à l’optimisation
❑processus d'optimisation

Le processus d'optimisation
passe par quatre étapes
principales :

➢ Modélisation : Il s'agit de convertir un problème réel en un modèle mathématique en identifiant les

variables, les contraintes et l'objectif.
➢ Résolution : Utilisation de méthodes analytiques ou numériques pour trouver la (ou les) solution(s)
optimale(s) du modèle.
➢ Interprétation : Analyse des résultats obtenus pour évaluer leur pertinence et leur validité par rapport au
problème initial.
➢ Mise en œuvre : Application de la solution optimale dans le contexte réel du problème. 25
ENSAF Introduction à l’optimisation
❑ Résolution d'un problème d'optimisation
La résolution d'un problème d'optimisation (PO) se fait selon deux approches principales :
1.Résolution géométrique : Utilisation de la représentation graphique des contraintes pour
visualiser et résoudre le problème d'optimisation.
2.Résolution algorithmique : Utilisation d'une méthode d'optimisation algorithmique. Le choix de
la méthode dépend de :
➢ La nature de la fonction objectif f, sa régularité (continuité, dérivabilité), ses propriétés
spécifiques (parité, convexité) et la connaissance de voisinages de ses extrema.
➢ Les contraintes qui caractérisent l'ensemble D des points admissibles (réalisables).

Ces approches permettent de choisir la meilleure manière d'aborder et de résoudre un

problème d'optimisation selon sa complexité et ses caractéristiques spécifiques

26
ENSAF Introduction à l’optimisation
❑ Méthodes d'optimisation

27
ENSAF Introduction à l’optimisation
❑ Méthodes d'optimisation

28
ENSAF Introduction à l’optimisation
❑Modélisation d’un PO
Exemple : Un fabricant souhaite vendre des unités d'un article à trois magasins (T1, T2 et T3).
Il dispose de deux entrepôts (A et B) pour l'envoi. L'entrepôt A contient 5 unités et l'entrepôt B
en contient 10. Les demandes des magasins T1, T2 et T3 sont respectivement de 8, 5 et 2 unités.
Les coûts de transport d'une unité de chaque entrepôt vers chaque magasin sont indiqués dans
le tableau.
T1 T2 T3
A 1 2 4
B 3 2 1
Comment il faut transporter les unités pour être le plus économique passible ?
Les étapes proposées pour résoudre ce problème sont :
[Link] et bien comprendre l'exercice.
[Link]éliser le problème sous forme d'un problème d'optimisation.
29
ENSAF Introduction à l’optimisation
❑Modélisation d’un PO
Pour la modélisation d'un problème d'optimisation, il faut bien lire l'exercice pour :
➢ comprendre la problématique.
➢ Identifier les données connues.
➢ Identifier les données inconnues.
➢ Déterminer le résultat demandé (la solution).
➢ Définir notre modèle comme un problème d'optimisation.
➢ Ressortir les concepts du modèle, notamment :
• Les variables.
• Leurs domaines.
• Les contraintes.
• L'objectif.

30
ENSAF Introduction à l’optimisation
❑Modélisation d’un PO
Problématique : Il s'agit d'un problème de transport.
Les données connues :
• La capacité de stockage des entrepôts.
• Les quantités demandées par les magasins.
• Le coût de transport entre les entrepôts et les magasins.
Les données inconnues :
• Quelles sont les quantités transportées des entrepôts vers les magasins ?

L'objectif : Trouver les quantités transportées des entrepôts vers les magasins qui minimisent le
coût de transport tout en respectant la demande des magasins et la capacité des entrepôts (les
contraintes).

31
ENSAF Introduction à l’optimisation
❑Modélisation d’un PO
Étape 1 : Déterminer les variables de décision et les représenter de manière algébrique.
Dans ce cas :
Xi : numéro d'unités transportées de chaque entrepôt à chaque magasin
X1: nombre d'unités transportées de l'entrepôt A au magasin T1
X2: nombre d'unités transportées de l'entrepôt A au magasin T2
X3: nombre d'unités transportées de l'entrepôt A au magasin T3
X4: nombre d'unités transportées de l'entrepôt B au magasin T1
X5 : nombre d'unités transportées de l'entrepôt B au magasin T2
X6: nombre d'unités transportées de l'entrepôt B au magasin T3

Étape 2 : Déterminer la fonction objectif :

Minimiser 32
ENSAF Introduction à l’optimisation
❑Modélisation d’un PO

Étape 1 : Déterminer les contraintes et les formuler comme équation ou inéquations

dépendants des variables de décision. Ces contraintes sont déduites de la disponibilité d'unités

qu'il y a dans chaque entrepôt de même que la demande de chaque magasin :

➢ Disponibilité dans l'entrepôt A : X1+X2+X3=5

➢ Disponibilité dans l'entrepôt B : X4+X5+X6=10

➢ Demande du magasin T1 : X1+X4=8

➢ Demande du magasin T2 : X2+X5=5

➢ Demande du magasin T3 : X3+X6=2

33
ENSAF Introduction à l’optimisation
❑Modélisation d’un PO
On obtient le problème d'optimisation suivant :

Minimiser

La nature de ce PO : c'est un PO linéaire.

Sa représentation géométrique est un polygone. 34
ENSAF Introduction à l’optimisation
❑Modélisation d’un PO
La solution optimale obtenue en utilisant la méthode du simplexe est la suivante :
Quantités transportées :
• X1=5 (5 unités de l'entrepôt A au magasin T1)
• X2=0 (0 unités de l'entrepôt A au magasin T2)
• X3=0 (0 unités de l'entrepôt A au magasin T3)
• X4=3 (3 unités de l'entrepôt B au magasin T1)
• X5=5 (5 unités de l'entrepôt B au magasin T2)
• X6=2 (2 unités de l'entrepôt B au magasin T3)
Coût total minimal : 26 unités.
Cette solution satisfait toutes les contraintes de capacité et de demande tout en minimisant le
coût total.
35
ENSAF Introduction à l’optimisation

❑ Exercice 1 :
Un agriculteur voudrait cultiver deux sortes de légumes : des brocolis et des courgettes. Il
pourrait pour cela planter toute sa terre si le besoin nécessite. Il utilise deux sortes d'engrais (A
et B).
➢ Les rendements des brocolis et des courgettes sont de 4 kg/m² et 5 kg/m² respectivement.
➢ Ses stocks sont de 8 litres d'engrais A et 7 litres d'engrais B.
➢ Les besoins en ces matières sont de 2 L/m² d'engrais A et 1 L/m² d'engrais B pour les
brocolis contre 1 L/m² d'engrais A et 2 L/m² d'engrais B pour les courgettes.
L'agriculteur veut produire le maximum de poids de légumes. Il vous demande de l'aider.

36
ENSAF Introduction à l’optimisation
❑ Exercice 1 :

Étapes pour résoudre un problème d'optimisation

[Link] et formulation du problème
➢ Identifier les différentes variables, leurs natures et leurs domaines d'étude
➢ Définir l'objectif du problème
➢ Définir d'éventuelles contraintes
[Link]élisation mathématique du problème
➢ Formuler une fonction mathématique, appelée fonction objectif, qui décrit le problème
➢ Écrire les contraintes sous forme mathématique
[Link] d'une méthode de résolution du problème modélisé
➢ Choisir une méthode d'optimisation adéquate au type du problème
➢ Appliquer la méthode d'optimisation pour résoudre le problème modélisé
37
ENSAF Introduction à l’optimisation
❑ Exercice 1 :
[Link] et formulation du problème
1. Les variables de décisions seront :
➢ x1: Surface pour les carottes (m2) de type réel.
➢ x2 : Surface pour les courgettes (m2) de type réel.
2. Objectif du problème :
➢ L'objectif est de déterminer les valeurs de x1 et x2 qui maximisent le poids total de la
production.
➢ Formuler une fonction f qui calcule le poids total.
3. Contraintes :
➢ Les stocks d'engrais A sont limités à 8 litres.
➢ Les stocks d'engrais B sont limités à 7 litres.
➢ Les surfaces x1 et x2 ont des valeurs positives. 38
ENSAF Introduction à l’optimisation
❑ Exercice 1 :
Modélisation du problème

39
ENSAF Introduction à l’optimisation
❑ Exercice 1 :
Résolution du problème
•Utiliser la méthode de
résolution géométrique
de la programmation
linéaire.
•x1=3 m2, x2=2m2
•Le poids maximal qui
peut être produit sera :
f(x1,x2)=22 kg

40
ENSAF Introduction à l’optimisation

Exercice 2:
Une entreprise met sur le marché un shampoing et un revitalisant pour les cheveux. Les produits
sont vendus en bouteilles de 500 ml.
Une étude de marché a permis de recueillir les informations suivantes :
➢ À chaque mois, le nombre de bouteilles de shampoing vendues sera supérieur ou égal au
nombre de bouteilles de revitalisant vendues.
➢ L'entreprise vendra au maximum 5000 bouteilles de ses nouveaux produits par mois.
➢ L'entreprise vendra au moins 1500 bouteilles de shampoing par mois.
L'équipe qui a mené l'étude de marché a proposé deux combinaisons de prix de vente :
➢ 3,00 $ par bouteille de shampoing et 3,00 $ par bouteille de revitalisant.
➢ 2,80 $ par bouteille de shampoing et 3,10 $ par bouteille de revitalisant.
Question : Quelle combinaison de prix l'entreprise doit-elle choisir pour maximiser ses revenus ?
41
ENSAF Introduction à l’optimisation
Exercice 3:
Pour réaliser des boîtes sans couvercle ayant la forme d'un parallélépipède rectangle, on
dispose d'une feuille en carton de 20 cm par 30 cm. Pour réaliser cette boîte, on découpe aux
quatre coins de la feuille quatre carrés identiques de côté x cm puis on plie le carton suivant les
segments en pointillés sur la figure ci-dessous :
[Link] quel intervalle I se situe la variable x ?
[Link] que le volume V(x) de la boîte obtenu après découpage et pliage est :
V(x)= 4x^3 - 100x^2 + 600x.
1.Étudier les variations de la fonction V sur l'intervalle I et en déduire les dimensions de la
boîte qui possède un volume maximal.

42
Chapitre 1:

43