Mathématiques Appliquées à la Gestion

Chapitre 1
Introduction

Doriann Albertin – d’après les documents de Stephan Sémirat

[Link]@[Link]
Dans ce chapitre

1. Notion d’efficacité
a. Faire c’est utiliser
b. Utiliser efficacement
c. Mise en garde
2. Les programmes d’optimisation
a. Motivations
b. Définition
c. Exemples
3. Vers la résolution de programmes
a. Dépasser la liste des cas
b. Notion de contrainte
c. Domaine

1
Vocabulaire

contrainte, 47 programme de minimisation,

critère, 23 24
domaine, 23 solution du programme, 26
fonction objectif, 23 sous contrainte, 25
programme d’optimisation, 24 valeur admissible, 23
programme de maximisation, valeur du programme, 26
23 variable décisionnelle, 23
1. Notion d’efficacité
1. Notion d’efficacité

a. Faire c’est utiliser

Toute activité nécessite d’utiliser des ressources :

• Produire nécessite d’utiliser des facteurs de production

(matières premières, énergie, heures de travail,...).
• Consommer nécessite d’utiliser une somme d’argent ou de
temps.

Même ne rien faire c’est allouer une certaine quantité de temps à

l’activité « ne rien faire ».

3
Il est possible d’utiliser différemment un même stock de ressources
disponibles et d’obtenir ainsi différents résultats.
Par exemple, disposant de 2h avant un examen, je peux :
réviser 1h puis dormir 1h, ou dormir 2h, ou regarder un film, ou
réviser 2h, ou ...

4
 Conséquence A

nA
isatio
Util

Ressources Utilisation B
Conséquence B
disponibles
Util
isat
ion
C

Conséquence C

5
1. Notion d’efficacité

b. Utiliser efficacement
Une utilisation est efficace lorsque les ressources disponibles sont
utilisées de la meilleure façon.

6
Ainsi pour pouvoir identifier une utilisation efficace, il faut disposer
d’une mesure de la qualité des utilisations possibles.
Une utilisation efficace étant alors associée à la plus grande qualité.

7
 Conséquence A :
qualité 10
A
ion
isat
Util
Ressources Utilisation B Conséquence B :
disponibles qualité 5
Util
isat
ion
C

Conséquence C :
qualité 20

L’utilisation C est efficace, les utilisations A et B sont inefficaces.

8
Exemple

Il faut livrer des bateaux neufs

C1 dans des ports P1 et P2 . Chaque
• 100 km

140 km • P1 port P1 et P2 doit réceptionner

• P2 au moins un bateau. Il y a un
45 km
bateau en stock en C1 (chan-
• 100 km tier naval 1) et un autre en C2
C2
(chantier naval 2). Chaque km
parcouru coûte 100 e. Quelles
sont les manières de livrer et leur
coût ?

9
Exemple

Il faut livrer des bateaux neufs

C1 dans des ports P1 et P2 . Chaque
• 100 km

140 km • P1 port P1 et P2 doit réceptionner

• P2 au moins un bateau. Il y a un
45 km
bateau en stock en C1 (chan-
• 100 km tier naval 1) et un autre en C2
C2
(chantier naval 2). Chaque km
parcouru coûte 100 e. Quelles
sont les manières de livrer et leur
coût ?

Livraison A : (C1 → P1 , C2 → P2 ), coût : 20 000 e.

Livraison B : (C1 → P2 , C2 → P1 ), coût : 18 500 e.
9
Exemple (suite)

