Recherche Opérationnelle

Pr. Amine El Kou

Année universitaire 2022/2023

Table des matières

1 Introduction 3
1.1 Origines de la recherche opérationnelle . . . . . . . . . . . . . 3
1.2 Dénitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Quelques domaines et exemples d'applications de la RO . . . 4
1.3.1 Problème de production . . . . . . . . . . . . . . . . . 4
1.3.2 Problème de transport . . . . . . . . . . . . . . . . . . 5

2 Usage des graphes 6

2.1 Quelques notions de base de la théorie des graphes . . . . . . 6
2.2 Quelques problèmes de la R.O utilisant les graphes . . . . . . 9
2.2.1 Planning d'examen . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Inéquations et Graphes . . . . . . . . . . . . . . . . . 11

3 Programmation linéaire 12
3.0.1 Notions de base . . . . . . . . . . . . . . . . . . . . . . 13
3.1 Quelques exemples de programmes linéaires . . . . . . . . . . 14
3.1.1 Problème de production résolu par la méthode graphique 14
3.1.2 Formulation du problème de transport . . . . . . . . . 16
3.1.3 Algorithme des simplexes . . . . . . . . . . . . . . . . 17
3.1.4 Fonction Solveur . . . . . . . . . . . . . . . . . . . . . 19
3.1.5 La dualité . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 Exercices d'application . . . . . . . . . . . . . . . . . . . . . . 21

4 Algorithmes de recherche d'un chemin optimal 24

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2 Formulation du problème . . . . . . . . . . . . . . . . . . . . 24
4.3 Algorithmes de résolution . . . . . . . . . . . . . . . . . . . . 25
4.3.1 Algorithme de Ford . . . . . . . . . . . . . . . . . . . . 25
4.3.2 L'algorithme d'identication d'un chemin optimal . . . 26
4.3.3 Algorithme de Bellman-Ford pour la recherche du plus
court chemin . . . . . . . . . . . . . . . . . . . . . . . 27
4.3.4 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . 30
4.4 Exercices d'application . . . . . . . . . . . . . . . . . . . . . . 31

1
5 Problèmes d'ordonnancement 32
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.2 Critère temporel . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.2.1 Méthode du potentiel . . . . . . . . . . . . . . . . . . 33
5.2.2 Méthode P.E.R.T. . . . . . . . . . . . . . . . . . . . . 33
5.2.3 Résolution . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.2.4 Algorithme d'obtention d'un ordonnancement de du-
rée minimale . . . . . . . . . . . . . . . . . . . . . . . 36
5.2.5 Diagramme de GANTT . . . . . . . . . . . . . . . . . 41

6 Annexe : Utilisation d'EXCEL pour résoudre un programme

linéaire 43

2
Chapitre 1

Introduction

1.1 Origines de la recherche opérationnelle

Si la recherche opérationnelle, (en abrégé RO), est aujourd'hui présente
dans la plupart des domaines civils, ses racines sont attribuées aux services
militaires. La seconde guerre mondiale, de part son envergure, créa un besoin
urgent d'allouer de manière ecace des ressources limitées aux diérentes
opérations militaires et aux activités au sein de chaque opération. En par-
ticulier, l'organisation militaire britanique, puis américaine, mis à contribu-
tion un grand nombre de scientiques pour gérer ces allocations, et s'occuper
d'autres problèmes stratégiques et tactiques. Ce faisant, ils furent appelés à
poursuivre des recherches sur des opérations (militaires), et constituèrent les
premières équipes de RO. Leurs eorts furent signicatifs dans la marche
vers la victoire, par exemple en ce qui touche l'utilisation du radar nou-
vellement développé. Ces succès encouragèrent la poursuite de l'utilisation
de la RO dans d'autres domaines. La croissance importante de l'industrie
d'après guerre entraîna des problèmes, causés par la complexité croissante
et la spécialisation dans les organisations, problèmes en fait proches de ceux
présents lors du conit. Au début des années 1950', la RO avait pénétré une
multitude d'organisations commerciales, industrielles et gouvernementales.
Et ce n'était que le début. Au moins deux autres facteurs ont joué un rôle
clé dans la croissance rapide de la RO. Tout d'abord, des progrès substan-
tiels ont été obtenus très tôt an d'améliorer les techniques de la RO. Ces
techniques, dans leur mise en pratique, furent soutenues par l'essor des outils
informatiques.

1.2 Dénitions
Dénition 1.2.1 La recherche opérationnelle (R.O) ou la science de la dé-
cision est la discipline des méthodes scientiques utilisables pour élaborer des
meilleures décisions. Elle permet de rationaliser, de simuler, de planier et

