Introduction à la

Recherche Opérationnelle
13UMQ20

ICHEC
Année académique 2017-2018
Table des matières

0.1 Qu'est-ce que la Recherche Opérationnelle ? . . . . . . . . . . . . . . . . . . . . 3

0.2 Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
0.3 Plan du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1 Modélisation 5
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Notion de modèles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Construction d'un modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Dénitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Un autre exemple, le Knapsack problem . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Programmation linéaire 13
2.1 Rappels sur les fonctions linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Dénitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Formes de programme linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Résolution graphique en deux dimensions (Rappels) . . . . . . . . . . . . . . . . 17
2.5 Déduction d'une résolution non graphique . . . . . . . . . . . . . . . . . . . . . 20
2.6 Vers l'algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.7 Les deux phases de l'algorithme du simplexe . . . . . . . . . . . . . . . . . . . . 24
2.7.1 Solutions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.7.2 La Phase 2 de Progression . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.7.3 Cas particuliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.7.4 La Phase 1 d'Initialisation . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.8 Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.8.1 Motivation du problème dual : la recherche d'une borne supérieure sur la
valeur optimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.8.2 Problème dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.8.3 Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.8.4 Construction du dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.8.5 Interprétation économique des variables duales . . . . . . . . . . . . . . . 38
2.8.6 Les écarts complémentaires . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.9 Rappel : Résolutions de systèmes d'équations linéaires . . . . . . . . . . . . . . . 41
2.9.1 Systèmes linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.9.2 Méthode des combinaisons linéaires d'équations . . . . . . . . . . . . . . 42
2.9.3 Erreurs à éviter ! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.9.4 Forme échelonnée d'un système . . . . . . . . . . . . . . . . . . . . . . . 44
2.9.5 La méthode d'élimination de Gauÿ . . . . . . . . . . . . . . . . . . . . . 44
2.9.6 Implémentation de la méthode de Gauÿ . . . . . . . . . . . . . . . . . . . 45
2.10 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

1
3 La gestion des stocks 59
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.2 Rappels sur l'optimisation des fonctions d'une variable . . . . . . . . . . . . . . 60
3.3 Les données des problèmes de gestion des stocks . . . . . . . . . . . . . . . . . . 65
3.4 Le modèle classique de Wilson . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.5 Le "Manufacturing Model" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.6 Un modèle avec rabais lié à la quantité . . . . . . . . . . . . . . . . . . . . . . . 72
3.7 Modèle avec demande aléatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.7.1 Rappels statistiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.7.2 Modèle simple de réapprovisionnement périodique . . . . . . . . . . . . . 78
3.7.3 Stock de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

4 La théorie des graphes 89

4.1 Bref historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.2 Dénitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.3 Encodage d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.4 Le problème de l'arbre couvrant de poids minimum . . . . . . . . . . . . . . . . 95
4.5 Le problème du plus court chemin . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.5.1 Dénition du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.5.2 Principes de programmation dynamique . . . . . . . . . . . . . . . . . . 97
4.5.3 L'algorithme de Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . 100
4.5.4 L'algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

2
Introduction

0.1 Qu'est-ce que la Recherche Opérationnelle ?

Ce cours d'introduction à la recherche opérationnelle (ROPE) est dans l'UFR Méthodes quan-
titatives. Alors, est-ce que c'est un cours de mathématiques ? Oui, mais pas seulement ! On
ne pourrait cloisonner la recherche opérationnelle aux seules mathématiques. En eet, il s'agit
d'une discipline qui est à l'intersection des mathématiques (algèbre, géométrie, algorithmique,
probabilité, logique,...), de l'informatique, de la gestion,...

Voici quelques exemples de questions auxquelles la ROPE s'intéresse :

 Comment organiser de la façon la plus ecace l'ordonnancement de travaux ?
 Comment planier un horaire réalisable et qui satisfait le plus de personnes dans un
hôpital ?
 Dans quel ordre gérer les livraisons d'un coursier an de minimiser la distance parcourue ?
 Comment optimiser les traitements de radiothérapie ?
 Comment gérer les problèmes de gestion de stock ?
 Comment trouver l'implantation la plus stratégique pour une caserne de pompiers ?

Comme on peut le constater via ces questions, le champ des applications est très vaste !

Si on va se renseigner sur wikipédia, on apprend que la ROPE peut être dénie comme l'en-
semble des méthodes, des outils et des techniques qui visent à déterminer une meilleure façon
d'opérer des choix ou d'arriver au meilleur résultat possible pour atteindre un objectif visé.
Elle fait partie des aides à la décision dans la mesure où elle propose des modèles conceptuels
en vue d'analyser et de maîtriser des situations complexes pour permettre aux décideurs de
comprendre et d'évaluer les enjeux et de faire des choix plus ecaces.

0.2 Historique
Dès le 17ème siècle, certains mathématiciens ont tenté de résoudre des problèmes de décision.

Mais c'est pendant la Seconde Guerre Mondiale que cette branche commença à être activement
étudiée dans le but de résoudre des problèmes tels que l'amélioration (optimisation) du trans-
port des vivres, l'implémentation optimale des radars,...

A la n de la guerre, cette branche a continué à se développer de façon très intense grâce à

l'arrivée des ordinateurs, également développés durant la guerre (machines de Turing, Alan
Turing), et de l'algorithme du simplexe (Dantzig, 1947) et est toujours intensivement étudiée
aujourd'hui (il sut de voir le très grand nombre de revues scientiques et de conférences
organisées de par le monde qui lui sont consacrées). Le champ des applications a bien sûr

3
dépassé le cadre militaire, et les techniques de ROPE sont utilisées aujourd'hui, entre autres,
pour :
 gérer les soins de santé dans les hôpitaux,
 organiser les services policiers ou ambulanciers,
 planier des systèmes de livraison,
 gérer la production, les stocks, la distribution de produits,
 concevoir des systèmes de communication,
 concevoir des algorithmes utilisés dans des GPS,
 établir des horaires,
 choisir des politiques d'économie,
 ···

A l'heure actuelle, la plupart des sociétés possèdent un département de ROPE en leur sein an
d'optimiser leur fonctionnement.

0.3 Plan du cours

Il serait impossible ne serait-ce que d'aborder l'ensemble des sujets que recouvre la ROPE.
Nous allons limiter cette introduction à la base des grands chapitres suivants :

1. La modélisation

2. La programmation linéaire

3. La gestion de stock

4. La théorie des graphes

Le but de ce cours est de vous donner les outils nécessaires de base à la ROPE an que vous
soyez capables, en cas de besoin (dans votre mémoire ou parcours professionnel), d'aller chercher
vous-même les réponses aux questions d'optimisation que vous vous poserez.

4
Chapitre 1
Modélisation

1.1 Introduction
Les problèmes traités en ROPE (et donc, dans ce cours) vont au-delà des aspects mathéma-
tiques. Comme vu dans le chapitre d'introduction, le champ des applications des techniques
ROPE est très vaste. On peut résumer les diérentes étapes qu'il convient de franchir an
de, partant d'une situation à optimiser (quel que soit le contexte), parvenir à une solution
satisfaisante de la façon suivante :

1. Formuler le problème : c'est-à-dire réussir à regrouper toutes les informations perti-

nentes dont on a besoin pour comprendre réellement le problème. C'est une étape très
dicile car elle demande de parvenir à bien comprendre les besoins, les objectifs et les
contraintes des diérents professionnels pour/avec qui on travaille. Il s'agit donc de partir
d'une situation de terrain et de retranscrire les informations nécessaires à la probléma-
tisation de la situation. Cette étape ne sera malheureusement pas abordée ici (en eet, le
simple fait de décrire par écrit une situation est déjà une première formulation du pro-
blème).

2. Construire un modèle mathématique qui représente le système étudié. Il s'agit

ici de l'étape de modélisation. C'est-à-dire que, de la formulation du problème obtenue au
point 1, on va la retranscrire dans le langage (abstrait) des mathématiques. Pour cela, on
va utiliser des variables, des équations, des inéquations,... Il s'agit en fait de supprimer le
contexte dans lequel on se trouve pour ne garder que la structure du problème. Il est assez
déroutant de voir que certains problèmes ayant des contextes très diérents se résolvent
de manière identique car ils possèdent une même modélisation. C'est cette étape qui sera
abordée dans ce chapitre.

3. Dériver une solution du modèle. Cette méthode de résolution dépend évidemment de

la modélisation du problème. Dans ce cours nous aborderons des techniques pour résoudre
des problèmes de programmation linéaire, de gestion de stocks et de théorie des graphes.

4. Utiliser les informations provenant de la résolution du modèle pour prendre

une décision.

5
1.2 Notion de modèles
Dénition 1.2.1 Un modèle est une construction qui a pour but de représenter ou reproduire
les caractéristiques et le fonctionnement du système étudié.

L'utilisation d'un modèle est poussée par le fait que l'expérimentation peut être envisageable.
Ces modèles peuvent être concrets (via des maquettes) ou abstraits. Nous nous intéressons à
cette deuxième catégorie.

Un modèle mathématique est constitué de :

 paramètres,
 variables (variables de décisions, d'état, de commande,...),
 contraintes (équations, inéquations,...),
 objectif(s) (fonction qui exprime notre préférence).

1.3 Construction d'un modèle

Nous voyons ici comment construire un modèle. Nous nous basons sur l'exemple suivant :

Exemple : Deux implantations d'une même ranerie distillent du pétrole venant de deux
sources diérentes : l'une en Arabie Saoudite, et l'autre au Vénézuéla.
Chaque baril provenant d'Arabie Saoudite rapporte 0, 3 baril d'essence, 0, 4 baril de kérosène et
0, 2 baril de lubriant. Chaque baril provenant du Vénézuéla rapporte 0, 4 baril d'essence, 0, 2
baril de kérosène et 0, 3 baril de lubriant. Dans chaque baril, les 10% restant sont perdus.
La ranerie peut acheter au plus 9000 barils d'Arabie Saoudite par jour au prix de 20 dollars
l'unité, et au plus 6000 barils du Vénézuéla par jour au prix de 15 dollars l'unité.
An de satisfaire les demandes, la ranerie doit produire chaque jour au moins 2000 barils
d'essence, 1500 de kérosène et 500 de lubriant.
Combien de barils d'Arabie Saoudite et du Vénézuéla la ranerie doit-elle distiller an de mi-
nimiser ses coûts ?

Comment parvenir à modéliser ce problème ?

Pour y parvenir, on doit d'abord identier dans la formulation diérents objets :

1. Identier les variables.

Ce sont les inconnues du problème. Elles doivent représenter des nombres !

Dans l'exemple, les variables apparaissent clairement dans la question : il s'agit du nombre
de barils saoudiens et vénézuéliens ranés par jour. On identie donc deux variables :

x1 = nombre de barils saoudiens ranés par jour (en milliers)

x2 = nombre de barils vénézuéliens ranés par jour (en milliers)

Attention aux raccourcis du genre

x1 = barils saoudiens ranés par jour (en milliers)

x2 = barils vénézuéliens ranés par jour (en milliers)

6
 Il faut garder en tête que les variables représentent des nombres ! ! !

2. Identier les diérentes contraintes auxquelles les variables sont soumises.

Dans l'exemple, on ne peut consommer plus que la quantité disponible :

x1 6 9 brut saoudien
x2 6 6 brut vénézuélien

et on doit satisfaire les demandes :

0, 3x1 + 0, 4x2 > 2 essence

0, 4x1 + 0, 2x2 > 1, 5 kérosène
0, 2x1 + 0, 3x2 > 0, 5 lubriant

Attention, ne pas oublier la contrainte implicite, liée à la nature des variables ! ! ! Dans
le cas de l'exemple, on ajoute la contrainte

x1 , x2 ∈ Z+

Evidemment, dans ce cas, comme x1 et x2 représentent des milliers d'unités, on pourrait

accepter certaines valeurs fractionnaires comme 0, 5 par exemple. Mais si on remplace
notre contrainte d'intégralité par simplement x1 , x2 > 0, on n'a pas de garantie que la
solution renvoyée ne sera pas un nombre fractionnaire comme x1 = 1, 24125, ce qui n'est
pas réalisable pour notre problème.

3. Identier l'(les) objectif(s).

C'est-à-dire la fonction à optimiser (maximiser ou minimiser).

Pour notre problème, on veut minimiser les coûts :

min 20 000x1 + 15 000x2

Attention, le prix est ici exprimé en milliers de dollars.

La formulation standard du modèle suit la structure générale suivante :

min ou max fonction(s) objectif(s)

contraintes
Scq
contraintes liées à la nature des variables

Pour notre exemple, on obtient :

7
 min 20 000x1 + 15 000x2
scq 0, 3x1 + 0, 4x2 > 2
0, 4x1 + 0, 2x2 > 1, 5
0, 2x1 + 0, 3x2 > 0, 5
x1 6 9
x2 6 6
x1 , x2 > 0

1.4 Dénitions
Dénition 1.4.1 Une solution réalisable est une solution qui satisfait toutes les conditions
du problème.

Dénition 1.4.2 Une solution optimale est une solution réalisable dont la valeur de la fonc-
tion objectif atteint une valeur au moins aussi bonne (c'est-à-dire aussi grande si on a un pro-
blème de maximisation, aussi petite si c'est un problème de minimisation) que toutes les autres
solutions réalisables.

Cas particuliers :
 Un modèle peut avoir plusieurs solutions optimales diérentes.

 Un modèle peut n'avoir aucune solution réalisable (on dit que le problème est non-
réalisable).
Exemple :

max x1 + x2
scq x1 + x 2 > 3
x1 + x 2 6 1
x1 , x2 > 0
 Un modèle peut avoir des solutions réalisables qui permettent d'améliorer la fonction
objectif à l'inni (on dit que le problème est non-borné).
Exemple :

max x1 + x2
scq x1 + x2 > 3
x1 , x2 > 0

1.5 Un autre exemple, le Knapsack problem

A titre d'exemple, donnons une modélisation possible du problème dit du sac-à-dos, plus connu
sous le nom de Knapsack Problem : on doit remplir un sac-à-dos pouvant contenir W kg en sé-
lectionnant un certain nombre d'objets parmi n objets diérents. Chaque objet i (i = 1, · · · , n)
possède un prot/utilité pi et un poids wi .
Comment composer un sac-à-dos qui respecte la capacité du sac et ayant le plus grand prot

8
possible ?

Reprenons les diérentes étapes qui mènent à une modélisation :

1. Les variables. Ici, il s'agit, pour chaque objet i (i = 1, · · · , n), de décider si on le prend
dans notre sac-à-dos ou non. On introduit donc une variable xi pour chacun des n objets
qui va encoder notre choix :


1 si l'objet i va dans le sac-à-dos
xi :=
0 sinon

2. Les contraintes. On a deux contraintes :

 la capacité du sac-à-dos. Il faut que la somme des poids des objets sélectionnés ne
dépasse pas W. Le poids de l'objet 1 est donné par w1 . Si on multiplie w1 par x1 on
aura bien que le poids de l'objet 1 ne sera comptabilisé que si ce dernier est sélectionné.
Avec le même raisonnement sur les objets 2 à n on obtient que le poids total des objets
sélectionnés est
w 1 x1 + w 2 x 2 + · · · + w n xn
ou, plus simplement
n
X
w i xi
i=1

Cette somme ne pouvant dépasser W nous obtenons la contrainte

n
X
w i xi 6 W
i=1

 les contraintes liées à la nature des variables. Ici, nos variables doivent valoir 0 ou 1.
On écrit les contraintes
xi ∈ {0, 1} , ∀i = 1, · · · , n
3. L'objectif. On veut maximiser le prot. Comme pour la contrainte de capacité, on ne
veut tenir compte du prot que des objets sélectionnés dans le sac, ce qui est donné par
p 1 x1 + p 2 x2 + · · · + p n xn . L'objectif est donc

n
X
max p i xi
i=1
.

Le knapsack problem peut donc être modélisé comme suit :

max P ni=1 pi xi
P
n
scq i=1 wi xi 6 W
xi ∈ {0, 1} , ∀i = 1, · · · , n

9
1.6 Exercices
Rappels sur les symbôles de sommation

1. Soient A et B deux séries telles que

A = {ai | i = 1, · · · , 6} = {1, 1, 0, 4, 3, 3}
et

B = {bi | i = 1, · · · , 6} = {0, 1, 2, 2, 1, 3}
Ecrire et calculer les sommes suivantes
P6
a) ai
Pi=1
3
b) ai
Pi=1
6
c) ai
Pi=4
6
d) 2ai
Pi=1
4
e) (ai + bi )
Pi=1
4 P4
f) i=1 ai + i=1 bi
P6
g) (2ai + 3bi )
Pi=1
6 2
h) i=1 ai
P3
i) (ai + 5)
Pi=1
3
j) ai + 5
Pi=1
6
k) ( i=1 ai )2
P6
l) kk∈R
P4i=1
m) i=1 ai (ai − 1)

2. Ecrire les expressions suivantes à l'aide de la notation d'une somme :

a) a21 + a22 + · · · + a2n

b) a1 b1 + a2 b2 + · · · + am bm
c) a1 + a2 + · · · + am + b 1 + b 2 + · · · + b n
d) a1 b21 + a2 b22 + · · · + an b2n
e) b1 + 2b2 + 3b3 + · · · + nbn

Modélisation
1. Un modèle d'optimisation doit décider comment allouer les ores de p sources s1 , · · · , sp
an de satisfaire les q demandes r1 , · · · , rq de ses clients. En utilisant les variables de
décisions suivantes

wi,j = la quantité allouée de la source i au client j

formulez chaque condition en une ligne :

a) La quantité allouée de la source 32 ne peut excéder l'ore disponible de la source 32.

10
 b) La quantité allouée depuis chaque source i ne peut excéder l'ore disponible de la
source i.
c) La quantité allouée au client n doit être égale à la demande du client n.
d) La quantité allouée à chaque client j doit être égale à la demande du client j.

2. Déterminez pour chaque système le nombre de contraintes :

P22
a) zi,3 > b3
Pi=1
22
b) i=1 zi,p > bp , ∀p = 1, · · · , 45
P10
c) k=1 zi,j,k > gj , ∀i = 1, · · · , 14, ∀j = 1, · · · , 30

3. Vous devez sélectionner des projets parmi une collection de 16 projets d'investissement.
En utilisant les variables de décisions suivantes

1 si le projet j est sélectionné
wj =
0 sinon

Formulez chaque condition en une ligne

a) Au moins un des 8 premiers projets doit être sélectionné.

b) Au plus 3 des 8 derniers projets peuvent être sélectionnés.

c) Soit le projet 4 ou soit le projet 9 doivent être sélectionnés, mais pas les deux.

d) Le projet 11 peut être sélectionné seulement si le projet 2 l'est également.

e) Vous devez sélectionner les projets 1 et 5 tous les deux, ou aucun des deux.

f ) Vous devez sélectionner soit au moins un des projets 1, 2 ou 3, soit au moins deux des
projets 2, 4, 5 ou 6.

4. Considérons le problème de transport suivant : une rme dispose de m entrepôts et de n

clients. Il faut livrer un certain type de produit des entrepôts vers les clients. Notons ai la
quantité du produit stockée dans l'entrepôt i, ∀i = 1, · · · , m et dj la quantité du produit
demandée par le client j , ∀j = 1, · · · , n. Le coût unitaire de transport de l'entrepôt i vers
le client j est noté cij . La rme veut minimiser le coût de transport total, en satisfaisant
tous les clients. Donnez une formulation de ce problème sous forme de programme linéaire
en nombres entiers.

5. Un organisateur d'une soirée cocktails dispose des alcools suivants : 1.2 litres de whisky,
1.8 litres de vodka, 1.6 litres de vermouth rouge, 0, 6 litre de cognac, 0, 5 litre de liqueur
et 0, 5 litre de vermouth blanc. Il veut orir 5 cocktails diérents, à savoir :

 Chauncy : 2/3 whisky, 1/3 vermouth rouge,

 Black Russian : 3/4 vodka, 1/4 liqueur,
 Sweet Italian : 1/2 cognac, 1/4 vermouth rouge, 1/4 vermouth blanc,
 Molotov Cocktail : 2/3 vodka, 1/3 vermouth blanc,
 Whisky on the Rocks : 1/1 whisky.

Chaque cocktail a un contenu de 10cl. L'organisateur veut maximiser le nombre total de

cocktails servis. De plus, il pense que le Molotov Cocktail se vend bien, et il veut donc en
avoir au moins deux fois plus que de Black Russian. Formulez ce problème sous forme de
programme linéaire en nombres entiers.

11
6. Supposons que m jobs doivent être exécutés par n personnes. Chaque job doit être ef-
fectué par une seule personne, et chaque personne ne peut faire plus d'un job. Le coût
d'assignation du job i à la personne j est donné par cij . Le problème d'aectation est
d'aecter les jobs aux personnes tout en minimisant le coût total d'aectation. Modélisez
ce problème.

12
Chapitre 2
Programmation linéaire

Dans ce chapitre nous allons voir comment résoudre un ensemble de problèmes appelés "pro-
blèmes de programmation linéaire".

2.1 Rappels sur les fonctions linéaires

Dénition 2.1.1 Une fonction de n variables de la forme

f (x1 , x2 , · · · , xn ) = c1 x1 + c2 x2 + · · · + cn xn

avec c1 , c2 , · · · , cn qui sont des constantes réelles, est une fonction linéaire.

Exemple : f (x1 , x2 ) = 20x1 + 15x2 .

Dénition 2.1.2 Une famille de fonctions f (x) = ax + b avec a xé et b variable représente
un faisceau de droites parallèles dans le plan.

4
Exemple : f (x) = x2 = − x1 + b est un faisceau de droites parallèles. Toutes les droites de
3
4
ce faisceau ont une pente égale à − . Mais quand b varie, l'intersection avec l'axe des y varie
3
également. Dans la gure suivante, on a représenté les droites de ce faisceau pour diérentes
valeurs de b.

Dénition 2.1.3 Une inéquation linéaire est une inéquation de la forme

a1 x1 + a2 x2 + · · · + an xn 6 b

ou
a1 x 1 + a2 x 2 + · · · + an x n < b

Remarque : On peut bien sûr avoir l'inégalité dans l'autre sens (il sut de multiplier les deux
côtés par −1).

13
Si n = 2, alors l'inéquation a1 x 1 + a2 x 2 6 b représente un demi-plan dans le plan. Pour déter-
miner graphiquement celui-ci, il sut de tracer la droite a1 x1 + a2 x2 = b. Une fois que c'est fait
on n'a plus que deux demi-plans possibles qui peuvent être délimités par cette droite. Il sut
alors de prendre n'importe quel point au hasard qui n'appartient pas à la droite et de vérier
analytiquement si celui-ci fait partie du demi-plan que l'on cherche ou non.

Exemple : On veut tracer 0, 3x1 + 0, 4x2 > 2 (c'est bien une inéquation linéaire car elle est
équivalente à −0, 3x1 − 0, 4x2 6 −2). Ce demi-plan est le demi-plan délimité par la droite
0, 3x1 + 0, 4x2 = 2 (passant, entre autre, par les points (0; 5) et (4; 2)) et qui ne contient pas le
point (0; 0) (car 0, 3 · 0 + 0, 4 · 0  2). La gure suivante représente ce demi-plan.

14
2.2 Dénitions
Dénition 2.2.1 La programmation linéaire est une branche de la recherche opérationnelle
qui vise à maximiser ou minimiser une fonction linéaire dont les variables sont soumises à des
contraintes qui peuvent être décrites par des égalités ou des inégalités linéaires.

Un programme linéaire (PL) peut donc s'écrire sous la forme suivante :

Pn
max ou min j=1 cj xj

Pn 6
scq j=1 aij xj > bi ∀1 6 i 6 m
=
6 0
xj > 0 ∀1 6 j 6 n
libre

De façon générale, on considère qu'il y a n variables et m contraintes.

Remarques :
 On ne peut évidemment pas modéliser tous les problèmes avec des contraintes et un
objectif linéaires. Toutefois, nous verrons qu'il y a quand même beaucoup de problèmes
qui peuvent l'être.

 L'avantage de la programmation linéaire c'est qu'il existe des méthodes (comme l'algo-
