Outils de recherche opérationnelle

Dr Moussa BARRO
Maitre de Conférences en mathématiques et applications
Université Nazi BONI (Burkina Faso)

Bobo-Dioulasso le 20 janvier 2025

Introduction à la recherche opérationnelle

2 / 98
 Introduction à la recherche opérationnelle
Qu’est-ce que la recherche opérationnelle (RO) ?

3 / 98
Introduction au cours de RO
La recherche opérationnelle est un ensemble de processus d’aide à la décision qui
permettent de trouver une solution optimale (si elle existe) grâce à la modélisation
mathématique.

On aborde dans ce cours la recherche opérationnelle appliquée à l’économie et la gestion

avec le but :
- De modéliser un problème économique en un PL ou par un graphe ;
- De résoudre mathématiquement le programme obtenu ;
- D’interpréter en terme économique les résultats mathématiques obtenus.

4 / 98
Introduction au cours de RO
La recherche opérationnelle est un ensemble de processus d’aide à la décision qui
permettent de trouver une solution optimale (si elle existe) grâce à la modélisation
mathématique.

On aborde dans ce cours la recherche opérationnelle appliquée à l’économie et la gestion

avec le but :
- De modéliser un problème économique en un PL ou par un graphe ;
- De résoudre mathématiquement le programme obtenu ;
- D’interpréter en terme économique les résultats mathématiques obtenus.

Un modèle est une représentation de la réalité qui capture « l’essence » de la réalité, i.e.
l’angle qui nous intéresse.

5 / 98
 Contenu du cours
1 Programmation linéaire,
2 Généralités sur les graphes,
3 Problème d’ordonnancement,
4 Problème de flot sur un graphe.

6 / 98
[Link] linéaire

7 / 98
 1.1. Formulation d’un problème de programmation linéaire
Formulation d’un problème de programmation linéaire
La forme canonique générale d’un problème de P.L est la suivante :
n
Optimiser Z = ∑ cj xj (1)
j=1
⎧ n
∑ tij xj ≤≥ di , i = 1, . . . , p
⎪
⎪
⎪ (2)
⎪
⎪
⎪
⎪ j=1
(P) ⎪
⎪
⎪
⎪ n
⎪∑ tij xj = di , i = 1 + p, . . . , m
s.l.c ⎨ (3)
⎪
⎪
⎪ j=1
⎪
⎪
⎪
⎪
⎪xj ≥ 0, j = 1, . . . , q (4)
⎪
⎪
⎪xj , de signe quelconque pour j = 1 + q, . . . , n
⎪
⎩ (5),

où
- (tij )1≤i≤m , (cj )1≤j≤n ,
1≤j≤n
- (di )1≤i≤m sont des constantes,
- (xj )1≤j≤n la variable (inconnue).

8 / 98
Minimisation d’un coût sous des obligations de fonctionnement

n
Minimiser Z = ∑ cj xj
j=1
n
⎧
(P)
⎪
⎪
⎪
⎪∑ tij xj ≥ di , i = 1, . . . , m
⎪
⎪j=1
s.l.c ⎨
⎪
⎪
⎪
⎪
⎩xj ≥ 0, j = 1, . . . , n
⎪
⎪

9 / 98
Exo 1.1.
La société ESSAKAN SA peut extraire du minerai d’or à partir de deux puits P1 et P2
dont les niveaux d’activité x1 et x2 sont mesurés en nombre de tonnes extraites
journellement. Ce minerai est concassé, analysé et rangé, selon sa teneur, dans l’une des
catégories O1 , O2 , O3 (riche, moyen et pauvre). Dans le premier puits P1 , une tonne de
minerai donne 1/2 tonne de minerai O1 , 1/6 tonne de minerai O2 et 1/3 de minerai O3 .
Dans le second puits, une tonne extraite donne 1/8 tonne de minerai O1 , 1/8 tonne de
minerai O2 et 3/4 tonne de minerai O3 . La société s’est engagée à fournir journellement à
une usine de séparation 3, 2 et 6 tonnes de minerai O1 , O2 et O3 . Le coût d’exploitation
est de 20 milliers de francs (mf) par tonne extraite du puits P1 et de 10mf par tonne
extraite du puits P2 . La société désir satisfaire à ces engagements à moindre coût. Écrire
le programme linéaire correspondant.

10 / 98
Maximisation d’un gain sous des contraintes de capacité

n
Maximiser Z = ∑ cj xj
j=1
n
⎧
(P)
⎪
⎪
⎪
⎪∑ tij xj ≤ di , i = 1, . . . , m
⎪
⎪j=1
s.l.c ⎨
⎪
⎪
⎪
⎪
⎩xj ≥ 0, j = 1, . . . , n
⎪
⎪

11 / 98
Exo 1.2.

La société BARA fabrique deux produits P et Q qu’elle vend à des grossistes aux prix
respectifs (en francs) de 32000 et 50000. Sur le plan de la fabrication, la production des
produits P et Q nécessite l’utilisation dans un ordre quelconque de trois type de machines
notées A, B, C pendant des temps exprimés en minute dans le tableau suivant :
Machines
A B C
Produits
P 20 50 10
Q 30 50 40
Par ailleurs pour cette fabrication, ces machines ne sont disponibles au cours d’un mois
que 300 heures pour la machine A, 600 heurs pour la machine B et de 200 heures pour la
machine C. Les marges sur coûts variables en pourcentage du prix sont de 25% pour P et
de 20% pour Q. Écrire le programme linéaire (P) qui modélise ce problème.

12 / 98
Déf 1.1 (notion de solutions).

+ Une solution est admissible ou réalisable si elle satisfait toutes les contraintes.
+ La région admissible est l’ensemble P des solutions admissibles ou réalisables.
+ Une solution optimale est une solution admissible qui optimise le critère.

Exo 1.3.
Construire dans le plan muni d’un repère orthogonal, l’ensemble des solutions admissible
du programme obtenu dans l’exercice 1.2.

13 / 98
Déf 1.2 (contrainte saturée).
Une contrainte d’inégalité est dite saturée (ou serrée ou encore active ) pour une solution
si elle est vérifiée avec le signe d’égalité et non saturée (ou non serrée ou encore
inactive) si elle est vérifiée avec le signe d’inégalité stricte.

14 / 98
Déf 1.2 (contrainte saturée).
Une contrainte d’inégalité est dite saturée (ou serrée ou encore active ) pour une solution
si elle est vérifiée avec le signe d’égalité et non saturée (ou non serrée ou encore
inactive) si elle est vérifiée avec le signe d’inégalité stricte.

Théo 1.1.
L’ensemble P des solutions admissibles d’un programme linéaire est soit :
4 un polytope (une figure bornée à plusieurs côtés),
4 un polyèdre convexe, non vide mais non borné,
4 un ensemble vide.

15 / 98
Théo 1.2.

1 Si P l’ensemble admissible de (P) est un polytope alors