3
d'optimiser l'architecture et le fonctionnement des systèmes de production et
d'organisation. En pratique, la R.O sert à résoudre diérents types de pro-
blèmes diciles (issus des mathématiques, de l'informatique, de l'économie,
de l'industrie...)

Une dénition possible de la RO pourrait être la suivante :

Dénition 1.2.2 Il s'agit d'unensemble de méthodes d'analyse scientique
des phénomènes d'organisation qui traite de la maximisation d'un prot,
d'une performance, d'un rendement ou bien de la minimisation d'un coût,
d'une dépense.

Etapes pratiques :
 Dénition du problème
 Construction d'un modèle
 Solution du modèle
 Validation du modèle
 Implémentation de la solution
Méthodologie
 Les étapes les plus importantes sont la dénition du problème (sup-
pose un dialogue avec le décideur) et la construction du modèle (prendre
conscience des hypothèses simplicatrices et de leur impact).
 La phase de validation doit permettre de remettre en cause la validité
du modèle.
 Une approche globale nécessite donc un aller-retour constant entre le
modèle et les attentes du décideur.
Techniques principales
 Théorie des graphes.
 Programmation linéaire.
 Programmation en nombres entiers.
 Optimisation dans les réseaux.

1.3 Quelques domaines et exemples d'applications

de la RO
1.3.1 Problème de production
Détermination d'un plan optimal de fabrication : Une entreprise fabrique
plusieurs produits, ce qui exige des ressources particulières (matières pre-
mières, machines, personnel...) en quantités limitées. Chaque produit rap-
porte un certain bénéce (connu) à l'entreprise.
Quels produits l'entreprise doit-elle fabriquer et en quelle quantité pour réa-
liser le bénéce total le plus élevé ?

4
Exemple 1.3.1 Une entreprise fabrique quatre produits. La fabrication de
chaque produit nécessite une certaine quantité de ressources. Les ressources
consommées, les stocks des ressources et les bénéces des produits sont réca-
pitulés dans le tableau suivant :

Produit 1 Produit 2 Produit 3 Produit 4 Stocks

Ressource A 2 4 5 7 42
Ressource B 1 1 2 2 17
Ressource C 1 2 3 3 24
Bénéce 7 9 18 17

1.3.2 Problème de transport

Une entreprise de construction d'automobiles possède trois usines situées
respectivement à Paris, Strasbourg et Lyon. Un certain métal nécessaire à la
construction des véhicules est disponible aux ports de Havre et de Marseille.
Les quantités de ce métal nécessaires aux usines sont 400,300 et 200 tonnes
respectivement pour les usines de Paris, Strasbourg et Lyon chaque semaine,
tandis que les quantités disponibles sont 550 et 350 tonnes par semaines
respectivement à Marseille et au Havre. Les coûts de transport sont supposés
varier proportionnelllement aux quantités transportées, les coûts unitaires
étant :
Paris Strasbourg Lyon
Marseille 5 6 3
Le Havre 3 5 4

Ce tableau signie que pour convoyer x tonnes de Marseille à Strasbourg,

par exemple, il en coûte 6x francs. Le problème consiste à déterminer un
plan de transport optimal, c'est-à- dire à trouver quels sont les poids de
métal à envoyer depuit chaque port à chaque usine de sorte que :
(i) Les demandes soient satisfaites (chaque usine reçoit au moins la quan-
tité de métal qui lui est nécessaire).
(ii) Les quantités demandées à chaque port n'excèdent pas les quantités
disponibles.
(iii) Les quantités envoyées sont positives ou nulles.
(iv) Le coût total du transport est rendu minimum compte tenu des
contraintes ci-dessus.

5
Chapitre 2

Usage des graphes

2.1 Quelques notions de base de la théorie des graphes

Dénition 2.1.1 Un graphe ( on dit aussi graphe simple ) est un couple
G := (V, E) dans lequel E est une partie de l'ensemble [V ]2 formé des paires
{x, y} d'éléments distincts de l'ensemble V . On convient de désigner par
V (G) l'ensemble V , par E(G) l'ensemble E . Les éléments de V sont appelés
sommets et ceux de E arêtes. On convient que si G est un graphe, son
complément G est le graphe obtenu en prenant E(G) := [V ]2 \ E(G).

Exemple 2.1.1 .

a b a b

f c f c

d d

le cycle C5 l'étoile C5

Figure 2.1  Le cycle C5 et son complément

6
Dénition 2.1.2 Un graphe dirigé (digraphe ) est un couple G := (V, R),
formé d'un ensemble V et d'une relation binaire R sur V . Les éléments de V
sont les sommets de G ; les couples (x, y) appartenant à R sont les arcs de G ;
les couples (x, x) appartenant à R sont les boucles de G. Le graphe dirigé G
étant donné, on note V (G) l'ensemble de ses sommets, E(G) l'ensemble de
ses arcs et, si besoin, on note xRG y le fait que (x, y) ∈ E(G). Sauf indication
contraire, on notera x ∈ G pour x ∈ V (G) et on conviendra que la cardinalité
de G est celle de V (G).
On note par G−1 le digraphe obtenu de G en inversant les sens des arcs, i.e.,
E(G−1 ) = {(x, y) : (y, x) ∈ E(G)}.
On note par G
e le graphe obtenu de G en supprimant les orientations des
arcs, i.e., [
−1
E(G)
e = E(G) E(G ).
Le graphe symétrique G e (i.e., (x, y) ∈ G
e ⇒ (y, x) ∈ G e , pour tous x, y ∈
V (G)) est le symétrisé du graphe G. On dit que G = (V ′ , E ′ ) est un sous
e ′

graphe de G si V ′ ⊆ V (G) et E ′ ⊆ E(G).

Soit ∆ = {(x, x) : x ∈ V (G)}. On dit que
 G est réexif si ∆ ⊆ E(G), autrement dit en tout sommet de G il y'a
une boucle, i.e., un arc de la forme (x, x) ou ce qui revient à dire que
la relation binaire R est réexive ;
 G est transitif si R est transitive, i.e., pour tous x, y, z ∈ V (G), si
(x, y) ∈ E(G) et (y, z) ∈ E(G), alors (x, z) ∈ E(G).
Dénition 2.1.3 Soient x et y deux sommets d'un graphe G. Un chemin
de longueur n ∈ N∗ dans G allant de x à y est une suite {xi }ni=0 de n + 1
sommets de G telle que
x0 = x, xn = y et (xi−1 , xi ) ∈ E(G) pour i = 1, ..., n.
Si x = y , la suite {xi }ni=0 est dite cycle de longueur n. On convient que les
cycles de longueur 0 sont les boucles.
Un digraphe est dit acyclique s'il ne contient aucun cycle de longueur
supérieure ou égale à 1. Un graphe orienté est un digraphe où chaque paire
de sommets est liée par au plus un arc. On peut voir le graphe orienté comme
une relation binaire antisymétrique.
Tout digraphe acyclique est un graphe orienté.
Exemple 2.1.2 Deux orientations de C4

Remarque 2.1.1 Soit  ⪯  est un ordre partiel sur un ensemble non vide
V, alors le graphe G⪯ déni sur V par

E(G⪯ ) = {(x, y) ∈ V 2 : x ⪯ y}
est un graphe orienté réexif.

7
 G1 G2

Figure 2.2  G1 : Graphe orienté acyclique, G2 : Graphe orienté non acy-

clique

Dénition 2.1.4 Un graphe simple G est dit complet si entre deux sommets
quelconques il existe une arête. Un graphe complet de n sommets est noté
Kn .

Figure 2.3  K6

Dénition 2.1.5 Un digraphe est complet si chaque paire de sommets est

liée par un arc. Un graphe G = (V, E) orienté complet est appelé tournoi.
On note par Tn un tournoi de n sommets.

Dénition 2.1.6 Soit G un digraphe. G est dit fortement connexe si pour

tous x, y ∈ V (G) il existe un chemin dans G allant de x à y et il est dit
faiblement connexe si Ge est connexe.

8
 Figure 2.4  T4

Figure 2.5  Exemple d'un digraphe qui n'est pas connexe mais faiblement
connexe

2.2 Quelques problèmes de la R.O utilisant les graphes

2.2.1 Planning d'examen
Les cinq étudiants : Ahmed, Bilal, Morad, Omar et Samir doivent passer
certaines épreuves parmi les suivantes : Français, Anglais, Dessin, Couture,
Mécanique et Solfège. L'examen se déroulant par écrit, on désire que tous
les étudiants qui doivent subir une même épreuve le fassent simultanément.
Chaque étudiant ne peut se présenter qu'à une épreuve au plus chaque jour.
Voici la liste des épreuves que doit passer chaque étudiant :

9
 S

A D

F M C

Figure 2.6  Graphe G = (X, V ) où X = {F, A, D, C, M, S} et une arête

de V relie deux sommets ssi un même étudiant doit subir les épreuves cor-
respondantes

Ahmed Français, Anglais, Mécanique

Bilal Dessin, Couture
Morad Anglais, Solfège
Omar Dessin, Couture, Mécanique
Samir Dessin, Solfège
1. Quel est le nombre maximal d'épreuves que l'on peut organiser le
même jour ?
2. Quel est le nombre de jours nécessaires à l'organisation de toutes les
épreuves ?
Pour répondre à ces questions, on cherchera des nombres particuliers
associés à un graphe qu l'on construira
1. Le nombre maximal d'épreuves que l'on peut organiser le même jour
est le nombre de stabilité du graphe G : α(G) = 3, correspondant à
l'ensemble stable {F, S, C}.
2. Le nombre minimal de jours nécessaires est le nombre chromatique
de G : χ(G) = 3
Exemple d'un planing d'examen
Premier jour Français, Couture, Solfège
Deuxième Anglais, Dessin
Troisième jour Mécanique

10
2.2.2 Inéquations et Graphes
Considérons le système d'inéquations suivant :

x1 + x2 ≤ 1
x1 + x3 + x4 ≤ 1
x4 + x5 ≤ 1

Déterminer une solution de ce système qui maximise la fonction :

z = x1 + x2 + x3 + x4 + x5

Ce problème revient à chercher un ensemble particulier de sommets d'un

graphe :

1 4

2 4 5

Figure 2.7  Graphe G déni comme suit : à chaque variable xi correspond

un sommet i de G. Une arête relie deux sommets i et j ssi les deux variables
xi et xj appartiennent à une même inéquation.

Chercher une solution maximisant z revient à chercher un ensemble stable

SM de G de cardinal maximal. Visuellement, on trouve SM = {2, 3, 5}, soit :

x2 = x3 = x5 = 1 x1 = x4 = 0 z = 3

11
Chapitre 3

Programmation linéaire

Le terme programmation linéaire a été introduit, en même temps que la

méthode du simplexe, par G.B. Dantzig au lendemain de la seconde guerre
mondiale. Le grand retentissement de cette nouvelle théorie a conduit les
auteurs qui, dans les années 1945-1955, se sont intéressés à diérents pro-
blèmes d'optimisation, à utiliser le terme programmation accompagné d'un
adjectif (plus ou moins bien choisi) pour désigner ces problèmes (programma-
tion convexe, dynamique...). Ceci a eu pour eet de donner au terme pro-
gramme le sens de problème d'optimisation, l'étude des problèmes d'op-
timisation généraux étant intitulée  programmation mathématique . On
ne pouvait pas dire  programmation  tout court puisque, plus ou moins
simultanément, le terme programme avait pris, dans le contexte de la science
des ordinateurs, le sens de séquence d'instructions.
La programmation linéaire est une branche des mathématiques appli-
quées, plus précisément de l'optimisation dont l'objectif est de minimiser
ou maximiser une fonction numérique multilinéaire(dite fonction-objectif ou
fonction économique) à plusieurs variables, sachant que ces dernières sont
liées moyennant des équations ou des inéquations linéaires dites contraintes.
Il s'agit de la technique la plus célèbre de la RO, celle qui a donné à cette dis-
cipline se respectabilité scientique. Ceci est certainement dû au fait que de
nombreux problèmes concrets provenant de domaines aussi divers que l'in-
dustrie lourde, le ranage, les transports, l'agriculture, la gestion...peuvent
être modélisés comme des programmes linéaires, la résolution de ces modèles
ayant permis l'obtention de gains substantiels. Les méthodes suivantes sont
les plus utilisées :
 Méthode graphique
 Méthode algébrique
 Méthodes des simplexes
 Fonction Solveur

12
3.0.1 Notions de base
Dénition 3.0.1 Un programme linéaire est un problème dans lequel les
variables sont des réels qui doivent satisfaire un ensemble d'équations et/ ou
d'inéquations linéaires (dites contraintes) et la valeur d'une fonction linéaire
de ces variables (appelée fonction objective ou fonction économique) doit
être rendue minimum (ou maximum).
Ingrédients principaux :
 Alternatives (variables, inconnues du problème).
 Restrictions (contraintes).
 Fonction objectif à optimiser (minimiser ou maximiser).
Forme générale d'un programme linéaire :

 n
Maximiser ou Minimiser
P


 z(x 1 , x2 , ..., x n ) = cj xj
j=1


n

 
 P
a1i xi ≤, =, ≥ b1

 


 
i=1
 

n

 

  P
 

 a2i xi ≤, =, ≥ b2
 i=1

Sous les contraintes ......................




......................

 


 
n
 

  P
 i=1 ami xi ≤, =, ≥ bm

 


 

 

x1 , x2 , ..., xn ≥ 0
 

Forme canonique d'un PL :

Traditionnellement, on présente un programme linéaire sous la forme
canonique suivante :
 [M ax] z = cT x


(P C) Ax ≤ b
x≥0


Remarque 3.0.1 Deux propriétés caractérisent la forme canonique.

• Toutes les variables sont astreintes à être positives ou nulles.
• Toutes les contraintes sont des inéquations.

Remarque 3.0.2 Les contraintes x ≥ 0 dans (PC) auraient pu être incluses

dans l'ensemble des contraintes Ax ≤ b, il aurait su de dénir A′ comme
la (m + n) × n-matrice obtenue à partir de A de la manière suivante :

 
′ A
A =
−In

13
et b′ aurait été le (m + n)−vecteur obtenu à partir de b en lui adjoignant n
composantes nulles et (PC) se serait écrit :

[M ax] z = cT x

(P C)
A′ x ≤ b′

Forme standard d'un PL :

Un programme linéaire est dit standard s'il est écrit sous la forme sui-
vante :
T

 [M ax] z = c x
(P C) Ax = b
x≥0


Remarque 3.0.3 Deux propriétés caractérisent la forme canonique.

• Toutes les variables sont astreintes à être positives ou nulles.
• Toutes les autres contraintes sont des équations.

Théorème 1 Tout programme linéaire sous forme standard peut être écrit
sous forme canonique et tout programme linéaire sous forme canonique peut
être écrit sous forme standard.

Dénition 3.0.2 (Solution admissible). Une solution admissible est un en-

semble de valeurs données aux variables qui satisfait toutes les contraintes.

Dénition 3.0.3 (Solution optimale). Une solution optimale est une solu-
tion admissible qui optimise la fonction objectif.

3.1 Quelques exemples de programmes linéaires

3.1.1 Problème de production résolu par la méthode gra-
phique
Une usine fabrique deux produit P1 et P2 . Chacun de ces produits de-
mande pour son usinage, des heures de fabrications unitaires sur les machines
A, B, C, D, E comme indiqué dans le tableau suivant :
A B C D E
P1 0 1,5 2 3 3
P2 3 4 3 2 0
Disponiblité de chaque machine 39h 60h 57h 70h 57h
Les marges brutes de chaque produit sont respactivement :
M1 = 1700euros
M2 = 3200euros

Ecrire le programme linéaire correspondant et donner une solution graphique.

14
1. Formalisation du Problème
Variables : X1 quantité à fabriquer de P1 et x2 quantité à fabriquer
de P2
L'objectif :
Maximiser z = 1700x1 + 3200x2
sous les contraintes suivantes

3x2 ≤ 39
1, 5x1 + 4x2 ≤ 60
2x1 + 3x2 ≤ 57
3x1 + 2x2 ≤ 70
3x1 ≤ 57
x1 ≥ 0, x2 ≥ 0

2. Résolution du problème par la méthode graphique

15
 A B

C
10

F E

10 20

L'optimum se trouve au point E de cordonnées :

X1 = 96
7 et x2 = 7 .
69

Donc
38400
zmax = .
7

3.1.2 Formulation du problème de transport

Reprenons le tableau des contraintes du problème de transport 3.1.2
Paris Strasbourg Lyon
Marseille 5 6 3
Le Havre 3 5 4

Aectant au port de Marseille l'indice 1, au port du Havre l'indice 2 et aux

trois usines les indices 1,2 et 3 respectivement pour Paris, Strasbourg et
Lyon, on conviendra que xij représentera le nombre de tonnes de métal qui

16
sont acheminées chaque semaine depuis le port d'indice i vers l'usine d'indice
j . Le programme linéaire s'écrit alors :


 [M in]z = 5x11 + 6x12 + 3x13 + 3x21 + 5x22 + 4x23



 x11 + x21 ≥ 400
 x12 + x22 ≥ 300


x13 + x23 ≥ 200
x11 + x12 + x13 ≤ 550




 x21 + x22 + x23 ≤ 350



x11 , x12 , x13 , x21 , x22 , x23 ≥ 0


3.1.3 Algorithme des simplexes

Considérons le programme linéaire suivant qui est sous forme canonique :


 [M ax]z = 30x + 50y
 3x + 2y ≤ 1800


x ≤ 400
y ≤ 600




x ≥ 0, y ≥ 0


 1re étape : Écrire le système sous forme standard



 [M ax]z = 30x + 50y
 3x + 2y + e1 = 1800


x + e2 = 400
y + e3 = 600




x ≥ 0, y ≥ 0, e1 ≥ 0, e2 ≥ 0, e3 ≥ 0


 2me étape : Construire le premier tableau correspondant à la

forme standard
x y e1 e2 e3
e1 3 2 1 0 0 1800
e2 1 0 0 1 0 400
e3 0 1 0 0 1 600
z 30 50 0 0 0 0
 3me étape : Choisir la variable à introduire dans la base
Le coecient le plus grand dans la fonction économique est 50, donc
il s'agit de la variable y qui entre à la base.
x y e1 e2 e3
e1 3 2 1 0 0 1800
e2 1 0 0 1 0 400
e3 0 1 0 0 1 600
z 30 50 0 0 0 0

17
 4me étape : Choisir la variable à enlever de la base
x y e1 e2 e3
e1 3 2 1 0 0 1800 1800
2 = 900
e2 1 0 0 1 0 400 400
0 =∞
e3 0 1 0 0 1 600 600
1 = 600
z 30 50 0 0 0 0
 5me étape : Encadrer le pivot
x y e1 e2 e3
e1 3 2 1 0 0 1800
e2 1 0 0 1 0 400
y 0 1 0 0 1 600
z 30 50 0 0 0 0
 6me étape : Diviser la ligne du pivot par le pivot
x y e1 e2 e3
e1
e2
y 0 1 0 0 1 600
z

 7me étape : Remplir les autres lignes : L′i = Li − aip × L′p

x y e1 e2 e3
e1 3 0 1 0 -2 600
e2 1 0 0 1 0 400
y 0 1 0 0 1 600
z 30 0 0 0 −50 −30000

 8me étape : Test d'arrêt

Les coecients de la fonction économique z sont-ils tous nuls
ou négatifs ? Si oui nous sommes à l'optimum, sinon nous ef-
fectuons un nouveau passage. On voit que 30 est le seul coecient
positif au sens strict. Il convient d'eectuer un nouveau passage : La
variable x est la variable entrante à la base

x y e1 e2 e3
e1 3 0 1 0 -2 600 600
3 = 200
e2 1 0 0 1 0 400 400
1 = 400
y 0 1 0 0 1 600 600
0 =∞
z 30 0 0 0 -50 −30000

18
 Donc e1 est la variable sortante de la base.

x y e1 e2 e3
x 1 0 1
3 0 −2
3 200
e2 0 0 − 31 1 2
3 200
y 0 1 0 0 1 600
z 0 0 -10 0 -30 −36000
Les coecients de la fonction économique sont tous nuls ou négatifs,
n de l'algorithme du simplexe.
La solution qui rend optimal le programme de production est le suivant :
La marge sur coût variable maximum= 36000, elle est réalisée pour la
solution x = 200 et y = 600.
Exemple 3.1.1 Appliquer cette méthode pour résoudre le problème de pro-
duction (Paragraphe3.1.1).

3.1.4 Fonction Solveur

Le solveur d'EXCEL est un outil puissante d'optimisation et d'allocation
de ressources. Il peut vous aider à déterminer comment utiliser au mieux des
ressources limitées pour maximiser les objectifs souhaités (telle la réalisation
des bénéces) et minimiser une perte donnée (tel un coûtde production). En
résumé, il permet de trouver le minimum, le maximum ou la valeur au plus
près d'une donnée tout en respectant les contraintes qu'on lui soumet. Plutôt
que de vous contenter d'approximations, vous pouvez faire appel au solveur
pour trouver la meilleure solution.
Quand utiliser le solveur ?
Utiliser le solveur lorsque vous recherchez la valeur optimale d'une cellule donnée
(la fonction économique) par ajustement des valeurs de plusieurs autres cellules
(les variables) respectant des conditions limitées supérieurement ou inférieurement
par des valeurs numériques (c'est à dire les contraintes).
L'étape à suivre sont explicitées dans le chapitre 6 pour la résolution du
programme suivant :


 [M ax]z = 10x1 + 15x2 + 25x3
 x1 + 2x2 + 4x3 ≤ 20000


x1 + x2 + 3x3 ≤ 16000
 3x1 + 5x2 + 3x3 ≤ 48000



xi ≥ 0


19
3.1.5 La dualité
Programme dual d'un PL sous forme standard
Un programme linéaire est caractérisé par le tableau simplexe suivant :
 
A b
c

Par dénition, le problème dual est obtenu en transposant ce tableau :

 T
cT

A
bT

Soit v ∈ Rn le vecteur colonne des variables du problème dual ou u ∈ Rn le

vecteur ligne des variables du problème dual. Sachant que u = v T , on a le
modèle suivant :

 [M ax]w = bT v
  
 [M in]z = cx  [M ax]w = ub
(P ) : sc Ax ≥ b ⇐⇒ (D) : sc uA ≤ c ⇐⇒ (D) : sc AT v ≤ cT
x≥0 u≤0 v≤0
  

Règles de passage :
Min Max
Primal Dual
Dual Primal
Variable ≥ 0 Contrainte ≤
Variable ≤ 0 Contrainte ≥
Variable ≶ 0 Contrainte =
Contrainte ≤ Variable ≤ 0
Contrainte = Variable ≶ 0
Contrainte ≥ Variable ≥ 0

Exemple 3.1.2 Donner le proramme dual du programme primal suivant :



 [M ax]z
 = 4x1 + 5x2 + 2x3



 
 2x1 + 4x2 = 3
x1 + x3 ≥ 2
 
(P ) : sc

 
 3x1 + x2 + x3 ≤ 10
x2 + x3 ≤ 1

 


x1 ≥ 0, x2 ≤ 0, x3 ≥ 0


20
Théorèmes de la dualité
1. Le dual du dual est le primal.
2. Si x et u sont respectivement des solutions du primal et du dual,
alors :
z = cx ≥ w = ub

Interprétation :
une solution primale (resp. duale) admissible sous-optimale est meilleure
qu'optimale, mais non admissible pour le problème dual (resp. pri-
mal).
3. Si (P) et (D) ont des solutions, alors chacun d'entre eux a une solution
optimale et
z ∗ = M in cx = w∗ = M ax ub
Réciproquement, si x est admissible pour (P) et y est admissible pour
(D) et que cx = ub, alors x est optimale pour (P) et u est optimale
pour (D).

3.2 Exercices d'application

Exercice 3.2.1 Un pays désire accroître son potentiel d'armement ; il veut
acquérir au moins 100 000 fusils, 200 000 grenades défensives et oensives,
une centaine de chars, 400 mitrailleuses lourdes et autant de bazookas. Il
s'adresse pour ce faire à des marchands d'armes qui récupèrent les matériels
utilisés ou non sur tous les champs de bataille. Ces marchands proposent
trois types de lots :

Lot 1 Lot 2 Lot 3

Fusils 500 300 800
Grenades 1000 2000 1500
Chars 10 20 15
Mitrailleuses 100 80 150
Bazookas 80 120 200
Cpûts des lots 10 MF 12 MF 15 MF

Le pays en question va donc essayer de minimiser le coût de l'armement

supplémentaire qu'il va acheter.

1. Ecrire le programme sous forme d'un programme linéaire.

2. Ecrire le programme dual correspondant.

3. quelle est l'interprétation économique du dual ?

4. déterminer le coût minimal de l'armement supplémentaire de ce pays.

21
Corrigé :
1. Le programme linéaire s'écrit :


 [M in]z
 = 10x1 + 12x2 + 15x3



 
 500x1 + 300x2 + 800x3 ≥ 100000
 1000x1 + 2000x2 + 1500x3 ≥ 200000

 


(P L) : sc 10x1 + 20x2 + 15x3 ≥ 100
100x 1 + 80x2 + 150x3 ≥ 400

 


 

80x 1 + 120x2 + 200x3 ≥ 400

 


x1 ≥ 0, x2 ≥ 0, x3 ≥ 0


Il exprime le point de vue de l'acheteur qui tente de minimiser le coût de son

armement. Dans ce programme linéaire, x1 0, x2 , x3 représentent, respective-
ment, le nombre de lots de type 1,2,3 qu'il faut acheter.
2. Le programme dual s'écrit :


 [M ax]v
 = 100000y1 + 200000y2 + 100y3 + 400y4 + 400y5
 500y1 + 1000y2 + 10y3 + 100y4 + 80y5 ≤ 10



(P L∗) : sc 300y1 + 2000y2 + 20y3 + 80y4 + 120y5 ≤ 12
800y1 + 1500y2 + 15y3 + 150y4 + 200y5 ≤ 15

 


y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0, y5 ≥ 0.


3. Le programme dual peut être interprété comme suit :

Un fabricant d'armements qui produit ces diérents types d'armes à la
demande veut s'emparer du marché. Soient
y1 le prix de vente d'un fusil ;
y2 le prix de vente d'une grenade ;
y3 le prix de vente d'un char ;
y4 le prix de vente d'une mitrailleuse ;
y5 le prix de vente d'un bazooka.
Un lot de type 1 coûtera : 500y1 + 1000y2 + 10y3 + 100y4 + 80y5 = γ1 .
Un lot de type 2 coûtera : 300y1 + 2000y2 + 20y3 + 80y4 + 120y5 = γ2 .
Un lot de type 3 coûtera :800y1 + 1500y2 + 15y3 + 150y4 + 200y5 = γ3 .
Le marché rapportera globalement :

100000y1 + 200000y2 + 100y3 + 400y4 + 400y5 .

Pour remporter le marché, le fabricant d'armements doit calculer ses prix de

vente unitaires de façon à concurrencer le marchand d'armes ( c'est-à-dire
γ1 ≤ 10, γ2 ≤ 12, γ3 ≤ 15) tout en faisant un bénice maximal.

4. Résolvons le programme (PL*) par la méthode des simplexes :

22
 y1 y2 y3 y4 y5 e1 e2 e3 b
e1 500 1000 10 100 80 1 0 0 10
e2 300 2000 20 80 120 0 1 0 12
e3 800 1500 15 150 200 0 0 1 15
v 100000 200000 100 400 400 0 0 0 0
e1 350 0 0 60 20 1 -0.5 0 4
y2 0.15 1 0.01 0.04 0.06 0 0.0005 0 0.006
e3 575 0 0 90 110 0 -0.75 1 6
v 70000 0 -1900 -7600 -11600 0 -100 0 -1200
e1 0 0 0 5.21739 -46.956521 1 -0.043478 -0.60869 0.34782
y2 0 1 0.01 0.01652 0.031304 0 0.00069 -0.000260 0.004
y1 1 0 0 0.15652 0.191304 0 -0.00130 0.00173 0.010434
v 0 0 -1900 -18556.521 -24991.304 0 -8.69565 -121.73913 -1930.434
Le bénice maximal est v = 1930.434. Il est atteint pour
max

y1 = 0.010434, y2 = 0.004, y3 = 0, y4 = 0, y5 = 0.

Donc le coût minimal d'armement est z min = 1930.434 . Il est atteint pour
x1 = 0, x2 = 8.69565, x3 = 121.73913.

Ceci par transpositition et en appliquant la transformation :

y 7→ e et e 7→ x où e sont les variables articielles du (PL).
i
′
i i i
′
i

Exercice 3.2.2 Soit le programme liniéaire :



 [M in]z
 = 2x1 + x2 + 35x3
4x1 − 2x2 − 6x3 ≥ 1

(P L) : sc

 −3x1 + x2 + 14x3 ≥ 2
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0


1. Donner le programme dual (PL*) de (PL).

2. Résoudre (PL*) à l'aide de la méthode des tableaux des simplexes.
3. En déduire le tableau optimal de (PL).

23
Chapitre 4

Algorithmes de recherche d'un

chemin optimal

4.1 Introduction
Supposons que, dans un graphe orienté, on décide d'attribuer à chaque arc une
longueur, positive ou non. Il est alors naturel de dénir la longueur d'un chemin
quelconque comme la somme des longueurs des arcs qui le composent. Un problème
fondamental, et qui se pose fréquemment dans les applications, est celui de la re-
cherche des chemins de longueur minimale ou maximale. L'objet de ce chapitre est
de présenter trois algorithmes simples permettant d'obtenir de tels chemins. Ces
algorithmes seront aussi utilisés dans la suite pour la recherche de ots et d'ordon-
nancements optimaux.
4.2 Formulation du problème
Soit G = (V, E) un 1-graphe orienté, sans boucle, comportant n sommets. A
tout arc (x , x ) ∈ E est associé un nombre réel l appelé longueur de l'arc (x , x ).
La longueur d'un chemin µ est la somme des longueurs des arcs qui le composent :
i j ij i j

X
l(µ) = lij
(xi ,xj )∈µ

Un chemin joignant un sommet x à un sommet x est dit de longueur minimale

ou maximale s'il minimise ou maximise cette longueur l(µ) dans l'ensemble de tous
s t

les chemins µ joignant x à x . La longueur d'un tel chemin est appelée distance
(minimale) ou distance maximale selon le cas. Par abus de language, et bien que
s t

l'unicité ne soit pas nécessairement réalisée, on parle parfois du plus court chemin
ou du plus long chemin de x à x .
s t

Nous présentons ci-dessous trois algorithmes permettant d'obtenir les chemins

de longueurs minimale ou maximale. Une renumération des sommets étant toujours
possible, nous ne considérons que des chemins de x à x . Les hypthèses faites sur
les signes des longueurs l varient selon l'algorithme proposé. Pour que le problème
1 n

admette une solution de longueur nie, nous supposerons que le graphe étudié
ij

24
ne comporte aucun circuit de longueur négative dans le cas de la recherche d'un
chemin de longueur minmale, ni aucun circuit de longueur positive dans le cas de
la recherche d'un chemin de longueur maximale.
Il sera commode d'introduire une matrice L, dite matrice de longueurs, dont
l'élément l se dénit de façon diérente selon le problème considéré :
ij

Problème du court chemin Problème du long chemin

si (x , x ) ∈ E , si (x , x ) ∈ E ,
 

/ E, / E,
 l ij i j  l ij i j
+∞ si (x , x ) ∈ −∞ si (x , x ) ∈
si i = j . si i = j .
ijl = i j l = ij i j
0 0
 

4.3 Algorithmes de résolution

4.3.1 Algorithme de Ford
Il permet l'obtention de chemins de longueur minimale ou maximale, quels que
soient les signes des longueurs l .
ij

Son principe :
On marque tout sommet x d'une marque λ qui correspond à une borne su-
périeure (inférieure) pour la distance minimale (maximale) de x à x . On diminue
j j

(augmente) progressivement ces marques, à raison d'une par étape, et en suivant

1 j

la procédure décrite dans l'organigramme ci-dessous. Lorsqu'une telle diminution

(augmentation) n'est plus possible, la marque λ est la distance minimale (maxi-
male) de x à x . Un chemin optimal de longueur minimale (maximale) peut être
j

