Mathématiques 3

Optimisation des Fonctions de Plusieurs Variables

Chapitre 1
Dénition d'un programme
d'optimisation

Stéphan Sémirat
[Link]@[Link]
Chapitre 1 : Dénition d'un programme d'optimisation

1. Introduction

2. Composantes d'un programme d'optimisation

a. Quoi chercher ? Les variables décisionnelles

b. Où chercher ? Le domaine

c. Comment chercher ? Le critère

3. Résolution

1
1. Introduction
Une décision rend compte d'un choix parmi un ensemble de
d'alternatives possibles.
Exemple
ˆ Je choisis de faire des études d'éco-gestion, plutôt que des études de

psychologie, de droit, ....

ˆ Je choisis de partir en vacances en Ardèche, plutôt qu'en Bretagne,

dans la Drôme, ...

ˆ Je choisis de ne pas sortir ce soir, plutôt que de sortir.

ˆ Je choisis de me vacciner, plutôt que de ne pas me vacciner.

ˆ Je choisis de créer mon entreprise de vestes polaires à Grenoble

(plutôt qu'à Marseille, Shangaï....) puis je choisis d'installer mon

atelier de production de vestes polaires à Voiron (plutôt qu'à

Grenoble, Valence, Lyon ...), puis je choisis de produire 1500 vestes

polaires (plutôt que 1000, 500, 1453, ...), ...

2
Parmi les possibilités, qu'est-ce qui guide le décideur vers une
décision plutôt qu'une autre ?
Une hypothèse est qu'une décision résulte d'un calcul
d'optimisation : parmi toutes les possibilités (le domaine des
possibles), la décision maximise un certain critère.
Dans ce cours, nous allons apprendre à identier puis résoudre ce
type de calcul.

3
Exercice
Faire l'exercice 1 du cours 1 sur moodle

[Link]

4
2. Composantes d'un programme
d'optimisation
Dénition
Un programme d'optimisation est identié par trois
composantes :
(1) La nature de la décision à prendre
(2) Un ensemble de décisions admissibles
(3) Un critère permettant de classer les décisions admissibles

5
Les trois composantes d'un programme d'optimisation se
formalisent par des objets mathématiques.
Chaque composante permet de répondre de manière précise à un
aspect du problème posé par la décision à prendre.
ˆ Nature de la décision : quoi chercher ?
ˆ Ensemble des décisions admissibles : où chercher ?
ˆ Critère : comment chercher ?
Une fois ces éléments correctements identiés, les mathématiques
sont utilisées pour trouver la meilleure décision.

6
Exercice
Faire l'exercice 2 du cours 1 sur moodle

[Link]

7
2. Composantes d'un programme
d'optimisation
a. Quoi chercher ? Les variables
décisionnelles
Dénition
Les variables décisionnelles représentent la nature de la décision.
On les note en général x1 , x2 , . . .

Chaque valeur (x1 , x2 , . . .) de l'ensemble des variables représente

une possibilité pour la décision à prendre.

8
Exemple
Supposons qu'on s'intéresse à certains aspects de l'emploi du temps
hebdomadaire d'un étudiant cherchant à maximiser ses chances de
réussite en L2.
Ces aspects sont décrits par les variables suivantes :
ˆ x1 : représente la quantité hebdomadaire d'heures consacrées
aux études ;
ˆ x2 : représente la quantité hebdomadaire d'heures consacrées
aux activités sociales (sorties, soirées, ...) ;
ˆ x3 : représente la quantité hebdomadaire d'heures consacrées
aux activités extra-scolaires (sports, associations, ....).
Par exemple, le triplet (x1 , x2 , x3 ) = (25, 15, 6) représente la
décision de consacrer, sur une semaine :
25 heures aux études, 15 heures aux activités sociales et 6 heures
aux activités extra-scolaires.
9
2. Composantes d'un programme
d'optimisation
b. Où chercher ? Le domaine
Dénition
Le domaine est l'ensemble des valeurs admissibles des variables.
Dénition
Une valeur adminissible est une valeur pour chacune des
variables, telle toutes les contraintes de la situation sont satisfaites
en ces valeurs des variables.
Dénition
Les contraintes du programme sont des égalités ou des inégalités
portant sur les variables décisionnelles :
g1 (x1 , x2 , . . .) = b, g2 (x1 , x2 , ...) ≤ b, g3 (x1 , x2 , ...) ≥ b, ...
où les gi (x1 , x2 . . . , ) sont des expressions faisant intervenir les
variables décisionnelles x1 , x2 , . . .

10
Exemple (suite)
Si x1 , x2 , x3 représentent les quantité hebdomadaire d'heures
qu'un étudiant consacre à ses études, aux activités sociales et aux
activités extra-scolaire, des contraintes de la situation peuvent
être :
ˆ une semaine dure 7 × 24 = 168 heures :
x1 + x2 + x3 ≤ 7 × 168
ˆ l'étudiant a 30h de cours obligatoires par semaine : x1 ≥ 30
ˆ l'étudiant est inscrit à un club de sport à 6h/semaine : x3 ≥ 6
ˆ il y a 12h par jour incompressibles (sommeil, transports, job
étudiant, ...) : x1 + x2 + x3 + 7 × 12 ≤ 168
ˆ contraintes de positivité : x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
ˆ ...