4 soit la solution optimale est unique et est située en un sommet de P ;
4 soit il existe une infinité de solutions optimales qui sont les points d’une face de P.
2 Si P est un polyèdre convexe, non vide mais non borné, en plus des situations
décrites ci-dessus, il est possible que le problème n’ai pas de solution optimale à
distance finie ; il existe une solution admissible (à l’infini) telle que Z = ∞ .
3 Si P est un ensemble vide, le problème n’a pas de solution optimale.

16 / 98
Résolution graphique : valable que pour deux inconnues
Les étapes d’une résolution graphique sont :
1 Tracer le domaine des solutions admissibles ;
2 Déterminer les coordonnées des sommets de l’ensemble des solutions admissibles ;
3 Dresser la table de décision ;
Sommets abscisse Ordonnée Critère Décision

4 Prendre le ou les sommet(s) où on a la plus grande valeur pour un problème de

maximisation,
5 Prendre le ou les sommet(s) où on a la plus petite valeur pour un problème de
minimisation.

17 / 98
Résolution graphique : valable que pour deux inconnues
Les étapes d’une résolution graphique sont :
1 Tracer le domaine des solutions admissibles ;
2 Déterminer les coordonnées des sommets de l’ensemble des solutions admissibles ;
3 Dresser la table de décision ;
Sommets abscisse Ordonnée Critère Décision

4 Prendre le ou les sommet(s) où on a la plus grande valeur pour un problème de

maximisation,
5 Prendre le ou les sommet(s) où on a la plus petite valeur pour un problème de
minimisation.

Exo 1.4.
Résoudre graphiquement le programme linéaire obtenu dans l’exercice 1.2.

18 / 98
 [Link]é
A chaque contrainte, on peut associer un nombre appelé « prix dual »

19 / 98
 [Link]é
A chaque contrainte, on peut associer un nombre appelé « prix dual »

Déf 1.3.
Le prix dual associé à la contrainte i est la variation de la fonction économique pour une
variation unitaire du second membre de la contrainte i.

Localisation de la marge sur coût variable (pour un problème de maximisation)

4 Profit=Prix dual-Prix d’usage >0, l’extension est profitable ;
4 Profit=Prix dual-Prix d’usage ≤0, l’extension n’est pas profitable.

20 / 98
 [Link]é
A chaque contrainte, on peut associer un nombre appelé « prix dual »

Déf 1.3.
Le prix dual associé à la contrainte i est la variation de la fonction économique pour une
variation unitaire du second membre de la contrainte i.

Localisation de la marge sur coût variable (pour un problème de maximisation)

4 Profit=Prix dual-Prix d’usage >0, l’extension est profitable ;
4 Profit=Prix dual-Prix d’usage ≤0, l’extension n’est pas profitable.

Localisation de la marge sur coût variable (pour un problème de minimisation)

4 Profit=Prix de vente-Prix dual >0, l’extension est profitable ;
4 Profit=Prix de vente-Prix dual ≤0, l’extension n’est pas profitable.

21 / 98
Déf 1.4 (Primal-dual).
On considère le problème de maximisation suivant sous sa forme canonique :
n
Maximiser Z = ∑ cj xj
j=1
n
(P) ⎧
⎪
⎪ i = 1, . . . , m
⎪∑ tij xj ≤ di ,
⎪
s.l.c ⎨j=1
⎪
⎩xj ≥ 0, j = 1, . . . , n
⎪
⎪
⎪

On appelle programme dual (canonique) de (P), le programme linéaire suivant :

m
Minimiser Z ′ = ∑ di yi
i=1
m
(D)
⎧
⎪
⎪
⎪∑ tji yi ≥ cj ,
⎪ j = 1, . . . , n
s.l.c ⎨i=1
⎪
⎩yi ≥ 0, i = 1, . . . , m
⎪
⎪
⎪

22 / 98
Rem 1.1 (Passage du primal au dual et vice versa).

4 Les programmes (P) et (D) sont dits primal et dual, et vice versa.
4 Si (P) est à maximiser alors (D) est à minimiser et vice versa.
4 Les inégalités de (P) et de (D) sont de sens opposés.
4 Les seconds membres de (P) sont les coefficients de la fonction économique de (D)
et vice versa.
4 Il y a autant de variables dual dans (D) que de contraintes dans le primal (P) et
vice versa.

23 / 98
Théo 1.3 (dualité forte).
Si le primal (P) admet une solution optimale alors le dual (D) admet une solution
optimale et vice versa et dans ce cas on a

(1.1) Valeur optimale du primal = Valeur optimale du dual.

24 / 98
Théo 1.3 (dualité forte).
Si le primal (P) admet une solution optimale alors le dual (D) admet une solution
optimale et vice versa et dans ce cas on a

(1.1) Valeur optimale du primal = Valeur optimale du dual.

Théo 1.4 (relations de complémentarités).

Si x est une solution optimale de (P) et y une solution optimale de (D) alors (x, y )
vérifie la relation suivant :
⎧ n
i ( ∑ tij xj − di ) = 0 pour i = 1; . . . ; m
⎪
⎪
⎪
⎪
⎪ y
⎪
⎪
⎪ j=1
⎪
(RC) ⎨
⎪
⎪
⎪ m
⎪
⎪
⎪
⎪
⎪ xj ( ∑ tji yi − cj ) = 0 pour j = 1; . . . ; n
⎪
⎩ i=1

25 / 98
Rem 1.2 (Conséquence).

1 Toutes les variables duales (respectivement primales) associées à des contraintes non
saturées du primal (respectivement du dual) sont nulles.
2 Les autres variables duales (respectivement primales) associées à des contraintes
saturées du primal (respectivement du dual) saturent les contraintes du dual
(respectivement du primal) auxquelles elles sont associées.
3 Le théorème 1.4 permet de résoudre le problème dual (D) connaissant la solution
optimale du primal (P) et vice versa.

26 / 98
Rem 1.2 (Conséquence).

1 Toutes les variables duales (respectivement primales) associées à des contraintes non
saturées du primal (respectivement du dual) sont nulles.
2 Les autres variables duales (respectivement primales) associées à des contraintes
saturées du primal (respectivement du dual) saturent les contraintes du dual
(respectivement du primal) auxquelles elles sont associées.
3 Le théorème 1.4 permet de résoudre le problème dual (D) connaissant la solution
optimale du primal (P) et vice versa.

Exo 1.5 (Camp vacance).

Un groupe d’étudiants organisent un voyage de vacance en car pour le Ghana. Il y a 425

étudiants et 9500kg de bagages à transporter. La compagnie Alpha propose trois types
de cars en location. Les caractéristiques unitaires sont résumées dans le tableau suivant :
Lux Confort Economique
Nombre de passagers 25 40 50
poids des bagages 1000 600 500
coût de location 8000 7200 7000
Déterminer la combinaison qui permet le coût minimum de location .

27 / 98
[Link] du simplexe

28 / 98
 [Link] du simplexe