construit, à partir des distances λ ainsi obtenues, par application de l'algorithme

1 j

d'identication décrit en 4.3.2.

j

L'organigramme ci-dessous présente simultanément les algorithmes de recherche

de chemins de longueur minimale et maximale. Lorsque les instructions relatives à
ces deux algorithmes sont distincts, ce qui se rapporte au chemin le plus court est
indiqué à gauche, ce qui se rapporte au chemin le plus long, à droite.

25
 λ1 = 0

λj = +∞, j ̸= 1 λj = −∞, j ̸= 1

Marquer xj de
λj = λi + lij

∃(xi , xj ) ∈ E
Oui tel que
λj > λi + lij λj < λi + lij

Non

Stop- Identication du chemin cherché

L'inconvénient de cet algorithme est sa très médiocre ecacité. Si le sommet

marqué à chaque étape est choisi au hasard, le nombre d'itérations peut être fort
élevé. Les algorithmes de Bellman-Ford et de Dijkstra sont, en moyenne, beaucoup
plus rapides.
4.3.2 L'algorithme d'identication d'un chemin optimal
L'identication d'un chemin de longueur minimale (de longueur maximale) se
fait à partir des distances minimales (maximales) de x aux autres sommets x .
Les distances correspondent aux marques λ obtenues en n d'application des al-
1 j