rithme du simplexe) pour résoudre ce genre de problème (ce qui n'est en général pas le
cas de la programmation non-linéaire).

 Attention, si on remplace une des variables xj > 0 par xj ∈ Z+ , alors on n'a plus un
programme linéaire mais un programme linéaire en nombres entiers. Pour ces derniers
problèmes, nous ne pourrons utiliser l'algorithme du simplexe.

2.3 Formes de programme linéaire

Dénition 2.3.1 Si toutes les contraintes sont dénies par des inégalités linéaires , on dit que
le PL est sous sa forme canonique, c'est-à-dire :
Pn
max ou min cx
Pnj=1 j j
scq j=1 ij xj 6 bi ∀1 6 i 6 m .
a
xj > 0 ∀1 6 j 6 n
Alors que si toutes les contraintes sont des égalités linéaires, on dira que le PL est sous sa
forme standard, c'est-à-dire
Pn
max ou min cx
Pnj=1 j j
scq j=1 aij xj = bi ∀1 6 i 6 m .
xj > 0 ∀1 6 j 6 n

Remarque : Si certaines contraintes sont des inégalités linéaires et d'autres des égalités li-
néaires, on dit que le PL est sous sa forme mixte.

15
Proposition 2.3.2 Tout PL sous forme standard peut se réécrire, de façon équivalente, sous
forme canonique, et inversement.

Démonstration :
1. Partons d'un PL sous sa forme standard, c'est-à-dire
Pn
max ou min cx
Pnj=1 j j
scq j=1 aij xj = bi ∀1 6 i 6 m .
xj > 0 ∀1 6 j 6 n

et voyons qu'on peut le réécrire sous une forme canonique. Pour cela, il sut de remplacer
les m égalités par 2m inégalités : m inégalités dans un sens, et m dans l'autre :

Pn
max ou min cx
Pnj=1 j j
scq aij xj 6 bi ∀1 6 i 6 m
Pj=1
n .
j=1 aij xj > bi ∀1 6 i 6 m
xj > 0 ∀1 6 j 6 n
Ensuite il sut de multiplier les m inégalités avec un > par −1 :

Pn
max ou min cx
Pnj=1 j j
scq a x 6 bi ∀1 6 i 6 m
Pn j=1 ij j .
j=1 −aij xj 6 −bi ∀1 6 i 6 m
xj > 0 ∀1 6 j 6 n
On a donc bien un PL sous forme canonique.

2. Partons d'un PL sous sa forme canonique, c'est-à-dire

Pn
max ou min cx
Pnj=1 j j
scq j=1 aij xj 6 bi ∀1 6 i 6 m .
xj > 0 ∀1 6 j 6 n

et voyons qu'on peut le réécrire sous une forme standard. Pour cela, introduisons m
variables d'écart t1 , t2 , · · · , tm an d'obtenir des égalités :

Pn
max ou min j=1 cj xj
Pn
scq j=1 aij xj + ti = bi ∀1 6 i 6 m
.
xj > 0 ∀1 6 j 6 n
ti > 0 ∀1 6 i 6 m
ce qui est un PL sous forme standard.

Reprenons notre exemple :

min 20x1 + 15x2

scq 0, 3x1 + 0, 4x2 > 2
0, 4x1 + 0, 2x2 > 1, 5
0, 2x1 + 0, 3x2 > 0, 5
x1 6 9
x2 6 6
x1 , x2 > 0

16
 Mettons-le d'abord sous sa forme canonique avec toutes les inégalités dans le même sens :

min 20x1 + 15x2

scq −0, 3x1 − 0, 4x2 6 −2
−0, 4x1 − 0, 2x2 6 −1, 5
−0, 2x1 − 0, 3x2 6 −0, 5
x1 6 9
x2 6 6
x1 , x2 > 0
On rajoute à présent les variables d'écart t1 , t2 , · · · , t5 pour obtenir la forme standard :

min 20x1 + 15x2

scq −0, 3x1 − 0, 4x2 + t1 = −2
−0, 4x1 − 0, 2x2 + t2 = −1, 5
−0, 2x1 − 0, 3x2 + t3 = −0, 5
x1 + t4 = 9
x2 + t5 = 6
x1 , x2 > 0

2.4 Résolution graphique en deux dimensions (Rappels)

Reprenons le problème que nous avons modélisé dans le chapitre 1 :

min 20x1 + 15x2

scq 0, 3x1 + 0, 4x2 > 2
0, 4x1 + 0, 2x2 > 1, 5
0, 2x1 + 0, 3x2 > 0, 5
x1 6 9
x2 6 6
x1 , x2 > 0
Dans cette section nous proposons une résolution graphique de ce problème (qui a déjà été
enseignée en Ba1).

Attention, cette résolution graphique n'est possible que dans le cas où on a deux variables.
Mais elle donne une bonne intuition géométrique sur ce qui se passe quand on a n variables.

La première étape de cette résolution consiste à représenter l'ensemble des solutions réali-
sables, c'est-à-dire l'ensemble des couples (x1 , x2 ) du plan qui respectent toutes les inégalités.
Pour cela, prenons un système d'axe orthogonal (on peut utiliser une échelle diérente sur les
deux axes) où l'axe des abscisses représente la variable x1 et l'axe des ordonnées la variable x2 .

Nous allons maintenant représenter les diérentes contraintes. Commençons par la première
inégalité : 0, 3x1 + 0, 4x2 > 2. Comme déjà obtenu auparavant, il s'agit du demi-plan délimité
par la droite 0, 3x1 + 0, 4x2 = 2 et ne contenant pas le point (0, 0). On procède de la même
façon pour les 4 autres inégalités. L'ensemble des points satisfaisant les 5 contraintes sont donc
les points qui se trouvent simultanément dans les 5 demi-plans. Or, par souci de visibilité, il
est plus facile de repérer des points non-colorés que colorés par 5 couleurs diérentes, c'est
pourquoi nous prenons la convention de laisser en blanc le demi-plan qui correspond à
l'inégalité et de colorer la partie du demi-plan qui correspond à des points ne satisfaisant pas

17
l'inégalité ! Nous obtenons alors le dessin suivant :

L' ensemble des solutions réalisables est donné par un polygone (non nécessairement borné)
à l'intérieur duquel chaque point est une solution possible du problème. Ce polygone est tou-
jours convexe. Pour notre problème on obtient le polygone ABCDE .

A présent nous devons chercher parmi tous les points de l'ensemble des solutions réalisables,
un qui donne une valeur optimale (minimale dans notre cas) à l'objectif. On veut minimiser les
coûts :
min c = 20x1 + 15x2

18
Ce qui revient à dire qu'on cherche la plus petite valeur de c = 20x1 + 15x2 telle que (x1 , x2 )
appartient à l'ensemble des solutions réalisables. Or les équations

4 c
c = 20x1 + 15x2 ⇔ x2 = − x1 +
3 15
4
représentent un faisceau de droites parallèles dont la pente est de − et dont l'ordonnée à
3
c
l'origine (ou intersection avec l'axe des y) est égale à . De plus, quand on minimise la valeur
15
c
de c, on minimise en même temps la valeur de . Donc, parmi toutes les droites de ce faisceau,
15
on en cherche une sur laquelle il y a une ou plusieurs solutions à notre problème (autrement
dit qui possède une intersection non-vide avec le polygone ABCDE ) et qui a la plus petite
ordonnée à l'origine possible.

Pour faire cela, commençons par tracer une des droites appartenant au faisceau

4 c
x2 = − x1 + .
3 15
4
Par exemple, la droite x2 = − x1 . Tous les points qui se trouvent sur cette droite correspondent
3
à des valeurs de x1 et x2 entraînant un coût nul. En eet, l'ordonnée à l'origine de cette droite
c
(= ) est égale à 0, par conséquent on a c = 0. Par contre, comme on le voit sur la gure
15
suivante, aucun des points de cette droite ne correspond à une solution réalisable car il n'y a
aucune intersection entre cette droite et le polygone ABCDE .

4
Il nous reste à identier une droite parallèle à la droite x 2 = − x1 qui possède une intersection
3
non-vide avec le polygone ABCDE et qui a la plus petite ordonnée à l'origine. Sur le graphique,
on peut tracer cette droite qui intercepte le polygone au point D.

On peut se convaincre sur cet exemple que, quelle que soit la fonction linéaire à optimiser sur
un domaine réalisable convexe, la solution optimale, si elle est unique, sera forcément sur un
sommet du polygone. Si la solution n'est pas unique, alors on aura toute une arête de solutions
équivalentes, et donc en particulier on aura deux sommets.

19
Maintenant qu'on a repéré graphiquement le sommet, on doit calculer ses coordonnées ana-
lytiquement. On remarque sur le graphique que D est le point d'intersection de la droite
0, 4x1 + 0, 2x2 = 1, 5 et de la droite 0, 3x1 + 0, 4x2 = 2. On résout donc le système suivant :

0, 4x1 + 0, 2x2 = 1, 5
0, 3x1 + 0, 4x2 = 2
Ce qui nous donne le point (2; 3, 5). Ainsi, la réponse optimale pour notre problème est unique
et révèle que nous devons distiller 2000 barils d'Arabie Saoudite et 3500 barils du Vénézuéla.
Ainsi, nous minimisons la fonction objectif qui a alors un coût de

c(2; 3, 5) = 20 · 2 + 15 · 3, 5 = 92, 5

c'est-à-dire 92 500 dollars.

Remarque : Comme la solution trouvée (si elle existe) est un sommet du polygone, si celui-ci
ne possède pas des coordonnées entières, la solution sera fractionnaire (comme dans ce cas où
x2 = 3, 5). C'est pourquoi, on ne peut généraliser telle quelle cette méthode pour des problèmes
où les variables doivent être entières. Ce qu'on peut alors faire, c'est résoudre notre problème et,
si la solution donnée est fractionnaire, on regarde les solutions entières les plus proches et pour
chacune d'elles on calcule la valeur de l'objectif correspondant. On termine en sélectionnant
la meilleure. Attention, cette étape peut devenir très compliquée si la dimension du problème
(c'est-à-dire son nombre de variables) est grand.

2.5 Déduction d'une résolution non graphique

Dans cette section, nous allons nous servir de la résolution graphique vue dans la section pré-
cédente pour en déduire une résolution générale non graphique. En eet, quand on abordera
des problèmes de dimensions supérieures à 2, nous ne pourrons plus nous baser sur la méthode
graphique.

Lors de la résolution graphique, nous avons remarqué que la solution optimale de notre problème
se trouvait en un sommet du polygone des solution réalisables. Formalisons ceci :

Proposition 2.5.1 Si un PL est réalisable et borné, alors tous les optima se trouvent sur le
bord du domaine réalisable.

20
Il est facile de s'en convaincre par dessin. La démonstration, elle, nécessite plus de formalisme.

Proposition 2.5.2 Si un PL est réalisable et borné, alors il existe (au moins) une solution
optimale qui est un sommet du polyèdre.

Ceci nous donne une idée de résolution non graphique : comme on sait qu'une solution optimale
se trouve en un sommet du polygone, il nous sut d'inspecter les sommets ! ! !

Reprenons notre problème de barils à distiller :

min 20x1 + 15x2

scq 0, 3x1 + 0, 4x2 > 2
0, 4x1 + 0, 2x2 > 1, 5
0, 2x1 + 0, 3x2 > 0, 5
x1 6 9
x2 6 6
x1 , x2 > 0
ainsi que son polygone :

Notre nouvelle méthode consisterait donc à déterminer les coordonnées des 5 sommets ABCDE
du polygone et d'évaluer la valeur de l'objectif pour chacun de ces 5 sommets. C'est ce que
nous faisons maintenant :
 On voit sur le graphique que le sommet A est la solution du système


x1 = 9
x2 = 0

dont la solution (triviale) est le point (9; 0) dont la valeur de l'objectif est c(9; 0) =
20 · 9 = 180.
 On voit sur le graphique que le sommet B est la solution du système


x1 = 9
x2 = 6

dont la solution (triviale) est le point (9; 6) dont la valeur de l'objectif est c(9; 6) =
20 · 9 + 15 · 6 = 270.

21
  On voit sur le graphique que le sommet C est la solution du système


0, 4x1 + 0, 2x2 = 1, 5
x2 = 6

soit le point (0, 75; 6) dont la valeur de l'objectif est c(0, 75; 6) = 20 · 0, 75 + 15 · 6 = 105.
 On voit sur le graphique que le sommet D est la solution du système


0, 4x1 + 0, 2x2 = 1, 5
0, 3x1 + 0, 4x2 = 2

soit le point (2; 3, 5) dont la valeur de l'objectif est c(2; 3, 5) = 20 · 2 + 15 · 3, 5 = 92, 5.

 On voit sur le graphique que le sommet E est la solution du système


0, 3x1 + 0, 4x2 = 2
x2 = 0

soit le point (6, 67; 0) dont la valeur de l'objectif est c(6, 67; 0) = 20 · 6, 67 = 133, 4.
Avec cette méthode, on obtient bien sûr la même solution que dans la section précédente !

Il reste que nous avons malgré tout encore utilisé notre représentation graphique des contraintes
pour déterminer les sommets... Nous devons donc encore rééchir à une méthode qui nous per-
mettrait dedéterminer les coordonnées des sommets sans avoir recours à la repré-
sentation graphique. On constate dans l'exemple ci-dessus que, comme on a un problème
à deux variables, chaque sommet est la solution d'un système formé par deux contraintes du
problème mises à l'égalité. Ainsi, on peut complètement se passer à présent de la représentation
graphique. On obtient l'algorithme suivant :

1. Pour chaque paire de contraintes, on résout le système formé par ces deux contraintes
mises à l'égalité.

2. Si le sommet résultant de ce système appartient au domaine réalisable (c'est-à-dire s'il

satisfait toutes les autres contraintes), on calcule la valeur de la fonction objectif pour ce
sommet. Sinon, on élimine le sommet.

3. On sélectionne le meilleur" sommet (c'est-à-dire celui ayant la plus grande valeur pour
la fonction objectif si c'est un problème à maximum, ou celui qui a la plus petite valeur
si c'est un problème à minimum).

Cet algorithme est très simple à adapter pour les problèmes qui possèdent n variables : à
l'étape un, au lieu de prendre des systèmes de 2 contraintes, on prend des systèmes formés par
n contraintes.

Pour se faire une idée, regardons comment cet algorithme s'appliquerait à notre exemple : nous
avons 7 inégalités (les 5 contraintes du problème ainsi que les deux contraintes liées à la nature
2 7·6
des variables) que nous devons associer par paires : il y a donc C7 = = 21 systèmes
2
possibles ! ! ! Or, on sait que seulement 5 d'entre eux mènent à une solution réalisable. En eet,
la résolution du système 
0, 4x1 + 0, 2x2 = 1, 5
0, 2x1 + 0, 3x2 = 0, 5

22
mène à la solution (0, 3; 1, 47) qui ne satisfait pas la contrainte 0, 3x1 + 0, 4x2 > 2.

On remarque donc que, même sur un petit exemple, l'application de cet algorithme peut prendre
beaucoup de temps ! Essayons d'évaluer combien de temps cela prendrait de résoudre un PL de
n variables avec m contraintes : pour déterminer chaque sommet, on doit résoudre un système
3
de m équations à m inconnues, ce qui prend de l'"ordre" de m opérations pour un ordinateur.
Combien de tels systèmes doit-on résoudre ? On doit pour chaque sommet choisir m variables
m
parmi n, c'est-à-dire qu'il y a Cn . Si les nombres m et n sont petits, c'est faisable, mais si m
et/ou n sont grands, le nombre d'opérations explose et l'algorithme devient vite impossible à
appliquer même par un ordinateur ! En eet, déjà quand n = 20 et m = 10, on obtient alors de
8
l'ordre de 2 · 10 opérations à eectuer !

Nous allons devoir adapter notre algorithme an qu'il fasse moins d'opérations.

2.6 Vers l'algorithme du simplexe

L'algorithme que nous avons construit à la section précédente avait l'avantage de ne pas avoir
besoin de recourir à une représentation graphique du PL, mais avait le gros désavantage de
coûter extrêmement cher en temps d'exécution, le rendant impratiquable pour la plupart des
problèmes. Ce temps d'exécution était lié au très grand nombre de systèmes à résoudre, dont
la plupart menait à des solutions non réalisables. Nous allons ici tenter de voir s'il n'y aurait
pas moyen de ne pas avoir à explorer tous les sommets et de ne pas avoir à résoudre tous les
systèmes possibles, an de gagner en ecacité.

Reprenons le graphique, et supposons que le premier sommet trouvé soit le sommet A, de coor-
données (9; 0) Comment trouver une stratégie
et dont la valeur pour l'objectif est de 180.
qui nous permette de ne pas visiter tous les sommets ? L'idée sera de parcourir le po-
lygone de sommet en sommet en améliorant toujours la valeur de notre objectif.

Gardons notre objectif en tête :

min 20x1 + 15x2
On se rend compte qu'au plus on va diminuer les valeurs de x1 et x2 , au plus l'objectif aura
une valeur minimale. Si on regarde uniquement les sommets adjacents au sommet A, quand
on regarde notre représentation graphique, on se rend compte que le sommet B sera de toute
façon moins intéressant pour notre objectif que le sommet actuel A : en eet, on voit sur le

23
graphique que pour passer de A à B, il faut augmenter la valeur de x2 sans modier la valeur
de x1 . Ceci aura pour conséquence d'augmenter la valeur de la fonction objectif à minimiser.
Par contre, si on passe du sommet actuel A au sommet E , on devra diminuer la valeur de x1
sans modier la valeur de x2 , ce qui aura pour eet de diminuer la valeur de l'objectif. On peut
donc voir graphiquement qu'il vaut la peine de passer par le sommet E = (6, 67; 0) et qui a
pour valeur de la fonction objectif 133, 4.

A présent nous sommes au sommet E . On ne va pas revenir en A, on peut juste aller au sommet
D. Pour cela, on diminue la valeur de x1 (d'environ 4 unités), mais x2 va augmenter (d'environ
3 unités). Il n'est donc pas évident que ce passage va entraîner une diminution de la fonction
objectif. Toutefois, dans ce cas, ce passage au sommet D de coordonnées (2; 3, 5) diminue bien
la valeur de la fonction objectif à 92, 5.

En partant du sommet D, on se demande s'il faut se rendre au sommet C = (0, 75; 6). La valeur
de la fonction objectif en ce sommet a augmenté, elle est de 105. On décide donc de rester au
sommet D qui est notre solution optimale.

Remarque : on n'a pas visité tous les sommets ! De plus, on n'a pas eu besoin de résoudre les
systèmes qui menaient à des sommets non réalisables !

Idée de la méthode du simplexe : Partir d'un sommet réalisable et se déplacer de sommet

réalisable en sommet réalisable en explorant seulement ceux qui permettent d'améliorer la valeur
de la fonction objectif (l'augmenter si c'est une fonction à maximiser, la diminuer si c'est une
fonction à minimiser).

2.7 Les deux phases de l'algorithme du simplexe

Nous allons à présent décrire la méthode du simplexe. L'algorithme du simplexe comprend deux
phases :
 Phase 1 : Initialisation
Il s'agit de déterminer une première solution réalisable (c'est-à-dire un sommet réalisable
de départ, comme le sommet A pour notre exemple précédent), ou de détecter l'impos-
sibilité d'en trouver une (si le problème est non réalisable).

 Phase 2 : Progression
On passe d'un sommet réalisable à un autre sommet réalisable an d'améliorer la valeur
de la fonction objectif.

Nous pouvons voir cette progression sur le schéma (voir page 187 livre (3)) suivant qui représente
le polyèdre des solutions réalisables pour un PL de 3 variables.
Il y a donc deux points essentiels qui doivent être abordés :

1. Comment déterminer un sommet réalisable de départ (ou détecter qu'il n'en existe pas) ?

2. Comment choisir une direction qui améliore la valeur de l'objectif ?

C'est ce que nous allons voir à présent.

24
2.7.1 Solutions de base
An de traduire de façon algorithmique, et sans représentation graphique, la méthode géomé-
trique vue plus haut, nous aurons besoin de diérentes dénitions.

Pour cela, partons d'un PL sous forme standard :

Pn
max ou min cx
Pnj=1 j j
scq j=1 aij xj = bi ∀1 6 i 6 m .
xj > 0 ∀1 6 j 6 n
De manière générale, on considère qu'on a un système de m contraintes à n variables. Nous
allons toujours faire l'hypothèse que
m<n
Pourquoi ? ? ?

Dénition 2.7.1 Une solution de base d'un PL sous forme standard est une solution obtenue
en xant n−m variables à 0 de telle sorte que le système restant (de m équations à m inconnues)
possède une unique solution.
Les n−m variables xées à 0 sont les variables hors base, et les autres sont les variables
en base.

Remarque : ceci correspond aux sommets que nous cherchions dans notre exemple à deux
variables.

Remarque : On peut donc xer les variables hors base à 0, et du coup les variables en base
seront déterminées par le système.

Dénition 2.7.2 Une solution de base est réalisable si xj > 0 pour toutes les variables.
Une solution de base est non-réalisable s'il existe un indice j tel que xj < 0.

Considérons le problème suivant :

25
 max 6x1 + 4x2
scq 3x1 + 9x2 6 81
4x1 + 5x2 6 55 .
2x1 + x2 6 20
x1 , x2 > 0
qui possède 2 (= n) variables et 3 (= m) contraintes. Or, nous avions supposé que m < n...
Mais quand le problème est écrit sous sa forme standard ! Pour écrire ce PL sous sa forme
standard, nous allons introduire les variables d'écart s1 , s2 et s3 :

max 6x1 + 4x2

scq 3x1 + 9x2 + s1 = 81
4x1 + 5x2 +s2 = 55 .
2x1 + x2 +s3 = 20
x1 , x2 , s1 , s2 , s3 > 0
ce qui nous donne m = 3 et n = 5. Choisissons à présent la base formée de s1 , s2 et s3 . Cela
signie que les variables x1 et x2 sont hors base et sont donc xées à 0. On doit alors résoudre
le système 
 s1 = 81
s2 = 55
s3 = 20


qui possède bien une solution unique. La solution correspondante (0, 0, 81, 55, 20) est bien une
solution de base réalisable puisqu'elle satisfait toutes les contraintes.

Remarque : géométriquement, ce point correspond à un sommet du polyèdre des solutions

réalisables.

Ici, on a juste introduit une terminologie plus spécique pour déterminer les sommets. On va
maintenant voir comment on passe d'un sommet à un autre.

2.7.2 La Phase 2 de Progression

Nous avons donc à présent une première solution de base réalisable que nous noterons xB :

xB = (0, 0, 81, 55, 20)

qui est associée à la base B = {s1 , s2 , s3 }. La valeur de la fonction objectif (qui est à maximiser)
associée est de 0 (= 6 · 0 + 4 · 0). La phase 1 est donc terminée.

On arrive à la phase 2 de l'algorithme : la progression. Le but est donc de déterminer une

∗ ∗
nouvelle base B telle que la solution de base associée à B soit réalisable et améliore la valeur
de la fonction objectif.

Principe : Faire entrer en base une variable hors-base, et faire sortir de la base une variable
en base.

Géométriquement, cela revient à se déplacer d'un sommet vers un autre le long d'une arête.

26
Il y a donc deux questions à se poser :

1. Comment choisir la variable (hors base) qui va entrer en base ?

2. Comment choisir la variable (en base) qui va sortir de la base ?

Pour répondre à ces questions, nous allons analyser notre exemple qui peut être réécrit de la
façon suivante : on exprime les variables en base en fonction des variables hors base :

s1 = 81 −3x1 −9x2
s2 = 55 −4x1 −5x2
s3 = 20 −2x1 −x2
z = 6x1 +4x2

On appelle le tableau ci-dessus un dictionnaire.

A. Variable entrante

Pour choisir la variable entrante dans notre exemple, on a le choix entre x1 et x2 . Pour l'instant,
comme ce sont des variables hors base on a x1 = x2 = 0. En observant la ligne de l'objectif
z = 6x1 + 4x2 , on se rend compte que si on augmente la valeur de x1 , la valeur de l'objectif va
s'améliorer car le coecient de x1 à la dernière ligne, appelé le coût réduit, est positif. Si on
augmente x2 également.

Conclusion, la solution actuelle (ou solution courante) xB = (0, 0, 81, 55, 20) n'est pas opti-
male vu qu'on peut améliorer l'objectif !