Déf 1.5 (forme standard).
La forme standard du programme (P) est le programme
n
Maximiser Z = ∑ cj xj
j=1
⎧ n
⎪
⎪
⎪
⎪∑ tij xj + ei = di , i = 1, . . . , m (α)
⎪
⎪
⎪ j=1
(PS) ⎪
⎪
⎪
⎪
⎪
s.l.c ⎨
⎪
⎪
⎪xj ≥ 0, j = 1, . . . , n
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩ei ≥ 0, i = 1, . . . , m
⎪
⎪

On suppose que le système (α) est non redondante.

29 / 98
 [Link] du simplexe
Déf 1.5 (forme standard).
La forme standard du programme (P) est le programme
n
Maximiser Z = ∑ cj xj
j=1
⎧ n
⎪
⎪
⎪
⎪∑ tij xj + ei = di , i = 1, . . . , m (α)
⎪
⎪
⎪ j=1
(PS) ⎪
⎪
⎪
⎪
⎪
s.l.c ⎨
⎪
⎪
⎪xj ≥ 0, j = 1, . . . , n
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩ei ≥ 0, i = 1, . . . , m
⎪
⎪

On suppose que le système (α) est non redondante.

Écrire la forme standard d’un problème de minimisation dans sa forme générale.

30 / 98
Algorithme du simplexe
Idée : L’algorithme du simplexe consiste à passer d’un sommet initial du polyèdre des
solutions réalisables (ou admissibles) vers un sommet adjacent tout en ayant soin :
3 de ne pas diminuer la valeur de la fonction économique,
3 de garder les variables en base positives.
L’algorithme du simplexe contient donc deux phases :
Phase 1 : procédure d’initialisation
Soit la solution initiale est évidente (le cas en général dans ce cours), soit on
applique la méthode des variables artificielles, complément de l’algorithme du
simplexe (non abordée dans le cadre de ce cours).
Phase 2 : procédure itérative
Calculer, à partir d’une solution de base admissible, la solution de base admissible
adjacente donnant la meilleure amélioration de la fonction économique.

31 / 98
Initialisation : solution réalisable de base (I)
Soit B une sous matrice de T carrée et régulière d’ordre m telle que

Maximiser Z = CB xB + CR xR
⎧
⎪ BxB + RxR = d
(PS)
⎪
⎪
⎪
s.l.c ⎨
⎪
⎪
⎩x ≥ 0,
⎪
⎪

où
• Les m variables de xB sont appelés variables de base. Notons I l’ensemble des indices
de base : xB = (xi ; i ∈ I )
• Les (n − m) variables de xR sont appelées variables hors base. Notons J l’ensemble
des (n − m) indices hors base : xR = (xj ; j ∈ J)

Déf 1.6.
Soit I une base du système (α). On appelle réalisable de I ou sommet de base I , et on
note x(I ), la solution réalisable ayant des composantes hors base nulles.

32 / 98
Rem 1.3.
Lorsque les variables de base sont non négatives la solution de base est admissible.
Lorsqu’au moins une variable de base est nulle, la solution de base est dite dégénérée. Le
problème sera dit non dégénéré si toutes les solutions de base admissibles sont non
dégénérées.

33 / 98
2. Passage d’un sommet à un autre
Le principe est de passer d’un sommet à un autre sommet adjacent. Dans l’algorithme du
simplexe, le choix de l’arête à suivre est le suivant :
• On introduit la variable hors base qui fait augmenter le plus la fonction économique,
que l’on appelle variable entrante.
• La variable sortante, imposée par les contraintes de non négativité, sera la variable
de base qui s’annulera la première lorsque l’on augmente la valeur de la variable
entrante.
• Il faut donc au préalable de ces deux étapes (puis à la suite de ces deux étapes pour
effectuer l’itération) exprimer les variables de base et la fonction économique en
fonction des variables hors bases de manière à pouvoir définir la variable entrante et
la variable sortante.
On impose un coefficient de 1 sur les variables de base. L’expression de la fonction
économique en fonction des variables hors base permet de voir si, par rapport au niveau
actuel de la fonction économique, l’introduction d’une variable hors base améliore ce
résultat. On en déduit logiquement le test d’arrêt de l’algorithme : lorsque aucune
variable hors base ne peut augmenter la valeur actuelle de notre fonction économique,
alors on a obtenu la solution optimale.

34 / 98
3. Récapitulatif : le tableau du simplexe
choix de la variable hors base qui augmente le plus la fonction économique : choix de
la variable entrante ;
choix de la variable de base qui limite le plus le niveau de la fonction économique :
choix de la variable sortante ;
expression des variables de base et de la fonction économique en fonction des
variables hors base de manière à pouvoir déterminer les choix précédents.
Important : Au niveau du tableau du simplexe, ces étapes se systématisent de la manière
suivante :
Premier critère de Dantzig : la colonne qui entre dans la base est celle d’indice j
ayant le plus grand coefficient de marge (∆j > 0) le pus grand strictement positif.
di
Deuxième critère de Dantzig : On effectue les opérations pour les indices lignes
tij
figurant dans le tableau colonne de gauche. La colonne qui sort de la base est celle
di
d’indice i ayant le plus petit rapport ( > 0) strictement positif.
tij

35 / 98
Règles pratiques :
1 On repère (en encerclant) le pivot = tij où i est déterminer par le deuxième critère
et j par le premier critère.
2 On divise les valeurs de la ligne du pivot par le pivot .
3 L’indice i qui sort de la base (colonne de gauche) devient l’indice j qui entre dans la
base.
4 Toutes les lignes du tableau ayant un zéro (0) dans la colonne du pivot ne sont pas
modifiées.
5 Les autres lignes du tableau (ayant un élément différent de zér 0) sont modifiées
comme suit :
• On multiplie la nouvelle ligne du pivot par l’élément différent de zéro et on la soustrait
de la ligne à modifiée ;
• Cette opération s’applique également à la ligne de la fonction économique toute fois
dans la colonne solution on effectue une addition au lieu d’une soustraction.

36 / 98
Rem 1.4.

1 Le tableau du simplexe est optimal dès l’or que tous les coefficients de la fonction
économique sont inférieurs ou égaux à zéro (∆j ≤ 0).
2 On modifiera alors toujours en priorité la ligne de la fonction économique.

Théo 1.5 (lecture des solutions duales dans le tableau optimal).

Soient ei , i = 1; . . . ; m les variables d’écart associées aux contraintes du primal et

yi , i = 1; . . . ; m les variables duales associées respectivement à ces contraintes du primal.
Alors dans le tableau optimal du simplexe on a :

yi = −∆ei , i = 1; . . . ; m et Valeur optimale du dual = Valeur optimale du primal.

Exo 1.6.
Résoudre par la méthode du simplexe le problème posé par la société Bétha dans
l’exemple 1.5.

37 / 98
Généralités sur les graphes

38 / 98
2.1. Introduction

39 / 98
 2.1. Introduction