gorithmes de Ford, Bellman-Ford ou Dijkstra.

j

Son principe et son organigramme :

Les chemins recherchés se reconstituent, à reculons, à partir de x , par juxta-
position d'arcs (x , x ) tels que λ = λ − l .
n
j k j k kj

26
 Obtention des
marques λj

xk = xn
µ = (xn )

Rechercher xj tel que

λj = λk − lkj
Poser xk = xj

µ = (xk , µ) Stop, µ est l'un des

chemins recherchés

xk = x1
Non Oui

Remarque 4.3.1 Rappelons que le chemin recherché (de longueur minimale ou de

longueur maximale) n'est pas nécessairement unique !

4.3.3 Algorithme de Bellman-Ford pour la recherche du plus

court chemin
cet algorithme se compose de quatre blocks.
Déclaration des variables :

Graphe=(S,A)
appartient à R (≤ 0 ou ≥ 0)



s'il n'y a pas d'arc entre x et y

 lij


lxy = ∞
Bellman-Ford (G, l, s)
graphe, l = l , s =point initial




G=

ij

Initialisation

 λ(s) ←− 0
Pour chaque v ∈ S sauf(s)

Faire λ(v) ←− ∞
27
Relaxation

Pour i ←− 1 à |S|-1
Faire, pour chaque arc (u, v) ∈ A



