République Algérienne Démocratique et Populaire

Ministère de l’enseignement supérieur et de la recherche scientifique

École Nationale Polytechnique de Constantine

POLYCOPIÉ PÉDAGOGIQUE DE COURS

Filière : Classes préparatoires

Niveau : Deuxième année

Informatique 3 :
Théorie des graphes et programmation linéaire

Mohamed Mahdi BENMOUSSA

Maître de conférences classe B

Année universitaire : 2021.

Table des matières

1 Introduction 8

2 Notions élémentaires sur les graphes 10

2.1 Exemple de problèmes représentables avec les graphes . . . . . . . . . . . . 10
2.1.1 Choix d’un itinéraire . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.2 Planification d’une session d’examens . . . . . . . . . . . . . . . . . 11
2.1.3 Routage dans les réseaux de télécommunications . . . . . . . . . . . 11
2.2 Généralités sur les graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Graphe non orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 Graphe orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.3 Graphe complet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.4 Chaînes et chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.5 Graphes eulériens et graphes Hamiltoniens . . . . . . . . . . . . . . 14
2.2.6 Connexité et connexité forte . . . . . . . . . . . . . . . . . . . . . . 16
2.2.7 Graphe réduit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.8 Graphes partiels et sous graphes . . . . . . . . . . . . . . . . . . . . 17
2.2.9 Graphe valué . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.10 Graphe coloré . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.11 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Représentation des graphes en machine . . . . . . . . . . . . . . . . . . . . 20
2.3.1 Matrice d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.2 Matrice d’incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 Parcours des graphes : largeur et profondeur . . . . . . . . . . . . . . . . . 23
2.4.1 Parcours en profondeur d’abord . . . . . . . . . . . . . . . . . . . . 23
2.4.2 Parcours en largeur d’abord . . . . . . . . . . . . . . . . . . . . . . 24
2.5 Arbres et arborescence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.5.1 Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.5.2 Arborescence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 Problème du parcours de graphes 29

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 Algorithme de Bellman-Ford-Kalaba (BFK) . . . . . . . . . . . . . . . . . 32
3.4 Algorithme de Floyd-Warshall-Roy (FWR) . . . . . . . . . . . . . . . . . . 34
3.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2
TABLE DES MATIÈRES 3

4 Problème des flots 38

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Recherche du flot maximum . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.4 Coupe, coupe minimale et flot maximum . . . . . . . . . . . . . . . . . . . 44
4.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5 Programmation linéaire 47
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.2 Notions de bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.3 Méthodes de résolutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3.1 Méthode graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3.2 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3.3 Cas particuliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.3.4 Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

6 Conclusion 63

Bibliographie 64
Liste des Algorithmes

1 Algorithme de Glouton. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 Algorithme du parcours en profondeur . . . . . . . . . . . . . . . . . . . . . 23
3 Algorithme du parcours en Largeur . . . . . . . . . . . . . . . . . . . . . . . 24

4 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5 Algorithme de Bellman-Ford-Kalaba . . . . . . . . . . . . . . . . . . . . . . 33
6 Algorithme de Floyad-Warshall-Roy . . . . . . . . . . . . . . . . . . . . . . 35

7 Algorithme Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4
Liste des tableaux

2.1 Tableau 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2 Tableau 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3 Tableau 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.1 Application de l’Algorithme 4 sur l’exemple de la Figure 3.1 . . . . . . . . 31

3.2 Application de l’Algorithme 5 sur l’exemple de la Figure 3.1 . . . . . . . . 33
3.3 Algorithme 6 : étape 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4 Algorithme 6 : étape 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5 Algorithme 6 : étape 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.6 Algorithme 6 : étape 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.7 Algorithme 6 : étape 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.8 Algorithme 6 : étape 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.9 Algorithme 6 : étape 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.10 Algorithme 6 : matrice Pred . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5.1 Exemple de modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.2 Représentation du PL sous forme de tableau . . . . . . . . . . . . . . . . . 55
5.3 Itération 1 : choix du pivot . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.4 Itération 1 : transformation . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.5 Itération 1 : calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.6 Itération 2 : Choix du pivot . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.7 Itération 2 : calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.8 Itération 2 : résultat final . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.9 Cas particulier 1 : égalité des coefficients lors du choix de la colonne du pivot 59
5.10 Cas particulier 2 : égalité des valeurs lors du choix de la ligne du pivot . . 59
5.11 Règles de dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5
Table des figures

2.1 Les sept ponts de Königsberg . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2 Graphe non orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Graphe orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Graphe complet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5 Graphes eulériens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6 Exercice sur les graphes eulériens . . . . . . . . . . . . . . . . . . . . . . . 15
2.7 Carte du TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.8 Graphe connexe et non connexe . . . . . . . . . . . . . . . . . . . . . . . . 16
2.9 Graphe orienté fortement connexe . . . . . . . . . . . . . . . . . . . . . . . 17
2.10 Exemple de graphe orienté réduit . . . . . . . . . . . . . . . . . . . . . . . 18
2.11 Graphes partiels et sous graphes . . . . . . . . . . . . . . . . . . . . . . . . 18
2.12 Exemple de graphe valué . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.13 Exemple de graphe coloré . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.14 Exemple de matrice d’adjacence pour un graphe orienté . . . . . . . . . . . 21
2.15 Exemple de matrice d’adjacence pour un graphe non orienté . . . . . . . . 21
2.16 Exemple de matrice d’incidence pour un graphe orienté . . . . . . . . . . . 22
2.17 Exemple de matrice d’incidence pour un graphe non orienté . . . . . . . . 22
2.18 Exemple de parcours en profondeur d’abord d’un graphe orienté . . . . . . 24
2.19 Exemple de parcours en largeur d’abord d’un graphe orienté . . . . . . . . 25
2.20 Exemple de graphe arbres et non-arbres . . . . . . . . . . . . . . . . . . . 26
2.21 Exemple de graphe arborescence et non-arborescence . . . . . . . . . . . . 26

3.1 Exemple de graphe orienté valué . . . . . . . . . . . . . . . . . . . . . . . . 31

3.2 Chemins optimaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3 Chemins optimaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.1 Exemple de réseau de transport . . . . . . . . . . . . . . . . . . . . . . . . 39

4.2 Exemple de réseau de transport . . . . . . . . . . . . . . . . . . . . . . . . 40
4.3 État initial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.4 État final . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5 Chemin 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.6 Chemin 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.7 Chemin 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.8 Chemin 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.9 Chemin 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.10 Chemin 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.11 Chemin 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

6
TABLE DES FIGURES 7

4.12 Chaîne 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.13 Exemple de coupe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.14 Exemple de coupe minimale . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.1 Étape 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.2 Étape 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.3 Étape 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.4 Étape 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.5 Étape 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.6 Étape 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Chapitre 1

Introduction

La complexité des problèmes du monde réel nécessite des outils puissants pour les
modéliser afin de les résoudre. Les mathématiques fournissent quelques outils pour at-
teindre cet objectif, tels que : les fonctions, les structures booléennes, etc. Néanmoins, ces
dispositifs ne s’adaptent pas à tous les problèmes. De ce fait, l’introduction d’un nouveau
type d’objet mathématique : les graphes. La théorie des graphes est l’un des outils
permettant la modélisation et la résolution d’un large nombre de problèmes de différents
domaines académiques et industriels. Parmi lesquels, on cite : problèmes de transport,
problèmes de logistique, problèmes d’énergétique, problèmes de réseaux informatiques,
etc.
L’existence de contraintes dans les problèmes, rend la tâche de modélisation en utilisant
les graphes difficile. Par conséquent, l’introduction de la recherche opérationnelle est plus
adaptée. Elle représente un problème par un modèle mathématique comportant : des
variables, des contraintes à respecter et une fonction objectif à optimiser. Parmi les
branches les plus étudiées dans cette discipline, on note : la programmation linéaire.
Les problèmes de la programmation linéaire ont une fonction objectif et des contraintes
linéaires.

Objectifs du cours
Ce cours couvre les objectifs suivants :

• Modéliser un problème en termes de graphes.

• Comprendre pourquoi la modélisation aide à trouver une solution générale et non

se concentrer sur les détails.

• Développer une compréhension des points communs dans les problèmes et comment
la théorie graphique aide à se concentrer sur les aspects essentiels de problèmes.

• Modéliser et résoudre un problème sous forme d’un programme linéaire.

Pré-requis du cours
La compréhension de cours nécessite la connaissance des éléments suivants :

8
CHAPITRE 1. INTRODUCTION 9

• Connaitre les notions basiques des mathématiques telles que : les équations, le pivot
de gauss, tracer des droites, etc.

• Maitriser l’algorithmique.

• Avoir des connaissances sur la manipulation des matrices à deux dimensions.

Volume horaire et évaluation

Ce module est destiné pour les étudiants de deuxième année classes préparatoires, et
il est constitué de :

• Cours : avec une charge horaire de 22h30.

• TD : avec une charge horaire de 22h30.

• Charge horaire totale en présentiel de 45h.

• Coefficient/crédit (semestriel) : 3.

L’évaluation de ce module est faite à travers une interrogation et un examen. Le calcul

de la note finale est fait avec la formule :

M oyenne = (N ote Interrogation + (N ote Examen × 2)) ÷ 3

Contenu du module
Ce cours est divisé en quatre chapitres, détaillés comme suit :

• Notions générales sur les graphes : dans ce chapitre on aborde les notions
élémentaires relatives aux graphes telles que : un graphe orienté, un chemin, un
circuit, etc. Ensuite, on présentera les propriétés relatives aux graphes telles que :
les graphes eulériens, le parcours en profondeur et en largeur, etc.

• Parcours du plus court chemin : dans ce chapitre on aborde trois algorithmes

permettant le calcul du plus court chemin dans un graphe. Chaque algorithme est
appliqué sur un exemple.

• Problèmes des flots : dans ce chapitre on aborde la notion d’un réseau de trans-
port, d’un flot et les propriétés sur les flots. Ensuite, on présente un algorithme
permettant le calcul du flot maximum. On termine par une présentation sur la
notion de coupe et sa relation avec le flot maximum.

• Programmation linéaire : dans ce chapitre, on aborde la modélisation d’un pro-

blème en utilisant un programme linéaire ainsi que deux méthodes de résolution :
méthode graphique et méthode du simplexe. Ensuite, on présente la notion de dua-
lité.
Chapitre 2

Notions élémentaires sur les graphes

Sommaire
2.1 Exemple de problèmes représentables avec les graphes . . . . 10
2.2 Généralités sur les graphes . . . . . . . . . . . . . . . . . . . . . 12
2.3 Représentation des graphes en machine . . . . . . . . . . . . . 20
2.4 Parcours des graphes : largeur et profondeur . . . . . . . . . . 23
2.5 Arbres et arborescence . . . . . . . . . . . . . . . . . . . . . . . 25
2.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Historique
L’apparition de la théorie des graphes est récente, le premier article considéré comme
fondateur de la théorie des graphes fut présenté par le mathématicien Leonhard Euler en
1735. Soit une ville qui contient sept ponts, la problématique est d’élaborer une promenade
à partir d’un point de départ donné en visitant tous les ponts une et une seule fois, pour
ensuite revenir au point de départ.

Figure 2.1 – Les sept ponts de Königsberg

2.1 Exemple de problèmes représentables avec les graphes

2.1.1 Choix d’un itinéraire
Comment choisir un itinéraire pour aller le plus rapidement possible de Bordeaux à
Grenoble, sachant qu’une manifestation d’étudiants bloque la gare de Poitiers ?

10
CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 11

• Bordeaux - Nantes : 4h

• Bordeaux - Marseille : 9h

• Bordeaux - Lyon : 12h

• Nantes - Paris-Montparnasse : 2h

• Nantes - Lyon : 7h

• Paris-Montparnasse - Paris-Lyon : 1h (en autobus)

• Paris-Lyon - Grenoble : 4h30

• Marseille - Lyon : 2h30

• Marseille - Grenoble : 4h30

• Lyon - Grenoble : 1h15

Afin de représenter ces données, il est plus facile d’utiliser un graphes où les sommets
représentent les gares et les arêtes représentent les trajets (avec comme étiquète la durée
du trajet).

2.1.2 Planification d’une session d’examens

Un autre exemple représentable avec les graphes est la planification des examens. On a
8 groupes d’étudiants (allant du groupe 1 au groupe 8) et qui doivent passer leurs examens
de différents modules, sachant que chaque examen occupe une demi-journée :

Chimie G1 et G2
Électronique G3 et G4
Informatique G3, G5, G6 et G7
Mathématiques G1, G5, G6 et G8
Physique G2, G6, G7 et G8

Dans cet exemple, on cherche à gérer la session d’examens la plus courte. Pour ce faire,
on modélise l’ensemble des enseignants par des sommets, c’est-à-dire, chaque enseignant
est assigné à un sommet. . Les arêtes vont représenter les liens entre les examens qui ne
peuvent pas se dérouler simultanément. Il suffit ensuite de colorer le graphe en utilisant
le moins de couleurs possible et que chaque deux sommets liés par une arête n’ont pas la
même couleur.