Comment choisir entre x1 et x2 ? Quand les deux variables peuvent entrer en base, on choisit
celle qui permet une meilleure progression de l'objectif, à savoir x1 dans notre cas.

On choisit donc la variable hors base ayant le coût réduit positif le plus grand si
c'est un problème de maximisation, négatif le plus petit si c'est un problème de
minimisation.
Attention : si tous les coûts réduits étaient négatifs pour notre exemple, cela signierait que
si on rentrait en base une des variables hors-base cela aurait pour conséquence de diminuer la
valeur de l'objectif. On ne pourrait donc plus augmenter la valeur de l'objectif ce qui entraine-
rait que la solution courante est optimale.

B. Variable sortante

Maintenant qu'on a décidé de faire entrer x1 en base, il faut choisir quelle variable en base (s1 ,
s2 ou s3 ) va sortir (ce qui aura pour conséquence que cette variable serait mise à 0). Reprenons
notre tableau

27
 s1 = 81 −3x1 −9x2 (1)
s2 = 55 −4x1 −5x2 (2)
s3 = 20 −2x1 −x2 (3)
On va choisir comme variable sortante la première variable à bloquer l'augmentation de la
variable entrante. Comme on veut maximiser l'objectif, on veut augmenter la valeur de la
variable entrante x1 autant que possible, mais tout en gardant une solution réalisable. Or,

 à cause de l'équation (1), on sait que x1 6 27, sinon la variable s1 serait négative et la
solution de base serait non réalisable.

 à cause de l'équation (2), on sait que x1 6 13, 75, sinon la variable s2 serait négative et
la solution de base serait non réalisable.

 à cause de l'équation (3), on sait que x1 6 10, sinon la variable s3 serait négative et la
solution de base serait non réalisable.

En assemblant ces trois données on a qu'on peut faire passer x1 au maximum de 0 à 10. Ceci
entraînera que s3 = 0. C'est donc s3 qui sort de la base.

On a donc une nouvelle base B ∗ = {x1 , s1 , s2 } et on peut adapter le dictionnaire :

1 1
x1 = 10 − x2 − s3
2 2
1 1
s1 = 81 − 3(10 − x2 − s3 ) − 9x2
2 2
1 1
s2 = 55 − 4(10 − x2 − s3 ) − 5x2
2 2
1 1
z = 6(10 − x2 − s3 ) + 4x2
2 2
ou encore

1 1
x1 = 10 − x2 − s3
2 2
15 3
s1 = 51 − x2 + s 3
2 2

s2 = 15 − 3x2 + 2s3

z = 60 + x2 − 3s3
La solution de base réalisable associée à notre nouvelle base B ∗ = {x1 , s1 , s2 } est (10, 0, 51, 15, 0)
et la valeur de l'objectif en ce point est de 60. On a bien amélioré la valeur de l'objectif. A
présent on doit revenir à l'étape 2 de la progression. On constate que si on fait entrer x2 en
base cela aura pour conséquence d'améliorer l'objectif. Donc x2 entre en base.

On obtient alors que c'est s2 qui va être mis à 0. C'est donc s2 qui sort. La mise à jour du
dictionnaire est

28
 1 2
x2 = 5 − s2 + s3
3 3
15 1 5
x1 = + s2 − s3
2 6 6
27 5 7
s1 = + s2 − s3
2 2 2
1 7
z = 65 − s2 − s3
3 3
15 27
La solution de base réalisable associée à notre nouvelle base {x1 , x2 , s1 } est ( , 5, , 0, 0) et
2 2
la valeur de l'objectif en ce point est de 65.

On constate que, si on fait entrer s2 ou s3 , la valeur de l'objectif ne fera que diminuer. On peut
donc s'arrêter, la solution courante est optimale.

2.7.3 Cas particuliers

1. Dans la progression de l'algorithme du simplexe il se peut, lors de la détermination de la
variable sortante, qu'il n'y ait aucun candidat.

Exemple : pour un problème de maximisation on a le dictionnaire suivant

1 1
x2 = 5 −x1 + s1 − s2
2 2
x3 = 20 −5x1 −s2

1 3
z = 15 −2x1 + s1 − s2
2 2
On décide de faire entrer s1 dans la base. Mais aucune des variables en base x2 ou x3
n'impose une limite sur la croissance de s1 . On peut donc accroître s1 autant que l'on
veut et du coup augmenter la valeur de l'objectif à l'inni. On peut donc conclure que le
problème est non-borné.

2. Un autre cas particulier est celui où on a plusieurs variables qui peuvent sortir. On prend
alors celle qui a le plus petit indice (idem si on a plusieurs candidats possibles qui peuvent
entrer en base).

La présence de plusieurs candidats à la sortie a une conséquence : il y aura d'oce une

variable en base qui sera mise à 0.

Exemple : pour un problème de maximisation on a le dictionnaire suivant

s1 = 1 −2x3
s2 = 3 −2x1 +4x2 −6x3
s3 = 2 +x1 −3x2 −4x3
z = 2x1 −x2 +8x3

29
 Supposons qu'on fasse entrer x3 en base. Chacune des 3 variables de s1 , s2 et s3 limite
1
à l'augmentation de x3 . Choisissons s1 pour sortir de la base. On obtient le nouveau
2
dictionnaire :

1 1
x3 = − s1
2 2
s2 = −2x1 +4x2 +3s1
s3 = x1 −3x2 +2s1
z = 4 +2x1 −x2 −4s1
1
La solution courante est xB = (0, 0, , 0, 0). Ainsi, malgré que s2 et s3 sont en base, elles
2
sont nulles.

Dénition 2.7.3 Une solution de base avec une ou plusieurs variables en base nulle(s)
est une solution dite solution de base dégénérée.

Voyons l'itération suivante de notre exemple : x1 entre en base et c'est s2 qui sort. Le
dictionnaire correspondant est :

3 1
x1 = 2x2 + s1 − s2
2 2
1 1
x3 = − s1
2 2
7 1
s3 = −x2 + s1 − s2
2 2
z = 4 +3x2 −s1 −s2
On remarque que la valeur de l'objectif ne change pas. Une telle itération est une itéra-
tion dite dégénérée.
Dans les problèmes concrets, il peut y avoir parfois quelques dizaines, voire quelques
centaines d'itérations dégénérées avant de voir une amélioration de l'objectif !

2.7.4 La Phase 1 d'Initialisation

Attention, il n'est pas toujours évident de déterminer une première solution de base réalisable !
Et pourtant, sans cette première solution, on ne peut démarrer l'algorithme ! Il n'est pas non
plus évident de repérer un problème qui ne possède aucune solution de base réalisable (problème
non-réalisable).

A titre d'exemple essayons de déterminer une première solution de base réalisable pour le PL
suivant :

max x1 − x2 + x 3
Scq 2x1 − x2 + 2x3 6 4
2x1 − 3x2 + x3 6 −5
−x1 + x2 − 2x3 6 −1
x1 , x2 , x3 > 0
Passons à la formulation standard de ce PL :

30
 max x1 − x2 + x3
Scq 2x1 − x2 + 2x3 + s1 = 4
2x1 − 3x2 + x3 +s2 = −5
−x1 + x2 − 2x3 +s3 = −1
x1 , x2 , x3 , s1 , s2 , s3 > 0
Si on prend, comme d'habitude, la base constituée par les variables d'écart {s1 , s2 , s3 }, on
constate que la solution de base associée n'est pas réalisable (s2 et s3 seront négatifs).

Une façon systématique d'aborder ce problème est de poser un problème auxiliaire. Suppo-
sons de façon générale qu'on doive résoudre le problème suivant :

Pn
max cx
Pnj=1 j j
Scq j=1 aij xj = bi ∀i = 1, · · · , m
xj > 0 ∀j = 1, · · · , n
et supposons qu'on ne trouve à priori aucune solution de base réalisable (remarque : on peut
supposer que tous les bi sont positifs, car sinon on multiplie l'égalité par −1). Considérons alors
le problème suivant :

Pm
min P i=1 ei
n
Scq j=1 aij xj + ei = bi ∀i = 1, · · · , m
xj > 0 ∀j = 1, · · · , n
ei > 0 ∀i = 1, · · · , m
Ce problème auxiliaire n'est bien sûr pas équivalent au problème original, mais on peut remar-
quer que le problème original possède une solution (problème réalisable) si et seulement si le
problème auxiliaire possède une solution réalisable avec tous les ei = 0 ∀1 6 i 6 m. Or, comme
on impose que les variables ei soient positives ou nulles pour tout i, si une solution avec tous
les ei = 0 existe, elle est forcément optimale. On a donc que

Le problème original est réalisable si et seulement si le problème auxiliaire a 0

pour valeur optimale.
Donc, on résout le problème auxiliaire par l'algorithme du simplexe, et on obtient alors que
 soit sa solution optimale est telle que ei = 0 ∀i = 1, · · · , m, auquel cas on sait que
le problème original est réalisable et on peut donc trouver une première solution de
base réalisable. Cette première solution est maintenant facile à déterminer vu qu'on a
terminé l'algorithme du simplexe sur le problème auxiliaire avec toutes les variables ei
nulles, donc hors base. La base déterminée par le simplexe sur le problème auxiliaire
nous donne donc une première solution de base réalisable, et on peut alors commencer
la phase de progression sur le problème original.

 soit sa solution optimale est supérieure à 0, auquel cas on sait que le problème original
est non réalisable, il n'y a donc rien à optimiser.

Exemples :

1. Reprenons notre exemple ci-dessus :

31
 max x1 − x2 + x3
Scq 2x1 − x2 + 2x3 + s1 = 4
2x1 − 3x2 + x3 +s2 = −5
−x1 + x2 − 2x3 +s3 = −1
x1 , x2 , x3 , s1 , s2 , s3 > 0
Comme nous l'avons déjà vu, la solution de base correspondant à la base {s1 , s2 , s3 } n'est
pas réalisable. On va devoir passer au problème auxiliaire an de déterminer une pre-
mière solution de base réalisable. Avant cela, multiplions par −1 la deuxième et troisième
contrainte an de rendre positifs tous les membres de droites :

max x1 − x2 + x3
Scq 2x1 − x2 + 2x3 + s1 = 4
−2x1 + 3x2 − x3 −s2 = 5
x1 − x2 + 2x3 −s3 = 1
x1 , x2 , x3 , s1 , s2 , s3 > 0
On introduit maintenant les nouvelles variables e1 , e2 et e3 pour formuler notre problème
auxiliaire :

min e1 + e2 + e3
Scq 2x1 − x2 + 2x3 + s1 +e1 = 4
−2x1 + 3x2 − x3 −s2 e2 = 5
x1 − x2 + 2x3 −s3 +e3 = 1
x1 , x2 , x3 , s1 , s2 , s3 > 0
e1 , e2 , e3 > 0
Ce problème possède une solution de base réalisable associée à la base {e1 , e2 , e3 } :

e1 = 4 −2x1 +x2 −2x3 −s1

e2 = 5 +2x1 −3x2 +x3 +s2
e3 = 1 −x1 +x2 −2x3 +s3
w = 10 −x1 −x2 −3x3 −s1 +s2 +s3
La solution de base réalisable initiale de ce problème est donc

xB = (0, 0, 0, 0, 0, 0, 4, 5, 1)
| {z } | {z } | {z }
xj sj ei

et la valeur correspondante de l'objectif est de 10. Comme on veut minimiser l'objectif,

on va faire entrer x3 en base. Par conséquent, c'est e3 qui sort :

e1 = 3 −x1 −s1 −s3 e3

11 3 5 1 1
e2 = + x1 − x2 +s2 + s3 − e3
2 2 2 2 2
1 1 1 1 1
x3 = − x1 + x2 + s3 − e 3
2 2 2 2 2
17 1 5 1 3
w = + x1 − x2 −s1 +s2 − s3 + e3
2 2 2 2 2
On continue, x2 entre et e2 sort :

32
 e1 = 3 −x1 −s1 −s3 +e3
11 3 2 1 2 1
x2 = + x1 + s2 + s3 − e 2 − e 3
5 5 5 5 5 5
8 1 1 3 1 3
x3 = − x1 + s2 + s3 − e 2 − e 3
5 5 5 5 5 5

w = 3 −x1 −s1 −s3 +e2 +2e3

On continue, x1 entre et e1 sort :

x1 = 3 −s1 −s3 −e1 +e3

3 2 2 3 2 2
x2 = 4 − s1 + s2 − s3 − e1 − e2 + e3
5 5 5 5 5 5
1 1 4 1 1 4
x3 = 1 − s1 + s2 − s3 + e1 − e2 − e3
5 5 5 5 5 5

w = e1 +e2 +e3
Tous les coûts réduits sont positifs, on a une solution optimale. Comme la valeur de
l'objectif pour cette solution (3, 4, 1, 0, 0, 0, 0, 0, 0) est nulle, on en déduit que la solution
(3, 4, 1, 0, 0, 0) est une solution de base réalisable pour le problème original ! On peut le
vérier en injectant cette solution dans le système des contraintes. La phase 1 d'initia-
lisation est (enn) terminée, et on va pouvoir commencer la phase 2 de progression en
démarrant avec le dernier tableau de la phase 1 (on peut supprimer les variables e1 , e2 et
e3 ) :

x1 = 3 −s1 −s3
3 2 2
x2 = 4 − s 1 + s 2 − s 3
5 5 5
1 1 4
x3 = 1 − s 1 + s 2 − s 3
5 5 5
3 1 7
z = − s1 − s2 − s3
5 5 5
Le problème original est un problème de maximisation. Ici, tous les coûts réduits sont
négatifs, on a donc à faire à une solution optimale.

2. On veut résoudre le PL suivant :

max 3x1 + 5x2

Scq x1 6 4
2x2 6 12
3x1 + 2x2 = 18
x1 , x2 > 0
On le met sous forme standard :

33
 max 3x1 + 5x2
Scq x1 +s1 = 4
2x2 +s2 = 12
3x1 + 2x2 = 18
x1 , x2 , s1 , s2 > 0
On ne trouve pas de solution. On introduit une variable e1 :

min e1
Scq x1 +s1 = 4
2x2 +s2 = 12
3x1 + 2x2 +e1 = 18
x1 , x2 s1 s2 e1 > 0
Cette manière de procéder est appelée algorithme du simplexe en deux phases :
 Première phase : résoudre le problème auxiliaire an de déterminer une première so-
lution de base réalisable ou déterminer que le problème est non réalisable.

 Deuxième phase : si le problème est réalisable, on entame la résolution du problème

original avec la solution initiale trouvée dans la phase 1.

2.8 Dualité
2.8.1 Motivation du problème dual : la recherche d'une borne supé-
rieure sur la valeur optimale
Partons du problème suivant :

max 40x1 + 30x2

Scq x1 6 16
x2 6 8
x1 + 2x2 6 24
x1 , x2 > 0
Supposons que l'on cherche, sans résoudre le problème, une borne inférieure et une borne su-
périeure sur la valeur optimale de l'objectif an d'avoir une idée de la valeur optimale (notons
∗
cette valeur z ).

Remarque : au plus la borne inférieure sera grande et au plus la borne supérieure sera petite,
au plus la fourchette des valeurs possibles de la valeur optimale sera restreinte, et donc meilleure
sera l'information.

Comment trouver une borne inférieure ?

Toute solution réalisable nous en donne une ! Par exemple, x1 = 4 et x2 = 4 est une solution
réalisable dont la valeur pour l'objectif est de 280. On sait par conséquent que

z ∗ > 280

34
Comment trouver une borne supérieure ?

En multipliant la troisième contrainte par 40 on obtient :

40x1 + 80x2 6 960

et donc

40x1 + 30x2 6 40x1 + 80x2 6 960

fn objectif
| {z }

On peut donc conclure que la valeur de la fonction objectif est comprise entre 280 et 960.

De façon générale, pour obtenir une borne supérieure, on essaie de déduire, à partir des
contraintes du problème, une inégalité où chaque coecient est supérieur ou égal au coecient
correspondant de la fonction objectif. Pour notre exemple, on peut aussi sommer la première
inégalité multipliée par 40 et la deuxième multipliée par 30 :

40x1 + 30x2 6 880

donc

z ∗ 6 880.

Essayons de construire une méthode systématique : multiplions la première inégalité par y1 , la

deuxième par y2 , et la troisième par y3 , puis on additionne le tout :

(y1 + y3 )x1 + (y2 + 2y3 )x2 6 16y1 + 8y2 + 24y3

Remarque : pour pouvoir écrire ceci, on est obligé d'imposer y1 , y2 , y3 > 0.
Pour pouvoir se servir de cette inégalité on veut :

40x1 + 30x2 6 (y1 + y3 )x1 + (y2 + 2y3 )x2

Il faut donc que

40 6 y1 + y3
30 6 y2 + 2y3
Si ces deux inégalités sont satisfaites, on peut alors conclure que

40x1 + 30x2 6 16y1 + 8y2 + 24y3

Comme dit précédemment, plus cette borne est petite, meilleure est l'information obtenue sur
z ∗ . On obtient alors le PL suivant :

min 16y1 + 8y2 + 24y3

Scq y1 + y3 > 40
y2 + 2y3 > 30
y1 , y2 , y3 > 0
Ce nouveau PL est appelé problème dual.
Exercice : cherchez des bornes inférieures et supérieures pour un problème de minimisation.
35
2.8.2 Problème dual
Le PL auquel nous sommes arrivés est appelé problème dual du problème original (qui lui
est alors appelé problème primal). De manière générale, si le problème primal est écrit sous
la forme

Pn
max cx
Pnj=1 j j
Scq j=1 aij xj 6 bi ∀i = 1, · · · , m
xj > 0 ∀j = 1, · · · , n
alors le problème dual est

min P m
P
i=1 bi yi
m
Scq i=1 aij yi > cj ∀j = 1, · · · , n
yi > 0 ∀i = 1, · · · , m
On observe que le dual d'un problème de maximisation est un problème de minimisation. Pour
chaque contrainte du primal, on a une variable du dual (m variables duales). De façon symé-
trique, à chaque contrainte du dual correspond une variable du primal (n variables primales).

Comme vu dans l'exemple précédent, toute solution du dual donne une borne supérieure sur la
valeur optimale du primal. En eet

Pn Pn
( m
P
j=1 cj xj 6 j=1  i=1 aij yi )
xj
Pm Pn
= i=1 j=1 aij xj yi
Pm
6 i=1 bi yi

Par conséquent, si on obtient une solution réalisable primale (x∗1 , · · · , x∗n ) et une
solution réalisable duale (y1∗ , · · · , ym∗ ) telle que
n
X m
X
cj x∗j = bi yi∗
j=1 i=1

alors on peut conclure que ces deux solutions sont optimales !

Grâce au théorème de dualité forte ci-dessous, on peut même aller plus loin :

Théorème 2.8.1 Théorème de dualité forte

Si le problème primal a une solution optimale (x∗1 , · · · , x∗n ), alors le problème dual admet une
∗ ∗
solution optimale (y1 , · · · , ym ) telle que

n
X m
X
cj x∗j = bi yi∗
j=1 i=1

2.8.3 Propriétés
Proposition 2.8.2 Le dual du dual est le primal.

Démonstration : Partons du dual d'un PL mis sous forme canonique :

Pm
min Pmi=1 bi yi
Scq i=1 aij yi > cj ∀j = 1, · · · , n
yi > 0 ∀i = 1, · · · , m

36
qui est équivalent à

max P m
P
i=1 (−bi )yi
m
Scq i=1 (−aij )yi 6 −cj ∀j = 1, · · · , n
yi > 0 ∀i = 1, · · · , m
Construisons le dual :

Pn
min −c x
Pnj=1 j j
Scq j=1 −a ij xj > −bi ∀i = 1, · · · , m
xj > 0 ∀j = 1, · · · , n
qui est équivalent à

Pn
max cx
Pnj=1 j j
Scq j=1 ij xj 6 bi ∀i = 1, · · · , m
a
xj > 0 ∀j = 1, · · · , n
ce qui correspond bien au primal. 

Théorème 2.8.3 Etant donné un problème primal (P ) et son problème dual (D), une et une
seule des 3 situations suivantes peut avoir lieu :
 Les deux problèmes possèdent chacun des solutions optimales (les valeurs optimales sont
égales)

 Un des problèmes possède une solution réalisable avec un optimum inni (problème non
borné), alors l'autre n'a pas de solution réalisable (problème non réalisable)

 Aucun des deux problèmes n'a de solution réalisable.

2.8.4 Construction du dual

Voici des exemples de problèmes primaux associés à leur dual :

(D)
(P ) Pm
Pn min Pmi=1 bi yi
max cx
Pnj=1 j j Scq i=1 aij yi = cj ∀j = 1, · · · , n
Scq j=1 ij xj 6 bi ∀i = 1, · · · , m
a
yi > 0 ∀i = 1, · · · , m

(P ) Pn (D) Pm
max cx min
Pnj=1 j j Pmi=1 bi yi
Scq j=1 aij xj 6 bi ∀i = 1, · · · , m Scq i=1 aij yi > cj ∀j = 1, · · · , n
xj > 0 ∀j = 1, · · · , n yi > 0 ∀i = 1, · · · , m

(P ) Pn (D)
max cx
Pnj=1 j j
Pm
min Pmi=1 bi yi
Scq j=1 aij xj = bi ∀i = 1, · · · , m Scq i=1 aij yi > cj ∀j = 1, · · · , n
xj > 0 ∀j = 1, · · · , n

37
Exemple : Le dual du problème suivant
max 6x1 − x2 + 13x3
Scq 3x1 + x2 + 2x3 = 7
5x1 − x2 6 6
x2 + x3 > 2
x1 > 0 x2 6 0
est

min 7y1 + 6y2 + 2y3

Scq 3y1 + 5y2 > 6
y1 − y2 + y3 6 −1
2y1 + y3 = 13
y2 > 0 y3 6 0

2.8.5 Interprétation économique des variables duales

Partons du problème de production suivant : On a deux produits P1 et P2 vendus au prix de 6
et 4 euros l'unité respectivement, qui sont fabriqués en quantité x1 et x2 , et qui nécessitent 3
types de ressources disponibles en quantités limitées.

max 6x1 + 4x2

Scq 3x1 + 9x2 6 81
4x1 + 5x2 6 55
2x1 + x2 6 20
x1 , x2 > 0
La première contrainte représente la contrainte liée à la disponibilité de la ressource R1 . Son
membre de gauche exprime la quantité totale de ressource R1 utilisée an de produire x1 unités
du produit P1 et x2 unités du produit P2 .

Supposons à présent qu'un acheteur se propose de racheter vos ressources R1 , R2 et R3 au prix

de y1 , y2 et y3 euros l'unité respectivement.

 L'entreprise acceptera de lui vendre toutes ses ressources si et seulement si cela lui rap-
porte une recette au moins aussi importante que celle qu'elle obtiendrait en vendant ses
produits.

Pour le produit 1 : il lui rapportait 6 euros l'unité et il nécessitait 3 unités de ressource

R1 , 4 unités de R2 et 2 unités de R3 par unité produite. L'entreprise veut donc que le
prix auquel elle va céder ses matières premières soit tel que la somme de 3 unités de R1 ,
4 de R2 et 2 de R3 soit supérieure à 6 euros.

3y1 + 4y2 + 2y3 > 6

Pour le produit P2 : en appliquant un raisonnement similaire à P1 on obtient l'inégalité :

9y1 + 5y2 + y3 > 4

 L'acheteur, quant à lui, veut acheter le moins cher possible :

min 81y1 + 55y2 + 20y3

38
Ainsi, on obtient le PL dual

min 81y1 + 55y2 + 20y3

Scq 3y1 + 4y2 + 2y3 > 6
9y1 + 5y2 + y3 > 4
y1 , y2 , y3 > 0
Ce qui est le dual du problème original. On voit que les variables duales y1 , y2 et y3 représentent
la valeur des ressources R1 , R2 et R3 respectivement.

2.8.6 Les écarts complémentaires