Faire : Si λ(v) > λ(u) + l






uv
λ(v) ←− λ(u) + l
Fin

 uv

Fin






Contrôle de la présence d'une boucle négative


Pour chaque arc (u, v) ∈ A
Faire : Si λ(v) > λ(u) + l



Alors, l'existence d'une boucle négative


uv

Sinon, retour à d(v)





Exemple 4.3.1 Considérons le graphe suivant : Il nous faut 5 itération pour déter-

-2
B D
2
3 3

A 9 3 F
-5
2

4 1

C E

miner un chemin de longueur minimale. A chaque itération, on utilise la notation

XY (λi (Y ), λi (X) + lXY ).

Première itération :

 AB(∞, 0 + 3) −→ λ(B) = 3
AC(∞, 0 + 4) −→ λ(C) = 4
λ(x) = ∞, pour tout x ∈
/ {A, B, C}


Deuxième itération :

 AB(3, 0 + 3) −→ λ(B) = 3 BD(∞, 3 + 2) −→ λ(D) = 4
AC(4, 0 + 4) −→ λ(C) = 4 BE(∞, 3 + 2) −→ λ(E) = 5
BC(4, 3 + 9) −→ λ(C) = 4 CD(∞, 4 − 5) −→ λ(D) = −1


Donc
λ(A) = 0, λ(B) = 3, λ(C) = 4, λ(D) = −1, λ(E) = 5, λ(F ) = ∞.