Introduction
Les graphes permettent de formaliser un certain nombre de problèmes qui se pose en
recherche opérationnelle. Citons parmi ceux-ci :
- les problèmes de circulation (ou problèmes de flot) : transport d’une production de
différentes usines vers différents lieux de distribution.
- Les problèmes d’ordonnancement : représentation de contraintes de succession que
doivent respecter certaines opérations de production ;

40 / 98
2.2.Généralités et définitions

41 / 98
 2.2.Généralités et définitions
Généralités sur les graphes
+ Soit X = {x1 ; x2 ; . . . ; xi ; ...; xn } = {1; 2; . . . .; i; . . . ..; n} un ensemble dit ensemble de
sommets ou de nœuds et R une correspondance de X dans l’ensemble des parties de
X . Le couple G = (X ; R) est appelé graphe.
+ Un couple ordonné u = (i; j) tel que j ∈ R(i) est appelé arc du graphe G , i est
l’extrémité origine et j est l’extrémité finale de l’arc u.
+ L’ordre du graphe est le cardinal de X , on le note : O(G ) = Card(X ) = n.
+ On note U l’ensemble des arcs du graphe alors G = (X ; U). Le graphe ainsi définit
peut être représenté par un ensemble de points reliés entre eux par des flèches. Une
flèches relie un sommet i à un sommet j si j ∈ R(i).
i j

+ Un sommet j est dit suivant ou successeur d’un sommet i si j ∈ R(i), autrement dit
il y a une flèche de i vers j. Dans ce cas i est dit précédent ou prédécesseur de j.
i j

42 / 98
Dans un graphe,
- Un sommet sans précédent est appelé entrée du graphe.
- Un sommet sans suivant est appelé sortie du graphe.
- On note S(i) = R(i), l’ensemble des suivants et P(i) = R −1 (i), l’ensemble des
précédents de i. Le tableau à simple entrée qui pour tout i énumère les éléments de
S(i) (resp P(i)) est appelé dictionnaire des suivants (resp précédents) du graphe G .

43 / 98
Prop 2.1 (Dictionnaire).
On note sur la ligne de i le numéro des lignes dans lesquelles i apparaissait comme
suivant et on obtient le dictionnaire des précédents et vice versa.

Déf 2.1 (matrice d’adjacence).

La matrice d’adjacence associée au graphe G d’ordre n, est la matrice carrée booléenne

d’ordre n, A = (aij )1≤i≤n définie par
1≤j≤n

⎧
⎪ 1
⎪ si j ∈ S(i)
(2.1) aij = ⎨
⎩ 0 si j ∉ S(i).
⎪
⎪

44 / 98
Prop 2.1 (Dictionnaire).
On note sur la ligne de i le numéro des lignes dans lesquelles i apparaissait comme
suivant et on obtient le dictionnaire des précédents et vice versa.

Déf 2.1 (matrice d’adjacence).

La matrice d’adjacence associée au graphe G d’ordre n, est la matrice carrée booléenne

d’ordre n, A = (aij )1≤i≤n définie par
1≤j≤n

⎧
⎪ 1
⎪ si j ∈ S(i)
(2.1) aij = ⎨
⎩ 0 si j ∉ S(i).
⎪
⎪

Rem 2.1.
Dans la matrice d’adjacence associée au graphe G on a :
- Si E est une entrée du graphe alors la colonne correspondante est nulle.
- Si S est une sortie du graphe alors la ligne correspondante est nulle.

45 / 98
Déf 2.2 (chemins d’un graphe).
Soit G = (X ; U) un graphe d’ordre n avec X = {1; 2; . . . ..; i; . . . ..; n}.
3 Un chemin est une suite ordonné de sommets ch = (i1 ; . . . .; ik ; . . . .; ip ) tel que pour
tout k on ait : ik+1 ∈ S(ik ).
3 Un circuit est un chemin qui se referme sur lui-même c’est-à-dire :
cc = (i1 ; . . . .; ik ; . . . .; ip ) est un circuit si i1 = ip .
3 Si i ∈ S(i) on dit que i est une boucle et cc = (i; i) est un circuit.
i

3 La longueur (au sens des arcs) d’un chemin est le nombre d’arcs qui le compose.
Ainsi la longueur d’un chemin à p sommets est p − 1.
3 Un chemin est dit hamiltonien s’il passe une et une seule fois par chaque sommet du
graphe, il est pré hamiltonien s’il passe au moins une fois par chaque sommet du
graphe.
3 Un chemin est dit eulérien s’il passe une et une seule fois par chaque arc du graphe,
il est dit pré-eulérien s’il passe au moins une fois par chaque arc du graphe.

46 / 98
Théo 2.1 (chemin de longueur p).

Soit G un graphe d’ordre n et A = (aij ) la matrice d’adjacence associée. On pose pour

tout naturel non nul p, M = Ap = (mij).
1 Le nombre mij est égal au nombre de chemins de longueur p allant du sommet i au
sommet j.
2 Si An n’est pas nulle (An ≠ 0) alors le graphe G contient des circuits. Un sommet i
est situé sur un circuit de longueur p si le terme diagonal mii de Ap est différent de 0
(mii ≠ 0).

47 / 98
Déf 2.3 (niveau ou rang d’un sommet).
Tous les graphes considérés ici sont sans circuit. Le niveau ou rang d’un sommet i est la
longueur du plus long chemin de l’entrée du graphe au sommet i.

Théo 2.2 (procédure de détermination du rang).

a. On pose N0 = {i ∈ X ∣ P(i) = ∅} l’ensemble des sommets sans précédent ou

ensemble des sommets de rang 0.
b. On barre les sommets de rang 0 partout où ils figurent dans la colonne des
précédents. Si une ligne a ainsi tous ces précédents barrés le sommet correspondant
est de rang 1.
c. On réitère le procédé b) en augmentant de 1 la valeur du rang jusqu’à ce que tous
les sommets soient barrés.

48 / 98
Rem 2.2 (utilité du rang).
L’ordonnancement par niveau croissant permet une représentation plus simple du graphe
et la recherche des chemins optimaux se fait plus facilement sur un graphe ordonné par
niveau.

49 / 98
 2.3. Chemins optimaux d’un graphe
Déf 2.4 (Valuation d’un arc).

On affecte à chaque arc u = (i; j) un nombre positif l(u) = lij appelé sa valuation qui
peut-être sa longueur, sa durée, son coût, sa capacité ....

lij
i j

Déf 2.5 (Longueur d’un chemin).

La longueur (L(ch)) d’un chemin (ch) (au sens de la valuation) est la somme des
valuations des arcs qui le composent c’est-à-dire : L (ch) = ∑ l(u) .
u∈ch

50 / 98
Problème de plus court ou plus long chemin d’un sommet i à un sommet j.
Soient i et j deux sommets d’un graphe, on cherche à déterminer le plus court ou le plus
long chemin reliant i à j. Il s’agit donc de résoudre le problème d’optimisation :

(CO) Optimiser L (ch(i; j)), s.l.c ch(i; j) ∈ G .

