Optimisation Logistique PDF
Optimisation Logistique PDF
2 Problèmes d’ordonnancement 25
2.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Notions de projet, tâche et ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.1 Notion de projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.2 Notion de tâche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Méthode d’ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4 Établissement d’un ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5 Détermination du chemin critique et énumération des tâches critiques . . . . . . . . . . . . . 26
2.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 La méthode MPM 29
3.1 Le graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.1 Eléments du graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.2 Contraintes potentielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.3 Exercice corrigé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.1.4 Tâches parallèles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1.5 Opérations dépendantes et indépendantes . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1.6 Opérations composées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.1.7 Conditions limites de démarrage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 Exercice synthétique corrigé : construction d’un pont . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Date au plus tôt d’une tâche i, ordonnancement minimum ou au plus tôt . . . . . . . . . . . 36
3.3.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3.2 Détermination des dates au plus tôt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3.3 Chemins critiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4 Date au plus tard de début d’une tâche i, ordonnancement limite (ou au plus tard) . . . . . . 37
3.4.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4.2 Recherche de l’ordonnancement au plus tard . . . . . . . . . . . . . . . . . . . . . . . 38
3.5 Marges d’une tâche i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.5.1 Marge totale mT (i) de la tâche i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.5.2 Marge libre mL (i) d’une tâche i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
I
II TABLE DES MATIÈRES
4 La méthode PERT 53
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2 Difficultés de construction du graphe PERT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3 Calcul de l’ordonnancement par la méthode PERT . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3.1 Calcul de l’ordonnancement au plus tôt . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3.2 Calcul de l’ordonnancement au plus tard . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3.3 Calcul du chemin critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
E × F = {(x, y)/x ∈ E, y ∈ F }
E × E = E 2 = {(x, y)/x ∈ E, y ∈ E}
xRy
L’ensemble des couples (x, y) de E × F tels que xRy est appelé graphe de la relation. On note
G = {(x, y) ∈ E × F/xRy}
On remarque que G ⊂ E × F .
Soit R une relation de E dans F , la relation réciproque R−1 est une relation de F dans E définie par
xRy ⇔ yR−1 x
• réflexive si :
∀x ∈ E, xRx
• symétrique si :
∀x ∈ E, ∀y ∈ E, xRy ⇒ yRx
• transitive si :
∀x ∈ E, ∀y ∈ E, ∀z ∈ E, (xRy et yRz) ⇒ xRz
1
2 CHAPITRE 1. QUELQUES RAPPELS SUR LES GRAPHES
XXX
XXX arrivée
XXX x1 x2 x3 x4 x5
départ XX
x1 ⋆ ⋆ ⋆
x2 ⋆ ⋆
x3
x4 ⋆ ⋆
x5 ⋆
XXX
XXX arrivée
XXX x1 x2 x3 x4 x5
départ XX
x1 1 1 0 0 1
x2 1 0 1 0 0
x3 0 0 0 0 0
x4 0 0 1 0 1
x5 0 0 1 0 0
x S(x)
x1 x1 , x2 , x5
x2 x1 , x3
x3
x4 x3 , x5
x5 x3
XXX
XXX arrivée
XXX x1 x2 x3 x4 x5
départ XX
x1 1 1 0 0 0
x2 1 0 0 0 0
x3 0 1 0 1 1
x4 0 0 0 0 0
x5 1 0 0 1 0
Remarque 1.1.2 Les matrices de R et R−1 ont leurs termes symétriques par rapport à la diagonale
principale.
(a) Cette relation binaire est caractérisée par son graphe, sa relation sagittale, sa représentation
cartésienne, sa matrice booléenne, le dictionnaire des suivants ou des précédents. On note
G = (X, R)
(b) On appelle boucle tout couple (Ap , Ap ) du graphe donc avec Ap RAp .
4 CHAPITRE 1. QUELQUES RAPPELS SUR LES GRAPHES
(c) On appelle arc tout couple de points distincts du graphe donc tout couple (Ap , Aq ) avec Ap ̸= Aq
et Ap RAq .
(d) On appelle arête toute partie {Ap , Aq } avec Ap ̸= Aq et Ap RAq ou Aq RAp .
ou
Figure 1.4 – Une arête
(e) On appelle arcs adjacents deux arcs (Ap , Aq ), (Aq , Ar ) avec Ap RAq et Aq RAr . Les sommets Ap ,
Aq et Ar sont des sommets adjacents.
Remarque 1.1.3 : Si on a le graphe suivant : les arcs (Ap , Aq ) et (Aq , Ar ) ne sont pas adjacents.
(f) On appelle chemin une suite de sommets adjacents permettant de passer d’une manière continue
d’un sommet à l’autre, c’est-à-dire une suite non vide d’arcs (Ai , Aj ) et (Aj , Ak ), l’extrémité de
chacun d’eux coı̈ncidant avec l’orgine de l’arc suivant (sauf pour le dernier arc de la suite).
• Un chemin est simple s’il ne contient pas deux fois le même arc.
• Un chemin est élémentaire s’il ne passe pas deux fois par le même sommet.
• Un chemin est hamiltonien s’il passe par tous les sommets une fois et une seule.
x3 admet un unique précédent qui est x2 . x3 est le descendant de x1 et x2 mais x3 n’est pas le
suivant de x1 .
Exercice
1 On se donne la relation binaire définie par l’ensemble de sommets E = {x1 , x2 , x3 , x4 , x5 }
et le graphe
1. Soit N0 l’ensemble des sommets exempts de précédent. Pour tout sommet xi de N0 , on pose r(xi ) = 0.
N0 est l’ensemble des sommets de niveau 0.
Exemple 1.1.6 dans l’exemple 1.1.1, en supprimant les boucles (x1 , x1 ) et (x2 , x1 ) (afin d’éviter les
boucles et les circuits), on obtient le dictionnaire suivant :
6 CHAPITRE 1. QUELQUES RAPPELS SUR LES GRAPHES
x P (x)
x1
x2 x1
X; R
x3 x2 , x4 , x5
x4
x5 x1 , x4
x P (x)
x2
X1 ; R
x3 x 2 , x5
x5
3. On supprime dans X1 les sommets de N1 (les sommets de niveau 1). On obtient un ensemble X2 et
G2 est la restriction du graphe de R à x2 .
Soit N2 l’ensemble des points de X2 exempts de précédent. Pour tout point xi de N2 , on pose r(xi ) = 2
et N2 est l’ensemble des sommets de niveau 2.
1.1. INITIATION À LA THÉORIE DES GRAPHES 7
x P (x)
X2 ; R
x3
4. Les itérations cessent dès que tous les sommets de X sont classés par niveaux. Si
Card(X) = n, on a
∀xi ∈ X, r(xi ) ≤ n
1.1.3 Exemples
Exemple 1.1.7 On se donne l’ensemble de sommets X = {a, b, c, d, e, f, g} ainsi que la représentation
sagittale du graphe considéré :
On donne les dictionnaires des précédents et des suivants des sommets du graphe :
8 CHAPITRE 1. QUELQUES RAPPELS SUR LES GRAPHES
x S(x) x P (x)
a b, c, e a
b g, f, c b a
c d, f, g c a, b, e
d f d c, e
e c, d e a
f f b, c, d
g g b, c
• Niveau 0 :
On obtient à l’aide du dictionnaire des précédents N0 = {a} ; en effet, “a” n’a pas de précédent. On
pose r(a) = 0.
• Niveau 1 :
X1 = X − N0 = {b, c, d, e, f, g}
x P (x)
b
c b, e
X1 , R d c, e
e
f b, c, d
g b, c
Les sommets b et e n’ont pas de précédent donc N1 = {b, e} avec r(b) = r(e) = 1.
• Niveau 2 :
X2 = X1 − N1 = {c, d, f, g}
x P (x)
c
X2 , R d c
f c, d
g c
Les sommets d et g n’ont pas de précédent donc N3 = {d, g} avec r(d) = r(g) = 3.
• Niveau 4 :
X4 = X3 − N3 = {f }
x P (x)
X4 , R
f
X = {1, 2, 3, 4, 5, 6, 7, 8}
x P (x)
1 3, 6, 7
2 1, 4, 7, 8
3 7
4 3, 5
5
6 5, 7
7
8 5
10 CHAPITRE 1. QUELQUES RAPPELS SUR LES GRAPHES
• Niveau 0 :
On obtient à l’aide du dictionnaire des précédents N0 = {5, 7} ; en effet, “5” et “7” n’ont pas de
précédent. On pose r(5) = r(7) = 0.
• Niveau 1 :
X1 = X − N0 = {1, 2, 3, 4, 6, 8}
x P (x)
1 3, 6
2 1, 4, 8
X1 , R 3
4 3
6
8
Les sommets 3, 6 et 8 sont exempts de précédent donc N1 = {3, 6, 8} avec r(3) = r(6) = r(8) = 1.
• Niveau 2 :
X2 = X1 − N1 = {1, 2, 4}
x P (x)
1
X2 , R
2 1, 4
4
Les sommets 1 et 4 sont exempts de précédent donc N2 = {1, 4} avec r(1) = r(4) = 2.
• Niveau 3 :
X3 = X2 − N2 = {2}
x P (x)
X3 , R
2
Remarque 1.1.7 Si xi est de niveau p ̸= 0, i.e. r(xi ) = p, p est le nombre d’arcs du plus long chemin
joignant un sommet de niveau 0 au sommet xi .
Définition 1.1.2 Si r(xi ) = p ̸= 0, p est le nombre maximum d’arcs d’un chemin d’origine un sommet de
niveau 0, d’extrémité ce point xi .
1.1.4 Exercices
Exercice
2 Huit entrepôts reliés par un réseau routier, sont mis à contribution pour fabriquer un produit
A. Le tableau ci-dessous indique les routes menant à chacun de ces entrepôts.
XXX
XXX Arrivée
XX A B C D E F G H
Départ XXX
A ⋆ ⋆
B ⋆
C ⋆
D ⋆ ⋆
E
F ⋆ ⋆ ⋆
G ⋆
H ⋆ ⋆
1. Établir le dictionnaire des précédents puis le dictionnaire des suivants des sommets du graphe.
2. Utiliser le dictionnaire des précédents pour ordonnancer le graphe par niveaux.
3. Représenter le graphe sous sa forme ordonnancée.
12 CHAPITRE 1. QUELQUES RAPPELS SUR LES GRAPHES
Exercice 3 On considère le graphe ci-dessous :
1. Montrer que le graphe admet des circuits tout en les précisant. Qu’est-ce que cela implique sur l’or-
donnancement par niveaux de ce graphe ?
2. On élimine l’arc (A, G)
(a) Déterminer le dictionnaire des précédents et des suivants de chacun des sommets du graphe.
(b) Ordonnancer le graphe par niveaux.
Exercice
4 On se donne la relation binaire définie par l’ensemble de sommets E = {A, B, C, D, E, F }
et le graphe
G = {(A, B); (A, D); (A, F ); (B, D); (C, A); (C, D); (C, E); (D, E); (F, C); (F, E)}.
Les valuations du graphe sont les suivantes : v13 = 7, v36 = 10, v14 = 2, v12 = 9, v24 = −2, v46 = 11,
v45 = 13, v65 = 6.
Soit un graphe valué et sans circuit, à valeurs positives (vij > 0), possédant une entrée notée
x1 et une sortie notée xn . Le problème que l’on souhaite résoudre consiste à déterminer parmi
tous les chemins d’origine xi , d’extrémité xn , ceux dont la longueur est extrémale (maximale ou
minimale).
α1 = 0
αj = min[αi + vij ]
Remarque 1.2.1 : Les valeurs αj sont portées au dessus des sommets dans le diagramme sagittal et
désignées par αj .
14 CHAPITRE 1. QUELQUES RAPPELS SUR LES GRAPHES
Pour retrouver les arcs qui constituent le chemin minimal, appelé chemin critique, on part de la
sortie et on repère l’arc qui donne la valeur α correspondante.
En généralisant, un chemin minimal d’origine xk d’extrémité xi est appelé k.i chemin minimal
et tout arc emprunté par ce chemin est appelé arc k-minimal.
On considère le graphe valué ci-dessous et on souhaite déterminer les chemins de longueur minimale issus
du sommet x1 et aboutissant à un sommet donné et ceci pour tout sommet.
Vérifions que ce graphe est sans circuit et ordonnançons-le en niveaux en utilisant le dictionnaire des
précédents.
1.2. GRAPHES VALUÉS ET CHEMINS CRITIQUES 15
sommet x précédent(s) de x
x1 –
x2 x1 , x3 , x5 , x8
x3 x1
x4 x 1 , x2 , x3
x5 x1
x6 x5 , x8
x7 x9 , x11 , x13
x8 x1
x9 x1 , x8
x10 x4 , x11
x11 x 2 , x5 , x6
x12 x4 , x7 , x9 , x10 , x11
x13 x6 , x8
16 CHAPITRE 1. QUELQUES RAPPELS SUR LES GRAPHES
• Niveau N0 :
Le sommet x1 est le seul exempt de précédent donc N0 = {x1 }.
On considère ensuite l’ensemble de sommets
X1 = X − N0 = {x2 , x3 , x4 , x5 , x6 , x7 , x8 , x9 , x10 , x11 , x12 , x13 }
On “barre” tous les sommets x1 dans le tableau précédent.
sommet x précédent(s) de x
x2 x3 , x5 , x8
x3
x4 x 2 , x3
x5
x6 x 5 , x8
x7 x9 , x11 , x13
x8
x9 x8
x10 x4 , x11
x11 x2 , x5 , x6
x12 x4 , x7 , x9 , x10 , x11
x13 x 6 , x8
Remarque 1.2.2 Dans la suite de l’exercice, tous les sommets xi seront notés i par souci de commo-
dité.
• Niveau N1 :
Les sommets 3, 5 et 8 sont exempts de précédent donc N1 = {3, 5, 8}.
On considère ensuite l’ensemble de sommets
X2 = X1 − N1 = {2, 4, 6, 7, 9, 10, 11, 12, 13}
On “barre” tous les sommets 3, 5, 8 dans le tableau précédent.
sommet x précédent(s) de x
2
4 2
6
7 9, 11, 13
9
10 4, 11
11 2, 6
12 4, 7, 9, 10, 11
13 6
• Niveau N2 :
Les sommets 2, 6 et 9 sont exempts de précédent donc N2 = {2, 6, 9}.
On considère ensuite l’ensemble de sommets
X3 = X2 − N2 = {4, 7, 10, 11, 12, 13}
On “barre” tous les sommets 2, 6, 9 dans le tableau précédent.
1.2. GRAPHES VALUÉS ET CHEMINS CRITIQUES 17
sommet x précédent(s) de x
4
7 11, 13
10 4, 11
11
12 4, 7, 10, 11
13
• Niveau N3 :
Les sommets 4, 11 et 13 sont exempts de précédent donc N3 = {4, 11, 13}.
On considère ensuite l’ensemble de sommets
X4 = X3 − N3 = {7, 10, 12}
On “barre” tous les sommets 4, 11, 13 dans le tableau précédent.
sommet x précédent(s) de x
7
10
12 7, 10
• Niveau N4 :
Les sommets 7 et 10 sont exempts de précédent donc N4 = {7, 10}.
On considère ensuite l’ensemble de sommets
X5 = X4 − N4 = {12}
On “barre” tous les sommets 7, 10 dans le tableau précédent.
sommet x précédent(s) de x
12
• Niveau N5 :
Le sommet 12 est exempt de précédent donc N5 = {12}.
Bien évidemment, on a r(1) = 0, r(3) = r(5) = r(8) = 1, r(2) = r(6) = r(9) = 2, r(4) = r(11) = r(13) = 3,
r(7) = r(10) = 4, r(12) = 5.
Pour chaque sommet, la valeur donnée indique la longueur du plus court chemin reliant le niveau
N0 à ce sommet.
Il y a deux plus courts chemins reliant x1 à x2 : (x1 , x3 , x2 ) et (x1 , x8 , x2 ) de longueur 3. Pour les chemins
de longueur minimale reliant x1 à x12 , on part de x12 , on chemine dans le sens contraire des flèches dans le
graphe 1-minimal et on retrouve ainsi les chemins :
(x1 , x3 , x2 , x11 , x7 , x12 ) et (x1 , x8 , x2 , x11 , x7 , x12 )
1.2. GRAPHES VALUÉS ET CHEMINS CRITIQUES 19
Remarque 1.2.3 Sur la figure 1.20, on a repassé en traits épais les arcs 1-minimaux au fur et à mesure qu’ils
ont été déterminés. La marque de chaque sommet xk c’est-à-dire αk est la longueur d’un plus court chemin
reliant le sommet x1 au sommet considéré xk . Il n’y a pas qu’un seul chemin reliant le sommet x1 à un sommet
donné de longueur minimale. Par exemple, les chemins (x1 , x3 , x2 , x11 , x7 , x12 ) et (x1 , x8 , x2 , x11 , x7 , x12 ) sont
de longueur 12 et sont les seuls à relier x1 à x12 .
α1 = 0
αj = max[αi + vij ]
où les xi sont les précédents de xj . αn représente alors la valeur maximale du chemin entre x1 et xn .
Reprenons l’exemple 1.2.3 précédent, le graphe étant ordonnancé par niveaux. Recherchons un graphe 1-
maximal. Les calculs sont identiques à l’étude précédente en remplaçant minimum par maximum.
• α1 = 0
• α3 = max[α1 + v13 ] = max[0 + 2] = 2
• α5 = max[α1 + v15 ] = max[0 + 2] = 2
• α8 = max[α1 + v18 ] = max[0 + 1] = 1
• α2 = max[α3 + v32 , α1 + v12 , α5 + v52 , α8 + v82 ] = max[2 + 1, 0 + 4, 2 + 3, 1 + 2] = 5
• α6 = max[α5 + v56 , α8 + v86 ] = max[2 + 5, 1 + 2] = 7
• α9 = max[α1 + v19 , α8 + v89 ] = max[0 + 9, 1 + 8] = 9
• α4 = max[α1 + v14 , α2 + v24 , α3 + v34 ] = max[0 + 7, 5 + 5, 2 + 3] = 10
• α11 = max[α2 + v2,11 , α5 + v5,11 , α6 + v6,11 ] = max[5 + 4, 2 + 6, 7 + 6] = 13
• α13 = max[α6 + v6,13 , α8 + v8,13 ] = max[7 + 6, 1 + 7] = 13
• α10 = max[α4 + v4,10 , α11 + v11,10 ] = max[10 + 3, 13 + 7] = 20
• α7 = max[α11 + v11,7 , α13 + v13,7 , α9 + v97 ] = max[13 + 3, 13 + 5, 9 + 3] = 18
• α12 = max[α4 + v4,12 , α10 + v10,12 , α11 + v11,12 , α7 + v7,12 , α9 + v9,12 = max[10 + 8, 20 + 5, 13 + 6, 18 +
2, 9 + 5] = 25
Le graphe prend maintenant les valeurs indiquées par la figure 1.21.
Remarque 1.2.4
• Sur la figure 1.21, on a repassé en traits épais les arcs 1-maximaux au fur et à mesure qu’ils ont été
déterminés. La marque de chaque sommet xk c’est-à-dire αk est la longueur d’un plus long chemin
reliant le sommet x1 au sommet considéré xk . Il n’y a pas qu’un seul chemin reliant le sommet x1 à un
sommet donné de longueur maximale. Par exemple, le chemin (x1 , x5 , x6 , x11 , x10 , x12 ) est de longueur
25 et est le seul à relier x1 à x12 . Les chemins reliant x1 à x9 sont au nombre de 2 à savoir (x1 , x9 ) et
(x1 , x8 , x9 ), de longueur maximale 9.
• Sur la figure 1.22 ci-après, on a repris le graphe sous sa forme initiale puis on a représenté les plus
courts chemins reliant le sommet x1 au sommet x12 en trait pointillé ainsi que le plus long chemin de
x1 à x12 en trait double.
• On voit que sous sa forme ordonnancée (lorsque cela est possible), non seulement le graphe est plus
lisible, mais permet de mettre en place un procédé très rapide de recherche de chemins extrémaux.
Il existe par ailleurs d’autres algorithmes applicables lorsque le graphe présente des circuits. On s’est
borné au cas le plus courant.
20 CHAPITRE 1. QUELQUES RAPPELS SUR LES GRAPHES
on verra que l’établissement du planning relatif à la réalisation d’une tâche conduit à considérer
un graphe dans lequel tout arc (xi , xj ) représente une opération, auquel on associe le nombre vij
représentant la durée de l’opération. Tout sommet traduit la fin d’une opération. L’extrémité d’un arc
coı̈ncide avec l’origine d’un autre si et seulement si l’opération associée au premier est achevée afin
que celle associée au second puisse débuter. La durée totale de réalisation d’un programme ne peut
être inférieure à la somme des durées prises sur le chemin le plus défavorable depuis le sommet x0
début des travaux jusqu’au sommet xn fin des travaux, c’est-à-dire les chemins de longueur maximale
de x0 à xn . Un tel chemin est un chemin critique. Pour que la durée de l’opération soit minimale,
il est nécessaire que sur ce chemin critique, lorsque deux opérations se suivent, la deuxième débute
exactement lorsque la première se termine.
Opérations A B C D E F G H I J K L
Durée en semaines 32 13 4 3 6 32 20 8 13 38 42 39
D’autre part, on a constaté que l’opération B devait être précédée de l’opération A et suivie des opérations
C, D, E et F, que les opérations C et D devaient précéder l’opération G, que les opérations H et J, enfin,
devaient suivre les opérations E, F et G et précéder les opérations I, K et L.
Déterminer la durée minimale du projet.
Exercice 7 Une entreprise connaı̂t une croissance importante créant de gros besoins en locaux de construc-
tion et aussi de stockage. Il en résulte une grande dispersion des différents bâtiments. Le tableau ci-dessous
indique le temps en minutes que mettent les navettes pour joindre les différents points :
XXX
XXX Arrivée
XXX A B C D E F G H I J
Départ XX
A 36 20 30 16 18
B 24 16
C 28
D 16
E 14 18 26 28
F 10 12
G 8
H 4
I 12
J
3. Quel est le chemin que doit emprunter un employé désirant se rendre du point A au point J en un
temps minimal ? Quel est ce temps ?
Exercice 8
Exercice
9 Une entreprise de transport SUISSEXPORT dont le siège est situé à Berne doit effectuer
de fréquentes livraisons à Milan, en dehors de la période hivernale. Ses véhicules doivent donc traverser le
massif des Alpes : leur gabarit interdit l’usage des tunnels ferroviaires (Simplon, Saint-Gothard, Lötsch-
berg,. . . ) qui, sinon, faciliteraient le voyage.
Vus la fréquence et le coût de ces livraisons, l’entreprise désire déterminer l’itinéraire le plus court de Berne
à Milan.
À l’aide d’un graphe que vous aurez tracé, déterminer l’itinéraire demandé et préciser son kilométrage.
1.3. EXERCICES RÉCAPITULATIFS 23
Exercice 10 On se donne le réseau routier ci-dessous où chaque sommet représente un entrepôt et chaque
arc, une route entre deux entrepôts ; chaque route est supposée à sens unique, le sens de progression étant
indiqué par la direction de l’arc.
1. Le premier problème est le suivant : tous les matins, plusieurs chauffeurs doivent acheminer le courrier
interne et les colis aux différents entrepôts de l’entreprise. On suppose que le centre de tri est l’entrepôt
B, c’est donc le point de départ des navettes.
(a) Sachant qu’une même navette ne peut emprunter deux fois le même arc (ce qui est permis pour
deux navettes différentes), combien faut-il de chauffeurs au minimum pour acheminer à chaque
entrepôt son courrier ? (certains arcs peuvent ne pas être parcourus.)
(b) En supposant que chaque route soit longue de 100 mètres, quelle distance totale parcourent
chaque matin les navettes ?
2. Le second problème s’énonce comme suit : on se donne ci-dessous, pour chaque entrepôt, le temps
moyen (en minutes) nécessaire à la livraison du courrier (trajet et/ou déchargement) des entrepôts
suivants :
Entrepôt i A B C D E F G H I J K
Temps t(i) 5 6 3 8 4 5 6 20 4 4 9
Par exemple, une fois le courrier livré en A, il faut 5 minutes pour livrer le ou les entrepôts suivants.
Déterminer la durée minimale moyenne de livraison du courrier dans cette entreprise.
Exercice
11 Une entreprise contacte votre société d’entreposage pour stocker des produits alimentaires.
Vos différents entrepôts sont localisés géographiquement à l’aide de la carte fournie ci-après.
24 CHAPITRE 1. QUELQUES RAPPELS SUR LES GRAPHES
Dans le cadre du contrat, l’entreprise vous demande de déterminer les chemins minimaux et maximaux du
réseau afin d’optimiser les prix de transport de leurs marchandises.
Les entrepôts sont schématisés par des points et les routes reliant ces différents entrepôts par des droites.
On supposera que les routes sont à sens unique, leur direction étant indiquée par les arcs orientés.
La valuation de chaque arc indique la distance séparant les entrepôts reliés par cet arc. Par exemple, les
entrepôts G et F sont distants de 160 mètres.
1. Établir le dictionnaire des précédents puis le dictionnaire des suivants des sommets du graphe.
2. Utiliser le dictionnaire des précédents pour ordonnancer le graphe par niveaux.
3. Représenter le graphe sous sa forme ordonnancée.
On précise que les entrepôts d’entrée sont ceux appartenant au niveau N0 et que les entrepôts de sortie sont
ceux appartenant au dernier niveau.
4. Déterminer la longueur du chemin minimal menant d’un entrepôt d’entrée à un entrepôt de sortie
tout en précisant ce chemin.
5. Déterminer la longueur du chemin maximal menant d’un entrepôt d’entrée à un entrepôt de sortie
tout en précisant ce chemin.
Chapitre 2
Problèmes d’ordonnancement
2.1 Contexte
Les retards apportés aux réalisations de projets aux livraisons ponctuelles aux clients dus en général à
– la mauvaise conception du produit à fabriquer,
– la mauvaise gestion des stocks,
– la fixation arbitraire d’un calendrier de fin des travaux sans rapport ni avec l’évolution réelle des
différentes tâches ni avec les moyens dont on dispose effectivement,
– le manque de coordination entre les responsables des opérations concernant l’ordre de passage des
différentes tâches et leur fin,
sont autant de problèmes que les entreprises doivent affronter aujourd’hui. Afin de minimiser ces retards,
l’organisation des tâches devient indispensable et fait intervenir des notions très particulières.
Un projet est un ensemble d’opérations permettant d’atteindre un objet fixé, ces opérations étant sou-
mises à un certain nombre de contraintes.
– Les contraintes potentielles On distingue deux cas :
. Les contraintes de succession ou contraintes d’antériorité qui se traduisent par le fait qu’une tâche j
ne peut débuter que lorsque la tâche i est achevée ou bien se trouve à un certain degré d’exécution.
. Les contraintes de localisation temporelle, permettant de localiser dans le temps chacune des tâches
en cours d’exécution ; la tâche i doit être achevée à telle date ou au contraire son exécution ne doit
jamais commencer avant telle date.
– Les contraintes disjonctives. Elles imposent la réalisation non simultanée de certaines tâches. Ces
contraintes se manifestent en particulier lorsque les disponibilités en matériel ou personnel sont insuf-
fisantes.
– Les contraintes cumulatives. Elles limitent les possibilités d’ordonnancement car elles tiennent compte
de tous les facteurs productifs, hommes, matériels, moyens financiers.
Une tâche est une opération. L’ensemble des tâches forme le projet.
On associe à chaque tâche sa durée et une contrainte d’antériorité par rapport aux autres tâches. On
dira que xi est immédiatement antérieure à xj si xj ne peut débuter que lorsque xi est achevée.
25
26 CHAPITRE 2. PROBLÈMES D’ORDONNANCEMENT
2.6 Exercices
Exercice 12 Votre société a besoin de vos services pour implanter la zone de stockage d’un entrepôt
qu’elle vient d’acquérir. Vous prenez connaissance des différentes tâches qu’il faudra réaliser :
2. Vérifier qu’il n’y a pas de circuit dans le graphe défini par le dictionnaire de la question précédente.
3. Ordonnancer les tâches du graphe par niveaux.
4. Visualiser les différentes tâches à accomplir.
5. Evaluer la durée totale du projet.
Exercice 13 Votre société désire faire construire un nouvel entrepôt commercial dont vous devez réaliser
la mise en chantier. Vous prenez connaissance des différentes tâches qu’il faudra réaliser :
Votre mission (si vous l’acceptez) est d’optimiser la mise en chantier de l’entrepôt
1. Etablir le tableau des antériorités (ou dictionnaire des précédents).
2. Vérifier qu’il n’y a pas de circuit dans le graphe défini par le dictionnaire de la question précédente.
3. Ordonnancer les tâches du graphe par niveaux.
4. Visualiser les différentes tâches à accomplir.
5. Evaluer la durée totale du projet.
28 CHAPITRE 2. PROBLÈMES D’ORDONNANCEMENT
Chapitre 3
La méthode MPM
3.1 Le graphe
3.1.1 Eléments du graphe
– Chaque opération est représentée par un sommet, chaque sommet est représenté par un rectangle dans
lequel on inscrit le numéro de code de la tâche associée. Il convient de considérer que le sommet no i
représente le début de la tâche i.
– Chaque arc représente une contrainte de succession.
– On introduit une opération initiale repérée par un sommet noté E (pour Entrée) ou D (pour Départ ou
Démarrage) ou 1 (première étape), ce qui correspond au démarrage des travaux, ainsi qu’une opération
terminale ou finale à laquelle on associe un sommet numéroté F (pour Final) ou n (dernière étape),
qui correspond à la livraison des travaux.
Remarque 3.1.1 Il est inutile d’introduire des sommets qui correspondraient au début de la réalisation de
certaines étapes ou objectifs partiels ou de période d’attente.
Par contre, si l’opération b peut démarrer 2 unités de temps après a, on aura En conclusion, la valeur
potentielle associée à l’arc (xi , xj ) est le délai minimum de la tâche xi , au bout duquel peut démarrer la
tâche xj .
29
30 CHAPITRE 3. LA MÉTHODE MPM
Correction : On vérifie tout d’abord que le graphe sagittal associé au projet est bien sans circuit. On
peut ensuite ordonnancer ce graphe par niveaux, ceci à l’aide du dictionnaire des précédents.
x a b c d e f g
P (x) a a b, d b, d c, f
On a :
• N0 = {a, b} et X1 = {c, d, e, f, g}.
x P (x)
c
d
e d
f d
g c, f
• N2 = {e, f } et X3 = {g}.
x P (x)
g
3.1. LE GRAPHE 31
• N3 = {g}
On a représenté sur les arcs d’origine a , la durée opératoire de la tâche a. Si l’on note ”D” le début, ”F”
la fin, les arcs issus de D sont affectés de potentiels nuls puisque la tâche correspondante est de durée nulle.
Les tâches a et b peuvent commencer dès le début.
mais les 3 sommets b1 , b2 et b3 peuvent être condensés en un seul b , en modifiant correctement les
potentiels sur les arcs issus de b :
Exemple 3.1.5
• b de durée 2 jours succède à a de durée 3 jours mais ne peut débuter qu’après un délai de 10 jours
après le début des travaux.
3.2. EXERCICE SYNTHÉTIQUE CORRIGÉ : CONSTRUCTION D’UN PONT 33
• b de durée 2 jours, c de durée 1 jour succèdent à a de durée 3 jours mais ne peuvent démarrer que 10
jours après le début des travaux.
Remarque 3.1.2 Les graphes ainsi obtenus sont exempts de circuit, sans quoi une opération pourrait faire
suite à elle même. On peut donc les ordonnancer en niveaux.
x A B C D E F G H J K L M N P Q
P (x) A B C D B B F,C H,D J E L,K K E K
x ̸A B C D E F G H J K L M N P Q
P (x) ̸A B C D B B F,C H,D J E L,K K E K
x ̸A ̸B C D E F G H J K L M N P Q
P (x) ̸A ̸B C D ̸B ̸B F,C H,D J E L,K K E K
x ̸A ̸B ̸C D E ̸F ̸G H J K L M N P Q
P (x) ̸A ̸B ̸C D ̸B ̸B ̸F, ̸C H,D J E L,K K E K
3.2. EXERCICE SYNTHÉTIQUE CORRIGÉ : CONSTRUCTION D’UN PONT 35
x ̸A ̸B ̸C ̸D E ̸F ̸G ̸H J K L M N P Q
P (x) ̸A ̸B ̸C ̸D ̸B ̸B ̸F,̸C ̸H,̸D J E L,K K E K
x ̸A ̸B ̸C ̸D ̸E ̸F ̸G ̸H ̸J K L M N P Q
P (x) ̸A ̸B ̸C ̸D ̸B ̸B ̸F,̸C ̸H,̸D ̸J ̸E L,K K ̸E K
x ̸A ̸B ̸C ̸D ̸E ̸F ̸G ̸H ̸J ̸K ̸L M N ̸P Q
P (x) ̸A ̸B ̸C ̸D ̸B ̸B ̸F,̸C ̸H,̸D ̸J ̸E ̸L,̸K ̸K ̸E ̸K
2. Le graphe ordonnancé :
Remarque 3.2.1
– La tâche L peut débuter 3 jours après le début de E alors que E dure 7 jours :
36 CHAPITRE 3. LA MÉTHODE MPM
– La tâche N suit K 3 jours après son début, K dure 7 jours, K précède aussi Q, M débute 3 jours
après le début de K :
T1 = 0
Ti = max [Th + dh,i ]
h∈P (i)
où
• P (i) est l’ensemble des précédents de i et Th la date de début au plus tôt de la tâche de niveau
précédent.
• dh,i est le potentiel (ou délai) porté sur l’arc (h, i) c’est-à-dire le délai minimum après le début de la
tâche h, au bout duquel peut démarrer la tâche i.
Remarque 3.3.1
– Les arcs du chemin critique sont en trait gras : (A,B,F,H,J,K,Q).
– 19 est la date au plus tôt de début de la tâche fin. La durée minimale des travaux est de 19 jours.
– Les tâches critiques sont repassées en traits gras, ce sont les tâches A,B,F,H,J,K et Q. Ce sont les
sommets qui jalonnent le chemin critique. Si le début d’une opération critique est retardée, tout le
programme se trouve retardé de la même durée. Il est donc formellement interdit de retarder une tâche
critique. Par contre, les autres tâches peuvent l’être.
Remarque 3.4.1 Pour les tâches critiques qui ne peuvent tolérer aucun retard , on a
Ti = Ti⋆
Tn⋆ = Tn
Ti⋆ = min (Tj⋆ − di,j )
j∈S(i)
où
• S(i) est l’ensemble des suivants du sommet i
• di,j est le potentiel porté sur l’arc (i, j).
Le chemin critique peut être obtenu à partir des deux ordonnancements, les tâches critiques étant celles
pour lesquelles Ti = Ti⋆ . Chaque sommet sera noté :
• TK
⋆ = min(T ⋆ − 3, T ⋆ − 7, T ⋆ − 3) = min(18 − 3, 17 − 7, 18 − 3) = 10
M Q N
• TE⋆ = min(TP⋆ − 7, TL⋆ − 3) = min(17 − 7, 17 − 3) = 10
• TJ⋆ = min(TK
⋆ − 1) = min(10 − 1) = 9
où Ti est la date au plus tôt du début de la tâche i et Ti⋆ est la date au plus tard de début de la tâche i.
La marge totale de la tâche i est le délai ou retard maximum que l’on peut apporter à la mise en route de
cette tâche sans répercussion sur le délai d’achèvement du programme.
Remarque 3.5.1 Les marges totales des tâches critiques sont nécessairement nulles.
où S(i) désigne l’ensemble des suivants du sommet i et dij désigne le potentiel porté par l’arc (i, j). La marge
libre de la tâche i est le délai ou retard maximum que l’on peut apporter à sa mise en route par rapport à
sa date au plus tôt Ti sans retarder la date de début au plus tôt de toute autre tâche.
où S(i) est l’ensemble des suivants de i. Si pour une tâche i, la marge certaine est strictement positive, cette
marge certaine représente le délai ou le retard maximum que l’on peut apporter à sa mise en route sans
perturber pour autant les dates attendues des événements postérieurs et ceci, bien que la tâche i n’ait été
réalisée qu’à sa date limite.
On remarquera que les marges certaines des tâches critiques sont nécessairement nulles.
3.5.4 Exemple
Reprenons l’exemple du pont :
– Les marges totales :
Tâche A B C D E F G H J K L M N P Q
Ti⋆ 0 1 7 8 10 4 18 8 9 10 17 18 18 17 17
Ti 0 1 4 5 6 4 4 8 9 10 9 13 13 13 17
mT (i) 0 0 3 3 4 0 14 0 0 0 8 5 5 4 0
On retrouve les marges totales des tâches critiques nulles (en effet, pour ces tâches critiques Ti = Ti⋆ ).
Par exemple, mT (G) = 14 ce qui signifie que 14 jours est le délai maximum que l’on peut apporter
à la mise en route de cette tâche (par rapport à sa date au plus tôt) sans répercussion sur le délai
d’achèvement du programme.
Signification :
. Comme mT (E) = 0, la tâche E peut démarrer au maximum 4 jours après sa date au plus tôt sans
retarder la fin des travaux. Comme mL (E) = 0, si l’on retarde la tâche E, par rapport à sa date au
plus tôt, les dates au plus tôt des autres tâches sont retardées.
. Comme mL (L), le seul suivant de L étant M, si l’on retarde la tâche L de 3 jours par rapport à sa
date au plus tôt, la date au plus tôt (13 jours) de la tâche M ne sera pas retardée. Comme mT (8),
on peut retarder la tâche L de 8 jours par rapport à sa date au plus tôt sans retarder la réalisation
du chantier mais dans ce cas, la tâche M sera retardée de 8 − 3 = 5 jours par rapport à sa date au
plus tôt.
3.6. MÉTHODE MPM PRÉSENTÉE SOUS FORME DE TABLEAUX 41
3, 17 − 10 − 7, 18 − 10 − 3)) = max(0, 0) = 0
• mC (M ) = max(0, min(Tn − TM
⋆ −d
M n )) = max(0, min(14 − 1 − 18)) = max(0, −5) = 0
• mC (Q) = max(0, min(Tn − TQ⋆ − dP n )) = max(0, min(19 − 17 − 2)) = max(0, 0) = 0
• mC (N ) = max(0, min(Tn − TN⋆ − dN n )) = max(0, min(14 − 18 − 1)) = max(0, −5) = 0
Les marges certaines de toutes les tâches sont nulles. Aucun délai ne peut être apporté à la mise
en route des tâches réalisées à leur date limite sans perturber les dates attendues des événements
postérieurs.
9:J 10 : K 13 : L 17 : M 17 : N 13 : P 17 : Q 19 : ω
5 D:1 9 J :1 6 E:7 10 K:7 10 K:7 6 E:7 10 K:7 4 G:1
8 H:1 13 L:1 17 M :1
17 N :1
13 P :2
17 Q:2
– Le tableau est complété de la façon suivante : à gauche des lettres représentant les tâches, sont inscrites
les dates au plus tôt de début Ti et ceci sur la première ligne et sur les lignes suivantes dans les sous-
colonnes de gauche. Ces dates de début au plus tôt sont déterminées par l’algorithme précédent, on
progresse selon les niveaux croissants dans le graphe, on écrit 0 à gauche de α partout où α est écrit.
Appelons colonne complète toute colonne dont les deux sous-colonnes sont entièrement remplies. Ainsi,
la colonne se référant à A est complète.
• La somme 0 + 0 des nombres figurant dans les deux sous-colonnes dans la même ligne donne la date
au plus tôt de A que l’on inscrit à gauche de tous les A du tableau.
• La colonne B est ainsi complète. La date de début au plus tôt de B est la somme 0 + 1 = 1 que l’on
inscrit à gauche de tous les B du tableau.
• Les colonnes C,F,G sont alors complètes. Les dates de début au plus tôt de C,F,G sont égales à
1 + 3 = 4 à inscrire à gauche de tous les C,F,G du tableau.
• Les colonnes de D et H sont complètes et 4 + 1 = 5 est la date de début au plus tôt de D à inscrire
à gauche de tous les D du tableau, la date de début au plus tôt de H est max(4 + 1, 4 + 4) = 8, on
inscrit 8 à gauche de tous les H du tableau...
• date au plus tôt de J : max(5 + 1, 8 + 1) = 9
• date au plus tôt de K : 9 + 1 = 10
• date au plus tôt de M : max(10 + 3, 9 + 1) = 13
• date au plus tôt de N : 10 + 3 = 13
• date au plus tôt de P : 6 + 7 = 13
• date au plus tôt de Q : 10 + 7 = 17
• date au plus tôt de ω : max(1 + 1, 13 + 1, 13 + 1, 13 + 2, 17 + 2) = 19
– Cette méthode n’est pas différente de celle de l’algorithme des précédents pour déterminer les ni-
veaux d’un graphe sans circuit. La notion de colonne complète correspond à celle de ligne vide dans
l’algorithme du dictionnaire des précédents. On voit ainsi apparaı̂tre les différents niveaux :
{α}, {A}, {C,F,G}, {D,H}, {E,J}, {K,L,P}, {M,N,Q}, {ω}
– Obtention du chemin critique :
• On part de la colonne ω et on souligne son précédent minimum Q dans la sous-colonne de droite
(précédent qui réalise le maximum de la somme des nombres par lignes dans les deux sous-colonnes).
• Dans la colonne Q, on souligne son précédent minimum K (unique précédent).
• Dans la colonne J, on souligne H, son précédent minimum (précédent qui réalise le maximum de la
somme des nombres par lignes dans les deux sous-colonnes).
• Dans la colonne H, on souligne F.
• Dans la colonne F, on souligne B.
• Dans la colonne B, on souligne A.
• Dans la colonne A, on souligne α.
On obtient ainsi le chemin critique en commençant par ω : ω Q K J H F B A α soit α, A B F H J K
Q ω en commençant par α.
3.6. MÉTHODE MPM PRÉSENTÉE SOUS FORME DE TABLEAUX 43
J :9 K : 10 L : 18 M : 18 N : 18 P : 17 Q : 17 ω : 19
K:1 10 H:3 18 M :1 18 ω:1 19 ω:1 19 ω:2 19 ω:2 19
N :3 18
Q:7 17
Ici, les dates de début au plus tard sont inscrites à droite de chaque lettre représentant une tâche.
• Conformément à l’algorithme de l’ordonnancement au plus tard, on commence par inscrire 19, durée
minimale du programme obtenue dans le tableau précédent (19 : ω), à droite de tous les ω du tableau
correspondant à la date de début au plus tard de ω.
• Les colonnes G,M,N,P,Q sont alors complètes, d’où les dates de début au plus tard des tâches corres-
pondantes. Pour G, on a 19 − 1 = 18 et on reporte 18 à droite de tous les G du tableau. Pour M, on a
19 − 1 = 18, on reporte 18 à droite de tous les M du tableau. Pour N, on a 19 − 1 = 18 et on reporte
18 à droite de tous les N du tableau. Pour P, on obtient 19 − 2 = 17 et on reporte 17 à droite de tous
les P du tableau. Enfin pour Q, on obtient 19 − 2 = 17 et on reporte 17 à droite de tous les Q du
tableau.
• Les colonnes K et L sont alors complètes. La date de début au plus tard de K est alors min(18 − 3, 18 −
3, 17 − 7) = 10, on reporte 10 à droite de tous les K du tableau. Pour L, la date de début au plus tard
est 18 − 1 = 17. On reporte 17 à droite de tous les L du tableau.
• Les colonnes de E et J sont alors complètes. La date de début au plus tard de E est min(18−3, 17−7) =
10. On reporte 10 à droite de tous les E du tableau. Pour J, la date de début au plus tard est de
10 − 1 = 9. On reporte 9 à droite de tous les J du tableau.
• Les colonnes D et H sont lors complètes. La date d ébut au plus tard de H est 9 − 1 = 8. On reporte 8
à droite de tous les H du tableau. Celle de D est min(10 − 1, 9 − 1) = 8. On reporte 8 à droite de tous
les D du tableau.
• Les colonnes C et F sont complètes. La date de début au plus tard de C est min(8 − 1, 8 − 1) = 7. On
reporte 7 à droite de tous les C du tableau. Celle de F est 8 − 4 = 4. On reporte 4 à droite de tous les
F du tableau.
• La colonne B est alors complète. La date de début au plus tard de B est min(7 − 3, 4 − 3, 18 − 3) = 1.
On reporte 1 à droite de tous les B du tableau.
• La colonne A est alors complète. La date de début au plus tard de A est 1 − 1 = 0. On reporte 0 à
droite de tous les A du tableau.
Pour chaque sommet, on a souligné le suivant qui réalise le minimum de la différence des nombres par lignes
dans les deux sous-colonnes.
souligne F. Dans la colonne F, le suivant qui réalise le minimum est H, qu’on souligne. Dans la colonne H,
le suivant qui réalise le minimum est J, qu’on souligne. Dans la colonne J, le suivant qui réalise le minimum
est K, qu’on souligne. Dans la colonne K, le suivant qui réalise le minimum est Q, qu’on souligne. Enfin,
dans la colonne Q, le suivant qui réalise le minimum est ω, qu’on souligne. Le chemin critique est alors :
(α,A,B,F,H,J,K,Q,ω)
3.7 Exercices
Exercice 14 Un entrepôt a procédé à la définition d’un certain nombre de tâches à effectuer et à l’évaluation
de leur durée. Le tableau suivant est l’aboutissement de ce travail.
1. Ordonnancer le graphe par niveaux. Tracer le graphe associé.
2. Indiquer les dates de début au plus tôt ainsi que les dates au plus tard de chaque tâche. On précisera
sur la copie l’algorithme (le programme) permettant la détermination de date au plus tôt de la tâche
k ainsi que celui donnant la date de début au plus tard de la tâche j.
3. En déduire le(s) chemin(s) critique(s) ainsi que la durée minimale du projet.
4. Calculer les marges libres et les marges totales de toutes les tâches. Donner la signification des marges
trouvées pour les tâches d, i et o uniquement.
Exercice 15 Un étudiant en Licence 2 Logistique se voit proposer un stage de deux mois dans une entre-
prise assemblant des téléphones portables. On lui propose de mener à bien un projet lié à la gestion des flux
des composants du téléphone produit. L’entreprise a procédé à la définition d’un certain nombre de tâches
à effectuer et à l’évaluation de leur durée. Les conditions d’antériorité liant ces tâches et les durées en jours
de celles-ci, sont rassemblées dans le tableau ci-dessous :
3.7. EXERCICES 45
Tâches A B C D E F G H I J K L M N
Tâches
immédiatement D B,H A A D B,D,F B,I,E D,E F,G,H G,H H,I,E J,G K,J
antérieures
Durées 10 14 14 8 12 22 25 18 6 9 13 8 10 9
2. Afin de diminuer la durée minimale du projet, on propose à l’étudiant différentes améliorations, les
durées initiales des tâches ne sont pas modifiées mais certaines d’entre-elles peuvent commencer avant
l’achèvement des tâches précédentes.
* La tâche F peut commencer 4 jours après le début de D.
* La tâche G peut commencer 15 jours après le début de F et 10 jours après le début de B.
* La tâche H peut commencer 7 jours après le début de B et 2 jours après le début de I.
* La tâche K peut commencer 15 jours après le début de G et 12 jours après le début de H.
* La tâche N peut commencer 5 jours après le début de J.
Tâches A B C D E F G H I J K L M N P
Tâches
immédiatement A B A A B,E A,D,E C,F F,H,K K E,F,G I,J D,G K,G,M J,M,N
antérieures
Durées 5 4 7 6 3 8 4 13 4 4 7 5 6 4 4
2. (a) Déterminer les dates de début au plus tôt de chacune des tâches du projet en précisant pour une
tâche quelconque, la signification de cette date.
(b) En déduire la durée minimale du projet ainsi que le chemin critique.
(a) Déterminer les dates de début au plus tard de chacune des tâches en précisant pour une tâche
quelconque, la signification de cette date.
(b) Que peut-on déduire des tâches pour lesquelles les dates au plus tôt et au plus tard sont égales ?
3. (a) Déterminer les marges totales et les marges libres de chacune des tâches du projet.
(b) On démarre la tâche G quatre jours après sa date au plus tôt, que se passe-t-il alors ?
Exercice
17 Vous travaillez actuellement sur un projet de construction d’un atelier de finition. Le début
des travaux est prévu pour le 1er mai. Le détail et le durée des travaux de chaque corps de métier vous sont
donnés ci-après. Afin de déterminer la date d’achèvement de l’atelier et d’éviter les retards qui seraient dus
à l’imprévision, vous êtes chargés de visualiser le projet.
À partir du tableau des antériorités ci-après (donnant les tâches précédentes et antécédentes),
1. Trouver les tâches immédiatement antérieures à chaque tâche.
2. Ordonnancer les tâches du projet par niveaux.
3. Déterminer les dates au plus tôt de chacune des tâches du projet en précisant pour l’une d’entre-elles
le calcul réalisé. Quelle est la date au plus tôt de réalisation du projet ?
4. Faire apparaı̂tre sur le graphe le chemin critique. Que peut-on dire sur les tâches qui composent ce
chemin ?
5. Déterminer les dates au plus tard de chacune des tâches du projet en précisant pour l’une d’entre-elles
le calcul réalisé.
6. Déterminer pour chacune des tâches qui composent le projet sa marge totale et sa marge libre.
Durée Tâches
Symboles Tâches
(en semaines) antérieures
Durée Tâches
Symboles Tâches
(en semaines) antérieures
O Peintures 5 N
P Electricité 3ème étape 1 O
Q Revêtements des sols 5 P
R Crépissage extérieur 3 O
Exercice
18 L’entreprise où vous travaillez a reçu commande d’une nouvelle machine-outil très perfec-
tionnée. Le délai de livraison est absolument impératif. Vous êtes chargé(e) d’établir les prévisions de durée
de fabrication.
À partir du tableau des antériorités ci-dessous (donnant les tâches précédentes et antécédentes),
1. Trouver les tâches immédiatement antérieures à chaque tâche.
2. Ordonnancer les tâches du projet par niveaux.
3. Déterminer les dates au plus tôt de chacune des tâches du projet en précisant pour l’une d’entre-elles
le calcul réalisé. Quelle est la date au plus tôt de réalisation du projet ?
4. Faire apparaı̂tre sur le graphe le chemin critique. Que peut-on dire sur les tâches qui composent ce
chemin ?
5. Déterminer les dates au plus tard de chacune des tâches du projet en précisant pour l’une d’entre-elles
le calcul réalisé.
6. Déterminer pour chacune des tâches qui composent le projet sa marge totale et sa marge libre.
Durée Tâches
Symboles Tâches
(en mois) antérieures
A Fabrication de l’élément 1 3 −−
B Fabrication de l’élément 2 2 A
C Assemblage a des éléments 1 et 2 1 A,B
D Fabrication de l’élément 3 2 C
E Assemblage b (assemblage a avec l’élément 3) 2 C,D
Fabrication de l’élément 4 quand les
F 3 A,B
éléments 1 et 2 sont terminés
Fabrication de l’élément 5 en même temps
G 24 A
que la fabrication de l’élément 4
Fabrication de l’élément 6 quand la fabrication de
H 4 G
l’élément 5 est terminée
I Fabrication de l’élément 7 6 H
J Assemblage d des éléments 5 et 6 1 G,H
K Assemblage c (assemblage b avec l’élément 4) 2 E,F
L Assemblage e (assemblage c,d avec l’élément 7) 7 I,J,K
48 CHAPITRE 3. LA MÉTHODE MPM
Exercice 19 Une importante société de magasins alimentaires à grande surface diversifie son activité
en créant des commerces dans de petites villes. La société crée le fonds de commerce qui est ensuite géré de
façon autonome par un commerçant franchisé.
La société réalise tout d’abord une étude d’implantation : étude de marché sur un certain rayon d’ac-
tion et choix de la localité où sera installé le commerce.
À partir du tableau des antériorités de la page suivante (donnant les tâches précédentes et antécédentes),
Durée Tâches
Symb. Tâches
(jours ouvr.) antérieures
Exercice 20 On souhaite réaliser un projet dont les principales tâches sont données ci-dessous et pour
lesquelles on précise les suivants ainsi que la durée :
Lancement du projet 1 2 0
2 Caractéristiques des charges 3, 4 5
3 Caractéristiques des flux entrants 8 4
Recueil des données
4 Caractéristiques des flux sortants 5, 8 4
5 Caractéristiques des commandes 8 4
6 Fonctionnalités générales 8 8
7 Contraintes diverses 8 3
8 Dimensionnement statique 10 7
9 Dimensionnement dynamique 10 8
1. Quelle est la condition nécessaire pour qu’un graphe quelconque puisse être ordonnancé par niveaux ?
Prouver que cette condition est vérifiée dans le cadre de l’exercice.
(a) Indiquer les dates de début au plus tôt ainsi que les dates de début au plus tard de chaque tâche.
(b) En déduire le(s) chemin(s) critique(s) ainsi que la durée minimale du projet.
(c) Calculer les marges libres et les marges totales de toutes les tâches. Donner la signification des
marges trouvées pour les tâches 3 et 13 uniquement.
Exercice
21 La société Dupont S.A. spécialisée dans l’étude et la composition d’unités industrielles a
obtenu la maı̂trise d’œuvre pour l’installation d’une usine chimique. L’analyse du projet a permis de distin-
guer 14 phases de travaux différents : maçonnerie, plomberie, électricité, conditionnement d’air, traitement
des déchets, installations et essais machines, etc. Ces travaux sont désignés par les lettres de A à N.
La société responsable de cette implantation dispose de moyens (moyens propres en équipes spécialisées,
machines. . . auxquels s’ajoutent quelques sous-traitants) permettant l’exécution des travaux en parallèle,
sous réserve toutefois du respect des relations d’ordre montrées dans le tableau suivant. Ces relations sont
imposées par un ensemble de contraintes techniques.
Ce tableau montre également la durée prévue (en jours) de chacune des phases des travaux.
50 CHAPITRE 3. LA MÉTHODE MPM
Liste des travaux Durée prévue (en jours) Travaux antérieurs Suivants Marge totale
A 10 – B,G,N 10
B 25 A C,K 10
C 25 B,E,G J 0
D 20 – G 0
E 35 – C,F,H,K 10
F 20 E,G J 5
G 25 A,D C,F,K 0
H 15 E J 20
I 40 – – 100
J 30 C,F,H L 0
K 20 B,E,G M 25
L 40 J,M – 0
M 10 K,N L 25
N 15 A M 65
1. Quelle est la durée (en jours ouvrés) minimale de réalisation de ce projet ? Indiquer la séquence des
travaux qui détermine cette durée (travaux critiques).
2. Déterminer la marge totale pour chacune des phases du projet.
Exercice 22 La société SGTB (Société des Grands Travaux de la Bièvre) a reçu la maı̂trise d’œuvre
de la construction d’une piscine olympique sur un campus universitaire. Le tableau des antériorités des
tâches est le suivant :
A Excavation – 5 B,F
B Fondation A 2 C
C Pose de canalisations B 4 D
D Essais en pression C,G 8 E
E Etanchéité D 9 J
F Mise en place de la station d’épuration A 6 G
G Mise en place du chauffage F 5 D,H
H Raccordement électrique G 4 I
I Sonorisation sous-marine H 5 J
J Dallage E,I 6 K,L
K Construction des vestiaires J 8 M
L Construction du solarium J 2 M
M Mise en eau K,L 3 –
3.7. EXERCICES 51
Les travaux débutent le 1er avril. Chaque mois comporte 20 jours ouvrables.
1. Déterminer si l’inauguration peut avoir lieu comme prévu le 15 juin.
2. Lors de la pose des canalisations, on apprend que, suite à un incident technique, cette opération durera
6 jours de plus que prévu. Cela aura-t-il une influence sur le délai prévu ?
Exercice
23 Dans le cadre de la réforme hospitalière, les conseils d’administration de 3 centres hospi-
taliers voisins ont élaboré en commun un plan de rationnalisation de leurs activités. Tout en maintenant les
3 sites existants, ils ont décidé de fusionner en une seule entité appele HOPITAL NORD. La réorganisation
des unités de soins et de leur gestion implique l’interconnexion des réseaux informatiques des 3 sites. Deux
des 3 hôpitaux, désigns H1 et H2, sont déjà interconnectés ; vous participez à l’étude et à la mise en place
de la connexion du troisième hôpital, désigné H3.
L’évolution du réseau local du site H3 a été planifiée. Les tâches nécessaires à la réalisation de ce pro-
jet, leurs durées ainsi que les conditions d’antériorité qui les relient figurent dans le tableau ci-dessous :
La méthode PERT
4.1 Introduction
La méthode PERT (pour Program Evaluation Review Technique) s’est développée, parallèlement à la
méthode des potentiels métra (méthode MPM), aux Etats-Unis en 1958 pour la planification de la construc-
tion des sous-marins Polaris. Elle se distingue de la méthode des potentiels par le fait que les tâches ne sont
plus associées aux nœuds mais aux arcs du réseau.
Un premier problème se rencontre lorsqu’on veut tenir compte des contraintes de localisation temporelle.
Par exemple, on suppose qu’une tâche i ne peut commencer avant une date li . Il faut introduire un arc
joignant l’origine des travaux à l’origine de l’arc représentant la tâche i et ayant pour longueur la date en
question li . On est donc amené, dans ce cas, à ajouter un arc fictif qui ne correspond à aucune tâche.
Un second problème plus délicat, se rencontre pour les contraintes de succession temporelle. En effet, sup-
posons que la tâche 1 précède les tâches 2 et 3 et que la tâche 4 précède la tâche 3. On pourrait tracer le
graphe ci-dessous mais ce graphe introduit une contrainte supplémentaire qui implique que la tâche 4 doit
précéder la tâche 2. Pour résoudre ce problème, on ajoute un arc fictif de longueur nulle entre l’extrémité
de la tâche 1 et le début de la tâche 3 : Il conviendra donc d’être vigilant dans la construction du graphe
PERT. On remarquera également que le problème ne peut se produire que dans le cas où il y a au moins
54 CHAPITRE 4. LA MÉTHODE PERT
deux prédecesseurs et deux successeurs. Dans tous les autres cas, on peut construire le graphe sans ajouter
d’arc fictif.
N0 = {1}, N1 = {2}, N2 = {3, 7}, N3 = {4, 6, 8}, N4 = {5, 9}, N5 = {10}, N6 = {11}.
suivant un nœud correspondent à la date au plus tôt ti du nœud situé juste avant la tâche.
Reprenons l’exemple 4.3.1 et plus particulièrement la tâche 4 de durée 2. La date de début au plus tard de
son successeur direct c’est-à-dire la tâche 5 est de 17. La date de début au plus tard de la tâche 4 est donc
de 17 − 2 = 15 alors que la date de début au plus tard du nœud précédent la tâche dans le graphe est de
11. Ce 11 provient en fait de la tâche 6 qui est critique (16 − 5 = 11).
Il convient donc de procéder en deux temps. D’abord, on calcule le temps de début au plus tard des nœuds
comme dans la méthode des potentiels. Ensuite, on calcule la marge de la tâche (i, j) entre les nœuds i et j
définie par
Autrement dit, la marge est la différence entre le temps de d’ebut au plus tard du nœud j et à l’arrivée
au plus tôt à ce nœud pour la tâche (i, j) qui peut partir au plus tôt en ti du nœud i. On obtient alors
les dates au plus tard des tâches en additionnant à la date au plus tôt du nœud de départ, la marge de la tâche.
Tâche 1 2 3 4 5 6 7 8 9 10 11
Date au plus tôt 0 5 9 11 13 11 9 12 16 20 30
Marge 0 0 0 4 4 0 1 1 0 0 0
Date au plus tard 0 5 9 15 17 11 10 13 16 20 30
On remarquera que le chemin critique peut ne pas être unique. En effet, on peut avoir des chemins critiques
parallèles. Si par exemple, la durée de la tâche 4 est portée de 2 à 6, un second chemin critique apparı̂t dans
notre exemple :
On remarquera également que pour réduire la durée minimum de réalisation du projet, il faut réduire la
durée d’une tâche dans chaque chemin critique. En effet, il ne sert à rien de réduire la durée d’un chemin
critique si un autre chemin reste critique avec une valeur supérieure. On doit alors soit réduire la durée
d’une tâche dans chaque chemin, soit réduire la durée d’une tâche dans chaque chemin, soit réduire la durée
d’une tâche commune aux chemins dans le cas où une telle tâche existe.
4.4 Exercices
Exercice
24 La réalisation d’un projet nécessite la réalisation des 15 tâches suivantes :
Exercice 25 Un entrepôt a procédé à la définition d’un certain nombre de tâches à effectuer et à l’évaluation
de leur durée. Le tableau ci-dessous est l’aboutissement de ce travail.
1. Quelle est la condition nécessaire pour qu’un graphe quelconque puisse être ordonnancé par niveaux ?
Prouver que cette condition est vérifiée dans le cadre de l’exercice.
2. Ordonnancer les tâches par niveaux. Tracer le graphe associé.
3. On utilise dans les questions suivantes la méthode MPM.
(a) Indiquer les dates de début au plus tôt ainsi que les dates au plus tard de chaque tâche.
(b) En déduire le(s) chemin(s) critique(s) ainsi que la durée minimale du projet.
(c) Calculer les marges libres et les marges totales de toutes les tâches. Donner la signification des
marges trouvées pour les tâches E et M uniquement.
4. Retrouver les résultats précédents à l’aide de la méthode PERT.
Exercice 26 Tracer le réseau PERT relatif au projet ci-dessous et déterminer sa durée minimale :
5.1 Introduction
On parle d’ateliers spécialisés lorsque l’ensemble des équipements nécessaires pour assurer une fonction
déterminée sont rassemblés dans un même atelier. Le problème de gestion quotidienne est de déterminer
l’ordre d’exécution d’un certain nombre de tâches, la réalisation d’une tâche nécessitant le passage sur une
ou plusieurs machines.
Tâche i 1 2 3 4 5
Temps opératoire Ti 50 150 80 200 30
Il s’agit de déterminer l’ordre dans lequel on va effectuer ces différentes tâches. Il est clair que, quel que
soit l’ordre choisi, le temps opératoire total (ou somme des temps opératoires) est le même. Il faut donc
définir un autre critère entre tous les ordonnancements possibles. Un exemple d’ordonnancement est donné
ci-dessous :
Ordre (j) 1 2 3 4 5
Tâche programmée (i) 3 4 1 5 2
Temps d’exécution Tj 80 200 50 30 150
Reprenons l’ordonnancement choisi dans l’exemple 4.3.1 et construisons le diagramme de Gantt associé :
∑
j
Aj = Ti = T1 + T2 + . . . + Tj
i=1
Le calcul des différents temps d’achèvement des tâches est donné dans le tableau ci-dessous :
Ordre (j) 1 2 3 4 5
Tj 80 200 50 30 150
Aj 80 280 330 360 510
1∑
n
80 + 280 + 330 + 360 + 510
A= Aj = = 312.
5 5
j=1
5.3. ORDONNANCEMENT AVEC DEUX CENTRES DE PRODUCTION 63
A = (80
+80 + 200
+80 + 200 + 50
+80 + 200 + 50 + 30
+80 + 200 + 50 + 30 + 150)/5
= (5 × 80 + 4 × 200 + 3 × 50 + 1 × 30)/5
Il s’agit donc d’une somme pondérée des temps opératoires, chaque temps opératoire étant pondéré par un
facteur d’autant plus grand qu’il se trouve exécuté plus tôt dans l’ordonnancement.
La règle d’ordonnancement qui minimise le temps d’achèvement moyen est celle du Temps Opératoire
Minimum (règle T.O.M.) qui consiste à exécuter les tâches par ordre croissant de durée :
T1 ≤ T2 ≤ . . . ≤ Tj ≤ . . . ≤ Tn
L’application de cette règle donne l’ordonnancement illustré dans le tableau ci-dessous On peut montrer
Ordre (j) 1 2 3 4 5
Tâches (i) 5 1 3 2 4
Tj 30 50 80 150 200
Aj 30 80 160 310 510
que la règle T.O.M. revient à minimiser le retard moyen, le retard d’une tâche étant la différence entre le
moment où la tâche est terminée et celui où elle aurait été terminée si l’on avait commencé en premier lieu.
Exemple 5.3.1 Supposons que cinq tâches soient à exécuter sur les machines A puis B. Les temps opératoires
(en centièmes d’heures) sont repris ci-dessous :
Tâches (i) 1 2 3 4 5
ti,A 50 150 80 200 30
ti,B 60 50 150 70 200
Durant l’exécution de la première tâche sur A, la machine B “dort”. On a donc intérêt à mettre en tête la
tâche de temps tiA le plus faible. De façon similaire, lors de l’exécution de la dernière tâche sur la machine
B, la machine A dort. On a donc intérêt à mettre en fin la tâche de durée d’exécution tiB minimum.
En se basant sur ces deux observations, l’algorithme Johnson (1954) calcule l’ordonnancement minimisant
le temps total d’exécution des tâches.
64CHAPITRE 5. ORDONNANCEMENT EN ATELIERS SPÉCIALISÉS - DIAGRAMMES DE GANTT
L’ordonnancement obtenu est optimal et est illustré à la figure 5.2. ci-dessous. Le passage d’une tâche d’une
machine à l’autre est visualisé à l’aide d’une flèche verticale. On notera qu’une machine au repos est indiquée
par un Z. Si l’on veille à aligner verticalement l’origine du temps pour chaque machine, une ligne verticale
indique donc à tout moment à quelle tâche est occupée chacune des machines. Un tableau mural peut être
ainsi d’un grand recours pour les agents de maı̂trise responsables de l’affectation des moyens humains et
matériels.
on constate que les conditions d’application énoncées précédemment sont vérifiées. Il est à remarquer que
les deux conditions ne doivent pas être vérifiées simultanément. Dans l’exemple 5.4.1, la seconde condition
n’est pas vérifiée.
Lorsqu’on se trouve dans un des deux cas, on reformule le problème en un problème à deux machines. Dans le
cadre de l’exemple 5.4.1, la première regroupe les machines A et B (puisque l’assemblage domine l’inspection)
avec tiAB = tiA + tiB et la seconde regroupe les machines B et C (l’expédition domine l’assemblage) avec
tiBC = tiB + tiC ce qui donne les nouveaux temps opératoires
Tâches 1 2 3 4 5 6 7
Assemblage + Inspection 24 13 28 28 19 19 25
Inspection + Expédition 11 12 13 30 23 10 14
On applique alors l’algorithme de Johnson à ce problème à deux machines pour déterminer l’ordonnancement
optimal.
Place 1 2 3 4 5 6 7
Tâche 5 4 7 3 2 1 6
On peut alors tracer le diagramme de Gantt correspondant au problème original, c’est-à-dire celui avec trois
machines.
5.5 Exercices
Exercice
27 Deux opérateurs sont chargés de remplir un camion avec des cartons identiques qui sont
disposés sur 8 palettes situées en zone de stockage. Chaque palette contient 40 cartons.
Le processus de chargement est le suivant : au départ de l’activité, l’opérateur 1 est sur son chariot élévateur
en zone de stockage. L’opérateur 2 est en attente près du camion. L’opérateur 1 déstocke une palette et
l’amène à l’opérateur 2 puis il retourne chercher une autre palette pour lui-même. Quand les cartons des
deux palettes sont chargés dans le camion, il va chercher deux autres palettes. Pendant ce temps, l’opérateur
2 à l’aide d’une transpalette, ramène les deux palettes vides au parc palettes et ainsi de suite jusqu’à la
fin des opérations. On appellera cette succession de manœuvres un cycle. On précise que les deux dernières
palettes sont rangées par l’opérateur 1.
1. Tracer un diagramme de Gantt correspondant à un cycle (on considérera en abscisse le temps exprimé
en centièmes de minutes et en ordonnée les opérateurs 1 et 2).
2. Préciser le temps nécessaire pour réaliser un cycle.
3. Quel est le temps nécessaire pour réaliser la totalité du chargement (et ranger les palettes vides) ?
4. Est-il nécessaire de déterminer un ordonnancement des palettes (numérotées de 1 à 8) ? Pourquoi ?
Exercice 28 Un responsable d’entrepôt reçoit une commande de chargement pour 10 palettes bien spécifiques.
Chaque palette doit être assemblée (atelier A), emballée (atelier B) puis inspectée et chargée (atelier C)
dans le camion. Les temps en heures des différentes opérations sont donnés à la page suivante.
Comme seulement 3 personnes sont disponibles pour réaliser ce travail, les palettes sont réalisées l’une
après l’autre et sont traitées sur A, puis sur B, puis sur C.
1. Pour chaque atelier, appliquer la règle T.O.M afin de minimiser le temps d’achèvement moyen Ti tout
en précisant cette valeur.
2. On considère ensuite les 3 ateliers simultanément.
(a) En justifiant des conditions nécessaires à l’utilisation de l’algorithme de Johnson, donner l’ordre
de traitement des palettes permettant de minimiser le temps nécessaire à la réalisation de la
commande.
(b) Tracer un diagramme de Gantt correspondant au problème. Préciser le temps minimal nécessaire
à la réalisation de la commande.
5.5. EXERCICES 67
Palette i 1 2 3 4 5 6 7 8 9 10
Temps
1h10′ 0h55′ 0h45′ 0h20′ 1h15′ 1h25′ 0h55′ 0h40′ 1h05′ 1h00′
assemblage tiA
Temps
0h25′ 0h30′ 0h35′ 0h25′ 0h40′ 0h35′ 0h40′ 0h25′ 0h20′ 0h30′
emballage tiB
Temps
inspection
0h45′ 0h55′ 1h10′ 1h05′ 0h50′ 1h15′ 0h45′ 0h50′ 1h05′ 1h20′
+ chargement tiC
Exercice 29 10 palettes de natures différentes sont à traiter sur trois ateliers différents. On se donne
le tableau ci-dessous fournissant les temps opératoires (exprimés en minutes) de chacune des palettes sur
chaque atelier :
XXX
XXX Palette
XX 1 2 3 4 5 6 7 8 9 10
Atelier XXX
A 40′ 30′ 60′ 75′ 20′ 50′ 50′ 55′ 35′ 25′
B 10′ 15′ 20′ 10′ 20′ 15′ 15′ 15′ 10′ 20′
C 15′ 27′ 35′ 40′ 40′ 30′ 10′ 20′ 30′ 30′
1. (a) À l’aide de l’algorithme de Johnson, déterminer tous les ordonnancements possibles permettant
de minimiser le temps de traitement total des palettes.
(b) À l’aide d’un diagramme de Gantt et de l’ordonnancement que vous aurez choisi, préciser le temps
total nécessaire au traitement des dix palettes.
2. (a) À l’aide de l’algorithme de Johnson Géneŕalisé, déterminer tous les ordonnancements possibles
permettant de minimiser le temps de traitement total des palettes.
(b) À l’aide d’un diagramme de Gantt et de l’ordonnancement que vous aurez choisi, préciser le temps
total nécessaire au traitement des dix palettes.
Exercice
30 Un entreposeur vous demande de gérer l’assemblage, l’inspection et l’expédition de 7 pa-
lettes en un temps minimum. Vos études antérieures vous permettent d’estimer les temps (en minutes)
nécessaires à la réalisation des trois tâches pour chaque palette à savoir :
XXX
XXX Palette
XXX P1 P2 P3 P4 P5 P6 P7
Atelier XX
Assemblage 7 4 11 18 18 3 6
Inspection 4 1 9 12 5 7 8
Expédition 20 12 19 16 14 12 17
Pour réaliser ces 7 palettes, vous employez trois personnes, chacune affectée à un atelier bien précis.
1. Préciser au moins une raison permettant d’expliquer l’importance des temps opératoires lors de
l’expédition des palettes.
2. (a) L’algorithme de Johnson peut-il s’appliquer ici et si oui, quel est l’ordonnancement optimal ?
(b) À l’aide d’un diagramme de Gantt et de l’ordonnancement précédent, déterminer le temps minimal
de traitement des 7 palettes.
68CHAPITRE 5. ORDONNANCEMENT EN ATELIERS SPÉCIALISÉS - DIAGRAMMES DE GANTT
Pi ...
où
– d correspond à la durée de la tâche,
– Td est la date au plus tôt de réalisation de la tâche,
– Tf est la date au plus tard de réalisation de la tâche,
– c est la contrainte ou temps d’attente.
(c) À l’aide d’un diagramme de Gantt et de l’ordonnancement précédent, déterminer le temps minimal
de traitement des 7 palettes.
Exercice
31 Une importante société de magasins alimentaires à grande surface diversifie son activité
en créant des commerces dans les petites villes. La société crée le fonds de commerce qui est ensuite géré de
façon autonome par un commerçant franchisé. La société réalise une étude d’implantation puis elle installe
le commerce.
Les tâches à exécuter sont résumées dans le tableau suivant :
Exercice 32 La décision vient d’être prise d’acquérir une imprimante thermique à codes barres. Les tâches
à réaliser, leurs antériorités ainsi que leur durée (en semaines) sont répertoriées dans le tableau suivant :
Votre mission consiste à déterminer dans quel délai le matériel sera opérationnel.
1. Construire le réseau PERT à partir des antériorités puis déterminer la durée minimale du projet.
2. À l’aide du planning, représenter l’ordonnancement au plus tôt du projet.
3. À l’aide du planning, représenter l’ordonnancement au plus tard du projet.
4. Déterminer les marges totale et libre de chacune des tâches.
Semaine no
Tâche Durée 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
A 2
B 1
C 2
D 1
E 1
F 4
G 3
H 2
I 2
J 2
70CHAPITRE 5. ORDONNANCEMENT EN ATELIERS SPÉCIALISÉS - DIAGRAMMES DE GANTT
Semaine no
Tâche Durée 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
A 2
B 1
C 2
D 1
E 1
F 4
G 3
H 2
I 2
J 2
Chapitre 6
Exemple 6.1.1 On considère la construction d’un bâtiment dont les différentes tâches sont listées dans le
tableau de la page suivante :
On a la possibilité de réduire la durée de certaines tâches moyennant un surcoût par jour de réduction de
la durée comme indiqué dans le tableau ci-dessous :
On utilise la méthode des potentiels pour mettre en place le graphe ordonnancé en niveaux : à l’aide du
dictionnaire des précédents, on obtient les niveaux ci-dessous :
72 CHAPITRE 6. RÉDUCTION DE LA DURÉE D’UN PROJET
N0 = {1, 12}, N1 = {2, 13}, N2 = {3, 7}, N3 = {4, 6, 8}, N4 = {5, 9}, N5 = {10}, N6 = {11}
Au départ, pour passer de 35 à 34 jours, seules sont candidates les tâches critiques 6 et 9. On réduit la tâche
6 d’un jour car c’est la décision la moins coûteuse. La tâche 9 débute en 15 et la tâche 8 devient critique.
Par répercussion, la tâche 7 devient aussi critique.
Le nouveau graphe est donné par :
On peut maintenant observer deux chemins critiques P1 = (1, 2, 3, 6, 9, 10, 11) et P2 = (1, 2, 7, 8, 9, 10, 11).
Pour diminuer la réalisation du projet d’un jour supplémentaire, il faut réduire simultanément une tâche
dans chaque chemin. Le choix est à effectuer entre 9 (de coût 200) et 8 et 6 (de coût 150 + 180 = 330). On
retient la tâche 9 que l’on diminue d’un jour. Le nouveau graphe est donné par
6.1. PRÉSENTATION DE LA MÉTHODE 73
Pour diminuer le projet d’un jour supplémentaire , on sélectionne la tâche 6 qui est commune à deux chemins
ainsi que la tâche 8 pour un coût total de 180 + 150 = 330. On remarque que la tâche 9 n’est plus disponible
car on a déja utilisé le seul jour de réduction possible. On obtient le graphe ci-dessous : Il n’est plus alors
possible de diminuer la durée du projet car si on diminuait la tâche 6 d’un jour, il resterait un des trois
chemins critiques (P2 ) et la durée resterait à 32 jours.
74 CHAPITRE 6. RÉDUCTION DE LA DURÉE D’UN PROJET
6.2 Exercices
Exercice
33 Vous travaillez actuellement sur un projet de construction d’un atelier jouxtant votre en-
trepôt. Le début des travaux est prévu pour le jeudi 1er septembre. Le détail et la durée des travaux de
chaque corps de métiers vous sont donnés ci-dessous. Afin de déterminer la date d’achèvement de l’atelier
et d’éviter les retards qui seraient dus à l’imprévision, vous êtes chargés de visualiser le projet.
Exercice
34 Une entreprise décide de commercialiser un nouveau produit. La planification de ce lan-
cement fait apparaı̂tre les tâches du tableau ci-après avec leur durée (en semaines) et leurs prédecesseurs.
1. Tracer le graphe correspondant à la méthode PERT.
2. Calculer les dates de début au plus tôt, au plus tard, les marges et le chemin critique.
6.2. EXERCICES 75
3. L’entreprise voudrait réduire la durée totale d’exécution des travaux. Pour cela, il est possible de
réduire la durée des tâches 5 et 11 d’une ou deux semaines, au prix d’un coût supplémentaire de
100000 euros par semaine de réduction pour la tâche 5 et de 200000 euros par semaine pour la tâche
11. De combien peut-on réduire la durée totale des travaux et à quel coût ?
7.1 Généralités
7.1.1 Réseau de circulation
Un problème de circulation a pour objet d’optimiser l’éxécution d’un certain mouvement de matière
sur un réseau donné. Il pourra s’agir d’un fluide (eau, gaz, pétrôle,. . . ) parcourant des canalisations ou des
véhicules se déplaçant sur des voies et transportant des marchandises.
Le mouvement de matière se décompose en un nombre fini de mouvements partiels, chacun allant d’un
point de départ i vers un point d’arrivée j de façon que :
– chaque mouvement se comporte entre i et j de façon indépendante des autres mouvements partiels,
– en i ou en j, différents mouvements partiels peuvent se séparer ou se réunir. La redistribution de ces
mouvements partiels n’est possible qu’en des points privilégiés du réseau, appelés nœuds du réseau.
Ce réseau est donc constitué de l’ensemble des nœuds et de l’ensemble des liaisons pour lesquelles il existe
des mouvements de matière. On supposera que la matière qui circule dans le réseau est constituée par un
seul produit homogène. Cette matière pénètre par certains nœuds appelés nœuds d’entrée, sort du réseau
par certains nœuds appelés nœuds de sortie. Les nœuds du réseau qui ne sont ni d’entrée ni de sortie sont
des nœuds de transit.
– deux arcs (xi , xj ) et (xj , xi ) si le mouvement peut s’effectuer dans les deux sens
– Il y a conservation de la matière transportée sur tout arc (xi , xj ) du réseau, la quantité de matière
partant du nœud i et empruntant la liaison (i, j) pendant la période de référence est la même que celle
arrivant au nœud j.
Définition 7.1.2 La quantité de matière s’écoulant pendant une période de référence sur l’arc u = (xi , xj )
s’appelle flux sur l’arc u et se note φ(u). Pour tout arc u on a évidemment φ(u) ≥ 0.
Pendant une période de référence, la quantité de matière qui arrive à un nœud de transit est égale à celle
qui en sort : il y a conservation de matière aux nœuds de transit.
Soient
• X l’ensemble des sommets du graphe G associé au réseau,
• E l’ensemble des sommets représentant les nœuds d’entrée,
• S l’ensemble des sommets représentant les nœuds de sortie,
• ω − (x) l’ensemble des arcs aboutissant au sommet x,
• ω + (x) l’ensemble des arcs sortant du sommet x.
La conservation de matière aux nœuds de transit s’exprime mathématiquement par la relation
∑ ∑
∀x ∈ X − (E ∪ S), φ(ui ) = φ(ui )
ui ∈ω − (x) ui ∈ω + (x)
Sur chaque arc ui , le flux φ(ui ) peut être soumis à une contrainte de canalisation c’est-à-dire que pour
l’arc ui , il peut exister deux réels bi et ci positifs ou nuls tels que
0 ≤ bi ≤ φ(ui ) ≤ ci
En un nœud d’entrée, la différence entre le flux total partant de ce nœud et le flux total y aboutissant
représente la quantité de matière s’introduisant, pendant la période considérée, par ce nœud dans le réseau.
Soit xk le sommet associé au nœud d’entrée k, ek la quantité entrante par le nœud k
∑ ∑
φ(ui ) − φ(ui ) = ek ≥ 0
ui ∈ω + (xk ) ui ∈ω − (xk )
De façon analogue pour un nœud de sortie, en désignant par sl la quantité sortante du réseau au nœud de
sortie l représenté par le sommet xl , pendant la période de référence
∑ ∑
φ(ui ) − φ(ui ) = sl ≥ 0
ui ∈ω − (xl ) ui ∈ω + (xl )
Remarque 7.1.1 Si, pour un arc particulier ui , aucune limite supérieure n’est imposée au flux, on notera
ci = ∞.
Exemple 7.1.1 On se donne le dictionnaire des suivants et des précédents des nœuds d’un certain réseau
7.1. GÉNÉRALITÉS 79
x1 x2 , x8 x7
x2 x1 , x3 , x8
x3 x2 , x9 x4 , x8
x4 x3 , x9 x5
x5 x4 , x6 , x9
x6 x7 , x8 x5 , x9
x7 x1 , x8 x6
x8 x2 , x3 x1 , x6 , x7 , x9
x9 x6 , x8 x3 , x4 , x5
nœuds d’entrée : x2 , x7 , x8
nœuds de sortie : x5 , x9
nœuds de transit : x1 , x3 , x4 , x6
On peut maintenant tracer le réseau ainsi défini.
Remarque 7.1.2
– Pendant la période considérée, la quantité totale de matière entrant dans le réseau est égale à la
quantité sortant de celui-ci, soit
∑ ∑
ek = sl
xk ∈E xl ∈S
ek ≤ ck
sl ≤ cl
80 CHAPITRE 7. OPTIMISATION DES FLUX
Soit G = (X, U) le graphe associé à un réseau de circulation, les sommets étant désignés par x1 , x2 , . . . , xn .
On appelle graphe canonique GC associé à ce réseau le graphe obtenu à partir de G de la façon suivante :
– On introduit un sommet fictif x0 relié à tout sommet d’entrée xk de E par un arc uk = (x0 , xk ). On
associe ensuite à chaque arc uk le flux d’entrée φ(uk ) = ek avec
0 ≤ φ(uk ) ≤ ck .
Le sommet x0 joue alors le rôle d’une entrée fictive remplaçant toutes les entrées réelles.
– On introduit un sommet fictif xn+1 relié à tout sommet de sortie xl de S par un arc ul = (xl , xn+1 ).
On associe ensuite à cet arc ul le flux φ(ul ) = sl avec
0 ≤ φ(ul ) ≤ cl .
– On introduit l’arc fictif (xn+1 , x0 ) appelé arc retour et on lui associe le flux φ(u0 ) tel que
∑ ∑
φ(u0 ) = ek = sl .
xk ∈E xl ∈S
On attribue conditionnellement à u0 une borne nulle et une capacité infinie.
En reprenant le graphe de l’exemple 7.1.1 précédent, on peut construire le graphe canonique associé
On considère dans la suite GC = (XC , UC ), c’est-à-dire le graphe canonique associé au graphe G = (X, U).
mais également que sur chaque arc du graphe canonique GC , on a des contraintes de limitation des flux
ainsi que des contraintes sur les quantités entrantes et sortantes :
∀ui ∈ UC , 0 ≤ φ(ui ) ≤ ci
7.1. GÉNÉRALITÉS 81
Exercice 35 On se donne le dictionnaire des précédents et des suivants des nœuds d’un certain réseau.
x1 - x2 , x3 , x5
x2 x1 , x3 x4
x3 x1 x2 , x7
x4 x2 , x5 , x6 -
x5 - x4 , x6 , x7
x6 x5 x4
x7 x3 , x5 -
Définition 7.1.3 On appelle flot tout élément de Rn : ϕ = (φ(u1 ), φ(u2 ), . . . , φ(un )) tel que
∑ ∑
∀x ∈ X φ(ui ) − φ(ui ) = 0
ui ∈ω − (x) ui ∈ω + (x)
Les nombres φ(ui ) s’interprètent comme les flux sur les arcs ui , conservatifs en tout sommet.
Lorsque les flux φ(ui ) sur tout arc ui de U sont astreints à vérifier une condition de canalisation
0 ≤ bi ≤ φ(ui ) ≤ ci ,
on dit que le flot est canalisé.
Le flux sur l’arc retour φ(u0 ) du graphe canonique du réseau représente la quantité totale de matière
qui traverse le réseau pendant la période considérée. On l’appelle valeur du flot.
Le problème que nous nous proposons de résoudre est celui de la recherche d’un flot canalisé ϕm de valeur
φm (u0 ) maximale, dans un réseau avec capacités : c’est le problème du flot maximal.
Exercice
36 On dispose de 15 tonnes de marchandises dans un dépôt A et de 6 tonnes de la même
marchandise dans un dépôt B. Des camions doivent transporter cette marchandise en trois lieux x, y et
z. Les liaisons existant entre les dépôts et les destinations, ainsi que les quantités maximales qui peuvent
transiter sur chacune d’elles sont données en tonnes dans le tableau suivant :
x y z
A 3 15 0
B 4 5 7
82 CHAPITRE 7. OPTIMISATION DES FLUX
1. Schématiser le problème par un réseau et placer sur chaque arc sa capacité maximale.
2. On considère ensuite le flot défini de la manière suivante :
u1 = (E, A) φ(u1 ) = 6
u2 = (E, B) φ(u2 ) = 6
u3 = (A, X) φ(u3 ) = 1
u4 = (A, Y ) φ(u4 ) = 5
u5 = (B, X) φ(u5 ) = 2
u6 = (B, Y ) φ(u6 ) = 4
u7 = (B, Z) φ(u7 ) = 0
u8 = (X, S) φ(u8 ) = 3
u9 = (Y, S) φ(u9 ) = 9
u10 = (Z, S) φ(u10 ) = 0
A
B
X
Y
Z
3. On peut encore augmenter la quantité de marchandise transportée, par exemple avec huit tonnes
provenant du dépôt A et six tonnes du dépôt B.
(a) Imaginer un flot défini partiellement par φ(u1 ) = 8 et φ(u2 ) = 6.
Vérifier que le flux est conservatif.
(b) Définir le flot maximal.
dont l’origine est dans A et l’extrémité hors de A, s’appelle la coupe du réseau associé à A. On appelle
capacité de la coupe la somme des capacités des arcs contenant la coupe
∑
c(A) = ci
ui ∈ω + (A)
7.2. RECHERCHE D’UN FLOT MAXIMAL DANS UN RÉSEAU AVEC CAPACITÉS 83
C’est l’ensemble des arcs du graphe canonique dont l’origine est hors de A et l’extrémité est dans A.
7.2.2 Applications
Exercice 37 On considère le réseau suivant :
1. Pour chaque sous-ensemble donné ci-dessous, préciser la coupe ainsi que la capacité de cette dernière.
• A = {x0 , x1 , x4 }
• B = {x0 , x2 , x3 , x7 }
2. Peut-on préciser la coupe du sous-ensemble C = {x0 , x3 , x8 } ? Pourquoi ?
Exercice 38 On se donne le graphe ci-dessous :
Pour chaque sous-ensemble donné ci-dessous, préciser la coupe ainsi que la capacité de cette dernière.
• A = {x0 , x1 , x2 , x4 , x7 }
• B = {x0 , x1 , x2 , x4 }
• C = {x0 , x1 , x2 }
84 CHAPITRE 7. OPTIMISATION DES FLUX
Propriété 7.2.1 Si l’on supprime tous les arcs d’une coupe, on supprime en même temps tous les chemins
reliant x0 à xn+1 dans le graphe canonique.
Propriété 7.2.2 Si ϕ est un flot canalisé sur G, tout mouvement de matière de x0 à xn+1 emprunte au
moins un arc de la coupe ω + (A) quelle qu’elle soit.
La valeur φ(u0 ) de ce flot canalisé et la capacité c(A) de cette coupe vérifient alors
φ(u0 ) ≤ c(A)
Définition 7.2.3 L’arc ui est saturé pour un flot canalisé ϕ si et seulement si φ(ui ) = ci .
Définition 7.2.4 La quantité ci − φ(ui ) s’appelle capacité résiduelle de l’arc ui pour le flot ϕ (un arc saturé
est donc de capacité résiduelle nulle).
Définition 7.2.5 Un arc non saturé de flot non nul s’appelle encore arc fluide.
Preuve : Soit δj = cj −φ(uj ) la capacité résiduelle de l’arc uj . Par hypothèse, aucun des arcs de Γ n’est saturé.
Par conséquent, sur ce chemin Γ, tous les δj sont strictement positifs. On peut donc poser δ = min δj > 0.
uj ∈Γ
En ajoutant δ au flux de tous les arcs de Γ ainsi qu’au flux φ(u0 ) de l’arc retour, on respecte la conservativité
du flux en chaque sommet et on définit un nouveau flot ϕ′ . Ce nouveau flot est canalisé et
Soient
• cj la capacité de l’arc uj ,
Le flot ϕ a pour valeur φ(u0 ) = 2 + 4 + 2 = 8, c’est-à-dire les quantités de matière entrant dans le réseau
par les trois entrées x1 , x2 et x3 .
On considère ensuite le chemin (x0 , x2 , x4 , x6 , x7 ) (en pointillés sur la figure 7.3) ne contenant aucun arc
saturé pour ϕ, on dira que le chemin n’est pas saturé pour le flot ϕ. Sur ce chemin, les capacités résiduelles
sont respectivement 5 − 4 = 1, 2 − 1 = 1, 1 − 0 = 1 et 7 − 3 = 4. Le plus petit de ces entiers est δ = 1. En
augmentant de 1 les flux sur chaque arc de ce chemin ainsi que sur l’arc retour, on obtient un flot ϕ′ défini
sur G, ce flot ϕ′ est canalisé et sa valeur est φ′ (u0 ) = φ(u0 ) + δ = 8 + 1 = 9.
Proposition 7.2.2 Soit ϕ un flot canalisé défini sur G et C une chaı̂ne reliant x0 à xn+1 , n’empruntant
pas l’arc retour u0 . Si en parcourant la chaı̂ne C depuis x0 jusqu’à xn+1 , un arc est emprunté dans un sens,
on le note −→
uj sinon dans le cas contraire, on le note ← u−j .
On définit ensuite les quantités δ1 , δ2 , δ respectivement par :
• δ1 = −
min [ci − φ(ui )] la plus petite des capacités résiduelles des arcs de la chaı̂ne C, parcourus dans
→ui ∈C
leur sens,
• δ2 = ← min [φ(ui )] le plus petit flux circulant sur les arcs de la chaı̂ne C, parcourus à l’opposé de leur
u−i ∈C
sens,
• δ = min(δ1 , δ2 ).
Alors si δ > 0, il existe un flot canalisé ϕ′ sur G tel que φ′ (u0 ) > φ(u0 ).
Retour à l’exemple 7.2.1. On envisage la chaı̂ne C = {x0 , x3 , x4 , x2 , x6 , x7 } (en pointillés sur la figure
FIG. 2.2.5). Les arcs (x0 , x3 ), (x3 , x4 ), (x2 , x6 ), (x6 , x7 ) sont dans le sens →, l’arc (x4 , x2 ) est dans le sens
←.
• δ1 = min(5 − 2, 2 − 0, 4 − 1, 7 − 4) = min(3, 2, 3, 3) = 2,
• δ2 = min(φ(u2 )) = min(2) = 2 (où φ(u2 ) est le flux entre x2 et x4 ),
• δ = min(2, 2) = 2.
On ajoute ensuite δ à tous les arcs → ainsi qu’à l’arc retour φ′ (u0 ), on retire δ à tous les arcs ← (c’est-
à-dire au flux de l’arc (x2 , x4 )). On obtient un nouveau flot ϕ′′ encore canalisé et φ′′ (u0 ) = φ′ (u0 ) + 2 soit
φ′′ (u0 ) = 9 + 2 = 11.
Exercice 39 On considère le dictionnaire suivant faisant intervenir treize sommets d’un graphe G.
1. Déterminer le dictionnaire des précédents du graphe G
2. Ordonnancer le graphe par niveaux.
7.2. RECHERCHE D’UN FLOT MAXIMAL DANS UN RÉSEAU AVEC CAPACITÉS 87
x Suivant de x
x0 x1 , x3 , x4
x1 x2 , x8 , x11
x2 x5 , x6
x3 x8
x4 x8 , x11
x5 x7 , x9
x6 x9 , x10
x7 x12
x8 x6
x9 x12
x10 x12
x11 x6 , x10
x12 –
Il suffit de prendre l’exemple 7.2.1, issu de l’exercice 38 ; en effet si on supprimait tous les arcs saturés par
ϕ′ (c’est-à-dire les arcs (x0 , x1 ), (x0 , x2 ), (x2 , x4 ), (x3 , x6 ), (x4 , x6 ), (x5 , x7 ), (x2 , x5 )), il ne resterait aucun
chemin reliant x0 à x7 . Cependant ϕ′ n’est pas de valeur maximale puisque dans l’exemple, on a amélioré
la valeur de φ′ (u0 ) = 9 à φ′′ (u0 ) = 11.
On a la figure ci-dessous en supprimant tous les arcs saturés (représentés en traits gras)
On ne peut passer de x0 à x7 par une ligne continue, par des arcs non saturés.
Définition 7.2.7 Toute chaı̂ne C reliant x0 à xn+1 , sans passer par l’arc retour, pour laquelle on a δ =
min(δ1 , δ2 ) = 0 donc δ1 = 0 ou δ2 = 0, relativement à un flot canalisé ϕ, est dite saturée pour le flot ϕ.
On peut remarquer que la chaı̂ne {x0 , x3 , x4 , x2 , x6 , x7 } qui intervient dans l’exemple de référence (issu de
l’exercice 34) n’est pas saturée pour ϕ′ , en effet δ1 = 2, δ2 = 2 et δ = 2.
Proposition 7.2.4 Une condition nécessaire et suffisante pour qu’un flot canalisé ϕm soit un flot de valeur
maximale est que toute chaı̂ne C reliant x0 à xn+1 (sans emprunter l’arc retour) soit saturée pour le flot
ϕm .
Tout flot canalisé de valeur maximale est nécessairement complet. On commencera donc, à partir d’un flot
de départ, par déterminer un flot complet. On cherchera ensuite à améliorer la valeur du flot complet. Enfin,
une proposition indiquera à quel moment il faut mettre un terme à la recherche d’une amélioration. L’énoncé
de l’algorithme qui va suivre fournit une procédure très commode de recherche des chaı̂nes insaturées reliant
x0 à xn+1 sans emprunter l’arc retour, au moyen de “marques” de sommets.
7.3. ALGORITHME DE FORD-FULKERSON 89
puis on augmente de δ le flux de chaque arc de Γ ainsi que l’arc retour u0 . On obtient ainsi un flot
Φ1 et un graphe partiel G1 de G par suppression dans G de tous les arcs saturés par Φ1 .
− On recommence sur G1 la recherche des chemins reliant x0 à xn+1 . Si G1 ne contient pas un tel
chemin alors Φ1 est un flot complet. Sinon, on applique pour Φ1 la procédure précédente.
• En itérant un nombre fini de fois une telle procédure, on parvient à un flot canalisé Φl et un graphe
partiel Gl de G ne possédant aucun chemin reliant x0 à xn+1 . Φl est alors un flot complet sur G.
Exemple 7.3.1 À l’aide de l’algorithme précédent, déterminer le(s) flot(s) complet(s) parcourant le graphe
ci-dessous.
On obtient le graphe G1 qui est le graphe de G obtenu en supprimant dans G l’arc saturé (x0 , x1 ) (en
traits gras dans G1 ) :
On obtient le graphe G2 :
On obtient le graphe G3 :
Dans le graphe G3 , on considère alors le chemin Γ = (x0 , x2 , x4 , x6 , x7 ), on a δ = min(5−2, 2−0, 1−0, 7−0) =
1. On ajoute une unité aux flux de tous les arcs de Γ ainsi qu’à l’arc retour. On obtient φ5 (u0 ) = 5 + 1 = 6,
les arcs (x4 , x6 ) et (x2 , x4 ) sont saturés. On les supprime dans le graphe de G3 .
On obtient le graphe G5 :
On obtient le graphe G6 :
Le flot Φ6 de valeur φ6 (u0 ) = 9 est alors complet. Tout chemin reliant x0 à x7 contient au moins un arc
saturé ou encore il n’existe plus de chemin reliant x0 à x7 constitué exclusivement par des arcs non saturés.
3. Si par cette procédure, xn+1 ne peut être marqué alors le flot complet Φl est un flot canalisé de
valeur maximale.
En conclusion, x7 peut être marqué par cette procédure (voir figure 7.15) et le flot complet Φ6 de valeur 9
n’est pas maximal :
δ2 = ←
min (φl (ui ))
ui ∈C
δ = min(δ1 , δ2 )
→
– Sur chaque arc ui de C, ainsi que sur l’arc retour uo , on augmente le flux de δ.
←
– Sur chaque arc ui de C, on diminue le flux de δ.
On obtient ainsi un flot Φl+1 à partir duquel on recommence la procédure de marquage des sommets.
4. On itère alternativement les procédures des sommets et des modifications de flux jusqu’à l’obtention
d’un flot Φm à partir duquel la procédure de marquage ne permet plus de marquer xn+1 . Φm est alors
un flot canalisé de valeur maximale sur G.
Revenons à l’exemple 7.3.1.
1. Déterminons tout d’abord la chaı̂ne insaturée qui parcourt le graphe :
. x7 est de marque 6 (on relie x7 et x6 ),
. x6 est de marque 2 (on relie x6 et x2 ),
. x2 est de marque 4 (on relie x2 et x4 ),
. x4 est de marque 3 (on relie x4 et x3 ),
. x3 est de marque 0 (on relie x3 et x0 ).
La chaı̂ne peut s’écrire : C = {x0 , x3 , x4 , x2 , x6 , x7 } (en gras sur la figure 7.16).
Comme x7 ne peut pas être marqué, le flot Φ7 est un flot canalisé de valeur maximale.
c(A0 ) = 2 + 5 + 2 + 2 = 11 = φ7 (u0 ).
Remarque 7.3.2 Dans l’exemple 7.3.1 précédent, lors de la recherche du flot complet, on a successivement
saturé les chemins dans un ordre systématique de haut en bas par exemple. Dans l’application manuelle de
l’algorithme, on peut souvent gagner du temps en saturant en priorité les chemins pour lesquels δ est le plus
grand possible. Il est très probable que le flot complet soit alors maximal, un marquage testant l’optimalité.
– On considère le chemin Γ = (x0 , x2 , x6 , x7 ) pour lequel δ = 4. On ajoute 4 aux flux des arcs (x0 , x2 ),
(x2 , x6 ), (x6 , x7 ) et φ1 (u0 ) = 4. L’arc (x2 , x6 ) est saturé (cf. figure 7.18).
– On considère le chemin Γ = (x0 , x1 , x5 , x7 ) pour lequel δ = 2. On ajoute 2 aux flux des arcs (x0 , x1 ),
(x1 , x5 ), (x5 , x7 ) et φ2 (u0 ) = 6. L’arc (x0 , x1 ) est saturé (cf. figure 7.19).
– On considère le chemin Γ = (x0 , x3 , x6 , x7 ) pour lequel δ = 2. On ajoute 2 aux flux des arcs (x0 , x3 ),
(x3 , x6 ), (x6 , x7 ) et φ3 (u0 ) = 8. L’arc (x3 , x6 ) est saturé (cf. figure 7.20).
– On considère le chemin Γ = (x0 , x3 , x4 , x5 , x7 ) pour lequel δ = 2. On ajoute 2 aux flux des arcs (x0 , x3 ),
(x3 , x4 ), (x4 , x5 ), (x5 , x7 ) et φ4 (u0 ) = 10. Les arcs (x3 , x4 ) et (x4 , x5 ) sont saturés (cf. figure 7.21).
– On considère le chemin Γ = (x0 , x2 , x5 , x7 ) pour lequel δ = 1. On ajoute 1 aux flux des arcs (x0 , x2 ),
(x2 , x5 ), (x5 , x7 ) et φ5 (u0 ) = 11. Les arcs (x0 , x2 ) et (x5 , x7 ) sont saturés (cf. figure 7.22).
96 CHAPITRE 7. OPTIMISATION DES FLUX
Le flot précédent est complet : si on supprime les arcs saturés (en traits gras sur la figure 7.20), il n’existe
plus de chemin reliant x0 à x7 d’où le flot complet de valeur φ5 (u0 ) = 11. Ce flot est-il maximal ? On utilise
pour le savoir la procédure de marquage :
On part de x0 : le seul arc (x0 , xk ) de capacité résiduelle non nulle est (x0 , x3 ), on marque le sommet x3
du chiffre 0. Le seul arc (xk , x3 ) de flux non nul est (x0 , x3 ) donc x0 est marqué du chiffre 3. Les marques
s’arrêtent, x7 ne pouvant être marqué, le flot complet est aussi de valeur maximale.
Remarque 7.3.3
Dans l’exemple précédent, on a trouvé deux flots différents ayant la même valeur maximale 11. La non-
unicité du flot maximal représente le cas général, il en est de même pour les coupes de capacité minimale.
On peut remarquer que les sommets marqués dans les deux flots de valeur maximale sont identiques, ce qui
conduit à la même coupe de capacité minimale pour les deux flots. Le choix des chemins qui conduit au flot
maximal ne donne pas nécessairement la solution la plus rapide, il a pour but d’illustrer l’algorithme.
Exemple 7.3.2 On reprend le sujet de l’exercice 36. Le graphe sous sa forme ordonnancée est donnée par
la figure 7.23 :
98 CHAPITRE 7. OPTIMISATION DES FLUX
Les arcs saturés sont (E, B), (A, X) et (Y, S) (en traits gras sur la figure 7.24). Si on supprime tous les arcs
saturés, il n’existe plus de chemin reliant E à S. Le flot est complet mais ce flot est-il maximal ? On utilise
pour le savoir le marquage des sommets.
. Le seul arc (E, xk ) de capacité résiduelle non nulle est (E, A), le sommet A est marqué de la lettre E.
. Le seul arc (xk , A) de flux non nul est (E, A), le sommet E est marqué de la lettre A.
. L’arc (A, Y ) est de capacité résiduelle non nulle donc Y est marqué par A.
. L’arc (B, Y ) est de flux non nul donc B est marqué par Y .
. L’arc (B, Z) est de capacité non nulle donc Z est marqué par B.
. L’arc (Z, S) est de capacité non nulle donc S est marqué par Z.
. L’arc (X, S) est de flux non nul donc X est marqué par S.
7.3. ALGORITHME DE FORD-FULKERSON 99
B est marqué par Y , l’arc (B, X) est de capacité non nulle donc on peut aussi marquer X de la lettre B. Le
sommet X étant marqué par B et l’arc (X, S) étant de capacité non nulle, le sommet S peut être marqué
par X. Il existe donc deux marquages possibles et dans les deux cas, la sortie fictive S est marquée, le flot
complet n’est donc pas maximal.
Sommet E A B X Y Z S
Marques A E Y S A B Z
Marques A E Y B A B X
Déterminons le flot maximal. Quelles sont les chaı̂nes non saturées ? Graphiquement, on trouve deux chaı̂nes
non saturées à savoir (E, A, Y, B, Z, S) et (E, A, Y, B, X, S). En utilisant l’algorithme, on pourrait éviter
d’utiliser le graphique.
On a φ2 (u0 ) > φ′2 (u0 ), Φ′2 n’est pas le flot maximal. Φ2 est-il maximal ?
Procédure de marquage :
(E, A) est de capacité résiduelle non nulle donc on marque A de la lettre E, (E, A) est de flux non nul, on
marque E de la lettre A. L’arc (A, Y ) est de capacité non nulle, on marque donc Y de la lettre A, (B, Y )
est de flux nul, on ne peut pas marquer B. L’arc (A, X) est de capacité nulle, on ne peut pas marquer S.
Pour ce flot Φ2 , S ne peut être marqué. Conclusion, le flot est maximal et vaut 18.
Il existe des chaı̂nes constituées d’arcs non saturés pour Φ2 à savoir (E, A, Y, B, Z, S) et (E, A, Y, B, X, S).
– Pour la première, δ1 = min(3, 6, 3, 8) = 3, δ2 = 0 et δ = min(δ1 , δ2 ) = 0. On ne peut donc plus faire
évoluer les flux sur cette chaı̂ne, tous les arcs ayant une capacité résiduelle non nulle et le flux sur l’arc
(B, Y ) étant nul.
Conclusion, dans le flot Φ2 , toutes les chaı̂nes reliant E à S sont saturées et ce flot est maximal.
Déterminons la capacité maximale : pour Φ2 , les seuls sommets marqués sont E, A, Y (on note A0 =
{E, A, Y }). Alors
3. Représenter le graphe canonique associé et indiquer les capacités et les flux sur chacun des arcs.
Indiquer la valeur du flot.
4. Vérifier qu’en chacun des noeuds du réseau, la matière est conservée. On utilisera un tableau de la
forme
flux entrants flux sortants
Noeud xk ∑ ∑
φ(ui ) φ(ui )
ui ∈ω − (xk ) ui ∈ω + (xk )
.. .. ..
. . .
5. Sur le graphe canonique, mettre en évidence à l’aide d’un crayon de couleur les arcs saturés. Montrer
que le flot n’est pas complet.
102 CHAPITRE 7. OPTIMISATION DES FLUX
Exercice
41 On considère le graphe orienté ci-après.
Les sommets x1 , x2 ,. . . ,x7 représentent des entrepôts et les arcs des routes à sens unique.
Il s’agit de transporter une certaine marchandise de certains entrepôts à d’autres entrepôts.
Les capacités sont toutes égales à 24.
(x0 , x6 ) 9
(x0 , x7 ) 15
(x3 , x8 ) 6
(x4 , x8 ) 10
(x5 , x8 ) 8
Exercice 42 Le réseau de la figure ci-après représente un problème de flot. Le réseau peut-être vu comme
un réseau de transport, dans lequel on charge de la marchandise à certains points et duquel on décharge à
d’autres points.
On définit des points d’entrée ainsi que des points de sortie. Par ailleurs, l’arête i a une capacité maximale
5 qui ne peut être dépassée (assimilable à une capacité de canalisation). Chaque nœud vérifie une loi de
conservation naturelle, à savoir que la quantité entrant dans un nœud doit être égale à la quantité sortant
du nœud. Bien entendu, les nœuds d’entrée et de sortie sont exclus de cette contrainte.
2. En considérant le problème tel que posé en 1., donner la quantité maximale que l’on peut faire passer
dans le réseau. Justifier votre raisonnement. Retrouver la valeur du flot maximal à l’aide de la capacité
minimale de la coupe associée.
Exercice
43 Le trafic matinal entre une banlieue dortoir (nœud 1) et le centre ville (nœud 9) est illustré
dans la figure ci-dessous. On a représenté le trafic actuel ainsi que la capacité maximum de chacune des
routes en nombre de véhicules par heure.
104 CHAPITRE 7. OPTIMISATION DES FLUX
1. Montrer à l’aide de l’algorithme du flot maximal que l’on peut augmenter le trafic global entre le
sommet 1 et le sommet 9. Quelle est la valeur de ce trafic maximum ?
2. Suggérer les endroits où le réseau devrait être renforcé si on veut dépasser ce flot maximum.
3. Montrer que si l’on considère le trafic inverse qui concerne la fin de journée (avec les mêmes capacités
pour le retour), le flot maximum sera le même qu’à la question 1.
Exercice 44 La société SUPERSTOCK est spécialisée dans la fabrication et le stockage de coussins.
Compte tenu de la réglementation européenne, cette société décide la construction d’un nouvel entrepôt aux
normes européennes à la place de l’ancien (symbolisé dans la suite par x5 ). Vous êtes chargés de mettre à
jour les flux de marchandises sur le réseau et de les maximiser.
Les liaisons entre les différents points névralgiques (ou sommets du graphe) de la société sont donnés dans
le tableau ci-dessous ainsi que la nature des sommets :
x1 x4 x7
x2 x4 x7
x3 – x4 , x5 , x11
x4 x3 x1 , x2 , x5
x5 x3 , x4 , x11 x6 , x7 , x8
entrée : x3
△ sortie : x6
x6 x5 , x7 , x8 – ◦ transit : x1 , x2 , x4 , x5 , x7 , x8 , x9 , x10 , x11
x7 x1 , x2 , x5 x6
x8 x5 , x9 , x10 x6
x9 x11 x8
x10 x11 x8
x11 x3 x5 , x9 , x10
Les flux et les capacités des différents axes routiers sont donnés par :
7.4. EXERCICES RÉCAPITULATIFS 105
Nom de l’arc Capacité de l’arc Flux de l’arc Nom de l’arc Capacité de l’arc Flux de l’arc
(x1 , x7 ) 4 4 (x5 , x7 ) 2 1
(x2 , x7 ) 3 2 (x5 , x8 ) 2 2
(x3 , x4 ) 10 8 (x7 , x6 ) 7 7
(x3 , x5 ) 1 1 (x8 , x6 ) 7 6
(x3 , x11 ) 5 5 (x9 , x8 ) 2 2
(x4 , x1 ) 5 4 (x10 , x8 ) 5 2
(x4 , x2 ) 4 2 (x11 , x5 ) 3 1
(x4 , x5 ) 2 2 (x11 , x9 ) 2 2
(x5 , x6 ) 1 1 (x11 , x10 ) 4 2
Exercice 45 Une société de vente par correspondance gère un réseau commercial et logistique composé
de :
– trois centres de prise de commandes Ci (i = 1, 2, 3),
– deux centres de préparation de commandes Pj (j = 1, 2),
– deux centres de distribution Dk (k = 1, 2).
Cette société désire évaluer la capacité mensuelle du réseau (nombre maximum de commandes pouvant
être prises, préparées et livrées en un mois). Le réseau possède les caractéristiques suivantes (en milliers de
commandes par mois) :
– les capacités de prise de commandes de C1 , C2 et C3 sont respectivement de 30, 30 et 10,
– les capacités de préparation de commandes de P1 et P2 sont respectivement de 10 et 60,
– les capacités de distribution de D1 et D2 sont respectivement de 30 et 50,
– chaque centre de prise de commandes peut alimenter les deux centres de préparation mais les capacités
des liaisons informatiques limitent à un maximum de 20000 commandes par mois le flux entre un centre
Ci et un centre Pj ,
– P1 alimente D1 , P2 alimente uniquement D2 ,
– D2 a la possibilité de transférer une partie de son activité sur D1 ; ce transfert ne peut dépasser 20000
commandes par mois, il ne réduit pas la capacité de distribution de D2 ,
– parmi les clients de la société, les collectivités ne s’adressent qu’à C3 ; il y a un minimum de 5000
commmandes mensuelles de ce type.
1. Construire en le justifiant le réseau de transport modélisant le contexte.
2. Définir le nombre maximum de commandes que la société peut traiter mensuellement (on pourra partir
d’un flot initial nul). Traduire le flot obtenu en termes d’activité pour chaque centre.
3. Identifier une coupe de capacité minimale.
106 CHAPITRE 7. OPTIMISATION DES FLUX
Exercice 46 Avant d’établir un projet de construction d’autoroute on désire étudier la capacité du réseau
autoroutier, représenté par le graphe suivant :
Pour cela, on a évalué le nombre maximal de véhicules que chaque route peut écouler par heure, compte
tenu des ralentissements aux traversées des villes et villages, des arrêts aux feux, etc. . . Ces évaluations sont
indiquées en centaines de véhicules par heure sur les arcs du graphe (nombres entre crochets). Les temps
de parcours entre villes sont tels que les automobilistes n’emprunteront que les chemins représentés par le
graphe.
Quel est le débit horaire total maximum de véhicules susceptibles de s’écouler entre les villes E et S ?
(En utilisant l’algorithme de Ford-Fulkerson, augmenter le flot entre les sommets E et S jusqu’à ce qu’il
devienne maximal).
Exercice 47 Soit le problème de transport suivant : une firme dispose de trois entrepôts A, B et C
dans lesquels sont stockés respectivement 31, 14 et 26 tonnes de marchandises. La firme doit livrer 5 clients
u, v, x, y et z ayant respectivement un besoin de 15, 20, 9, 10 et 17 tonnes de marchandises.
Les coûts de transport (par tonne de marchandises) des entrepôts vers les clients sont les suivants :
```
```
``` Clients u v x y z
Entrepôt ```
``
A 6 – – 12 –
B – 5 9 – –
C – 4 – 8 10
On voit que chaque client n’est pas accessible à partir de chaque entrepôt.
Utiliser les flots afin de voir s’il existe une solution réalisable à ce problème. Si le problème est réalisable, en
donner une solution. Sinon, quelle est la quantité maximale de marchandises qui peut être délivrée ?
Exercice 48 Une société d’import-export dispose, dans les ports de Veracruz, Sâo Paulo, Conakry et
Abidjan, de stocks de café de respectivement 120 tonnes, 100 tonnes, 100 tonnes et 100 tonnes, pour lesquels
elle a reçu des commandes d’importateurs de Dunkerque (100 tonnes), Bordeaux (80 tonnes), Saint-Nazaire
(90 tonnes) et Le Havre (150 tonnes). Divers bateaux se rendent des ports étrangers considérés vers les ports
français de destination. Les tonnages sont donnés par le tableau suivant :
7.4. EXERCICES RÉCAPITULATIFS 107
```
``` Destination
``` Dunkerque Bordeaux Saint-Nazaire Le Havre
Origine ```
``
Veracruz 70 30 20 –
Sâo Paulo 50 40 10 –
Conakry – 20 40 80
Abidjan – 20 40 80
Déterminer les diverses cargaisons de façon à satisfaire au mieux les demandes, les commandes destinées à
Bordeaux et au Havre étant prioritaires. On donnera également la coupe minimale.
108 CHAPITRE 7. OPTIMISATION DES FLUX
Chapitre 8
La programmation linéaire
8.1 Introduction
La programmation mathématique recouvre un ensemble de techniques d’optimisation sous contraintes
qui permettent de déterminer dans quelles conditions on peut rendre maximum ou minimum une fonction
objectif Z(Xj ) de n variables Xj liées par m relations ou contraintes Hi (Xj ) ≤ 0.
De nombreux problèmes de l’entreprise peuvent s’exprimer en termes d’optimisation contrainte, aussi ren-
contre t-on de multiples applications de la programmation mathématique et ceci dans pratiquement tous les
domaines de la gestion.
La gestion de production est le domaine où ces applications sont les plus nombreuses. On citera entre-autres :
– l’élaboration de plans de production et de stockage,
– le choix de techniques de production,
– l’affectation de moyens de production,
– la détermination de la composition de produits.
Les applications sont également nombreuses dans le domaine du marketing avec, en particulier :
– le choix de plans-média,
– la détermination de politiques de prix,
– la répartition des efforts de la force de vente,
– la sélection des caractéristiques du produit.
On citera encore des applications en matière financière (choix de programmes d’investissements), en matière
logistique (gestion des transports) et en matière de gestion des ressources humaines (affectation de person-
nel).
Si les applications de la programmation mathématique sont aussi nombreuses, on doit l’attribuer en grande
partie à la souplesse de ses techniques en ce qui concerne leur formulation mais aussi à la relative simplicité
des méthodes de résolution utilisables dans les cas les plus courants et pour lesquelles existent des pro-
grammes informatiques largement répandus.
Parmi les techniques de programmation mathématique la programmation linéaire est la plus classique.
Les deux chapitres qui suivent traitent exclusivement de ce type de programmation.
3. La formulation des contraintes. Il est bien rare qu’un responsable dispose de toute liberté d’action. Le
plus souvent il existe des limites à ne pas dépasser qui revêtent la forme d’équations ou d’inéquations
mathématiques.
Le responsable d’une décision ne dispose que de sa compétence pour réaliser une formalisation correcte
du problème posé car il n’existe pas de méthode en la matière. Un moyen d’acquérir cette compétence est
l’apprentissage comme proposé dans les exemples suivants :
8.2.1 Exemples
Exemple 8.2.1 Une usine fabrique deux produits P1 et P2 à l’aide de trois matières premières M1 , M2
et M3 dont on dispose en quantité limitée. On se pose le problème de l’utilisation optimale de ce stock de
matières premières c’est-à-dire la détermination d’un schéma, d’un programme de fabrication tel que :
– les contraintes de ressources en matières premières soient respectées,
– le bénéfice réalisé par la vente de la production soit maximum.
Modèle mathématique :
– Données numériques des contraintes. La disponibilité en matières premières est de 18 unités de M1 , 8
unités de M2 et 14 unités de M3 .
– Caractéristiques de fabrication. Elles sont données dans le tableau ci-dessous :
M1 M2 M3
P1 1 1 2
P2 3 1 1
– Hypothèses de linéarité du modèle. La fabrication est à rendement constant, c’est-à-dire que pour
fabriquer x1 unités de P1 , il faut 1 × x1 unités de M1 , 1 × x1 unités de M2 et 2 × x1 unités de M3 , de
même pour la fabrication de x2 unités de P2 .
– Linéarité de la fonction économique. On suppose que le bénéfice peut s’exprimer à l’aide des bénéfices
unitaires c1 , c2 sous la forme :
Z = c1 x1 + c2 x2
Exemple 8.2.2 L’intendant d’un lycée doit composer un menu qui doit contenir un minimum d’éléments
nutritifs et qui doit être le moins coûteux possible. On se limite à une situation simple, deux denrées ali-
mentaires principales D1 , D2 et trois éléments nutritifs, les vitamines V, les calories C et les protéines P.
V C P
D1 1 1 3
D2 5 2 2
Modèle mathématique :
Exercice 49 Formaliser les situations suivantes :
1. La société Bonvin, S.A., qui pratique le négoce en vins propose à sa clientèle deux vins de table : l’un
est dénommé “Extra”, l’autre “Supérieur”. Ces produits sont obtenus par coupage de crus issus de
diverses régions : un vin de l’Hérault, un vin du Bordelais et un vin d’Italie.
Les coupages sont réalisés selon les proportions fixes suivantes :
Vin “Extra” Vin “Supérieur”
Vin de l’Hérault 0,5 0,2
Vin du Bordelais 0,3 0,6
Vin d’Italie 0,2 0,2
Total 1 1
Après les vendanges, la société dispose en stock dans ses cuves des quantités suivantes de crus d’origine :
Vin de l’Hérault .. 13600 hectolitres
Vin du Bordelais .. 12000 hectolitres
Vin d’Italie ... 10400 hectolitres
Ces quantités constituent les ressources disponibles pour la production de l’année à venir. En outre,
compte tenu des capacités techniques de mise en bouteille existantes, cette production ne peut pas
dépasser 36000 hectolitres au total dans l’année.
L’activité de cette entreprise comporte des coûts qui ont été classés en deux catégories :
– Une partie est considérée comme fixe ; elle correspond aux approvisionnements, puisque ceux-ci sont
déja constitués, ainsi qu’aux frais de personnel. Ces coûts s’élèvent à 12000000 euros pour l’année.
– L’autre partie correspond aux frais de mise en bouteille, d’emballage et de commercialisation. Cette
seconde partie est proportionnelle aux quantités produites : soit 100 euros par hectolitre de vin
quelle que soit la qualité de celui-ci.
112 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
Chaque atelier fonctionne au maximum 4000 heures dans l’année. Les prévisions de coût variable de
production de chaque type de récipient donnent comme résultats :
Coûts variables de production
Atelier A Atelier B
0,75 litre ... 0,4 0,55
3 litres ..... 0,75 0,85
Mais Bonvin peut également sous-traiter la fabrication de ces récipients à la société Corec qui propose
comme tarif :
0,5 euro la bouteille de 0,75 litre
1 euro la bouteille de 3 litres
Les dirigeants de Bonvin S.A. se posent trois questions
– faut-il produire des bouteilles et en quelles quantités ?
8.2. MODÉLISATION D’UN PROGRAMME LINÉAIRE 113
Si les variables sont continues, si les coefficients économiques et techniques sont indépendants des valeurs
des variables, alors le problème peut être formalisé à l’aide d’un programme linéaire.
Un même programme peut être traduit sous une forme canonique ou sous une forme standard ; l’une et
l’autre pouvant adopter soit la notation algébrique classique soit la notation matricielle que l’on ne traitera
pas ici.
Voyons tout d’abord la forme canonique. Elle se caractérise par des contraintes présentées sous la forme
d’inéquations telles que
x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0
a11 x1 + a12 x2 + . . . + a1n xn ≤ ou ≥ ou = b1
..
.
i1 x1 + ai2 x2 + . . . + ain xn ≤ ou ≥ ou = bi
a
..
.
am1 x1 + am2 x2 + . . . + amn xn ≤ ou ≥ ou = bm
114 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
Z = c1 x1 + c2 x2 + . . . + cn xn
Résoudre le programme linéaire consiste à déterminer les n-uplets (x1 , x2 , . . . , xn ) qui optimisent Z (maxi-
misent ou minimisent) Z ou à montrer que de tels n-uplets n’existent pas.
Définition 8.2.1
– On appelle solution réalisable tout n-uplet (x1 , x2 , . . . , xn ) vérifiant le système d’inéquations précédent.
– On appelle solution optimale toute solution réalisable qui optimise Z.
– On appelle fonction objectif la forme linéaire
Z = c1 x1 + c2 x2 + . . . + cn xn
– L’ensemble des solutions réalisables du programme linéaire P est appelé domaine des solutions
réalisables. Lorsque ce domaine est non vide, on dit que P est réalisable.
Résoudre un programme linéaire consiste à déterminer les valeurs des variables qui permettent d’optimiser
la fonction économique.
Il existe diverses techniques de résolution parmi lesquelles la méthode graphique se montre à l’évidence
la plus rapide et la plus simple mais aussi la plus limitée, car dès lors que le nombre de variables ou de
contraintes dépasse 2, elle devient impraticable. C’est pourquoi divers chercheurs se sont efforcés de mettre
au point une méthode de calcul algorithmique qui permet de détecter la solution optimale (si elle existe)
quel que soit le nombre des variables et des contraintes.
Bien que très efficace, cette méthode connue sous le nom d’algorithme du simplexe, exige des calculs longs
et fastidieux. C’est pourquoi ceux-ci sont de plus en plus confiés à l’outil informatique. Dès lors une question
se pose : puisque les logiciels correspondants sont largement répandus, est-il nécessaire pour appliquer la
méthode, d’en connaı̂tre les ressorts ? Deux raisons essentielles justifient une réponse affirmative :
– d’abord, la compréhension des principes de résolution est une aide précieuse pour, en amont, analyser
et formaliser le problème et pour, en aval, interpréter et exploiter la solution obtenue ;
– ensuite parce que la démarche algorithmique présente en elle-même un intérêt formateur non négligeable.
Exemple 8.3.1
– Signe de x + y − 1 :
– Signe de −x + y :
On trace la droite D d’équation −x + y = 0, cette droite contient l’origine du repère. Pour le point
A(1, 0), x − y = 1 > 0 donc pour tous les points M (x, y) situés dans le demi-plan (I), x − y > 0 et
pour tous les points N (x, y) situés dans le demi-plan (II), x − y < 0. Pour les points P (x, y) de la
droie D, x − y prend la valeur 0.
Exemple 8.3.2
• Le disque est un ensemble convexe :
• Le cercle n’est pas un ensemble convexe : les points du segment ]M1 , M2 [ n’appartiennent pas au cercle.
On trace la droite D2 d’équation −x1 − x2 = −1. Considérons l’origine, −x1 − x2 = 0 − 0 = 0 > −1 donc
l’origine n’est pas solution, les solutions
( du
) système sont par conséquent les points du triangle ABC et son
2 1
intérieur avec A(1, 0), B(2, 0) et C , .
3 3
On considère la droite d’équation D1 : x1 + x2 = 1. Le demi-plan qui convient est repéré grâce, par exemple,
à l’origine.
On considère la droite d’équation D2 : −3x1 + x2 = −3. Le demi-plan qui convient est repéré une fois de
plus grâce à l’origine. L’ensemble solution se restreint à un seul point, le couple solution (1, 0).
On considère la droite d’équation D1 : x1 +5x2 = 5. Le demi-plan qui convient est repéré grâce, par exemple,
à l’origine.
8.3. MÉTHODE GRAPHIQUE : PROBLÈME À DEUX INCONNUES 119
On considère la droite d’équation D2 : x1 +2x2 = 4. Le demi-plan qui convient est repéré grâce, par exemple,
à l’origine.
On considère la droite d’équation D3 : 3x1 + 2x2 = 6. Le demi-plan qui convient est repéré grâce, par
exemple, à l’origine.
L’ensemble solution est un polyèdre convexe limité par la ligne polygonale OABCD.
120 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
On rappelle que le domaine des solutions réalisables est donné graphiquement par :
Le programme linéaire admet une unique solution réalisable (1, 0) qui est d’ailleurs la solution optimale. Z
est maximum pour le couple (1, 0) et vaut Z = 3 × 1 + 0 = 3.
Exemple 8.3.8 On reprend le système de l’exemple 8.3.3 auquel on ajoute une fonction objectif :
x1 ≥ 0, x2 ≥ 0
x1 + 4x2 ≤ 2
−x1 − x2 ≤ −1
6x1 + x2 ≤ 2
Z = 6x1 + x2 à maximiser
Ce programme n’a pas de solution réalisable. Le domaine des solutions réalisables est le vide.
Exemple 8.3.9 On reprend le système de l’exemple 8.3.6 auquel on ajoute une fonction objectif :
x1 ≥ 0, x2 ≥ 0
x1 + 3x2 ≤ 18
x1 + x2 ≤ 8
2x1 + x2 ≤ 14
Z = 2x1 + 4x2 à maximiser
Le domaine des solutions réalisables est un domaine plan, délimité par le polygone OABCD. Le domaine
plan est un ensemble convexe.
On détermine ensuite les couples (x1 , x2 ) de solutions réalisables tels que Z = 2x1 + 4x2 soit maximum.
Pour tout nombre Z, on note DZ la droite d’équation
Z = 2x1 + 4x2 .
( ) ( )
−4 −2 1
Un vecteur directeur de cette droite DZ est ⃗v ou w⃗ . Son coefficient directeur est − . En
2 1 2
1 Z
effet, x2 = − x1 + . Lorsque Z varie, ces droites DZ ayant même coefficient directeur sont parallèles entre
2 4
Z Z
elles. L’ordonnée à l’origine des droites DZ est . Maximiser Z est équivalent à maximiser . Le problème
4 4
consiste donc à déterminer une ou plusieurs droites DZ qui rencontrent le domaine des solutions réalisables
et ayant une ordonnée à l’origine maximale. Lorsque Z augmente, la droite DZ se déplace parallèlement à
elle même vers le haut :
La droite DZ qui rencontre le domaine des solutions réalisables et qui a une ordonnée à l’origine maximale
est celle qui contient le point C.
Le programme linéaire a une seule solution maximale, le couple (3, 5).
En conclusion, pour x1 = 3, x2 = 5, la fonction objectif est maximale et vaut
Z = 2 × 3 + 4 × 5 = 26.
Remarque 8.3.1 La fonction objectif atteint son maximum en un des sommets du polygone.
122 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
Le domaine des solutions réalisables est convexe. Minimisons la fonction objectif : pour Z donné, on trace
) DZ d’équation −x1 + x2 = Z ⇔ x2 = x1 + Z. Lorsque Z varie, ces droites DZ de vecteur directeur
la droite
(
1
(de coefficient directeur 1) sont parallèles entre elles. On recherche une ou plusieurs droites DZ ayant
1
une ordonnée à l’origine Z minimale. Pour toute valeur de Z (∈ R), DZ rencontre le domaine des solutions
réalisables. Le programme linéaire n’a pas de solution minimale.
Exemple 8.3.11 On reprend le système de l’exemple 8.3.5 auquel on ajoute une fonction objectif :
x1 ≥ 0, x2 ≥ 0
x1 + 5x2 ≥ 5
x1 + 2x2 ≥ 4
3x1 + 2x2 ≥ 6
Z = 20x1 + 25x2 à minimiser
Le domaine des solutions réalisables est donné graphiquement par :
4 Z
Pour Z donné, on trace la droite DZ d’équation Z = 20x1 + 25x2 ou encore x2 = − x1 + . Cette droite
( ) ( 5) 25
4 −25 −5
DZ a pour coefficient directeur − , pour vecteur directeur ⃗v ou w⃗ et pour ordonnée à
5 20 4
8.3. MÉTHODE GRAPHIQUE : PROBLÈME À DEUX INCONNUES 123
Z 4
l’origine . On trace des droites DZ de coefficient directeur − et on recherche une ou plusieurs droites
25 5
Z
DZ , rencontrant le domaine des solutions réalisables et ayant une ordonnée à l’origine minimale. La
25
droite DZ rencontrant le domaine
( ) des solutions réalisables et ayant une ordonnée à l’origine( minimale
) est
3 3
celle qui contient le point C 1, . La fonction objectif atteint son minimum pour le couple 1, et vaut
2 2
3 115
Z = 20 × 1 + 25 × = .
2 2
Exemple 8.3.12 On considère le système mis en place dans le cadre de l’exemple 8.3.6 :
x1 ≥ 0, x2 ≥ 0
x1 + 3x2 ≤ 18
x1 + x2 ≤ 8
2x 1 + x2 ≤ 14
Z = c1 x1 + c2 x2
où Z est une fonction économique ou fonction objectif qu’il faut maximiser et c1 et c2 sont les bénéfices
unitaires.
Le domaine des solutions réalisables est le domaine convexe délimité par le polygone OABCD. Les co-
ordonnées des sommets sont obtenues en déterminant les intersections des droites donc en résolvant des
systèmes de deux équations à deux inconnues.
( )
−1
de vecteur directeur v⃗5 . La droite qui a une ordonnée à l’origine maximale est celle qui contient
5
( )
7
le point A . La fonction objectif atteint son maximum au point (7, 0) et vaut Z = 5 × 7 + 0 = 35.
0
Remarque 8.3.2 En fonction des différentes valeurs attribuées à c1 et c2 , la fonction objectif atteint son
maximum en différents sommets du polygone. Le programme linéaire a soit une unique solution soit une
infinité de solutions (lorsque la droite DZ est parallèle à l’un des côtés du polygone).
c1 c1
• − < −2 ⇔ > 2 ⇔ c1 > 2c2
c2 c2
Dans ce cas, la droite des bénéfices est plus ”pointue” que le côté (AB). Le maximum est atteint
au point A(7, 0) et en ce point seulement. Le programme linéaire admet une seule solution maximale
(7, 0) qui est un sommet, avec x2 = 0 on ne produit que P1 .
c1
• − = −2 ⇔ c1 = 2c2
c2
−2 est la pente du côté (AB). Les droites DZ : c1 x1 + c2 x2 = Z sont parallèles au côté (AB). Il y a
une infinité de solutions optimales représentées
{ par tous les points du segment [AB] défini par :
2x1 + x2 = 14
[AB] :
6 ≤ x1 ≤ 7
8.3. MÉTHODE GRAPHIQUE : PROBLÈME À DEUX INCONNUES 125
{
6 ≤ x1 ≤ 7
Tous les couples (x1 , x2 ) tels que sont solutions optimales, le bénéfice vaut alors
2x1 + x2 = 14
14c2 . En effet, Z = c1 x1 + c2 x2 = 2c2 x1 + c2 x2 = c2 (2x1 + x2 ).
c1 c1
• −2 < − < −1 ⇔ 1 < <2
c2 c2
−1 est la pente du côté (BC), −2 celle de (AB). Le maximum est atteint en un seul point B qui est
aussi un sommet.
c1 c1
• − = −1 ⇔ = 1 ⇔ c1 = c2
c2 c2
Les droites DZ sont parallèles au côté (BC). Il y a une infinité de solutions optimales représentées par
tous les points du segment [BC] défini par : {
x1 + x2 = 8
[BC] :
3 ≤ x1 ≤ 6
{
3 ≤ x1 ≤ 6
Tous les couples (x1 , x2 ) tels que sont solutions optimales, le bénéfice vaut alors 8c1 .
x1 + x2 = 8
c1 1
• −1 < − < −
c2 3
1
− est la pente du côté (CD), −1 celle du côté (BC). Le programme linéaire a un seule solution
3
optimale soit le point C(3, 5) qui est un sommet.
c1 1
• − = − ⇔ c2 = 3c1
c2 3
Les solutions optimales sont tous les points du{segment [CD] d’où une infinité de solutions.
x1 + 3x2 = 18
[CD] :
0 ≤ x1 ≤ 3
La fonction objectif atteint son maximum{pour tous les couples (x1 , x2 ) tels que
x1 + 3x2 = 18
0 ≤ x1 ≤ 3
et le bénéfice vaut Z = 18c1 .
1 c1 c1 1
• − <− <0⇔0< <
3 c2 c2 3
Il existe une seule solution optimale c’est-à-dire le point D(0, 6) qui est un sommet ; x1 étant nul, on
ne produit que P2 .
Le domaine des solutions réalisables est représenté par l’intérieur de la pyramide OM1 M2 M3 . La fonction
objectif est x1 + x2 = Z. Lorsque Z varie, x1 + x2 = Z est l’équation d’un plan parallèle à (0, ⃗k), ce plan
rencontre le plan (O,⃗i, ⃗j) suivant la droite d’équation Z = 0 et x1 + x2 = Z. Le plan PZ qui rencontre
le
0
domaine des solutions réalisables et tel que Z soit maximum est celui qui contient le point M 4 . La
0
fonction objectif atteint son maximum en un seul point qui est d’ailleurs un des sommets, c’est-à-dire M2 .
8.3.6 Exercices
Exercice
50 Une entreprise stocke successivement deux types de polystyrènes A1 et A2 dans trois en-
trepôts distincts E1 , E2 et E3 afin qu’ils y subissent des traitements particuliers. Le coût de fonctionnement
de l’entrepôt E1 est de 200 euros par jour, celui de l’entrepôt E2 est de 400 euros et celui de l’entrepôt E3
est de 300 euros. Les temps de stockage pour une tonne de polystyrène A1 sont de 3 jours dans l’entrepôt
E1 , de 1 jour dans l’entrepôt E2 et d’une demi-journée dans l’entrepôt E3 . Ils sont pour le polystyrène A2
de 2 jours dans chacun des 3 entrepôts.
Les coûts de fabrication des polystyrènes A1 et A2 sont respectivement de 600 euros et 400 euros la tonne.
Les prix de vente d’une tonne des polystyrènes fabriqués sont de 1950 euros pour A1 et de 2440 euros pour
A2 .
1. (a) Calculer le coût de stockage d’une tonne de polystyrène A1 et d’une tonne de polystyrène A2 .
(b) Déterminer le bénéfice réalisé par la fabrication, le stockage et la vente d’une tonne de chacun
des produits.
(c) En déduire que le bénéfice total Z pour la production, le stockage et la vente de x tonnes de
polystyrène A1 et de y tonnes de polysytyrène A2 est donné par Z = 200x + 240y.
2. La logistique des stockages est telle que l’entrepôt E1 peut fonctionner au maximum 360 jours dans
l’année, l’entrepôt E2 peut fonctionner au maximum 160 jours par an, l’entrepôt E3 ne peut fonctionner
annuellement plus de 120 jours.
La demande est telle que la production de polystyrène A1 ne peut dépasser 120 tonnes, celle de A2 50
tonnes.
(a) Déterminer les nombres x et y de tonnes des deux produits fabriqués pour que l’entrepôt E1
fonctionne exactement 360 jours et l’entrepôt E3 exactement 120 jours. Cette production est-elle
possible ?
(b) On veut maintenant déterminer les nombres x et y de tonnes des deux produits fabriqués, stockés
et vendus qui donneraient à l’entreprise le bénéfice maximum.
i. Donner les 7 contraintes de production ainsi que la fonction à maximiser sous la forme d’un
programme linéaire du type
8.3. MÉTHODE GRAPHIQUE : PROBLÈME À DEUX INCONNUES 127
x ≤ · · · et/ou ≥ · · ·
y ≤ · · · et/ou ≥ · · ·
..
.
Z = · · · à maximiser
ii. Représenter sur le graphique ci-joint le domaine des solutions réalisables en justifiant.
iii. À l’aide d’une résolution graphique, déterminer en justifiant la production qui assurera le
bénéfice maximal. Quel sera alors son prix ?
Exercice
51 Une entreprise possède deux unités de production U1 et U2 . Elle commercialise ses pro-
duits à l’aide de trois entrepôts distincts E1 , E2 et E3 situés dans différentes zones de consommation. Le
tableau ci-dessous indique pour chaque entrepôt, les proportions de stockage d’unités x et y provenant
respectivement de U1 et U2 .
HH Ei
H E1 E2 E3
Ui HHH
U1 1 2 1
U2 2 3 1
Ces valeurs signifient par exemple que les structures de l’entrepôt E1 permettent de stocker 2 fois plus
d’unités provenant de U2 que d’unités provenant de U1 .
L’organisation actuelle des entrepôts est telle que E1 ne peut stocker au total plus de 120 unités, E2 ne peut
stocker au total plus 200 unités et E3 ne peut stocker au total plus 90 unités.
Les productions journalières de U1 et de U2 sont limitées respectivement à 80 et 50 unités.
128 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
On sait que le bénéfice réalisé par l’entreprise est de 50 euros pour la vente d’une unité de U1 et 80 euros
pour la vente d’une unité de U2 .
On veut déterminer maintenant les nombres x et y d’unités provenant de U1 et U2 , qui permettraient à
l’entreprise de réaliser un bénéfice journalier maximum.
1. Donner les 7 contraintes portant sur x et y ainsi que la fonction à maximiser sous la forme d’un
programme linéaire
2. Résolution graphique
(a) Représenter sur le graphique de la page suivante, le domaine des solutions réalisables en justifiant
vos démarches.
(b) À l’aide d’une résolution graphique, déterminer en justifiant, la production qui assurera le bénéfice
maximal. À quoi sera alors égal ce bénéfice ?
Exercice
52 Le gérant d’un entrepôt souhaite renouveler le matériel de sécurité de son établissement.
Il a besoin au minimum de
– 90 paires de chaussures de sécurité,
– 240 casques de sécurité,
– 240 paires de gants.
Une première entreprise de vente lui propose un lot A comprenant 2 paires de chaussures, 4 casques et
8 paires de gants pour 200 euros. Une deuxième entreprise vend pour 400 euros un lot B de 3 paires de
chaussures, 12 casques et 6 paires de gants.
Pour répondre à ses besoins, le gérant achète x lots A et y lots B.
1. Traduire par un système d’inéquations les contraintes auxquelles satisfont x et y.
On considère un plan P rapporté à un repère orthonormé (O,⃗i, ⃗j). A tout couple (x, y) on associe le point
M de P de coordonnées (x, y), en prenant comme unité 1 cm pour 10 lots.
2. Représenter dans P l’ensemble des points M (x, y) satisfaisant aux inéquations :
8.3. MÉTHODE GRAPHIQUE : PROBLÈME À DEUX INCONNUES 129
x ≥ 0 et y ≥ 0
2x + 3y ≥ 90
x + 3y ≥ 60
4x + 3y ≥ 120
On hachurera la partie du plan formée des points pour lesquels les contraintes ne sont pas respectées.
3. Exprimer en fonction de x et de y la dépense en euros occasionnée par l’achat de x lots A et de y lots
B.
4. Est-il possible de procéder aux achats nécessaires avec 5000 euros ? Justifier la réponse.
5. Déterminer graphiquement, en précisant la démarche suivie, le nombres de lots A et de lots B à acheter
pour avoir une dépense minimale.
6. Quelle est cette dépense minimale ?
Exercice 53 Un artisan fabrique des objets A et des objets B. On dispose des informations suivantes :
– La réalisation d’un objet A demande 30 euros de matière première et 125 euros de main-d’œuvre.
– La réalisation des objets B demande 70 euros de matière première et 75 euros de mains-d’œuvre.
– Les profits réalisés sont de 54 euros par objets A, et de 45 euros par objet B.
On note x le nombre d’objets A fabriqués et y le nombre d’objets B fabriqués, en une journée. La dépense
journalière en matière première ne doit pas dépasser 560 euros. La dépense journalière en main-d’œuvre ne
doit pas dépasser 1250 euros.
1. Traduire mathématiquement ces deux hypothèses.
2. Le plan est rapporté à un repère orthonormé (unité graphique = 1 cm). Représenter graphiquement
l’ensemble des points M (x, y) dont les coordonnées vérifient ces hypothèses. Exprimer le bénéfice
journalier Z de l’entreprise en fonction de x et de y, puis la production journalière d’objets A et B
qui assurerait un bénéfice maximum. On précisera, graphiquement, et par le calcul, cette production
journalière.
130 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
Exercice 54 Résoudre le problème de la société Bonvin S.A. dans sa forme initiale à l’aide de la méthode
graphique (exercice 45)
Théorème 8.4.1
– Si un programme linéaire admet une solution possible finie, alors il admet au moins une solution de
base.
– Si ce programme linéaire admet une solution optimale, il admet au moins une solution de base optimale
(ce qui signifie qu’une solution de base au moins est optimale).
3. changer de solution de base puis reprendre la procédure au 1. jusqu’à l’obtention de la solution optimale.
Chaque changement de solution de base constitue une itération.
Afin de réaliser les opérations successives de l’algorithme du simplexe, il convient de mettre le programme
sous une forme standard.
On introduit des variables auxiliaires positives ou nulles appelées variables d’écart de la façon suivante :
{
5x1 − x2 + e1 = 3
5x1 − x2 ≤ 3 ⇔
e1 ≥ 0
{
x1 + 4x2 + e2 = 4
x1 + 4x2 ≤ 4 ⇔
e2 ≥ 0
Cas général.
Soit un programme linéaire à n variables. On remplace chacune des égalités
a1 x1 + a2 x2 + . . . + an xn ≤ b1
par l’égalité
a1 x1 + a2 x2 + . . . + an xn + e1 = b1 avec e1 ≥ 0
132 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
et chaque inégalité
a1 x1 + a2 x2 + . . . + an xn ≥ b1
par l’égalité
a1 x1 + a2 x2 + . . . + an xn − e1 = b1 avec e1 ≥ 0
2. Mise en équation
Soit x1 le nombre de bureaux de type luxe, x2 le nombre de bureaux de type standard. Le programme
linéaire est
x1 ≥ 0, x2 ≥ 0
x1 ≤ 300
x2 ≤ 400
x1 + x2 ≤ 500
2x1 + x2 ≤ 700
Z = 7x1 + 5x2 à maximiser
3. Domaine des solutions réalisables
4. Forme standard
On introduit les variables d’écart xi avec i ∈ {3, 4, 5, 6} positives ou nulles.
x1 + x3 = 300
x2 + x4 = 400
x1 + x2 + x5 = 500
2x1 + x2 + x6 = 700
Z = 7x1 + 5x2 à maximiser
8.4. LA MÉTHODE DU SIMPLEXE 133
VDB VHB
x3 x1
Notation : x4 x2
x5
x6
Tableau initial :
PP
PP VHB
PP x3 x4 x5 x6
VDB PP
P x1 x2 cste
• • • •
x3 1 0 1 0 0 0 300 x1 + x3 = 300
x4 0 1 0 1 0 0 400 x2 + x4 = 400
x5 1 1 0 0 1 0 500 x1 + x2 + x5 = 500
x6 2 1 0 0 0 1 700 2x1 + x2 + x6 = 700
Z 7 5 0 0 0 0 0 Z = 7x1 + 5x2
6. Première itération
La solution de base de départ consiste à ne rien produire soit x1 = x2 = 0. On étudie ensuite, à partir
de cette solution, jusqu’à quel niveau on peut porter x1 ou x2 conformément aux contraintes de façon
à accroı̂tre au maximum le profit. Il se pose le problème du choix de la variable x1 ou x2 qui va passer
de la valeur 0 à une valeur strictement positive. La variable choisie sera appelée variable entrante.
• Critère de sélection de la variable entrante :
Cette sélection doit s’accompagner d’une augmentation de la fonction économique
Z = 7x1 + 5x2
La sélection portera sur x1 qui par unité rapporte le plus. Cette règle est appelée règle du plus
grand gain marginal :
Le critère de sélection de Dantzig de la variable entrante consiste, dans la fonction économique exprimée
exclusivement en fonction des variables hors-base, à sélectionner la variable affectée du coefficient
strictement positif le plus élevé.
x3 = 300 − x1
x4 = 400 − x2
x5 = 500 − x1 − x2
x = 700 − 2x1 − x2
6
Z = 7x1 + 5x2
La variable x2 reste hors-base donc nulle, la variable x1 entre en base. On reporte x2 = 0 dans ce
système, on obtient :
x3 = 300 − x1
x4 = 400
x5 = 500 − x1
x6 = 700 − 2x1
Z = 7x1
On cherche jusqu’à quel niveau il est possible de porter x1 , de façon compatible avec les contraintes
x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0. Les contraintes de positivité donnent
x1 ≤ 300, x1 ≤ 500, x1 ≤ 350.
La valeur maximale prise par x1 est donc 300. On remplace x1 par 300 dans le système et on obtient
x3 = 0, x4 = 400, x5 = 200, x6 = 100 et Z = 2100.
La variable x3 est devenue nulle, elle est sortie de la base, x3 est appelée variable sortante. Les
variables x1 et x3 ont permuté.
On a pris la colonne des variables dans la base du premier tableau et on y a remplacé x3 par x1 .
Pour la fonction économique Z, le coefficient constant 2100 est affecté impérativement du signe ”−”
et on place −2100.
7. Deuxième itération
• Sélection de la variable entrante :
8.4. LA MÉTHODE DU SIMPLEXE 135
Les variables hors-base sont alors x3 et x6 , les variables dans la base sont x1 , x2 , x4 et x5 . Cette
itération conduit au sommet B(300, 100). Pour cette solution, la fonction économique prend la valeur
2600.
x2 et x6 ont permuté. On exprime les variables dans la base en fonction des nouvelles variables hors-base
x3 et x6
x 1 + x 3 = 300
x1 = 300 − x3
x2 + x4 = 400 x2 = 700 − 2(300 − x3 ) − x6 = 100 + 2x3 − x6
x1 + x2 + x5 = 500 ⇔ x4 = 400 − (100 + 2x3 − x6 )
2x1 + x2 + x6 = 700
x5 = 500 − (300 − x3 ) − (100 + 2x3 − x6 )
Z = 7x1 + 5x2 Z = 7(300 − x3 ) + 5(100 + 2x3 − x6 )
Le programme linéaire se réécrit finalement :
x1 + x3 = 300
x2 − 2x3 + x6 = 100
2x3 + x4 − x6 = 300
x + x5 − x6 = 100
3
Z = 2600 + 3x3 − 5x6
PP
PP VHB
PP x1 x2 x4 x5
VDB PP
P x3 x6 cste
• • • •
x1 1 0 1 0 0 0 300 x1 + x3 = 300
x4 0 0 2 1 0 −1 300 2x3 + x4 − x6 = 300
x5 0 0 1 0 1 −1 100 x3 + x5 − x6 = 100
x2 0 1 −2 0 0 1 100 x2 − 2x3 + x6 = 100
Z 0 0 3 0 0 −5 −2600 Z = 3x3 − 5x6 + 2600
On a pris la colonne des variables dans la base du second tableau et on y a remplacé x6 par x2 (ces
deux variables permutent).
Pour la fonction économique Z, le coefficient constant 2600 est affecté du signe ”−” et on place −2600.
8. Troisième itération
136 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
Cette itération conduit au sommet C(200, 300). La valeur de la fonction économique est Z = 2900.
On a pris la colonne des variables dans la base du troisième tableau et on y a remplacé x5 par x3 .
Pour la fonction économique Z, le coefficient constant 2900 est affecté du signe ”−” et on place −2900.
8.4. LA MÉTHODE DU SIMPLEXE 137
Conclusion :
Z = 2900 − 3x5 − 2x6 ,
x5 et x6 sont hors-base donc nulles, toute augmentation de x5 ou x6 entraı̂ne une diminution de Z. Il n’est
plus possible d’améliorer la fonction économique, la solution (x1 = 200, x2 = 300) est la solution optimale.
On interprète les résultats de la manière suivante :
. x1 = 200 bureaux de modèle luxe,
. x2 = 300 bureaux de modèle standard,
. x3 = 100, il reste une possibilité de fabriquer 100 bureaux de modèle luxe,
. x4 = 100, il reste une possibilité de fabriquer 100 bureaux de modèle standard,
. x5 = 0, tout le bois disponible est utilisé,
. x6 = 0, tout le temps disponible est utilisé.
– Tableau initial
PP
PP VHB
PP x3 x4 x5 x6
VDB PP
P x1 x2 cste
• • • •
x3 1 0 1 0 0 0 300
x4 0 1 0 1 0 0 400
x5 1 1 0 0 1 0 500
x6 2 1 0 0 0 1 700
Z 7 5 0 0 0 0 0
x1 constante C
300
x3 1 300 = 300
1
400
x4 0 400 = +∞
0
500
x5 1 500 = 500
1
700
x6 2 700 = 350
2
On sélectionne dans cette colonne le plus petit nombre strictement positif 300. La variable x3 sort
de la base. Les deux variables x1 et x3 ont permuté. Le pivot est situé à l’intersection de la colonne
variable entrante et de la ligne variable sortante et est égal à 1.
138 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
– Deuxième tableau :
Impérativement dans la colonne des variables dans la base du tableau initial, on remplace la variable
x3 qui sort de la base par la variable x1 qui entre en base, on recopie les autres variables d’où la
disposition du second tableau
PP
PP VHB
PP x1 x4 x5 x6
VDB PP
P x2 x3 cste
• • • •
x1
x4
x5
x6
Z
Comment remplit-on le tableau ?
On recopie la ligne Lp du pivot (avec un pivot a = 1) dans la ligne Lx1 :
Lp 1 0 1 0 0 0 300
On doit exprimer le programme en fonction des nouvelles variables hors-base x2 et x3 .
. Pour la ligne Lx4 ,
x2 + x4 = 400.
x4 s’exprime bien en fonction de x2 et x3 . On recopie cette ligne.
. Pour la ligne Lx5 ,
x1 + x2 + x5 = 500.
Par une combinaison linéaire de la ligne Lx5 et de la ligne pivot Lp , on élimine la variable x1 qui
est entrée en base :
Lx5 1 1 0 0 1 0 500
Lp 1 0 1 0 0 0 300
Lx5 − Lp 0 1 −1 0 1 0 200
Lx6 2 1 0 0 0 1 700
Lp 1 0 1 0 0 0 300
Lx6 − 2Lp 0 1 −2 0 0 1 100
– Troisième tableau :
Z = 5x2 − 7x3 + 2100,
la variable entrante est x2 (une augmentation de x3 entraı̂ne une dimimution de Z). Déterminons la
variable sortante : la colonne C est donnée par :
x2 constante C
300
x1 0 300 = +∞
0
400
x4 1 400 = 400
1
200
x5 1 200 = 200
1
100
x6 1 100 = 100
1
On sélectionne dans cette colonne C le coefficient strictement positif le plus petit c’est-à-dire 100, la
variable x6 sort de la base. Les variables x2 et x6 ont permuté. Le pivot est situé à l’intersection de la
colonne variable entrante et de la ligne variable sortante. Ce pivot vaut 1.
On remplit le troisième tableau : dans la colonne des variables dans la base du deuxième tableau,
on remplace la variable x6 qui sort de la base par la variable x2 qui entre en base. On recopie la ligne
pivot avec le pivot de 1 :
Lp : 1.x2 − 2.x3 + 1.x6 = 100
PP
PP VHB
PP x1 x2 x4 x5
VDB PP
P x3 x6 cste
• • • •
x1
x4
x5
x2 0 1 −2 0 0 1 100
Z
Par des combinaisons avec la ligne pivot, on exprime le système en fonction des variables hors-base x3
140 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
– Quatrième tableau :
Z = 3x3 − 5x6 + 2600
La variable entrante est x3 (toute augmentation de x6 entraı̂ne une diminution de Z). Déterminons la
variable sortante : la colonne C est donnée par
x3 constante C
300
x1 1 300
= 300
1
300
x4 2 300 = 150
2
100
x5 1 100 = 100
1
100
x2 −2 100 = −50
−2
On sélectionne dans cette colonne C le coefficient strictement positif le plus petit c’est-à-dire 100, la
variable x5 sort de la base. Les variables x3 et x5 ont permuté. Le pivot est 1, il est situé à l’intersection
de la colonne x3 et de la ligne x5 . On remplit le quatrième tableau : dans la colonne des variables dans
la base du troisième tableau, on remplace la variable x5 qui sort de base par la variable x3 qui entre
en base. On recopie la ligne pivot avec un pivot de 1 :
8.4. LA MÉTHODE DU SIMPLEXE 141
Lp : x3 + x5 − x6 = 100
PP
PP VHB
PP x1 x2 x3 x4
VDB PP
P x5 x6 cste
• • • •
x1
x4
x3 0 0 1 0 1 −1 100
x2
Z
Par des combinaisons avec la ligne pivot, on exprime le système en fonction des variables hors-base x5
et x6 c’est-à-dire qu’on élimine la variable x3 qui est entrée en base :
. pour la ligne Lx1 :
Lx1 1 0 1 0 0 0 300
Lp 0 0 1 0 1 −1 100
Lx1 − Lp 1 0 0 0 −1 1 200
. pour la ligne Lx4 :
Lx4 0 0 2 1 0 −1 300
Lp 0 0 1 0 1 −1 100
Lx4 − 2Lp 0 0 0 1 −2 1 100
. pour la ligne Lx2 :
Lx2 0 1 −2 0 0 1 100
Lp 0 0 1 0 1 −1 100
Lx2 + 2Lp 0 1 0 0 2 −1 300
. pour la ligne LZ :
LZ 0 0 3 0 0 −5 −2600
Lp 0 0 1 0 1 −1 100
LZ − 3Lp 0 0 0 0 −3 −2 −2900
On peut ensuite remplir le quatrième tableau :
PP
PP VHB
PP x1 x2 x3 x4
VDB PP
P x5 x6 cste
• • • •
x1 1 0 0 0 −1 1 200
x4 0 0 0 1 −2 1 100
x3 0 0 1 0 1 −1 100
x2 0 1 0 0 2 −1 300
Z 0 0 0 0 −3 −2 −2900
142 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
Conclusion, la fonction économique s’écrit Z = 2900 − 3x5 − 2x6 où x5 et x6 sont les variables hors-base donc
nulles. Toute augmentation de x5 et x6 conduit à une diminution de Z. Donc x1 = 200, x2 = 300, x3 = 100,
x4 = 100 et Z = 2900. La fonction économique atteint son maximum au point C(200, 300) et vaut 2900.
1. Programme standard :
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0
x1 + 3x2 + 2x3 + x4 = 40
3x1 + 2x2 + x3 + x5 = 45
x + x2 + 4x3 + x6 = 38
1
Z = 10x1 + 14x2 + 12x3 à maximiser
La solution de base de départ du programme correspond au sommet 0, c’est la solution nulle qui
consiste à ne rien produire : x1 = x2 = x3 = 0 et Z = 0. Les variables x1 , x2 , x3 sont hors-base donc
nulles, les autres variables x4 , x5 , x6 sont dans la base.
2. Tableau initial :
PP
PP VHB
PP x4 x5 x6
VDB PP
P x1 x2 x3 cste
• • •
x4 1 3 2 1 0 0 40 x1 + 3x2 + 2x3 + x4 = 40
x5 3 2 1 0 1 0 45 3x1 + 2x2 + x3 + x5 = 45
x6 1 1 4 0 0 1 38 x1 + x2 + 4x3 + x6 = 38
Z 10 14 12 0 0 0 0 Z = 10x1 + 14x2 + 12x3
x2 constante C
40
x4 3 40 ≃ 13, 33
3
45
x5 2 45 = 22, 5
2
38
x6 1 38 = 38
1
On sélectionne le coefficient strictement positif le plus petit dans la colonne C, la variable x4 sort
de la base.
8.4. LA MÉTHODE DU SIMPLEXE 143
• Le pivot : il est situé à l’intersection de la colonne variable qui entre en base et de la ligne variable
qui sort de la base, ce pivot est 3. Afin d’obtenir un pivot de 1, on divise tous les coefficients de la
ligne pivot par ce pivot 3. On obtient la nouvelle ligne pivot :
1 2 1 40
Lp : x1 + x2 + x3 + x4 =
3 3 3 3
soit
1 2 40
Lp 1 1 0 0
3 3 3
3. Deuxième tableau :
PP
PP VHB
PP x2 x5 x6
VDB PP
P x1 x3 x4 cste
• • •
1 2 1 40
x2 1 0 0
3 3 3 3
x5
x6
Z
Lx5 3 2 1 0 1 0 45
1 2 1 40
Lp 1 0 0
3 3 3 3
7 1 2 55
Lx5 − 2Lp 0 − − 1 0
3 3 3 3
. pour la ligne Lx6 :
L x6 1 1 4 0 0 1 38
1 2 1 40
Lp 1 0 0
3 3 3 3
2 10 1 74
Lx6 − Lp 0 − 0 1
3 3 3 3
. pour la ligne LZ :
LZ 10 14 12 0 0 0 0
1 2 1 40
Lp 1 0 0
3 3 3 3
16 8 14 560
LZ − 14Lp 0 − 0 0 −
3 3 3 3
PP
PP VHB
PP x2 x5 x6
VDB PP
P x1 x3 x4 cste
• • •
1 2 1 40
x2 1 0 0
3 3 3 3
7 1 2 55
x5 0 − − 1 0
3 3 3 3
2 10 1 74
x6 0 − 0 1
3 3 3 3
16 8 14 560
Z 0 − 0 0 −
3 3 3 3
On a par conséquent
16 8 14 560
Z= x1 + x3 − x4 +
3 3 3 3
4. Troisième tableau :
16
• La variable entrante est x1 ; en effet, est le coefficient strictement positif le plus grand dans la
3
fonction économique.
• La variable sortante est déterminée à l’aide de la colonne C :
x1 constante C
1 40 40 1
x2 / = 40
3 3 3 3
7 55 55 7 55
x5 / =
3 3 3 3 7
2 74 74 2
x6 / = 37
3 3 3 3
55
On choisit le coefficient strictement positif le plus petit dans la colonne C soit , la variable x5
7
sort de la base.
7
• Le pivot est , situé à l’intersection de la colonne variable qui entre en base et de la ligne variable
3
7
qui sort de la base. Pour obtenir un pivot de 1, on divise la ligne pivot par ce pivot , on obtient
3
1 2 3 55
Lp = x1 − x3 − x4 + x5 =
7 7 7 7
soit
1 2 3 55
Lp 1 0 − − 0
7 7 7 7
5. Quatrième tableau :
24 22 16 1600
Z= x3 − x4 − x5 +
7 7 7 7
24
• Variable entrante : on sélectionne le coefficient , la variable x3 entre en base.
7
• Variable sortante :
x3 Constante C
5 75 75 5
x2 / = 15
7 7 7 7
1 55 55 1
x1 − / − = −55
7 7 7 7
24 136 136 24 17
x6 / =
7 7 7 7 3
La variable x6 sort de base.
24
• Le pivot est , on divise la ligne pivot par ce pivot et on obtient la nouvelle ligne pivot :
7
1 1 7 17
Lp : x3 − x4 − x5 + x6 =
24 12 24 3
1 1 7 17
Lp 0 0 1 − −
24 12 24 3
146 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
Dans la colonne variables dans la base du troisième tableau, on remplace la variable x6 par la variable
x3 et on y recopie la nouvelle ligne pivot
PP
PP VHB
PP x1 x2 x3
VDB PP
P x4 x5 x6 cste
• • •
x2
x1
1 1 7 17
x3 0 0 1 − −
24 12 24 3
Z
On exprime le système en fonction des variables hors-base x4 , x5 et x6 . On élimine la variable x3
qui est entrée en base :
. pour la ligne Lx2 :
5 3 1 75
Lx2 0 1 − 0
7 7 7 7
1 1 7 17
Lp 0 0 1 − −
24 12 24 3
11 1 5 20
Lx2 − 57 Lp 0 1 0 − −
24 12 24 3
. pour la ligne Lx1 :
1 2 3 55
Lx1 1 0 − − 0
7 7 7 7
1 1 7 17
Lp 0 0 1 − −
24 12 24 3
7 5 1 26
Lx1 + 17 Lp 1 0 0 −
24 12 24 3
. pour la ligne LZ :
24 22 16 1600
LZ 0 0 − − 0 −
7 7 7 7
1 1 7 17
Lp 0 0 1 − −
24 12 24 3
LZ − 24
7 Lp 0 0 0 −3 −2 −1 −248
PP
PP VHB
PP x1 x2 x3
VDB PP
P x4 x5 x6 cste
• • •
11 1 5 20
x2 0 1 0 − −
24 12 24 3
7 5 1 26
x1 1 0 0 −
24 12 24 3
1 1 7 17
x3 0 0 1 − −
24 12 24 3
Z 0 0 0 −3 −2 −1 −248
8.4. LA MÉTHODE DU SIMPLEXE 147
6. Conclusion :
Z = −3x4 − 2x5 − x6 + 248
Les trois variables x4 , x5 et x6 sont affectées de coefficients négatifs, toute augmentation de x4 , x5 ou
x6 diminuerait la valeur de Z. Il n’est plus possible d’améliorer la fonction économique.
20 26 17
Z est maximum pour x4 = 0, x5 = 0, x6 = 0, x1 = , x2 = , x3 = et Z = 248.
3 ( 3 )3
20 26 17
La fonction économique atteint son maximum au point , , . De plus, x4 = 0, x5 = 0 et
3 3 3
x6 = 0, les trois matières premières sont utilisées en totalité.
x1 ≥ 0, x2 ≥ 0
x2 ≤ 45
3x1 + x2 ≤ 120
x1 + 2x2 ≤ 100
x + x2 ≤ 60
1
Maximiser Z = x1 + 2x2
1. Résolution graphique
( )
−2
On trace les droites DZ d’équations Z = x1 + 2x2 , ces droites ont pour vecteur directeur ⃗v .
1
Elles sont parallèles entre-elles et de plus, elles sont parallèles au côté (BC) d’équation x1 + 2x2 = 100,
10 ≤ x1 ≤ 20. La droite DZ qui rencontre le domaine des solutions réalisables et qui a une ordonnée à
l’origine maximale est la droite qui contient B et C, d’équation x1{+2x2 = 100. La fonction économique
x1 + 2x2 = 100
atteint son maximum 100 en tous les points du segment [BC] :
10 ≤ x1 ≤ 20
2. Le simplexe
Comment fait-on apparaı̂tre cette infinité de couples solutions dans les tableaux du simplexe ?
148 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
(a) Tableau initial : les variables hors-base sont x1 et x2 , le programme standard est donné par :
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0
x2 + x3 = 45
3x1 + x2 + x4 = 120
x1 + 2x2 + x5 = 100
x1 + x2 + x6 = 60
Z = x1 + 2x2 à maximiser
Lp 0 1 1 0 0 0 45
Lx4 3 1 0 1 0 0 120
Lp 0 1 1 0 0 0 45
Lx4 − Lp 3 0 −1 1 0 0 75
. Pour la ligne Lx5 :
Lx5 1 2 0 0 1 0 100
Lp 0 1 1 0 0 0 45
Lx5 − 2Lp 1 0 −2 0 1 0 10
. Pour la ligne Lx6 :
Lx6 1 1 0 0 0 1 60
Lp 0 1 1 0 0 0 45
Lx6 − Lp 1 0 −1 0 0 1 15
. Pour la ligne LZ :
8.4. LA MÉTHODE DU SIMPLEXE 149
LZ 1 2
Lp 0 1 1 0 0 0 45
LZ − 2Lp 1 0 −2 0 0 0 −90
PP
PP VHB
PP x2 x4 x5 x6
VDB PP
P x1 x3 cste C
• • • •
45
x2 0 1 1 0 0 0 45 = +∞
0
75
x4 3 0 −1 1 0 0 75 = 25
3
10
x5 1 0 −2 0 1 0 10 = 10
1
15
x6 1 0 −1 0 0 1 15 = 15
1
Z 1 0 −2 0 0 0 −90
Cette première itération conduit du sommet O(0, 0) au sommet A(0, 45) et Z = 90.
L x2 0 1 1 0 0 0 45
Lp 1 0 −2 0 1 0 10
L x2 0 1 1 0 0 0 45
Lx4 3 0 −1 1 0 0 75
Lp 1 0 −2 0 1 0 10
Lx4 − 3Lp 0 0 5 1 −3 0 45
Lx6 1 0 −1 0 0 1 15
Lp 1 0 −2 0 1 0 10
Lx6 − Lp 0 0 1 0 −1 1 5
LZ 1 0 −2 0 0 0 −90
Lp 1 0 −2 0 1 0 10
LZ − Lp 0 0 0 0 −1 0 −100
150 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
PP
PP VHB
PP x1 x2 x4 x6
VDB PP
P x3 x5 cste C
• • • •
45
x2 0 1 1 0 0 0 45 = 45
1
45
x4 0 0 5 1 −3 0 45 =9
5
10
x1 1 0 −2 0 1 0 10 = −5
−2
5
x6 0 0 1 0 −1 1 5 =5
1
Z 0 0 0 0 −1 0 −100
Lp : x3 − x5 + x6 = 5
soit
Lp 0 0 1 0 −1 1 5
x3 et x6 ont permuté
Lx2 0 1 1 0 0 0 45
Lp 0 0 1 0 −1 1 5
Lx2 − Lp 0 1 0 0 1 −1 40
Lx4 0 0 5 1 −3 0 45
Lp 0 0 1 0 −1 1 5
Lx4 − 5Lp 0 0 0 1 2 −5 20
Lx1 1 0 −2 0 1 0 10
Lp 0 0 1 0 −1 1 5
Lx1 + 2Lp 1 0 0 0 −1 2 20
LZ 0 0 0 0
Lp 0 0 1 0 −1 1 5
LZ + [Link] 0 0 0 0 −1 0 −100
8.4. LA MÉTHODE DU SIMPLEXE 151
PP
PP VHB
PP x1 x2 x3 x4
VDB PP
P x5 x6 cste
• • • •
x2 0 1 0 0 1 −1 40
x4 0 0 0 1 2 −5 20
x1 1 0 0 0 −1 2 20
x3 0 0 1 0 −1 1 5
Z 0 0 0 0 −1 0 −100
Remarque 8.4.1
1. La présence d’un zéro dans la ligne pivot entraı̂ne l’invariance de la colonne correspondante.
Le pivot est 1, dans la ligne pivot, les variables x2 , x4 , x5 , x6 sont affectées du coefficient 0. Ces quatre
colonnes seront invariantes dans le tableau suivant, on peut donc recopier ces quatre colonnes sans
effectuer de calculs.
PP
PP VHB
PP x1 x4 x5 x6
VDB PP
P x2 x3 cste
• • • •
x1 1 0 1 0 0 0 300
x4 1 1 0 0
x5 1 0 1 0
x6 1 0 0 1
Z 5 0 0 0
152 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
On peut aussi recopier la ligne pivot. De plus, le système doit s’exprimer en fonction des variables
hors-base x2 , x3 donc x4 s’exprime en fonction de x2 , x3 ainsi que x5 , x6 et Z d’où les compléments
dans le tableau “encadrés”. On peut donc, sans effectuer de calculs, remplir certaines cases du tableau.
2. La présence d’un zéro dans la colonne du pivot entraı̂ne l’invariance de la ligne correspondante.
On reprend le second tableau de l’exemple 8.4.3. En utilisant les deux remarques 1. et 2., on ob-
tient
PP
PP VHB
PP x1 x4 x5 x6
VDB PP
P x2 x3 cste C
• • • •
300
x1 1 0 1 0 0 0 300 = 300
1
400
x4 0 1 0 1 0 0 400 = 400
1
200
x5 0 1 −1 0 1 0 200 = 200
1
100
x6 0 1 −2 0 0 1 100 = 100
1
Z 0 5 −7 0 0 0 −200
Lp 0 1 −2 0 0 1 100
. Dans la ligne du pivot, les variables x1 , x4 ou x5 sont affectées du coefficient 0, on recopiera ces trois
colonnes.
. On recopie la ligne du pivot.
. Dans la colonne du pivot apparaı̂t un zéro, on recopie la ligne Lx1 .
Ces remarques permettent donc d’obtenir deux lignes et trois colonnes du tableau suivant :
PP
PP VHB
PP x1 x4 x5 x6
VDB PP
P x2 x3 cste
• • • •
x1 1 0 1 0 0 0 300
x4 0 1 0
x5 0 0 1
x2 0 1 −2 0 0 1 100
Z 0 0 0
Les variables hors-base étant x2 , x3 , le système s’écrit en fonction des variables hors-base seulement
d’où les compléments dans le tableau “encadrés´’.
Il reste neuf cases à remplir dans le tableau.
3. Si deux coefficients positifs dans la fonction économique sont égaux, on pourra déterminer dans chaque
colonne correspondante le pivot éventuel et le rapport associé. On choisira comme pivot celui qui
correspond au plus grand rapport.
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
3x1 + 5x2 + x3 ≤ 150
x + 4x2 + 2x3 + x5 ≤ 80
1
Z = 2x1 + 2x2 + x3 à maximiser
PP
PP VHB
PP x4 x5
VDB PP
P x1 x2 x3 cste
• •
x4 3 5 1 1 0 150
x5 1 4 2 0 1 80
Z 2 2 1
x1 C
150
x4 3 150 = 50
3
80
x5 1 80 = 80
1
La variable sortante est x4 , le pivot est égal à 3, le rapport vaut 50.
x2 C
150
x4 5 150 = 30
5
80
x5 4 80 = 20
4
La variable sortante est alors x5 , le pivot est égal à 4 et le rapport vaut 20.
On choisit comme variable sortante celle qui correspond au plus grand rapport. Dans l’exemple, 50 > 20, la
variable sortante est x4 , la variable entrante x1 , le pivot est 3.
La règle d’entrée du plus grand gain marginal nous propose une méthode qui permet d’obtenir la valeur
optimale de Z, mais rien n’indique que cette méthode propose le plus court chemin.
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0
1 + x4 = 5
x
4x1 + x2 + x5 = 25
8x1 + 4x2 + x3 + x6 = 125
Z = 4x1 + 2x2 + x3 à maximiser
On a le tableau :
PP
PP VHB
PP x4 x5 x6
VDB PP
P x1 x2 x3 cste C
• • •
x4 1 0 0 1 0 0 5 5
25
x5 4 1 0 0 1 0 25 = 6, 25
4
125
x6 8 4 1 0 0 1 125 = 15, 625
8
Z 4 2 1 0 0 0 0
On applique la règle du plus grand gain marginal, x1 entre en base, x4 sort de base, le pivot est 1. On
obtient le tableau suivant
PP
PP VHB
PP x1 x5 x6
VDB PP
P x2 x3 x4 cste C
• • •
5
x4 1 0 0 1 0 0 5 = +∞
0
5
x5 0 1 0 −4 1 0 5 =5
1
85
x6 0 4 1 −8 0 1 85 = 21, 25
4
Z 0 2 1 −4 0 0 −20
PP
PP VHB
PP x2 x4 x6
VDB PP
P x1 x3 x5 cste C
• • •
x4 1 0 0 1 0 0 5 +∞
x2 4 1 0 0 1 0 25 +∞
x6 −8 0 1 0 −4 1 25 25
Z −4 0 1 0 −2 0 −50
PP
PP VHB
PP x2 x3 x4
VDB PP
P x1 x5 x6 cste C
• • •
x4 1 0 0 1 0 0 5 5
x2 4 1 0 0 1 0 25 6, 25
x3 −8 0 1 0 −4 1 25 −3, 125
Z 4 0 0 0 −2 −1 −75
PP
PP VHB
PP x1 x2 x3
VDB PP
P x4 x5 x6 cste C
• • •
x1 1 0 0 1 0 0 5 +∞
x2 0 1 0 −4 1 0 5 5
x3 0 0 1 8 −4 1 65 −16, 25
Z 0 0 0 −4 2 −1 −95
PP
PP VHB
PP x1 x3 x5
VDB PP
P x2 x4 x6 cste C
• • •
x1 1 0 0 1 0 0 5 5
x5 0 1 0 −4 1 0 5 −1, 25
x3 0 4 1 −8 0 1 85 −10, 625
Z 0 −2 0 4 0 −1 −105
PP
PP VHB
PP x3 x4 x5
VDB PP
P x1 x2 x6 C
• • •
x4 1 0 0 1 0 0 5
x5 4 1 0 0 1 0 25
x3 8 4 1 0 0 1 125
Z −4 −2 0 0 0 −1 −125
les variables hors-base x1 , x2 et x6 sont affectées de coefficients négatifs, Z atteint son maximum au point
A7 (0, 0, 125) et vaut 125.
La règle du plus grand gain marginal nous a contraint au chemin OA1 A2 A3 A4 A5 A6 A7 de coordonnées
respectives (0, 0, 0), (5, 0, 0), (5, 5, 0), 0, 25, 0), (0, 25, 25), (5, 5, 65), (5, 0, 85), (0, 0, 125).
PP
PP VHB
PP x4 x5 x6
VDB PP
P x1 x2 x3 cste C
• • •
x4 1 0 0 1 0 0 5 +∞
x5 4 1 0 0 1 0 25 +∞
x6 8 4 1 0 0 1 125 125
Z 4 2 1 0 0 0 0
Si on n’utilise pas la règle du plus grand gain marginal et si on décide de faire entrer x3 en base, x6 sort de
base et le pivot est 1 :
8.4. LA MÉTHODE DU SIMPLEXE 157
PP
PP VHB
PP x3 x4 x5
VDB PP
P x1 x2 x6 cste
• • •
x4 1 0 0 1 0 0 5
x5 4 1 0 0 1 0 25
x3 8 4 1 0 0 1 125
Z −4 −2 0 0 0 −1 −125
les variables hors-base x1 , x2 et x6 sont affectées de coefficients négatifs, Z atteint son maximum au point
A7 (0, 0, 125) et vaut 125. Le résultat est cette fois-ci atteint en une seule itération à l’aide de ce qu’on appelle
la règle du plus petit gain marginal. Il conviendra de choisir alors parmi les deux règles proposées afin de
minimiser les temps de calculs.
Une solution consiste alors à annuler au hasard n variables parmi les m + n variables que comporte le
problème (dans le cas de l’exemple précédent, 2 variables parmi 9).
n
Il y a alors Cm+n solutions de base envisageables (ici C92 = 36). Mais toutes ne sont pas admissibles et,
de plus, si le nombre de variables et de contraintes est important, il devient fastidieux de s’en remettre au
hasard.
C’est pourquoi une procédure plus méthodique consiste :
1. À introduire dans chaque contrainte h qui pose problème une variable artificielle ah affectée
d’un coefficient égal à 1.
2. À infliger à chaque variable artificielle une pénalité sous la forme d’un coefficient négatif (dans le
cas d’un problème de maximisation) et de valeur absolue très élevée dans la fonction économique
originelle.
158 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
Ainsi, l’introduction de variables artificielles permet de déterminer simplement une base, certes artificielle,
mais admissible pour amorcer l’algorithme.
Les pénalités ont pour objet de provoquer l’élimination des variables artificielles au fil des itérations.
La méthode consiste donc ensuite
Dans le cas étudié, après introduction des variables artificielles a6 et a7 respectivement dans les contraintes
6 et 7, le problème s’écrit :
X1 , X2 , e1 , . . . , e7 , a6 , a7 ≥ 0
0, 5X1 + 0, 2X2 + e1 = 13600
0, 3X1 + 0, 6X2 + e2 = 12000
0, 2X1 + 0, 2X2 + e3 = 10400
X1 + e4 = 20000
X2 + e5 = 16000
X1 − e6 + a6 = 15000
X2 − e7 + a7 = 5000
max Z avec Z = 400X1 + 500X2 − Ga6 − Ga7
Les tableaux ci-dessous montrent qu’après deux itérations, une solution de base admissible est obtenue.
Cette base n’est plus artificielle mais réelle. La procédure doit ensuite être poursuivie jusqu’à l’obtention de
l’optimum, sans tenir compte des colonnes concernant les variables artificielles.
PP
PP VHB
PP e1 e2 e3 e4 e5 a6 a7
VDB PP
P X1 X2 e6 e7 cste C
• • • • • • •
e1 0,5 0,2 1 0 0 0 0 0 0 0 0 13600 68000
e4 1 0 0 0 0 1 0 0 0 0 0 20000 +∞
e5 0 1 0 0 0 0 1 0 0 0 0 16000 16000
a6 1 0 0 0 0 0 0 -1 0 1 0 15000 +∞
a7 0 1 0 0 0 0 0 0 -1 0 1 5000 5000
Z 400 500 0 0 0 0 0 0 0 -G -G 0
8.4. LA MÉTHODE DU SIMPLEXE 159
PP
PP VHB
PP X2 e1 e2 e3 e4 e5 a6
VDB PP
P X1 e6 e7 cste C
• • • • • • •
e1 0,5 0 1 0 0 0 0 0 0,2 0 12600 25200
e4 1 0 0 0 0 1 0 0 0 0 20000 20000
e5 0 0 0 0 0 0 1 0 1 0 11000 +∞
a6 1 0 0 0 0 0 0 -1 0 1 15000 15000
X2 0 1 0 0 0 0 0 0 -1 0 5000 +∞
Z 400 0 0 0 0 0 0 0 500 -G -2500000
PP
PP VHB
PP X1 X2 e1 e2 e3 e4 e5
VDB PP
P e6 e7 cste C
• • • • • • •
e1 0 0 1 0 0 0 0 0,5 0,2 5100
e2 0 0 0 1 0 0 0 0,3 0,6 4500
e3 0 0 0 0 1 0 0 0,2 0,2 6400
e4 0 0 0 0 0 1 0 1 0 5000
e5 0 0 0 0 0 0 1 0 1 11000
X1 1 0 0 0 0 0 0 -1 0 15000
X2 0 1 0 0 0 0 0 0 -1 5000
Z 0 0 0 0 0 0 0 400 500 -8500000
On peut alors démarrer l’algorithme du simplexe avec la solution admissible X1 = 15000 et X2 = 5000.
Exemple 8.4.8
x≥0 , y≥0
Maximiser ω = 2x + 6y si x − y ≤ 30
y − x ≤ 40
En résolvant graphiquement ce problème on remarque que la solution optimale n’existe pas puisque l’en-
semble convexe des solutions réalisables n’est pas borné et la fonction objectif peut augmenter dans ce cas
sans limite.
Appliquons l’algorithme du simplexe à cet exemple : la solution (x, y) = (0, 0) est admissible.
160 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
PP
PP VHB
PP e1 e2
VDB PP
P x y cste C
• •
e1 1 -1 1 0 30 -30
y -1 1 0 1 40 40
ω 2 6 0 0 0
PP
PP VHB
PP y e1
VDB PP
P x e2 cste C
• •
e1 0 0 1 1 70 +∞
y -1 1 0 1 40 -40
ω 8 0 0 -6 -240
Aucun coefficient de la colonne sélectionnée n’est positif donc la colonne C ne donne aucune valeur positive
non infinie, x peut donc augmenter indéfiniment et la fonction objectif ω également. On dira dans ce cas
que la valeur maximale n’existe pas.
Exemple 8.4.9
x≥0 , y≥0
Minimiser ω = −2x + y si x − 3y ≥ −1
x−y ≤ 1
On définit dans ce cas une façon de transformer les problèmes de minimisation en problèmes de maximisation.
On formule le principe suivant :
minimiser ω = - maximiser(-ω)
Le problème de minimisation précédent devra donc être transformé en un problème de maximisation soit
x≥0 , y≥0
Maximiser −ω = 2x − y si x − 3y ≥ −1
x−y ≤ 1
Appliquons l’algorithme du simplexe à cet exemple : la solution (x, y) = (0, 0) est admissible.
PP
PP VHB
PP e1 e2
VDB PP
P x y cste C
• •
e1 1 -3 -1 0 -1 -1
e2 1 -1 0 1 1 1
−ω 2 -1 0 0 0
8.4. LA MÉTHODE DU SIMPLEXE 161
PP
PP VHB
PP x e1
VDB PP
P y e2 cste C
• •
e1 0 -2 -1 -1 -2 1
x 1 -1 0 1 1 -1
−ω 0 1 0 -2 -2
PP
PP VHB
PP x y
VDB PP
P e1 e2 cste C
• •
1 1
y 0 1 1
2 2
1 3
x 1 0 2
2 2
1 5
−ω 0 0 − − -3
2 2
Produits
P1 P2 P3
Nombre de composants C1 1 2 4
Nombre de composants C2 2 1 2
Nombre de composants C3 3 2 2
Par exemple, pour fabriquer une unité de produit P3 , il faut 4 composants C1 , 2 composants C2 et 2
composants C3 .
On se donne ensuite les coûts unitaires transport et hors transport en euros des différents composants :
C1 C2 C3
Coûts unitaires hors-transport (en euros) 20 25 25
Coûts unitaires transport (en euros) 7 6 5
Les contraintes d’approvisionnement sont telles que l’entrepôt dispose chaque semaine de 70 composants C1 ,
80 composants C2 et 60 composants C3 .
Les marges sur coûts variables unitaires sont de 3 euros pour P1 , 5 euros pour P2 et 6 euros pour P3 .
On note respectivement x, y et z les nombres d’unités de P1 , P2 et P3 fabriquées au cours d’une semaine.
1. Quels sont les coûts totaux hors-transport ainsi que les coûts totaux de transport pour chacun des
composants utilisés ?
162 CHAPITRE 8. LA PROGRAMMATION LINÉAIRE
2. Présenter la forme canonique du programme linéaire permettant de maximiser la marge sur coûts
variables hebdomadaires.
3. Présenter la forme standard du programme linéaire permettant de maximiser la marge sur coûts
variables hebdomadaires.
4. Déterminer le programme optimal de production. Quelle est la marge correspondante ?
5. Si l’entreprise fabrique le programme optimal, combien reste t-il de composants de chaque sorte ?
Exercice 56 Suite à l’incendie d’un entrepôt, une société fait appel à vos compétences pour reconsti-
tuer un programme linéaire retrouvé sur place, dans un état malheureusement assez délabré. Les seules
informations dont vous disposez consistent en le tableau donné ci dessous :
PP
PP VHB
PP x y z e1 e2 e3 cste C
VDB PP
P
e1 1 0 0 0 0 0 400
e2 2 1 1 0 0 0 1000
e3 2 2 3 0 0 0 2000
Z 20 16 12 0 0 0 0
Exercice 58 La société SUPERSTOCK désire stocker dans son nouvel entrepôt trois types de produits à
savoir des coussins (produit P1 ), des traversins (produit P2 ) et des couvertures (produit P3 ) à l’aide de trois
conditionnements particuliers C1 (sacs), C2 (palettes) et C3 (cartons). Les données sont rassemblées dans
les tableaux ci-dessous :
Conditionnement
C1 C2 C3
Nombre de coussins P1 20 40 80
Nombre de traversins P2 40 20 40
Nombre de couvertures P3 60 40 40
Les contraintes de fabrication sont telles que l’entreprise stocke journalièrement 1400 coussins, 1600 traversins
et 1200 couvertures. Les gains relatifs au stockage et au transport pour les trois conditionnements sont donnés
ci-dessous :
C1 C2 C3