28
 Troisième itération :


 AB(3, 0 + 3) −→ λ(B) = 3 BD(−1, 3 + 2) −→ λ(D) = −1
 DB(3, −1 − 2) −→ λ(B) = −3 CD(−1, 4 − 5) −→ λ(D) = −1


AC(4, 0 + 4) −→ λ(C) = 4 ED(−1, 5 + 3) −→ λ(D) = −1
BC(4, 3 + 9) −→ λ(C) = 4 BE(5, 3 + 2) −→ λ(E) = 5




DF (∞, −1 + 3) −→ λ(F ) = 2 EF (∞, 5 + 1) −→ λ(F ) = 5


Donc
λ(A) = 0, λ(B) = −3, λ(C) = 4, λ(D) = −1, λ(E) = 5, λ(F ) = 2.
Quatrième itération :


 AB(3, 0 + 3) −→ λ(B) = 3 BD(−1, 3 + 2) −→ λ(D) = −1
 DB(3, −1 − 2) −→ λ(B) = −3 CD(−1, 4 − 5) −→ λ(D) = −1


AC(4, 0 + 4) −→ λ(C) = 4 ED(−1, 5 + 3) −→ λ(D) = −1
BC(4, 3 + 9) −→ λ(C) = 4 BE(5, −3 + 2) −→ λ(E) = −1




DF (∞, −1 + 3) −→ λ(F ) = 2 EF (2, 5 + 1) −→ λ(F ) = 2


Donc
λ(A) = 0, λ(B) = −3, λ(C) = 4, λ(D) = −1, λ(E) = −1, λ(F ) = 2.
Cinquième itération :


 AB(3, 0 + 3) −→ λ(B) = 3 BD(−1, 3 + 2) −→ λ(D) = −1
 DB(3, −1 − 2) −→ λ(B) = −3 CD(−1, 4 − 5) −→ λ(D) = −1


AC(4, 0 + 4) −→ λ(C) = 4 ED(−1, 5 + 3) −→ λ(D) = −1
BC(4, 3 + 9) −→ λ(C) = 4 BE(5, −3 + 2) −→ λ(E) = −1




DF (∞, −1 + 3) −→ λ(F ) = 2 EF (2, −1 + 1) −→ λ(F ) = 0


Donc
λ(A) = 0, λ(B) = −3, λ(C) = 4, λ(D) = −1, λ(E) = −1, λ(F ) = 0.
Nous pouvons résumer les résultats des cinq itération dans le tableau ci-dessous :
A B C D E F
Initialisation 0 ∞ ∞ ∞ ∞ ∞
1ère Itération 0 3-A 4-A ∞ ∞ ∞ A
2ème Itération 0 3-A 4-A -1-C 5-B ∞ C
3ème Itération 0 -3-D 4-A -1-C 5-B 2-D D
4ème Itération 0 -3-D 4-A -1-C -1-B 2-D B
5ème Itération 0 -3-D 4-A -1-C -1-B 0-E E
Contrôle 0 -3-D 4-A -1-C -1-B 0-E F
Remarque 4.3.2 L'étape de contrôle de l'existence d'une boucle négative, est une
sixième itération. Si tous les poids des sommets coïncident avec ceux de la cinquième
itération, on conclut qu'il n'y a pas de boucle négative.
Le chemin optimal est :
A(0) −→ C(4) −→ D(−1) −→ B(−3) −→ E(−1) −→ F (0)
Il est de longueur 0. On a obtenu les sous chemins optimaux, par exemple, le plus
court chemin allant de A à B est de longueur -3 :
A(0) −→ C(4) −→ D(−1) −→ B(−3) →

29
4.3.4 Algorithme de Dijkstra
Cet algorithme permet uniquement l'obtention de chemins de longueur mini-
male, et sous la conditions que les longueurs l soient toutes non négatives. Il
présente de grands avantages de rapidité dans son application.
ij

Son principe :
On considère, au départ de x , les chemins d'un arc (étape 1), puis ceux de deux
arcs au plus (étape 2),...,et ceux de t arcs au plus (étape t). Soit D l'ensemble des
1

sommets marqués à l'étape t − 1. A l'étape t, on considère l'ensemble des sommets

n'appartenant pas à D mais ayant un ascendant direct dans D, et on marque l'un de
ses sommets, soit x , d'une marque dénitive λ qui représente la distance minimale
de x à x . Lorsque le sommet x est marqué, les marques λ obtenues représentent
k k

les distances de x à x nécessaires à l'application de l'algorithme d'identication.

1 k n j
1 j

Exemple 4.3.2 Le graphe suivant représente un réseau de 7 villages A,B,C,D,E,F

et G. Les étiquettes correspondent aux distances en km. A l'aide de l'algorithmes
de Dijkstra, déterminer le plus court chemin entre A et G.

3
B F
1 2 3 4

3
A D G
2
2 3 5
C E
4

A B C D E F G Sommets
0 1-A 2-A ∞ ∞ ∞ ∞ en A
- 1-A 3-B ∞ 4-B ∞ en B
- - 2-A 5-C 6-C ∞ en C
- - - 3-B 6-D 6-D 6-D en D
- - - - 4-B 8-F en F
- - - - 5-D - 10-E en E
- - - - - - 6-D en G
Le chemin le plus court est de longueur 6 km :
A −→ B −→ D −→ G

30
 1 9
D E F

2 8 1
1 2

A B C 2
6 4
8 3
2
7
G H