Rem 2.3.
On peut lister tous les chemins de i à j et leur longueur et sélection le (ou les) chemins
optimaux. Cependant cette méthode est complexe quand le nombre de chemins est
important.

51 / 98
Algorithme de FORD (plus long chemin d’un sommet i à un sommet j)
1. On supprime du graphe tous les sommets de rang inférieur ou égal au rang de i ainsi
que tous ceux de rang supérieur ou égal au rang de j. On supprime également du
graphe tous les arcs ayant perdu au moins un sommet. Dans le nouveau sous graphe
ainsi obtenu le rang de i est égal à 0 et le rang de j est maximal.
2.
2.a. On pose ti = 0,
2.b. Prendre les sommets k par rang croissant et faire : tk = max{tx + lxk ∶ x ∈ P(k)}.
«La marque tj est la longueur du plus long chemin de i à j »,
3.
3.a. On pose ch = (. . . ; j),
3.b. On cherche le sommet x tel que tj = tx + lxj et on pose ch = (. . . ; x; j),
3.c. On répète le procédé 3.b. en prenant les sommets par rang décroissant jusqu’à obtenir
le sommet i. « Le chemin ch = (i; . . . ; j) est le plus long chemin du sommet i au
sommet j».

52 / 98
Algorithme de FORD (plus long chemin d’un sommet i à un sommet j)
1. On supprime du graphe tous les sommets de rang inférieur ou égal au rang de i ainsi
que tous ceux de rang supérieur ou égal au rang de j. On supprime également du
graphe tous les arcs ayant perdu au moins un sommet. Dans le nouveau sous graphe
ainsi obtenu le rang de i est égal à 0 et le rang de j est maximal.
2.
2.a. On pose ti = 0,
2.b. Prendre les sommets k par rang croissant et faire : tk = max{tx + lxk ∶ x ∈ P(k)}.
«La marque tj est la longueur du plus long chemin de i à j »,
3.
3.a. On pose ch = (. . . ; j),
3.b. On cherche le sommet x tel que tj = tx + lxj et on pose ch = (. . . ; x; j),
3.c. On répète le procédé 3.b. en prenant les sommets par rang décroissant jusqu’à obtenir
le sommet i. « Le chemin ch = (i; . . . ; j) est le plus long chemin du sommet i au
sommet j».

Rem 2.4.
En remplaçant max par min dans 2. b. on obtient le plus court chemin du sommet i au
sommet j.

53 / 98
Rem 2.5.
Il existe d’autres algorithmes de recherche de plus court ou plus long chemin dans un
graphe. Par exemple l’ algorithme de Moore – Dijstra (1959 – 1960) permet de calculer le
plus court chemin d’un sommet initial à tous les autres sommets. Il donne l’arborescence
des plus courts chemins. Des variantes de cet algorithme ont été proposées par Dantzig
(1960) et par Whiting – Hillier (1960).

54 / 98
Exercice d’application
La société ZOR connaît une croissance importante et régulière créant de gros besoins en
locaux de production en aires de stockage. Il en résulte une importante dispersion
géographique des différents bâtiments de l’entreprise. La matrice ci-dessous indique le
temps en minutes (temps de trajet + temps d’arrêt aux stations) que mettent les
navettes pour joindre les différents points.

1 Établir le dictionnaire des précédents et des suivants.

2 Représenter le problème sous forme de graphe ordonné en niveaux
3 Quel est le chemin que doit emprunter un employé désirant se rendre du point A au
point J en un temps minimum ? Quel est ce temps ?

55 / 98
3. Problème d’ordonnancement

56 / 98
3. Problème d’ordonnancement
3.1. Position du problème

57 / 98
 3. Problème d’ordonnancement
3.1. Position du problème
Position du problème
En toute généralité, il se pose sous la forme suivante : Étant donné un objectif qu’on se
propose d’atteindre, et dont la réalisation suppose l’exécution préalable de multiples
tâches soumises à de nombreuses contraintes, déterminer l’ordre et le calendrier (ou
planning) d’exécution des divers tâches. Les contraintes peuvent être :
de succession dans le temps (l’exécution de la tâche j ne peut commencer qu’un
certain laps de temps ou lorsque la tâche i est achevée).
de date (une tâche ne peut commencer avant une certaines date, indépendamment,
du fait qu’elle doit succéder à d’autres tâches).
L’objectif consiste à déterminer le planning optimal pour la réalisation du projet.

58 / 98
Méthodes de résolution d’un problème d’ordonnancement
La représentation d’un problème d’ordonnancement par un graphe permettra d’identifier
les tâches prioritaires et de détecter à temps les retards ou les déplacements de moyens.
Nous étudierons deux représentations possibles :
- Le graphe potentiels – tâches ou méthode M.P.M ;
- Le graphe potentiels – étapes ou méthode PERT.

59 / 98
3.2. Méthode MPM

60 / 98
 3.2. Méthode MPM

La méthode M.P.M (Roy 1960)

Méthode des Potentiels – Métra développée en France par la [Link].

61 / 98
 3.2. Méthode MPM

La méthode M.P.M (Roy 1960)

Méthode des Potentiels – Métra développée en France par la [Link].

Principe de la représentation
v A chaque tâche (ou opération) i on associe un sommet i du graphe (par abus) ;
v On définira un arc de i à j de longueur di ,la durée de la tâche i si la tâche i doit
précéder la tâche j.
di
i j

v on ajoute à ce graphe deux sommets correspondants à deux tâches fictives :

• α= tâche début des travaux de durée d0 = 0 qui doit être antérieure à toutes les autres
tâches, autrement dit α est reliée à toutes les tâches sans précédent.
• ω= tâche fin des travaux qui doit être postérieur à toutes les autres tâches, autrement
dit toutes les tâches sans suivant sont reliées à ω.

62 / 98
Le calendrier
Le travail commence toujours à la date 0. On cherche un ordonnancement qui minimise
la durée totale du projet. Pour qu’une tâche débute, il est nécessaire que toutes les
tâches qui la relient à la tâche début du projet soient réalisées.

63 / 98
Le calendrier
Le travail commence toujours à la date 0. On cherche un ordonnancement qui minimise
la durée totale du projet. Pour qu’une tâche débute, il est nécessaire que toutes les
tâches qui la relient à la tâche début du projet soient réalisées.

Déf 3.1 (date de début au plus tôt).

La date au plus tôt ti de début de la tâche i est la longueur du plus long chemin de α à i.

La procédure de calcul des ti

a. On pose tα = 0.
b. Prendre les sommets i par rang croissant et faire :ti = max{tj + dj ∶ j ∈ P(i)}.

64 / 98
Le calendrier
Le travail commence toujours à la date 0. On cherche un ordonnancement qui minimise
la durée totale du projet. Pour qu’une tâche débute, il est nécessaire que toutes les
tâches qui la relient à la tâche début du projet soient réalisées.

Déf 3.1 (date de début au plus tôt).

La date au plus tôt ti de début de la tâche i est la longueur du plus long chemin de α à i.

