Résumé de Recherche

Opérationnelle
EBENGO BONSONGI Alain
+243824179316
alainebengo67@[Link]

1
 TABLE DES MATIERES

CHAPITRE 1 : PROGRAMMATION LINEAIRE ............................................. 3

1.1 Algorithme primal de simplexe sans matrice identité explicite ..................... 3
1.2 Algorithme dual de simplexe ....................................................................10
CHAPITRE 2 : PROBLEME DE TRANSPORT .................................................11
2.1 La règle du Coin Nord-Ouest ....................................................................13
2.2 Méthode du minimum de la ligne ..............................................................16
2.3 Méthode du minimum de la colonne .........................................................18
2.4 Méthode du minimum de la matrice ..........................................................20
2.5 Méthode de la double préférence .............................................................23
2.6 Méthode d’Approximation de VOGEL .........................................................25
2.7 Méthode de fréquence .............................................................................28
2.8 Méthode d’affectation ..............................................................................31
2.9 Méthode de tremplin................................................................................34

CHAPITRE 3 : THEORIE DE GRAPHES ........................................................39

3.1 La détermination des composants fortement connexes d’un graphe ............39

CHAPITRE 4 : PROBLEME DU VOYAGEUR DE COMMERCE .......................... 43

CHAPITRE 5 : PROBLEME D’ORDONNANCEMENT ........................................ 50

5.1 La méthode PERT ....................................................................................50

BIBLIOGRAPHIE ................................................................................................ 57

2
 CHAPITRE 1 : PROGRAMMATION LINÉAIRE
La programmation linéaire est une technique mathématique qui consiste à optimiser (maximiser ou
minimiser) une fonction (appelée fonction-objectif ou encore fonction économique) soumise à des
contraintes d'égalités ou d'inégalités.

Les contraintes sont très variées; elles peuvent être imposées par :

- la condition de non-négativité de l'ensemble des variables ;

- la quantité minimale ou maximale à fabriquer pour chaque produit ;
- la durée de fabrication unitaire pour chaque machine ;
- la durée pendant laquelle chaque machine est disponible ;
- etc.

Généralement ces contraintes s'énoncent dans les termes suivants: "pas plus que", "pas moins que", "au
moins", "au plus", etc. et s'expriment mathématiquement par un système d'inéquations.

1.1 Algorithme primal de simplexe sans matrice identité explicite

Exercice : L’entreprise COTECA vend quatre types de produits. Les ressources nécessaires pour produire
une unité de chaque produit et le prix de vente pour chaque produit sont donnés dans le tableau ci-
dessous. Pour le moment, l’entreprise dispose de 4600 unités de matière première et de 5000 heures de
travail. Pour satisfaire les demandes des clients, l’entreprise doit produire 950 unités de produit, dans
n’importe quelle combinaison pourvu que l’entreprise produise au moins 450 unités de produit de type
4.

Produit 1 Produit 2 Produit 3 Produit 4

Matière première 2 3 4 7
Heures de travail 3 4 5 6
Prix de vente ($) 4 6 7 8

Identifions tout d’abord les contraintes.

Nous allons énumérer les lignes où les contraintes sont reprises.

1ère contrainte : Pour le moment, l’entreprise dispose de 4600 unités de matière première (il s’agit de la
contrainte de la matière première, laquelle est de type ≤ puisque ne disposant que d’une quantité de
4600, pas plus) ;

2ème contrainte : L’entreprise dispose de 4600 unités de matière première et de 5000 heures de travail
(contrainte en termes d’heures de travail, l’entreprise n’en disposant que de 5000, il s’agit encore ici
d’une contrainte de type ≤) ;

3ème contrainte : Pour satisfaire les demandes des clients, l’entreprise doit produire 950 unités de produit,
dans n’importe quelle combinaison (de ces 4600 unités de MP que nous disposons, nous devons produire
950 unités avec n’importe quel produit, cela veut dire qu’avec X₁ nous produirons autant, avec X₂ autant,
etc. mais la production totale doit être égale à 950, il s’agit donc d’une contrainte de type =) ;

4ème contrainte : Pourvu que l’entreprise produise au moins 450 unités de produit de type 4 (il s’agit d’une
contrainte de type ≥ puisque la quantité minimale à produire est de 450).

3
 Modélisons le problème :

Ne connaissant pas les quantités des produits P₁, P₂, P₃ et P₄, nous écrivons ce qui suit :

X₁ P₁
X₂ P₂
X₃ P₃
X₄ P₄

Max 𝜋 = 4x₁+6x₂+7x₃+8x₄

SC 2x₁+3x₂+4x₃+7x₄ ≤ 4600
3x₁+4x₂+5x₃+6x₄ ≤ 5000
x₁+x₂+x₃+x₄ = 950
x₄ ≥ 450
xi ≥ 0 (i = 1….4)

Soulignons que pour chaque type de contrainte, il y a des variables à introduire.

Pour ce qui est des contraintes de type ≤, nous ajouterons la variable d’écart yi. Comme nous avons 2
contraintes de type ≤, nous ajouterons donc 2 variables d’écart yi (y₁ et y₂).
Pour les contraintes de type =, nous ajouterons la variable artificielle zi (z₁ dans notre exemple).
L’on ajoute également la variable zi avec les contraintes de type ≥, sauf qu’avec ce type de contrainte, il
faut en premier lieu retrancher la variable d’écart wi.
La variable d’écart wi à retrancher ne concerne que la
contrainte de type ≥, d’où les zéros sur les autres contraintes
Le 1er tableau se présentera comme suit : et -1 sur la 4ème contrainte.

Variables x₁ x₂ x₃ x₄ w₁
d’écart des Ressources
y₁ 2 3 4 7 0 4600
contraintes respectives
de type ≤. y₂ 3 4 5 6 0 5000 de chaque
z₁ 1 1 1 1 0 950 variable de
z₂ 0 0 0 1 -1 450 base.
FOA -1 -1 -1 -2 1
FO -4 -6 -7 -8 0 0

La production de 450 unités ne

Pour trouver -1 de la 1ère ligne de la fonction-objectif artificielle concerne que le 4ème produit.
(FOA), nous avons additionné z₁ avec z₂ (1+0 = 1), que l’on Il s’agit du PV de chaque produit
multiplie par -1, ce qui donnera -1. Appliquez le même principe que l’on a multiplié par -1 puisqu’il
pour toute la ligne. est question ici d’un problème de
maximisation.

Bien avant de procéder à la première transformation du tableau, nous disons que la solution sera dite
optimale si tous les éléments de la fonction-objectif (FO) sont positifs. Notons que les variables se trouvant
dans la base sont y₁,y₂,z₁ et z₂ et celles se trouvant hors base sont x₁,x₂,x₃, x₄ et w₁.

4
Identifions la colonne pivot et la ligne pivot :

Nous pouvons identifier la colonne pivot à partir de la fonction-objectif artificielle (FOA) ou de la fonction-
objectif (FO) en considérant l’élément négatif le plus petit. Ici nous choisissons la colonne pivot à partir
de la FOA. L’élément négatif le plus petit de la FOA correspond à -2.

x₁ x₂ x₃ x₄ w₁
y₁ 2 3 4 7 0 4600
y₂ 3 4 5 6 0 5000
z₁ 1 1 1 1 0 950
z₂ 0 0 0 1 -1 450
FOA -1 -1 -1 -2 1
FO -4 -6 -7 -8 0 0

Pour trouver la ligne pivot, nous nous servons de la colonne pivot. Nous divisons tout d’abord chaque
ressource par l’élément de la colonne pivot se trouvant sur sa ligne. Par exemple pour la ressource 4600,
nous la divisons par l’élément de la colonne pivot se trouvant sur sa ligne, il s’agit de 7 dans notre exemple
4600
(voir tableau précédent). Nous aurons donc qui nous donne 657,14 et pour les autres éléments nous
7
5000 950 450
aurons : 6 = 833,33, 1 = 950 et 1
= 450. Le plus petit de tous ces rapports correspondra à la ligne
pivot. Et le plus petit rapport dans notre exemple correspond à 450 (450/1=450), provenant de la 4ème
ligne.
1 est appelé élément pivot puisqu’il se trouve dans
l’intersection de la ligne pivot et de la colonne pivot.
Nous aurons ce résultat :

x₁ x₂ x₃ x₄ w₁
y₁ 2 3 4 7 0 4600
y₂ 3 4 5 6 0 5000
z₁ 1 1 1 1 0 950
z₂ 0 0 0 1 -1 450
FOA -1 -1 -1 -2 1
FO -4 -6 -7 -8 0 0

La première transformation du tableau consiste à identifier la variable entrante dans la base et la variable
sortante de celle-ci. Z₂ de la ligne pivot sort de la base et x₄ de la colonne pivot y entre. Les deux variables
échangent leurs places. Les transformations pour trouver le 2ème tableau vont également concerner les
éléments de la ligne pivot, la colonne pivot et les ressources.

Transformation de la ligne pivot :

Prendre chaque élément de la ligne pivot et le diviser par l’élément pivot, excepté l’élément pivot. Nous
aurons ainsi :
0 0 0 −1
= 0, = 0, = 0, = -1
1 1 1 1

5
Transformation de la colonne pivot :

Prendre chaque élément de la colonne pivot et le diviser par l’élément pivot, excepté l’élément pivot. Et
multiplié la réponse trouvée par -1. Nous aurons :

7
= 7, multiplié par -1 nous donne -7
1
6
= 6, multiplié par -1 nous donne -6
1
−2
= -2, multiplié par -1 nous donne 2
1

Procéder ainsi avec les éléments restants.

Transformation des ressources :

E à T : Elément à transformer.

𝑙𝑎 𝑝𝑙𝑢𝑠 𝑝𝑒𝑡𝑖𝑡𝑒 𝑟𝑒𝑠𝑠𝑜𝑢𝑟𝑐𝑒 × élément de la colonne pivot se trouvant sur la ligne de E à T

EàT - ( )
é𝑙é𝑚𝑒𝑛𝑡 𝑝𝑖𝑣𝑜𝑡
450×7 450×6
4600-( ) = 1450, 5000-( ) = 2300, etc…
1 1 Trouvé à partir du tableau
−8×450
NB : Toutes ces transformations sont faites sur base du tableau précédent. précédent en faisant 0− (
1
).

Le nouveau tableau dans lequel nous avons déjà identifié la ligne et la colonne pivot est le
suivant :

x₁ x₂ x₃ z₂ w₁
y₁ 2 3 4 -7 7 1450
y₂ 3 4 5 -6 6 2300
z₁ 1 1 1 -1 1 500
x₄ 0 0 0 1 -1 450
FOA -1 -1 -1 2 -1
FO -4 -6 -7 8 -8 3600

Partant du 3ème tableau, les éléments se trouvant en bas de la ligne pivot du tableau précédent ont été
transformés avec la formule suivante :

é𝑙é𝑚𝑒𝑛𝑡 𝑑𝑒 𝑙𝑎 𝑙𝑖𝑔𝑛𝑒 𝑝𝑖𝑣𝑜𝑡 𝑎𝑢−𝑑𝑒𝑠𝑠𝑢𝑠 𝑑𝑒 E à T × élément de la colonne pivot sur la ligne de E à T

E à T-( )
é𝑙é𝑚𝑒𝑛𝑡 𝑝𝑖𝑣𝑜𝑡
−1(−2) −1(−8)
1-( 1
) = -1 et 0-( 1
) = -8, etc.