4.4 Exercices d'application

Exercice 4.4.1 Considérons le graphe suivant :
Appliquer l'algorithme de Bellman-Ford puis l'algorithme de Dijkstra pour dé-
terminer un plus court chemin allant du A à H.

31
Chapitre 5

Problèmes d'ordonnancement

5.1 Introduction
Lobjet d'un problème d'ordonnancement est de faciliter la mise en oeuvre et
de guider l'exécution d'un ensemble complexe de tâches (programme de recherche
ou de production, lancement d'un produit, construction d'un bâtiment ou d'une
route...). La technique d'analyse la plus connue, appelée méthode P.E.R.T. (Pro-
gram Evaluation and Review Technique), a été introduite aux états-unis en 1958
pour la réalisation d'un programme de recherches et de construction des fusées Po-
laris. Cette méthode tient une place dominante par sa simplicité, son ecacité et
la variété des extensions qui ont pu être développées.
Dans ce chapitre, nous illustrons les principales techniques de base lorsque le
critère d'optimalité est la minimisation de la durée ou du coût de la réalisation du
projet. Nous supposons que ce projet est décomposable en un nombre ni de tâches,
caractérisées par leurs durées d'exécution (généralement xes, parfois aléatoires),
éventuellement aussi par leurs coûts d'exécutions, et soumises à des contraintes de
postériorité stricte (une tâche ne peut commencer que si certaines autres tâches
sont complètement terminées).
5.2 Critère temporel
Le problème s'énonce comme suit : étant donné un projet constitué de n tâches
de durées d'exécution xes et soumises à des contraintes de postériorité stricte,
déterminer un "calendrier d'exécution " ou ordonnancement qui minimise la durée
de réalisation totale du projet.
En pratique, le travail préliminaire à accomplir sera donc de dresser une liste
des diérentes opérations à mener qu'on décompose plus ou moins selon la précision
souhaitée. Généralement, les tâches sont dénies de manière simple et telle que leurs
durées d'exécution sont de même ordre de grandeur; de plus, les contraintes de
postériorité entre les tâches doivent pouvoir être établies avec précision. Ce travail
important est souvent long, et nécessite une collaboration étroite entre les diverses
personnes impliquées dans l'exécution du projet.

32
Mise sous forme de graphe
Le problème peut être représenté de deux manières par un graphe G = (X, U )
sans circuit et aux arcs (x , x ) duquel sont associés des quantités non négatives t
i j ij

5.2.1 Méthode du potentiel

Le graphe, appelé graphe-tâches, est construit comme suit :
 Chaque tâche i est représentée par un sommet x ;
 Toute contraintes de postériorité stricte du type "i doit être terminée avant
i

que j ne puisse commencer" se traduit par la présence dans U d'un arc

(x , x ) ;
 La durée de la tâche i est associée à tout arc (x , x ) ∈ U et est alors notée
i j

t ;
i j

 Deux tâches ctives de durée nulle sont introduites : x , qui représente le

ij

"début du projet", et x = x qui représente la "n du projet".

0
n+1 N

5.2.2 Méthode P.E.R.T.

Le graphe, appelé graphe-étapes, est construit comme suit :
 Chaque tâche i donne naissance à un arc (x , x ) ∈ U ;
 Toute contraintes de postériorité stricte du type "i doit être terminée avant
k l

que j ne puisse être commencée" se traduit en confondant l'extrémité ter-

minale de l'arc représentant la tâche i et l'extrémité initiale de l'arc repré-
sentant la tâche j (via, éventuellemnt, un arc ctif comme nous le verrons
ci-dessous);
 La durée de la tâche i est associée à l'arc correspondant (x , x ), et s notée
t ;
k l

 Deux sommets ctifs sont introduits : x , qui représente le "début du pro-

kl

jet", et x qui représente la "n du projet".

0
N

Remarquons que dans cette dernière mise en graphe, les sommets correspondent
au début ou à la n d'une (de plusieurs) tâche(s) ou encore à un instant situé
entre ceux-ci. Il peuvent donc s'interpréter comme des étapes du projet marquant
la réalisation de travaux partiels. Certaines d'entre eux représentent des étapes
importantes (construction d'une partie d'un bâtiment par exemple), mais beaucoup
ne pr ésentent que peu de signiaction pratique.
Soulignons aussi que pour pouvoir exprimer certaines contraintes de postériorité
stricte, il est parfois nécessaire d'introduire des tâches ctives et donc des arcs ctifs
de durées nulles. A titre d'exemple, considérons le sous-graphe partiel ci-dessous :
indiquant que les tâches 3 et 4 doivent succéder aux tâches 1 et 2. Supposons
que suite à une modication des conditions techniques, l'exécution de la tâche 4
puisse commencer avant que soit achevée la tâche 1. Pour adapter le graphe à ce
changement, nous ajoutons un arc ctif de la manière suivante :
5.2.3 Résolution
Nous appelons ordonnancement un programme d'exécution {t : 0 ≤ i ≤ N }
avec t = 0, qui xe la date t de début d'exécution de chacune des tâches (dans la
i

méthode M.P.M) ou début de réalisation de chacune des étapes (dans la méthode

0 i

33
 Tâche 1 Tâche 3

Tâche 2 Tache 4

Tâche 1 Tâche 3

Tâche ctive

Tâche 2 Tâche 4

P.E.R.T). Un ordonnancement est optimal s'il est réalisable , c'est-à-dire si t − t ≥

t , (x , x ) ∈ U , et si de plus il minimise la durée de réalisation t du projet.
j i
ij i j N

Dénissons la longueur d'un arc comme étant la durée associée à cet arc. La
durée minimale du projet est alors égale à la longueur du plus long chemin de
x à x . En eet, pour qu'une tâche puisse commencer, il faut que toutes les
tâches précédentes aient été exécutées, de sorte que la durée du projet ne peut
0 N

être inférieure à la somme des durées des tâches composant le chemin le plus long
de x à x . Ce chemin, qui n'est pas nécessairement unique, est appelé chemin
critique. Pour le déterminer, il sut d'appliquer l'algorithme de Bellman-Ford ou
0 N

l'algorothme de Dijkstra. Comme le graphe est sans circuit, on trouve

t = max{t + t : x ∈ Γ (x )}, 0 ≤ j ≤ N
j i ij i
−
j

où Γ (x ) = {x ∈ X : (x , x ) ∈ U }.
−
j i i j

Chaque t ainsi obtenu est la longueur du chemin le plus long de x à x et

représente la date au plus tôt de début d'exécution de la tâche ou l'étape i.
i 0 i

La durée minimale du projet t ayant été évaluée, il est bien sûr possible de
retarder l'exécution de certaines tâches ou étapes sans pour autant accroître t . Il
N

est dès lors intéressant de déterminer les dates au plus tard T de début d'exécution
N

des diérentes tâches ou étapes i sous la condition que la durée minimale du projet
i

t ne soit pas modiée. Ces dates se calculent au moyen du même algoritme ci-
dessus, mais appliqué au réseau inverse construit en inversant le sens de tous les
N

arcs. Il vient
T = t et T = min{T − t : x ∈ Γ (x )} , 0 ≤ j ≤ N − 1
N N j i ij i
+
j

34
où Γ (x ) = {x ∈ X : (x , x ) ∈ U }.
+
j i j i

Chaque quantité T − T ainsi obtenue est la longueur du chemin le plus long

de x à x .
N i
i N

Pour chacune des tâches ou étapes i composant un chemin critique, on a t = T .

Tout retard dans leur date d'exécution entraîne donc un retard équivalent dans la
i i

durée du projet : elles sont appelées tâches ou étapes critiques. Plus généralement,
à chaque sommet i, on peut associer un intervalle de ottement, (t , T ), qui indique
la latitude laissée dans le choix de l'ordonnancement et permet, éventuellement, de
i i

tenir compte de contraintes additionnelles.