11
Exemple (suite)
Le domaine est alors représenté par l'ensemble des valeurs de
(x1 , x2 , x3 ) satisfaisant simultanément les 7 contraintes :



x1 + x2 + x3 ≤ 168


x1 ≥ 30



D : x3 ≥ 6


x1 + x2 + x3 + 84 ≤ 168






x ≥ 0, x ≥ 0, x ≥ 0
1 2 3

12
Exercice
Si le domaine est


x1 + x2 + x3 ≤ 168




x1 ≥ 30



D: x3 ≥ 6


x1 + x2 + x3 + 84 ≤ 168






x ≥ 0, x ≥ 0, x ≥ 0
1 2 3

1. La valeur (x1 , x2 , x3 ) = (50, 20, 10) est-elle admissible ?

Et la valeur (x1 , x2 , x3 ) = (20, 20, 20) ?

2. Quelle est le nombre maximal d'heures pouvant être

consacrées aux études ( x1 ) ?

3. Peut-on déterminer, à partir du domaine, les valeurs

(x∗1 , x∗2 , x∗3 ) maximisant la réussite de l'étudiant en L2 ?

13
2. Composantes d'un programme
d'optimisation
c. Comment chercher ? Le critère
Dénition
Le critère d'une situation est une mesure permettant de dire si une
valeur admissible est meilleure qu'une autre.
Il est modélisé par la fonction objectif du programme.
Cette fonction, disons f , associe à toute valeur admissible
(x1 , x2 , . . .) des variables, une valeur f (x1 , x2 , . . .).
La fonction doit être telle que si A = (x1 , x2 , . . .) et
B = (x′1 , x′2 , . . .) représentent deux valeurs admissibles, alors :

A est meilleure que B si et seulement si f (A) > f (B).

14
Exemple
Soit un programme à deux variables x1 et x2 , et dont la fonction
objectif est dénie par
x1
f (x1 , x2 ) = .
x2
Comparons les deux décisions représentées par
A = (30, 20) et B = (25, 50).
On a :
20 = 1.5 et f (25, 50) = 50 = 0.5 donc f (A) > f (B).
f (30, 20) = 30 25

Donc f est telle que la décision A est meilleure que la décision B .

Cette fonction f est censée rendre compte de la préférence du
décideur pour la décision A plutôt que la décision B .

15
Exemple (suite)
L'objectif de réussite d'un étudiant de L2 selon x1 (h études), x2 (h
sociales) et x3 (h extra) pourrait être mesuré par :
f (x1 , x2 , x3 ) = −4(x1 − 60)2 − (x2 − 20)2 − (x3 − 20)2 .

Cette fonction est :

selon x1 , croissante lorsque x1 ≤ 60, puis décroissante,
selon x2 , croissante lorsque x2 ≤ 20, puis décroissante,
selon x3 , croissante lorsque x3 ≤ 20, puis décroissante.
Elle atteint donc son maximum en (x1 , x2 , x3 ) = (60, 20, 20),
qui n'est pas une valeur admissible sur le domaine D déni
précedemment (x1 + x2 + x3 + 84 ≤ 168 n'est pas satisfaite).
La résolution du programme consiste à trouver la valeur (x1 , x2 , x3 )
maximisant f parmi les valeurs admissibles.

16
Remarque
Si le critère d'une situation vise à minimiser une certaine quantité
f , on peut toujours modéliser la situation à travers un programme
de maximisation, en prenant pour critère −f .
En eet, le minimum de f est atteint au maximum de −f .

17
3. Résolution
Notation
Un programme de maximisation à deux variables et trois

contraintes (dont deux contraintes de positivité) se note :

max f (x1 , x2 )
(x
(1 ,x2 )
g(x1 , x2 ) ≤ b
s.c.
x1 ≥ 0, x2 ≥ 0

L'abbréviation  s.c. signie  sous contrainte .

La plupart des programmes que nous résoudrons dans ce cours
auront cette forme.

18
Dénition
La résolution d'un programme de maximisation, de variables x1 , x2 ,
. . ., de fonction objectif f et de domaine D, consiste à déterminer
le maximum de la fonction f parmi les valeurs du domaine.
La valeur admissible maximisant f , en général notée
x∗ = (x∗1 , x∗2 , . . .)

est appelée solution du programme .

19
Exercice
Faire l'exercice 3 du cours 1 sur moodle

[Link]

20
À retenir

contrainte, p. 10 5
critère, p. 14 solution du programme, p. 18
domaine, p. 10 valeur adminissible, p. 10
fonction objectif, p. 14 variable décisionnelle, p. 8
programme d'optimisation, p.