2.1.3 Routage dans les réseaux de télécommunications

Dans ce genre de problème, il est nécessaire de savoir s’il est possible d’acheminer
de l’information entre deux centres reliés par un réseau de télécommunications. Ce genre
de problème peut être représenté par un flot de valeur maximale (dans un graphe qui
modélise ce réseau) avec : les sommets représentant les centres et les arcs représentant les
liaisons entre ces centres.
CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 12

2.2 Généralités sur les graphes

2.2.1 Graphe non orienté
Définition 1 Un graphe non orienté G = (S, E), est défini par :

• S = {s1 , s2 , ..., sn } : un ensemble où ses éléments sont les sommets (ou nœuds).
L’ordre d’un graphe G est le nombre de sommets n.

• E = {e1 , e2 , ..., em } : un ensemble où ses éléments sont appelés les arêtes. Chaque
arête représente un couple non ordonné S ∗ S = {{s1 , s2 }|s1 ∈ S, s2 ∈ S}. On note
|E| = m.

Figure 2.2 – Graphe non orienté

La Figure 2.2 est un graphe non orienté avec 14 sommets (0,1, 2,...,13) et 30 arêtes.

2.2.2 Graphe orienté

Définition 2 Un graphe orienté G = (S, A), est défini par :

• S = {s1 , s2 , ..., sn } : un ensemble où ses éléments sont les sommets (ou nœuds).
L’ordre d’un graphe G est le nombre de sommets n.

• A = {a1 , a2 , ..., am } : un ensemble où ses éléments sont appelés les arcs. Chaque
arc représente un couple ordonné S × S = {(s1 , s2 )|s1 , s2 ∈ S}, tels que s1 est
l’extrémité initiale et s2 est l’extrémité terminale de a, s2 est successeur de s1 ) et s1
est le prédécesseur de s2 ). On note |A| = m.

La Figure 2.3 est un graphe orienté de 6 sommets (1, 2, 3,...,6) et 14 arcs (dont 5
boucles).
Quelques notions relatives aux graphes orientés :

• Une boucle dans un graphe orienté est représentée par un arc dont le sommet d’ex-
trémité initiale est le même que le sommet d’extrémité terminale : a = (s, s), ∀s ∈ S.
CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 13

Figure 2.3 – Graphe orienté

• On note par ω(s) : l’ensemble des arcs ayant s comme extrémité.

• On note par ω + (s) : l’ensemble des arcs ayant s comme extrémité initiale (ensemble
des arcs sortant de s).

• On note par ω − (s) : l’ensemble des arcs ayant s comme extrémité terminale (en-
semble des arcs entrant dans s).

• On note par Γ(s) : l’ensemble des successeurs de s.

• On note par δ + (s) : le degré sortant de s (nombre de successeurs).

• On note par δ − (s) : le degré entrant de s (nombre de prédécesseurs, c’est-à-dire le

nombre de sommets pour lesquels s est un successeur).

2.2.3 Graphe complet

Définition 3 Un graphe G = (S, A) est dit complet si, pour toute paire de sommets
(s1 , s2 ), si ∈ S, il existe au moins un arc/arête de la forme (s1 , s2 ) ou (s2 , s1 ). La Figure 2.4
représente un graphe complet.

Figure 2.4 – Graphe complet

CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 14

2.2.4 Chaînes et chemins

Chaînes : soit G = (S, E) un graphe non orienté, une chaîne de longueur l allant
du sommet s1 au sommet s2 est une suite d’arêtes e(s1 , s2 ) = (e1 , e2 , ..., el ) tels que
∀i ∈ {1, ..., l − 1}, ei et ei+1 sont adjacents. Le sommet s1 est appelé l’extrémité initiale,
et le sommet s2 l’extrémité terminale de la chaîne.
Remarque : si aucun sommet composant la séquence d’une chaîne n’apparaît plus
d’une fois, alors c’est une chaîne élémentaire. Si aucune arête composant la séquence
n’apparaît plus d’une fois, alors c’est une chaîne simple.
Une chaîne est un cycle si les extrémités initiale et terminale coïncident. Un cycle est
dit élémentaire s’il est minimale, c’est-à-dire, il ne contient (au sens de l’inclusion)
strictement aucun cycle.
Chemins : Soit G = (S, A) un graphe orienté, un chemin de longueur l allant du
somment s1 au sommet s2 est une suite d’arcs a(s1 , s2 ) = ((a1 , a2 , ..., al )) tels que ∀i ∈
{1, ..., l − 1}, ai et ai+1 sont adjacents et l’extrémité terminale de ai est l’extrémité initiale
au+i .
Si aucun sommet composant la séquence n’apparaît plus d’une fois, alors c’est un chemin
élémentaire. Si aucun arc composant la séquence n’apparaît plus d’une fois, alors c’est
un chemin simple.
Un chemin est un circuit si les extrémités initiale et terminale coïncident. Un circuit
est dit élémentaire s’il est minimale, c’est-à-dire, il ne contient (au sens de l’inclusion)
strictement aucun circuit.

2.2.5 Graphes eulériens et graphes Hamiltoniens

Définition 4 Graphes eulériens
Soit un graphe orienté G = (S, A) :

• Un chemin eulérien est un chemin empruntant une fois et une fois seulement
chaque arc de G.

• Un circuit eulérien est un chemin eulérien dont les extrémités coïncident.

• Un graphe possédant un cycle eulérien est appelé graphe eulérien.

• Un graphe orienté est dit eulérien s’il admet un circuit eulérien.

• Remarque : la même définition s’applique sur les graphes non orientés (c’est-à-dire,
chaîne eulérien, cycle eulérien et graphe non orienté eulérien).

La Figure 2.5 comporte deux graphes (orienté à droite et non orienté à gauche) qui
sont des graphes eulériens.

Théorème 1 Graphe non orienté

• Un graphe non orienté connexe possède une chaîne eulérienne si et seulement si

le nombre de sommets de degré impair est égal à 0 ou 2.
CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 15

Figure 2.5 – Graphes eulériens

• Un graphe non orienté connexe admet un cycle eulérien si et seulement si tous ses
sommets ont un degré pair.
Théorème 2 Graphe orienté
• Un graphe orienté connexe admet un circuit eulérien si, et seulement si, pour tout
sommet, le degré entrant est égal au degré sortant.
Exercice :
Les graphes suivants sont-ils eulériens ? (voir Figure 2.6)

Figure 2.6 – Exercice sur les graphes eulériens

Définition 5 Graphe hamiltonien

Soit un graphe orienté G = (S, A) :
• Un chemin hamiltonien (ou une chaîne hamiltonienne) est un chemin (une
chaîne) qui passe une fois, et une fois seulement, par chacun des sommets de G.
• Un chemin hamiltonien (une chaîne hamiltonienne) est donc un chemin (une
chaîne) élémentaire de longueur n − 1 (sachant que n est le nombre de sommets).
• Un circuit hamiltonien (cycle hamiltonien) est un circuit (cycle) qui passe une
fois, et une seule fois, par chacun des sommets de G.
• Un graphe est dit hamiltonien s’il contient un cycle hamiltonien (pour les graphes
non orientés) ou un circuit hamiltonien (pour les graphes orientés).
La Figure 2.7 montre l’exemple du TSP (Travelling Salesman Problem).
• Données : on a une liste de villes et leurs distances deux à deux.
• Question : trouver le plus petit tour qui visite chaque ville exactement une fois.
• Solution : reformuler le problème sous forme de graphe qui sera complet et pondéré
et de trouver un cycle hamiltonien de poids minimum.
CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 16

Figure 2.7 – Carte du TSP

2.2.6 Connexité et connexité forte

Définition 6 Graphe connexe
Un graphe G est connexe s’il existe au moins une chaîne entre une paire quelconque de
sommets de G :