Dans la méthode M.P.M., il peut être intéressant de déterminer le retard qui
peut être apporté dans la mise en oeuvre de chaque tâche I sans que soit pour
autant aectée la durée de réalisation du projet.

ti Ti tij tj Tj

I J

35
 On dénit
 la marge totale M (I) = T − t , longueur de l'intervalle de ottement de la
tâche I ; elle représente le retard maximal que peut prendre la tâche I sans
T j i

altérer les dates des débuts au plus tard des tâches suivantes et parsuite
sans que la durée minimale du projet soit modiée.
 la marge libre M (I) = min{t − t − t } de la tâche I ; elle représente le
L j i ij

retard maximal qui peut être apporté dans la mise à exécution de la tâche
j

I sans altérer les dates des débuts au plus tôt des tâches suivantes.

5.2.4 Algorithme d'obtention d'un ordonnancement de

durée minimale
Déclaration des variables : G = (X, U )
Graphe-tâches (dans la méthode M.P.M)
ou
Graphe-étapes (dans la méthode P.E.R.T).
Initialisation : 
 t0 = 0
ti = t0i : Γ− (xi ) = {x0 }
M = {x0 , xi : Γ− (xi ) = {x0 }}
Relaxation :


Si M ̸= X , 
 j ∈ Choisir un x
/M Γ− (xj ) ⊂ M tel que
M = M ∪ {xj }
Tj = min{ti + tij : xi ∈ Γ− (xj )}
Sinon, i.e. , alors


est la durée minimale de réalisation du projet.

M =X
tN 
 TN = tN
Ti = tN − tiN : Γ+ (xi ) = {xN }
M ∗ = {xN , xi : Γ+ (xi ) = {xN }}
Si


Choisir un tel que

M∗ =
̸ X 
 Sj ∈
x / M∗ Γ+ (xj ) ⊂ M ∗
M ∗ = M ∗ {xj }
Tj = min{Ti − tij : xi ∈ Γ+ (xj )}
Sinon, i.e. , alors


Date de réalisation au plus tôt : ,

 M∗ = X
t i xi ∈ X
Date de réalisation au plus tard : ,


Ti xi ∈ X
Intervalle de ottement : ,

i ∈X
Chemins critiques : chemins de longueur maximale entre x et x

 (ti , Ti ) x

Dans la méthode P.E.R.T. : marges


0 N

 libre : t − t − t , (x , x ) ∈ U
 totale : T − t − t , (x , x ) ∈ U
j i ij i j

 certaine : t − T − t , (x , x ) ∈ U
j i ij i j

Fin si
j i ij i j

Fin si
Fin.
Exemple 5.2.1 Une entreprise s'intéresse à un procédé de construction d'un pro-
duit nouveau. Ce procédé fait intervenir un certain nombre d'opérations. Leur du-

36
rées et les contraintes auxquelles elles sont soumises sont données dans le tableau
suivant :
Tâches Durées Contraintes d'antériorité
A 30 -
B 5 après A
C 12 après A
D 17 après A
E 4 après B et C
F 3 après C
G 14 après E et F
H 8 après D
Déterminer un ordonnancement des tâches qui minimise la durée d'exécution du
procédé de construction.
La méthode française : Méthode du Potentiel Métra (M.P.M)
Le graphe-tâches est le suivant :

5
B E
4
30 12

3 G
0 30 12
début A C F
14
30

8 Fin
17
D H

37
 Par application de l'algorithme précédent, on obtient les dates au plus tôt ti et
au plus tard Ti de début d'exécution des opérations. Les résultats sont données dans
le tableau suivant :
Sommets : xi ti Ti Longueurs des intervalles de ottement : Ti − ti
x0 0 0 0
A 0 0 0
B 30 37 7
C 30 30 0
D 30 35 5
E 42 42 0
F 42 43 1
G 46 46 0
H 47 52 5
xN 60 60 0
Il y'a donc un seul chemin critique :
x0 → A → C → E → G → xN

Rappelons qu'il s'agit du chemin le plus long de x0 à xN et que sa longueur tN =

60 représente la durée minimale d'exécution du procédé. Aux opérations A,C,E,G
composant ce chemin correspondent des intervalles de ottement de longueur nulle :
tout retard dans la réalisation de l'une d'entre elles entraîne un retard équivalent
pour la durée minimale du projet.
La méthode américaine : Méthode P.E.R.T.
La construction du graphe-étapes est plus délicate. Nous présentons ci-dessous
deux mises en graphes possibles du problème dont la seconde, plus compacte, est
préférable.
Première représentation :

38
 début x0

A(30)
x1
B(5)
D(17) C(12)

x4 x3 x2
i(0)
i(0)

H(8) F(3) x5

E(4)

x10 x7 x6
i(0)
i(0)

x8
i(0)
G(14)

x9

i(0)
Fin xN

Deuxième représentation :
Dans les deux cas, nous avons introduit, pour exprimer certaines contraintes de
postériorités strictes, des tâches ctives de durée nulle, notés i et représentées par
des arcs en traits discontinus. Surabondants dans la première gure, leur nombre a
été réduit dans la deuxième gure où, toutefois, un arc ctif (x3 , x2 ) est nécessaire
pour traduire que la tâche C doit être terminée avant que la tâche E ne puisse
commencer.
Par application de l'algorithme précédent, au graphe de la deuxième gure, on
obtient les dates au plus tôt ti et au plus tard Ti de début de réalisation des étapes
ainsi que les diérentes marges des opérations. Les résultats sont données dans les

39
 x2

E(4)
B(5)
i(0)
F(3) x5
A(30) C(12) G(14)
début : x0 x1 x3

Fin :xN
D(17)

H(8)
x4

tableaux suivants :
Sommets : xi ti Ti Longueurs des intervalles de ottement : Ti − ti
x0 0 0 0
x1 30 30 0
x2 42 42 0
x3 42 42 0
x4 47 52 5
x5 46 46 0
xN 60 60 0

Tableau des marges :

Arcs : (xi , xj ) Marge libre Marge totale Marge certaine
(x0 , x1 ) 0 0 0
(x1 , x2 ) 7 7 7
(x1 , x3 ) 0 0 0
(x1 , x4 ) 0 5 0
(x2 , x5 ) 0 0 0
(x3 , x2 ) 0 0 0
(x3 , x5 ) 1 1 1
(x4 , xN ) 5 5 0
(x5 , xN ) 0 0 0
Il y'a un seul chemin critique qui est :
A C E G
x0 −
→ x1 −
→ x3 → x2 −
→ x5 −
→ xN

C'est le chemin le plus long de x0 à xN , et sa longueur tN = 60 représente la

durée minimale d'exécution du procédé. Il se compose, bien sûr, des mêmes tâches
que celui obtenu par la méthode du potentiel. Remarquons qu'il n'est pas possible

40
dans l'exemple de déterminer ce chemin sur base des intervalles de ottement de
longueur nulle ; pour l'obtenir, il sut d'appliquer l'algorithme d'identication du
plus long chemin de x0 à xN ou de repérer les arcs dont toutes les marges sont
nulles.

5.2.5 Diagramme de GANTT

Dans la pratique, il arrive qu'on associe au problème traité un diagramme dit
de GANTT, dans lequel chaque tâche est représentée par un segmant horizontal qui
"commence" à la date au plus tôt de réalisation de cette tâche et dont la longueur
représente la durée. C'est ainsi que nous avons, dans notre exemple, le diagramme
suivant :

10 20 30 40 50 60

41
 Les segments sont prolongés en pointillés d'une longueur égale à l'intervalle de
ottement associé à chaque tâche, ce qui permet de voir d'une part la succession
des tâches et d'autres part les retards qu'on peut apporter à leur réalisation.

42
Chapitre 6

Annexe : Utilisation d'EXCEL

pour résoudre un programme

linéaire

43