On va voir ici un résultat qui va nous permettre de tester l'optimalité d'une solution réalisable.
Cette technique sera bien utile pour pouvoir élaborer des techniques de calculs plus complexes,
ou plus simplement, pour passer d'une solution réalisable du primal à la solution correspondante
duale (qui, si elle est réalisable garantit que les solutions primales et duales sont optimales, et
si elle n'est pas réalisable garantit que la solution réalisable primale n'est pas optimale). On
pourra donc choisir d'appliquer la méthode du simplexe au problème primal ou au problème
dual. Voici ce résultat :

Théorème 2.8.4 Soient (x∗1 , x∗2 , · · · , x∗n ) et

∗
(y1∗ , y2∗ , · · · , ym ) sont des solutions optimales pour
le problème primal et le problème dual respectivement si et seulement si on a

m
X
aij yi∗ = cj ou x∗j = 0, j = 1, · · · , n
i=1

et
n
X
aij x∗j = bi ou yi∗ = 0, i = 1, · · · , m
j=1

Démonstration : Pour démontrer ce résultat rappelons que, par le théorème de dualité forte,
si les solutions (x∗1 , x∗2 , · · · , x∗n ) et (y1∗ , y2∗ , · · · , ym
∗
) sont des solutions optimales pour le problème
primal et le problème dual respectivement alors on a

n
X m
X
cj x∗j = bi y i
j=1 i=1

Or, on peut écrire les inégalités suivantes

n n m
! m
X X X X
cj x∗j 6 aij yi∗ x∗j car aij yi∗ = cj
j=1 j=1 i=1 i=1
m n
!
X X
= aij x∗j yi∗
i=1 j=1
Xm
6 bi yi∗
i=1

Comme, dans une solution optimale, il n'y a que des égalités, on veut que les deux inégalités
ci-dessus soient des égalités. Or, ces deux inégalités sont vériées à l'égalité si et seulement si

39
 m
X
aij yi∗ = cj ou x∗j = 0, j = 1, · · · , n
i=1

et n
X
aij x∗j = bi ou yi∗ = 0, i = 1, · · · , m
j=1

Ces conditions s'appellent les conditions de complémentarité. La première condition ex-

prime que, si pour le PL primal, une contrainte n'est pas satisfaite à l'égalité, alors cela veut
dire qu'on pourra supprimer cette contrainte sans que cela ne change la solution optimale. Du
coup, il est logique que la variable duale associée à cette contrainte soit nulle (elle estime son
"prix").

Ces conditions sont particulièrement utiles quand on veut tester si une solution réalisable donnée
pour le primal est optimale ou non. En eet, supposons que pour un PL primal on désire
vérier que la solution (x1 , x2 , · · · , xn ) est optimale. Il faudrait alors vérier que la solution
duale associée est réalisable (alors la solution donnée du primal est optimale) ou non réalisable
(alors la solution donnée du primal n'est pas optimale). An de déterminer la solution duale
associée on dresse le système suivant :

Pm
 Si x∗j > 0 alors i=1 aij yi∗ = cj , j = 1, · · · , n
Pn
 Si j=1 aij x∗j < bi alors yi∗ = 0, i = 1, · · · , m

La solution associée est la solution de ce système.

Exemple : On a le PL suivant
max 18x1 − 7x2 + 12x3 + 5x4 + 8x6
Scq 2x1 − 6x2 + 2x3 + 7x4 + 3x5 + 8x6 6 1
−3x1 − x2 + 4x3 − 3x4 + x5 + 2x6 6 −2
8x1 − 3x2 + 5x3 − 2x4 + 2x6 6 4
4x1 + 8x3 + 7x4 − x5 + 3x6 6 1
5x1 + 2x2 − 3x3 + 6x4 − 2x5 − x6 6 5
x1 , x2 , x3 , x4 , x5 , x6 > 0
Supposons que l'on veuille tester si la solution (2, 4, 0, 0, 7, 0) est optimale. On construit alors
le système :
 Comme x1 > 0, alors on a

2y1∗ − 3y2∗ + 8y3∗ + 4y4∗ + 5y5∗ = 18

 Comme x2 > 0, alors on a

−6y1∗ − y2∗ − 3y3∗ + 2y5∗ = −7

 Comme x5 > 0, alors on a

3y1∗ + y2∗ − y4∗ − 2y5∗ = 0

40
  Comme la deuxième inégalité n'est pas satisfaite à l'égalité on a

y2∗ = 0
 Comme la cinquième inégalité n'est pas satisfaite à l'égalité on a

y5∗ = 0
La résolution de ce système nous donne la solution duale
 
1 5
, 0, , 1, 0
3 3
Nous devons encore vérier que cette solution satisfait les conditions du dual. Cette vérication
est laissée à titre d'exercice.

Pour résoudre ce genre d'exercices, il faut pouvoir résoudre des systèmes d'équations linéaires
non-homogènes. Pour cela, nous rappelons à la section suivante la méthode de Gauÿ pour
résoudre ce genre de systèmes.

2.9 Rappel : Résolutions de systèmes d'équations linéaires

Comme nous l'avons déjà cité à plusieurs reprises dans ce chapitre, il apparaît indispensable
de pouvoir déterminer les solutions d'un système d'équations linéaires. Il existe diérentes mé-
thodes, nous rappelons ici la méthode de Gauÿ.

2.9.1 Systèmes linéaires

De manière plus générale, on étudie des systèmes de m équations linéaires à n inconnues



 a11 x1 + a12 x2 + · · · + a1n xn = b1
 a21 x1 + a22 x2 + · · · + a2n xn

= b2
. . .
. . .

 . . .

 a x + a x + ··· + a x = b
m1 1 m2 2 mn n m

où inconnues du système, les réels a11 , a12 , · · · , amn sont les coe-
x1 , x2 , · · · , xn sont les
cients du système et les nombres b1 , · · · , bm sont les termes indépendants.
Un vecteur (x1 , x2 , · · · , xn ) est une solution du système si (x1 , x2 , · · · , xn ) est une solution de
toutes les équations du système.

Le système est dit homogène lorsque les termes indépendants b1 , b2 , · · · , bm sont tous nuls. Si
l'un d'entre eux est non-nul, alors le système est dit non-homogène.

Par exemple, le vecteur (0, 0, · · · , 0) est une solution du système homogène, mais n'est jamais
une solution du système non-homogène.

Nos objectifs seront successivement de :

41
 1. déterminer si un système donné admet des solutions et, dans le cas armatif, si la solution
est unique ou s'il y a plusieurs solutions.

2. déterminer, si le système possède plusieurs solutions, l'ensemble des solutions.

2.9.2 Méthode des combinaisons linéaires d'équations

Il y a deux méthodes élémentaires de résolution des systèmes linéaires :

 La méthode de substitution.

 La méthode des combinaisons linéaires d'équations.

Nous revoyons ici la seconde méthode.

Toute méthode de résolution comprend deux parties :

1. Une technique de transformation du système qui garantit que le système transformé est
un système équivalent au système initial (c'est-à-dire qui admet les mêmes solutions que
le système initial).

2. Une technique de progression vers la solution

La technique de transformation du système utilisée dans la méthode des combinaisons linéaires

d'équations est basée sur le théorème suivant :

Théorème 2.9.1 Lorsque dans un système d'équations, on remplace une équation par une com-
binaison linéaire d'équations renfermant cette équation, on obtient un système équivalent
au système initial.

L'application de ce théorème garantit l'équivalence du système transformé mais pas la progres-

sion vers la solution.

Exemple :
On désire résoudre le système

 2x2 − x3 = −7 (1)
x1 + x2 + 3x3 = 2 (2)
−3x1 + 2x2 + 2x3 = −10 (3)


Commençons par éliminer x1 : on remplace alors la troisième équation par (3) + 3 × (2).

Le système est équivalent à


 2x2 − x3 = −7 (1)
x1 + x2 + 3x3 = 2 (2)
5x2 + 11x3 = −4 (4)


42
A présent, nous ne travaillons plus sur l'équation (2). Les équations (1) et (4) forment un sys-
tème de deux équations à deux inconnues.

On peut décider d'éliminer x2 . On remplace l'équation (4) par 5 × (1) − 2 × (4). Le système est
équivalent à

 2x2 − x3 = −7 (1)
x1 + x2 + 3x3 = 2 (2)
− 27x3 = −27 (5)


On déduit de (5) que x3 = 1. En injectant cette donnée dans (1) on trouve x2 = −3. En
injectant ces deux données dans (2) on trouve x1 = 2 . La solution de ce système est donc
S : {(2, −3, 1)}.

2.9.3 Erreurs à éviter !

Partons du système suivant :


 (1)
(2)
(3)


Attention : voici un petit lexique des erreurs à éviter !

1. Remplacer deux ou plusieurs équations par une combinaison linéaire de ces équations :

 
 (1) 
Incorrecte : (2) ⇔ (2) − (1)
(3) (3)
 
 
 (1)  (1)
Correcte : (2) ⇔ (2) − (1)
(3) (3)
 

2. Remplacer une équation par une combinaison linéaire de ces équations ne renfermant pas
cette équation

 
 (1)  (1)
Incorrecte : (2) ⇔ (2)
(3) (2) − (1)
 
 
 (1)  (1)
Correcte : (2) ⇔ (2)
(3) (3) − (1)
 

Remplacer arbitrairement des équations par des combinaisons linéaires d'équations ; pra-
tiquement cela revient à commettre simultanément plusieurs des fautes signalées aux deux
premiers points ci-dessus.

43
  
 (1)  (2) − (1)
Incorrecte : (2) ⇔ (3) − (1)
(3) (3) − (2)
 

2.9.4 Forme échelonnée d'un système

Nous rappelons dans cette sous-section quelques dénitions qui nous seront utiles an d'établir
la méthode de Gauÿ.

Dénition 2.9.2 On dit qu'un système linéaire est échelonné si le nombre de coecients
nuls au début de chaque équation est strictement croissant quand on passe d'une équation à
l'équation suivante.

Exemple : Le système suivant, avec a11 6= 0 6= a22 , est échelonné


 a11 x1 + a12 x2 + a13 x3 + a14 x4 = 0
0x1 + a22 x2 + a23 x3 + a24 x4 = 0
0x1 + 0x2 + 0x3 + a34 x4 = 0


Exemple : Le système suivant, avec a32 6= 0, n'est pas échelonné


 a11 x1 + a12 x2 + a13 x3 = 0
0x1 + a22 x2 + a23 x3 = 0
0x1 + a32 x2 + a33 x3 = 0


2.9.5 La méthode d'élimination de Gauÿ

La méthode de Gauÿ se base alors sur l'idée de "transformer" le système de départ en un sys-
tème équivalent dont il est plus simple de décrire l'ensemble des solutions (système échelonné).

Voici les opérations élémentaires que l'on peut eectuer sur le système an d'obtenir un système
équivalent sous forme échelonnée :

 changer l'ordre des équations.

 multiplier une équation par une constante non nulle.
 ajouter à une équation un multiple d'une autre équation.
Toutes ces modications ne modient pas l'ensemble des solutions.

Exemple : On désire résoudre le système


 2x2 − x3 = −7
x1 + x2 + 3x3 = 2
−3x1 + 2x2 + 2x3 = −10


On peut écrire ce système sous forme matricielle :

44
     
0 2 −1 x1 −7
 1 1 3   x2  =  2 
−3 2 2 x3 −10
Qu'on peut encore écrire de façon plus compacte :

 
0 2 −1 −7
 1 1 3 2 
−3 2 2 −10
On appelle cette matrice, la matrice augmentée du système.
La méthode de Gauÿ consiste à appliquer des opérations élémentaires sur la matrice augmentée
an d'obtenir un système équivalent échelonné :

   
0 2 −1 −7 −3 2 2 −10
 1 1 3 2  ⇐⇒L1 ↔L3  1 1 3 2 
−3 2 2 −10 0 2 −1 −7
 
1 −2/3 −2/3 10/3
L1 ←L1 /(−3) 
⇐⇒ 1 1 3 2 
0 2 −1 −7
 
1 −2/3 −2/3 10/3
L2 ←L2 −L1 
⇐⇒ 0 5/3 11/3 −4/3 
0 2 −1 −7
 
1 −2/3 −2/3 10/3
L2 ←L2 /(5/3) 
⇐⇒ 0 1 11/5 −4/5 
0 2 −1 −7
 
1 −2/3 −2/3 10/3
L3 ←L3 −2L2 
⇐⇒ 0 1 11/5 −4/5 
0 0 −27/5 −27/5
On a maintenant un système équivalent au système de l'énoncé mais sous une forme échelonnée.
Le système sous cette forme est simple à résoudre et nous mène à la solution

S : {(2, −3, 1)}

2.9.6 Implémentation de la méthode de Gauÿ

La méthode de Gauÿ donne un algorithme ecace pour résoudre les systèmes linéaires. On
démarre du système dont on numérote les lignes


 a11 x1 + a12 x2 + . . . + a1n xn = b1 (L1)
a21 x1 + a22 x2 + . . . + a2n xn = b2 (L2)


.
.

 .

 a x + a x + ... + a x = b
m1 1 m2 2 mn n m (Lm)

Pour garder une trace des opérations eectuées sur les lignes, on peut écrire en marge des
calculs les opérations eectuées, comme par exemple

(L10 ) = (L1) − 2(L2) + 6(L3)

45
pour signier que dans le nouveau système équivalent, la nouvelle première ligne est la combi-
naison décrite des autres lignes.
Pour démarrer la méthode, on choisit de mettre en première ligne une équation dont le
coecient multipliant x1 est non nul et on prend la matrice augmentée (A|b) du système écrit
dans cet ordre.

Remarque : Dans le cas inintéressant où tous les coecients multipliant x1 sont nuls, la
première colonne est identiquement nulle (on peut donc la supprimer) et x1 est indéterminé.
On démarre dans ce cas la méthode en renumérotant les inconnues et en choisissant la première
inconnue de sorte qu'elle apparaisse dans au moins une équation du système.

La première opération d'échelonnement est alors

(L10 ) = (L1)/a11 .
Ceci fait apparaître dans la matrice un 1 dans le coin supérieur gauche et la première ligne
devient

a12 a1n b1
x1 + x2 + . . . + xn = (L10 )
a11 a11 a11
La deuxième opération consiste à utiliser la nouvelle première ligne pour faire apparaître
des zéros dans la première colonne de la matrice (A|b), de la deuxième à la dernière ligne. On
fait donc les opérations

(L20 ) = (L2) − a21 (L10 ), . . . , (Lm0 ) = (Lm) − am1 (L10 ).

L'étape suivante consiste à mettre en deuxième ligne une équation dont le coecient de x2
est non nul (si il y en a une) puis à répéter les étapes précédentes pour faire apparaître
• un 1 en position (2, 2) de la matrice du système par l'opération

(L200 ) = (L20 )/a022 ;

• des zéros dans la deuxième colonne de la matrice, de la troisième à la dernière ligne via les
opérations
(L300 ) = (L30 ) − a32 (L200 ), . . . , (Lm00 ) = (Lm0 ) − am2 (L200 ).
Si aucune équation ne contient l'inconnue x2 , on met en deuxième place une équation débutant
par l'inconnue du plus petit indice i qui apparaît dans le système.

Les opérations à eectuer sont alors

(L200 ) = (L20 )/a02i ,

ce qui produit un 1 en position (2, i) de la matrice du système ;

(L300 ) = (L30 ) − a3i (L200 ), . . . , (Lm00 ) = (Lm0 ) − ami (L200 )

qui produit des zéros dans la colonne i de la matrice, de la troisième à la dernière ligne.

On recommence successivement ces étapes sur les lignes suivantes pour faire apparaître la struc-
ture échelonnée.

La procédure s'achève lorsqu'on a épuisé toutes les variables ou toutes les équations. On se
retrouve alors avec
• des équations qui ne comportent plus d'inconnues :
46
  les équations du type 0=0 peuvent être supprimées,
 si une équation est du type 0 = constante 6= 0, le système n'a pas de solution.
• des équations qui comportent (au moins) une inconnue multipliée par un co-
ecient non nul.
Parmi ces équations, on commence à traiter la dernière équation du système :
 si elle ne contient qu'une seule inconnue, celle-ci est alors xée par l'équation ;
 pour une équation qui comporte plus d'une inconnue, on exprime l'inconnue ayant le
plus petit indice en fonction des autres inconnues (qui apparaissent alors comme des
paramètres arbitraires).
On substitue maintenant les valeurs déjà déterminées par la dernière équation dans les équa-
tions précédentes et on traite l'avant-dernière équation comme on vient de traiter la dernière.

On continue ainsi jusqu'à être remonté à la première équation.

La solution est alors exprimée en fonction des paramètres arbitraires, ce qui permet d'écrire
une base du système homogène associé et une solution particulière.

Considérons le système

 2x + y − z = 8
−3x − y + 2z = −11
−2x + y + 2z = −3


Écrivons le système augmenté

 
2 1 −1 8
 −3 −1 2 −11 
−2 1 2 −3
et divisons la première ligne par 2 (L10 = (L1)/2), ce qui donne
 
1 1/2 −1/2 4
 −3 −1 2 −11  .
−2 1 2 −3
La première ligne peut maintenant servir à annuler la première composante dans les deuxième
0 0 0 0
et troisième lignes (L2 = L2 + 3 ∗ L1 et L3 = L3 + 2 ∗ L1 ), ce qui donne

 
1 1/2 −1/2 4
 0 1/2 1/2 1  .
0 2 1 5
00
Multiplions la deuxième ligne (L2 = 2 ∗ L20 ) et utilisons-la pour éliminer la deuxième inconnue
dans la troisième ligne. Nous obtenons

 
1 1/2 −1/2 4
 0 1 1 2 .
0 0 −1 1
La matrice est maintenant échelonnée et le système à résoudre est

 x + y/2 − z/2 = 4
y+z =2
−z = 1


47
ce qui mène à la solution (2, 3, −1).
Autre exemple :

   
1 3 1 9 1 3 1 9
 1 1 −1 1  →  0 −2 −2 −8 
3 11 5 35 0 2 2 8
 
1 3 1 9
→  0 −2 −2 −8 
0 0 0 0
 
1 0 −2 −3
→  0 1 1 4 
0 0 0 0
Les équations utiles dans le système échelonné sont

x − 2z = −3 et y + z = 4.
Dans la deuxième équation, laissons z comme paramètre libre. On en déduit la forme générale
des solutions

{(2z − 3, 4 − z, z)|z ∈ R} = (−3, 4, 0) + h(2, −1, 1)i.

Un exemple de système impossible :

   
1 2 1 1 1 2 1 1
 1 −1 2 0  →  1 −1 2 0  .
2 1 3 2 0 0 0 1
Le système équivalent est obtenu en soustrayant de la troisième ligne, les deux premières. Le
rang du système homogène est 2 alors que celui du système augmenté est 3.

La dernière ligne correspond à l'équation

0x1 + 0x2 + 0x3 = 1,

ce qui est bien entendu impossible.

48
2.10 Exercices
1. Déterminez pour chaque modèle suivant s'il s'agit d'un programme linéaire ou non, sa-
chant que les yi représentent des variables, et que tous les autres symbôles représentent
des constantes.

a)
min α(3y1 + 11y4 )
P5
scq j=1 dj yj 6 β
yj > 0 ∀j = 1, · · · , 9
b)
min α(3y1 + 11y4 )2
P5
scq j=1 dj yj 6 β
yj > 0 ∀j = 1, · · · , 9
c)
P9
max j=1 yj
scq y1 y2 6 100
yj > 1 ∀j = 1, · · · , 9

Résolution graphique

2. Dessinez dans un repère les diérents domaines réalisables correspondant aux systèmes
suivants :

 
 x1 + x2 6 2  x1 + x2 6 2
(a) 3x1 + x2 > 3 (b) 3x1 + x2 = 3
x1 , x2 > 0 x1 , x2 > 0
 

3. Déterminez graphiquement pour chaque programme linéaire suivant s'il possède une
unique solution optimale, ou s'il en existe plusieurs.

max 3x1 + 3x2 max 3x1 + x2

(a) scq x1 + x2 6 2 (b) scq x1 + x2 6 2
x1 , x2 > 0 x1 , x2 > 0

max 2x1 − 4x2

(c) scq x1 + x2 6 2
x1 , x2 > 0

4. Déterminez graphiquement pour chaque programme linéaire suivant s'il est réalisable ou
non.

max 3x1 + x2 max 3x1 + x2

scq x1 + x2 6 2 scq x1 + x 2 6 2
(a) (b)
x1 + x2 > 1 x1 + x 2 > 3
x1 , x2 > 0 x1 , x2 > 0

49
 max 3x1 + x2
scq x1 + x2 6 1, 8
(c)
x1 + x2 > 1, 2
x1 , x2 ∈ Z+

5. Déterminez graphiquement pour chaque programme linéaire suivant s'il est borné ou non.

max −3x1 + x2 max 3x1 + x2

(a) scq −x1 + x2 6 1 (b) scq x1 + x2 6 1
x1 , x2 > 0 x1 , x2 > 0

6. Dans la gure suivante, le domaine réalisable est représenté par le polygone non-borné
blanc. Indiquez pour chaque point donné s'il peut s'agir d'un point optimal, d'un point
optimal unique, d'un point non optimal.

7. Une usine fabrique les produits P1 et P2 . Pour cela, elle utilise les matières premières M1 ,
M2 et M3 , à raison de
 7 tonnes de M1 , 4 tonnes de M2 et 3 tonnes de M3 par unité produite de produit P1 .
 2 tonnes de M1 , 8 tonnes de M2 et 11 tonnes de M3 par unité produite de produit P2 .
Elle dispose mensuellement de 80 tonnes de M1 , de 60 tonnes de M2 et de 64 tonnes de
M3 . Le bénéce net est de 4000 euros par unité de P1 et de 5000 euros par unité de P2 .
Quelles quantités (non nécessairement entières) des deux produits l'entreprise doit-elle
fabriquer pour maximiser son bénéce ?

a) Donner une modélisation de ce problème sous la forme d'un programme linéaire.

b) Déterminer une solution optimale en utilisant une résolution graphique.

8. L'entreprise Top Toys souhaite faire une nouvelle campagne de publicité. La diusion
d'un spot publicitaire à la radio coûte 300 euros et la diusion d'un spot publicitaire à la

50
 télé coûte 2000 euros. L'entreprise dispose d'un budget total de 20 000 euros pour sa cam-
pagne. Par ailleurs, l'entreprise souhaite que chaque média soit susamment représenté,
c'est pourquoi elle décide que le coût alloué pour chaque média ne peut pas dépasser
80% du budget total (c'est-à-dire que le coût total des publicités à la radio ne peut pas
dépasser 80% du budget total, idem pour les publicités à la télévision). Il a été estimé
que la première diusion du spot à la radio touchera 5000 personnes, et chaque diusion
supplémentaire touchera 2000 nouvelles personnes en plus. La première diusion du spot
à la télévision touchera elle 4500 personnes, et chaque diusion supplémentaire touchera
3000 nouvelles personnes en plus. Combien de diusions doit-on attribuer à la radio et à
la télévision an de toucher le plus grand nombre de personnes ?

a) Donner une modélisation de ce problème sous la forme d'un programme linéaire.

b) Déterminer une solution optimale en utilisant une résolution graphique.

9. La société interlimonade fabrique diverses boissons depuis de nombreuses années. La

direction envisage le lancement de deux nouveaux produits : la limonade El Sol et le
jus de fruit Delicioso. Le directeur de la production est chargé d'organiser la production
de ces deux produits de manière à maximiser le prot réalisé tout en tenant compte de
contraintes existantes. En fait, le dossier qu'on lui a remis contient les données suivantes :
les coûts de production estimés de El Sol et Delicioso sont respectivement de 0, 2 euros
et 0, 4 euros par bouteille. Les frais de distribution s'élèvent à 0, 3 euros et 0, 5 euros par
bouteille respectivement. La société doit couvrir des frais xes mensuels d'un montant de
200 000 euros.

Une étude poussée du marché a permis de situer le prix de la limonade à 0, 7 euros et

celui du jus de fruit à 1, 2 euros. Cette même étude a donné une estimation de la demande
mensuelle qui se situe entre 300 000 et 375 000 bouteilles pour la limonade et entre 150
000 et 250 000 bouteilles pour le jus. L'entreprise dispose mensuellement de 1 000 000 de
bouteilles.

Les fruits sont d'importantes matières premières pour la fabrication des rafraîchissements.
Le stock mensuel de fruits s'élève à 300 tonnes. La fabrication d'un litre de jus requiert
2 kg de fruits et celle d'un litre de limonade 0,5 kg. Les bouteilles ont une contenance de
25 cl.