La procédure de calcul des ti

a. On pose tα = 0.
b. Prendre les sommets i par rang croissant et faire :ti = max{tj + dj ∶ j ∈ P(i)}.

Conséquence
La durée minimale du projet est donc tω égale à la longueur du plus long chemin de α à
ω. C’est aussi la longueur du plus long chemin du graphe de α à ω.

65 / 98
Déf 3.2 (date de début au plus tard Ti ).
On fixe à tω la durée du projet. La date au plus tard Ti pour commencer la tâche i est la
longueur du plus long chemin de i à ω.

La procédure de calcul des Ti est la suivante :

a. On pose Tω = tω
b. prendre les sommets i par rang décroissant et faire :

Ti = min{Tj − di ∶ j ∈ S(i)} = min{Tj ∶ j ∈ S(i)} − di .

66 / 98
Déf 3.2 (date de début au plus tard Ti ).
On fixe à tω la durée du projet. La date au plus tard Ti pour commencer la tâche i est la
longueur du plus long chemin de i à ω.

La procédure de calcul des Ti est la suivante :

a. On pose Tω = tω
b. prendre les sommets i par rang décroissant et faire :

Ti = min{Tj − di ∶ j ∈ S(i)} = min{Tj ∶ j ∈ S(i)} − di .

Notation
Ti

tâche

ti

67 / 98
Déf 3.3 (marge totale).
La marge totale est le retard maximum que l’on peut prendre dans la mise en route d’une
tâche sans remettre en cause les dates au plus tard des tâches suivantes, donc sans
retarder la fin des travaux. Pour une tâche i donnée, cette marge totale est :

(3.1) mi = Ti − ti .

Déf 3.4 (marge libre).

La marge libre est le retard maximum que l’on peut prendre dans la mise en route d’une
tâche sans remettre en cause les dates de début au plus tôt d’aucune autre tâche. Pour
une tâche i donnée, cette marge libre est :

(3.2) Mi = min{tj − ti − di ∶ j ∈ S(i)}.

68 / 98
3.3. Méthode PERT

69 / 98
 3.3. Méthode PERT

La méthode PERT (Malcolm, Roseboom, Clark and Fasar :1959)

Program Evaluation Research Task (or Review Technic) de conception américaine.

Principe de la représentation
à chaque tâche correspond un arc du graphe, dont la longueur est égale à la durée
de la tâche.
i , di

chaque sommet du graphe est un évènement (ou étape) signifiant que toutes les
tâches qui arrivent sont terminées et toutes celles qui partent peuvent commencer.

70 / 98
Exem 3.1.
Représenter les contraintes d’antériorité suivantes et commenter. Les tâches a et b sont
précédentes des tâches c et d

Rem 3.1.
La représentation en PERT, de certaines relations d’antériorité nécessite l’introduction de
tâches fictives de durée 0. 0

Exem 3.2.
Les tâches a et b sont précédentes de la tâche c et la tâche d est suivante de la tâche b.
Représenter les contraintes d’antériorité ci-dessus et commenter.

71 / 98
Rem 3.2.
La détermination des niveaux ne correspond pas à la formulation PERT, (Pourquoi ?)
on définira une étape début du projet d’où partent toutes les tâches sans précédent
et une étape fin du projet à laquelle aboutissent toutes les tâches sans suivant.
Si une tâche j doit succéder à une tâche i, l’extrémité origine de l’arc j est égale à
l’extrémité finale de l’arc i.
i , di j , dj
E

Pour chaque tâche i, on détermine P(i) l’ensemble de ses précédents et les

différentes étapes du projet correspondent aux différents ensemble P(i).

72 / 98
Le calendrier
On note α (ou 1) l’étape début du projet et ω (ou n) l’étape fin du projet.

Déf 3.5 (date de début au plus tôt).

Pour chaque étape x on définit sa date de début au plus tôt tx égal à la longueur du plus
long chemin de α à x. tx est appelé aussi la date attendue de l’évènement x. La date de
début au plus tôt de chaque étape x est égale à la date de début au plus tôt de toutes les
tâches qui partent de x.
di
i,

tx = ti = tj

j , dj
x
tx

73 / 98
Déf 3.6 (date de début au plus tard).
On détermine pour chaque étape y , ty∗ sa date de début au plus tard. Soit i une tâche
aboutissant à l’étape y , alors la date de début au plus tard de la tâche i est : Ti = ty∗ − di .

ty∗
i , di
y Ti = ty∗ − di

74 / 98
Déf 3.6 (date de début au plus tard).
On détermine pour chaque étape y , ty∗ sa date de début au plus tard. Soit i une tâche
aboutissant à l’étape y , alors la date de début au plus tard de la tâche i est : Ti = ty∗ − di .

ty∗
i , di
y Ti = ty∗ − di

Déf 3.7 (marges).

Soit i une tâche joignant l’étape x à l’étape y , alors
sa marge totale est : mi = Ti − ti = ty∗ − di − tx ,
sa marge libre est : Mi = ty − di − tx .

tx∗ ty∗
i , di
x y
tx ty

75 / 98
Observation
Pour toute tâche i on a 0 ≤ Mi ≤ mi . (Commenter).

Déf 3.8 (tâche critique).

• une tâche i est dite critique si sa marge totale mi = 0, en d’autres termes si sa date
de début au plus tôt est égale à sa date de début au plus tard c’est–à–dire ti = Ti .
• les tâches critiques sont situées sur le (un) chemin critique. Si un retard est pris sur
une des tâches critiques la durée minimale du projet sera décalée d’autant.
• ainsi on identifie les tâches critiques qui permettent la surveillance de la bonnes
marche des opérations.
• notons qu’il existe toujours au moins un chemin critique de α à ω qui est le plus
long chemin de α à ω. autrement dit la durée minimale du projet est la longueur du
plus long chemin du graphe.

76 / 98
Déf 3.9 (diagramme de GANTT).
Le diagramme en bâtons qui donne l’évolution de l’exécution des tâches en fonction du
temps (à la date de début au plus tôt ou au plus tard) est appelé diagramme de GANTT.

Temps
A
B
C
D

Tâches

77 / 98
Exo 3.1 (société « HIGH-TECHN »).

La société « HIGH-TECHN » envisage la mise en place de nouveaux équipements

industriels. Dans le cadre de son projet, elle a procédé à la définition d’un certain nombre
de tâches à effectuer et à l’évaluation de leur durée. Les conditions d’antériorité liant ces
tâches, et les durées en semaines de celle-ci, sont rassemblées dans le tableau ci-dessous.
Tâches A B C D E F G H I
Tâches antérieures - D BH A A D F I DE
Durée (en semaines) 10 14 14 8 12 22 25 18 6

1 Construire le graphe MPM de cet ordonnancement.

2 Déterminer la durée minimale de réalisation de ce projet.
3 Déterminer le retard maximum que l’on peut admettre au démarrage de la tâche B
sans remettre en cause la date de début au plus tôt des autres tâches.
4 Reprendre les questions 1. 2. et 3. avec la méthode PERT.