6
NB : Soulignons que x₄ et z₂ ont échangé de place (variable entrante et variable sortante) et que la
ligne de 500 a été choisie comme pivot puisque celle de 450 a déjà été utilisée.

Cette-fois, les transformations concerneront tous les éléments pour trouver le nouveau tableau.

Les éléments se trouvant en haut de la ligne pivot sont transformés avec la formule suivante :

é𝑙é𝑚𝑒𝑛𝑡 𝑝𝑖𝑣𝑜𝑡 × élément de la colonne pivot se trouvant sur la ligne de E à T

EàT - ( )
é𝑙é𝑚𝑒𝑛𝑡 𝑝𝑖𝑣𝑜𝑡
Partant du tableau précédent, nous transformons 3 qui est un élément en haut de la ligne pivot, nous
aurons :
1×2
3-( ) = 1 (donc 3 qui est un élément se trouvant en haut de la ligne pivot dans le tableau précédent,
1

deviendra 1 dans le tableau suivant). Appliquez la même formule avec tous les éléments se trouvant en
haut de la ligne pivot. Étant donné que toutes les formules pour transformer les éléments du tableau ont
été énumérées, nous obtenons ce nouveau tableau :

z₁ x₂ x₃ z₂ w₁
y₁ -2 1 2 -5 5 450
y₂ -3 1 2 -3 3 800
x₁ -1 1 1 -1 1 500
x₄ 0 0 0 1 -1 450
FOA 1 0 0 1 0
FO 4 -2 -3 4 -4 5600

Interprétation du tableau : L’entreprise COTECA doit produire 500 unités de produit de type 1 et 450
unités de produit de type 4 pour maximiser son chiffre d’affaires à 5600$. Il lui restera 450 unités de
matière première (ȳ₁ = 450) et elle aura économisé 800 heures de travail (ȳ₂ = 800).

Les éléments du tableau ont été trouvés de la manière suivante, partant du tableau qui vient avant lui :

Elément se trouvant en haut de la ligne pivot :

1×2
4-( 1
) =2

1×2
7-( 1
) =5

Elément se trouvant en bas de la ligne pivot :

1(−4)
-6-( 1
) = -6+4

= -2
1(−4)
-7-( 1
) = -7+4 ce qui donne -3.

7
 −1(−4)
8-( 1
) =4

1(−4)
-8-( ) = -8+4
1

= -4
1(−1)
-1-( 1
) = -1-(-1)

= -1+1 ce qui donne 0.

1(−1)
-1-( 1
) = -1-(-1)

= -1+1 ce qui donne 0.

−1(−1)
2-( ) =1
1

Etant donné que nous n’avons plus de valeurs négatives sur la FOA, on supprime les colonnes des
variables artificielles (z₁ et z₂) et la FOA.

z₁ x₂ x₃ z₂ w₁
y₁ -2 1 2 -5 5 450
y₂ -3 1 2 -3 3 800
x₁ -1 1 1 -1 1 500
x₄ 0 0 0 1 -1 450
FOA 1 0 0 1 0
FO 4 -2 -3 4 -4 5600

Après avoir supprimé ces éléments, nous aurons ce résultat, dans lequel ont été identifiées la ligne
pivot et la colonne pivot :

x₂ x₃ w₁

y₁ 1 2 5 450

y₂ 1 2 3 800

x₁ 1 1 1 500

x₄ 0 0 -1 450

FO -2 -3 -4 5600

Au niveau de la colonne pivot, nous devrions choisir 4 puisqu’il est l’élément négatif le plus petit,
nous avons choisi -2 dans le but de raccourcir les calculs. La solution n’est toujours pas optimale
étant donné que l’on retrouve des éléments négatifs sur la fonction-objectif (FO). Procédons à une
nouvelle transformation du tableau.

8
 y₂ x₂ w₁

x₂ 1 2 5 450

y₂ -1 0 -2 350

x₁ -1 -1 -4 50

x₄ 0 0 -1 450

FO 2 1 6 6500

Trouvé à partir du tableau

précédent en faisant
−2×450
5600− ( 1
).

Interprétation du tableau : L’entreprise COTECA doit produire 50 unités de produit de type 1, 450 unités
de produit de type 2 et 450 unités de produit de type 4, ceci pour maximiser son chiffre d’affaires à 6500$.
Elle économisera 350 heures de travail.

Les calculs suivants ont été effectués pour avoir les éléments du tableau :
Les éléments du tableau ont été trouvés de la manière suivante, partant du tableau qui vient avant lui :
Les ressources :
450(1)
800-( 1
) = 350
450(1)
500-( ) = 50
1
450(0)
450-( 1 ) = 450

Elément se trouvant en bas de la ligne pivot :

2(1)
2-( 1
) = 2-2
=0
5(1)
3-( ) = 3-5
1
= -2
2(1)
1-( 1 ) = -1
5(1)
1-( 1 ) = 1-5
= -4
5(0)
-1-( 1 ) = -1
2(0)
0-( 1 ) = 0
2(−2)
-3-( 1 ) = -3-(-4)
=1
5(−2)
-4-( 1 ) = -4-(-10)
=6

9
 1.2 Algorithme dual de simplexe
Soit le problème P suivant :

P : min 𝜋 = 2x1+3x2

S/C

2x1+x2 ≥ 4
-x1+x2 ≥ 2
x1, x2 ≥ 0
Résoudre ce problème à l’aide de l’algorithme dual du simplexe.
Notons qu’en plus de changer de signe, les contraintes de type ≥ deviennent ≤.
Nous aurons donc :
P : min 𝜋 = 2x1+3x2

S/C

-2x1-x2 ≤ -4
Nous avons ajouté 2
x1-x2 ≤ -2
variables d’écart (une pour
x1, x2 ≥ 0 chaque contrainte). Ces 2
Construisons le tableau : variables d’écart forment
notre matrice unité.

x₁ x₂ y₁ y₂ 1

-2 -1 1 0 -4

1 -1 0 1 -2

2 3 0 0 0

Coefficients de la fonction-
S’il existe au moins une
objectif (FO), provenant de
ressource < 0, la
P : min 𝜋 = 2x1+3x2.
solution n’est pas
Transformons le tableau : optimale.
2 3
Colonne pivot : elle correspond au plus petit rapport entre |−2|
et |−1|. Le plus petit rapport est donc le
2
premier c’est-à-dire |−2| = 1.

Ligne pivot : correspond à la plus petite ressource (-4 avec notre exemple).
Diviser tous les éléments de la ligne pivot (y compris la ressource) par l’élément pivot, excepté l’élément
pivot lui-même. Ce qui nous donnera les résultats suivants :

−1 1 0 −4
= 0,5, =-0,5, = 0, = 2.
−2 −2 −2 −2

10
Chaque élément de la colonne pivot devient 0 et l’élément pivot devient 1 dans le nouveau tableau.

Les éléments en bas de la ligne pivot sont trouvés avec la formule suivante :

E à T : Elément à transformer.
é𝑙é𝑚𝑒𝑛𝑡 𝑑𝑒 𝑙𝑎 𝑙𝑖𝑔𝑛𝑒 𝑝𝑖𝑣𝑜𝑡 𝑎𝑢−𝑑𝑒𝑠𝑠𝑢𝑠 𝑑𝑒 E à T × élément de la colonne pivot sur la ligne de E à T
E à T-( )
é𝑙é𝑚𝑒𝑛𝑡 𝑝𝑖𝑣𝑜𝑡
Nous aurons les résultats suivant en appliquant la formule :
−1×1
-1-( −2
) = -1-0,5
= -1,5
1×1
0-( −2 ) = 0-(-0,5)
= 0+0,5 = 0,5
0×1
1-( −2 ) = 1

−1×2
3-( −2
) = 3-1
=2
1×2
0-( ) = 0-(-1)
−2
= 0+1= 1
0×2
0-( ) = 0
−2

−4×2
0-( −2
) = -4

Les ressources sont transformées avec la formule suivante :

𝑙𝑎 𝑝𝑙𝑢𝑠 𝑝𝑒𝑡𝑖𝑡𝑒 𝑟𝑒𝑠𝑠𝑜𝑢𝑟𝑐𝑒 × élément de la colonne pivot sur la ligne de E à T

EàT - ( )
é𝑙é𝑚𝑒𝑛𝑡 𝑝𝑖𝑣𝑜𝑡
−4×1
-2-( ) = -2-2 ce qui donne -4.
−2

Le nouveau tableau dans lequel sont identifiées la colonne pivot et la ligne pivot est le suivant :

x₁ x₂ y₁ y₂ 1

1 1⁄ −1⁄ 0 2
2 2
0 −3⁄ 1⁄ 1 -4
2 2
0 2 1 0 -4

Etant donné qu’une ressource est < 0, nous transformons à nouveau le tableau.

0 0,5 1 −4
Ligne pivot : = 0, =-0,33, =-0,66, = 2,66.
−1,5 −1,5 −1,5 −1,5

11
Les éléments en haut de la ligne pivot sont trouvés avec la formule suivante :

é𝑙é𝑚𝑒𝑛𝑡 𝑑𝑒 𝑙𝑎 𝑙𝑖𝑔𝑛𝑒 𝑝𝑖𝑣𝑜𝑡 𝑒𝑛−𝑑𝑒𝑠𝑠𝑜𝑢𝑠 𝑑𝑒 E à T × élément de la colonne pivot sur la ligne de E à T

E à T-( )
é𝑙é𝑚𝑒𝑛𝑡 𝑝𝑖𝑣𝑜𝑡

Elément en haut de la ligne pivot :

0,5×0,5
− 0,5 − ( −1,5
) = −1⁄3

1×0,5
0− ( ) = 1⁄3
−1,5

Elément en bas de la ligne pivot :

0,5×2
1− ( −1,5 ) = 5⁄3

1×2
0− (−1,5) = 4⁄3

Les ressources :
−4×0,5
2− ( −1,5
) = 2⁄3

−4×2
−4−( ) = −28⁄3
−1,5

Le résultat sera le suivant :

x₁ x₂ y₁ y₂ 1

1 0 −1⁄ 1⁄ 2⁄
3 3 3
0 1 −1⁄ −2⁄ 8⁄
3 3 3
0 0 5⁄ 4⁄ −28⁄
3 3 3

Toutes les ressources sont > 0, la solution est donc optimale.

Notons que l’algorithme dual de simplexe est une méthode utilisée en programmation
linéaire pour résoudre des problèmes d’optimisation. Contrairement à l’algorithme primal
de simplexe, qui déplace les variables de base vers l’optimalité, l’algorithme dual de
simplexe travaille avec les variables duales pour améliorer la solution. Sa particularité
réside dans le fait qu’il utilise des informations de dualité pour effectuer des pivots dans
le tableau de programmation linéaire. Cela permet de détecter et de traiter les
incohérences dans les contraintes du problème, ce qui peut accélérer la convergence vers
une solution optimale.

12
 CHAPITRE 2 : PROBLÈME DE TRANSPORT