La préparation de 1000 litres de limonade nécessite 1h de temps en machine, et 2h pour

1000 litres de jus. L'entreprise travaille 25 jours par mois. Les diérentes unités de pré-
paration ont une capacité de production de 20 heures par jour.

La mise en bouteille s'eectue à la cadence de 3000 bouteilles par heure. La chaîne de

mise en bouteille peut fonctionner 7 heures par jour (la huitième heure étant consacrée à
la mise en route et au nettoyage).

Modélisez ce problème

Formes d'un programme linéaire

10. Mettez le programme linéaire suivant sous sa forme standard :

51
 max x1 + x2
scq x1 + x2 6 10
x1 , x2 > 0

11. Mettez le programme linéaire suivant sous sa forme canonique :

max x1 + x2
scq x1 + x2 = 10
x1 , x2 > 0

12. Mettez le programme linéaire suivant sous sa forme canonique, et ensuite sous sa forme
standard :

max x1 + x2
scq x1 + x2 > 10
x1 , x2 > 0

13. Mettez le programme linéaire suivant sous sa forme canonique, et ensuite sous sa forme
standard :

max x1 + x2
scq x1 + x2 > 10
x1 > 0
x2 6 0

14. Mettez le programme linéaire suivant sous sa forme standard :

max 9x1 + 6x2

scq 2x1 + x2 > 10
x1 > 50
x1 + x2 = 40
100 > x1 + 2x2 > 15
x1 , x2 6 0

15. Mettez le programme linéaire suivant sous sa forme standard :

min 15(2x1 + 8x2 ) − 4x3

scq 2(10 − x1 ) + x2 + 5(9 − x3 ) > 10
x1 + 2x3 > x3
2x2 + 18x3 = 50
x1 , x2 , x3 6 0

Solutions de base

52
16. Supposons qu'on étudie le programme linéaire dont les contraintes sont les suivantes :

4x1 − x2 + x3 = 1
3x1 + 2x2 − 2x3 = 8
x1 , x2 , x3 > 0
Déterminez la solution de base correspondant à la base formée de x1 et x2 .

17. Soit le programme linéaire suivant mis sous sa forme canonique :

max 12x1 + 9x2

scq x1 6 1000
x2 6 1500
x1 + x2 6 1750
4x1 + 2x2 6 4800
x1 , x2 > 0
a) Mettez ce programme sous sa forme standard.

b) Déterminez une base correspondant à une solution de base réalisable.

c) Déterminez une base correspondant à une solution de base non-réalisable.

18. L'ensemble des contraintes d'un programme linéaire mis sous sa forme standard est donné
par

−x1 + x2 − x3 = 0
x1 + x4 = 2
x2 + x5 = 3
x1 , x 2 , x 3 , x 4 , x 5 > 0
a) En supposant que les variables x 3 , x4 et x5 sont des variables d'écart qui ont été
ajoutées an de mettre le programme sous sa forme standard, dessinez la domaine
réalisable en fonction des variables originelles x1 et x2 .
b) Déterminez la solution correspondant aux diérents ensembles de variables en base
suivants, et déterminez si la solution de base correspondante est réalisable :
 B1 = {x3 , x4 , x5 }
 B2 = {x2 , x4 , x5 }
 B3 = {x1 , x2 , x5 }
 B4 = {x1 , x2 , x4 }
 B5 = {x1 , x3 , x5 }
c) Vériez, pour chaque solution de base déterminée au point précédent, que les solutions
de base réalisables correspondent à un sommet du polygone dessiné au point a), et
que les solutions de base non réalisables se trouvent en dehors du polygone.

L'algorithme du simplexe
19. Résoudre par l'algorithme du simplexe le programme linéaire suivant :

max x 1 + x2
scq x1 + 3x2 6 3
x 1 + x2 6 2
3x1 + x2 6 3
x1 , x2 > 0

53
20. Résoudre par l'algorithme du simplexe le programme linéaire suivant :

max x1 + 3x2 − x3
scq 2x1 + 2x2 − x3 6 10
3x1 − 2x2 + x3 6 10
x1 − 3x2 + x3 6 10
x1 , x2 , x3 > 0

21. Résoudre par l'algorithme du simplexe le programme linéaire suivant :

min 2x1 − 3x2 − 4x3 + x4

scq x1 + 3x2 − x3 − 3x4 > −2
2x1 + x2 + x3 + 3x4 6 8
−4x2 + 2x3 + 6x4 6 4
x1 , x2 , x3 , x4 > 0

22. Résoudre par l'algorithme du simplexe le programme linéaire suivant :

min −10x1 + x2
scq −5x1 + 3x2 6 15
3x1 − 5x2 6 8
x1 , x2 > 0

23. Résoudre par l'algorithme du simplexe le programme linéaire suivant :

max 4x1 + 5x2

scq −x1 + x2 6 4
x1 − x2 6 10
x1 , x2 > 0

L'algorithme du simplexe en deux phases

24. Résoudre par l'algorithme du simplexe le programme linéaire suivant :

max 3x1 + 5x2

scq x1 6 4
2x2 = 12
3x1 + 2x2 > 18
x1 , x2 > 0

25. Résoudre par l'algorithme du simplexe le programme linéaire suivant :

max 3x1 + x2
scq x1 − x2 6 −1
−x1 − x2 6 −3
2x1 + x2 6 4
x1 , x2 > 0

54
26. Résoudre par l'algorithme du simplexe le programme linéaire suivant :

max 3x1 + x2
scq x1 − x2 6 −1
−x1 − x2 6 −3
2x1 − x2 6 2
x1 , x2 > 0

27. Résoudre par l'algorithme du simplexe le programme linéaire suivant :

max 9x1 + x2
scq −2x1 + x2 > 2
x2 6 1
x1 , x2 > 0

28. Résoudre par l'algorithme du simplexe le programme linéaire suivant :

min 2x1 + 8x2

scq x 1 + x2 6 2
x1 > 3
x1 , x2 > 0

Dualité

29. Déterminez le dual du problème suivant :

min 30x1 + 5x3

scq x1 − x2 + x3 > 1
3x1 + x2 = 4
4x2 + x3 6 10
x1 , x2 , x3 > 0

30. Déterminez le dual du problème suivant :

max 10x1 + 9x2 − 6x3

scq 2x1 + x2 > 3
5x1 + 3x2 − x3 6 15
x2 + x3 = 1
x1 , x2 , x3 > 0

31. Déterminez le dual du problème suivant :

min 7x1 + 44x3

scq −2x1 − 4x2 + x3 6 15
x1 + 4x2 > 5
5x1 − x2 + 3x3 = −11
x1 6 0 , x3 > 0

55
32. Démontrez que le dual du dual du problème suivant est équivalent à ce problème :

max 6x1 − x2 + 13x3

scq 3x1 + x2 + 2x3 = 7
5x1 − x2 6 6
x2 + x3 > 2
x1 > 0 , x2 6 0

33. Considérons le programme linéaire suivant :

max 6x1 + x2
scq x1 6 1
2x1 + x2 6 4
x1 , x2 > 0
a) Déterminez le dual de ce problème.

b) Résolvez les deux problèmes graphiquement.

c) Vériez que les valeurs optimales sont bien égales.

34. Déterminez graphiquement que le programme linéaire suivant est non-borné et vériez ce
que cela implique pour son dual :

max x1
scq −x1 + x2 > 1
x2 > 2
x1 , x2 > 0

35. Déterminez graphiquement que le dual du programme linéaire suivant est non-borné et
vériez ce que cela implique pour le primal :

min x1 + x2
scq 2x1 + x2 > 3
5x1 + x2 6 0
x1 , x2 > 0

36. Un vieux menuisier fabrique des portes en bois de 2 dimensions diérentes. Il dispose
pour ce faire de grands panneaux en bois qu'il scie en 3, pour réaliser des portes grand
format et en 4 pour réaliser des portes petit format.

Les travaux de gros-oeuvre et de gnolage lui prennent 1h par porte grand format et
2h par porte petit format.

Un fournisseur lui livre 30 panneaux par mois.

Pour satisfaire la demande de sa clientèle, le menuisier doit travailler 6 heures par jour à
raison de 20 jours par mois.

56
 Sachant que cette production artisanale lui rapporte 16 euros par porte grand format et
20 euros par porte petit format, quelle quantité de chaque article doit-il fabriquer par
mois ?

a) Résolvez le problème par la méthode du simplexe.

b) Formulez le problème dual et interprétez ses variables.

37. A l'occasion du mariage de votre soeur, votre père a décidé d'organiser une soirée. Il a
à sa disposition deux listes de personnes auxquelles il doit lancer des invitations : une
liste d'amis et une liste de relations qu'il serait de bon ton d'inviter. Inviter un ami lui
procure 2 unités de satisfaction et lui coûte 150 euros (ses amis sont de joyeux lurons)
alors qu'inviter une relation lui procure 1 unité de satisfaction mais ne lui coûte que 100
euros. Il veut retirer de sa soirée au moins 90 unités de satisfaction mais ne veut en aucun
cas dépenser plus de 7500 euros. Il désire aussi avoir au moins autant d'amis dans la salle
que de relations et veut faire participer le plus de monde possible à sa joie. Sachant que
la salle ne peut contenir plus de 100 personnes, quel est le nombre de personnes dans les
deux listes que vous proposeriez à votre père d'inviter ? Formulez le problème dual.

38. Soit le PL suivant

max 7x1 + 6x2 + 5x3 − 2x4 + 3x5

Scq x1 + 3x2 + 5x3 − 2x4 + 2x5 6 4
4x1 + 2x2 − 2x3 + x4 + x5 6 3
2x1 + 4x2 + 4x3 − 2x4 + 5x5 6 5
3x1 + x2 + 2x3 − x4 − 2x5 6 1
x1 , x2 , x3 , x4 , x5 > 0
4 2 5
Testez à l'aide des conditions de complémentarités si la solution (0, , , , 0) est optimale
3 3 3
ou non.

57
39. Soit le PL suivant

max 4x1 + 5x2 + x3 + 3x4 − 5x5 + 8x6

Scq x1 − 4x3 + 3x4 + x5 + x6 6 1
5x1 + 3x2 + x3 − 5x5 + 3x6 6 4
4x1 + 5x2 − 3x3 + 3x4 − 4x5 + x6 6 4
−x2 + 2x4 + x5 − 5x6 6 5
−2x1 + x2 + x3 + x4 + 2x5 + 2x6 6 7
2x1 − 3x2 + 2x3 − x4 + 4x5 + 5x6 6 5
x1 , x2 , x3 , x4 , x5 , x6 > 0
5 7 1
Testez à l'aide des conditions de complémentarité si la solution (0, 0, , , 0, ) est opti-
2 2 2
male ou non.

40. Résoudre le PL suivant

max −x1 − 2x2

Scq −3x1 + x2 6 −1
x1 − x2 6 1
−2x1 + 7x2 6 6
9x1 − 4x2 6 6
−5x1 + 2x2 6 −3
7x1 − 3x2 6 6
x1 , x2 > 0
Suggestion : des deux formulations (primale et duale), utilisez celle qui demande le moins
de calculs.

58
Chapitre 3
La gestion des stocks

Dans ce chapitre nous allons nous focaliser sur une classe bien précise de problèmes de recherche
opérationnelle : les problèmes liés à la gestion des stocks.

3.1 Introduction
En guise d'introduction nous allons étudier diérentes solutions du problème suivant, an de
nous convaincre de la nécessité d'optimiser méthodiquement la manière de gérer les stocks.

Exemple : Une entreprise qui fabrique des moteurs électriques doit faire face à une demande
approximativement constante de 3600 moteurs par an.
Un des composants de ces moteurs est acheté chez un fournisseur qui accepte une commande de
n'importe quelle quantité à n'importe quel moment mais avec des frais de mise en route de 2200
euros par commande (coût de lancement). D'autre part, le coût de stockage de ces composants
par l'entreprise est évalué à 26 euros par unité et par an. Les ruptures de stock sont exclues car
l'entreprise ne peut se permettre de ne pas livrer un moteur à ses clients.
La question est de déterminer la quantité de composants que l'entreprise doit commander en
une fois pour minimiser ses coûts.

Remarquons que le coût annuel d'approvisionnement est constitué essentiellement des coûts de
lancement et des coûts de stockage, nous donnant ainsi la formule générale :

coût annuel d'approvisionnement =

coût de lancement + coût de stockage

