UNIVERSITE DE DJELFA
Département : Génie mécanique Module : Optimisation
Spécialité : Energétique Dr. HABIB S.H.
Niveau : 2ème Master
[email protected] CHAPITRE 1
MODELISATION
1. Optimisation ? l'on minimise) est appelée indifféremment fonction
coût, objectif ou critère.
L’optimisation vise à résoudre des problèmes où
l’on cherche à déterminer parmi un grand nombre g : ℝn → ℝp est une fonction de plusieurs variables x
de solutions candidates celle qui donne le meilleur ∈ ℝn à valeurs dans ℝp : elle a p composantes et on
rendement. Plus précisément, on cherche à trouver peut écrire
une solution satisfaisant un ensemble de contraintes
g ( x ) = ( g1 ( x ), , g p ( x ))
qui minimise ou maximise une fonction donnée.
L’application de l’optimisation est en expansion chaque fonction gi étant définie sur ℝn et à valeurs
croissante et se retrouve dans plusieurs domaines. dans ℝ. La fonction g représente les contraintes en
Tout problème d’optimisation comporte une inégalité.
étape essentielle : la modélisation mathématique. h : ℝn → ℝq est une fonction de plusieurs variables x ∈
Elle consiste en trois étapes : ℝn à valeurs dans ℝq : elle a q composantes et on peut
écrire
1) Identification des variables de décisions (souvent h( x ) = ( h1 ( x ), , hq ( x ))
désignées par un vecteur x ∈ ℝn) : ce sont les
paramètres sur lesquels l’utilisateur peut agir
chaque fonction hi étant définie sur ℝn et à valeurs
pour faire évoluer le système considéré.
dans ℝ. La fonction h représente les contraintes en
2) Définition d’une fonction coût (appelée fonction égalité.
objectif) permettant d’évaluer l’état du système Précisons maintenant que qu'on entend par
(ex : rendement, performance,. . .). minimisation (ou maximisation) d'une fonction. Soit
C l'ensemble des contraintes, c'est-à-dire par
3) Description des contraintes imposées aux
exemple dans le cas précèdent
variables de décision.
C ={ x n
| g ( x) 0, h( x) = 0 }
Le problème d’optimisation consiste alors à
déterminer les variables de décision conduisant aux On suppose que C est non vide ; un élément x de C
meilleures conditions de fonctionnement du sera dit réalisable.
système (ce qui revient à minimiser ou maximiser la Ce formalisme englobe tous les problèmes
fonction coût), tout en respectant les contraintes d’optimisation, y compris les problèmes de
d’utilisation définies à l’étape 3. maximisation puisque maximiser une quantité
2. Formulation mathématique revient à minimiser son opposé.
Un problème d'optimisation peut s'écrire sous la Exemple de problème d’optimisation
forme générale suivante Déterminer le parallélépipède rectangle de
volume maximal parmi ceux dont la surface
minimiser f ( x) extérieure vaut 6.
g x 0 ou g x 0
( ) ( ) En introduisant a, b et c, les longueurs des côtés
h( x ) = 0 du parallélépipède, on se ramène à la résolution du
x n problème
où, f : ℝn → ℝ est une fonction de plusieurs variables
(x = (x1; … ; xn)) à valeurs réelles. Cette fonction (que
Nom : ………………………………………………………………………… Prénom : ……………………………………………………………………
max V ( a, b, c) = abc La fabrication d’un produit consomme des
ressources. Le produit A requiert 2 unités du
ab + ac + bc = 3
a 0, b 0, c 0 composant et 3 minutes de temps. Le produit B
requiert 1 unité du composant et 4 minutes de
Il s’agit donc d’un problème d’optimisation dans temps.
3
ℝ sous contrainte. Il faut stocker les produits fabriqués durant la
semaine. L’entrepôt a une capacité de 700 produits.
3. Remarques
▪ Avant d’entreprendre une optimisation, vérifiez Le nombre de produits A ne doit pas excéder le
que cela fait sens pour le problème qu’il s’agit de nombre de produits B de plus de 350 unités.
traiter. Le profit est : 8 $ pour une unité du produit A. 5 $
▪ On peut toujours transformer un problème de pour une unité du produit B.
maximisation en un problème de minimisation 2. Problème de minimisation :
(max f = min - f). Une compagnie possède deux mines de charbon
▪ On peut classifier les problèmes d’optimisation A et B. La mine A produit quotidiennement 1 tonne
suivant le type du domaine admissible pour de charbon de qualité supérieure, 1 tonne de qualité
leurs variables de décision, on parle moyenne et 6 tonnes de qualité inférieure. La mine
d'optimisation continue et d’optimisation B produit par jour 2, 4 et 3 tonnes de chacune des
combinatoire. trois qualités. La compagnie doit produire au moins
90 tonnes de charbon de qualité supérieure, 120
▪ Le type de la fonction de cout (par ex. linéaire, tonnes de qualité moyenne et 180 tonnes de qualité
quadratique, convexe, différentiable ou non- inférieure.
différentiable) a une influence forte sur les
classes de méthodes d’optimisation utilisables. Sachant que le coût de production journalier est
le même dans chaque mine, soit 1000 $, quel est le
▪ La dimension de vecteur de décision x est un nombre de jours de production dans la mine A et
facteur clé à prendre en compte dans le choix dans la mine B qui minimisent le coût de production
d’un algorithme. de la compagnie ?
▪ Le temps nécessaire pour une évaluation de la
4.2 Modélisations des problèmes linéaire à
fonction de coût doit aussi être pris en plusieurs variables
considération.
1. Problème de transport
4. Modélisation linéaire Un constructeur automobile possède trois usines
situées à Paris, Strasbourg et Lyon. Les métaux
4.1 Modélisations des problèmes linéaire à deux
variables nécessaires à la fabrication des automobiles arrivent
dans les ports du Havre et de Marseille. Les quantités
Bien que la réalité soit souvent loin d’être hebdomadaires de métal nécessaires à chaque usine
linéaire, un grand nombre de problèmes peuvent sont respectivement de 400, 300 et 200 tonnes. La
s’écrire sous forme linéaire, soit directement, soit en quantité hebdomadaire qui arrive au Havre est de
première simplification. D’autre part, un très grand 350 tonnes et elle est de 550 tonnes à Marseille. Les
nombre de modèles constituent des extensions de coûts de transport d'un port à une usine sont donnés
programmes linéaires. Sa compréhension est dans le tableau suivant :
essentielle à la compréhension de modèles plus
sophistiqués. Paris Strasbourg Lyon Coûts de
transport
1. Problème de maximisation : Marseille 5 6 3 (en euro par
Le havre 3 5 4 tonne)
Un fabricant assemble deux produits A et B. Les
ressources sont limitées. 1000 unités du composant Le but est de déterminer les poids de métal à
de fabrication. 40 heures de production par semaine. envoyer à chaque usine depuis chaque port afin que :
Nom : ………………………………………………………………………… Prénom : ……………………………………………………………………
▪ Chaque usine reçoive, au moins, la quantité de
métal qu'elle demande ;
▪ Les quantités demandées à chaque port
n'excèdent pas les quantités disponibles ;
▪ Le coût total de transport soit minimum.
2. Problème du découpage On peut prendre n’importe quelle portion de ces
Une entreprise fabrique des meubles à partir des frets. En d’autres termes, on peut choisir de ne pas
plaques de bois. Les plaques ont une longueur de transporter l’intégralité d’un fret. Ecrire le problème
deux mètres et une largeur d’un mètre et dix qui consiste à trouver un chargement de cet avion
centimètres. L’entreprise consomme les plaques en qui maximise le bénéfice sous forme d’un
les découpant longitudinalement. Les besoins de programme linéaire.
l’entreprise sont les suivants : 1000 plaques de 16
Supplément : Comment faire lorsque chaque type de
centimètres, 1200 plaques de 20 centimètres et
fret est composé de palettes de 500 kg ?
1800 plaques de 25 centimètres. Pour satisfaire ses
besoins, l’entreprise utilise cinq plans de découpage 4. Problème de raffinage
dont les caractéristiques sont données ci-dessous : Une raffinerie produit de l’essence e1 (SP98) et e2
(SP95) à partir de 3 composants c1, c2 et c3. Les
limitations sont de :
▪ 30000 barils/jours pour c1,
▪ 20000 barils/jours pour c2,
▪ 10000 barils/jours pour c3.
Certaines proportions doivent être respectées dans
la production de SP95 et SP98 :
L’entreprise cherche à satisfaire les besoins en
▪ un baril de SP95 doit contenir au plus 50% de c1
minimisant les pertes de découpage.
et au moins 10% de c2,
3. Problème de chargement ▪ un baril de SP98 doit contenir au plus 30% de c1,
Un avion-cargo possède trois compartiments au moins 40% de c2 et au moins 50% de c3.
pour le chargement de fret : un à l’avant, un au centre Les prix de vente aux distributeurs par baril sont
et un dernier à l’arrière. Les limites de capacité en de :
poids et en volume sont résumées dans le tableau ▪ 54€ pour le SP95,
suivant : ▪ 66€ pour le SP98.
Les prix d’achat par baril sont de :
▪ 36€ pour le composant c1,
▪ 48€ pour le composant c2,
▪ 60€ pour le composant c3.
Pour des raisons de stabilité de l’avion en vol, le La demande maximum des stations de distribution
chargement doit être équilibré dans chaque est de :
compartiment, c’est-à-dire que, pour les trois ▪ 15000 barils pour le SP95,
compartiments, le chargement doit représenter la ▪ 35000 barils pour le SP98.
même proportion, en poids, de la limite de charge.
Quelle est la structure de production journalière
L’avion a la possibilité de charger les quatre frets
qui maximise la marge d’exploitation.
suivants :
Nom : ………………………………………………………………………… Prénom : ……………………………………………………………………
5. Modélisation non-linéaire devons sélectionner une approche mathématique à
utiliser pour obtenir une réponse. Dans ce chapitre,
Dans cette section, nous décrivons une procédure
les problèmes préciseront l'approche de
générale qui peut être utilisée pour résoudre des
modélisation à utiliser.
problèmes en utilisant la modélisation
mathématique. Nous allons illustrer cette L'étape 3 consiste à formuler le modèle. Nous
procédure, appelée la méthode en 5 étapes, en devons prendre la question présentée à l'étape 1 et
l'utilisant pour résoudre un problème non-linéaire. la reformuler sous la forme sélectionnée à l'étape 2,
L'approche de modélisation mathématique pour afin que nous puissions appliquer la procédure de
la résolution de problèmes se compose de cinq solution. Il est souvent commode de changer les
étapes : noms de variables si l'on se réfère à une approche
de modélisation qui a été décrite à l'aide de noms de
1. Poser la question. variables spécifiques.
2. Sélectionner l'approche de modélisation.
3. Formuler le modèle. L'étape 4 consiste à résoudre le modèle en
4. Résoudre le modèle. utilisant la méthode de résolution identifiée à
5. Répondre à la question. l'étape 2.
L’étape 1 consiste à poser une question. La L'étape 5 consiste à répondre à la question posée
question doit être formulée en termes initialement à l'étape 1. La réponse est valable tant
mathématiques, et cela demande souvent beaucoup que les hypothèses formulées à l'étape 1 restent
de travail pour y parvenir. Dans le processus, nous valables.
sommes tenus de faire un certain nombre
d'hypothèses ou de suppositions sur la façon dont 5.1 Applications
les choses sont réellement. Nous ne devrions pas
avoir peur de deviner à ce stade. Nous pouvons
Problème 1
Un veau pesant 200 kg gagne 1.134 kg par jour et
toujours revenir et faire une meilleure estimation
coûte 145.34 DA par jour à élever. Le prix du marché
plus tard. Avant de pouvoir poser une question en
des veaux est de 1100 DA le kilogramme, mais
termes mathématiques, nous devons définir nos
diminue de 5 DA par jour.
termes. Parcourir le problème et faire une liste de
variables. Inclure les unités appropriées. Ensuite, Quand faut-il vendre le veau ?
faire une liste d'hypothèses sur ces variables.
Inclure toutes les relations entre les variables Problème 2
(équations et inégalités) qui sont connues ou Un constructeur automobile réalise un profit de
supposées. Après avoir fait tout cela, nous sommes 1500 $ sur la vente d'un certain modèle. On estime
prêts à poser une question. Écrire dans un langage que pour chaque tranche de 100 $ de remise, les
mathématique explicite l'objectif de ce problème. ventes augmentent de 15 %.
Notons que les étapes préliminaires d'énumération Quel montant de remise maximisera le profit ?
des variables, des unités, des équations et des
inégalités, et d'autres hypothèses font vraiment Problème 3
partie de la question. Ils encadrent la question. Un déversement de pétrole a encrassé 200 milles
de côtes du Pacifique. La compagnie pétrolière
Les trois points de l'étape 1 (variables, responsable a 14 jours pour nettoyer le rivage, après
hypothèses et objectif) n'ont pas besoin d'être une amende de 10 000 $/jour sera imposée.
complétées dans un ordre particulier. Par exemple, L'équipe de nettoyage locale peut nettoyer cinq
il est souvent utile de déterminer l'objectif au début miles de plage par semaine pour un coût de 500
de l'étape 1. $/jour. Des équipes supplémentaires peuvent être
amenés au coût de 18000 $ plus 800 $/jour pour
L'étape 2 consiste à sélectionner l'approche de
chaque équipe.
modélisation. Maintenant que nous avons un
problème énoncé en langage mathématique, nous
Nom : ………………………………………………………………………… Prénom : ……………………………………………………………………
Combien d'équipes supplémentaires faut-il venir problème. Nous sommes rarement suffisamment
pour minimiser le coût total pour l'entreprise ? sûrs de la véracité de toutes ces hypothèses. Par
conséquent, nous devons examiner dans quelle
Problème 4
mesure nos conclusions sont sensibles à chacune des
Reprenons le problème 1, mais supposons
hypothèses que nous avons formulées. Ce type
maintenant que notre objectif est de maximiser
d'analyse de sensibilité est un aspect important de la
notre taux de profit ($/jour). Supposons que nous
modélisation mathématique. Les détails varient en
possédions déjà le veau depuis 90 jours et que nous
fonction de l'approche de modélisation utilisée, c'est
ayons investi 15000 DA dans ce veau à ce jour.
pourquoi notre discussion sur l'analyse de
Trouver le meilleur moment pour vendre le veau. sensibilité se poursuivra tout au long du reste de ce
chapitre. Nous nous concentrerons ici sur l'analyse
Problème 5 de sensibilité pour des problèmes simples
Reconsidérer le problème 1, mais prenons
d'optimisation à une variable. Dans ce cas, les
maintenant en compte le fait que le taux de
données et les hypothèses sont souvent claires.
croissance du veau diminue à mesure que le veau
Même ainsi, nous devons être critiques. Les données
vieillit. Supposons que le veau sera complètement
sont obtenues par mesure, observation et parfois
développé dans cinq mois.
pure conjecture. Nous devons envisager la
Trouver le meilleur moment pour vendre le veau possibilité que les données ne soient pas précises.
afin de maximiser les profits. Certaines données sont naturellement connues avec
beaucoup plus de certitude que d'autres.
Problème 6
Un quotidien local avec un tirage de 80 000 Il est plus utile d'interpréter les données de la
abonnés envisage d'augmenter son prix sensibilité en termes de changement relatif ou en
d'abonnement. Actuellement, le prix est de 1,50 $ pourcentage, plutôt qu'en termes absolus. Si la seule
par semaine, et on estime que le journal perdrait 5 variable x change d'une quantité ∆x, la variation
000 abonnés si le tarif était augmenté de 0.1 $ par relative de x est donnée par ∆x/x, et le pourcentage
semaine. de variation de x est de 100 ∆x/x. Si la donnée r du
Trouvez le prix d'abonnement qui maximise le modèle élaboré change de ∆r, ce qui entraîne le
profit. changement ∆x dans x ; alors le rapport entre les
changements relatifs est ∆x/x divisé par ∆r/r : en
Soit n = 5000 désigne le nombre d'abonnés laissant ∆r → 0 et en utilisant la définition de la
perdus lorsque le prix de l'abonnement augmente de dérivée, on obtient
0.1 $.
Calculer le prix de souscription optimal p en fonction x / x dx r
→
de n. r / r dr x
Le journal doit-il changer son prix d'abonnement ?
Nous appelons cette quantité limite la sensibilité de
Justifiez vos conclusions.
x à r, et nous la désignerons par S (x, r).
6. Analyse de sensibilité
L'application des procédures d'analyse de
Des questions supplémentaires et des sensibilité requiert un bon jugement. Il n'est
hypothèses alternatives peuvent être traitées en généralement pas possible de calculer les
changeant ce que nous avons fait à l'étape 1 de la coefficients de sensibilité pour chaque paramètre
modélisation. Puisqu'il s'agit d'un problème réel, il y dans le modèle. Nous devons sélectionner les
a un élément de risque impliqué dans l'étape 1. Pour paramètres sur lesquels il existe le plus d'incertitude
cette raison, il est généralement nécessaire d'étudier et effectuer une analyse de sensibilité sur eux.
plusieurs alternatives. Ce processus, appelé analyse L'interprétation des coefficients de sensibilité
de sensibilité, qui est discuté dans cette section. dépend également du degré d'incertitude, la
question fondamentale étant dans quelle mesure
La section précédente décrite l'approche en cinq
notre incertitude sur les données affecte notre
étapes de la modélisation mathématique. Le
confiance dans la réponse.
processus commence par faire des hypothèses sur le
Nom : ………………………………………………………………………… Prénom : ……………………………………………………………………
6.1 Exercices
Exercice 1
Reconsidérons le problème 2.
1. Calculer la sensibilité de votre réponse à
l'hypothèse de 15 %. Considérer à la fois le
montant de la remise et le bénéfice qui en
résulte.
2. Supposons que les remises ne génèrent en
réalité qu'une augmentation des ventes de 10 %
par tranche de 100 $. Quel sera l'effet sur la
remise et les bénéfices optimales ?
3. Dans quelles circonstances une offre de remise
entraînerait-elle une réduction des bénéfices ?
Exercice 2
Reprenons le problème 3
1. Examiner la sensibilité à la vitesse à laquelle une
équipe peut nettoyer le déversement. Tenir
compte à la fois du nombre optimal d'équipages
et du coût total pour l'entreprise.
2. Examiner la sensibilité au montant de l'amende.
Tenir compte du nombre de jours qu'il faudra à
l'entreprise pour nettoyer le déversement et du
coût total pour l'entreprise.
3. La société a déposé un recours au motif que le
montant de l'amende est excessif. En supposant
que le seul but de l'amende est de motiver
l'entreprise à nettoyer le déversement de
pétrole en temps opportun, l'amende est-elle
excessive ?
Exercice 3
Reprenons le problème 6
1. Examiner la sensibilité de votre réponse dans le
problème 6 à l'hypothèse de 5 000 abonnés
perdus. Calculer le taux d'abonnement optimal
en supposant que ce paramètre est 3000, 4000,
5000, 6000 ou 7000.
2. Soit n = 5000 désigne le nombre d'abonnés
perdus lorsque le prix de l'abonnement
augmente de 10 centimes. Calculer le prix de
souscription optimal p en fonction de n, et
utiliser cette formule pour déterminer la
sensibilité S(p, n).
3. Le journal doit-il changer son prix
d'abonnement ?
Nom : ………………………………………………………………………… Prénom : ……………………………………………………………………