Coût :
20 000 e
P 2)
→
C2
P 1,
→
(C 1
A:

Euros disponibles
B:
(C
1 →
P2 ,
C2
→
P1 )
Coût :
18 500 e

Si je mesure la qualité de mon choix en termes de moindre coût,

alors l’allocation efficace est la B.

10
1. Notion d’efficacité

c. Mise en garde
Attention toutefois à bien choisir la mesure de l’efficacité d’une
prise de décision.
Efficacité ne veut pas nécessairement dire profit maximum.

11
Exemple
Pour optimiser un trajet à vélo, il ne s’agit pas juste de trouver le
chemin le plus court.

12
2. Les programmes d’optimisation
2. Les programmes d’optimisation

a. Motivations
L’environnement réel est souvent complexe et les paramètres à
prendre en compte dans une décision sont difficilement identifiables.
Dans ce cas, les conséquences d’une décision sont souvent difficiles
à évaluer.

13
Exemple
La mise en place d’automates de prêts dans les bibliothèques
municipales est-elle efficace pour la collectivité afin de maximiser
le bien-être social ?

• Le coût de fonctionnement du service de prêt est réduit — sous

réserve que le coût d’un automate est plus faible que celui d’un
employé.
• L’économie réalisée permet d’utiliser le budget municipal pour
d’autres activités sociales.
• Mais la production de lien social (accueil, assistance, contact
avec les bibliothécaires) est réduite.
• L’utilisation alternative du budget ne permettrait peut-être pas
de compenser cette réduction.

14
De plus, même lorsque les paramètres de la situation sont
clairement identifiés, la recherche d’une meilleure solution peut
s’avérer difficile.

15
Exemple
Je veux aller de Bures à Verrières en passant par Chilly en un
minimum de temps

16
Le formalisme mathématique permet parfois de répondre à ces
difficultés :

• Il impose la transparence des paramètres pris en compte et de

leurs relations.
→ En particulier, les choix faits peuvent être critiquables.
• Il permet l’utilisation d’outils de calculs (algorithmes, ...) pour
déterminer une meilleure solution, même parmi un grand
nombre de possibilités.

17
Toutefois, la modélisation peut s’avérer trop simplificatrice.

→ Il faut souvent trouver un compromis entre simplification du

problème et capacité à le résoudre.

18
2. Les programmes d’optimisation

b. Définition
Exemple

Je dois affecter des travaux

T1 T1 et T2 à des employés E1
• 100 h

140 h • E1 et E2 . Chaque travailleur doit

• E2 effectuer un travail. Le coût
45 h
horaire du travail est 100 e.
• 100 h
T2

19
Exemple

Je dois affecter des travaux

T1 T1 et T2 à des employés E1
• 100 h

140 h • E1 et E2 . Chaque travailleur doit

• E2 effectuer un travail. Le coût
45 h
horaire du travail est 100 e.
• 100 h
T2

On reconnaît ici le problème de transport de bateaux.

Modéliser, c’est expliciter le cadre abstrait qui décrit ces deux
problèmes.

19
L’outil mathématique adapté aux problèmes de décision s’appelle
programme d’optimisation.

20
 Qualité
e atteinte
sibl

Qualité maximum ?
os
np
atio
U tilis

Ressources Utilisation possible Qualité

disponibles atteinte
Util
isat
ion
p os
sibl
e
Qualité
atteinte

Un programme d’optimisation formalise la recherche d’un maximum

parmi un ensemble de possibilités
21
 calcul du
e
résultat
sibl

Maximum obtenu ?
ur p os
vale

Variables appartenant valeur possible calcul du

à un domaine limité résultat
vale
ur po
ssib
le
calcul du
résultat

X = (x1 , x2 , ....) ∈ D Z(X) ∈ R

Rechercher un maximum parmi un ensemble de possibilités, c’est

22
rechercher le maximum d’une fonction sur un domaine.
Définition
Un programme de maximisation est constitué de :

• un ensemble de variables décisionnelles, notées

x1 , x2 , x3 , . . .,
• un domaine, noté D, constitué d’un ensemble de valeurs
admissibles des variables décisionnelles,
• une fonction objectif (ou critère), notée Z, associant à
chaque valeur X ∈ D un nombre réel Z(X) :

Z: D → R
X 7→ Z(X)

Il modélise la recherche d’une valeur, notée X ∗ , maximisant Z

parmi l’ensemble des valeurs admissibles :

X ∗ ? tel que X ∗ ∈ D et pour tout X ∈ D, Z(X ∗ ) ≥ Z(X).

23
On définit de même un programme de minimisation.
Plus généralement, un programme d’optimisation est ou bien
un programme de maximisation ou bien un programme de
minimisation.

24
Notations
Un programme de maximisation se note :

Max Z(X)
s.c. X ∈ D

où s.c. est l’abbréviation de « sous contrainte ».

Un programme de minimisation se note :

Min Z(X)
s.c. X ∈ D

25
Définition
Une valeur X ∗ maximisant (ou minimisant) Z(X) est appelée
solution du programme.
La valeur maximale Z(X ∗ ) du critère, atteinte en X ∗ , est appelée
valeur du programme, et notée Z ∗ .

26
Remarque
Il ne peut y avoir qu’une seule valeur Z ∗ d’un programme, mais
cette valeur peut être atteinte en plusieurs solutions.

Exemple
Max Z(x1 , x2 ) = x1
s.c. x1 , x2 ∈ [0, 1]
a pour valeur Z ∗ = 1
X ∗ = (1, 1), X ∗ = (1, 0), X ∗ = (1, 0.4),... sont solutions
(le programme possède une infinité de solutions)

27
Remarque
Un programme peut ne pas avoir de solution (et dans ce cas, il
n’a pas de valeur non plus).

Exemple
Max Z(x1 , x2 ) = x1
s.c. x1 , x2 ∈ [0, +∞[
n’a pas de solution car le critère Z peut être arbitrairement grand
sur le domaine spécifié.

28
Remarque
Toute solution d’un programme de minimisation
[Min Z(X) s.c. X ∈ D] est aussi solution du programme de
maximisation [Max −Z(X) s.c. X ∈ D].

29
Remarque
Toute solution d’un programme de minimisation
[Min Z(X) s.c. X ∈ D] est aussi solution du programme de
maximisation [Max −Z(X) s.c. X ∈ D].

En effet : pour tout X ∈ D, Z(X ∗ ) ≤ Z(X) si et seulement si

pour tout X ∈ D, −Z(X ∗ ) ≥ −Z(X).

29
Remarque (suite)
De même, toute solution de [Max Z(X) s.c. X ∈ D] est aussi
solution de [Min −Z(X) s.c. X ∈ D].
Ainsi tout problème de décision peut indifféremment être modélisé
par un programme de maximisation ou de minimisation.

30
2. Les programmes d’optimisation

c. Exemples
Reconsidérons le problème de livraison des bateaux.

Il faut livrer des bateaux neufs

C1 dans des ports P1 et P2 . Chaque
• 100 km

140 km •P1 port P1 et P2 doit réceptionner

•P2 au moins un bateau. Il y a un

45 km
bateau en stock en C1 (chan-
• 100 km
tier naval 1) et un autre en C2
C2
(chantier naval 2). Chaque km

parcouru coûte 100 e. Quelles

sont les manières de livrer et leur

coût ?

Nous allons examiner trois manières de modéliser ce problème.

31
Modélisation no 1

Je choisis comme variables les nombres de km parcourus par les

bateaux :
x1 : nombre de km parcouru par le bateau disponible en C1 .
x2 : nombre de km parcouru par le bateau disponible en C2 .

32
Modélisation no 1

Je choisis comme variables les nombres de km parcourus par les

bateaux :
x1 : nombre de km parcouru par le bateau disponible en C1 .
x2 : nombre de km parcouru par le bateau disponible en C2 .
Les valeurs admissibles sont :
100km 100km
(C1 → P1 , C2 → P2 ), soit : (x1 = 100 et x2 = 100).
140km 45km
(C1 → P2 , C2 → P1 ), soit : (x1 = 140 et x2 = 45).
Ainsi le domaine est : D = {(100, 100), (140, 45)}.

32
Modélisation no 1

Je choisis comme variables les nombres de km parcourus par les

bateaux :
x1 : nombre de km parcouru par le bateau disponible en C1 .
x2 : nombre de km parcouru par le bateau disponible en C2 .
Les valeurs admissibles sont :
100km 100km
(C1 → P1 , C2 → P2 ), soit : (x1 = 100 et x2 = 100).
140km 45km
(C1 → P2 , C2 → P1 ), soit : (x1 = 140 et x2 = 45).
Ainsi le domaine est : D = {(100, 100), (140, 45)}.
À 100 euros le km parcouru, le coût du transport est :
100 × x1 + 100 × x2 .

32
Modélisation no 1

Je choisis comme variables les nombres de km parcourus par les

bateaux :
x1 : nombre de km parcouru par le bateau disponible en C1 .
x2 : nombre de km parcouru par le bateau disponible en C2 .
Les valeurs admissibles sont :
100km 100km
(C1 → P1 , C2 → P2 ), soit : (x1 = 100 et x2 = 100).
140km 45km
(C1 → P2 , C2 → P1 ), soit : (x1 = 140 et x2 = 45).
Ainsi le domaine est : D = {(100, 100), (140, 45)}.
À 100 euros le km parcouru, le coût du transport est :
100 × x1 + 100 × x2 .
L’objectif à minimiser est donc Z(x1 , x2 ) = 100x1 + 100x2 .

32
Modélisation no 1 (suite)

Z = 100(100 + 100)
= 20 000
00)
100, 1
=(
, x 2)
(x 1

D = {(100, 100), (140, 45)}

(x
1, x
2) =(
140
, 45)

Z = 100(140 + 45)
= 18 500

33
Modélisation no 2

Je choisis comme variables les numéros de port où livrer les

bateaux
( : (
1 si C1 → P1 1 si C2 → P1
x1 = , x2 = .
2 si C1 → P2 2 si C2 → P2
Le domaine est alors D = {(1, 2), (2, 1)}.

34
Modélisation no 2

Je choisis comme variables les numéros de port où livrer les

bateaux
( : (
1 si C1 → P1 1 si C2 → P1
x1 = , x2 = .
2 si C1 → P2 2 si C2 → P2
Le domaine est alors D = {(1, 2), (2, 1)}.
La fonction objectif
( est : (
10 000 si x1 = 1 4 500 si x2 = 1
Z(x1 , x2 ) = + .
14 000 si x1 = 2 10 000 si x2 = 2

34
Modélisation no 2 (suite)

Z = 10 000 + 10 000
= 20 000
2 )
(1,
x2 )=
(x 1,

D = {(1, 2), (2, 1)}

(x
1, x
2) =(
2, 1)

Z = 4 500 + 14 000
= 18 500

35
Modélisation no 3

Je choisis comme variables les quantités de bateaux parcourant le

trajet Ci → Pj :
x11 : nombre de bateaux parcourant C1 → P1 .
x12 : nombre de bateaux parcourant C1 → P2 .
x21 : nombre de bateaux parcourant C2 → P1 .
x22 : nombre de bateaux parcourant C2 → P2 .
Le domaine est alors :

36
Modélisation no 3

Je choisis comme variables les quantités de bateaux parcourant le

trajet Ci → Pj :
x11 : nombre de bateaux parcourant C1 → P1 .
x12 : nombre de bateaux parcourant C1 → P2 .
x21 : nombre de bateaux parcourant C2 → P1 .
x22 : nombre de bateaux parcourant C2 → P2 .
Le domaine est alors :
D = {(1, 0, 0, 1), (0, 1, 1, 0)}.
La fonction objectif est :
Z(x1 , x2 ) = 10 000x11 + 14 000x12 + 4 500x21 + 10 000x22 .

36
Modélisation no 3 (suite)

Z = 10 000 × 1 +
14 000×0+4 500×0+
, x 22
)= 10 000 × 1 = 20 000
, x 21
, x 12
(x 11
, 1)
0, 0
(1,

D = {(1, 0, 0, 1), (0, 1, 1, 0)}

(x
11 , x
12 , x
(0, 21 , x
1, 1 22 )
=
, 0)

Z = 10 000 × 0 +
14 000×1+4 500×1+
10 000 × 0 = 18 500

37
3. Vers la résolution de
programmes
3. Vers la résolution de
programmes

a. Dépasser la liste des cas

Parmi les modélisations précédentes, aucune n’est a priori meilleure
que les autres.

Modélisation no 1 no 2 no 3
Variables x1 , x2 ∈ R x1 , x2 ∈ {1, 2} x11 , x12 , x21 , x22 ∈ N
nombre de km no de port nombre de bateaux
par bateau (
par bateau par trajet
10 000 si x1 = 1
Objectif Z 100x1 + 100x2 Z= Z = 10 000x11 + 14 000x12
14 000 si x1 = 2
(
4 500 si x2 = 1
+ +4 500x21 + 10 000x22
10 000 si x2 = 2
Domaine D {(100, 100), (140, 45)} {(1, 2), (2, 1)} {(1, 0, 0, 1), (0, 1, 1, 0)}

La situation est assez simple pour calculer la solution dans chaque

cas : il suffit de comparer les coûts Z pour chacun des deux
éléments du domaine.

38
Dans une situation plus complexe, le choix du modèle doit être
pertinent pour permettre sa résolution facilement.
C’est-à-dire pour permettre sa résolution par une machine en un
temps raisonnable.

39
Si on part d’une situation avec 3 chantiers, 3 ports, 1 bateau
disponible par chantier et 1 bateau à livrer dans chaque port, alors
il faut comparer les coûts des 6 cas :
(C1 → P1 , C2 → P2 , C3 → P3 ), (C1 → P1 , C2 → P3 , C3 → P2 ),
(C1 → P2 , C2 → P1 , C3 → P3 ), (C1 → P2 , C2 → P3 , C3 → P1 ),
(C1 → P3 , C2 → P1 , C3 → P2 ), (C1 → P3 C2 → P2 , C3 → P1 ).
C’est encore raisonnable.

40
Une situation analogue avec 20 chantiers et 20 ports compte :

41
Une situation analogue avec 20 chantiers et 20 ports compte :
20 × 19 × . . . × 1 ≃ 2 × 1018 cas.
Même avec un ordinateur puissant, le nombre de cas à évaluer
devient trop important dès que le nombre de chantiers et de ports
devient relativement grand.
On pourrait aussi imaginer plusieurs bateaux disponible par
chantier, plusieurs bateaux à livrer dans chaque port, ce qui
décuplerait le nombre de cas à traiter.

41
La méthode de résolution d’un programme d’optimisation par
évaluation exhaustive des cas possibles n’est pas en général
algorithmiquement efficace.

42
Dans le cours, nous présentons des méthodes évitant l’examen de
l’ensemble des cas possibles.
Ces méthodes reposent sur une description du domaine plutôt
qu’une présentation de la liste de ses éléments.

43
Exemple
x2
•
• •
• • •
• • • •
• • • • •
x1

Un domaine

• Liste des éléments du domaine :

D = {(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (0, 1), (1, 1), (2, 1),
(3, 1), (0, 2), (1, 2), (2, 2), (0, 3), (1, 3), (0, 4)}
• Description du domaine :
D = {x1 , x2 ∈ N | x1 + x2 ≤ 4, x1 ≥ 0, x2 ≥ 0}
44
Exemple (suite)
Selon la manière de considérer le domaine, pour savoir si une
valeur (x1 , x2 ), est dans le domaine :

• à partir de D = {(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (0, 1), (1, 1),
(2, 1), (3, 1), (0, 2), (1, 2), (2, 2), (0, 3), (1, 3), (0, 4)},
il y a 15 conditions à considérer :
(x1 , x2 ) = (0, 0) ou (x1 , x2 ) = (1, 0) ou . . .ou (x1 , x2 ) =
(0, 4) ;
• à partir de D = {x1 , x2 ∈ N | x1 + x2 ≤ 4, x1 ≥ 0, x2 ≥ 0},
il y a 3 conditions à considérer :
x1 + x2 ≤ 4, x1 ≥ 0 et x2 ≥ 0.

Ainsi, la seconde manière est plus performante (et plus

synthétique).

45
3. Vers la résolution de
programmes

b. Notion de contrainte
Plutôt que d’énumérer tous les cas possibles, le domaine peut être
décrit par l’ensemble des contraintes que doit satisfaire une valeur
pour être admissible.

46
Définition
Une contrainte est une relation qui doit être vérifiée par toute
valeur admissible.
Exemple
Un investisseur choisit d’investir un montant x dans une
entreprise.
A priori, x peut prendre toutes les valeurs positives (1 euro, 1
milliard d’euros, ...).
La contrainte de budget de l’investisseur est la relation entre le
montant x et le budget B de l’investisseur : x ≤ B.
Ainsi, pour qu’un montant x soit admissible, il faut que x ≤ B
soit vérifiée.
Si B = 106 , alors 107 ≤ 106 n’est pas vérifiée, donc x = 107 n’est
pas admissible.
47
Astuce : Analyse dimensionnelle

Un bon moyen de vérifier si on a écrit une bêtise est de procéder à

une analyse dimensionnelle de la contrainte : on vérifie que les
unités sont cohérentes.
D’après l’exemple des crêpes, supposons qu’en une heure, on
produit 500 crêpes, au plus 20 heures par jour, et posons x le
nombre de crêpes produites.

48
Astuce : Analyse dimensionnelle

Un bon moyen de vérifier si on a écrit une bêtise est de procéder à

une analyse dimensionnelle de la contrainte : on vérifie que les
unités sont cohérentes.
D’après l’exemple des crêpes, supposons qu’en une heure, on
produit 500 crêpes, au plus 20 heures par jour, et posons x le
nombre de crêpes produites.
x
Soit ≤ 20. Et en remplaçant chaque valeur par son unité :
500
crêpes
crêpes/heure ≤ heures, ce qui est cohérent.

Si on commet une erreur : 500x ≤ 20 par exemple, on obtient

crêpes
heure × heures ≤ crêpes, ce qui n’est pas cohérent.

Attention : ceci permet de détecter certaines erreurs, mais ne

garanti pas forcément que la contrainte est bien écrite !
48
Exemple
Étant donnée des variables binaires x1 , x2 ∈ {0, 1}, la relation

x1 + x2 ≤ 1

est :

• vérifiée par les couples (x1 , x2 ) = (0, 0), (x1 , x2 ) = (0, 1) et

(x1 , x2 ) = (1, 0),
• non vérifiée par (x1 , x2 ) = (1, 1).

Ainsi la valeur (x1 , x2 ) = (1, 1) n’est pas admissible.

Toutefois, les autres valeurs (0, 0), (0, 1), (1, 0) sont-elles
forcément admissibles ?

49
Remarque
Une contrainte considérée isolément permet d’exclure du domaine
les valeurs ne la vérifiant pas.
Elle ne permet pas de rendre admissible les valeurs la vérifiant.

50
Exemple
Un investisseur cherche à placer une somme d’argent. Il dispose
de 100 000e, et peut investir dans deux entreprises. De plus, il
souhaite investir plus dans l’entreprise 2 que dans l’entreprise 1.

51
Exemple
Un investisseur cherche à placer une somme d’argent. Il dispose
de 100 000e, et peut investir dans deux entreprises. De plus, il
souhaite investir plus dans l’entreprise 2 que dans l’entreprise 1.
On modélise la somme à placer dans les entreprises 1 et 2 par les
variables x1 et x2 , avec x1 ∈ [0, +∞[ et x2 ∈ [0, +∞[.
Comme il ne peut investir qu’une quantité positive d’argent, on a
x1 ≥ 0 et x2 ≥ 0.
La contrainte de budget de l’investisseur s’écrit
x1 + x2 ≤ 100 000.
La préférence de l’investisseur pour l’entreprise 2 s’écrit x1 ≤ x2 .
Ces quatre contraintes déterminent les choix possibles pour
l’investisseur.

51
3. Vers la résolution de
programmes

c. Domaine
Chaque contrainte exclut un certain ensemble de valeurs des
variables.
Le domaine est alors constitué des valeurs qui, en considérant
chaque contrainte isolément, ne sont exclues par aucune contrainte.
Toutes les valeurs possibles

Valeurs exclues par

une contrainte
D
Valeurs exclues par

une autre contrainte

Valeurs exclues par

une autre contrainte

52
 D2 D3
D1

Contrainte 1 Contrainte 2 Contrainte 3

Le domaine est ainsi constitué des valeurs vérifiant l’ensemble des

contraintes simultanément, c’est l’intersection des ensembles de valeurs
vérifiées par chacune des contraintes : D = D1 ∩ D2 ∩ . . .

53
Exemple
(
x1 + x2 ≥ 5
Le domaine D : est tel que :
x1 ≥ 0

• (x1 , x2 ) = (2, 3) ∈ D car x1 + x2 = 2 + 3 = 5 ≥ 5 est vérifiée,

et x1 = 2 ≥ 0 est vérifiée.
• (x1 , x2 ) = (1, 6) ∈ D car x1 + x2 = 1 + 6 = 7 ≥ 5 est vérifiée
et x1 = 1 ≥ 0 est vérifiée.
• (x1 , x2 ) = (−1, 6) ∈
/ D car x1 + x2 = −1 + 6 = 5 ≥ 5 est
vérifiée mais x1 = −1 ≥ 0 n’est pas vérifiée.

54
Exemple
Reprenons le problème de transport des bateaux et les 3 modèles
considérés précédemment

C1
• 100 km

140 km • P1
45 km
• P2
•100 km
C2

Modélisation no 1 no 2 no 3
Variables x1 , x2 ∈ R x1 , x2 ∈ {1, 2} x11 , x12 , x21 , x22 ∈ N
nombre de km no de port nombre de bateaux
par bateau (
par bateau par trajet
10 000 si x1 = 1
Objectif Z 100x1 + 100x2 Z= Z = 10 000x11 + 14 000x12
14 000 si x1 = 2
(
4 500 si x2 = 1
+ +4 500x21 + 10 000x22
10 000 si x2 = 2
Domaine D {(100, 100), (140, 45)} {(1, 2), (2, 1)} {(1, 0, 0, 1), (0, 1, 1, 0)} 55
Exemple (suite)
L’expression des contraintes dépend fortement des choix de
modélisation.
Si xi représente le nombre de km par bateau disponible en Ci
(modélisation no 1), alors les valeurs a priori possibles des variables
sont tous les couples (x1 , x2 ) avec x1 ∈ [0, +∞[ et x2 ∈ [0, +∞[.
Les contraintes doivent exclure tous les couples sauf (100, 100) et
(140, 45).
Il semble difficile de caractériser D comme une intersection
d’ensemble de valeurs vérifiant certaines relations entre x1 et x2 .

56
Exemple (suite)
Si xi représente le numéro du port où amener le bateau en Ci
(modélisation no 2), alors les valeurs a priori possibles des
variables sont (1, 1), (1, 2), (2, 1) et (2, 2).
Les contraintes doivent exclure (1, 1) et (2, 2).
Par exemple, le domaine peut être identifié par une unique
relation : x1 + x2 = 3.
Toutefois, cette contrainte est difficilement interprétable dans la
situation, et difficilement généralisable à de nombreux ports,
nombreux chantiers, ...

57
Exemple (suite)
Si xij représente le nombre de bateaux parcourant Ci → Pj
(modélisation no 3), , alors les valeurs a priori possibles des
variables sont (0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1), . . .,
(1, 1, 1, 1) (on trouve 24 = 16 possibilités).
Les contraintes doivent exclure toutes les possibilités sauf
(1, 0, 0, 1) et (0, 1, 1, 0).
Les contraintes suivantes conviennent :

(1) x11 + x12 ≤ 1 soit : au plus 1 bateau doit partir de C1 .

(2) x21 + x22 ≤ 1 soit : au plus 1 bateau peut partir de C2 .
(3) x11 + x21 ≥ 1 soit : au moins 1 bateau doit arriver à P1 .
(3) x12 + x22 ≥ 1 soit : au moins 1 bateau doit arriver à P2 .

58
Exemple (suite)
Le programme d’optimisation du modèle no 3 s’écrit alors :

Min
 100x11 + 140x12 + 45x21 + 100x22


 x11 + x12 ≤ 1,
 x21 + x22 ≤ 1,



s.c. x11 + x21 ≥ 1,

 x12 + x22 ≥ 1,




 x , x , x , x ∈ {0, 1}.
11 12 21 22

59
Exemple (suite)
Le modèle no 3 se généralise facilement à de nombreux ports,
chantiers et bateaux.
Par exemple, avec 20 chantiers, 20 ports, et 1 bateau par
chantier, le domaine contient 20 × 19 × . . . × 1 ≃ 2 × 1018 valeurs
admissibles.
En utilisant la formalisation no 3, le nombre de variable xij est
20 × 20 = 400, et le nombre de contraintes est 40 :

• au plus 1 bateau doit partir de chaque chantier Ci .

(20 contraintes de la forme xi1 + xi2 + . . . + xi20 ≤ 1)
• au moins 1 bateau doit arriver à chaque port Pi .
(20 contraintes de la forme x1j + x2j + . . . + x20j ≥ 1)

C’est un ordre de grandeur de programme d’optimisation

largement acceptable pour être traité de manière algorithmique.
60
Exemple de synthèse

Un menuisier fabrique des chaises, des tables et des buffets.

En complétant l’énoncé (avec des valeurs "inventées" si besoin),
proposer un programme d’optimisation à ce menuisier.

1 Variables décisionnelles ?
2 Fonction objectif ?
3 Contraintes ?

61
Variables décisionnelles

Les variables décisionnelles représentent toujours les choix que

l’agent concerné (ici un menuisier) peut entreprendre.

62
Variables décisionnelles

Les variables décisionnelles représentent toujours les choix que

l’agent concerné (ici un menuisier) peut entreprendre.
Dans le cas présent, le menuisier peut, par exemple, choisir de
fabriquer 6 chaises, 2 tables et 1 buffet. Il est donc naturel de
considérer les variables décisionnelles xC , xT et xB , désignant
respectivement le nombre de chaises, tables et buffets fabriqués par
le menuisier.

62
Variables décisionnelles

Les variables décisionnelles représentent toujours les choix que

l’agent concerné (ici un menuisier) peut entreprendre.
Dans le cas présent, le menuisier peut, par exemple, choisir de
fabriquer 6 chaises, 2 tables et 1 buffet. Il est donc naturel de
considérer les variables décisionnelles xC , xT et xB , désignant
respectivement le nombre de chaises, tables et buffets fabriqués par
le menuisier.
On pourrait ajouter le prix de vente de chaque meuble, et obtenir
trois variables décisionnelles supplémentaires. On supposera ici que
ces prix sont imposés par le marché.

62
Variables décisionnelles

Les variables décisionnelles représentent toujours les choix que

l’agent concerné (ici un menuisier) peut entreprendre.
Dans le cas présent, le menuisier peut, par exemple, choisir de
fabriquer 6 chaises, 2 tables et 1 buffet. Il est donc naturel de
considérer les variables décisionnelles xC , xT et xB , désignant
respectivement le nombre de chaises, tables et buffets fabriqués par
le menuisier.
On pourrait ajouter le prix de vente de chaque meuble, et obtenir
trois variables décisionnelles supplémentaires. On supposera ici que
ces prix sont imposés par le marché.
On pourrait choisir de considérer des variables correspondant aux
quantités de matière première à acheter. Pourquoi pas ! Mais les
quantités produites donnent plus d’information, et représentent plus
62
fidèlement la décision du menuisier.
Fonction objectif

C’est une fonction prenant en argument les variables décisionnelles

xC , xT et xB , calculant une valeur d’utilité. Il faut se poser la
question de ce que l’on souhaite maximiser ou minimiser.

63
Fonction objectif

C’est une fonction prenant en argument les variables décisionnelles

xC , xT et xB , calculant une valeur d’utilité. Il faut se poser la
question de ce que l’on souhaite maximiser ou minimiser. On peut :
• Maximiser le profit.

63
Fonction objectif

C’est une fonction prenant en argument les variables décisionnelles

xC , xT et xB , calculant une valeur d’utilité. Il faut se poser la
question de ce que l’on souhaite maximiser ou minimiser. On peut :
• Maximiser le profit. Max pC xC + pT xT + pB xB

63
Fonction objectif

C’est une fonction prenant en argument les variables décisionnelles

xC , xT et xB , calculant une valeur d’utilité. Il faut se poser la
question de ce que l’on souhaite maximiser ou minimiser. On peut :
• Maximiser le profit. Max 10xC + 30xT + 80xB

63
Fonction objectif

C’est une fonction prenant en argument les variables décisionnelles

xC , xT et xB , calculant une valeur d’utilité. Il faut se poser la
question de ce que l’on souhaite maximiser ou minimiser. On peut :
• Maximiser le profit. Max 10xC + 30xT + 80xB
• Maximiser les recettes. Max rC xC + rT xT + rB xB

63
Fonction objectif

C’est une fonction prenant en argument les variables décisionnelles

xC , xT et xB , calculant une valeur d’utilité. Il faut se poser la
question de ce que l’on souhaite maximiser ou minimiser. On peut :
• Maximiser le profit. Max 10xC + 30xT + 80xB
• Maximiser les recettes. Max rC xC + rT xT + rB xB
• Maximiser le nombre de meubles. Max xC + xT + xB

63
Fonction objectif

C’est une fonction prenant en argument les variables décisionnelles

xC , xT et xB , calculant une valeur d’utilité. Il faut se poser la
question de ce que l’on souhaite maximiser ou minimiser. On peut :
• Maximiser le profit. Max 10xC + 30xT + 80xB
• Maximiser les recettes. Max rC xC + rT xT + rB xB
• Maximiser le nombre de meubles. Max xC + xT + xB
• Minimiser le temps de travail. Min tC xC + tT xT + tB xB

63
Fonction objectif

C’est une fonction prenant en argument les variables décisionnelles

xC , xT et xB , calculant une valeur d’utilité. Il faut se poser la
question de ce que l’on souhaite maximiser ou minimiser. On peut :
• Maximiser le profit. Max 10xC + 30xT + 80xB
• Maximiser les recettes. Max rC xC + rT xT + rB xB
• Maximiser le nombre de meubles. Max xC + xT + xB
• Minimiser le temps de travail. Min tC xC + tT xT + tB xB
• Minimiser l’investissement.

63
Fonction objectif

C’est une fonction prenant en argument les variables décisionnelles

xC , xT et xB , calculant une valeur d’utilité. Il faut se poser la
question de ce que l’on souhaite maximiser ou minimiser. On peut :
• Maximiser le profit. Max 10xC + 30xT + 80xB
• Maximiser les recettes. Max rC xC + rT xT + rB xB
• Maximiser le nombre de meubles. Max xC + xT + xB
• Minimiser le temps de travail. Min tC xC + tT xT + tB xB
• Minimiser l’investissement.
• Minimiser les résidus de matière
première.

63
Fonction objectif

C’est une fonction prenant en argument les variables décisionnelles

xC , xT et xB , calculant une valeur d’utilité. Il faut se poser la
question de ce que l’on souhaite maximiser ou minimiser. On peut :
• Maximiser le profit. Max 10xC + 30xT + 80xB
• Maximiser les recettes. Max rC xC + rT xT + rB xB
• Maximiser le nombre de meubles. Max xC + xT + xB
• Minimiser le temps de travail. Min tC xC + tT xT + tB xB
• Minimiser l’investissement.
• Minimiser les résidus de matière
première.
• ...

63
Contraintes

64
Contraintes

• Contraintes intrinsèques

64
Contraintes

• Contraintes intrinsèques : xC , xT et xB sont des entiers

positifs.
• Contraintes propres au contexte.

64
Contraintes

• Contraintes intrinsèques : xC , xT et xB sont des entiers

positifs.
• Contraintes propres au contexte.
—Temps. tC xC + tT xT + tB xB ≤ ttotal

64
Contraintes

• Contraintes intrinsèques : xC , xT et xB sont des entiers

positifs.
• Contraintes propres au contexte.
—Temps. tC xC + tT xT + tB xB ≤ ttotal
— Profit. pC xC + pT xT + pB xB ≥ pmin

64
Contraintes

• Contraintes intrinsèques : xC , xT et xB sont des entiers

positifs.
• Contraintes propres au contexte.
—Temps. tC xC + tT xT + tB xB ≤ ttotal
— Profit. pC xC + pT xT + pB xB ≥ pmin
— Demande. xC ≤ 12 ; xT ≤ 6 ; xB ≤ 5

64
Contraintes

• Contraintes intrinsèques : xC , xT et xB sont des entiers

positifs.
• Contraintes propres au contexte.
—Temps. tC xC + tT xT + tB xB ≤ ttotal
— Profit. pC xC + pT xT + pB xB ≥ pmin
— Demande. xC ≤ 12 ; xT ≤ 6 ; xB ≤ 5

Les contraintes ne peuvent pas être les mêmes selon ce que l’on
souhaite optimiser. Il est absurde d’imposer un profit minimal si
l’on est déjà en train de maximiser le profit !

64
Contraintes (suite)

— Contrainte de matériaux.
Chaise Table Buffet
Planches 1 3 6
Tasseaux 4 8 2
Quincaillerie 20 16 60
Vernis 1 3 6

65
Contraintes (suite)

— Contrainte de matériaux.
Chaise Table Buffet
Planches 1 3 6
Tasseaux 4 8 2
Quincaillerie 20 16 60
Vernis 1 3 6
• Construire dans les limites d’un stock.
• Ne pas dépasser un certain budget de commande de ma-
tière première.

65
Contraintes (suite)

— Contrainte de matériaux.
Chaise Table Buffet
Planches 1 3 6
Tasseaux 4 8 2
Quincaillerie 20 16 60
Vernis 1 3 6
• Construire dans les limites d’un stock.
• Ne pas dépasser un certain budget de commande de ma-
tière première.
— Diversité : construire au moins un exemplaire de chaque meuble
pour alimenter les réseaux publicitaires.

65
Contraintes (suite)

— Contrainte de matériaux.
Chaise Table Buffet
Planches 1 3 6
Tasseaux 4 8 2
Quincaillerie 20 16 60
Vernis 1 3 6
• Construire dans les limites d’un stock.
• Ne pas dépasser un certain budget de commande de ma-
tière première.
— Diversité : construire au moins un exemplaire de chaque meuble
pour alimenter les réseaux publicitaires.
— ...
65
Résumé du chapitre (1/2)

On modélise un problème de décision à travers un programme

d’optimisation afin de confier aux mathématiques la recherche
d’une meilleure décision.
Si la situation est suffisamment simple, un traitement de tous les
cas possibles peut être envisagé.
Sinon, des méthodes algorithmiques peuvent être utilisées. Nous en
parlerons la semaine prochaine.

66
Résumé du chapitre (2/2)

Un programme d’optimisation est défini par :

• Des variables décisionnelles, notées x1 ,. . .,xn ,

représentant le support des décision.
Une valeur numérique pour chaque variable (x1 = 2, x2 = 0,
. . ., xn = −1) représente une décision possible.
• Un domaine, noté D, représentant les décisions admissibles.
Le domaine peut être décrit par des contraintes : des
relations devant être vérifiées par les valeurs admissibles.
• Une fonction objectif, notée Z, représentant une mesure de
l’efficacité des décisions.
Une décision X est plus efficace qu’une autre décision X ′ si et
seulement si Z(X) > Z(X ′ ).

67