78 / 98
4. Problème de flots maximum

79 / 98
4. Problème de flots maximum

4.1. Introduction

80 / 98
 4. Problème de flots maximum

4.1. Introduction
+ Nous allons pouvoir faire circuler sur des graphes des flux de biens ou des flux
monétaires. Ces circulations seront soumises à des équations de nœuds analogues à
celles des réseaux électriques et à des bornes.
+ Soit un graphe de sommets ai , i = 1, . . . , n. A chaque arc (ai , aj ) joignant les
sommets ai et aj , on peut associé un flux ϕ(ai , aj ) qu’on notera aussi plus
simplement ϕij .
ϕij
ai aj

+ Concrètement, ces flux seront des quantités de matières, des heures de travail
affectées à certaines tâches, des revenues monétaires, ... .

81 / 98
 4. Problème de flots maximum

4.1. Introduction
+ Nous allons pouvoir faire circuler sur des graphes des flux de biens ou des flux
monétaires. Ces circulations seront soumises à des équations de nœuds analogues à
celles des réseaux électriques et à des bornes.
+ Soit un graphe de sommets ai , i = 1, . . . , n. A chaque arc (ai , aj ) joignant les
sommets ai et aj , on peut associé un flux ϕ(ai , aj ) qu’on notera aussi plus
simplement ϕij .
ϕij
ai aj

+ Concrètement, ces flux seront des quantités de matières, des heures de travail
affectées à certaines tâches, des revenues monétaires, ... .
+ L’ensemble de ces flux forme un flot si, en chaque sommet ai , la somme des flux
entrants est égal à la somme des flux sortants :

(4.1) ∑ ϕki = ∑ ϕij ,

ak ∈P(ai ) aj ∈S(ai )

82 / 98
Un flot circule généralement entre un ensemble de sommets qui servent d’origines au flot
et un ensemble de sommets qui sont des destinations. Les sommets d’origines sont joints
à une "entrée" ā par des arcs nommés arcs entrants. Les sommets qui sont des
destinations sont joints à une "sortie" b̄ par des arcs nommés arcs sortants. On joint la
sortie à l’entrée par un arc (b̄, ā) appelé arc de retour.

83 / 98
Un flot circule généralement entre un ensemble de sommets qui servent d’origines au flot
et un ensemble de sommets qui sont des destinations. Les sommets d’origines sont joints
à une "entrée" ā par des arcs nommés arcs entrants. Les sommets qui sont des
destinations sont joints à une "sortie" b̄ par des arcs nommés arcs sortants. On joint la
sortie à l’entrée par un arc (b̄, ā) appelé arc de retour.

Exemple

O1 D1

ā O2 D2 b̄

O3 D3

ϕ(b̄, ā)

84 / 98
[Link] problème de flot maximum

85 / 98
 [Link] problème de flot maximum
Déf 4.1.
Étant donné un réseau de transport où les flux doivent être compris entre des bornes
supérieures et inférieures, on veux trouver un flot tel que le flux circulant sur l’arc de
retour soit maximum.

Rem 4.1.
On constate d’abord que le vocabulaire est malheureux puisqu’on parle de flot maximum,
alors qu’on maximise un flux. En fait, le flux circulant sur l’arc de retour est égal à la
somme des flux entrant dans le réseau par les arcs d’origine ā et aussi la somme des flux
sortant du réseau par les arcs d’extrémité terminale b̄.

86 / 98
 [Link] problème de flot maximum
Déf 4.1.
Étant donné un réseau de transport où les flux doivent être compris entre des bornes
supérieures et inférieures, on veux trouver un flot tel que le flux circulant sur l’arc de
retour soit maximum.

Rem 4.1.
On constate d’abord que le vocabulaire est malheureux puisqu’on parle de flot maximum,
alors qu’on maximise un flux. En fait, le flux circulant sur l’arc de retour est égal à la
somme des flux entrant dans le réseau par les arcs d’origine ā et aussi la somme des flux
sortant du réseau par les arcs d’extrémité terminale b̄.

Formulation par un PL
Comme les différents flux doivent constituer un flot, notre problème prend la forme d’un
programme linéaire dont les inconnues sont les flux ϕij circulant sur tous les arcs (ai , aj )
du réseau. On note cij et bij les bornes supérieures et inférieures auxquelles sont soumis
les flux ϕij , i.e

bij ≤ ϕij ≤ cij

ai aj

87 / 98
Formulation par un PL
Le problème de flot maximum prend alors la forme suivante :

Max ϕ(b̄, ā)

⎧
⎪ ∑ ϕki = ∑ ϕij , pour tout sommet ai du graphe
(PT) ⎪
⎪
⎪ak ∈P(ai )
⎪
⎪ aj ∈S(ai )
s.l.c ⎨
⎪
⎪
⎪
⎪
⎪
⎩bij ≤ ϕij ≤ cij ,
⎪ pour tout arc (ai , aj ) du graphe.

88 / 98
Formulation par un PL
Le problème de flot maximum prend alors la forme suivante :

Max ϕ(b̄, ā)

⎧
⎪ ∑ ϕki = ∑ ϕij , pour tout sommet ai du graphe
(PT) ⎪
⎪
⎪ak ∈P(ai )
⎪
⎪ aj ∈S(ai )
s.l.c ⎨
⎪
⎪
⎪
⎪
⎪
⎩bij ≤ ϕij ≤ cij ,
⎪ pour tout arc (ai , aj ) du graphe.

On peut alors résoudre de tels programmes à l’aide de l’algorithme du simplex et la

théorie des graphes nous aura simplement servi à poser le problème. Mais ces
programmes on une forme algébrique très particulière. On peut aussi les résoudre par un
algorithme particulier dans lequel les calculs peuvent être effectuer à la main.

89 / 98
 Algorithme de Fülkerson

1 Flot au jugé. On détermine un flot au jugé qui respecte le principe de conservation

de flux à chaque nœud de transit et la contrainte de capacité sur chaque arc.
2 Flot maximum
+ Définitions :
, On appelle chaîne de ā à b̄ une suite de sommets (ā, a1 , ..., ai , aj , . . . , b̄) tel que ai est un
suivant de aj ou ai est un précédent de aj .
, Une chaîne est dite saturée si au moins un des arcs parcourus dans le sens des flèches est
saturé (son flux est égale à sa capacité) ou si au moins un des arcs parcourus dans le sens
contraire des flèches a un flux égale à sa borne inférieure.
, Un flot est dit maximum s’il n’y a plus de chaîne non saturée de ā à b̄.
+ Détermination :
, On détermine une chaîne non saturée de ā à b̄ et on la sature par la procédure suivante :
, On note A+ , l’ensemble des arcs parcourus dans le sens des flèches et on calcule
+
r1 = min{cij − ϕij ∶ (ai , aj ) ∈ A };
−
, On note A , l’ensemble des arcs parcourus dans le sens contraire des flèches et on calcule
−
r2 = min{ϕij − bij ∶ (ai , aj ) ∈ A };
, On pose r = min{r1 ; r2 } ;
, On ajoute au flux de chacun des arcs de A+ la quantité r ;
, On retranche au flux de chacun des arcs de A− la quantité r ;
, On répète ce processus jusqu’à ce qu’il n’y ait plus de chaîne non saturée de ā à b̄.