Remarquons que pour déterminer les coûts de stockage sur une période, il est important de
déterminer quel sera le stock moyen durant toute la période où la marchandise sera stockée.
Pour cela, représentons la situation sur un graphique. On commence avec un stock de Q unités
(la quantité stockée est donnée sur l'axe des ordonnées) qui diminue linéairement en fonction
du temps (représenté par l'axe des abscisses). La variable T représente le temps qu'il faut pour
écouler la quantité Q.
Q
On peut se convaincre sur le graphique qu'en moyenne on va stocker unités durant une
2
période T. Ceci va nous aider à calculer le coût annuel d'approvisionnement.

59
Tentons une première solution pour notre problème : on pourrait commander 3600 composants
en début d'année. Ceci réduirait au minimum les frais liés aux coûts de lancement, mais maxi-
miserait les coûts liés au stockage de la marchandise. Le coût annuel d'approvisionnement dans
ce cas serait égal à :

3600
C = 2200 + · 26
2
= 2200 + 46800 = 49000 euros

Cette solution reviendrait à un total de 49 000 euros par an.

Calculons à présent le coût annuel d'approvisionnement correspondant à la solution qui consis-

3600
terait à passer une commande de pièces en début de chaque mois :
12

3600
C = 2200 · 12 + · 26
2 · 12
= 26400 + 3900 = 30300 euros

On voit que le coût de cette nouvelle solution est signicativement plus bas que celui de la
solution précédente. Il apparaît naturellement que la stratégie à adopter ne doit pas être déter-
minée par le fruit du hasard. Au cours de ce chapitre, vous pourrez déterminer que la solution
optimale de ce problème est de passer une commande tous les 79 jours environ, et que le coût
total d'approvisionnement lié à cette solution est de 20 294 euros. Il y a donc moyen de faire
de belles économies pour l'entreprise à utiliser des moyens d'optimisation !

3.2 Rappels sur l'optimisation des fonctions d'une variable

Dans cette section nous faisons un bref rappel sur les outils d'optimisation des fonctions d'une
variable. Pour commencer, nous allons dénir les diérents types d'extrema d'une fonction.
Observons le graphique suivant :

60
  En x = a, il y a un minimum absolu/global.
 En x = b, il y a un maximum local.
 En x = c, il y a un minimum local.
 En x = d, il y a un maximum absolu/global.

A présent, donnons les dénitions formelles de ces diérents points observés :

Dénition 3.2.1 f admet un minimum absolu en x=a si et seulement si

f (x) > f (a), ∀x ∈ Dom(f )

Dénition 3.2.2 f admet un minimum local en x=c si et seulement si il existe un inter-

valle I contenant c tel que

f (x) > f (c), ∀x ∈ I, x ∈ Dom(f )

Dénition 3.2.3 f admet un maximum absolu en x=d si et seulement si

f (x) 6 f (d), ∀x ∈ Dom(f )

Dénition 3.2.4 f admet un maximum local en x=b si et seulement si il existe un inter-

valle I contenant b tel que

f (x) 6 f (b), ∀x ∈ I, x ∈ Dom(f )

On rassemble tous ces types de points sous l'expression points extrêmes ou extrema.

Remarque : Dans la suite de ce chapitre, nous chercherons à caractériser les extrema locaux
uniquement.

Tentons à présent de trouver une caractéristique qui nous permettra de déterminer les extrema
locaux d'une fonction d'une variable. Observons la gure suivante :

61
On observe que la tangente à la courbe y = f (x) en c (maximum local) et en d (minimum local)
est horizontale, et donc que

f 0 (c) = 0 et f 0 (d) = 0.

Dénition 3.2.5 Un point c intérieur au domaine de f tel que f 0 (c) = 0 est appelé point
stationnaire.

On observe donc que pour avoir un point extrême local (attention, ceci n'est pas vrai pour les
extrema absolus de façon générale), il faut que ce point soit un point stationnaire. Ceci nous
mène à la proposition suivante :

Proposition 3.2.6 Soit f dérivable sur un intervalle I, soit c un point intérieur de I . Une
condition nécessaire pour que f admette un point maximum local ou minimum local en x = c
est que

c soit un point stationnaire de f, càd f 0 (c) = 0

Autrement dit :

c donne un max/min local à f ⇒ f 0 (c) = 0

Cette proposition est connue sous le nom de condition nécessaire de premier ordre.
ATTENTION : Il s'agit bien d'une condition nécessaire, mais malheureusement pas su-
sante. Cela signie que le fait de répérer qu'un point est un point stationnaire ne sut pas à
pouvoir établir le fait que ce point est un extrema local. En eet, il existe des points station-
3
naires qui ne sont pas des extrema ! Analysons la fonction f (x) = x dont le graphe est donné
0 2
ci-dessous. La dérivée de cette fonction est f (x) = 3x qui s'annule en x = 0. On peut donc
conclure qu'en x = 0 on a un point stationnaire. Mais, comme on peut l'observer sur le graphe,
il n'y a ni maximum local ni minimum local en x = 0. Il s'agit simplement d'un point où la
tangente au graphe en ce point est horizontale.

Nous devons donc nous demander comment distinguer un point stationnaire qui correspond à
un extremum local de celui qui n'y correspond pas.

Observons les graphiques suivants :

62
On observe sur ces graphiques que lorsque le point stationnaire correspond à un maximum local,
il faut nécessairement que juste avant ce maximum la fonction soit croissante (et donc sa dérivée
doit être positive ou nulle), et que juste après la fonction soit décroissante (et donc sa dérivée
doit être négative ou nulle). Avec un même raisonnement, si le point stationnaire correspond à
un minimum local, la dérivée de la fonction doit être négative juste avant ce point, puis positive
3
juste après. Observons également que pour le point stationnaire de la fonction x , on n'observe
pas un tel changement dans le signe de la dérivée. Nous tenons donc ici une caractéristique
propre aux points stationnaires qui correspondent à des extrema : leur dérivée doit changer de
signe ! Ceci nous amène à la proposition suivante :

Proposition 3.2.7 Soit f dérivable sur son domaine Dom(f ). Soit c un point intérieur de
Dom(f ) tel que f 0 (c) = 0. Soit I un intervalle contenu dans Dom(f ) et contenant c.
 f admet un maximum local en c si

f 0 (x) > 0 ∀x ∈ I et x6c

f 0 (x) 6 0 ∀x ∈ I et x>c

 f admet un minimum local en c si

63
 f 0 (x) 6 0 ∀x ∈ I et x6c
f 0 (x) > 0 ∀x ∈ I et x>c

Cette proposition est connue sous le nom de condition susante du premier ordre (car
elle fait intervenir la dérivée première).
Nous avons à présent une caractéristique qui va nous permettre de déterminer les extrema
locaux d'une fonction. Toutefois, cette condition fait que nous devons déterminer le tableau de
signe de la fonction dérivée, ce qui peut, pour certaines fonctions, être dicile à déterminer.
Nous allons tenter de trouver une autre condition susante. Pour cela, observons les graphiques
suivants :

f 0 (c) = 0 et ∃I tel que f 0 (c) = 0 et ∃I tel que

f 00 (x) 6 0 ∀x ∈ I . f admet f 00 (x) > 0 ∀x ∈ I . f admet
un max local en c. un min local en c.

On constate que si le point stationnaire correspond à un maximum local, alors la fonction

présente une concavité vers le bas (et donc une dérivée seconde strictement négative en ce
point) alors que si le point stationnaire correspond à un minimum local, la fonction présente
une concavité vers le haut (et donc une dérivée seconde strictement positive en ce point). Pour
3
le cas du point stationnaire de la fonction x , on constate que sa dérivée seconde en ce point
est nulle.

Proposition 3.2.8 Soit f dérivable sur un intervalle I. Soit c un point intérieur de I.

 x=c est un maximum local si

f 0 (c) = 0 et f 00 (c) < 0

 x=c est un minimum local si

f 0 (c) = 0 et f 00 (c) > 0

Cette proposition est connue sous le nom de condition susante du deuxième ordre (parce
qu'elle fait intervenir la dérivée seconde).

Suivant l'expression de la fonction à analyser, on choisira d'utiliser la condition du premier ou

du deuxième ordre. Pour certaines fonctions, le tableau de signes de leur dérivée sera facile
à faire, pour d'autres il sera plus commode d'utiliser le critère faisant intervenir la dérivée
seconde.

64
3.3 Les données des problèmes de gestion des stocks
Les problèmes de gestion des stocks traitent de la diculté de savoir comment gérer le stock
d'une marchandise an de satisfaire les uctuations de la demande. Il faut évidemment garder à
l'esprit que stocker une trop grande quantité engendrera des coûts de stockage importants, mais
stocker trop peu peut perturber la production ou la vente, voire entraîner une rupture de stock.
Il faut donc gérer les stocks et l'approvisionnement avec une grande minutie en minimisant une
fonction de coût. Cette fonction dépendra toujours des élément suivants :

 La demande. Celle-ci peut être

1. Déterministe et constante, c'est-à-dire que la demande reste constante sur une année
(ne varie pas en fonction des mois) et on connaît exactement la quantité demandée
chaque mois.

2. Déterministe et variable, c'est-à-dire que la demande varie suivant le mois de l'année,

mais on connaît les demandes correspondant à chaque mois (par exemple, la consom-
mation de gaz de chauage varie fortement entre les mois d'été et d'hiver, mais on
peut +/− connaître la quantité demandée à l'avance).

3. Aléatoire et constante, c'est-à-dire qu'on sait que la demande reste la même tout au
long de l'année, mais on ne la connaît pas exactement.

4. Aléatoire et variable.

Le premier cas est le plus facile à traiter, le dernier étant le plus complexe.

 Le prix d'achat de la marchandise.

 Les coûts de lancement d'une commande ou d'une fabrication. Ce sont des coûts xes à
payer par commande, et qui ne dépendent pas de la quantité commandée.

 Les coûts de stockage, qui comprennent l'intérêt sur le capital immobilisé, les frais de
loyer, d'entretien, de surveillance, d'assurance, ...

 Le coût de rupture de stock qui peut parfois être estimé directement, ou xé indirecte-
ment au moyen d'une probabilité de rupture.

 Les délais de livraison ou de fabrication, plus ou moins xes, ou connus en probabilités.

 Les capacités de fabrication et de stockage, et d'autres contraintes.

Essentiellement, dans tous les problèmes de gestion des stocks, il s'agit de répondre à deux
questions :

1. Quand doit-on lancer une commande ?

2. Combien commander en une fois ?

3.4 Le modèle classique de Wilson

Le modèle classique de Wilson est un des modèles les plus simples de gestion des stocks. Les
hypothèses sont les suivantes :

65
  La demande est connue avec certitude, elle est constante et continue, exprimée par unité
de temps. Nous la noterons r.

 Le délai de réapprovisionnement est instantané.

Nous avons déjà abordé un tel problème dans l'introduction de ce chapitre (voir page 59).

Parmi les données du problème on retrouve la valeur CS , comme étant le coût de stockage par
unité et par unité de temps, CR le coût de lancement d'une commande et CA le coût d'achat
unitaire de la marchandise.

Le problème est toujours le même : on se demande quand et combien commander an de mi-
nimiser les coûts. La diculté réside donc dans l'écriture de cette fonction de coût. Dans le
modèle de Wilson comme pour les autres modèles que nous aborderons, il est souvent salutaire
de commencer par faire un dessin de la situation. Ce dessin comprend deux axes : l'axe ver-
tical représentant les quantités de marchandises, et l'axe horizontal le temps. Comme nous ne
savons pas encore combien nous allons commander ni à quelle fréquence, nous allons, comme
toujours en mathématiques, donner des noms à ces inconnues : Q sera la quantité que nous
commanderons, et T le temps entre deux commandes (le temps qui sépare deux commandes
est généralement appelé un cycle).

Le stock atteint la quantité Q au moment du réapprovisionnement, puis diminue progressive-

ment et de façon constante suivant la demande r. Quand il atteint le niveau nul, on lance une
nouvelle commande qui entre en stock aussitôt.

On doit maintenant écrire la fonction de coût que l'on désire minimiser. On sait que le coût
total par cycle est constitué du coût de lancement, du coût de stockage et du coût d'achat. On
peut donc écrire

Q
Ccycle (T, Q) = CR + · T · CS + Q · CA
2
Attention, on doit minimiser la fonction de coût par unité de temps, et pas la fonction de coût
par cycle ! Il faut donc multiplier par le nombre de cycles ! Or, le nombre de cycles peut être
exprimé en fonction de sa durée T.

66
  Si on commande r pièces en une fois, la longueur du cycle est

r
T = =1 année
r
r
 Si on commande pièces en une fois, la longueur du cycle est
2
r/2 1
T = = année
r 2
Il y a deux cycles par an.

r
 Si on commande pièces en une fois, la longueur du cycle est
5
r/5 1
T = = année
r 5
Il y a 5 cycles par an.

 ···

 Si on commande une quantité Q, la longueur du cycle est

Q
T = année
r
1
Il y a cycles par an.
T

Il suit que, comme le coût de réapprovisionnement par unité de temps (l'année ici) est égal au
coût de réapprovisionnement par cycle multiplié par le nombre de cycles, il sut de multiplier
1
la fonction Ccycle (T, Q) par :
T
1 Q Q
C(T, Q) = · CR + · CS + · CA
T 2 T
Q
On élimine une des deux variables grâce à la relation T = :
r
r Q
C(Q) = · CR + · CS + r · CA
Q 2
Notons que la partie liée au coût d'achat est constante. Elle n'interviendra donc pas dans notre
stratégie optimale (en eet, à partir du moment où on sait qu'on doit commander r pièces en
tout sur l'année au prix unitaire de CA , il est logique que ce prix soit le même qu'on passe nos
commandes en une ou 15 fois). Cette fonction est donc la somme d'une hyperbole, d'une droite
et d'une constante. La gure suivante donne une représentation graphique d'une telle fonction.

Il apparait sur le graphique que cette fonction admet un minimum à l'intersection de l'hyperbole
avec la droite. Vérions cela analytiquement. Comme rappelé lors de la section 3.2, nous devons,
pour déterminer un minimum local de cette fonction, déterminer les points stationnaires. Pour
cela, commençons par dériver la fonction :

r 1
C 0 (Q) = − 2
· CR + CS
Q 2

67
En un minimum, la dérivée doit être nulle. On cherche donc une valeur de Q telle que

r 1
− 2
· CR + CS = 0
Q 2
c'est-à-dire

r 1
2
· CR = CS
Q 2
Ceci est bien équivalent à (en multipliant par Q) :

r Q
· CR = CS
Q 2
Ce qui conrme que le minimum se trouve au point d'intersection de l'hyperbole et de la droite.
Déterminons donc la valeur de Q pour laquelle nous avons un point stationnaire :

r 1
2
· CR = CS
Q 2
CR
Q2 = 2r ·
CS
r
CR
Q = 2r ·
CS
De par le contexte nous ne considérons que la racine positive. Notons par Q∗ ce point station-
naire. Il nous reste à vérier que ce point stationnaire correspond bien à un minimum. On peut
choisir d'utiliser la condition susante du premier ou du deuxième ordre. Nous utilisons ici la
condition susante du deuxième ordre :

r 1
C 00 (Q) = (− 2
· CR + CS )0
Q 2
2r
= · CR
Q3

68
ce qui est bien positif quelle que soit la valeur de Q > 0. Il s'agit donc bien d'un minimum local.
Notons qu'il apparait clairement sur le graphique que ce minimum local est bien un minimum
absolu.

On peut donc nalement conclure que la meilleure stratégie à adopter est de commander à
chaque commande une quantité
r
∗ CR
Q = 2r ·
CS
La longueur optimale d'un cycle est de

r
Q 2 CR
T = = ·
r r CS
Le coût associé à cette solution est de

r Q∗
C(Q∗ ) = · C R + · CS + r · CA
Q∗ 2
r r
CS CS CR
= r· + 2r · + r · CA
2rCR 2 CS
r r
CR · CS · r CR · CS · r
= + + r · CA
r 2 2
CR · CS · r
= 2 + r · CA
p 2
= 2 · CR · CS · r + r · CA

3.5 Le "Manufacturing Model"

Il s'agit d'un modèle dont les hypothèses sont les mêmes que dans le modèle de Wilson, à
l'exception près que le taux d'approvisionnement n'est pas instantané mais vaut p, qui est ni
et uniforme et tel que p > r. Cela signie que le fournisseur ne va pas livrer la marchandise
commandée en une fois, mais de façon uniforme comme sur le graphique suivant :

69
Comme spécié sur le graphique, nous appellerons L le temps mis à être réapprovisionné.
Comme la relation obtenue dans le modèle de Wilson concernant le taux d'épuisement du stock
Q
r= on peut établir la relation concernant le taux de réapprovisionnement
T
Q
p=
L
La question à se poser est de savoir ce que ce délai d'approvisionnement change pour notre
problème d'optimisation. A priori, notre fonction de coût par cycle ou par unité de temps sera
toujours composée des frais liés au coût de lancement et au coût d'achat (qui eux ne seront
pas modiés par rapport au modèle de Wilson) et des frais liés aux coûts de stockage. Ce sont
ces derniers qui vont être modiés. En eet, pour connaître les coûts de stockage, il faut savoir
quelle quantité on stocke pendant combien de temps. Comme pour le modèle de Wilson, une
représentation graphique de la situation nous aidera :

DE
On voit sur le dessin que le stock moyen est donné par oùDE correspond au niveau
2
maximum de stock. Commençons donc par exprimer la valeur de DE en fonction des variables
et paramètres du problème :

DE = Q − CD
= Q−r·L
= p·L−r·L
p
= p·L− ·r·L
p
 
r
= p·L 1−
p
 
r
= Q· 1−
p
 
Q r
Le stock moyen est donc de · 1− . Les coûts de stockage par cycle sont donc donnés
2 p
par

 
Q r
· 1− · T · CS
2 p

70
On peut donc écrire la fonction de coût par cycle :

 
Q r
Ccycle (T, Q) = CR + · 1 − · T · CS + Q · CA
2 p
On en déduit la fonction de coût par unité de temps (rappelons que le nombre de cycles est
1
égal à ) :
T
 
1 Q r Q
C(T, Q) = · CR + · 1 − · CS + · CA
T 2 p T
Q
On remplace la variable T par :
r
 
r Q r
C(Q) = · CR + · 1 − · CS + r · CA
Q 2 p
Il nous reste à minimiser cette fonction. A nouveau, la fonction de coût s'obtient par l'addition
d'une hyperbole avec une droite, nous donnant le même genre de courbe que pour le modèle de
Wilson. On peut donc à nouveau se convaincre que le minimum de cette fonction correspondra
à l'intersection de l'hyperbole et de la droite. Cherchons à présent les points stationnaires :

 
0 r 1 r
C (Q) = − 2 · CR + · 1 − · CS
Q 2 p
Il faut annuler la dérivée :

 
r 1 r
− 2 · CR + · 1 − · CS = 0
Q 2 p
 
1 r r
· 1− · CS = · CR
2 p Q2
2 · r · CR
Q2 =  
r
1− · CS
p
v
u 2·r·C
Q = u
u R
r
1− · CS
t
p
A nouveau, nous ne considérons que la racine positive. Comme pour le modèle de Wilson, le
critère de la dérivée seconde nous assure que ce point stationnaire est bien un minimum. Il faut
donc commander une quantité de

v
u 2·r·C
∗
Q = u
u R
r
1− · CS
t
p
an d'optimiser les coûts. Le coût associé àQ∗ est égal à
v  
r 1 uu  2 · r ·CR r
C(Q∗ ) = v · CR + · u · 1− · CS + r · CA
u 2·r·C 2 t r p
u R 1− · CS
u
r p
1− · CS
t
p

71
Comme nous pouvons vérier qu'à l'optimalité les frais liés aux coûts de lancement et les frais
liés aux coûts de stockage sont égaux, on obtient

v  
r
u
u r · CR · CS · 1 −
u
∗
t p
C(Q ) = 2 · + r · CA
2
s  
r
= 2 · r · CR · CS · 1 − + r · CA
p

Remarque : Si le délai de livraison est instantané, ce qui mathématiquement revient à dire

que p tend vers l'inni, on retrouve la formule de coût du modèle de Wilson.

Exemple : Un importateur de voitures vous demande de résoudre son problème d'approvision-

nement de pièces de rechange. Il doit faire face à une demande de 100 axes de distributeur par
mois pour un modèle (on supposera 20 jours ouvrables par mois). Il peut s'approvisionner soit
en les commandant à l'usine de fabrication en Angleterre, soit en les faisant réaliser dans ses
ateliers.

L'importation d'un lot d'axes de distributeur lui coûte 5 euros par pièce plus 200 euros par lot
pour frais de commande et de transport.

La réalisation d'un lot d'axes de distributeur dans ses ateliers lui coûte 25 euros en frais de
lancement de la production, plus 6, 25 euros par pièce. Un seul ouvrier est capable de réaliser
ce travail, et il ne peut en produire que 10 par jour.

Les coûts de stockage sont de 0, 05 euro par pièce et par jour.

Quelle solution l'importateur doit-il choisir ?

3.6 Un modèle avec rabais lié à la quantité

Chez certains fournisseurs, il est parfois possible d'obtenir un rabais sur le prix de la marchan-
dise à condition de commander au moins une certaine quantité donnée. Ceci peut nous amener
à accepter de supporter des frais de stockage supplémentaires an de pouvoir bénécier de la
réduction de prix. A nouveau, la question que nous traitons dans cette section est "en quelle
quantité nous devons eectuer nos commandes, et à quelle fréquence an d'optimiser le coût
par unité de temps ?".

A nouveau, nous devons écrire cette fonction de coût par unité de temps. Remarquons que
dans les deux précédents modèles le coût d'achat n'a jamais inuencé notre stratégie optimale
(pourquoi ?). Ici, ce coût d'achat aura clairement un impact puisque celui-ci est variable. La
fonction de coût sera donc composée de trois parties : les frais liés aux coûts de lancement, les
frais liés aux coûts de stockage et enn les frais liés au prix d'achat de la marchandise. Notons
par

 p1 le prix initial de la marchandise (si on commande une quantité inférieure à A).

72
  p2 le prix avec rabais de la marchandise (si on commande une quantité supérieure ou
égale à A).

Nous faisons ici l'hypothèse que le prix de stockage, noté CS est proportionnel au prix unitaire,
c'est-à-dire

CS = CS0 · p
Ecrivons à présent la fonction de coût que l'on doit supporter si on commande une quantité
Q < A. Nous pouvons reprendre du modèle de Wilson (on suppose le réapprovisionnement
instantané)

r
 les frais liés aux coûts de lancement : · CR
Q
Q Q
 les frais liés aux coûts de stockage : · CS = · CS0 · p1 .
2 2
Il reste à inclure les frais liés au coût d'achat de la marchandise. Si on décide de commander
à chaque cycle une quantité inférieure à A, nous devrons payer les r unités sur l'année au prix
de p1 unité monétaire l'unité. Le coût d'achat sera donc p1 · r . Ainsi, on obtient la fonction de
coût dans le cas où Q<A :

 
r Q
C1 (Q) = · CR + · CS0 · p1 + p1 · r
Q 2
Par un même raisonnement nous obtenons la fonction de coût dans le cas où, an de bénécier
du rabais, nous commandons à chaque cycle une quantité Q>A :

 
r Q
C2 (Q) = · CR + · CS0 · p2 + p2 · r
Q 2
Remarque : Observons que cette fonction aura la même allure que dans les autres modèles
précédents : il s'agit de la somme d'une hyperbole, d'une droite et d'une constante. L'allure
du graphique de ces fonctions sera donc de même nature que le graphique du modèle de Wilson.

Comme à chaque fois, une représentation graphique de la situation peut grandement nous aider.

Etant données les deux courbes C1 et C2 , le graphique de la fonction objectif considérée est
donc déni par morceaux : il faut considérer le graphique de

73
  C1 pour des quantités comprises entre 0 et A.

 C2 pour des quantités supérieures à A.

Notons par Q∗1 le minimum de la fonction C1 et par Q∗2 le minimum de la fonction C2 (ces
quantités se déterminent exactement de la même façon que pour le modèle de Wilson). Il ap-
paraît sur le graphique que le point le plus bas de ces deux courbes correspond à la quantité
Q∗2 . Donc, si pour la quantité Q∗2 on peut bénécier du prix p2 (autrement dit si Q∗2 > A),
∗ ∗
alors la quantité optimale est Q2 . En revanche, si Q2 < A, on ne bénéciera pas de ce prix en
Q∗2 . Regardons de manière plus précise les diérents graphes que l'on peut obtenir. La solution
optimale apparaîtra clairement.

Commençons par le cas où A 6 Q∗2 :

Comme nous l'avons déjà souligné ci-dessus, dans ce cas la solution optimale est visiblement Q∗2 .

Dans l'hypothèse où A > Q∗2 deux situations peuvent se produire :

Dans la situation de gauche, on observe que le minimum se produit pour une quantité comman-
∗
dée A, car le point le plus bas que l'on obtient avec le prix p1 (autrement dit, Q1 ) correspond
à un prix supérieur au prix le plus bas que l'on obtient dans ce cas avec le prix p2 (autrement
dit pour une quantité A). On peut exprimer cela encore diéremment en disant que comme
C1 (Q∗1 ) > C2 (A), la quantité optimale à commander est A.

∗
Dans la situation de droite en revanche on observe que C1 (Q1 ) < C2 (A). Il est donc plus inté-
∗
ressant de commander une quantité Q1 même si on ne bénécie pas du rabais dans ce cas.

74
La règle de décision peut s'exprimer comme suit :

1. Calculer Q∗2 avec le prix p2 :

 Si Q∗2 > A : commander Q∗2 au prix p2 .

 Si Q∗2 < A : passer au point 2.

2. Calculer Q∗1 et les coûts C1 (Q∗1 ) et C2 (A) :

 Si C1 (Q∗1 ) > C2 (A) : commander A pour bénécier du rabais.

 Si C1 (Q∗1 ) < C2 (A) : commander Q∗1 au prix p1 .

Exemple : On utilise régulièrement 480 tonnes par mois d'une certaine matière. On évalue à
50 euros les frais directs relatifs à une commande, tandis que le coût de possession est estimé,
pour cette matière, à 20% sur la valeur par an.

On reçoit une ore pour un prix de 50 euros la tonne avec une proposition de rabais d'1% pour
des livraisons de 500 tonnes et plus.

Quelle doit être la politique d'approvisionnement par année pour cette matière ?

3.7 Modèle avec demande aléatoire

Dans cette section nous allons nous intéresser au cas où la demande n'est pas connue avec cer-
titude (comme c'est souvent le cas en pratique). Nous devrons donc tenir compte de l'aléatoire
dans notre gestion des stocks, c'est-à-dire d'éléments dont la valeur ne peut être connue à priori
(on aborde ici des techniques de décision dans l'incertain ). Nous allons voir un modèle simple
de réapprovisionnement périodique.

Avant de nous intéresser à ce modèle, un petit rappel sur les notions statistiques-probabilistes
s'impose.

3.7.1 Rappels statistiques

Il est souvent perturbant d'imaginer qu'on puisse prendre des décisions rationnelles et optimales
alors que les éléments nécessaires à la décision ne sont pas connus. Bien sûr, pour cela, il faut
que l'élément inconnu obéisse à certaines lois : si on lance un dé, le résultat est inconnu, mais
on est certain que le résultat sera un entier compris entre 1 et 6. Plus encore, on sait que la
distribution de probabilité du dé est uniforme, ce qui signie que si on lance un dé un très grand
nombre de fois, on admet que chaque résultat sera observé dans une même proportion (à savoir
1/6 dans ce cas). Il faut donc pouvoir décrire le hasard. Cela se fait au moyen, notamment, de
la fonction de distribution.

75
Histogramme et fonctions de densité

Au long de cette section, nous considérerons une demande aléatoire D pour un produit quel-
conque. En termes mathématiques, il s'agit d'une variable aléatoire, c'est-à-dire un être ma-
thématique qui à chaque fois qu'on l'évalue, prend une valeur diérente de manière imprévisible.

La source d'erreur la plus fréquente vient de la confusion entre deux outils statistiques à pre-
mière vue semblables, mais en réalité très diérents : la fonction de densité et l'histogramme.

Un histogramme est une représentation graphique d'un phénomène aléatoire qui ne peut prendre
ses valeurs que dans un ensemble dénombrable (généralement ni), tel qu'un lancement de pièce
de monnaie ou de dé, un tirage de carte... Ce phénomène est souvent mesuré par un nombre
entier ou rationnel. On parle d'un phénomène discret.
Par contre, la fonction de densité rend compte d'un phénomène aléatoire qui prend ses valeurs
dans un ensemble non dénombrable ; il s'agit généralement d'un phénomène qui se mesure dans
un sous-ensemble des nombres réels (une taille, un poids...). On parle d'un phénomène continu.

Il faut se rendre compte que très souvent, la classication entre phénomènes discrets et continus
comporte une part d'arbitraire. Par exemple, le lancement d'un dé est, par nature, discret. Mais
qu'en est-il de la demande d'un produit ? Si l'on parle de la demande de navires adressée chaque
année à un chantier naval, on parlera d'un phénomène discret ; si, par contre, on s'intéresse à
la quantité de sable commandée chaque année par une société de travaux publics, qu'en est-il ?
Si l'on compte en tonnes, on peut estimer qu'il s'agit d'un phénomène continu, puisque comp-
tabilisé par un nombre réel comme 388,232 tonnes. Bien entendu, on peut prétendre qu'aucun
comptable sensé n'utilisera dans ce cas plus de trois décimales et qu'il s'agit donc d'un nombre
entier de kilogrammes. En poussant le raisonnement plus loin, on peut également imaginer de
compter les grains de sable ! Bref, on choisit souvent d'utiliser une variable continue plutôt que
discrète pour des raisons de bon sens et de facilité, notamment mathématique.

La façon habituelle de représenter un phénomène discret est l'histogramme, ou diagramme en

bâtonnets, qui présente en abscisse les valeurs de la variable aléatoire (son domaine) et en or-
donnée la probabilité d'observer cette valeur de la variable aléatoire à chaque tirage. La gure
suivante représente l'histogramme d'un lancer de dé.

On a bien sûr que la somme des valeurs de l'histogramme est égale à 1.

Pour les phénomènes continus on ne peut par dénition pas faire une énumération de tous les
résultats possibles. L'utilisation d'un histogramme tel que celui décrit ci-dessus est donc impos-
sible. Les phénomènes continus sont souvent représentés par une courbe qui doit être interprétée
d'une façon radicalement diérente : la probabilité se mesure en fonction de la surface située
en dessous la courbe. La gure suivante représente une telle courbe (fonction de densité).

76
On suppose que la surface totale en dessous de la courbe (et au-dessus de l'axe horizontal)
vaut 1, c'est-à-dire 100 %. On l'interprète comme suit : si la surface comprise entre 3 et 5 sous
la courbe (partie sombre du graphe) vaut 42 % de la surface totale, alors la probabilité que
la variable aléatoire soit comprise entre 3 et 5 est de 0, 42. Ceci entraîne que la probabilité
que la variable aléatoire prenne une valeur précise est toujours nulle ! ! ! On en arrive ainsi à
la conclusion paradoxale que, pour les variables aléatoires continues, toute valeur possède a
priori une probabilité nulle d'être choisie et donc que le résultat constaté a posteriori avait une
probabilité nulle de se présenter !

Fonction de distribution

En pratique, dans la résolution des exercices de gestion de stock, on utilisera un troisième type
de graphique : la fonction de distribution ou fonction cumulative. Celle-ci a l'avantage
d'être dénie de la même façon pour les variables aléatoires continues et discrètes.

La fonction de distribution d'une variable aléatoire Q présente un graphique dont l'axe hori-
zontal représente un nombre réel x mesuré dans les mêmes unités que la variable aléatoire et
dont l'axe vertical mesure la probabilité :

FD (x) = P [Q 6 x]
c'est-à-dire la probabilité que la variable aléatoire Q soit inférieure ou égale à x. Un exemple
d'une telle fonction est donné à la gure suivante :

La fonction de distribution présente toujours les propriétés suivantes :

 sa limite à gauche est 0.

 sa limite à droite est 1.

 la fonction est monotone croissante.

77
Remarque : les variables aléatoires discrètes ont une fonction de distribution en escaliers, les
variables aléatoires continues ont une fonction de distribution continue, qui peut être linéaire
par morceaux ou dérivable.

3.7.2 Modèle simple de réapprovisionnement périodique

Dans cette section, nous allons considérer un modèle simple de réapprovionnement périodique
avec une demande aléatoire mais dont on connaît la distribution. On suppose ici que le réap-
provisionnement se fait à intervalles xes. Il s'agit donc uniquement dans ce cas de déterminer
le niveau de stock S en début de période. Commençons par xer les notations :

 CS désigne le coût de stockage par unité stockée en n de période.

 Crup désigne le coût de rupture par unité manquante en n de période.

 x est la demande aléatoire exprimée sur la période.

 f (x) est la fonction de densité de probabilité de la demande.

Nous travaillons ici sur un modèle alors qu'une partie des données (la variable x) est inconnue
ou incertaine. L'hypothèse généralement admise est de supposer que l'utilisateur va raisonner
en moyenne et donc supposer qu'il sera confronté un très grand nombre de fois à la même
situation ou à une situation comparable et que, l'un dans l'autre, à long terme les bons résultats
compenseront les mauvais. Il ne s'agit que d'une hypothèse et, avant de l'admettre, il convient
d'en apprécier la pertinence.

Il faut en premier lieu que les résultats puissent se compenser : jouer à la roulette russe avec une
chance sur deux de gagner 1 million de dollars ne va pas donner comme résultat un demi-mort
possédant un demi-million de dollars.

Ensuite, il faut que les gains (ou les pertes) hauts et bas soient appréciés avec le même déta-
chement. Or, dans la réalité, on ne joue pas mille dollars à pile ou face de la même façon selon
que l'on est SDF, étudiant ou milliardaire.

Par contre, il n'est pas besoin de devoir être confronté à la même situation pour admettre l'hy-
pothèse : il sut de pouvoir utiliser les mêmes principes de décision un grand nombre de fois,
même si la situation varie d'un cas à l'autre. Par exemple, si vous devez jouer 1 000 000 euros
à pile ou face, en jouant 1 million de fois 1 euro, le résultat sera très proche de l'espérance de
gain : à savoir 1 000 000 euros. Si, par contre, vous les jouez en une fois vous terminerez avec
2 000 000 euros ou rien du tout. La moyenne est la même, la variance est très diérente.

Du point de vue mathématique cette hypothèse s'avère très pratique puisqu'elle permet de
calculer la stratégie optimale en minimisant l'espérance mathématique du coût d'approvision-
nement par cycle.

Il s'agit donc maintenant de déterminer cette espérance. Suivant l'importance de la demande

par rapport au niveau de stock en début de période, deux situations peuvent se produire :

78
  On arrive en n de période avec un surplus de marchandise (on n'a pas tout vendu).

On obtient que le coût de réapprovisionnement dans cette situation est de CR +CS ·(S−x).
 On arrive en n de période avec une rupture de stock.

On obtient que le coût de réapprovisionnement dans cette situation est de CR + CRupt ·

(x − S).

Comme nous supposons que la longueur du cycle T est xée, il suit que le coût de lancement
n'a pas d'importance dans ce modèle. L'espérance mathématique du coût d'approvisionnement
par cycle s'exprime donc de la façon suivante :

Z S Z +∞
E [Ccycle (S)] = CS · (S − x) · f (x) dx + Crupt · (x − S) · f (x) dx
0 S
Il s'agit d'une fonction de la variable S. Pour déterminer la valeur de S qui minimise cette
fonction, nous devons la dériver. Nous devons pour cela nous référer au résultat suivant, donné
sans démonstration :

Théorème 3.7.1
R b(S)
Si p(S) = a(S)
f (x, S) dx, alors

Z b(S)
dP (S) ∂f (x, S) db(S) da(S)
= · dx + · f (b(S), S) − · f (a(S), S)
dS a(S) ∂S dS dS

Commençons par calculer la dérivée de la première intégrale (dans ce cas, la fonction f (x, S)
du théorème ci-dessus est la fonction (S − x) · f (x)) :

79
 Z S 0 Z S 0
CS · (S − x) · f (x) dx = CS · (S − x) · f (x) dx
0 S 0
Z S 
= CS · 1 · f (x) dx + 1 · (S − S)f (S) − 0
0
Z S
= CS · f (x) dx
0

On applique un même raisonnement sur la deuxième intégrale (dans ce cas, on a f (x, S) =

(x − S) · f (x)) :

Z +∞ 0 Z +∞ 0
Crupt · (x − S) · f (x) dx = Crupt · (x − S) · f (x) dx
S S S
Z +∞ 
= Crupt · (−1) · f (x) dx + 0 − 1 · (S − S) · f (S)
S
Z +∞
= −Crupt · f (x) dx
S

Il vient donc

S +∞
dE [Ccycle (S)]
Z Z
= CS · f (x) dx − Crupt · f (x) dx
dS 0 S
Or, par dénition, on a

Z S
f (x) dx = F (S)
0

où F (S) est la fonction de distribution de probabilité cumulée de la demande. On en déduit

que

Z +∞
f (x) dx = 1 − F (S)
S

On peut donc réécrire la dérivée de E[CCycle (S)] en fonction de cette fonction F (S) :

dE [Ccycle (S)]
= CS · F (S) − Crupt · (1 − F (S))
dS
Comme nous cherchons un point stationnaire, nous devons déterminer la (les) valeur(s) S∗ qui
annule(nt) cette dérivée :

CS · F (S ∗ ) − Crupt · (1 − F (S ∗ )) 0 =
⇔ CS · F (S ∗ ) Crupt · (1 − F (S ∗ ))
=
⇔ CS · F (S ∗ ) + Crupt · F (S ∗ ) Crupt =
⇔ F (S ∗ )(CS + Crupt ) Crupt =
Crupt
⇔ F (S ∗ ) =
CS + Crupt

80
Pour déterminer S ∗, il faut donc trouver quelle est l'abscisse de la fonction de distribution
Crupt
cumulée qui a pour image , comme indiqué sur le graphique ci-dessous :
CS + Crupt

En observant attentivement la formule et le graphique, on constate sans surprise que si CS de-

∗ ∗
vient très grand, F (S ), et par conséquent S , se rapprochent de 0 : ce qui signie simplement
que si le coût subi pour détenir une unité en début de période est très élevé, il vaut mieux
commander très peu.

∗
Inversement, si Crupt devient très grand ou si CS devient relativement petit, alors F (S ) tend
∗
vers 1 et S doit être grand. En d'autres termes si le coût pour une unité manquante devient
très grand ou si le coût d'approvisionnement et de stockage est très petit, il est plus intéressant
d'avoir un stock important. Ce qui est tout aussi logique.

Tout l'art de la résolution des exercices consiste donc à déterminer à partir des informations
reçues

1. La fonction de distribution de la demande pour la période.

2. Le coût subi pour une unité manquante par rapport au stock en début de période.

3. Le prix payé pour détenir une unité en début de période.

3.7.3 Stock de sécurité

Pour pouvoir appliquer en pratique la formulation de la quantité économique de commande
basée sur l'hypothèse de demande certaine, il faut pouvoir tenir compte des facteurs aléatoires
d'une autre manière. D'habitude, en plus du stock normal, on maintient un stock de sécurité
destiné à absorber les conséquences des éléments aléatoires : la demande et le délai de réappro-
visionnement.

Les problèmes de recherche opérationnelle liés concernant les stocks de sécurité sont à la limite
de ce qu'il est possible d'aborder au sein de ce cours, que ce soit au niveau de la diculté
théorique ou de la complexité des calculs.

Dans la pratique, on recourt généralement à des logiciels spécialisés pour résoudre ces pro-
blèmes et l'important est donc d'en comprendre le fonctionnement et, surtout, les limites de la

81
modélisation qu'ils proposent. Nous nous contenterons ici d'étudier un cas très simple.

Le problème est le suivant : un gestionnaire de stock est confronté à une demande aléatoire,
un coût de réapprovisionnement, un coût de rupture et un délai de réapprovisionnement non
négligeables. Par conséquent, il est tiraillé entre le fait de commander rapidement lorsque son
stock diminue et de supporter des frais de réapprovisionnement fréquents ou de retarder ses
commandes et de risquer des coûts de rupture.

Nous allons adopter les notations suivantes :

 L : la durée de réapprovisionnent ;

 F (x) : la fonction de distribution de la demande aléatoire x sur une durée L;

 Crupt : le coût de rupture exprimé en unité monétaire par unité de temps ;

 CS : le coût de stockage exprimé en unité monétaire par unité de produit et par unité
de temps ;

 CR : le coût de réapprovisionnement ;

 Q∗ : la quantité que l'on commande à chaque cycle ;

 Ssec : le niveau du stock de sécurité, c'est-à- dire le niveau du stock en dessous duquel
le gestionnaire doit lancer une nouvelle commande Q∗ .

Au cours de la résolution, on est généralement amené à calculer r, la demande moyenne par

unité de temps (en unité de produits par unité de temps).

La grande simplication que l'on pose au niveau de la résolution théorique est de supposer que
l'on peut travailler en deux étapes successives :

 Dans un premier temps, on fait abstraction du caractère aléatoire de la demande et on

suppose que cette demande est constante. Grâce à ce biais, on peut alors déterminer la
∗
commande optimale Q qu'on lancerait à chaque période. Si, par exemple on utilise le
modèle de Wilson, la quantité optimale est :

r
∗ CR
Q = 2r
CS
Et la durée de la période correspondante T ∗ (toujours en supposant la demande constante)
est :

Q∗
T∗ =
r
 On suppose alors que le niveau de réapprovisionnement est connu et que le second
problème consiste à déterminer le stock de sécurité de façon à minimiser l'espérance des
coûts. Et l'on trouve (par une dérivation non triviale de l'espérance des coûts) que le
niveau du stock de sécurité Ssec satisfait à la relation :

CS Q∗ CS · T ∗
F (Ssec ) = 1 − =1−
Crupt r Crupt

82
Enn, quelques remarques de bon sens peuvent vous aider à évaluer la solution obtenue :

 le niveau du stock de sécurité est toujours inférieur à la demande maximale possible

durant le délai de réapprovisionnement ;

 si les coûts de stockage sont élevés, le stock de sécurité sera relativement bas, le gestion-
naire se préservant de stocks minimums importants qui constituent une sorte de frais
xes importants ;

 à l'inverse, des coûts de rupture importants provoquent une hausse du niveau du stock
de sécurité.

83
3.8 Exercices
1. Walmark Store compresse et met en palette les emballages vides destinés au recyclage. Le
magasin produit cinq palettes par jour. Le coût de stockage dans l'entrepôt du magasin
est de 0, 10 euros par jour.

La société qui transporte les palettes destinées au recyclage facture un montant forfaitaire
de 100 euros pour la location du matériel de manutention et un coût de transport de 3
euros par palette.

Dessinez le graphe représentant le nombre de palettes en fonction du temps et élaborez

une politique optimale pour l'évacuation des palettes vers le centre de recyclage.

2. Votre marchand de journaux se trouve devant un problème complexe : il doit assurer la

diusion d'un périodique bimensuel, mais ne sait quelle quantité commander.

En eet, une étude de marché lui a montré qu'il pourrait vendre de façon continue 100
exemplaires la première quinzaine et 150 exemplaires la seconde quinzaine, le nombre de
pages de ces derniers étant plus important.

Votre marchand de journaux estime son coût de stockage à 0, 01 euros par journal et par
jour et son coût de rupture à 0, 40 euros par pièce. Il a, par ailleurs, la possibilité d'écouler
sur un marché extérieur les périodiques invendus, moyennant une perte de 0, 13 euros par
pièce.

Malheureusement, l'éditeur exige que le marchand commande la même quantité de pério-

diques toutes les quinzaines.

Quelle est la quantité optimale à commander ?

3. Soit un client qui commande des pièces détachées à un rythme de 2400 pièces par an. La
compagnie qui fournit ces pièces peut les produire en n'importe quelle quantité à n'im-
porte quel moment.

Le coût de mise en route de la machine est de 105 euros. Le coût de stockage d'une pièce
détachée est de 1, 4 euros par pièce et par an. On refuse toute rupture de stock !

Quelle quantité faut-il commander ?

4. Un vendeur de produits périssables doit rendre un rapport mensuel. Son entreprise est
organisée de façon à considérer qu'un mois comporte 4 semaines de 5 jours. On sait que
la demande s'exprime uniquement en n de journée et vaut 5 unités par semaine. Le coût
de possession d'une unité est de 3 euros par jour. Quels sont les coûts de stockage si on
eectue :

a) une commande par mois ?

b) une commande par semaine ?

c) une commande par jour ?

84
5. La rme BETONEX est une entreprise qui fabrique des dalles et des tuyaux en béton.

Elle écoule toute sa fabrication de tuyaux à un syndicat d'entrepreneurs de la région qui

s'est engagé à prendre livraison de 1 000 tuyaux par jour.

Sa production quotidienne est de 1 500 pièces.

Dans la mesure de son temps disponible, l'entreprise fabrique des dalles qui sont vendues
et livrées immédiatement.

L'appareil de production se compose principalement d'une presse à béton alimentée par

un mélangeur.

Le passage d'un type de fabrication à un autre entraîne les frais suivants :

 changement de moules : 60 euros
 nettoyage du mélangeur : 40 euros
Le coût de stockage est de 0,01 euros par tuyau et par jour.

Déterminez la quantité optimale de tuyaux en béton que la rme doit fabriquer lors de
chaque lancement ainsi que la période optimale de ces lancements.

6. Un artisan fabrique pour un consommateur particulier 3 600 articles par an.

La réalisation de cet article se fait en deux étapes principales : le gros oeuvre et la nition.

L'artisan eectue d'abord le gros oeuvre d'une certaine quantité d'articles au rythme de
30 gros oeuvres par jour. Il achève ensuite ces articles à raison de 20 par jour. Abandon-
nant la production, il peut alors eectuer lui-même la livraison de ses articles au prix de
5 euros la pièce. La capacité de livraison est de 60 produits nis par jour.

L'artisan a établi comme suit la liste de ses coûts ;

 coût de stockage : 0, 075 euros par jour et par article entré dans le cycle de fabrication ;
 coût de démarrage du matériel destiné au gros oeuvre : 150 euros ;
 coût de démarrage du matériel nécessaire à la nition : 75 euros ;
 coût d'utilisation du matériel de livraison : 5 euros/jour.

a) Établissez son plan de production optimal.

b) Pour avoir des livraisons plus rapprochées, le client serait disposé à payer plus cher
les articles. L'artisan se propose alors de faire le gros oeuvre d'une certaine quantité
d'articles, d'en nir la moitié et de la livrer puis de terminer l'autre moitié et de la
livrer. Quel doit être le nouveau plan de production ? De combien l'artisan doit-il
augmenter le prix de l'article pour garder le même bénéce ?

7. Une entreprise prévoit que la demande de l'article AA qu'elle distribue devrait être de 4000
unités pour l'année. Le coût de passation/lancement d'une commande est de 100 euros. Le
coût de possession en stock est de 10% de la valeur d'achat de l'article. Le fournisseur de
cet article pour inciter ses clients à augmenter l'importance de leurs commandes propose
à l'entreprise les conditions suivantes :

85
 a) Quantités commandées inférieures à 2000 unités : prix unitaire de 8 euros.