2.1 La règle du Coin Nord-Ouest
Le problème de transport en R.O sont des
2 5 7 problèmes mathématiques qui cherchent à
C=(
3 6 1
) optimiser le transport de marchandises (ou de
9 6 4 personnes) entre des lieux donnés, en
50 50 50 utilisant le moins de ressources possibles. Ses
problèmes se posent souvent dans les
Z = (zi) = (10;4;6;5) situations où il y a des contraintes de
capacités (par exemple, un camion ne peut
W = (wj) = (5;12;8)
transporter qu’un certain nombre de
Où : marchandises), des coûts variables (par
exemple, le coût de transport peut dépendre
C = Matrice de coût de la distance parcourue ou du mode de
Z = La quantité offerte transport utilisé), et des objectifs différents
(par exemple, minimiser les coûts ou
W = La demande
maximiser le profit).
Résolution : Le but de R.O est de trouver les solutions
5 12 8 efficaces. Les solutions obtenues permettent
10 d’optimiser les itinéraires de transport, de
4 réduire les coûts, d’améliorer la productivité
( ) et de maximiser les profits.
6
5

Etape 1 :
Nous avons 10 et la quantité
demandée est de 5, nous donnons
5 12 8 5, il nous restera 5 et la demande
10 sera éliminée.
4
( )
6
5

Nous aurons ce résultat :

0
5 12 8
5 10 5
4
( )
6
5

13
Etape 2 :
Nous avons 5 et la demande est de 12,
étant donné que la demande est
supérieure à l’offre (12>5), nous donnons
0
tout ce que nous avons. L’offre devient
5 12 8
donc 0 et la demande diminue de 7.
5 10 5
4
( )
6
5

Nous aurons ce résultat :

0 7
5 12 8
0 5 10 5 5
4
( )
6
5

Etape 3 :
Nous avons 0 et la demande est de
8, nous mettons simplement 0
puisque l’offre est nulle.
0 7
5 12 8
0 5 10 5 5
4
( )
6
5

Nous aurons ce résultat :

0 7
5 12 8
0 5 10 5 5 0
4
( )
6
5

Etape 4 : Nous avons 4 et la demande

est de 0, nous mettons 0 et
0 7 l’offre restera inchangée.
5 12 8
0 5 10 5 5 0
4
( )
6
5

14
 Etape 5 :
Nous avons 4 et la demande est de 7,
la demande est donc supérieure à
l’offre, nous donnons tout, c’est-à-
0 7
dire 4. La demande reste donc 3.
5 12 8
0 5 10 5 5 0
4 0
( )
6
5

Nous aurons ce résultat :

3
0 7
5 12 8
0 5 10 5 5 0
0 4 0 4
( )
6
5

NB : Si l’offre est égale à 0 et que la demande est supérieure à O, nous mettrons 0. Nous
ferons de même dans le sens inverse.

Si vous avez continué avec cette logique, vous aurez ce résultat à la fin :

0
3 0
0 7 5
5 12 8
0 510 5 5 0
04 0 4 0
( ) Ce résultat forme la matrice de transport, nommée X.
03 6 0 3 3
0 5 0 0 5

5 5 0
0 4 0
X=( ) est un plan de transport admissible.
0 3 3
0 0 5

Pour trouver le coût de transport, nous multiplions la matrice de coût par la matrice
de transport c’est-à-dire C×X.

15
 2 5 7 5 5 0
3 6 1 0 4 0
( ) ( )
9 6 4 0 3 3
50 50 50 0 0 5
= 2×5+5×5+7×0+3×0+6×4+1×0+9×0+6×3+4×3+50×0+50×0+50×5
= 339 FC
IMPORTANT : L’offre peut être des chaises et la demande des chaises bien évidement.
L’offre peut aussi s’agir des tables, des télévisions, des ordinateurs, etc. Cela dépendra
de ce que vous produisez. Et le coût pour transporter ces tables (par exemple) vers la
demande est de 339FC. Il est possible de transporter ces marchandises vers la demande
à un coût inférieur à 339FC, c’est ainsi nous disons que la solution n’est pas optimale
mais plutôt admissible.
2.2 Méthode du minimum de la ligne
Principe : Saturer la 1ère ligne et choisir le 1er élément minimal et aller faire le calcul dans la
matrice de transport, suivant son emplacement. Choisir le 2ème élément minimal et faire de
même jusqu’à la fin de la ligne.

Travaillons avec le même exercice, celui que l’on a utilisé dans la méthode du Coin Nord-Ouest.

C. Le minimum est 5. B. Emplacement de 2

suivant la matrice de
coût.
5 12 8
A. Nous avons choisi le 1er
10 2 5 7
élément minimal de la 1ère
4 3 6 1
( ) C=( ) ligne, et nous allons
6 9 6 4
5 50 50 50 effectuer des calculs au
niveau de la matrice de
Nous aurons ce résultat : transport comme nous
l’avions fait avec la
0 méthode du Coin Nord-
5 12 8 Ouest.
5 10 5
4
( )
6
5 Emplacement de 5
suivant la matrice
Etape 2 : Le minimum est 5. de coût. 5 est le 2ème élément
5 12 8 minimal sur cette
5 10 2 5 7 ligne.
4 3 6 1
( ) C=( )
6 9 6 4
5 50 50 50

16
 Nous aurons ce résultat :
0 7
5 12 8
0 5 10 5 5
4
( )
6
5

Etape 3 :
Pour le dernier élément minimal de la 1ère ligne c’est-à-dire 7 (voir matrice de coût), au
niveau du calcul dans la matrice de transport, nous savons qu’entre 0 et 8, le minimum
est 0. Nous avons donc placé 0.
Entre 4 et 8 le minimum est
4.

Emplacement de 1 suivant
0 7 la matrice de coût. 1 est le premier
5 12 8 élément minimal à la
0 5 10 5 5 0 2 5 7 2ème ligne.
4 3 6 1
( ) C=( )
6 9 6 4
5 50 50 50

Nous aurons ce résultat :

0 7 4
5 12 8
0 5 10 5 5 0
0 4 4
( )
6
5

Etape 4 :
Si vous suivez cette logique et que vous terminez avec la 3ème ligne, vous aurez ce résultat :

5 0 Emplacement de 50 suivant
0 7 4 la matrice de coût.
5 12 8
0 5 10 5 5 0 2 5 7
0 4 0 0 4 3 6 1
( ) C=( )
02 6 0 2 4 9 6 4
5 50 50 50
A la 4ème ligne, il y a 3 éléments minimaux identiques, vous
remarquerez que nous avons choisi celui du milieu comme le
1er élément minimal, puisqu’il permet le plus grand transport.
Autrement dit, dans le calcul au niveau de la matrice de 17
transport, celui du milieu donne un nombre supérieur aux
autres (entre 5 et 0, la valeur la plus élevée est 5).
Nous aurons ce résultat :

0
5 0
0 7 4
5 12 8
0 510 5 5 0 2 5 7
04 0 0 4 3 6 1 Nous nous arrêtons étant
( ) C=( ) donné que tous les
02 6 0 2 4 9 6 4
05 0 5 0 50 50 50 éléments ont été utilisés.

2.3 Méthode du minimum de la colonne

Principe : Saturer la 1ère colonne et choisir le 1er élément minimal et aller effectuer les
calculs dans la matrice de transport, suivant son emplacement. Choisir le 2ème élément
minimal et faire de même jusqu’à la fin de la colonne.

C. 5 est le B. Emplacement de 2
minimum. suivant la matrice de coût.

5 12 8
A. Nous avons choisi le 1er
10 2 5 7
élément minimal de la 1ère
4 3 6 1
( ) C= ( ) colonne et nous allons
6 9 6 4
5 50 50 50 effectuer les calculs au
niveau de la matrice de
Nous aurons ce résultat : coût.

0
5 12 8
5 10 5
4
( )
6
5
Le Emplacement de 3 suivant
Etape 2 : minimum la matrice de coût.
est O. 3 est le 2ème élément
0
5 12 8 minimal de la 1ère
colonne.
5 10 5 2 5 7
4 3 6 1
( ) C =( )
6 9 6 4
5 50 50 50

18
Nous aurons ce résultat :

0
5 12 8
5 10 5
4 0
( )
6
5
Le minimum
Etape 3 :
est 0. Emplacement de 9
suivant la matrice de coût. 9 est le 3ème élément
0
5 12 8 minimal de la 1ère colonne.

5 10 5 2 5 7
4 0
6
( ) c = (
3
9
6
6
1
4
)
5 50 50 50

Nous aurons ce résultat après avoir fini avec la 1ère colonne :

0
5 12 8
5 10 5
4 0
( )
6 0
5 0
Min est 5. Emplacement
Etape 4 :
de 5 suivant la 5 est le 1er élément
0
matrice de coût. minimal de la 2ème
5 12 8 colonne.
5 10 5 2 5 7
4 0 3 6 1
( ) C=( )
6 0 9 6 4
5 0 50 50 50

Nous aurons ce résultat :

0 7
5 12 8
0 5 10 5 5
4 0
( )
6 0
5 0

19
 Etape 5 :
Emplacement de 6
Le minimum suivant la matrice
est 6. 0 7 de coût.
A la 2ème colonne il y a 2 éléments
5 12 8
minimaux identiques c’est-à-dire 6
0 5 10 5 5 2 5 7 et 6. Vous remarquerez que nous
4 0 3 6 1 avons choisi le second comme 2ème
( ) C=( )
6 0 9 6 4 élément minimal, puisqu’il permet
5 0 50 50 50 le plus grand transport. C’est-à-dire
dans le calcul au niveau de la
matrice de transport, le second
donne un nombre supérieur au 1er.
Nous aurons ce résultat :

1
0 7
5 12 8
0 5 10 5 5
4 0
( )
0 6 0 6
5 0
Si vous suivez cette logique jusqu’à épuiser tous les éléments, vous aurez ce résultat :

0
1 0
0 7 5
5 12 8
0 510 5 5 0 2 5 7
03 4 0 1 3 3 6 1
( ) C=( )
06 0 6 0 9 6 4
05 0 0 5 50 50 50

2.4 Méthode du minimum de la matrice

B. Emplacement de
C. Entre 8 1 suivant la matrice
et 4 le min de coût. A. 1 est le premier
est 4. 5 12 8 élément minimal de
10 2 5 7 toute la matrice.
4 3 6 1
( ) C= ( )
6 9 6 4
5 50 50 50

20
 Nous aurons ce résultat :

4
5 12 8
10
0 4 ( 4)
6
5

Etape 2 : Emplacement de 2
suivant la matrice
Le de coût. 2 est le 2ème élément
minimum 4 minimal de toute la matrice.
est 5. 5 12 8
10 2 5 7
0 4 ( 4) C= (
3 6 1
)
6 9 6 4
5 50 50 50
Nous aurons ce résultat :