90 / 98
Exo 4.1.
En prévision d’une augmentation du trafic routier entre les villes A et F, On veut analyser
les possibilité du réseau joignant ces deux villes, soit :
4
B D
∣4∣

2 6

∣3∣ ∣6∣

0
A 2 ∣2∣ 2 ∣2∣ F
∣2∣

6 2

∣7∣ ∣5∣

4
C E
∣4∣

Les capacités des routes (en centaines de véhicules par heure) sont indiquées par des
nombres encadrés et les flux actuels par des nombres non encadrés. Les bornes inférieures
sont nulles. Déterminer le flot maximum pouvant circuler de A à F.

91 / 98
[Link]ème général de transport

92 / 98
 [Link]ème général de transport
Position du problème
Maximiser le flot entrant et sortant n’est pas en générale le problème essentiel que pose
la gestion d’un réseau de transport. On cherche plutôt à faire passer une quantité de flux
donnée en minimisant le coût de l’opération ou en maximisant un profit. Cette quantité
de flux donnée correspondra à des demandes exprimées par des bornes inférieures
attachées aux arc sortants. On pourra d’ailleurs par paramétrisation, augmenter ces
demandes à moindre coût. Ainsi, le problème général de transport fait intervenir un réseau
de transport et comporte donc les mêmes contraintes que le problème de flot maximum.
Par contre on minimise (ou maximise) une fonction linéaire quelconque des flux.

Optimiser Z= ∑ Cij ϕij

arc (ai ,aj )

(PGT)
⎧
⎪
⎪ ∑ ϕki = ∑ ϕij , pour tout sommet ai
⎪
⎪ak ∈P(ai )
⎪
⎪ aj ∈S(ai )
s.l.c ⎨
⎪
⎪
⎪
⎪
⎪
⎩bij ≤ ϕij ≤ cij ,
⎪ pour tout arc (ai , aj ) .

93 / 98
Problème de transport simple
Un cas particulier important dans la littérature est le problème de transport simple. On
considère alors un ensemble de sommets
4 origines a1 , . . . , ai , . . . , an en lesquels sont disponibles des quantités de biens si ,
4 destinations a1′ , . . . aj′ , . . . , am
′
en lesquelles on doit satisfaire des demandes dj .
On suppose d’autre part que les arcs liant les sommets ai et les sommets aj′ ont une
capacité infinie et que le coût unitaire de transport entre ai et aj′ est Cij .

On cherche les quantités ϕij du bien à envoyer de ai vers aj , en respectant les stocks si et
les demandes dj tout en minimisant le coût total du transport :

Minimiser ∑ ∑ cij ϕij

i j

n
⎧
⎪
⎪
⎪
⎪∑ ϕij = dj , j = 1, . . . , m,
⎪
⎪
⎪ i=1
(PTS) ⎪
⎪
⎪
⎪
⎪
⎪
⎪m
s.l.c ⎨∑ ϕ = s , i = 1, . . . , n,
⎪ ij i
⎪
⎪
⎪ j=1
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩ϕij ≥ 0, i = 1, . . . , n; j = 1, . . . , m.
⎪
⎪
94 / 98
Le problème (PTS) est dit équilibré si l’offre totale est égale à la demande totale i.e.
n m
(4.2) ∑ si = ∑ dj .
i=1 j=1

Une condition nécessaire et suffisante pour que le problème de transport simple (PTS)
admet une solution optimale est qu’il soit équilibré

Problème de transport non équilibré

Le problème (PTS) est dit non équilibré si l’offre totale est différente de la demande
n m
totale i.e. ∑ si ≠ ∑ dj . Dans ce cas , deux cas sont possibles :
i=1 j=1
′
+ Si l’offre excède la demande alors on crée un point virtuel am+1 de demande dont la
n m
demande est dm+1 = ∑ si − ∑ dj pour lequel le coût de transport du point ai vers
i=1 j=1
′
am+1 est nul ;
+ Si la demande excède l’offre alors (PTS) n’admet pas de solution. Parfois, la
modélisation permet d’avoir de la demande non satisfaite, souvent en ajoutant une
pénalité. On peut garder l’égalité dans les contraintes d’offre et replacer « = » par
«≤» dans celles des demandes pour obtenir la situation de demandes non satisfaites.
95 / 98
Problème d’affectation
Il s’agit en faite de résoudre des problèmes de transport simple avec des flux qui vaudront
0 ou 1. Dans le problème d’affectation classique, le nombre de sommets origines est égal
au nombre de sommets qui servent de destination. On supposera par exemple qu’une
entreprise ou une administration veux affecter n personnes à n postes. Les personnes
ayant exprimé leurs préférences en classant chacune les n postes. On note Cij la note
attribuer par l’employé i au poste j et ϕij la variable égale 1 si l’ouvrier i est affecté au
poste j et 0 sinon.

96 / 98
Problème d’affectation
Il s’agit en faite de résoudre des problèmes de transport simple avec des flux qui vaudront
0 ou 1. Dans le problème d’affectation classique, le nombre de sommets origines est égal
au nombre de sommets qui servent de destination. On supposera par exemple qu’une
entreprise ou une administration veux affecter n personnes à n postes. Les personnes
ayant exprimé leurs préférences en classant chacune les n postes. On note Cij la note
attribuer par l’employé i au poste j et ϕij la variable égale 1 si l’ouvrier i est affecté au
poste j et 0 sinon.

On désir minimiser les regrets causés par l’affectation.

Minimiser ∑ ∑ Cij ϕij

i j
⎧ n
ϕij = 1, j = 1, . . . , m,
⎪
⎪
⎪
⎪
⎪∑
(PA) ⎪
⎪
⎪
⎪m
i=1
s.l.c ⎨∑ ϕ = 1, i = 1, . . . , n,
⎪ ij
⎪
⎪
⎪ j=1
⎪
⎪
⎩ϕij variables binaires.
⎪
⎪
⎪

Le même problème se pose si on veut maximiser le rendement global.

97 / 98
Exo 4.2.
Quatre personnes sont à affecter à quatre travaux (chaque personne doit être affecter à
un travail, chaque travail doit être prise en charge par une personne). Le rendement
obtenu par la ième personne affectée au travail j est Rij . Les valeurs des Rij sont données
dans le tableau suivant :
Travail 1 Travail 2 Travail 3 Travail 4
Personne 1 2 5 4 4
Personne 2 0 9 3 7
Personne 3 1 8 8 9
Personne 4 9 4 1 6
Quelle est l’affectation de ces personnes aux travaux pour laquelle la somme des
rendement est maximale ?

98 / 98