b) Quantités commandées comprises entre 2000 et 3500 unités : remise de 2%.

c) Quantités commandées supérieures à 3500 unités : remise de 3%.
Questions :

(a) Comment l'entreprise doit-elle gérer ses achats ?

(b) Donner le coût annuel de l'achat et de la conservation en stock de l'article.

(c) Que se passe-t-il si les prévisions de demande passent à 6000 unités par an ?

8. Une société de distribution vend des batteries AA à raison de 15 000 unités par an.
Cette demande est répartie uniformément sur l'année qui comporte 50 semaines. Le prix
d'achat unitaire est de 16 euros. Le coût d'une commande est de 24 euros quelle que soit
la quantité. Comme le matériel se déprécie rapidement, il faut compter qu'un matériel
détenu en stock perd (linéairement) toute sa valeur en un an.

a) Déterminer la politique d'approvisionnement optimale.

b) Actuellement, la société utilise la politique suivante : elle dispose de deux bacs conte-
nant au maximum 500 pièces. Dès qu'un bac est vide, la société repasse une commande
de 500 pièces. Par rapport à cette stratégie, quel est le gain annuel que vous allez réa-
liser ?

c) La société vend également des batteries BB à raison de 15 000 unités par an dont le
coût d'achat unitaire est de 20 euros . Sachant que la société s'approvisionne auprès
du même fournisseur que pour les batteries AA, la société a-t-elle intérêt ou non à
grouper ses commandes ?

9. Un industriel utilise une matière dont le délai de réapprovisionnement est de deux se-
maines. D'après les statistiques du passé, il a pu arriver à certaines conclusions sur les
caractéristiques de sa consommation :

 La demande globale annuelle est remarquablement stable aux environs de 39 000 kgs ;

 La demande sur de courtes périodes présente un caractère aléatoire assez marqué : la

distribution de la demande par quinzaine peut être considérée comme uniforme entre
1250 et 1750 kgs.

Les données de coûts sont les suivants :

 prix : 5 euros le kg ;
 coût de lancement : 195 euros ;
 coût de possession : 20% sur le prix par kg et par an ;
 coût de rupture : 1 euro par kg manquant et par pénurie.

A quel niveau doit être xé le stock de sécurité ?

10. Monsieur Léon est très connu pour ses moules au vin blanc. La preuve en est que, sur
une soirée, il espère accueillir entre 50 et 100 personnes les jours de petite auence et
entre 200 et 300 personnes les jours de grande auence. Monsieur Léon considère qu'il y
a autant de chance d'avoir un jour de petite auence qu'un jour de grande auence. Par
ailleurs, la répartition de la demande à l'intérieur de chaque intervalle est uniforme.

86
 Monsieur Léon vend sa portion de moules 15 euros et réalise une marge de prot de 50%
sur sa vente.

Si, sur sa soirée, il manque des portions de moules, Monsieur Léon a toujours la possibilité
d'en préparer, mais avec un coût de 20% supérieur au coût normal. Le client qui aura pris
le temps d'attendre (en moyenne 75% des clients concernés) sera ainsi servi. Par contre,
si toutes les portions ne sont pas vendues, Monsieur Léon estime qu'il subit un coût de 1
euro de stockage (surgélation) par portion non vendue.

Combien de portions de moules notre ami Léon doit-il avoir en stock en début de sa
soirée ?

11. Un grossiste en produits pharmaceutiques doit faire face à une demande aléatoire de ME-
GARDOL : cette demande suit une distribution uniforme entre 250 et 350 acons tous
les deux jours.

Le délai d'approvisionnement normal du grossiste est de deux jours. Le prix d'achat est
de 2, 5 euros le acon ; le coût de lancement d'une commande normale est de 7, 5 euros.

Lorsqu'il n'a plus de MEGARDOL en stock, le grossiste peut s'approvisionner instan-

tanément, mais cela lui coûte 0, 50 euros par acon commandé, en plus du prix d'achat
normal pour  demande urgente .

Les frais de stockage du MEGARDOL sont de 0, 025 euro par jour et par acon.

a) Quel est le stock de sécurité que vous conseillez pour le MEGARDOL ?

b) Quel stock de sécurité lui conseillez-vous s'il ne possède que des données journalières
sur la demande et que celle-ci suit une distribution uniforme entre 100 et 200 acons
par jours ?

12. Un magasin spécialisé en vêtements de mode se veut continuellement à la pointe de la

mode. Il commande au début du printemps les articles qui seront mis en vente à l'au-
tomne suivant. Il est particulièrement intéressé par un article que certains considèrent
déjà comme le vêtement de l'avenir : le PLASTICUNIK, d'un prix de revient de 125 euros.

Les services de marketing ont déterminé qu'il y avait autant de chances d'avoir demandé
entre 300 et 350 unités qu'une demande entre 275 et 300 unités (à l'intérieur de ces deux
intervalles, la demande est uniforme).

Si l'article n'est pas vendu à la n de l'automne, il sera liquidé au cours des soldes à 50%
du prix de vente. Toute demande non satisfaite entraîne un préjudice évalué à 50 euros.

Les frais de lancement de la commande s'élèvent à 125 euros et le prix de vente d'un
PLASTICUNIK est de 200 euros.

Combien de PLASTICUNIK le magasin doit-il acheter ? Formulez la fonction économique

et résolvez.

87
13. Un boulanger a observé que dans 25% des cas la demande journalière de ses clients se
situait entre 101 et 125 pains ; dans 50% des cas, elle oscille entre 126 et 150 pains et, dans
les autres cas, elle va de 151 à 175 pains. À l'intérieur de ces intervalles, la distribution
de la demande est uniforme.

Le boulanger vend son pain à 1,50 euros. Il écoule les pains non vendus en n de journée
à une oeuvre de charité et se contente d'un prix de 0,1 euro par pain.

En outre, il estime que toute demande non satisfaite lui cause un préjudice de 0,50 euro.

Quelle doit être sa politique de production journalière si :

a) fabriquer un pain lui coûte 0,75 euro ?

b) fabriquer un pain lui coûte 1,25 euros ?

14. Devant assurer la diusion d'un périodique vendu 2 euros pièce, un marchand de journaux
a relevé les données nécessaires pour déterminer la quantité optimale de commande :

 la demande pour le périodique est uniforme entre 101 et 150 exemplaires ;

 le prix d'achat du périodique est de 1,50 euros ;
 les exemplaires invendus sont écoulés sur un marché extérieur au prix de 0,9 euro ;
 la valorisation de la perte potentielle d'un client due à un manque est de 0,2 euro par
unité.

Déterminer la quantité optimale de commande.

88
Chapitre 4
La théorie des graphes

Dans ce chapitre, nous allons introduire la notion de graphes et nous consacrer à la résolution
de deux problèmes majeurs de la théorie des graphes : le problème de la recherche de l'arbre
couvrant de poids minimum ainsi que le problème du plus court chemin. Pour ce dernier, nous
allons voir diérentes méthodes de résolution. Avant cela, nous allons présenter un bref histo-
rique ainsi que quelques dénitions.

4.1 Bref historique

La théorie des graphes serait née en 1735 lorsqu'Euler proposa une solution au célèbre problème
des 7 ponts de Königsberg. Cette ville se présente de la façon suivante :

Cette ville compte 4 parties terrestres (que nous nommerons A - B - C et D) et 7 ponts. Le

problème posé est celui-ci

Est-il possible de partir d'une des 4 terres, de traverser chacun des 7 ponts exactement une
fois, et de revenir à l'endroit initial ?

Euler modélisa cette situation à l'aide d'un dessin : il représenta chaque partie de terre par un
point, et chaque pont par un trait.

89
Il est assez facile de se convaincre, sur ce graphe, qu'il n'existe pas de tel parcours. Euler
présenta la solution de ce problème à l'académie de Saint Pétersbourg en 1735. Il réussit à
déterminer une condition nécessaire et susante pour qu'un tel parcours existe, quel que soit
le graphe que l'on étudie (pouvez-vous donner cette condition ?).

4.2 Dénitions
Dans cette section, nous apportons quelques dénitions élémentaires.

Dénition 4.2.1 Un graphe G = (V, A, E) est une structure constituée :

 d'un ensemble V d'éléments appelés noeuds.

 d'un ensemble A de paires orientées de noeuds appelées arcs (ceux-ci représentent des
liens orientés entre deux noeuds).
 d'un ensemble E de paires non-orientées de noeuds appelés arêtes (celles-ci représentent
des liens non-orientés entre deux noeuds).

Exemple : Pour le graphe suivant nous pouvons identier les ensembles V , A et E :

90
 V := {1, 2, 3, 4, 5}
A := {(2, 4); (3, 4); (4, 3); (5, 3)}
E := {(1, 2); (1, 3); (4, 5)}

Graphiquement, les noeuds sont représentés par des points, les arcs par des traits échés,
et les arêtes par des traits, dont les longueurs n'ont aucune importance. Les deux graphes ci-
dessous sont identiques :

Attention : les arcs et arêtes ne peuvent avoir des intersections qu'en des noeuds. Dans la
gure ci-dessus, les arêtes (2, 4) et (1, 3) n'ont pas de noeuds communs.

Dénition 4.2.2 Un chemin est une séquence nie alternée de noeuds et d'arcs/arêtes telle
que chaque arc/arête est sortant d'un noeud et incidant au noeud suivant. Chaque arc doit être
parcouru dans le bon sens et aucun noeud ne peut être parcouru plus d'une fois.

Exemple : Voici un chemin entre le noeud 1 et le noeud 5 :

91
Contre-exemple : Ceci n'est pas un chemin entre le noeud 1 et le noeud 5 :

Dénition 4.2.3 Un cycle est un chemin dont les extrémités coïncident.

Exemple :

Dénition 4.2.4 Un graphe est connexe si toute paire de noeuds est reliée par au moins un
chemin.

Contre-exemple : le graphe suivant n'est pas connexe car il n'existe pas de chemin entre le
noeud 1 et le noeud 5 :

92
Dénition 4.2.5 Un arbre est un graphe connexe sans cycle (non orienté).

Exemple :

Dénition 4.2.6 Un arbre couvrant de G est un arbre qui inclut tous les noeuds de G (non-
orienté).

Exemple :

4.3 Encodage d'un graphe

Dans cette section nous abordons la question de l'encodage d'un graphe, autrement dit quels
sont les moyens de dénir ou décrire un graphe ?