0 4
5 12 8
5 10 5
0 4 4)
(
6
5

Etape 3 :
Emplacement de 3
Le suivant la matrice
minimum 0 4 de coût. 3 est le 3ème élément
est O. 5 12 8 minimal de toute la matrice.

5 10 5 2 5 7
0 4 4) 3 6 1
( C= ( )
6 9 6 4
5 50 50 50
Nous aurons ce résultat :

0 4
5 12 8
5 10 5
0 4 0 4)
(
6
5

21
 Après avoir fini avec 4 et 5, nous aurons ce résultat :

0
0 7 4
5 12 8
0 5 10 5 5 2 5 7
0 4 0 4) 3 6 1
( C= ( )
2 6 4 9 6 4
5 50 50 50
Etape 4 :
Emplacement de 6 Nous devons trouver le 6ème
Le 0
minimum suivant la matrice de élément minimal de la
0 7 4
est 2. 5 12 8 coût. matrice et nous remarquons
qu’il y a 2 éléments minimaux
0 5 10 5 5 2 5 7 identiques c’est-à-dire 6 et 6.
0 4 0 4) 3 6 1
( C= ( ) Nous choisissons le second
2 6 4 9 6 4
5 50 50 50 puisqu’il offre le plus grand
transport. Cela veut dire
Nous aurons ce résultat : qu’au niveau de la matrice de
5 0 transport il permet d’avoir un
0 7 4 nombre supérieur par rapport
5 12 8 à l’autre.
0 5 10 5 5
0 4 0 4)
(
02 6 2 4
5
Nous aurons ce résultat final :

0
5 0
0 7 4
5 12 8
0 510 5 5 0 2 5 7
04 0 0 4 3 6 1
( ) C=( )
02 6 0 2 4 9 6 4
05 0 5 0 50 50 50

Interprétation de la solution : Nous allons acheminer 5 unités de marchandises vers la

demande au coût de 2 (coût correspondant de 5), 5 unités de marchandises au coût de 5,
etc... Et le coût de transport correspond à 317 FC.

22
 Vous pourriez procéder ainsi pour interpréter les solutions trouvées avec les autres
méthodes. Il est nécessaire de souligner que le coût de transport le plus faible trouver
avec toutes les méthodes (hormis la méthode de tremplin) sera celui qui s’approche le
plus de la solution optimale.

2.5 Méthode de la double préférence

Principe : Prendre en premier lieu les éléments qui sont minimaux sur leur ligne et en
même temps sur leur colonne. Et puis ceux qui sont minimaux soit sur leur ligne, soit sur
leur colonne uniquement. Et pour le reste, prendre un par un les minimaux (ce sont ceux
qui sont minimaux ni sur leur ligne, ni sur leur colonne).

B. Emplacement de 2
C. Le suivant la matrice de coût.
minimum est A. 2 est le 1er élément minimal à la
5 12 8
5. fois sur sa ligne et sa colonne. Nous
10 2 5 7 choisissons selon l’ordre
4 3 6 1 décroissant (du plus grand au plus
( ) C= ( )
6 9 6 4 petit) avec cette catégorie.
5 50 50 50
Nous aurons ce résultat :
0
5 12 8
5 10 5
4
( )
6
5

Etape 2 : Emplacement de 1
suivant la matrice
0 de coût.
Le min 5 12 8 1 est le 2ème élément à la
est 4. fois minimal sur sa ligne
5 10 5 2 5 7
4 3 6 1 et sa colonne.
( ) C= ( )
6 9 6 4
5 50 50 50
Nous aurons ce résultat :

0 4
5 12 8
5 10 5
0 4 4)
(
6
5

23
 Nous allons à présent travailler avec les éléments qui sont le minimaux soit sur leur
ligne, soit sur leur colonne.
Etape 3 : Emplacement de 4
0 4 suivant la matrice de coût.
Le 4 est le premier élément choisi dans
5 12 8 la catégorie de ceux qui sont
minimu
m est 5 10 5 2 5 7 minimaux soit sur leur ligne, soit
4. 0 4 4) 3 6 1 sur leur colonne. Nous les
( C= ( ) choisissons suivant un ordre
6 9 6 4
5 50 50 50 croissant (plus petit au plus grand).

Nous aurons ce résultat :

0
0 4
5 12 8
5 10 5
0 4 4)
(
2 6 4
5

Si vous finissez les calculs avec les éléments qui sont minimaux soit sur leur ligne, soit
sur leur colonne et que vous respectez l’ordre croissant, vous aurez ce résultat :

2 0
0 7 4
5 12 8
0 510 5 5 2 5 7
04 4) 3 6 1
( C= ( )
26 4 9 6 4
05 0 5 0 50 50 50

Les éléments de la 4ème ligne sont tous minimaux sur leurs lignes et non sur leurs
colonnes. Pour choisir le 1er élément, le 2ème et le 3ème, nous allons considérer celui qui
permet le plus grand transport.
Les éléments qui restent ne sont ni les minimaux sur leurs lignes, ni sur leurs colonnes
(3, 6, 6, 7 et 9). Procédez aux calculs selon l’ordre croissant et en respectant le principe
de l’élément qui permet le plus grand transport. Vous aurez à la fin ce résultat :

24
 0
2 0
0 7 4
5 12 8
0 510 5 5 0 2 5 7
04 0 0 4 3 6 1
( ) C=( )
02 6 0 2 4 9 6 4
05 0 5 0 50 50 50

Interprétation de la solution : Nous allons acheminer 5 unités de marchandises vers la

demande au coût de 2 (coût correspondant de 5), 5 unités de marchandises au coût de 5,
etc... Et le coût de transport correspond à 317 FC.
2.6 Méthode d’Approximation de VOGEL
Calculer pour chaque ligne et colonne la différence en valeur absolue entre le 1 er
élément minimal et le 2ème élément minimal.

5 12 8
10 2 5 7
4 3 6 1
( ) C =( )
6 9 6 4
5 50 50 50

Si nous appliquons le principe ci-haut énoncé, nous aurons ce résultat sur la matrice
de coût :

2 5 7 3
3 6 1 2
C =( )
9 6 4 2
50 50 50 0
1 1 3

Pour les avoir nous avons procédé comme suit :

1ère ligne 2-5 = -3, en valeur absolue nous donne 3.
2ème ligne 1-3 = -2, en valeur absolue nous donne 2.
3ème ligne 4-6 = -2, en valeur absolue nous donne 2.
4ème ligne 50-50 = 0

1ère colonne 2-3 = -1, en valeur absolue nous donne 1.

2ème colonne 5-6 = -1, en valeur absolue nous donne 1.

25
 3ème colonne 1-4 = -3, en valeur absolue nous donne 3.

Nous prenons la plus grande de toutes les valeurs trouvées au niveau des lignes (entre
3, 2, 2 et 0, la plus grande valeur est 3). Et puis nous sélectionnons le coût le plus faible
sur la ligne de 3, ce coût correspond à 2.
Emplacement de
Le 2 suivant la 2 est le coût le plus
minimum 5 12 8
matrice de coût. faible sur la ligne de 3.
est 5. 10 2 5 7
4 3 6 1
( ) C =( )
6 9 6 4
5 50 50 50

Nous aurons ce résultat :

0
5 12 8
5 10 5 2 5 7 3
4 3 6 1 2
( ) C =( )
6 9 6 4 2
5 50 50 50 0
1 1 3

La colonne de 2 supprimée, nous restons avec la matrice suivante :

5 7 2
6 1 5
C =( )
6 4 2
50 50 0
1 3

1ère ligne 5-7 = -2, en valeur absolue 2.

2ème ligne 1-6 = -5, en valeur absolue 5.
3ème ligne 4-6 = -2, en valeur absolue 2.
4ème ligne 50-50 = 0.

1ère colonne 5-6 = -1, en valeur absolue 1.

2ème colonne 1-4 = -3, en valeur absolue 3.

La plus grande de toutes les valeurs trouvées au niveau des lignes correspond à 5, et le
coût le plus faible sur la ligne de 5 est 1.

26
 Emplacement de 1
Le suivant la matrice
minimum 0
de coût. 1 est le coût le plus
faible sur la ligne de 5.
est 4. 5 12 8
5 10 5 5 7 2
4 6 1 5
( ) C =( )
6 6 4 2
5 50 50 0
1 3

Le résultat impliquera cette fois-ci la suppression de la ligne de 1. Donc avec ce

problème, c’est d’abord la colonne qui sera supprimée, puis la ligne, etc. Pour arriver au
dernier calcul (C = (5)5 ), nous supprimerons successivement deux lignes pour pouvoir
travailler avec 5.
Nous aurons donc ce résultat :

0 4
5 12 8
5 10 5
0 4 4)
(
6
5
La ligne de 1 supprimée, nous restons avec la matrice suivante :

5 7 2
C =(6 4 )2
50 50 0
1 3
Nous avons 2 valeurs (les plus grandes) trouvées au niveau des lignes, il s’agit de 2 et 2. Nous
choisissons celle dont la valeur la plus petite sur la ligne est inférieure à celle de l’autre (4 est
inférieur à 5).

Emplacement de
4 suivant la
matrice de coût. 4 est le coût le plus
Le faible sur la ligne de 2.
0 4
minimum
5 12 8
est 4.
5 10 5
5 7 2
0 4 4)
( C=(6 4 )2
6
50 50 0
5
1 3

27
 Le résultat impliquera la suppression de la colonne de 4.

Nous aurons donc ce résultat :

0
0 4
5 12 8
5 10 5
5 7 2
0 4 4)
( C =(6 4 )2
2 6 4
50 50 0
5
1 3

La colonne de 4 supprimée, nous aurons ce résultat :

5 5
C=(6) 6
50 50
1
Et si vous poursuivez avec cette logique, vous aurez ce résultat final :

0
5 0
0 7 4
5 12 8
0 510 5 5 0
04 0 0 4
( ) C = (5)5
02 6 0 2 4
05 0 5 0

Interprétation de la solution : Nous allons acheminer 5 unités de marchandises vers la

demande au coût de 2 (coût correspondant de 5), 5 unités de marchandises au coût de 5,
etc... Et le coût de transport correspond à 317 FC.

2.7 Méthode de fréquence

Dans la méthode de fréquence pour résoudre les problèmes de transport, on examine
combien de fois différents itinéraires sont utilisés pour transporter des marchandises.
Plus un itinéraire est utilisé souvent, plus il a de "fréquence". On utilise cette information
pour décider quels itinéraires sont les meilleurs. On veut choisir les itinéraires les moins
chers et les plus efficaces, mais on tient compte aussi de leur fréquence d'utilisation.
Ainsi, on préfère généralement les itinéraires fréquemment utilisés, sauf s'ils sont trop

28
coûteux. L'idée est de trouver un équilibre entre les itinéraires populaires et les
itinéraires moins utilisés pour obtenir la solution la plus économique.

2 5 7
3 6 1
C=( )
9 6 4
50 50 50
1ère étape :
Calculons les r. Etant donné que nous avons 4 lignes sur la matrice, nous aurons r4.
Pour trouver r1, nous regardons le nombre d’éléments composant la 1ère ligne, il y a donc
3 éléments qui composent la 1ère ligne (2, 5 et 7). 2+5+7 = 14.
1 1
Nous aurons r1 = 3 (2+5+7) = 3 (14)
1 1
Notons que 3
vient de 𝑛
.

Pour trouver r2, r3 et r4 faites la même chose.

1 1
NB : r1 = 3 provient donc de la formule suivante : r𝑖 = 𝑛 ∑𝑛𝑗=1 𝐶𝑖𝑗

Nous aurons ce résultat :

1 1
r₁ = 3 (2 + 5 + 7) = 3 (14)
2 5 7 1 1
3 6 1 r₂ = 3 (3 + 6 + 1) = 3 (10)
C=( ) 1 1
9 6 4 r₃ = 3 (9 + 6 + 4) = 3 (19)
50 50 50 1 1
r₄ = 3 (50 + 50 + 50) = 3 (150)

Pour aboutir à un plan de transport faisable, nous devons trouver la matrice c,̃ et pour ce
faire, nous aurons besoin de la somme d’éléments composant la 1ère colonne, la 2ème
colonne et la 3ème colonne de la matrice de coût.

De la formule
1
× 64 Somme des éléments de la 1ère colonne (2+3+9+50).
4

Nombre d’éléments composant la 1ère

colonne c’est-à-dire 2, 3, 9 et 50.

Si vous faites de même avec les colonnes restantes, vous aurez ceci :

29
 1 1
r₁ = 3 (2 + 5 + 7) = 3 (14)
2 5 7 1 1
3 6 1 r₂ = 3 (3 + 6 + 1) = 3 (10)
C=( ) 1 1
9 6 4 r₃ = 3 (9 + 6 + 4) = 3 (19)
50 50 50 1 1
r₄ = 3 (50 + 50 + 50) = 3 (150)
1 1 1
× 64 × 67 × 62
4 4 4

Formons à présent la matrice c.̃ Nous allons trouver les éléments qui composent la 1ère
ligne de ladite matrice.
2, 5 et 7 sont les éléments de la 1ère ligne de la matrice de coût, procédons à leur
transformation.
14
Pour 2 = ( 3 + 16) − 2

3 est le dénominateur commun, nous aurons donc :

14+48
= 3 14+48
62
= −2
3

3 est le dénominateur commun, nous aurons donc :

62−6
= 3
56
= ce qui donne 18,67.
3

1 67
Sa colonne correspondante 4 × 64 = = 16,75.
14 4
Pour 5 = ( 3 + 16,75) − 5

2 est le dénominateur commun, nous aurons donc :

14+50,25
= 3
64,25
= −5
3

3 est le dénominateur commun, nous aurons donc :

64,25−15
= 3
49,25
= ce qui donne 16,41.
3
14
Pour 7 = ( 3 + 15,5) − 7
14+46,5
= 3
60,5−7
= 3

30
 60,5−21
= 3
39,5
= ce qui donne 13,16.
3

La réponse finale est la suivante :

18,67 16,41 13,16

c̃ =(
16,33
13,33
14,08 17,83
17,08 17,83
)
16 16,75 15,5

2.8 Problème d’affectation

Le problème d’affectation en R.O consiste à affecter des ressources à des taches de

manière optimale, en minimisant le coût ou le temps de réalisation, tout en respectant
certaines contraintes. Par exemple, dans une entreprise de transport, le problème
d’affectation pourrait consister à décider quel camion doit transporter quelle cargaison.
Chaque camion a une capacité maximale de transport et chaque cargaison a un poids
différent. Le but serait de minimiser le coût total de transport tout en satisfaisant les
contraintes de capacité de chaque camion.
Les ressources peuvent être des travailleurs, des machines, des véhicules et les taches
peuvent être des missions, des projets, des activités, etc.

𝟐 𝟑 𝟓 𝟖
𝟏 𝟕 𝟗 𝟔
( )
𝟗 𝟔 𝟖 𝟔
𝟐 𝟒 𝟕 𝟒
Appliquons la technique de Flood, laquelle consiste à choisir en premier lieu le minimum
de chaque ligne et à le soustraire de toute la ligne. Puis choisir le minimum de chaque
colonne et le soustraire de toute la colonne.

𝟐 𝟑 𝟓 𝟖 𝟐
𝟏 𝟕 𝟗 𝟔 𝟏
( )
𝟗 𝟔 𝟖 𝟔 𝟔
𝟐 𝟒 𝟕 𝟒 𝟐
Nous aurons ce résultat :

𝟎 𝟏 𝟑 𝟔
𝟎 𝟔 𝟖 𝟓
( )
𝟑 𝟎 𝟐 𝟎
𝟎 𝟐 𝟓 𝟐

31
Faisons l’opération avec les colonnes.

𝟎 𝟏 𝟑 𝟔
𝟎 𝟔 𝟖 𝟓
( )
𝟑 𝟎 𝟐 𝟎
𝟎 𝟐 𝟓 𝟐
0 0 2 0

Le Flood garantit une solution optimale en examinant toutes les options, bien que cela
puisse être couteux en termes de temps de calcul pour les problèmes de grande taille.
Ce qui nous donne ce résultat :

𝟎 𝟏 𝟏 𝟔
𝟎 𝟔 𝟔 𝟓
( )
𝟑 𝟎 𝟎 𝟎
𝟎 𝟐 𝟑 𝟐

Nous allons appliquer la méthode hongroise (ainsi dénommée en souvenir d'un théorème
assez célèbre du mathématicien hongrois, KÖNIG) pour résoudre notre problème
d’affectation.
Etape 2 :
Pour chaque ligne, nous allons déterminer le nombre de zéros. Nous procédons comme
suit :
𝟎 𝟏 𝟏 𝟔 𝟏
𝟎 𝟔 𝟔 𝟓 𝟏
( )
𝟑 𝟎 𝟎 𝟎 𝟑
𝟎 𝟐 𝟑 𝟐 𝟏

Choisir la ligne qui a le moins de zéros, s’il en existe plusieurs (1ère ligne, 2ème ligne et
4ème ligne dans notre exemple), choisir la 1ère et son zéro se trouvant le plus à gauche (0),
barrez les zéros se trouvant sur la ligne et la colonne de celui-ci (0).
𝟎 𝟏 𝟏 𝟔 𝟏
𝟎 𝟔 𝟔 𝟓 𝟏
( )
𝟑 𝟎 𝟎 𝟎 𝟑
𝟎 𝟐 𝟑 𝟐 𝟏

Nous refaisons l’opération. Après la ligne 1, c’est maintenant la ligne 3 qui comporte le
moins de zéros.
𝟎 𝟏 𝟏 𝟔 𝟏
𝟎 𝟔 𝟔 𝟓 𝟏
( )
𝟑 𝟎 𝟎 𝟎 𝟑
𝟎 𝟐 𝟑 𝟐 𝟏

32
Si avec toutes les lignes, les zéros ont été encadrés (ici nous colorons ces-derniers en vert),
alors la solution serait optimale. Ici la solution n’est pas encore optimale.

Nous allons procéder à une modification du tableau et répéter l’étape 2.

Etape 3 : Marquer toutes les lignes sans zéro encadré (sans zéro coloré).
𝟎 𝟏 𝟏 𝟔
𝟎 𝟔 𝟔 𝟓
( )
𝟑 𝟎 𝟎 𝟎
𝟎 𝟐 𝟑 𝟐

Marquer toute colonne ayant un zéro barré sur une ligne marquée.
𝟎 𝟏 𝟏 𝟔
𝟎 𝟔 𝟔 𝟓
( )
𝟑 𝟎 𝟎 𝟎
𝟎 𝟐 𝟑 𝟐

Marquer toute ligne ayant un zéro encadré (zéro coloré) dans une colonne marquée.

𝟎 𝟏 𝟏 𝟔
𝟎 𝟔 𝟔 𝟓
( )
𝟑 𝟎 𝟎 𝟎
𝟎 𝟐 𝟑 𝟐

Etape 4 : Mettre un trait sur les lignes non marquées et sur les colonnes marquées.

𝟎 𝟏 𝟏 𝟔
𝟎 𝟔 𝟔 𝟓
( )
𝟑 𝟎 𝟎 𝟎
𝟎 𝟐 𝟑 𝟐

Etape 5 : Rechercher le plus petit élément des cases traversées par aucun trait et
soustraire cet élément de ces cases. Ici cet élément est 1. Et après, additionner cet
élément à toute case traversée par 2 traits. La case traversée par 2 traits est 3.

𝟎 𝟎 𝟎 𝟓
𝟎 𝟓 𝟓 𝟒
( )
𝟒 𝟎 𝟎 𝟎
𝟎 𝟏 𝟐 𝟏

Refaire l’étape 2.

33
 𝟎 𝟎 𝟎 𝟓 𝟑
𝟎 𝟓 𝟓 𝟒 𝟏
( )
𝟒 𝟎 𝟎 𝟎 𝟑
𝟎 𝟏 𝟐 𝟏 𝟏

𝟎 𝟎 𝟎 𝟓 𝟑
𝟎 𝟓 𝟓 𝟒 𝟏
( )
𝟒 𝟎 𝟎 𝟎 𝟑
𝟎 𝟏 𝟐 𝟏 𝟏

Etape 5 :

𝟏 𝟎 𝟎 𝟓
𝟎 𝟒 𝟒 𝟑
( )
𝟓 𝟎 𝟎 𝟎
𝟎 𝟎 𝟏 𝟎

Refaire l’étape 2 pour voir si la solution est optimale.

𝟏 𝟎 𝟎 𝟓 𝟐
𝟎 𝟒 𝟒 𝟑 𝟏
( )
𝟓 𝟎 𝟎 𝟎 𝟑
𝟎 𝟎 𝟏 𝟎 𝟑

𝑾₁ 𝑾₂ 𝑾₃ 𝑾₄
𝒁₁ 𝟏 𝟎 𝟎 𝟓
𝒁₂ 𝟎 𝟒 𝟒 𝟑
( )
𝒁₃ 𝟓 𝟎 𝟎 𝟎
𝒁₄ 𝟎 𝟎 𝟏 𝟎

La solution est optimale puisqu’avec toutes les lignes, les zéros ont été encadrés (ici nous
colorons ces-derniers en vert comme nous l’avons dit). Le coût d’affectation correspond à
3+1+8+4 ce qui donne 16.
Z1 avec W2
Z2 avec W1
Z3 avec W3
Z4 avec W4

2.9 Méthode de tremplin ou algorithme de Stepping Stone

Les solutions trouvées avec les autres méthodes ont été admissibles mais non optimales,
nous utilisons donc cette méthode pour rendre ces-dernières optimales. Prenons au
hasard n’importe quelle solution trouvée avec les autres méthodes et nous allons
appliquer la méthode de tremplin dans le but de rendre celle-ci optimale.

34
Nous prenons la solution trouvée à partir de la règle du Coin Nord-Ouest et la matrice de
coût y relative.
Une illustration de la non optimalité de
la solution qui a été trouvée est que dans
5 5 0 2 5 7 la matrice de coût, 1 qui correspond au
0 4 0 3 6 1 coût le plus faible n’a pas été transporté
X=( ) C =( )
0 3 3 9 6 4 dans la matrice de transport.
0 0 5 50 50 50
Nous nommons les éléments de la matrice de coût comme suit :

Qui signifie première ligne, première colonne.

𝐶₁₁ 𝐶₁₂ 𝐶₁₃

𝐶₂₁ 𝐶₂₂ 𝐶₂₃
C=( )
𝐶₃₁ 𝐶₃₂ 𝐶₃₃
𝐶₄₁ 𝐶₄₂ 𝐶₄₃
Partant de la matrice X, nous identifions les éléments supérieurs à zéro (nous les colorons
en rouge).
𝐶₁₁ 𝐶₁₂ 𝐶₁₃
𝐶₂₁ 𝐶₂₂ 𝐶₂₃
X=( )
𝐶₃₁ 𝐶₃₂ 𝐶₃₃
𝐶₄₁ 𝐶₄₂ 𝐶₄₃
Etape 1 : Test d’optimalité de la solution courante1
Nous aurons besoin pour faire ce test, de la matrice C*, laquelle ressemble au tableau
suivant :

v₁ v₂ v₃ v/u
u₁
u₂
u₃
u₄

1
Nous nous limitons à v₃ étant donné que la matrice X a 3 colonnes. Nous nous limitons à u₄ étant
donné que la matrice X a 4 lignes.

35
Posons V₁ = 0
Pour c4̃ 1 on a : u₄+v₁-c41
Et calculons premièrement les éléments supérieurs à zéro dans la matrice X.
= 49+0-50
Pour C₁₁ on a : u₁+v₁ = C₁₁ = -1
u₁+0 = 2 (2 est la valeur de C₁₁ partant de la matrice de coût)
u₁ = 2 Pour c4̃ 2 on a : u₄+v₂-c₄₂
= 49+3-50
Pour C₁₂ on a : u₁+v₂ = c₁₂ =2
2+v₂ = 5
v₂ = 5-3 Pour c3̃ 1 on a : u₃+v₁-c₃₁
v₂ = 3 = 3+0-9
= -6

Pour C₂₂ on a : u₂+v₂ = c₂₂ Nous pouvons donc insérer les résultats obtenus dans la matrice C* en
u₂+3 = 6 notant que les éléments supérieurs à zéro que l’on vient de calculer seront
u₂ = 6-3 remplacés par des zéros dans la partie colorée en vert du tableau.
u₂ = 3
0 3 1 v/u
Pour C43 on a : u₄+v₃ = c43 0 0 -4 2
u₄+1 = 50 0 0 3 3
u₄ = 50-1 -6 0 0 3
u₄ = 49 -1 2 0 49

Pour C32 on a : u₃+v₂ = c₃₂ Le résultat est dit optimal lorsque tous les éléments qui sont colorés en
u₃+3 = 6 vert dans la matrice C* sont ≤ 0.
u₃ = 6-3
u₃ = 3 Etant donné que le résultat ne pas optimal, nous déterminons une
nouvelle solution. Nous allons étiqueter la matrice de transport (nommée
Pour C33 on a : u₃+v₃ = c₃₃ X), à partir de la matrice C*.
3+v₃ = 4
v₃ = 4-3 Principe pour étiqueter : Partant de la matrice C*, voir la place du plus
v₃ = 1 grand positif (3 dans notre exemple) et étiqueter l’élément se trouvant sur
son emplacement dans la matrice X du signe « + », ce qui nous donnera 0+.
Sur la matrice X, voir sur la ligne de 0+ un élément différent de 0 sur la
Calculons les éléments égaux à zéro dans la matrice X, donc les éléments restants.
colonne duquel se trouve au moins un élément positif et l’étiqueter du
signe « - », ce qui donnera 4-, sur la colonne de 4-, voir un élément différent
Pour Ĉ13 on a : u₁+v₃-c₁₃
de 0 et l’étiqueter du signe « + », ce qui donnera 3+, sur la ligne de 3+, voir
= 2+1-7 (7 est la valeur de c₁₃ partant de la matrice de coût)
un élément différent de 0 et l’étiqueter du signe « - », ce qui donnera 3-.
= -4
Pour Ĉ21 on a : u₂+v₁-c₂₁
Le résultat sera le suivant :
= 3+0-3
=0 5 5 0
Pour c2̃ 3 on a : u₂+v₃-c₂₃ 0 4⁻ 0⁺
X(1) =( )
= 3+1-1 0 3⁺ 3⁻
=3 0 0 5

36
Trouvons la matrice X(2) et sa matrice C* afin de voir si la solution est optimale. Pour C₂₂ on a : u₂+v₂ = c₂₂
u₂+3 = 6
Pour construire la matrice X(2), nous observons la matrice X(1) et choisissons u₂ = 6-3
parmi les éléments étiquetés par le signe -, celui ayant une valeur absolue u₂ = 3
minimale. Nous additionnons ou soustrayons cet élément selon qu’il s’agit des
signes, avec tous les éléments étiquetés. En termes simples, pour 4-, étant donné Pour C23 on a : u2+v₃ = c23
qu’il a le signe « - », nous aurons 4-3 (3 étant l’élément à valeur absolue minimale 3+v₃ = 1
de tous les éléments étiquetés du signe -), ce qui nous donnera 1. Pour 0+, étant v₃ = 1-3
donné qu’il a le signe « + », nous aurons 0+3, ce qui nous donnera 3. Appliquez la
v₃ = -2
même logique avec 3+ et 3- .
Pour C32 on a : u3+v2 = c32
Nous aurons le résultat suivant :
u3+3 = 6
u3 = 6-3
5 5 0
0 1 3 u3 = 3
X(2) =( )
0 6 0
0 0 5 Pour C43 on a : u4+v₃ = c43
u4-2 = 50
Construisons la matrice C* de la matrice X(2) pour voir si la solution est optimale. u4 = 50+2
Au cas où la solution ne sera pas optimale, nous allons de nouveau étiqueter la u4 = 52
matrice X(2) et poursuivre les calculs.
Calculons les éléments égaux à zéro dans la matrice X(2), donc les éléments
Pour construire la matrice C* de la matrice X(2),
nous faisons comme au début, restants.
c’est-à-dire nous partons de la matrice X , nous identifions les éléments
(2)

supérieurs à zéro (nous les colorons en rouge). Pour c1̃ 3 on a : u₁+v₃-c₁₃

= 2-2-7 (7 est la valeur de c₁₃ partant de la matrice de coût)
𝐶₁₁ 𝐶₁₂ 𝐶₁₃ = -7
𝐶₂₁ 𝐶₂₂ 𝐶₂₃ Pour c3̃ 3 on a : u3+v₃-c33
X(2) =( )
𝐶₃₁ 𝐶₃₂ 𝐶₃₃ = 3-2-4
𝐶₄₁ 𝐶₄₂ 𝐶₄₃ = -3
Pour c4̃ 2 on a : u₄+v2-c42
Etape 1 : Test d’optimalité de la solution courante = 52+3-50
=5
Posons V₁ = 0
Pour c3̃ 1 on a : u₃+v₁-c₃₁
Et calculons premièrement les éléments supérieurs à zéro dans la matrice X(2). = 3+0-9
= -6
Pour C₁₁ on a : u₁+v₁ = C₁₁ Pour c2̃ 1 on a : u2+v₁-c21
u₁+0 = 2 (2 est la valeur de C₁₁ partant de la matrice de coût) = 3+0-3
u₁ = 2 =0
Pour C₁₂ on a : u₁+v₂ = c₁₂ Pour c4̃ 1 on a : u4+v₁-c41
2+v₂ = 5 = 52+0-50
v₂ = 5-3 =2
v₂ = 3

37
Nous pouvons donc insérer les résultats obtenus dans la matrice C*.

0 3 -2 v/u
0 0 -7 2
0 0 0 3
-6 0 -3 3
2 5 0 52

Etant donné que la solution ne pas optimale, nous déterminons une nouvelle solution.
Nous allons étiqueter la matrice X(2), à partir de la matrice C* de cette-dernière.

Partant de la matrice C* de la matrice X(2), voir la place du plus grand positif (5 dans
notre exemple) et étiqueter l’élément se trouvant sur son emplacement dans la matrice
X(2) du signe « + », ce qui nous donnera 0+, voir sur la ligne de 0+ un élément différent de
0 dans la colonne duquel se trouve au moins un élément positif et l’étiqueter du signe « -
», ce qui donnera 5-, sur la colonne de 5-, voir un élément différent de 0 et l’étiqueter du
signe « + », ce qui donnera 3+, sur la ligne de 3+, voir un élément différent de 0 et l’étiqueter
du signe « - », ce qui donnera 1-.

Le résultat sera le suivant :

5 5 0
0 1⁻ 3⁺
X(2) =( )
0 6 0
0 0⁺ 5⁻

Si vous poursuivez la même démarche c’est-à-dire vous trouvez la matrice X(3) et sa

matrice C* afin de voir si la solution est optimale et que vous continuez les calculs, vous
aurez ce résultat final, lequel est optimal puisque tous les éléments qui sont colorés en
vert dans la matrice C* sont ≤ 0.

0 3 1 v/u
5 5 0 0 0 -4 2
0 0 4
X(4) =( ) -3 -3 0 0
0 2 4
-6 0 0 3
0 5 0
-3 0 -2 47

ASTUCE : Dans les calculs des éléments supérieurs à zéro (test d’optimalité de la solution
courante), si vous ne parvenez pas à trouver la valeur d’une inconnue d’un élément donné,
poursuivez les calculs avec les autres éléments et certainement, cette inconnue sera
trouvée.

38
 CHAPITRE 3 : THÉORIE DE GRAPHES
3.1 La détermination des composants fortement connexes d’un graphe
Exemple :
Soit le graphe suivant :

n2

n1 n5
n4

n3

Une composante fortement connexe d’un graphe orienté est un sous graphe induit maximal
en nombre de sommets qui soit fortement connexe.
Partant de notre graphe, nous pouvons identifier une composante fortement connexe. Nous
avons ici identifié le graphe n2, n3 et n4. Cela veut dire que nous pouvons faire un contour à
partir de ces 3 sommets.

n2

n1 n5
n4

n3

39
 𝑛₁ 𝑛₂ 𝑛₃ 𝑛₄ 𝑛₅ 4 arcs partent de n1, 1 arc vers n2, 1 arc
𝑛₁ 0 1 1 1 1 vers n3, 1 arc vers n4 et 1 arc vers n5.
𝑛₂ 0 0 1 0 1
A (G) = 𝑛₃ 0
*
0 0 1 1
𝑛₄ 0 1 0 0 1
𝑛₅ (0 0 0 0 0)

La matrice A(O) correspond à l’addition de la matrice A*(G) avec la matrice unité2. Nous
aurons donc :

0 1 1 1 1 1 0 0 0 0
0 0 1 0 1 0 1 0 0 0
A(O) = A (G) + I =
*
0 0 0 1 1 + 0 0 1 0 0
0 1 0 0 1 0 0 0 1 0
(0 0 0 0 0) (0 0 0 0 1)

1 1 1 1 1
0 1 1 0 1
A(O) = 0 0 1 1 1
0 1 0 1 1
(0 0 0 0 1)

Etant donné que nous avons 5 sommets, nous ferons successivement 5 itérations partant de
la matrice A(O). Le but ici est de trouver la matrice à (G'), laquelle correspond à la solution.
Principe d’itération : Encerclez la 1ère ligne et la 1ère colonne de la matrice à la première
itération, encerclez la 2ème ligne et la 2ème colonne de la matrice à la deuxième itération, etc.
Nous transformerons uniquement les éléments non encerclés correspondants à 0 et ayant des
éléments encerclés sur leurs lignes correspondants à 1 et sur leurs colonnes correspondants
à 1.

2
La matrice unité est, en algèbre linéaire, une matrice carrée avec des 1 sur la diagonale
et des 0 partout ailleurs.
40
Nous aurons donc :

1 1 1 1 1 Parmi les éléments non encerclés dans cette

0 1 1 0 1 matrice, aucun correspondant à 0 n’a
A(O) = 0 0 1 1 1 d’élément encerclé sur sa ligne correspondant
0 1 0 1 1 à 1 et sur sa colonne correspondant à 1. Il n’y
(0 0 0 0 1) aura donc pas de changement, la matrice
suivante aura les mêmes éléments.

1 1 1 1 1 Parmi les éléments non encerclés dans cette

0 1 1 0 1
matrice, 1 seul correspondant à 0 n’a d’élément
A(1) = 0 0 1 1 1
encerclé sur sa ligne correspondant à 1 et sur
0 1 0 1 1
(0 0 0 0 1) sa colonne correspondant à 1. Donc dans la
matrice suivante 0 deviendra 1.

1 1 1 1 1
0 1 1 0 1
A(2) = 0 0 1 1 1 Dans cette matrice, c’est 0 qui changera.
0 1 1 1 1
(0 0 0 0 1)

1 1 1 1 1
0 1 1 1 1
A(3) = 0 0 1 1 1 Dans cette matrice, c’est bien 0 qui deviendra 1.
0 1 1 1 1
(0 0 0 0 1)

1 1 1 1 1
0 1 1 1 1
A(4) = 0 1 1 1 1
0 1 1 1 1
(0 0 0 0 1)

Arriver au terme de la 4ème itération, nous procédons comme suit :

41
 Ce bloc dans lequel
1 est repris 3 fois ne
sera constitué que
d’un seul 1 dans la
matrice à (G').

Ce bloc dans lequel 1 1 1 1 1

0 est repris 3 fois ne 0 1 1 1 1 Nous avons regroupé les lignes et les colonnes
A(5) = 0 1 1 1 1 équivalentes. Dans cette matrice, les 3
sera constitué que
d’un seul 0 dans la
0 1 1 1 1 colonnes encerclées en bleu correspondent aux
matrice à (G'). (0 0 0 0 1) 3 lignes encerclées également en bleu.

Partant donc de notre graphe, il est possible d’atteindre, à partir de n₁, le bloc n₂, n₃ et n₄.
On peut également atteindre n₅.

1 1 1
à (G') = (0 1 1)
0 0 1

A*(G') = Ã (G') - I

Pour avoir ce résultat, on a retranché les

1 1 1 1 0 0 éléments de la diagonale principale de la
A (G') = (0
*
1 1) - (0 1 0)
0 0 1 0 0 1 matrice à (G') avec les éléments de la diagonale
principale de la matrice unité et avons repris les
éléments hors diagonale principale de la matrice Ã
0 1 1 (G').
A* (G') = (0 0 1)
0 0 0

42
 CHAPITRE 4 : PROBLÈME DU VOYAGEUR DE COMMERCE
La méthode du voyageur de commerce (TSP - Traveling Salesman Problem en anglais) est
un problème d'optimisation combinatoire qui cherche à trouver le chemin le plus court
pour visiter un ensemble de villes données une seule fois et revenir à la ville de départ. Ce
problème est un NP (Non-deterministic Polynomial Time) difficile, ce qui signifie qu'il
n'existe pas d'algorithme efficace pour résoudre de manière exacte les instances de grande
taille en un temps raisonnable.
Dans un contexte africain, nous pouvons illustrer la méthode du voyageur de commerce en
considérant un vendeur qui souhaite visiter plusieurs grandes villes d'Afrique de l'Ouest
pour présenter ses produits. Supposons que les villes à visiter soient Dakar (Sénégal),
Abidjan (Côte d'Ivoire), Accra (Ghana) et Lagos (Nigeria). Le vendeur cherche à trouver le
chemin le plus court pour visiter ces villes une seule fois et revenir à Dakar.

Exemple : Soit la matrice de coût suivante décrivant complètement le graphe correspondant 𝒩.

1 2 3 4 5
C̄ = 1 ∞ 3 9 8 2
2 2 ∞ 9 4 5
3 1 7 ∞ 9 5
4 3 5 6 ∞ 4
5 1 6 8 4 ∞

Etape 1 : Identifier le minimum de chaque ligne et le soustraite avec toute sa ligne.

1 2 3 4 5
C̄ = 1 ∞ 3 9 8 2 2
2 2 ∞ 9 4 5 2
3 1 7 ∞ 9 5 1
4 3 5 6 ∞ 4 3
5 1 6 8 4 ∞ 1

1 2 3 4 5
1 ∞ 1 7 6 0
2-2 = 0
C̄ = 2 0 ∞ 7 2 3
3 0 6 ∞ 8 4 5-2 = 3
4 0 2 3 ∞ 1
5 0 5 7 3 ∞

Etape 2 : Identifier le minimum de chaque colonne et le soustraite avec toute sa colonne.

43
 1 2 3 4 5
1 ∞ 1 7 6 0
2 0 ∞ 7 2 3
3 0 6 ∞ 8 4
4 0 2 3 ∞ 1
5 0 5 7 3 ∞
0 1 3 2 0

1 2 3 4 5
1 ∞ 0 4 4 0
C= 2 0 ∞ 4 0 3
3 0 5 ∞ 6 4
4 0 1 0 ∞ 1
5 0 4 4 1 ∞

0-0 = 0 5-1 = 4

Constance de réduction3 r๐ = 15 (somme tous les minimaux, ligne et colonne. Donc

2+2+1+3+1+0+1+3+2+0).
Etape 3 : Identifier l’élément de valeur nulle (0) de chaque ligne, et trouver la somme du
minimum de la ligne et de la colonne sur lesquelles le 0 se situe (en ne tenant pas compte du
0 sur lequel nous travaillons).
S’il existe un 2ème élément de valeur nulle (0) sur une même ligne, faites avec lui la même
procédure.

1 2 3 4 5 0 est le 1er élément de valeur nulle

sur sa ligne, il est marqué de
C= 1 ∞ 01 4 4 01
l’exposant 1, puisque 1 constitue la
2 00 ∞ 4 01 3 somme du minimum de sa ligne et
4
3 0 5 ∞ 6 4 de sa colonne, soit 0+1.
0 4
4 0 1 0 ∞ 1
1
5 0 4 4 1 ∞

Dans la matrice précédente, identifions l’élément ayant le plus grand super indice c’est-à-dire
l’élément ayant le plus grand exposant4. Il s’agit de l’élément se trouvant sur la 3ème ligne et
la 1ère colonne (3,1). Cela signifie que nous avons intérêt à employer l’arc (3,1) qui, a priori, est
à recommander, étant donné le coût le plus petit sur sa ligne.

Crs = C31 r = 3, s = 1

3
Constance de réduction car la résolution commence en réduisant, comme pour les
problèmes d’affectation, la matrice de coût donnée.
4 Si une matrice a 2 éléments ayant le même super indice, considérez le premier.

44
Etape 4 : Inclusion de (3,1), Il s’agit de calculer le coût d’éviction associé au fait d’emprunter
(3,1).
Si nous éliminons la ligne et la colonne du plus grand super indice (pour l’empêcher d’effectuer
le chemin retour sur le même chemin) nous aurons :
Q : ∪ {𝑟} = {3}
Cet élément correspondait à 4
2 3 4 5
dans la matrice précédente, il
C̄1= 1 0 ∞ 4 0 devient ∞ puisque se trouvant
2 ∞ 4 0 3 au croisement de 3 et 1.
4 1 0 ∞ 1
5 4 4 1 ∞

A ce niveau, refaire les étapes 1 et 2.

Nous aurons ce résultat :

2 3 4 5
C̄ = 1 0 ∞ 4 0
2 ∞ 4 0 3
4 1 0 ∞ 1
5 3 3 0 ∞

Constance de réduction r₁ = 1 (somme de tous les minimaux, ligne et colonne. Donc

0+0+0+1+0+0+0+0).
Ȓ = R+r₁ = 15+1 = 16

Etape 5 : Exclusion de (3,1) dans le parcours. Calculer le coût d’éviction associé au fait de
ne pas emprunter (3,1). Nous reproduisons la matrice juste avant l’inclusion de (3,1) et de
cette matrice, nous plaçons ∞ sur l’emplacement ayant le plus grand super indice5. Et puis
refaire les étapes 1 et 2 c’est-à-dire trouver le minimum de chaque ligne puis soustraire la
ligne par son minimum, de même pour la colonne.

1 2 3 4 5 1 2 3 4 5
1 ∞ 0 4 4 0 0 1 ∞ 0 4 4 0
2 0 ∞ 4 0 3 0 2 0 ∞ 4 0 3
3 ∞ 5 ∞ 6 4 4 3 ∞ 1 ∞ 2 0
4 0 1 0 ∞ 1 0 4 0 1 0 ∞ 1
5 0 4 4 1 ∞ 0 5 0 4 4 1 ∞

5
Nous plaçons infini sur le super indice puisque cela nous indique que si l’on ne prend
pas ce chemin dans le parcours, cela nous coutera cher.

45
 1 2 3 4 5
1 ∞ 0 4 4 0 1 2 3 4 5
2 0 ∞ 4 0 3 1 ∞ 0 4 4 0
3 ∞ 1 ∞ 2 0 2 0 ∞ 4 0 3
4 0 1 0 ∞ 1 3 ∞ 1 ∞ 2 0
5 0 4 4 1 ∞ 4 0 1 0 ∞ 1
0 0 0 0 0 5 0 4 4 1 ∞

Constance de réduction r₂ = 4 (somme de tous les minimaux, ligne et colonne. Donc

0+0+4+0+0+0+0+0+0).

Ȓ = R+r₂ = 15+4 = 19

Nous allons choisir l’option qui donne un R minimum. Généralement c’est l’option qui
inclut le chemin dans le parcours qui est choisie.

3.1 R=19 3.1 R=16

Etape 6 : A partir de la matrice choisie c’est-à-dire (3,1) inclus, nous faisons l’étape 3
(mettre des exposants sur les 0 et choisir celui qui a l’exposant maximum). En reprenant
la matrice de coût résultant de l’inclusion, l’algorithme peut ainsi déterminer la meilleure
solution pour les sous-problèmes6 plus grands et plus complexes, en utilisant les résultats
précédemment calculés pour les sous-problèmes plus petits. Cette méthode permet ainsi
d’optimiser la complexité de l’algorithme et obtenir une solution optimale pour le PVC en
un temps raisonnable.

2 3 4 5 0⁴ qui a l’exposant maximum se

1 0¹ ∞ 4 0¹ trouve sur la 4ème ligne et la 3ème
colonne (4,3).
C= 2 ∞ 4 0ᶟ 3
4 1 0⁴ ∞ 1
5 3 3 0ᶟ ∞

6
Avec LITTLE, pour résoudre le PVC, un sous-problème est une instance plus petite du
PVC qui résout de manière itérative à partir de la résolution du problème de base. Plus
précisément, chaque sous-ensemble du PVC correspond à un sous-problème des éléments
du PVC original et une capacité de sac à dos donnée.
46
Etape 4 : Inclusion de (4,3)
Nous éliminons la ligne et la colonne du plus grand super indice ou de l’exposant maximum
et nous faisons ensuite les étapes 2 et 3 c’est-à-dire trouver le minimum de chaque ligne
puis soustraire la ligne par son minimum, de même pour la colonne.
Nous aurons ce résultat après calcul :

2 4 5
1 0 4 0
2 ∞ 0 3
5 3 0 ∞

r₁ = 0 ; Ȓ = R+r₁ = 16+0 = 16
Etape 6 : Exclusion de (4,3)
Nous reproduisons la matrice juste avant l’inclusion de (4,3) et de cette matrice nous
plaçons ∞ sur l’emplacement ayant le plus grand super indice. Et puis refaire les étapes 1
et 2 c’est-à-dire trouver le minimum de chaque ligne puis soustraire la ligne par son
minimum, de même pour la colonne.

2 3 4 5 2 3 4 5
1 0 ∞ 4 0 0 1 0 ∞ 4 0
2 ∞ 4 0 3 0 2 ∞ 4 0 3
4 1 ∞ ∞ 1 1 4 0 ∞ ∞ 0
5 3 3 0 ∞ 0 5 3 3 0 ∞

2 3 4 5
1 0 ∞ 4 0 2 3 4 5
2 ∞ 4 0 3 1 0 ∞ 4 0
4 0 ∞ ∞ 0 2 ∞ 1 0 3
5 3 3 0 ∞ 4 0 ∞ ∞ 0
0 3 0 0 5 3 0 0 ∞

r₂ = 4 ; Ȓ = R+r₂ = 16+4 = 20
Lorsque LITTLE calcule le coût d’exclusion pour un élément de la matrice de coûts, il doit
tenir compte à la fois du coût d’inclusion de l’élément précédent et de la constance de
réduction. Pour cela, il utilise le coût d’inclusion du sous-problème précédent (qui a été
calculé lors du traitement de l’élément précédent) ; auquel il ajoute la constance de
réduction.
L’ajout de la constance de réduction au coût d’inclusion du sous-problème précédent est
effectué pour tenir compte de réduction du coût de l’inclusion. Lorsque l’on passe d’un sous-
problème à un autre, on doit prendre en compte la solution trouvée pour le sous-problème

47
précédent, car cette solution a une influence sur le coût du sous problème actuel. La
constance de réduction est ajoutée pour refléter la réduction du coût de l’inclusion, qui est
liée à la résolution trouvée pour le sous-problème7 précédent. Ainsi, en ajoutant cette
constance au coût d’inclusion du sous-problème précédent, on tient compte de cette
réduction du coût et on peut obtenir le coût optimal pour le sous-problème actuel.

3.1 R=19 3.1 R=16

4.3 4.3
R=20 R=16

Etape 6 : A partir de la matrice choisie c’est-à-dire (4,3) inclus, nous faisons l’étape 3 (mettre
des exposants sur les 0 et choisir celui qui a l’exposant maximum).

O3 qui a l’exposant maximum se

2 4 5 trouve sur la 1ème ligne et la 2ème
1 0ᶟ 4 03 colonne (1,2).
2 ∞ 03 3
5 3 03 ∞

Crs = C12
Etape 4 : Inclusion de (1,2)
Nous éliminons la ligne et la colonne de l’exposant maximum et faisons les étapes 1 et 2.

4 5

2 0 0

5 0 ∞

r₁ = 3 ; Ȓ = R+r₁ = 16+3 = 19

7
Un sous-problème est une instance plus petite du PVC qui résout de manière itérative à
partir de la résolution du problème de base. Plus précisément, chaque sous-ensemble du
PVC correspond à un sous-problème des éléments du PVC original et une capacité de sac
à dos donnée.
48
Etape 5 : Exclusion de (4,3)
Nous reproduisons la matrice juste avant l’inclusion de (1,2) et de cette matrice nous
plaçons ∞ sur l’emplacement ayant le plus grand super indice. Et puis refaire les étapes 1
et 2 c’est-à-dire trouver le minimum de chaque ligne puis soustraire la ligne par son
minimum, de même pour la colonne. Nous aurons ce résultat :

2 4 5
1 ∞ 4 0
2 ∞ 0 3
5 0 0 ∞

r₂ = 3 ; Ȓ = R+r₂ = 16+3 = 19
Etape 6 : A partir de la matrice choisie c’est-à-dire (1,2) inclus, nous faisons l’étape 3 (mettre des
exposants sur les 0 et choisir celui qui a l’exposant maximum).

4 5
2 0 0

5 0 ∞

Nous voyons que nous pouvons affecter les arcs (2,4), (2,5) et (5,4 ) sans frais supplémentaires.

3.1 R=19 3.1 R=16

4.3 4.3
R=20 R=16

1.2 R=19 1.2 R=19

Notons que l’arborescence de la solution est une structure de données qui présente le flux optimal
à travers le réseau, en indiquant les chemins qui doivent être suivis pour chaque unité de flux
entre chaque paire de source et de destinations.

49
 CHAPITRE 5 : PROBLÈME D’ORDONNANCEMENT
Le problème d’ordonnancement en R.O consiste à planifier et organiser la réalisation de
plusieurs tâches, en déterminant l’ordre dans lequel elles doivent être effectuées, ainsi que
les ressources nécessaires et le temps de réalisation. L’objectif est de minimiser le temps
total de réalisation ou le coût total, tout en respectant les contraintes liées aux ressources
disponibles et au délai à respecter.
Par exemple, dans une entreprise de construction, le problème d’ordonnancement pourrait
consister à planifier l’ordre de réalisation des différentes étapes de construction d’un
bâtiment. Chaque étape nécessite des ressources et du temps, et certaines étapes peuvent
être dépendantes les unes des autres. Le but serait de planifier l’ordre optimal des étapes
de construction pour minimiser le temps total de construction.

5.1 La méthode PERT

La méthode PERT (Program Evaluation and Review Technique) est une technique de
gestion de projet utilisée pour planifier, organiser et contrôler les projets. Elle est
largement utilisée en recherche opérationnelle pour modéliser et optimiser les projets
complexes.
Exemple :
Projet : renouvellement d’un appartement

Description tâche Numéro de la Durée de la Tâche Tâche

tâche tâche précédente suivante
Vider l'appartement A 3 - C,D,E

Acheter des papiers B 2 - F,G

peints
Enlever les rideaux C 1 A F,G

Mélanger la peinture D 6 A H

Disposer le tapis E 9 A I

Laver les rideaux F 4 B,C H

Tapisser l'appartement G 3 B,C I

Peindre le plafond H 2 D,F I

Nettoyer l'appartement I 8 E,H,G -

Construction du graphe PERT

1ère étape : Commencer à insérer les tâches qui n’ont pas de précédent.
NB : Dans notre exemple, il n’y a que 2 tâches qui n’ont pas de précédent, il s’agit de A et
B.

50
 n2
A (3)

Durée de
la tâche
n1

B (2)

n3

N1 est le nœud source et la construction du graphe prendra fin au nœud terminal nn.
2ème étape : Analyser les tâches suivantes des tâches initiales (A et B dans notre exemple).
Quelles sont les activités suivantes de A ? Il s’agit bien de C,D et E dans notre exercice.
Nous les écrivons provisoirement juste après A. Nous aurons :

C (1)

D (6)
n2
A (3)
E (9)

n1

B (2)

n3

Continuons tout en suivant l’ordre des activités suivantes de la tâche A. Commençons

donc par la tâche C. La tâche C à quelle activité suivante en commun avec une autre
tâche ? En observant notre tableau de départ, nous remarquons que la tâche C a les
mêmes suivants avec la tâche B et ces suivants sont F et G. Nous relions donc C avec B

51
étant donné qu’elles ont deux éléments suivants en commun (F et G) et après leur liaison,
nous sortirons immédiatement ces deux éléments communs. Nous aurons :

D (6)

n2
A (3) E (9)

n1 C (1)

F (4)
B (2)

n3
G (3)

NB : Même si C et B avaient un seul élément en commun, il faut toujours les reliez et

sortir cet élément en commun.
Nous analysons avec la même logique les éléments suivants restants de la tâche A. La
tâche D sera reliée avec F et immédiatement leur élément en commun qui est H va sortir.
La tâche E sera reliée avec les tâches G et H et immédiatement leur élément commun
qui est la tâche I va donc sortir. Nous aurons :

n2 E (9)
A (3) D (6)

H (2) I (8)
n1 C (1) n4 n5 n6

F (4)
B (2)

G (3)
n3

52
Nous venons d’achever la construction du graphe. Essayons à présent de déterminer le
chemin critique :
A gauche sera placé la date au plus tôt de la tâche,
celle-ci indique le début le plus précoce d’une
activité. A droite sera placé la date au plus tard de
| tâche, elle indique la fin la plus tardive d’une
activité.
n2 E (9)
A (3) D (6)
| | | |

H (2) I (8)
n1 C (1) n4 n5 n6

F (4)
B (2)

G (3)
n3

Déterminons les dates au plus tôt (sens aller). Considérons 2 scenarios.

1er scenario : le nœud ne reçoit qu’un seul arc (ou flèche pour faciliter la compréhension).

3| Le nœud n2 ne
O+3 = 3 reçoit qu’un seul
arc ou flèche.
n2
A (3)
0|

n1

O dans le nœud initial puisque la date au plus tôt des tâches initiales est toujours égale
à 0 étant donné que les activités initiales représentent les premières étapes du projet
qui ne dépendront d’aucune autre activité pour démarrer. Par conséquent, leur date au

53
plus tôt est fixée à O, car elles peuvent être entamées dès le début du projet, sans aucun
délai d’attente.
2ème scenario : le nœud reçoit 2 arcs ou plus. Considérer l’arc qui donne la valeur la plus
élevée.

3+1 = 4

3|

n2
A (3)
0|
Etant donné que le
n1 C (1) nœud n3 reçoit 2 arcs,
nous considérons celui
B (2) qui donne la valeur la
plus élevée (entre 2 et 4
O+2 = 2 la valeur la plus élevée
n3 est 4). C’est pourquoi
nous avons placé 4 à la
date au plus tôt de n3.
4|

Si vous appliquez ce principe dans tout le graphe, dans le sens aller bien-sûr, vous
aurez ces dates au plus tôt :

3|
O
n2 E (9)
A (3) D (6)
0| 9| 12| 20|20

H (2) I (8)
n1 C (1) n4 n5 n6

F (4)
B (2)

G (3)
n3

4| 54
NB : La date au plus tôt du nœud terminal n6 sera recopiée à la date au plus tard du
même nœud pour garantir que le projet se termine à la date la plus tôt possible sans
retard et que la durée totale du projet est correctement calculée.
Déterminons les dates au plus tard (sens retour). Considérons toujours 2 scénarios.
1er scénario : Il y a qu’un seul arc qui part du nœud.

Il y a qu’un seul arc qui

part du nœud n5, nous
faisons simplement 20- 20-8 = 12
8 ce qui donne 12. D’où
la présence d’un 12 à la
date au plus tard du
nœud n5. 12|12 20|20

I (8)
n5 n6

2ème scénario : Il y a un ou plusieurs arcs qui partent du nœud. Considérer l’arc qui
donne la valeur la plus petite.

10-4 = 6

Deux arcs partent du nœud 9|10 12|12

n3. Nous considérons celui
H (2)
qui donne la valeur la plus n4 n5
petite.
F (4) 12-3 = 9

G (3)
n3

4|6

En continuant avec cette logique, nous aurons ce résultat final avec le chemin critique
déterminé (le chemin critique comprend les activités les plus importantes et si l’une
d’entre elles est retardée, cela retardera tout le projet, en identifiant donc le chemin
critique on sait quelles activités sont les plus importantes et nécessitent une attention
particulière pour éviter les retards, pour identifier une tâche critique, il faudrait voir si
ses dates au plus tôt et au plus tard sont égales).

55
 3|3
O
n2 E (9)
A (3) D (6)
0|0 9|10 12|12 20|20

H (2) I (8)
n1 C (1) n4 n5 n6

F (4)
B (2)

G (3)
n3

4|6

56
 BIBLIOGRAPHIE

FAUVRE R., Précis de recherche opérationnelle, Méthodes et exercices d’application, Paris,

DUNOD, 1974

KAMIANTAKO MIYAMUENI A., Cours de RO, FASEG, Université de Kinshasa, 2013

KAMIANTAKO MIYAMUENI A. et KAMAVUAKO DIWAVOVA J.S., Travaux pratiques de

recherche opérationnelle, Mbanza-Ngungu, FASEG, Université Kongo, 2013

KUTANGILA MAYOYA S.D., Cours de RO, FASE, Université Protestante au Congo, 2021

TOMBOLA M. Cédric, Recherche Opérationnelle, Kinshasa, LAREQ, 2011

57