(
soit si = sj
si R s j ↔ (2.1)
soit il existe une chaîne joignant si et sj

Remarque :

• La connexité d’un graphe ne dépend pas de l’orientation du graphe (orienté ou non

orienté). Par conséquent, on va ignorer le sens des arcs dans le cas d’un graphe
orienté.

• Si un graphe non orienté est connexe alors il est par définition fortement connexe.

La Figure 2.8 montre deux exemples d’un graphe connexe (le plus à droite) et d’un graphe
non connexe (le plus à gauche).

Figure 2.8 – Graphe connexe et non connexe

CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 17

Définition 7 Graphe fortement connexe

Un graphe orienté G est fortement connexe s’il existe un chemin joignant deux som-
mets quelconques :

(
soit si = sj
si R s j ↔ (2.2)
soit il existe à la fois un chemin joignant si et sj et inversement

Remarque :

• Si un graphe non orienté est connexe alors il est par définition fortement connexe.

La Figure 2.9 montre un exemple d’un graphe orienté fortement connexe.

Figure 2.9 – Graphe orienté fortement connexe

2.2.7 Graphe réduit

Définition 8 Soit un graphe orienté G = (S, A), on appelle un graphe réduit le quotient
du graphe G par la relation de forte connexité : Gr = G/R.

• Les sommets de Gr sont donc les composantes fortement connexes.

• Il existe un arc entre deux composantes fortement connexes si et seulement s’il existe
au moins un arc entre un sommet de la première composante et un sommet de la
seconde.

• Un graphe réduit est nécessairement sans circuit.

La Figure 2.10 montre un exemple de réduction de graphe en utilisant trois compo-

santes fortement connexes (en rouge, bleu et vert).

2.2.8 Graphes partiels et sous graphes

Définition 9 Soit G = (S, A) un graphe orienté, on appelle :
′ ′
• Le graphe partiel G = (S, A ) de G, le graphe auquel on enlève quelques arcs (ou
′
arêtes), tel que A ⊂ A
′ ′ ′
• Le sous graphe G = (S , A ) de G, le graphe auquel on enlève quelques sommets avec
′ ′
les arcs dont ils sont l’extrémité (initiale ou terminale), tel que S ⊂ S et A ⊂ A
CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 18

Figure 2.10 – Exemple de graphe orienté réduit

• Le sous graphe partiel d’un graphe G est un le sous graphe d’un graphe partiel de
G.

La Figure 2.11 représente (en partant de la gauche) un graphe G, son graphe partiel, son
sous graphe et son sous graphe partiel.

Figure 2.11 – Graphes partiels et sous graphes

2.2.9 Graphe valué

Définition 10 Soit un graphe G = (S, A). On dit que G est un graphe valué dans le cas
où on associe des réels aux arcs (ou arêtes). Le graphe G est alors muni d’une fonction
(appelée fonction de coût f ) : A → R où R est l’ensemble des réels.

La Figure 2.12 représente un graphe avec un ensemble de sommets, d’arêtes et des valeurs
pour chaque arête.

2.2.10 Graphe coloré

Définition 11 Soit G = (S, A) un graphe orienté (non orienté) :

• On dit que G est k-chromatique ou bien G admet une k-coloration s’il existe une
partition de S en k ensembles. Ceci revient à dire qu’il est possible de colorer les
sommets de G avec k couleurs différentes.
CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 19

Figure 2.12 – Exemple de graphe valué

• Le nombre chromatique est le nombre le plus petit nécessaire pour colorier un

graphe et il est compris entre 1 et le nombre de sommets.

L’un des algorithmes les plus simples à utiliser est l’algorithme de Glouton,son principe
est le suivant (voir Algorithme 1) :

Algorithme 1 : Algorithme de Glouton.

1 Établir une liste ordonnée de sommets (suivant l’ordre décroissant de leur degré)
tant que il reste des sommets à colorier faire
2 Choisir une nouvelle couleur (couleur d’usage)
3 Chercher dans la liste des sommets le premier sommet non coloré et le colorer
par la couleur d’usage
4 Examiner tour à tour, dans l’ordre de la liste, tous les sommets non coloriés et
colorier chaque sommet non adjacent à un sommet déjà coloré avec la
couleur d’usage

L’exemple de la Figure 2.13 montre un graphe coloré, où chaque deux sommets sous
adjacent n’ont pas la même couleur. Il y a 3 couleurs et c’est le nombre chromatique (car
c’est le nombre minimum nécessaire pour colorer ce graphe).

Figure 2.13 – Exemple de graphe coloré

CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 20

2.2.11 Généralités
• Les arcs ont un sens. l’arc a = (s1 , s2 ) va de s1 vers s2 .

• Un arc (arête) peut avoir un coût, une capacité, un poids, etc.

• Deux sommets sont voisins s’ils sont reliés par un arc ou une arête.
′
• N (s) : ensemble des voisins de s, ensemble des sommets s tels qu’il existe une
′
arête/arc contenant s et s .

• Un graphe est dit symétrique si (x, y) ∈ A ⇒ (y, x) ∈ A.

• Un multigraphe est un graphe non orienté où entre chaque deux sommets x et y

il peut y avoir plusieurs arêtes.

• Un graphe non orienté est dit simple s’il est sans boucle et s’il n’existe pas plus
d’une arête entre toute parie de sommets.

• Deux arcs (arêtes) sont adjacent(e)s s’ils ont au moins une extrémité communes.

• Ordre d’un graphe : est représenté par le nombre de sommets contenu dans ce
graphe.

• Taille d’un graphe : est le nombre d’arêtes (arcs) contenu dans ce graphe.

• Degré dans un graphe : est le degré maximum de tous ses sommets.

• Degré dans un graphe non orienté : est le nombre d’arêtes reliant ce sommet
aux autres.

• Degré dans un graphe orienté : on parle de degré entrant et degré sortant d’un
sommet.

• Longueur d’une chaîne (chemin) : est le nombre des arêtes (arcs) qui la com-
posent.

• Valeur d’une chaîne (chemin)dans un graphe valué : est la somme des valeurs
des arêtes (arcs) qui la composent.

• Distance entre deux sommets : est la longueur de la plus courte chaîne (chemin)
entre eux.

• Diamètre d’un graphe : est le maximum des distances entre ses sommets.

2.3 Représentation des graphes en machine

Il y a plusieurs représentations des graphes dans une machine, parmi eux deux seront
présentés dans ce cours.
CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 21

2.3.1 Matrice d’adjacence

Considérons un graphe orienté G = (S, A) comportant n sommets. La matrice d’ad-
jacence de G est égale à la matrice U = (uij ) de dimension n × n telle que :
1 Si (i, j) ∈ A (c’est-à-dire (i, j) est un arc)

• uij =
0 Sinon
• Une telle matrice ne contenant que des "0" et des "1" est appelée matrice booléenne
• Le principe de cette matrice s’applique de la même manière sur un graphe non
orienté. Dans ce cas la matrice sera symétrique car les arêtes seront comptabilisées
dans les deux sens ( (i, j) et (j, i)).
La Figure 2.14 montre un exemple de matrice d’adjacence pour un graphe orienté. La
Figure 2.15 montre un exemple de matrice d’adjacence pour un graphe non orienté.

Figure 2.14 – Exemple de matrice d’adjacence pour un graphe orienté

Figure 2.15 – Exemple de matrice d’adjacence pour un graphe non orienté

Propriétés :
• La somme des éléments de la ième ligne de U est égale au degré sortant ds (si ) du
sommet si de G.
• La somme des éléments de la ième ligne de U est égale au degré entrant de (si ) du
sommet si de G.
• U est symétrique si, et seulement si, le graphe G est symétrique.
CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 22

2.3.2 Matrice d’incidence

Considérons un graphe orienté sans boucle G = (S, A) comportant n sommets s1 , ..., sn
et m arêtes a1 , ..., am . On appelle matrice d’incidence (aux arcs) de G la matrice M =
(mij ) de dimension n × m telle que :

 1 Si si est l’extrémité terminale de aj



• mij = −1 Si si est l’extrémité initiale de aj

0 Si si n’est pas une extrémité de aj


Pour un graphe non orienté sans boucle G = (S, E), la matrice d’incidence (arêtes)
est définie par :
1 Si si est une extrémité ej

• mij =
0 Sinon
La Figure 2.16 représente un exemple d’une matrice d’incidence d’un graphe orienté.
La taille de la matrice est de 8 × 5 (8 est le nombre d’arcs et 5 est le nombre de sommets).
La matrice comporte trois valeurs : 0, 1 et -1.

Figure 2.16 – Exemple de matrice d’incidence pour un graphe orienté

La Figure 2.17 représente un exemple d’une matrice d’incidence d’un graphe non
orienté. La taille de la matrice est de 5 × 5 (8 est le nombre d’arêtes et 5 est le nombre
de sommets). La matrice comporte deux valeurs : 0 et 1.

Figure 2.17 – Exemple de matrice d’incidence pour un graphe non orienté

CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 23

2.4 Parcours des graphes : largeur et profondeur

Il existe plusieurs problèmes en théorie des graphes concernant la connexité, par
exemple :
• Est-ce qu’un sommet est accessible par un chemin à partir d’un sommet donné ?
• Est-ce que tous les sommets sont accessibles à partir d’un sommet donné ?
• etc.
Pour répondre à ce genre de problèmes, il existe deux types d’algorithmes : parcours en
profondeur d’abord et parcours en largeur d’abord.

2.4.1 Parcours en profondeur d’abord

Le parcours en profondeur consiste à parcourir un graphe G branche par branche et
refaire la même chose pour le reste. Chaque parcours a un sommet de départ, et chaque
sommet peut être dans deux états : exploré ou non exploré. L’Algorithme 2 représente le
principe d’un parcours en profondeur d’abord.

Algorithme 2 : Algorithme du parcours en profondeur

1 Entrée : (G)
2 Visiter tous les sommets
3 Visiter un sommet s :
4 if s n’a pas encore été enfilé alors then
5 {pré-traitement de s} ;
6 visiter tous les successeurs de s ;
7 {post-traitement de s} ;

Chaque sommet est visité exactement une seule fois. La Figure 2.18 représente un
exemple de parcours en profondeur d’abord en commençant par le sommet 1 et en choi-
sissant le successeur ayant le plus petit indice. Le résultat du parcours est de : 1, 2, 4, 3, 5.
L’application de l’algorithme sur notre exemple est la suivante :
• Première étape, on choisit le sommet de départ pour faire le parcours, c’est-à-dire
1.
• Deuxième étape, on choisit le successeur du sommet 1 ayant l’indice le plus petit,
c’est-à-dire 2.
• Troisième étape, on choisit le successeur du sommet 2 ayant l’indice le plus petit,
c’est-à-dire 4.
• Quatrième étape, on choisit le successeur du sommet 4 ayant l’indice le plus petit,
c’est-à-dire 3.
• Cinquième étape, on choisit le successeur du sommet 3 ayant l’indice le plus petit,
c’est-à-dire 5.
CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 24

• Une fois que tous les sommets sont parcourus, l’algorithme est terminé.

Figure 2.18 – Exemple de parcours en profondeur d’abord d’un graphe orienté

2.4.2 Parcours en largeur d’abord

Le parcours en largeur d’abord consiste à parcourir un graphe G étape par étape
en faisant tous les sommets de chaque étape. Chaque parcours a un sommet de départ,
et chaque sommet peut être dans deux états : exploré ou non exploré. L’Algorithme 3
représente le principe d’un parcours en largeur d’abord.
Chaque sommet est visité, donc enfilé au moins une fois, or, on ne peut pas enfiler que
des sommets non encore enfilés ; par conséquent, chaque sommet est enfilé exactement
une fois.
Algorithme 3 : Algorithme du parcours en Largeur
1 Entrée : (G)
2 Visiter tous les sommets
3 Visiter un sommet s :
4 if s n’a pas encore été enfilé alors then
5 enfiler s ;
6 tant que la file n’est pas vide faire
7 soit "n" le premier sommet de la file ;
8 {traitement de "n"} ;
9 défiler ;
10 enfiler tous les successeurs non encore enfilés de "n" ;

La Figure 2.19 représente le parcours en largeur d’abord d’un graphe orienté en com-
mençant par le sommet 1 et en choisissant le successeur ayant le plus petit indice. Le
résultat du parcours est de : 1, 2, 4, 5, 3. L’application de l’algorithme sur notre exemple
est la suivante :

• Première étape, on choisit le sommet de départ pour faire le parcours, c’est-à-dire

1.
CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 25

• Deuxième étape, on choisit les successeurs du sommet 1 ayant l’indice le plus petit,
c’est-à-dire 2.

• Troisième étape, on choisit les successeurs du sommet 2 ayant l’indice le plus petit,
c’est-à-dire 4 et 5 (dans l’ordre).

• Quatrième étape, on choisit les successeurs du sommet 4 ayant l’indice le plus petit,
c’est-à-dire 3, ensuite les successeurs du sommet 5 (dans cet exemple, il y en a pas).

• Cinquième étape, on choisit le successeur du sommet 3 ayant l’indice le plus petit.

Dans cette situation, le 5 étant déjà parcours, le 3 ne possède pas de successeurs
non parcourus.

• Une fois que tous les sommets sont parcourus, l’algorithme est terminé.

Figure 2.19 – Exemple de parcours en largeur d’abord d’un graphe orienté

2.5 Arbres et arborescence

2.5.1 Arbres
Soit un graphe orienté G = (S, A). G est un arbre s’il existe un et un seul chemin
reliant deux sommets distincts de S.

• G est connexe, car il existe au moins un chemin entre deux sommets.

• G ne contient pas de circuit, car il existe au plus un chemin entre deux sommets.

• Une feuille, est un sommet de degré "un".

• Un nœud, est un sommet de degré "deux" ou plus.

• G contient n − 1 arcs (n est le nombre de sommets).

CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 26

La Figure 2.20 représente un ensemble graphes qui sont des arbres ou non.

Figure 2.20 – Exemple de graphe arbres et non-arbres

2.5.2 Arborescence
Soit G = (S, E) un graphe orienté. G est une arborescence si :
• G n’a qu’un seul point d’entrée, c’est-à-dire, un sommet qui n’a pas de prédécesseur.
Ce sommet est la racine de l’arborescence.

• Il existe un seul chemin de la racine vers un autre sommet du graphe (nœud ou

feuille).
La Figure 2.21 représente un exemple d’arborescence et non arborescence. Le graphe
du côté gauche est une arborescence, car il n’existe qu’une seule racine (le sommet 6).
Cependant, le graphe à droite n’est pas une arborescence car il n’existe pas de racine.

Figure 2.21 – Exemple de graphe arborescence et non-arborescence

Propriétés :

• G ne comporte pas de circuit.

• Chaque sommet du graphe a un et un seul prédécesseur (sauf la racine).

• Si on ignore l’orientation des arcs dans une arborescence, alors le graphe devient un
arbre.

• Une forêt est un graphe qui contient plusieurs arbres ou arborescences distinctes.
CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 27

2.6 Exercices
Exercice 1
Pour les graphes orientés, il faut considérer des suites de couples d’entiers (le premier
élément d’un couple correspond au degré entrant, le second au degré sortant). Les suites
suivantes sont-elles des suites graphiques ?

• (0, 1), (1, 1), (1, 1), (1, 1), (1, 0)

• (1, 1), (1, 1), (1, 1), (1, 1), (1, 1)

• (0, 2), (1, 1), (1, 1), (1, 1)

• (0, 2), (1, 1), (1, 1), (2, 0)

• (1, 2), (1, 2), (2, 1), (2, 1)

• (1, 2), (1, 2), (2, 1), (2, 2), (1, 1)

Exercice 2
Ce graphe à cinq sommets est tel que deux sommets quelconques sont reliés par un
arc unique, dans un sens ou dans l’autre. Ce type de graphe a comme propriété d’avoir un
nombre impair de chemins hamiltoniens (avec le sommet final différent du sommet initial)
lorsque l’on prend les cinq points de départ possibles à tour de rôle.

• Déterminer tous les chemins hamiltoniens partant de chacun des 5 sommets (0, puis
1, puis 2, puis 3 et enfin 4), et se terminant en un sommet différent du point de
départ. Les dessiner dans chacun de ces 5 cas. Combien y en a-t-il ?

• Vérifier que pour chacun des points de départ, un des chemins hamiltoniens peut être
prolongé pour donner un cycle hamiltonien. Les cinq cycles hamiltoniens obtenus
constituent le même cycle si l’on ne tient pas compte du point de départ.
CHAPITRE 2. NOTIONS ÉLÉMENTAIRES SUR LES GRAPHES 28

Exercice 3
Pour ce graphe non orienté à 14 sommets, les voisins de chaque sommet sont supposés
être dans l’ordre croissant de leurs numéros, ainsi :

• 0 a pour voisins 1, 4, 7, 8 / 1 a pour voisins 0, 5, 7 / etc.

• En partant du sommet 0, faire une exploration en profondeur de ce graphe en utili-

sant l’ordre de voisins tel qu’il a été défini. Dessiner l’arbre obtenu.

• Toujours en partant du sommet 0, faire une exploration en largeur du graphe. On

aura intérêt à utiliser l’évolution d’une file, afin de dessiner l’arbre final de l’explo-
ration.

Exercice 4
Représenter graphiquement les graphes associés aux matrices suivantes :

0 0 0 0 0 0
-1 -1 0 0 0 0 1 1 -1 0 0 0 1
1 0 0 0 0 0
1 0 -1 1 0 0 0 0 0 1 0 -1 0
0 1 0 0 0 1
0 1 1 0 -1 0 -1 0 0 0 1 0 0
1 0 0 0 0 0
0 0 0 -1 0 1 0 0 0 0 -1 1 -1
0 1 0 1 0 0
0 0 0 0 1 -1 0 -1 1 -1 0 0 0
0 0 0 0 1 0
Table 2.1 – Tableau 1 Table 2.2 – Tableau 2
Table 2.3 – Tableau 3
Chapitre 3

Problème du parcours de graphes

Sommaire
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 Algorithme de Bellman-Ford-Kalaba (BFK) . . . . . . . . . . 32
3.4 Algorithme de Floyd-Warshall-Roy (FWR) . . . . . . . . . . . 34
3.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.1 Introduction
Les problèmes de recherche du plus court chemin dans les graphes comptent parmi
les plus classiques de la théorie des graphes. Le principe du plus court chemin est de
trouver un chemin allant d’un sommet de départ vers un sommet d’arrivée en considérant
le chemin le plus court (les arcs du graphe sont valués, et les valeurs peuvent être positives
ou négatives). Certaines conditions sont nécessaires pour pouvoir calculer le plus court
chemin :

• Le graphe doit être connexe et tous les sommets sont atteignables (il suffit d’utiliser
la procédure du parcours du graphe pour vérifier si un sommet est atteignable).

• Absence de cycle/circuit négatif, c’est-à-dire, un cycle/circuit dont la somme des

valeurs sur ses arcs est négative.

Il existe un grand nombre d’algorithmes permettant de déterminer un plus court chemin

à partir d’un sommet de départ. Dans ce qui suit, les algorithmes cités ci-après seront
détaillés :

• Algorithme de Dijkstra.

• Algorithme de Floyd-Warshall-Roy.

• Algorithme de Bellman-Ford.

29
CHAPITRE 3. PROBLÈME DU PARCOURS DE GRAPHES 30

3.2 Algorithme de Dijkstra

L’algorithme de Dijkstra est l’un des algorithmes les plus simples en matière de com-
plexité. Il permet la recherche du plus court chemin à partir d’un sommet vers le reste.
L’algorithme de Dijkstra calcule en permanence la distance des sommets avec l’origine (le
point de départ). Il utilise trois ensembles :

• Sommets ouverts : les sommets qui sont accessibles et qui ne sont pas encore
traités.

• Sommets fermés : les sommets qui sont traités et dont on ne peut plus modifier
la valeur.

• Sommets indéfinis : les sommets qui ne sont pas encore accessibles.

Dans chaque étape de cet algorithme, on choisit un sommet ouvert qui a la plus petite
distance et on récupère ses successeurs (qui deviendront des sommets ouverts). Ensuite,
on ferme le sommet traité et on refait ce processus jusqu’à ce que tous les sommets soient
fermés.

Définition 12 Soit un graphe orienté et valué G = (S, A, f ), l’algorithme de Dijkstra

calcule deux matrices :

• Dist : matrice des distances telle que Dist(y) = distance optimale de x à y.

• Pred : matrice des précédences pour la recherche des chemins une fois le plus court
chemin est calculé.

L’algorithme représentant Dijkstra est le suivant (Algorithme 4) :

Algorithme 4 : Algorithme de Dijkstra

1 Entrée : (G,s), Sortie : [Dist,Pred]
2 Initialisation :
3 n = nombre de sommets de G
4 P red = tableau des prédécesseurs initialisé à 0
5 Dist = tableau des distances initialisé à ∞ sauf Dist(0)
6 W = matrice des poids des arcs, ∞ si l’arc n’existe pas
7 C = {1; 2; ...; n} (liste des somments restant à traiter)
8 D = ∅ (liste des sommets déjà traités, fermés)
9 Calcule :
10 tant que C ̸= ∅ faire
11 x = sommet de C le plus proche de s
12 retirer x de C et le mettre dans D
13 pour tous les sommets y ∈ C faire
14 si Dist(x) + W (x, y) < Dist(y) alors
15 modifier Dist(y) et P red(y) = x
CHAPITRE 3. PROBLÈME DU PARCOURS DE GRAPHES 31

Le temps d’exécution de l’algorithme Dijkstra est rapide (O(n2 )) mais il ne marche pas
avec des graphes ayant des valuations négatives. Il ne calcule que le plus court chemin et
non pas le plus long chemin. Afin de démontrer le déroulement de l’algorithme de Dijkstra,
nous l’appliquons sur l’exemple de la Figure 3.1.

Figure 3.1 – Exemple de graphe orienté valué

Dist P red
x D C 1 2 3 4 5 6 1 2 3 4 5 6
0 {} {1; 2; 3; 4; 5; 6} ∞ ∞ ∞ ∞ ∞ 0 0 0 0 0 0 0
6 {6} {1; 2; 3; 4; 5} ∞ 9 11 ∞ 19 0 0 6 6 0 6 0
2 {6; 2} {1; 3; 4; 5} ∞ 9 11 10 19 0 0 6 6 2 6 0
4 {6; 2; 4} {1; 3; 5} 8 9 11 10 12 0 4 6 6 2 4 0
3 {6; 2; 4; 3} {1; 5} 8 9 11 10 12 0 4 6 6 2 4 0
1 {6; 2; 4; 3; 1} {5} 8 9 11 10 12 0 4 6 6 2 4 0
5 {6; 2; 4; 3; 1; 5} {} 8 9 11 10 12 0 4 6 6 2 4 0

Table 3.1 – Application de l’Algorithme 4 sur l’exemple de la Figure 3.1

La première ligne du tableau 3.1 est l’étape d’initialisation où les distances ont la
valeur ∞ (mise à part celle du sommet de départ), l’ensemble des so mmets fermés D est
vide et l’ensemble des sommets à traiter C comporte tous les sommets. À chaque étape, on
choisit le sommet ayant la plus petite distance, on calcule ses successeurs en considérant
toujours le sommet de départ et on change les valeurs si les anciennes sont plus grandes
(ainsi que les indices pour la matrice de précédence).

Figure 3.2 – Chemins optimaux

Prenant l’exemple du tableau 3.1 :

CHAPITRE 3. PROBLÈME DU PARCOURS DE GRAPHES 32

• À la deuxième ligne où x = 6 ; on choisit le sommet 6 car c’est le sommet de départ

et c’est le seul sommet disponible. On génère les successeurs du sommet 6 (c’est-à-
dire 2, 3 et 5) tout en mettant dans la partie Dist les distances entre le sommet 6
et ses successeurs (en partant du graphe). La matrice Pred est également modifiée
en changeant le prédécesseur de 2, 3 et 5 à la valeur 6. Le sommet 6 sera fermé
(c’est-à-dire ajouté dans l’ensemble D) car son traitement est terminé.

• À la troisième ligne où x = 2, on choisit, à partir de la ligne précédente, le sommet

ayant la plus petite distance (c’est-à-dire 2). On génère ses successeurs 5, 4 et 3 tout
en calculant la distance entre le sommet 6 et les successeurs de 2 en passant par le
sommet 2. Dans le cas où la nouvelle distance est plus petite on remplace la distance
dans le sommet concerné (dans la matrice Dist) et on change son prédécesseur à 2.

• L’algorithme se termine une fois que tous les sommets sont traités, c’est-à-dire,
l’ensemble D est remplit et l’ensemble C est vide. La Figure 3.2 montre les différents
chemins optimaux accessibles à partir du sommet 6.

• Si on souhaite par exemple aller du sommet 6 au sommet 1, il suffit de regarder la

dernière ligne de la table Pred dans le Tableau 3.1. Le dernier sommet visité avant
d’arriver à 1 est le sommet 4. Le dernier sommet visité avant d’arriver à 4 est le
sommet 2. Le dernier sommet visité avant d’arriver à 2 est le sommet 6 (qui est le
sommet de départ). Par conséquent, le chemin pour aller du sommet 6 au sommet
1 est : 6 → 2 → 4 → 1 et sa valeur est 8.

3.3 Algorithme de Bellman-Ford-Kalaba (BFK)

L’algorithme de BFK est plus coûteux (O(n3 )) que l’algorithme de Dijkstra mais il
permet la résolution des graphes avec des valeurs négatives et le calcul du plus long
chemin.

Définition 13 Soit un graphe orienté et valué G = (S, A, f ), l’algorithme de BFK calcule

deux matrices :

• Dist : matrice des distances telle que Dist(y) = distance optimale de x à y.

• Pred : matrice des précédences pour la recherche des chemins une fois le plus court
chemin est calculé.

L’algorithme représentant BFK est le suivant (Algorithme 5) :

Afin de démontrer le déroulement de l’algorithme de BFK, nous l’appliquons sur
l’exemple de la Figure 3.1 (voir le tableau 3.2). Nous souhaitons trouver les plus courts
chemins du graphe G depuis le sommet 2.
La première ligne du tableau 3.2 est l’étape d’initialisation où les distances ont la
valeur ∞ (mise à part celle du sommet de départ). À chaque étape on calcule toutes les
distances entre les sommets accessibles (c’est-à-dire ceux qui ont une valeur dans la table
Dist) à partir du point de départ (dans l’exemple, le sommet 2). La Figure 3.3 montre
les différents chemins optimaux accessibles à partir du sommet 2.
Prenant l’exemple du tableau 3.2 :
CHAPITRE 3. PROBLÈME DU PARCOURS DE GRAPHES 33

Algorithme 5 : Algorithme de Bellman-Ford-Kalaba

1 Entrée : (G,s), Sortie : [Dist,Pred]
2 Initialisation :
3 n = nombre de sommets de G
4 P red = tableau des prédécesseurs initialisé à 0
5 Dist = tableau des distances initialisé à ∞ sauf Dist(0)
6 W = matrice des poids des arcs, ∞ si l’arc n’existe pas
7 Calcule :
8 k = 1
9 tant que n ⩽ n et il y a eu des modifications à l’étape précédente faire
10 pour tous les sommets x faire
11 pour tous les y successeur de x faire
12 si Dist(x) + W (x, y) < Dist(y) alors
13 modifier Dist(y) et P red(y) = x

14 k =k+1

Dist P red
k x 1 2 3 4 5 6 1 2 3 4 5 6
0 0 ∞ 0 ∞ ∞ ∞ ∞ 0 0 0 0 0 0
0 2 ∞ 0 15 1 11 ∞ 0 0 2 2 2 0
1 4 -1 0 15 1 3 ∞ 4 0 2 2 4 0
2 1 -1 0 15 1 3 2 4 0 2 2 4 1
2 6 -1 0 15 1 3 2 4 0 6 2 4 1

Table 3.2 – Application de l’Algorithme 5 sur l’exemple de la Figure 3.1

• Dans la première étape, on sélectionne le sommet de départ et on génère ses succes-

seurs. Le sommet de départ est 2 et ses successeurs sont 3, 4 et 5. On représente dans
la matrice Dist la distance directe entre le sommet 2 et ses successeurs. La matrice
Pred sera également modifiée pour mettre le sommet 2 comme prédécesseur de ses
successeurs. L’ensemble des sommets à traiter pour la prochaine étape comportera
les sommets 3, 4 et 5.

• L’étape suivante (représentée par la ligne où k = 1) sera de traiter les trois sommets
3, 4 et 5 en calculant à chaque fois leurs successeurs. Dans le cas où le sommet traité
change les valeurs de la matrice Dist alors la ligne correspondante sera présente. Elle
sera ignorée dans le cas inverse. Dans notre exemple, uniquement la ligne du sommet
4 n’est pas ignorée car c’est la seule qui apporte les modifications nécessaires.

• L’algorithme s’arrête dans le cas où le nombre d’étapes (k) est égal au nombre de
sommets ou l’étape ki et l’étape ki−1 sont les mêmes.
CHAPITRE 3. PROBLÈME DU PARCOURS DE GRAPHES 34

Figure 3.3 – Chemins optimaux

3.4 Algorithme de Floyd-Warshall-Roy (FWR)

L’algorithme de FWR consiste à calculer toutes les distances entre couples de sommets
(i, j). Contrairement aux précédents algorithmes, FWR ne nécessite pas de sommet de
départ car il calcule toutes les distances minimales entre tous les sommets. L’algorithme
FWR est très coûteux (son temps de calcul est de n3 ) et souvent il n’est pas nécessaire
de calculer les toutes les distances minimales.

Définition 14 Soit un graphe orienté et valué G = (S, A, f ), l’algorithme de FWR calcule

deux matrices :

• Dist : matrice des distances telle que Dist(y) = distance optimale de x à y.

• Pred : matrice des précédences pour la recherche des chemins une fois le plus court
chemin est calculé.

L’algorithme FWR est le suivant (Algorithme 6) :

Afin de démontrer le déroulement de l’algorithme FWR, nous l’appliquons sur l’exemple

de la Figure 3.1 (voir les tableaux 3.3, 3.4, 3.5, 3.6, 3.7, 3.8, 3.9, 3.10).
CHAPITRE 3. PROBLÈME DU PARCOURS DE GRAPHES 35

Algorithme 6 : Algorithme de Floyad-Warshall-Roy

1 Entrée : (G)
2 Sortie : [Dist,Pred]
3 Initialisation :
4 n = nombre de sommets de G
5 P red = matrice des prédécesseurs initialisée à P red(i, j) = i si l’arc (i, j) existe,
0 sinon
6 Dist = matrice des poids relativement à f initialisée à 0 sur la diagonale
Dist(s, s) = 0, ∀s = 1, ..., n
7 Calcule :
8 k = 1
9 pour z allant de 1 jusqu’à n faire
10 pour x allant de 1 jusqu’à n faire
11 pour y allant de 1 jusqu’à n faire
12 si Dist(x, z) + Dist(z, y) < Dist(x, y) alors
13 modifier Dist(x, y) et P red(y) = P red(z, y)

Sommets 1 2 3 4 5 6 Sommets 1 2 3 4 5 6
1 0 ∞ ∞ ∞ ∞ 3 1 0 ∞ ∞ ∞ ∞ 3
2 ∞ 0 15 1 11 ∞ 2 ∞ 0 15 1 11 ∞
3 ∞ ∞ 0 16 ∞ ∞ 3 ∞ ∞ 0 16 ∞ ∞
4 -2 ∞ ∞ 0 2 ∞ 4 -2 ∞ ∞ 0 2 1
5 0 ∞ ∞ ∞ 0 ∞ 5 0 ∞ ∞ ∞ 0 3
6 ∞ 9 11 ∞ 19 0 6 ∞ 9 11 ∞ 19 0

Table 3.3 – Algorithme 6 : étape 0 Table 3.4 – Algorithme 6 : étape 1

Sommets 1 2 3 4 5 6 Sommets 1 2 3 4 5 6
1 0 ∞ ∞ ∞ ∞ 3 1 0 ∞ ∞ ∞ ∞ 3
2 ∞ 0 15 1 11 ∞ 2 ∞ 0 15 1 11 ∞
3 ∞ ∞ 0 16 ∞ ∞ 3 ∞ ∞ 0 16 ∞ ∞
4 -2 ∞ ∞ 0 2 1 4 -2 ∞ ∞ 0 2 1
5 0 ∞ ∞ ∞ 0 3 5 0 ∞ ∞ ∞ 0 3
6 ∞ 9 11 10 19 0 6 ∞ 9 11 10 19 0

Table 3.5 – Algorithme 6 : étape 2 Table 3.6 – Algorithme 6 : étape 3

Le premier tableau (3.3) représente la matrice initiale qui comporte les distances di-
rectes entre chaque deux sommets i et j (c’est la représentation matricielle du graphe).
Chaque étape de l’application de l’Algorithme 6 correspond à la valeur de z (c’est-à-dire,
z = 1 à l’étape 1, z = 2 à l’étape 2, etc). Pour chaque étape, la valeur de x change de 1 à
6 (sachant qu’il y a 6 sommets), et pour chaque valeur de x on change la valeur de y de
1 à 6.
Prenant l’exemple de la première itération, c’est-à-dire, le premier tableau (étape 1).
CHAPITRE 3. PROBLÈME DU PARCOURS DE GRAPHES 36

Sommets 1 2 3 4 5 6 Sommets 1 2 3 4 5 6
1 0 ∞ ∞ ∞ ∞ 3 1 0 ∞ ∞ ∞ ∞ 3
2 -1 0 15 1 3 2 2 -1 0 15 1 3 2
3 14 ∞ 0 16 18 17 3 14 ∞ 0 16 18 17
4 -2 ∞ ∞ 0 2 1 4 -2 ∞ ∞ 0 2 1
5 0 ∞ ∞ ∞ 0 3 5 0 ∞ ∞ ∞ 0 3
6 8 9 11 10 12 0 6 8 9 11 10 12 0

Table 3.7 – Algorithme 6 : étape 4 Table 3.8 – Algorithme 6 : étape 5

Sommets 1 2 3 4 5 6 Sommets 1 2 3 4 5 6
1 0 12 14 13 15 3 1 0 6 6 2 4 1
2 -1 0 13 1 3 2 2 4 0 6 2 4 1
3 14 26 0 16 18 17 3 4 6 0 3 4 1
4 -2 10 12 0 2 1 4 4 6 6 0 4 1
5 0 12 14 13 0 3 5 5 6 6 2 0 1
6 8 9 11 10 12 0 6 4 6 6 2 4 0

Table 3.9 – Algorithme 6 : étape 6 Table 3.10 – Algorithme 6 : matrice Pred

À l’étape 1, la valeur de z est égale à 1, la valeur de x va varier de 1 à 6 et la valeur de y

va varier de 1 à 6 pour chaque valeur de x.

• On va utiliser la formule Dist(x, z) + Dist(z, y) < Dist(x, y).

• La première valeur de la combinaison sera z = 1, x = 1, y = 1. La formule n’est pas

réalisable, alors on incrémente la valeur de y. L’algorithme continu de cette manière
jusqu’à ce que la valeur de x atteigne la valeur 6 alors on incrémente z.

• Dans l’étape 1, les seules situations où la formule est réalisée, c’est dans le cas où
x = 4, y = 6 et x = 5, y = 6. L’application de la formule se manifeste par la présence
de deux cases rouges dans la matrice. Cela signifie que les deux valeurs ont changé
car leurs valeurs précédentes étaient plus grandes.

• L’étape suivante z = 2 (le tableau de l’étape 2) où on refait la même chose c’est-à-

dire, on varie les valeurs de x et y (comme expliqué à l’étape précédente).

• À chaque changement dans la matrice, on retient l’indice de l’élément intermédiaire

qui a permet ce changement-là, c’est-à-dire, la valeur de z. Cet indice sera placé
dans la case correspondante de la matrice P red.

3.5 Exercices
Exercice 1
Calculer le plus court chemin en partant du sommet D vers le sommet A et en utilisant
l’algorithme de Dijkstra du graphe suivant :
CHAPITRE 3. PROBLÈME DU PARCOURS DE GRAPHES 37

Exercice 2

PB B A S I F E
PB 0/15/2 0/5/4
B 15/0/2 8/0/3 22/0/2
A 5/0/4 0/10/3 5/0/3 15/0/4
S 0/5/3 0/15/2 5/0/5
I 15/0/2 8/0/6
F 0/10/2 0/15/4 0/5/5 0/8/6 0/5/6
E 5/0/6

Les sept pays, les Pays-Bas, la Belgique, l’Allemagne, la Suisse, l’Italie, l’Espagne et la
France, produisent, exportent, importent et consomment le beurre. Certains de ces pays
surproduisent et sont obligés d’exporter, d’autres doivent importer. Le gouvernement de
chaque pays décide de créer un organisme dont le rôle est d’aider les échanges. Pour
cela, dans un premier temps, chaque pays passe un accord commercial avec chacun de
ses voisins fixant des aides pour l’exportation vers des pays déficitaires et des taxes pour
l’exportation vers des pays surproducteurs. Les données sont résumées dans le tableau 1.
Les nombres dans chaque case du tableau représentent les taxes, les aides et les coûts de
transport sous forme : Taxe/aide/coût (calcule : taxe-aide+coût).

• Modéliser le problème sous forme d’un problème du plus court chemin dans un
graphe orienté. Que remarque-t-on ?

• La commission Européenne propose de réduire de 15 à 10 l’aide à exportation de la

France vers l’Allemagne. Quelle en est la raison ?

• Résoudre le problème de l’exportation du beurre des Pays-Bas vers l’Espagne.

Chapitre 4

Problème des flots

Sommaire
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Recherche du flot maximum . . . . . . . . . . . . . . . . . . . . 40
4.4 Coupe, coupe minimale et flot maximum . . . . . . . . . . . . 44
4.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.1 Introduction
L’optimisation des flots dans les réseaux est un axe important de la théorie des graphes.
Cela concerne la circulation de matière sur les arcs comme par exemple :
• Réseau électrique : la source est la centrale électrique, le puits est l’endroit où
l’électricité est consommée, les arcs sont les lignes électriques (l’intensité du courant
électrique supportée par la ligne est la capacité) et le flot est la quantité du courant.

• Réseau de distribution de l’eau : la source est le barrage, le puits est l’endroit où

l’eau est rejetée, les arcs sont les canalisations (le débit maximal de chaque canal
représente la capacité) et le flot est la quantité d’eau.

• Réseau routier : la source est l’endroit de départ des voitures, le puits est l’endroit
de destination des voitures, le flot est la quantité de voitures et les arcs sont les
routes (la quantité de voiture qui passe par chaque route est la capacité).

4.2 Définitions
Définition 15 Réseau de transport
Soit R = (N, A) un réseau de transport tel que :
• Un réseau de transport est un graphe orienté, connexe, sans boucle et valué.

• Il existe deux sommets particuliers :

38
CHAPITRE 4. PROBLÈME DES FLOTS 39

• Racine : un sommet qui a que des arcs sortants et qui est le départ de notre
réseau.
• Puits : un sommet qui a que des arcs entrants et qui est l’arrivée de notre
réseau.

• À chaque arc e entre deux sommets i et j (i, j ∈ A) est associé un nombre positif
c(e) appelée capacité.

Figure 4.1 – Exemple de réseau de transport

L’exemple de la Figure 4.1 représente un réseau de transport avec S la racine et R le

puits. Chaque arc possède une capacité représentée par la valeur de l’arc correspondant.

Définition 16 Flot
Un flot F dans un réseau de transport, associe à chaque arc e une quantité f (e) qui
représente la quantité de flux qui passe par cet arc en provenance de la source vers le
puits.

Le flot est sujet à des restrictions (règles) et également des propriétés qui sont les sui-
vantes :

• Flot conservatif : le flot est conservatif s’il obéit à la loi de Kirchoff (la loi des
nœuds) : la somme des quantités de flux sur les arcs entrant dans un sommet doit
être égale à la somme des quantités de flux sur les arcs sortant de ce même sommet.

• Flot compatible : un flot est compatible dans un réseau de transport si pour tout
arc e le flux qui le traverse ne dépasse pas sa capacité :

∀ e ∈ A (e = (u, v)/u, v ∈ N ), 0 ≤ f (e) ≤ c(e).

• Arc saturé : soit e un arc allant du sommet u au sommet v. On dit que l’arc e est
saturé si et seulement si le flux qui le traverse est égal à sa capacité (f (e) = c(e)).

• Flot complet : un flot est complet si pour tout chemin allant de la source au puits
il y a au moins un arc saturé.

• Une chaine : un chemin qui comporte des arcs dans le sens direct et des arcs dans
le sens inverse.
CHAPITRE 4. PROBLÈME DES FLOTS 40

Figure 4.2 – Exemple de réseau de transport

La Figure 4.2 représente un exemple de réseau de transport dont le flot est conservatif,
compatible et qui comporte des flots complets.

• La capacité est la valeur à gauche et le flux est la valeur à droite. Par exemple, l’arc
e entre A et C : c(e) = 4 et f (e) = 2.

• Le réseau de la figure est compatible car pour tout arc le flux est inférieur à la
capacité.

• L’arc e entre B et D est un arc saturé, car sa capacité est égale à son flux.

• Le chemin A, B, D, F est chemin saturé avec un flot complet car il contient un arc
saturé (l’arc entre B et D).

• Pour tout sommet du transport, le flux entrant est égal au flux sortant (le flot
conservatif). Par exemple, le flux entrant du sommet B est 2 et le flux sortant du
sommet B est 2 (1 + 1).

4.3 Recherche du flot maximum

La recherche du flot maximum consiste à trouver la quantité maximum de flot à
acheminer de la source S vers le puits P en tenant compte des capacités de transport. Nous
allons étudier dans cette section l’algorithme de Ford-Fulkerson (voir l’Algorithme 7)
qui permet la recherche du flot maximum dans un réseau de transport. Afin de mieux
comprendre l’algorithme 7 nous l’appliquerons sur un exemple étape par étape.
CHAPITRE 4. PROBLÈME DES FLOTS 41

Algorithme 7 : Algorithme Ford-Fulkerson

1 h ! Entrée : R(N, A, c)
2 Sortie : F lotM ax
3 Initialisation :
4 Initialiser le flot f à 0 sur tous les arcs ;
5 F lotM ax = 0 ;
6 Calcule :
7 tant que Il existe un chaîne ou un chemin améliorant faire
8 Chercher une chemin ou une chaîne améliorante µ de r à p ;
9 si µ existe alors
10 Calculer ε ;
11 Augmenter f sur les arcs (sens direct) de ε+ ;
12 Diminuer f sur les arcs (sens indirect) de ε− ;
13 F lotM ax = F lotM ax + ε ;

Le fonctionnement de l’Algorithme 7 consiste à faire passer un flot compatible dans le

réseau puis l’améliorer jusqu’à ce qu’on obtienne un flot complet. Pour améliorer le flot,
il faut trouver un chemin ou une chaîne de S à P dont les arcs dans le sens direct n’ont
pas atteint leur limite (f (e) < c(e)) et les arcs dans le sens indirect ont un flux non nul
(f (u) > 0). Cette chaîne (chemin) est dite améliorante.
Le flot peut être amélioré de ε = min(ε+ , ε− ) avec ε+ = min(c(e) − f (e)/e ∈ C + ) et
ε− = min(f (e)/e ∈ C − ) en rajoutant ε au flot des arcs C + et en retranchant ε au flot
des arcs C − . Autrement dit, dans le cas où il y a un chemin ε− = 0 et dans le cas de la
présence d’une chaîne (où on parcourt des arcs dans le sens inverse) la valeur de ε− sera
non null.
Exemple
Nous allons appliquer l’algorithme 7 sur un exemple de chemin routier (voir la Figure 4.3),
où :

• Les villes sont représentées par des sommets.

• Les autoroutes sont représentées par des arcs.

• Les capacités des autoroutes en matière de véhicules sont indiquées sur les arcs.

Figure 4.3 – État initial Figure 4.4 – État final

CHAPITRE 4. PROBLÈME DES FLOTS 42

Figure 4.5 – Chemin 1 Figure 4.6 – Chemin 2

Figure 4.7 – Chemin 3 Figure 4.8 – Chemin 4

Figure 4.9 – Chemin 5 Figure 4.10 – Chemin 6

Figure 4.11 – Chemin 7 Figure 4.12 – Chaîne 1

Les Figures 4.5, 4.6, 4.7, 4.8, 4.9, 4.10, 4.11 et 4.12 représentent la recherche du flot
maximum en appliquant l’algorithme 7. L’application sur l’exemple de la Figure 4.3 est
de la manière suivante :

• Les flots du graphe ainsi que le flot maximum (F lotM ax) avant l’application de
l’algorithme sont initialisés à 0.

• {s, a, d, t} : est le premier chemin sélectionné pour l’amélioration du flot et la satu-

ration des arcs (voir la Figure 4.5). Pour calculer ε, il suffit de soustraire le flux de
chaque arc de sa capacité et de prendre la valeur minimum :
CHAPITRE 4. PROBLÈME DES FLOTS 43

∀ e (e arc appartient au chemin) ε = min(c(e) − f (e)). Dans l’exemple, on a 3 arcs

le premier avec la valeur de 30 − 0 = 30, le second avec la valeur 13 − 0 = 13 et le
dernier avec valeur 7 − 0 = 7. Donc la valeur de ε qui va nous permettre d’améliorer
le chemin est la valeur minimale, c’est-à-dire, 7. La nouvelle valeur du flot maximum
est alors F lotM ax = F lotM ax + 7 = 14.

• {s, a, c, e, t} : est le chemin sélectionné pour être amélioré et ainsi augmenter le flot
maximum (voir Figure 4.6). La valeur permettant l’amélioration est calculée de la
même manière que précédemment : ε = min(30 − 7, 11 − 0, 8 − 0, 7 − 0) = 7. La
nouvelle valeur du flot maximum est alors F lotM ax = F lotM ax + 7 = 14.

• {s, a, d, b, c, f, t} : est le chemin sélectionné pour être amélioré et ainsi augmenter le

flot maximum (voir Figure 4.7). La valeur permettant l’amélioration est calculée de
la même manière que précédemment : ε = min(30−14, 13−7, 2−0, 26−0, 22−0, 27−
0) = 2. La nouvelle valeur du flot maximum est alors F lotM ax = F lotM ax+2 = 16.

• {s, a, b, c, f, t} : est le chemin sélectionné pour être amélioré et ainsi augmenter le flot
maximum (voir Figure 4.8). La valeur permettant l’amélioration est calculée de la
même manière que précédemment : ε = min(30−16, 8−0, 26−2, 22−2, 27−2) = 8.
La nouvelle valeur du flot maximum est alors F lotM ax = F lotM ax + 8 = 24.

• {s, b, c, f, t} : est le chemin sélectionné pour être amélioré et ainsi augmenter le flot
maximum (voir Figure 4.9). La valeur permettant l’amélioration est calculée de la
même manière que précédemment : ε = min(1 − 0, 26 − 10, 22 − 10, 27 − 10) = 1.
La nouvelle valeur du flot maximum est alors F lotM ax = F lotM ax + 1 = 25.

• {s, f, t} : est le chemin sélectionné pour être amélioré et ainsi augmenter le flot
maximum (voir Figure 4.10). La valeur permettant l’amélioration est calculée de la
même manière que précédemment : ε = min(2 − 0, 27 − 11) = 2. La nouvelle valeur
du flot maximum est alors F lotM ax = F lotM ax + 2 = 27.

• {s, a, c, f, t} : est le chemin sélectionné pour être amélioré et ainsi augmenter le flot
maximum (voir Figure 4.11). La valeur permettant l’amélioration est calculée de la
même manière que précédemment : ε = min(30 − 24, 11 − 7, 22 − 11, 27 − 13) = 4. La
nouvelle valeur du flot maximum est alors F lotM ax = F lotM ax + 4 = 31. C’est le
dernier chemin possible à améliorer dans notre réseau de transport (flot complet).
Il est maintenant nécessaire de chercher une chaîne avec des arcs dans le sens inverse
pour augmenter le flot maximum.

• {s, a, d, e, c, f, t} : est la seule chaine disponible qui nous permet d’améliorer le flot
maximum (voir Figure 4.12). Pour calculer ε le principe est le suivant :

• Calculer ε+ comme pour les chemins.

• Calculer ε− qui est le flot minimum de tous les arcs parcourus dans leur sens
inverse.
• Calculer ε en faisant le minimum entre ε+ et ε− .

Ajouter la valeur de ε aux arcs parcours dans leur sens et soustraire ε des arcs
parcourus dans leur sens inverse. La valeur permettant l’amélioration est calculée
CHAPITRE 4. PROBLÈME DES FLOTS 44

de la même manière que précédemment : ε = min(30−28, 13−9, 1−0, 7, 22−15, 27−

17) = 1. La nouvelle valeur du flot maximum est alors F lotM ax = F lotM ax + 1 =
32.

La Figure 4.4 représente la version finale du réseau de transport, avec en gras les arcs
saturés (par exemple, l’arc entre a et c). Pour vérifier que l’application de l’Algorithme 7
est faite correctement et que le flot maximum est correcte, il est nécessaire de vérifier la
loi de conservation de flux. Le flot maximum est de 32 qui est la somme des flots des arcs
sortant de la source s (ou la somme des flots des arcs entrant dans t).

4.4 Coupe, coupe minimale et flot maximum

Définition 17 Soit R = (N, A) un réseau de transport et soit S un sous-ensemble de N
(S ⊂ N ). On appelle une coupe associée à S (notée δ(S)) l’ensemble des arcs (i, j) tels
que i ∈ S et j ∈ N et j ̸∈ S.

• L’ensemble S doit contenir au minimum un sommet (la racine) et ne doit pas conte-
nir le puits.

• La capacité d’une coupe δ(S) est définie par :

P
C(δ(S)) = (i,j)∈δ(S) c(i, j)

La Figure 4.13 montre un exemple de coupe S = {1, 3, 4} avec δ(S) = {(1, 2), (1, 5), (3
, 2), (4, 5)}.

Figure 4.13 – Exemple de coupe

Théorème La valeur maximum d’un flot réalisable entre s (la source) et t (le puits) est
égale à la capacité minimum d’une coupe séparant s et t.

La Figure 4.14 représente l’exemple d’une coupe minimale δ(S) = {(d, t), (d, e), (a, c), (s, f ), (b, c)}
(S = {s, a, b, d}) avec la capacité c(δ(S)) = F lotM ax = 32.
CHAPITRE 4. PROBLÈME DES FLOTS 45

Figure 4.14 – Exemple de coupe minimale

4.5 Exercices
Exercice 1
Calculer le flot maximum pour le réseau suivant :

Exercice 2
Soit le réseau suivant :

• Trouver le flot maximum, en utilisant à chaque étape un chemin améliorant d’une

capacité maximale.
CHAPITRE 4. PROBLÈME DES FLOTS 46

• Trouver une coupe minimale

• Le réseau subit des changements indiqués plus bas. Essayez de trouver, dans chaque
cas, le flot maximum sans beaucoup d’efforts, et surtout sans recommencer l’algo-
rithme dès le début (indication : la connaissance de la coupe minimum peut être
utile).

• La capacité de l’arc "ac" diminue jusqu’à 8.

• La capacité de l’arc "cd" diminue jusqu’à 10.
• La capacité de l’arc "ac" augmente jusqu’à 12, celle de l’arc "ad" jusqu’à 16,
et l’arc "de" disparaît.
Chapitre 5

Programmation linéaire

Sommaire
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.2 Notions de bases . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.3 Méthodes de résolutions . . . . . . . . . . . . . . . . . . . . . . 51
5.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

La programmation linéaire est une partie du vaste domaine de la recherche opération-

nelle. Son importance réside dans sa capacité a représenter plusieurs problèmes, aussi bien
académiques que réel. Dans ce chapitre nous aborderons le principe de la programmation
linéaire, la modélisation, les méthodes de résolution ainsi que quelques applications.

5.1 Introduction
La recherche opérationnelle est un ensemble de méthodes (algorithmiques, mathéma-
tiques, modélisation, etc). Elle permet de prendre des décisions optimales (ou proches de
l’optimum) concernant des problèmes complexes qui ont pour objectif la maximisation
d’un profit ou de la minimisation d’un coût. Dans ce qui va suivre, on présente quelques
exemples d’applications de la recherche opérationnelle :

• Comment aller le plus vite d’Orléans à Berlin, en voiture ?

• Comment ordonnancer les tâches d’un projet en fonction de la main-d’œuvre, tout

en minimisant sa durée ?

• Comment investir ses 1000 euros d’économie de sorte à maximiser le profit obtenu
après deux ans ?

• Trouver un chemin entre deux villes (plus court chemin dans un graphe).

• Envoi d’un maximum d’informations dans un réseau (problème du flot maximum).

En recherche opérationnelle (RO), modéliser un problème consiste à identifier les éléments

suivants :

47
CHAPITRE 5. PROGRAMMATION LINÉAIRE 48

• Les variables intrinsèques (inconnues).

• Les contraintes auxquelles sont soumises ces variables.
• L’objectif visé par l’optimisation.
Dans un problème de programmation linéaire (PL), les contraintes et l’objectif sont des
fonctions linéaires des variables. On parle aussi de programme linéaire.

5.2 Notions de bases

Un problème de programmation linéaire est un problème d’optimisation où la fonction
objectif et les contraintes sont toutes linéaires. L’objectif de cette section est d’apprendre
à modéliser les problèmes réels sous forme de programme linéaire et les résoudre avec des
méthodes spécifiques. De nombreux problèmes réels peuvent être exprimés comme des
programmes linéaires et peuvent être résolus efficacement par certains algorithmes (par
exemple, la méthode du simplexe).
Définition 18 PL
Soit un problème exprimé en programme linéaire, alors on a :
• Variables réelles :

x1 , x2 ...xn

• Fonction objectif à optimiser (minimum ou maximum) :

Min/Max F = c1 x1 + c2 x2 + ... + cn xn

• Contraintes linéaires (égalités ou inégalités) :



 a11 x1 + a12 x2 + ... + a1n xn ≤ b1

a21 x1 + a22 x2 + ... + a2n xn ≥ b2



... (5.1)

am1 x1 + am2 x2 + ... + amn xn = bm




x , x , ..., x ≥ 0 (les variables doivent tre toujours positives)
1 2 n

La solution est toute affectation des variables qui respecte les contraintes. La solution
optimale est la solution qui optimise (maximise ou minimise) la fonction objectif.

Exemple
Considérons un agriculteur qui possède des terres, de superficie égale à H hectares,
dans lesquelles il peut planter du blé et du maïs. l’agriculteur possède une quantité E
d’engrais et I d’insecticide. Le blé nécessite une quantité Eb d’engrais par hectare et Ib
d’insecticide par hectare. Les quantités correspondantes pour le maïs sont notées Em et
Im. Soit P b le prix de vente du blé et P m celui du maïs. Si l’on note par xb et xm le
nombre d’hectares à planter en blé et en maïs, comment exprimer le fait que l’agriculteur
souhaite maximiser son gain, tout en restant dans les limites de ses ressources.
CHAPITRE 5. PROGRAMMATION LINÉAIRE 49

Solution
L’exemple peut être résolu par la programmation linéaire. C’est un problème de maxi-
misation car l’agriculteur cherche à maximiser son gain par la vente de blé et le maïs. Sa
modélisation est la suivante :

• C’est un problème de maximisation de gains

• La fonction objectif

M ax F = Pb xb + Pm xm (Pi est le prix et xi estlaquantit).

• Les contraintes


 xb + x m ≤ H

E x + E x ≤ E
b b m m
(5.2)


 Ib xb + Im xm ≤ I
xb , xm ≥ 0


Forme standard et forme canonique

Définition 19 Forme canonique
La forme d’un programme linéaire est dite sous forme canonique lorsque toutes ses contraintes
sont des inégalités inférieures (respectivement supérieures) dans le cas d’une maximisation
(respectivement minimisation) et toutes ses variables sont non-négatives :

• fonction objectif :

max F = c1 x1 + c2 x2 + ... + cn xn

• des contraintes :


a11 x1 + a12 x2 + ... + a1n xn ≤ b1

a21 x1 + a22 x2 + ... + a2n xn ≤ b2



... (5.3)

am1 x1 + am2 x2 + ... + amn xn ≤ bm





x , x , ..., x ≥ 0
1 2 n

• n variables, m contraintes

Définition 20 Forme standard

La forme d’un programme linéaire est dite sous forme standard lorsque toutes ses contraintes
sont des égalités et toutes ses variables sont non-négatives :

• fonction objectif :

max/min F = c1 x1 + c2 x2 + ... + cn xn
CHAPITRE 5. PROGRAMMATION LINÉAIRE 50

• des contraintes :

a11 x1 + a12 x2 + ... + a1n xn = b1


a21 x1 + a22 x2 + ... + a2n xn = b2



... (5.4)

am1 x1 + am2 x2 + ... + amn xn = bm





x , x , ..., x ≥ 0
1 2 n

• n variables, m contraintes

Remarque :
Il est possible d’aller d’une forme canonique à une forme standard et inversement : théo-
rème d’équivalence des formes standard et canonique ("Tout programme linéaire
peut s’écrire sous forme standard et sous forme canonique").
• Une contrainte d’inégalité aT x ≤ b peut être transformée en égalité par l’introduc-
tion d’une variable d’écart s :
(
aT x + s = b
(5.5)
s≥0

• Une contrainte d’égalité aT x = b peut être remplacée par deux inégalités :

(
aT x ≤ b
(5.6)
−aT x ≤ −b

Exemple
Une société produit de la peinture d’intérieur et d’extérieur à partir de deux produits
de base M 1 et M 2. La demande maximum en peinture d’intérieur est de 2 tonnes par
jour. La production de peinture d’intérieur ne dépasse que d’une tonne celle d’extérieur
(voir le Tableau 5.1).

Qualité disponible par tonne

Qualité disponible par jour
Extérieure Intérieure
M1 6 4 24
M2 1 2 6
profit par tonne 5 4

Table 5.1 – Exemple de modélisation

Solution
Les variables du problèmes sont :
• x1 : tonnes de peinture d’extérieur produites par jour.
CHAPITRE 5. PROGRAMMATION LINÉAIRE 51

• x2 : tonnes de peinture d’intérieur produites par jour.

Forme canonique Forme standard
La fonction objectif est : La fonction objectif est :

• max F = 5x1 + 4x2 • max F = 5x1 + 4x2

Les contraintes sont : Les contraintes sont :

 

 6x1 + 4x2 ≤ 24 
 6x1 + 4x2 + s1 = 24
 
x1 + 2x2 ≤ 6 x1 + 2x2 + s2 = 6

 

 
x2 ≤ 2 (5.7) x2 + s 3 = 2 (5.8)
 
x2 − x1 ≤ 1 x2 − x1 + s 4 = 1

 


 


x1, x ≥ 0 
x1, x + s = 0
2 2 5

5.3 Méthodes de résolutions

Selon le nombre de variables du problème il y a des méthodes qui sont faisables et
d’autres non. Nous aborderons dans les sections suivantes deux méthodes : méthode gra-
phique et méthode du simplexe. Il y a plusieurs types de solutions possibles lors de la
résolution d’un programme linéaire, parmi lesquelles on cite : solutions réalisable et solu-
tion optimale.

Définition 21 Solution réalisable

Une solution réalisable si d’un programme linéaire est une solution qui satisfait toutes les
contraintes du problème en question (y compris la contrainte de positivité). L’ensemble
des solutions réalisables est appelé le domaine des solutions réalisables : D.

Définition 22 Solution optimale

Une solution optimale sj d’un programme linéaire est une solution qui est réalisable et qui
maximise (minimise) la fonction objectif. En d’autre termes :

∀si ∈ D, F (sj ) ≥ F (si ) / M ax F (5.9)

∀si ∈ D, F (sj ) ≤ F (si ) / M in F (5.10)

Il existe plusieurs méthodes pour la résolution des problèmes de programmation li-

néaire :

• Résolution graphique

• La méthode su simplexe

• La méthode des deux phases

• ...
CHAPITRE 5. PROGRAMMATION LINÉAIRE 52

5.3.1 Méthode graphique

La méthode graphique fonctionne uniquement si le programme linéaire comporte deux
variables. Cette méthode peut être utilisée pour mieux comprendre la méthode du sim-
plexe car elle représente la manière de calculer d’une valeur optimale.
Les contraintes où apparaissent des inégalités correspondent géométriquement à des demi-
plans. L’intersection de ces demi-plans représente l’ensemble des variables satisfaisant
toutes les contraintes (l’ensemble des solutions réalisables). Cet ensemble représente un
polygone convexe et à son sommet la solution optimale (si elle existe).

La méthode graphique comporte 4 étapes pour la résolution d’un programme linéaire :

1. Représenter graphiquement les droites des equations des contraintes et déterminer
le demi-plan fermé satisfaisant chaque contrainte.
2. Trouver la région des solutions réalisables qui est l’intersection entre tous les demi-
plans satisfaisant les contraintes.
3. Dessiner le vecteur de coûts de la fonction objectif.
4. Remplacer les cordonnées de chaque point du polygone (des solutions réalisables)
dans la fonction objectif afin de trouver la solution optimale (ou les solutions opti-
males).

Exemple
Afin d’expliquer le fonctionnement de la méthode graphique, nous allons utiliser le
programme linéaire suivant :

M ax F = 2x1 + x2 (5.11)



 x1 + 2x2 ≤ 6

x + x ≤ 4
1 2
(5.12)


 x1 ≤ 3
x1 , x2 ≥ 0


Solution
L’ensemble des solutions réalisables est l’ensemble des points de l’espace qui vérifient
les contraintes. Les figures suivantes représentent l’application de la méthode graphique :
• Il y a deux variables dans notre problème, donc on aura besoin de deux axes.
• Dans la Figure 5.1, il y a la représentation de trois contraintes. La première contrainte
est celle de la positivité de x1 (on supprime toutes les valeurs négatives de x1 ). La
seconde contrainte est celle de la positivité de x2 (on supprime toutes les valeurs
négatives de x2 ). La troisième contrainte est celle de x3 ≤ 3, où on trace une droite
(passant par la valeur x1 = 3) et on ignore les valeurs où x1 > 3.
CHAPITRE 5. PROGRAMMATION LINÉAIRE 53

• Dans la Figure 5.2 on trace la droite x1 + 2x2 = 6 de la contrainte correspondante

en ignorant les valeurs supérieures à 6.

• Dans la Figure 5.3 on trace la droite x1 + x2 = 4 de la contrainte correspondante en

ignorant les valeurs supérieures à 4.

• Dans la Figure 5.4 il y a la représentation de l’ensemble des solutions réalisables S.

qui est le résultat de l’intersection des différentes droites des différentes contraintes.
Cet ensemble représente, de point de vue géométrique, un polygone avec les points
A, B, C, D et E (voir la Figures 5.5 et 5.6). Ces points seront les meilleures solutions
possibles dont la solution optimale sera choisie.

• Afin de trouver la solution optimale, il suffit de remplacer les coordonnées des points
précédentes (première coordonnée représente le x1 et la seconde coordonnée repré-
sente le x2 ) au niveau de la fonction objectif. Le point qui permet d’obtenir la
meilleure valeur pour la fonction objectif sera le point de la solution optimale. Par
exemple, en remplaçant le point A dans la fonction objectif on obtient F = 0.

• Dans cet exemple la solution optimale correspond à x1 = 3 et x2 = 1 (les coordonnées

du point D) et qui donne la valeur de F = 7.

Figure 5.1 – Étape 1 Figure 5.2 – Étape 2

Figure 5.3 – Étape 3 Figure 5.4 – Étape 4

CHAPITRE 5. PROGRAMMATION LINÉAIRE 54

Figure 5.5 – Étape 5 Figure 5.6 – Étape 6

5.3.2 Méthode du simplexe

La méthode du simplexe a été développée par G.Dantzig, et qui est un algorithme
de résolution de programme linéaire. La méthode est facile à comprendre, à implémenter
et efficace pour la résolution d’un PL même pour un nombre important de variables ou
de contraintes. Il existe plusieurs manières d’appliquer la méthode du simplexe. Dans ce
cours nous allons utiliser l’une des méthodes les plus simples : la méthode du pivot.

Exemple
Afin de mieux comprendre son implémentation, nous allons utiliser l’exemple suivant :

M ax F = 5x1 + 4x2 + 3x3 (5.13)



 2x1 + 3x2 + x3 ≤ 5

4x + x + 2x ≤ 11
1 2 3
(5.14)


 3x1 + 4x2 + 2x3 ≤ 8
x1 , x2 , x3 ≥ 0


Solution
La première étape consiste à transformer la forme du PL d’une forme canonique à une
forme standard (c’est-à-dire des inégalités à des égalités). Les variables d’écarts indiquent
les ressources disponibles et les variables initiales fournissent les informations sur le pro-
blème (production, vente, etc). Cette transformation est faite en ajoutant les variables
d’écarts ei :

M ax F = 5x1 + 4x2 + 3x3 (5.15)



 2x1 + 3x2 + x3 + e1 = 5

4x + x + 2x + e = 11
1 2 3 2
(5.16)


 3x1 + 4x2 + 2x3 + e3 = 8
x1 , x2 , x3 , e1 , e2 , e3 ≥ 0

CHAPITRE 5. PROGRAMMATION LINÉAIRE 55

Principe : on part d’une solution de base, par exemple le point 0, et à chaque étape
de l’algorithme on passe à un autre sommet qui améliore la solution et par conséquent la
fonction objectif. Dans notre exemple, si on part du point 0 on aura :
X : (x1 , x2 , x3 , e1 , e2 , e3 ) = (0, 0, 0, 5, 11, 8)
xi : sont les variables hors base (leur valeur est toujours égale à 0).
ei : sont les variables de base (leur valeur est toujours différente de 0).

Le Tableau 5.2 regroupe les variables de base, les variables hors base, et toutes les
informations nécessaires pour le calcul de la méthode du simplexe.

x1 x2 x3 e1 e2 e3 B
e1 2 3 1 0 0 0 5
e2 4 1 2 0 1 0 11
e3 3 4 2 0 0 1 8
F 5 4 3 0 0 0 0

Table 5.2 – Représentation du PL sous forme de tableau

Dans chaque itération, on doit déterminer le pivot qui va nous permettre de calculer
la nouvelle valeur du tableau. Dans ce type d’itération, une variable hors base devient une
variable de base et inversement. Le pivot est l’intersection entre une ligne i et une colonne
j (il est nécessaire de choisir d’abord la colonne avant de choisir la ligne). L’algorithme
s’arrêtera une fois que les valeurs au niveau de la ligne de F soient négatives ou nulles.

Itération 1
On calcule le premier pivot et le tableau correspondant comme suit :
• La colonne j (c’est-à-dire la variable hors base qui va devenir de base) est choisie
selon la valeur de la variable ayant le meilleur coefficient (qui doit être positif).
Dans notre exemple et en regardant la dernière ligne (celle de F ), on remarque que
la meilleure valeur (entre les xi et les ei ) pour augmenter la fonction objectif est
celle de 5 (correspondante à la variable hors base x1 ). Pour cette raison, la colonne
j sera la colonne de la variable x1 .

• La ligne i (c’est-à-dire la variable de base qui va devenir hors base) est choisie selon
la valeur minimale de la division de chaque valeur de B par la valeur correspondante
dans la colonne j (choisie précédemment). Dans notre exemple, on aura les valeurs
suivantes :

• 5/2 = 2.5
• 11/4 = 2.75
• 3/8 = 2.66

En se basant sur ces valeurs, la ligne correspondante à la valeur minimale est celle
de e1 (c’est-à-dire, 2.5). Par conséquent, la ligne i est la ligne de la variable de base
e1 .
CHAPITRE 5. PROGRAMMATION LINÉAIRE 56

• Le pivot est l’intersection de la ligne i et la colonne j, c’est-à-dire, la valeur 2.

Le Tableau 5.3 résume le choix du pivot et sa valeur.

Table 5.3 – Itération 1 : choix du pivot

Une fois le pivot calculé, les modifications à faire (avant de calculer le nouveau tableau)
sont les suivantes :

• Les valeurs de la ligne du pivot sera divisé par la valeur du pivot.

• Les valeurs de la colonne du pivot seront 0.

• La variable x1 (devenue variable de base) prend la place de la variable e1

• Le Tableau 5.4 représente ces changements.

x1 x2 x3 e1 e2 e3 B
x1 2/2 3/2 1/2 0/2 0/2 0/2 5/2
e2 0 1 2 0 1 0 11
e3 0 4 2 0 0 1 8
F 0 4 3 0 0 0 0

Table 5.4 – Itération 1 : transformation

Pour calculer les valeurs des autres éléments du tableau, il est nécessaire d’utiliser la
formule suivante :

• On utilisera le Tableau 5.3 pour calculer les valeurs.

• Supposons qu’on souhaite calculer la valeur de la case (e2 , x2 ). La formule permettant

cela est : (e2 , x2 )−(((e1 , x2 )×(e2 , x1 ))/(e1 , x1 )), autrement dit la valeur de la nouvelle
case sera : 1 − ((3 × 4)/2) = −5.

• Les autres valeurs seront calculées de la même manière. Le Tableau 5.5 montrent
plus en détail ce calcul. Le résultat sera utilisé comme tableau de départ pour choisir
le nouveau pivot et calculer le nouveau tableau.
CHAPITRE 5. PROGRAMMATION LINÉAIRE 57

Table 5.5 – Itération 1 : calcul

Itération 2
Dans cette itération, on utilisera le dernier tableau calculé (voir Tableau 5.5) pour
choisir le nouveau pivot en choisissant la colonne j et la ligne i (la même méthode que
l’itération précédente sera utilisée). Le pivot est choisi de la même manière que l’étape
précédente (voir Tableau 5.6).

x1 x2 x3 e1 e2 e3 B
x1 1 1.5 0.5 0.5 0 0 2.5
e2 0 -5 0 -2 1 0 1
e3 0 -0.5 0.5 -1.5 0 1 0.5
F 0 -3.5 0.5 -2.5 0 0 -1.25

Table 5.6 – Itération 2 : Choix du pivot

Une fois le pivot choisi, on applique les modifications avant de calculer le nouveau
tableau de solutions (c’est-à-dire, divisé la ligne du pivot par le pivot et mettre à 0 sa
colonne). Le Tableau 5.7 montre cette application avant le calcul du reste des valeurs.
La suite de l’étape est le calcul des nouvelles valeurs en utilisant la formule de la
première étape. La seule différence avec la première étape est la position du pivot ainsi
que sa valeur. Le Tableau 5.8 montre le résultat du calcul des nouvelles solutions. En
analysant le Tableau 5.8, on remarque qu’il n’y a plus de coefficient positif à la ligne F .
Par conséquent, il n’y a plus de choix à faire et donc le résultat final est le suivant :
CHAPITRE 5. PROGRAMMATION LINÉAIRE 58

x1 x2 x3 e1 e2 e3 B
x1 1 1.5 0 0.5 0 0 2.5
e2 0 -5 0 -2 1 0 1
x3 0 -1 1 -3 0 2 1
F 0 -3.5 0 -2.5 0 0 -1.25

Table 5.7 – Itération 2 : calcul

• La valeur de x1 = 2, c’est une variable de base, sa valeur est celle de la même ligne
au niveau de la colonne B.

• La valeur de x2 = 0, c’est une variable hors base, donc par défaut sa valeur est 0.

• La valeur de x3 = 1, c’est une variable de base, sa valeur est celle de la même ligne
au niveau de la colonne B.

• Il reste des ressources pour les contraintes : e2 = 1. Le reste des ressources (c’est-à-
dire, e1 et e3 ) sont saturées.

• La valeur de la fonction objectif est F = | − 13| = 13. Il suffit de remplacer les

valeurs des xi dans la fonction objectif initiale pour obtenir la valeur 13.

x1 x2 x3 e1 e2 e3 B
x1 1 2 0 2 0 -1 2
e2 0 -5 0 -2 1 0 1
x3 0 -1 1 -3 0 2 1
F 0 -3 0 -1 0 -1 -13

Table 5.8 – Itération 2 : résultat final

5.3.3 Cas particuliers

Il existe des cas particuliers lors de l’application de la méthode du pivot (simplexe)
sur des PLs. Dans ce qui suit, on abordera deux cas qui sont récurrents qui optimise le
nombre d’itérations de la méthode du simplexe.
Cas 1 :
On applique la méthode du simplexe sur l’exemple suivant :

M ax z = 12x + 12y (5.17)


x + y ≤ 7

2x + y ≤ 9 (5.18)

x, y ≥ 0

CHAPITRE 5. PROGRAMMATION LINÉAIRE 59

x y e1 e2 B R
e1 1 1 1 0 7 7/1 7/1
e2 2 1 0 1 9 9/2 9/1
F 12 12 0 0 0 0

Table 5.9 – Cas particulier 1 : égalité des coefficients lors du choix de la colonne du pivot

Le Tableau 5.9 représente l’étape du choix de la colonne du premier pivot. Dans le cas
où il y a deux coefficients de la même valeur (lors du choix de la colonne du pivot, dans
l’exemple c’est le coefficient 12) il est nécessaire le traitement suivant :

• On suppose que la première colonne du premier coefficient (les valeurs en bleu) est
la colonne du pivot. On divise la colonne B par la colonne du pivot choisi (les valeurs
en bleu dans la colonne R).

• On suppose maintenant que la seconde colonne du second coefficient (les valeurs en

rouge) est la colonne du pivot. On divise la colonne C par la colonne du pivot choisi
(les valeurs en rouge dans la colonne R).

• Pour déterminer le pivot, on doit choisir la valeur maximale parmi les valeurs mini-
males de la colonne bleue et la colonne rouge, c’est-à-dire,
ligne du pivot = max(min(7/1, 9/2), min(7/1, 9/1)).

Cas 2 :
On applique la méthode du simplexe sur l’exemple suivant :

M ax z = 8x + 5y (5.19)


x + y ≤ 7

2x + y ≤ 14 (5.20)

x, y ≥ 0


x y e1 e2 B R
e1 1 1 1 0 7 7/1
e2 2 1 0 1 14 14/2
F 8 5 0 0 0 0

Table 5.10 – Cas particulier 2 : égalité des valeurs lors du choix de la ligne du pivot

Le Tableau 5.10 représente l’étape du choix de la ligne du premier pivot. En divisant

la colonne B sur la colonne du pivot (dans l’exemple la colonne x), on réalise que dans la
colonne résultat R, il y a deux valeurs égales (rappelons qu’on souhaite choisir la valeur
minimale pour avoir la ligne du pivot). Dans ce cas de figure, il est optimal de faire le
traitement suivant :
CHAPITRE 5. PROGRAMMATION LINÉAIRE 60

• On additionne les valeurs de la première ligne : 1 + 1 + 1 + 0 = 3.

• On additionne les valeurs de la seconde ligne : 2 + 1 + 0 + 1 = 4.

• On choisit la valeur la plus petite (c’est-à-dire la valeur 3), par conséquent la ligne
choisie est la première.

5.3.4 Dualité
La dualité consiste à associer au programme linéaire initial, appelé primal, un deuxième
programme linéaire, appelé dual, tel que :

• Le dual a m variables (autant de contraintes dans le programme primal).

• Le dual a n contraintes (autant de variables dans le programme primal).

• Si le programme primal est la maximisation alors le programme dual est la minimi-

sation (et inversement).

• Pour toute solution du dual et toute solution du primal, l’objectif final du dual est
supérieur ou égal à celui du primal.

• Les règles de passage entre le problème primal au dual sont résumées dans le Ta-
bleau 5.11.

Problème max Problème min

Contrainte Variable
≤ ≥0
= non restreinte
Variable contrainte
≥0 ≥
non restreinte =

Table 5.11 – Règles de dualité

Problème primal

maxcT X (5.21)

(
Ax = b
(5.22)
X≥0

n variables, m contraintes, m < n/ c, x ∈ Rn , b ∈ Rm , A ∈ Rm×n .

CHAPITRE 5. PROGRAMMATION LINÉAIRE 61

Problème dual

minbT y (5.23)

(
AT y = c
(5.24)
y non restreint

n variables, m contraintes, m < n/ c ∈ Rn , b, y ∈ Rm , A ∈ Rm×n .

Exemple
On montre dans ce qui suit un exemple d’un problème linéaire primal et son dual.
Problème primal :

max z = x1 + x2 (5.25)


2x1 + x2 = 5 (y1 )

3x1 − x2 = 6 (y2 ) (5.26)

x1 , x2 ≥ 0


Problème dual correspondant :

min w = 5y1 + 6y2 (5.27)

(
2y1 + 3y2 ≥ 1 (x1 )
(5.28)
y1 − y2 ≥ 1 (x2 )

5.4 Exercices
Exercice 1
Au quatorzième siècle, un Touareg compte gagner un peu d’or en investissant dans
des dromadaires qu’il sait pouvoir revendre à Tombouctou. Comme sa route passe par
Taoudeni, il pense aussi y acheter du sel pour tirer d’avantage de bénéfice de son voyage.
Il sait qu’il pourra obtenir au terme de son voyage 10 po (pièce d’or) de bénéfice par
dromadaire, et 1 pa (pièce d’argent, 1 po = 10 pa) de bénéfice par kg de sel. Avant toute
chose il faut déjà qu’il achète ces dromadaires et ce sel. Chaque dromadaire lui coûte
10 po, et chaque kg de sel 0.2 pa. Il peut investir 65po. Sachant qu’un dromadaire peut
transporter jusqu’à 150 kg de sel, comment ce Touareg doit investir son pécule pour tirer
le bénéfice maximal de son investissement ?
CHAPITRE 5. PROGRAMMATION LINÉAIRE 62

Exercice 2
Une laiterie s’est spécialisé dans deux fromages. Le premier est une AOC qui exige
plus d’heures de travail et un lait en provenance d’une région bien précise. Le second
demande moins de travail, et peut-être fabriqué avec n’importe quel lait. Par contre sa
vente dégage une marge moindre. La laiterie dispose 21000 heures de travail annuel, elle
reçoit 4 millions de litres de lait de la zone AOC, et 6 millions de litres d’autres zones. Le
tableau suivant indique les ressources nécessaires pour produire 1 tonne de fromage.

Heures de travail Litres de lait

Fromage
par tonne de fromage par tonne de fromage
Fromage (AOC) 30h 10000
Fromage 2 15h 7500

Sachant qu’un kilo du fromage AOC dégage une marge de 3 euros et qu’un kilo de
l’autre fromage seulement 1 euro, quelle production doit fabriquer cette laiterie pour
optimiser ses bénéfices ?

Exercice 3
Un revendeur d’électricité a promis à sa clientèle qu’un au moins 25% de son électricité
serait d’origine renouvelable. Il a calculé que pour l’année qui arrive il aura un marché de
18 TWh (téra watt heure). Il a aussi présélectionné trois fournisseurs à qui il va acheter
son électricité en gros. Voici les quantités (en TWh), le taux d’électricité renouvelable et
la marge dégagée (en k euro/TWh) que peuvent lui fournir ces trois producteurs.

% d’électricité quantité d’électricité

marge (k euro/TWh)
renouvelable achetable (TWh)
Producteur 1 10% 25 900
Producteur 2 46% 6 700
Producteur 3 100% 4 500

Chez quels producteurs et en quelle quantité ce revendeur doit-il acheter son électricité
pour avoir le meilleur bénéfice possible ?
Chapitre 6

Conclusion

Nous avons présenté dans ce cours une introduction à la théorie des graphes et la
programmation linéaire. Le début du document comporte les différentes tables de matières
(sections, figures, tableaux et algorithmes). La fin du document comporte les références
bibliographiques dont nous nous sommes inspirés pour élaborer ce cours.
Nous avons abordé dans le Chapitre 2 les notions élémentaires relatives à la théorie
des graphes (graphe, chemin, cycle, représentation matricielle, etc). Ensuite, nous avons
présenté dans le Chapitre 3 trois algorithmes pour le parcours du plus court chemin.
Cette partie était nécessaire pour exploiter les graphes dans la résolution de différents
problèmes académique ou industriel. Nous avons abordé dans le Chapitre 4 les réseaux
de transports, les flots et leurs propriétés. Nous avons également abordé un algorithme
de calcul du flot maximum ainsi qu’un théorème relatif au moyen de trouver une coupe
minimale. Ensuite nous avons présenté dans le Chapitre 5 la notion de modélisation d’un
problème sous forme de programme linéaire et la manière de le résoudre avec la méthode
graphique et la méthode du simplexe.
L’illustration des différentes notions abordées (dans les différents chapitres) est faite
avec des exemples explicatifs. À la fin de chaque chapitre, il y a également des exercices
pour pouvoir s’exercer d’une manière plus profonde.

63
Bibliographie

[Bou ] Mourad Bouzenada. Théorie des graphes. Technical report, Université Frères
Mentouri Constantine-2, -.

[Bou20] Samira Bouzoubia. Outils d’optimisation logistique. Technical report, Départe-

ment Génie des transports, Université Frères Mentouri Constantine-1, 2020.

[Cla ] François Clautiaux. Programmation linéaire. Technical report, Université Bor-

deaux 1, -.

[Dic97] Anne Dicky. Graphes et algorithmes. Technical report, Conservatoire national

des arts et métiers, 1997.

[EL13] Jean-Luc Raffy Eric Lallet. Techniques quantitatives de gestion - cahier d’exer-
cices corrigés. Technical report, Telecom école de management, 2013.

[For12] Bernard Fortz. Recherche opérationnelle et applications. Technical report, Uni-

versité Libre de Bruxelles, 2012.

[Gab16] Virginie Gabrel. Algorithmique et applications. Technical report, -, 2016.

[JCR15] Arnaud Malapert Jean-Charles Régin. Théorie des graphes. Technical report, -,
2015.

[Let ] Lucas Letocart. Algorithmique de graphes. Technical report, Université Paris

13, -.

[RK93] James B.Orlin Ravindra K.Ahuja, Thomas L. Magnanti. Nework flows. Technical
report, Library of congress, 1993.

[Rou09] Ph. Roux. Théorie des graphes. Technical report, DUT Informatique, 2009.

[Rou11] Frédéric Roupin. Algorithmique de graphes l3. Technical report, Université Paris
13, 2011.

[Sme ] Didier Smets. Programmation linéaire et optimisation. Technical report, Sor-

bonne Université, -.

[Tod ] Loan Todinca. Programmation linéaire et recherche opérationnelle. Technical

report, Université d’Orleans, -.

64