Bien sûr, le moyen le plus naturel de décrire un graphe est d'en donner une représentation
(attention, celle-ci n'est pas unique). Voici une représentation d'un graphe :

93
On peut aussi décrire ce graphe de manière plus algébrique en donnant la liste de ses noeuds,
arcs et arêtes :

V := {1, 2, 3, 4, 5}
A := {(2, 4); (3, 4); (4, 3); (5, 3)}
E := {(1, 2); (1, 3); (4, 5)}

Enn, la manière la plus commode (utilisée en informatique) est encore d'encoder un graphe
sous la forme d'une matrice carrée appelée matrice d'adjacence. Supposons que le graphe
possède n noeuds, il pourra alors être décrit par une matrice carrée de dimension n (c'est-à-dire
possédant n lignes et n colonnes), dans laquelle l'entrée aij décrira s'il existe un arc qui va du
noeud i au noeud j ou s'il existe une arête entre i et j . De manière plus formelle, on dénit
l'entrée aij de cette matrice de la façon suivante :


1 s'il existe un arc de i à j ou s'il existe une arête (i, j)
aij :=
0 sinon

Pour notre exemple, la matrice d'adjacence est

 
0 1 1 0 0

 1 0 0 1 0 


 1 0 0 1 0 

 0 0 1 0 1 
0 0 1 1 0

Notons que si le graphe est uniquement constitué d'arêtes (c'est-à-dire s'il est non orienté) alors
la matrice d'adjacence sera symétrique (autrement dit on aura toujours aij = aji ).

Finalement, comme nous le verrons dans la suite de ce chapitre, il n'est pas rare d'associer à
chaque arc/arête du graphe un poids ou une longueur `ij . On peut également encoder un tel
graphe à l'aide d'une matrice. De manière plus formelle, on dénit l'entrée `ij de cette matrice
de la façon suivante :

`ij := distance entre i et j (on note ∞ si aij = 0)

Exemple : On peut encoder le graphe suivant par la matrice

 
0 2 5 6 +∞ +∞

 +∞ 0 1 +∞ +∞ 7 


 +∞ +∞ 0 +∞ 1 +∞ 


 +∞ +∞ +∞ 0 +∞ 6 

 +∞ +∞ +∞ +∞ 0 1 
+∞ +∞ +∞ +∞ +∞ 0

94
4.4 Le problème de l'arbre couvrant de poids minimum
Considérons le problème qui consiste à relier n villes par un réseau cablé de la manière la
plus économique possible. Le réseau doit être connexe (an que toutes les villes soient reliées)
et ne doit pas admettre de cycle (pour ne pas construire de réseaux superus). Il s'agit donc
de trouver au sein du réseau un arbre couvrant de poids minimum. Nous considérerons dans
cette section que le graphe est uniquement constitué d'arêtes, c'est-à-dire que le graphe est
non-orienté.

Etant donné un graphe orienté G = (V, A, E), on associe à chaque arc (i, j) ∈ A un nombre
réel

`ij ∈ R
appelé "longueur" de l'arc. En réalité, cette longueur peut représenter autre chose qu'une dis-
tance suivant le contexte du problème.

Exemple : on désire déterminer l'arbre couvrant de poids minimum dans le graphe suivant :

95
Nous allons ici aborder l'algorithme de Kruskal pour résoudre ce problème. Nous noterons par
V l'ensemble des noeuds du graphe,
Ck l'ensemble des noeuds connectés lors de l'itération k ou avant,
C̄k l'ensemble des noeuds à connecter après l'itération k.

Algorithme de Kruskal :
Step 0 : On initialise C0 = φ et C̄0 = V

Step 1 : Choisir un noeud i ∈ {1, · · · , n} et mettre à jour :

C1 = {i} et C̄1 = V \ {i} et k = 2.

Step k : Choisir une arête de poids minimal qui a un pied dans Ck−1 et l'autre dans C̄k−1 .
Soit j le noeud de C̄k−1 qui est l'extrémité de cette arête.
Ck := Ck−1 ∪ {j} et C̄k := C̄k−1 \ {j}.
Si C̄k = φ, alors STOP
sinon k := k + 1

Cet algorithme est un algorithme de type "glouton" (greedy algorithm), c'est-à-dire qu'à chaque
itération il choisit une meilleure solution.

4.5 Le problème du plus court chemin

Le problème du plus court chemin est celui de déterminer le chemin le plus court entre un
noeud source et un noeud destination dans un graphe. Mais ce problème ne se retrouve pas
uniquement dans les GPS ! Il y a un très vaste champ d'applications à ce genre de problème :

 certains problèmes de tournées,

 certains problèmes d'investissements et de gestion de stocks,
 problèmes d'optimisation de réseaux (télécoms, routiers,...)
 ...

4.5.1 Dénition du problème

Le problème du plus court chemin entre deux noeuds i et j consiste à déterminer un chemin
µ(i, j) de i à j dont la longueur totale donnée par

X
`(a)
a∈µ(i,j)

soit minimale.

Ce problème a beaucoup d'applications car la "longueur" `(a) peut s'interpréter de diérentes

façons (distance, temps, coût,...).

Nous allons étudier diérentes façons de résoudre ce problème.

96
4.5.2 Principes de programmation dynamique

Nous allons présenter ici le principe général de programmation dynamique introduit dans les
années 1950 par Bellman. Nous verrons par la suite deux célèbres exemples de ce type d'al-
gorithme pour résoudre le problème du plus court chemin : l'algorithme de Bellman-Ford et
l'algorithme de Dijkstra.

Commençons par observer la propriété suivante : supposons que nous savons que, dans un graphe
donné, le plus court chemin entre le noeud 1 et le noeud 10 est le chemin 1 − 3 − 6 − 8 − 10.
Est-ce qu'on peut en déduire que le plus court chemin entre le noeud 3 et le noeud 8 est 3−6−8 ?

Il est assez intuitif de répondre à cette question par l'absurde : supposons que le chemin 3−6−8
ne soit pas optimal. Alors, cela signie qu'il existe un autre chemin entre 3 et 8 qui soit plus
court. Il serait donc plus intéressant d'emprunter ce chemin plus court entre 3 et 8 ce qui aurait
pour eet de diminuer la longueur du chemin entre 1 et 10. Mais ceci n'est pas possible vu
qu'on a supposé le chemin 1 − 3 − 6 − 8 − 10 comme étant le plus court. La contradiction nous
permet donc d'armer que le chemin 3 − 6 − 8 est lui aussi optimal.

Il est tentant de conclure de ce qui précède que tous les sous-chemins d'un chemin optimal
sont également optimaux... Malheureusement, il existe un contre-exemple. En eet, s'il existe
un cycle de longueur négative, c'est-à-dire un cycle dont la somme des longueurs des arêtes ou
arcs le constituant est négative, alors ce principe n'est pas valable. Voyons cela sur la gure
suivante

Sur cet exemple, nous voyons que le plus court chemin entre le noeud source 1 et le noeud 3
est le chemin 1−2−3 de longueur 5. On voudrait donc pouvoir conclure que le chemin le plus
court entre 1 et 2 est le sous-chemin 1−2 de longueur 2. Or, le chemin 1−3−4−2 est plus
court car de longueur égale à −3 (notons qu'on ne peut utiliser ce sous-chemin comme chemin
pour aller de 1 à 3 car la séquence 1 − 3 − 4 − 2 − 3 n'est pas un chemin car elle passe deux fois
par le noeud 3). Heureusement, dans beaucoup de problèmes les graphes ne contiennent pas
de cycle de longueur négative. Nous devrons donc utiliser le résultat vu plus haut en vériant
d'abord que le graphe ne contient pas de cycle de longueur négative.

97
Théorème 4.5.1 Principe d'optimalité :
Dans un graphe ne contenant pas de cycle de longueur négative, tout sous-chemin d'un plus
court chemin est un plus court chemin entre ses extrémités.

Le principe de la programmation dynamique est de parvenir à écrire une fonction récursive

dénissant la valeur de la solution optimale. Pour cela, nous allons bien sûr nous baser sur le
principe d'optimalité décrit ci-dessus. Nous allons décrire cette fonction pour le cas où nous
cherchons le plus court chemin entre un noeud de départ, appelé le noeud source, et n'importe
quel autre noeud du graphe. Pour cela, introduisons la notation suivante :

v[k] := longueur du plus court chemin entre le noeud source et le noeud k (= +∞ si un tel
chemin n'existe pas).

Nous pouvons alors donner le résultat suivant :

Proposition 4.5.2 Les fonctions de récurrence pour le problème du plus court chemin d'un
noeud source s à n'importe quel noeud du graphe sont :

v[s] = 0
v[k] = min{v[i] + `ik : (i, k) ∈ A ou E}

Notons qu'en l'absence de cycle de longueur négative, les longueurs des plus courts chemins
satisfont les équations de récurrence car elles satisfont au principe d'optimalité. Evidemment,
il faudrait que ce résultat, pour pouvoir être utilisé, soit valable dans les deux sens. Ce qui est
le cas (nous donnons ce résultat sans démonstration).

Théorème 4.5.3 Dans un graphe sans cycle de longueur négative, les valeurs v[k] représentent
la longueur du plus court chemin entre le noeud source s et le noeud k si et seulement si ces
valeurs satisfont les équations de récurrence.

Remarque : Il suit de ce résultat que pour déterminer les longueurs v[k] il sut de calculer
les valeurs qui satisfont les fonctions de récurrence.

Pour nous convaincre de ce résultat (en réalité nous sommes déjà convaincus que c'est bien une
condition nécessaire, voyons qu'elle est susante, c'est-à-dire que nous devons nous convaincre
que si on a des valeurs v[k] qui satisfont les équations de récurrence alors elles correspondent
bien à des valeurs de plus courts chemins) nous allons examiner le graphe suivant dans lequel le
noeud source est le noeud 3 et pour lequel nous avons déjà calculé les valeurs v[k] satisfaisant
les équations de récurrence (voir livre (3)).

Nous allons seulement vérier que la valeur v[4] = 623 correspond bien à la longueur du plus
court chemin entre le noeud 3 et le noeud 4. Cette vérication se fait en deux temps :

1. Nous vérions d'abord que v[4] = 623 correspond bien à la longueur d'un chemin entre le
noeud source 3 et le noeud 4. Par dénition, on a

v[4] = min{v[i] + `i4 : (i, 4) ∈ A ou E}

98
Dans notre cas on a

v[4] = min{v[2] + `24 ; v[5] + `54 ; v[6] + `64 }

= min{347 + 345; 180 + 443; 272 + 415}
= min{692; 623; 687}
= 623

Ici on a donc que v[4] = v[5] + `54 . Déterminons quel est le prédécesseur du noeud 5 :

v[5] = min{v[i] + `i5 : (i, 5) ∈ A ou E}

= min{v[3] + `35 }
= min{0 + 180}
= 180

On continue ainsi jusqu'à arriver au noeud source (ce qui est le cas ici). On peut donc
recomposer la valeur v[4] :

v[4] = v[5] + `54

= v[3] + `35 + `54
= `35 + `54

On a donc bien que v[4] correspond à la longueur d'un chemin, qui est le chemin 3 − 5 − 4.

99
 2. Nous devons maintenant vérier que ce chemin 3 − 5 − 4 est bien le plus court entre le
noeud 3 et le noeud 4. Prenons par exemple le chemin 3 − 1 − 2 − 4. Comme nous savons
que les valeurs v[k] satisfont les équations de récurrence, on peut écrire

v[1] 6 v[3] + `31

v[2] 6 v[1] + `12
v[4] 6 v[2] + `24

On obtient donc

v[1] + v[2] + v[4] 6 v[3] + `31 + v[1] + `12 + v[2] + `24

ce qui est équivalent à

v[4] 6 `31 + `12 + `24

ce qui prouve bien que v[4] est plus petit que la longueur du chemin 3 − 1 − 2 − 4.
Il reste à savoir comment parvenir à calculer les valeurs qui satisfont les équations de récurrence.
Nous allons voir à présent deux algorithmes qui permettent de répondre à cette question.

4.5.3 L'algorithme de Bellman-Ford

Nous venons de voir par le principe de la programmation dynamique que déterminer les lon-
gueurs des plus courts chemins entre un noeud source s et tous les autres noeuds du graphe
revient à calculer les quantités v[k] qui satisfont les équations de récurrence dénies plus haut.
Notre problème revient donc à trouver une méthode ecace permettant de calculer ces quanti-
tés. Notons que si le graphe ne contient pas de cycle, ces valeurs sont assez faciles à déterminer.
Les dicultés commencent quand nous avons une conguration comme celle-ci

100
Si on écrit les équations de récurrence on obtient

v[1] = min{v[3] + 5, · · · }
v[2] = min{v[1] + 2, · · · }
v[3] = min{v[2] + 4, · · · }

On constate ici que pour déterminer la valeur de v[1] nous avons besoin de la valeur de v[3] qui
elle-même nécessite la valeur de v[2] v[1]. En conclusion,
pour laquelle nous avons besoin de
pour déterminer la valeur de v[1] nous avons nécessairement besoin de la valeur de v[1]... L'idée
de l'algorithme de Bellman-Ford (1956) est d'évaluer ces valeurs à répétition.

An de présenter cet algorithme, introduisons la notation suivante :

vt (k) := la valeur de v[k] à l'itération t

Nous ne pouvons nous contenter de déterminer les nombres v[k] car nous devrons également
reconstituer le chemin :

d[k] := noeud qui précède le noeud k dans un plus court chemin

Nous donnons à présent l'algorithme :

Algorithme de Bellman-Ford : pour déterminer un plus court chemin entre le noeud source
s et tous les autres noeuds du graphe :

Step 0 : Initialisation 
0 si k=s
v0 [k] := ∀k ∈ A ∪ E
+∞ sinon
t := 1

Step 1 : Evaluation
pour tout k 6= s :
vt [k] := min{vt−1 [i] + `ik : (i, k) ∈ A ∪ E}
Si vt [k] < vt−1 [k], alors stocker le noeud prédécesseur dans d[k]

Step 2 : Arrêt
On arrête l'exécution dans les cas suivants :
• vt [k] = vt−1 [k] pour tout k
si
• si t = n (nombre de noeuds dans le graphe) (attention, si des
valeurs de vt [k] ont été modiées à la dernière itération t, cela signie
que le graphe contient un cycle de longueur négative !

Step 3 : Progression
Si au moins une des valeurs vt [k] a été modiée et que t<n alors
t := t + 1 et on retourne au Step 1.

Exemple : Supposons que nous voulions déterminer les plus courts chemins depuis le noeud 1
vers tous les autres noeuds du graphe suivant :

101
Appliquons l'algorithme de Bellman-Ford :
A l'étape 0 on a :

v0 [1] := 0
v0 [2] := +∞
v0 [3] := +∞
v0 [4] := +∞
v0 [5] := +∞
v0 [6] := +∞

A l'étape t := 1, on a

v1 [1] := 0
v1 [2] := min{v0 [1] + `12 } = 0 + 2 = 2
v1 [2] < v0 [2] ⇒ d[2] := 1
v1 [3] := min{v0 [1] + `13 ; v0 [2] + `23 } = min{0 + 5; +∞} = 5
v1 [3] < v0 [3] ⇒ d[3] := 1
v1 [4] := min{v0 [1] + `14 } = 0 + 6 = 6
v1 [4] < v0 [4] ⇒ d[4] := 1
v1 [5] := min{v0 [3] + `35 } = +∞
v1 [6] := min{v0 [2] + `26 ; v0 [4] + `46 ; v0 [5] + `56 } = +∞

102
A l'étape t := 2, on a

v2 [1] := 0
v2 [2] := min{v1 [1] + `12 } = 0 + 2 = 2
v2 [3] := min{v1 [1] + `13 ; v1 [2] + `23 } = min{0 + 5; 2 + 1} = 3
v2 [3] < v1 [3] ⇒ d[3] := 2
v2 [4] := min{v1 [1] + `14 } = 0 + 6 = 6
v2 [5] := min{v1 [3] + `35 } = 5 + 1 = 6
v2 [5] < v1 [5] ⇒ d[5] := 3
v2 [6] := min{v1 [2] + `26 ; v1 [4] + `46 ; v1 [5] + `56 } = min{2 + 7; 6 + 6; +∞} = 9
v2 [6] < v1 [6] ⇒ d[6] := 2

A l'étape t := 3, on a

v3 [1] := 0
v3 [2] := 2
v3 [3] := 3
v3 [4] := 6
v3 [5] := min{v2 [3] + `35 } = 3 + 1 = 4
v3 [5] < v2 [5] ⇒ d[5] := 3
v3 [6] := min{v2 [2] + `26 ; v2 [4] + `46 ; v2 [5] + `56 } = min{2 + 7; 6 + 6; 6 + 1} = 7
v3 [6] < v2 [6] ⇒ d[6] := 5

A l'étape t := 4, on a

v4 [1] := 0
v4 [2] := 2
v4 [3] := 3
v4 [4] := 6
v4 [5] := 4
v4 [6] := min{v3 [2] + `26 ; v3 [4] + `46 ; v3 [5] + `56 } = min{2 + 7; 6 + 6; 4 + 1} = 5
v4 [6] < v3 [6] ⇒ d[6] := 5

103
A l'étape t := 5, on a

v5 [1] := 0
v5 [2] := 2
v5 [3] := 3
v5 [4] := 6
v5 [5] := 4
v5 [6] := 5

Les valeurs n'ont pas été modiées lors de cette dernière itération, on peut donc stopper l'exé-
cution de l'algorithme. Les valeurs v5 [k] nous donnent la longueur du plus court chemin du
noeud 1 jusqu'au noeud k . Par exemple, la longueur du plus court chemin du noeud 1 vers le
noeud 6 est de v5 [6] = 5. Si on veut déterminer le chemin exact, il sut de regarder le vecteur
d : Comme d[6] = 5 cela signie que le prédécesseur du noeud 6 dans le plus court chemin est
le noeud 5. Le prédécesseur du noeud 5 est le noeud d[5] = 3 qui a pour prédécesseur le noeud
d[3] = 2. Enn, le prédécesseur du noeud 2 est le noeud 1. On a donc reconstruit le chemin à
l'envers : 1 − 2 − 3 − 5 − 6.

Remarque : Grâce au critère d'arrêt énoncé, on peut appliquer cet algorithme même sur des
graphes possédant un cycle de longueur négative : l'algorithme permettra d'ailleurs de repérer
ceux-ci.

4.5.4 L'algorithme de Dijkstra

Nous présentons dans cette section un algorithme publié en 1959 par Dijkstra qui permet, lui
aussi, de déterminer les plus courts chemins qui séparent un noeud source s de tous les autres
noeuds d'un graphe donné. Si l'output de cet algorithme est le même que pour l'algorithme de
Bellman-Ford, cet algorithme dière tout de même en apportant une nouvelle manière (plus
ecace) de parcourir les noeuds du graphe. L'ecacité de cet algorithme est telle qu'il est
souvent appliqué dans les itinéraires routiers. Par contre, cet algorithme ne peut être appliqué
à des graphes possédant au moins une arête de longueur négative.

Le principe de l'algorithme de Bellman-Ford décrit plus haut est d'évaluer à chaque itération t
de l'algorithme l'ensemble des valeurs vt [k] pour tous les noeuds k ∈ A ∪ E. Avec l'algorithme
de Dijkstra nous allons gagner en ecacité en marquant un noeud de façon dénitive au fur et à
mesure des itérations, ce qui permet de ne plus devoir réévaluer des valeurs qui ne bougent plus.

104
Algorithme de Dijkstra : pour déterminer un plus court chemin entre un noeud source s et
tous les autres noeuds du graphe :

Step 0 : Initialisation :
On marque chaque noeud de façon temporaire :

0 si k = s
v[k] := ∀k ∈ A ∪ E
+∞ sinon
On note par p le prochain noeud à être marqué
de façon permanente.
On impose p := s.

Step 1 : Procédure
On marque le noeud p de façon permanente.
Pour chaque arc ou arête (p, k) du noeud p
vers un noeud marqué temporairement
on met les marquages à jour :
v[k] := min{v[k]; v[p] + `pk }
Si la valeur de v[k] a changé, alors d[k] := p.

Step 2 : Arrêt
S'il ne reste plus de noeud marqué de façon temporaire,
on s'arrête.

Step 3 : Choix du noeud :

Le prochain noeud p à être marqué de façon permanente
est celui qui possède la plus petite valeur v[k] temporaire,
c'est-à-dire qu'on choisit p tel que :
p := argmin{v[k] : k est un noeud marqué temporairement}
Retour au Step 1

Exemple : Appliquons l'algorithme de Dijkstra au graphe de l'exemple précédent :

105
A l'étape d'initialisation on a

v[1] := 0
v[2] := +∞
v[3] := +∞
v[4] := +∞
v[5] := +∞
v[6] := +∞

On marque le noeud 1 de façon permanente. On met donc à jour les valeurs v[2], v[3] et v[4] :

v[2] := min{v[2]; v[1] + `12 } = 2, d[2] := 1

v[3] := min{v[3]; v[1] + `13 } = 5, d[3] := 1
v[4] := min{v[4]; v[1] + `14 } = 6, d[4] := 1

On marque le noeud 2 de façon permanente. On met donc à jour les valeurs v[3] et v[6] :

v[3] := min{v[3]; v[2] + `23 } = min{5; 3} = 3, d[3] := 2

v[6] := min{v[6]; v[2] + `26 } = 9, d[6] := 2

On marque le noeud 3 de façon permanente. On met donc à jour la valeur v[5] :

v[5] := min{v[5]; v[3] + `35 } = 4, d[5] := 3

On marque le noeud 5 de façon permanente. On met donc à jour la valeur v[6] :

v[6] := min{v[6]; v[5] + `56 } = 5, d[6] := 5

On marque le noeud 6 de façon permanente. Il n'y a pas de mise à jour à faire

On marque le noeud 4 de façon permanente. Tous les noeuds sont marqués de façon permanente.
L'algorithme s'arrête.

Théorème 4.5.4 L'algorithme de Dijkstra est l'algorithme le plus ecace pour déterminer les
plus courts chemins entre un noeud source et n'importe quel noeud dans un graphe ne contenant
pas d'arête de longueur négative.

106
Attention : Cet algorithme ne peut être utilisé que sous la condition que tous les arcs/arêtes
soient de longueur positive (voyez-vous pourquoi ?).

L'algorithme de Dijkstra est fort utilisé dans les problèmes routiers. Les longueurs des arcs/arêtes
représenteront les longueurs des routes, le temps de parcours moyen, ou même le prix du car-
burant utilisé pour parcourir une route ainsi que les éventuels péages à payer suivant que l'on
veuille minimiser la distance, le temps ou le coût du parcours. Dans tous ces cas, il est clair que
les longueurs seront des nombres positifs.

Dans le cas où il y aurait une ou plusieurs arêtes de longueur négative, on peut toujours utiliser
l'algorithme de Bellman-Ford.

Notons qu'il existe encore d'autres algorithmes de résolution du problème du plus court chemin.

107
4.6 Exercices
1. Considérons le graphe suivant :

a) Identiez les ensembles V, A et E.

b) Déterminez la matrice d'adjacence ainsi que la matrice des distances de ce graphe.

c) Identiez cinq chemins allant du noeud 1 au noeud 5.

d) Donner un graphe orienté équivalent.

2. Déterminez un arbre couvrant de poids minimum dans le graphe suivant en commençant

par le noeud 6

3. En reprenant le graphe ci-dessus, déterminez un arbre couvrant de poids minimum dans

chacune des situations suivantes :

108
 a) Le noeuds 5 et 6 sont liés par une arête de longueur 2.

b) Les noeuds 2 et 5 ne peuvent pas être reliés.

c) Le noeud 2 ne peut être directement relié aux noeuds 3 et 5.

4. On donne la matrice suivante qui indique les distances des routes entre les villes 1 à 8

 
/ +∞ 35 30 10 ∞ ∞ ∞

 +∞ / 20 10 15 80 30 30 


 35 20 / 20 20 +∞ +∞ +∞ 

 30 10 20 / +∞ +∞ 18 +∞  

 10 15 20 +∞ / +∞ +∞ +∞ 

 +∞ 80 +∞ +∞ +∞ / 40 50 

 +∞ 30 +∞ 18 +∞ 40 / 75 
+∞ 30 +∞ +∞ +∞ 50 75 /
a) Représentez les villes et les routes par un graphe.

b) Déterminez un arbre couvrant de poids minimum sachant que la route entre la ville 2
et la ville 5 doit nécessairement être utilisée.

5. Considérons le problème de déterminer le plus court chemin du noeud source 1 à tous les
autres noeuds dans le graphe suivant :

a) Déterminez tous les plus courts chemins par simple inspection.

b) Complétez
v[1] = v[2] = v[3] = v[4] = v[5] =
c) Ecrivez toutes les fonctions de récurrence et vériez que les valeurs déterminées ci-
dessous les satisfont.

109
6. Identiez tous les cycles de longueur négative dans le graphe suivant :

7. Considérons le graphe suivant ainsi que les valeurs v[k] associées :

a) Vériez que les valeurs données v[k] satisfont les fonctions de récurrence.

b) Identiez les chemins associés à chacune des valeurs v[k].

c) Utilisez les fonctions de récurrence pour prouver que le chemin 1−3−2−4 doit être
de longueur supérieure ou égale à v[4].

8. Appliquez l'algorithme de Bellman-Ford pour déterminer les plus courts chemin du noeud
1 vers les autres noeuds dans le graphe dont voici la matrice des distances :

 
0 5 8 +∞
 +∞ 0 −10 +∞ 
 
 8 +∞ 0 +∞ 
+∞ 2 3 0

110
 9. Appliquez l'algorithme de Dijkstra pour déterminer les plus courts chemin du noeud 1
vers les autres noeuds dans le graphe suivant :

10. Appliquez l'algorithme de Bellman-Ford pour déterminer les plus courts chemin du noeud
1 vers les autres noeuds dans le graphe suivant :

11. Pour le graphe suivant, quel algorithme appliqueriez-vous pour déterminer les plus courts
chemins entre le noeud 1 et tous les autres noeuds du graphe ? Expliquez votre choix.

111
Références bibliographiques

1. D. Bonheure, D. Paindaveine, Mathématiques pour la gestion, partie II, PUB, 2014.

2. P. Gille, Syllabus d'exercices du cours d'introduction à la recherche opération-

nelle, 2013.

3. P. Marchandise, Syllabus de Recherche opérationnelle, SIC-Ichec, 2015.

4. R. Rardin, Optimization in Operations Research, Pearson New International Edi-

tion, 2013.

5. H. A. Taha, Operations Research : an Introduction, Pearson, 2011.

112