Université Protestante au Congo

Faculté d’Administration des Affaires et Sciences Économiques

RÉSUMÉ DE RECHERCHE
OPÉRATIONNELLE
EBENGO BONSONGI Alain

Licence 1 FASE
Octobre 2022
 TABLE DES MATIERES

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

1.1 Algorithme primal de simplexe sans matrice identité explicite ..................... 1
1.2 Algorithme dual de simplexe ..................................................................... 8
CHAPITRE 2 : PROBLEME DE TRANSPORT .................................................11
2.1 La règle du Coin Nord-Ouest ....................................................................11
2.2 Méthode du minimum de la ligne ..............................................................14
2.3 Méthode du minimum de la colonne .........................................................16
2.4 Méthode du minimum de la matrice ..........................................................18
2.5 Méthode de la double préférence .............................................................21
2.6 Méthode d’Approximation de VOGEL .........................................................23
2.7 Méthode de fréquence .............................................................................26
2.8 Méthode d’affectation ..............................................................................28
2.9 Méthode de tremplin................................................................................32
CHAPITRE 3 : THEORIE DE GRAPHES ........................................................36
3.1 La détermination des composants fortement connexes d’un graphe ............36
CHAPITRE 4 : PROBLEME DU VOYAGEUR DE COMMERCE .......................... 40
BIBLIOGRAPHIE ................................................................................................ 46
 1

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ées 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).
 2

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 y₁ 2 3 4 7 0 4600 Ressources
contraintes y₂ 3 4 5 6 0 5000 respectives
de type ≤. z₁ 1 1 1 1 0 950 de chaque
z₂ 0 0 0 1 -1 450 variable de
FOA -1 -1 -1 -2 1 base.
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₁.

Identifions la colonne pivot et la ligne pivot :

 3

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 7 qui nous donne 657,14 et pour les autres éléments nous
5000 950 450
aurons : = 833,33, = 950 et = 450. Le plus petit de tous ces rapports correspondra à la ligne
6 1 1
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. Donc 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

Transformation de la colonne pivot :

 4

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 : Élé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.

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 :
 5

é𝑙é𝑚𝑒𝑛𝑡 𝑝𝑖𝑣𝑜𝑡 × é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
) = 1 (donc 3 qui est un élément se trouvant en haut de la ligne pivot dans le tableau précédent,

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 :

Élément se trouvant en haut de la ligne pivot :

1×2
4-( ) =2
1

1×2
7-( ) =5
1

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

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

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

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

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

= -1+1 ce qui donne 0.

 6

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

NB : 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.

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
).
 7

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-( 1 ) = 50
450(0)
450-( ) = 450
1
Elément se trouvant en bas de la ligne pivot :
2(1)
2-( ) = 2-2
1
=0
5(1)
3-( 1 ) = 3-5
= -2
2(1)
1-( 1 ) = -1
5(1)
1-( ) = 1-5
1
= -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
 8

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.
Résolution :
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-
objectif (FO), provenant de S’il existe au moins une
P : min 𝜋 = 2x1+3x2. ressource < 0, la
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
 9

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 : Élé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-( −2 ) = 0

−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-2 ce qui donne -4.

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
 10

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.

 11

CHAPITRE 2 : PROBLÈME DE TRANSPORT

2.1 La règle du Coin Nord-Ouest

2 5 7 Les problèmes de transport se posent

3 6 1 comme suit :
C=( )
9 6 4 Il faut minimiser le coût de transport d'un
50 50 50 certain bien dans m usines P1, P2, ..., Pm
situées en des endroits différents; les
Z = (zi) = (10;4;6;5) quantités de ce bien disponible dans chaque
usine sont respectivement O1, O2, ..., Om
W = (wj) = (5;12;8)
(offres).
Où :

C = Matrice de coût
Z = La quantité offerte
W = La demande

Résolution :
5 12 8
10
4
( )
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
 12

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 tout ce que
0 nous avons. L’offre devient donc 0 et la
5 12 8 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
 13

Etape 5 : Nous avons 4 et la demande est de 7,

la demande est donc supérieure à
l’offre, nous donnons tout, c’est-à-dire
0 7 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 é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.
 14

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
= 10+25+0+0+24+0+0+18+12+0+0+250
= 399 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 399FC. Il est possible de transporter ces
marchandises vers la demande à un coût inférieur à 399FC, 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 ligne, et nous allons effectuer
( ) C=( )
6 9 6 4 des calculs au niveau de la
5 50 50 50 matrice de transport comme
nous l’avions fait avec la
Nous aurons ce résultat : méthode du Coin Nord-Ouest.
0
5 12 8
5 10 5
4
( )
6
5
Emplacement de 5
Etape 2 : Le minimum est 5. suivant la matrice
5 est le 2ème élément
de coût.
5 12 8 minimal sur cette
ligne.
5 10 2 5 7
4 3 6 1
( ) C=( )
6 9 6 4
5 50 50 50
 15

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 1 est le premier
la matrice de coût.
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 transport, celui du milieu donne un nombre
supérieur aux autres (entre 5 et 5, le minimum est 5).
 16

Nous aurons ce résultat :

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

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 colonne et nous allons
( ) C= ( )
6 9 6 4 effectuer les calculs au niveau
5 50 50 50 de la matrice de coût.
Nous aurons ce résultat :

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
minimal de la 1ère
5 12 8
colonne.
5 10 5 2 5 7
4 3 6 1
( ) C =( )
6 9 6 4
5 50 50 50
 17

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 : 5 est le 1er élément
de 5 suivant la
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
 18

Etape 5 :
Emplacement de 6
Le minimum suivant la matrice
est 6. 0 7 A la 2ème colonne il y a 2 éléments
de coût.
5 12 8 minimaux identiques c’est-à-dire 6 et 6.
0 5 10 5 2 5 7 Vous remarquerez que nous avons
5
4 0 3 6 1 choisi le second comme 2ème élément
( ) C=( ) minimal, puisqu’il permet le plus grand
6 0 9 6 4
5 0 50 50 50 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 1
C. Entre 8 et suivant la matrice de
4 le min est coût. A. 1 est le premier
4.
5 12 8 élément minimal de toute
10 2 5 7 la matrice.
4 3 6 1
( ) C= ( )
6 9 6 4
5 50 50 50
 19

Nous aurons ce résultat :

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

Etape 2 : Emplacement de 2
suivant la matrice
Le minimum de coût. 2 est le 2ème élément minimal
est 5. 4 de toute la matrice.
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 minimum suivant la matrice
est O. 0 4 de coût. 3 est le 3ème élément minimal
5 12 8 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
 20

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 minimum 0 suivant la matrice de élément minimal de la matrice et
est 2. 0 7 4
coût. nous remarquons qu’il y a 2
5 12 8
éléments minimaux identiques
0 5 10 5 5 2 5 7 c’est-à-dire 6 et 6. Nous
0 4 0 4) 3 6 1 choisissons le second puisqu’il
( C= ( )
2 6 4 9 6 4
offre le plus grand transport. Cela
5 50 50 50
veut dire qu’au niveau de la
Nous aurons ce résultat : matrice de transport il permet
d’avoir un nombre supérieur par
5 0
rapport à l’autre.
0 7 4
5 12 8
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 trouver en faisant
5×2+5×5+0×7+0×3+0×6+4×1+0×9+2×6+4×4+0×50+5×50+0×50.
 21

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 minimum suivant la matrice de coût.
est 5. A. 2 est le 1er élément minimal à la
5 12 8 fois sur sa ligne et sa colonne. Nous
10 2 5 7 choisissons selon l’ordre décroissant
4 3 6 1 (du plus grand au plus petit) avec
( ) C= ( )
6 9 6 4 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
Le min de coût. 1 est le 2ème élément à la
5 12 8
est 4. fois minimal sur sa ligne et
5 10 5 2 5 7 sa colonne.
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 4)
(
6
5
 22

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 suivant
la matrice de coût. 4 est le premier élément choisi dans
Le 0 4
5 12 8 la catégorie de ceux qui sont
minimum
minimaux soit sur leur ligne, soit sur
est 4. 5 10 5 2 5 7 leur colonne. Nous les choisissons
0 4 4) 3 6 1
( C= ( ) suivant un ordre croissant (plus petit
6 9 6 4 au plus grand).
5 50 50 50

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 :
 23

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. T rouver en faisant
5×2+5×5+0×7+0×3+0×6+4×1+0×9+2×6+4×4+0×50+5×50+0×50.
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
 24

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

2ème colonne 5-6 = -1, en valeur absolue nous donne 1.
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 minimum 2 suivant la
est 5. 5 12 8 matrice de coût. 2 est le coût le plus
faible sur la ligne de 3.
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.

Le plus grand 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.
 25

Emplacement de 1
suivant la matrice
Le
de coût. 1 est le coût le plus
minimum 0 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 permettant le plus grand transport, c’est bien le second, dont le coût le plus
faible est 4. Nous avons choisi le plus grand transport à partir de l’élément minimal sur la ligne
de chacune.
Emplacement de 4
suivant la matrice 4 est le coût le plus
Le minimum de coût. faible sur la ligne de 2.
est 4. 0 4
5 12 8
5 10 5
5 7 2
0 4 4)
( C=(6 4 )2
6
50 50 0
5
1 3
 26

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. Trouver en faisant
5×2+5×5+0×7+0×3+0×6+4×1+0×9+2×6+4×4+0×50+5×50+0×50.

2.7 Méthode de fréquence

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

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 vient de .
3 𝑛

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 + 6 + 1) = (10)
3 3
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 :
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.
 28

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
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
 29

2.8 Problème d’affectation

𝟐 𝟑 𝟓 𝟖
𝟏 𝟕 𝟗 𝟔
( )
𝟗 𝟔 𝟖 𝟔
𝟐 𝟒 𝟕 𝟒
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 :

𝟎 𝟏 𝟑 𝟔
𝟎 𝟔 𝟖 𝟓
( )
𝟑 𝟎 𝟐 𝟎
𝟎 𝟐 𝟓 𝟐
Faisons l’opération avec les colonnes.

𝟎 𝟏 𝟑 𝟔
𝟎 𝟔 𝟖 𝟓
( )
𝟑 𝟎 𝟐 𝟎
𝟎 𝟐 𝟓 𝟐
0 0 2 0
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 :
𝟎 𝟏 𝟏 𝟔 𝟏
𝟎 𝟔 𝟔 𝟓 𝟏
( )
𝟑 𝟎 𝟎 𝟎 𝟑
𝟎 𝟐 𝟑 𝟐 𝟏
 30

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.
𝟎 𝟏 𝟏 𝟔 𝟏
𝟎 𝟔 𝟔 𝟓 𝟏
( )
𝟑 𝟎 𝟎 𝟎 𝟑
𝟎 𝟐 𝟑 𝟐 𝟏

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.

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

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 additionner cet élément (ici
c’est 1) à toute case traversée par 2 traits. La case traversée par 2 traits est 3.
𝟎 𝟎 𝟎 𝟓
𝟎 𝟓 𝟓 𝟒
( )
𝟒 𝟎 𝟎 𝟎
𝟎 𝟏 𝟐 𝟏

Refaire l’étape 2.
𝟎 𝟎 𝟎 𝟓 𝟑
𝟎 𝟓 𝟓 𝟒 𝟏
( )
𝟒 𝟎 𝟎 𝟎 𝟑
𝟎 𝟏 𝟐 𝟏 𝟏

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

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
 32

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.
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 la
matrice de coût, 1 qui correspond au coût
5 5 0 2 5 7
0 4 0 3 6 1 le plus faible n’a pas été transporté dans la
X=( ) C =( ) matrice de transport.
0 3 3 9 6 4
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.
 33

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 et
Calculons les éléments égaux à zéro dans la matrice X, donc les éléments restants.
l’étiqueter du signe « - », ce qui donnera 4-, sur la colonne de 4-, voir un
élément différent de 0 et l’étiqueter du signe « + », ce qui donnera 3+, sur
Pour Ĉ13 on a : u₁+v₃-c₁₃
la ligne de 3+, voir un élément différent de 0 et l’étiqueter du signe « - », ce
= 2+1-7 (7 est la valeur de c₁₃ partant de la matrice de coût)
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
 34

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 partons de la matrice X(1) et nous u₂ = 6-3
additionnons ou soustrayons le plus grand positif de la matrice C* (qui est 3), u₂ = 3
selon qu’il s’agit des signes, avec tous les éléments étiquetés. En termes simples,
pour 4-, étant donné qu’il a le signe « - », nous aurons 4-3 (3 étant le plus grand Pour C23 on a : u2+v₃ = c23
positif), ce qui nous donnera 1. Pour 0+, étant donné qu’il a le signe « + », nous 3+v₃ = 1
aurons 0+3 (3 étant le plus grand positif), ce qui nous donnera 3. Appliquez la v₃ = 1-3
même logique avec 3+ et 3- .
v₃ = -2

Nous aurons le résultat suivant :

Pour C32 on a : u3+v2 = c32
u3+3 = 6
5 5 0
0 1 3 u3 = 6-3
X(2) =( ) u3 = 3
0 6 0
0 0 5
Pour C43 on a : u4+v₃ = c43
Construisons la matrice C* de la matrice X(2) pour voir si la solution est optimale. u4-2 = 50
Au cas où la solution ne sera pas optimale, nous allons de nouveau étiqueter la u4 = 50+2
matrice X(2) et poursuivre les calculs. u4 = 52

Pour construire la matrice C* de la matrice X(2), nous faisons comme au début, Calculons les éléments égaux à zéro dans la matrice X(2), donc les éléments
c’est-à-dire nous partons de la matrice X(2), nous identifions les éléments restants.
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
X(2) =( )
𝐶₃₁ 𝐶₃₂ 𝐶₃₃ Pour c3̃ 3 on a : u3+v₃-c33
𝐶₄₁ 𝐶₄₂ 𝐶₄₃ = 3-2-4
= -3
Etape 1 : Test d’optimalité de la solution courante Pour c4̃ 2 on a : u₄+v2-c42
= 52+3-50
Posons V₁ = 0
=5
Et calculons premièrement les éléments supérieurs à zéro dans la matrice X(2). Pour c3̃ 1 on a : u₃+v₁-c₃₁
= 3+0-9
Pour C₁₁ on a : u₁+v₁ = C₁₁ = -6
u₁+0 = 2 (2 est la valeur de C₁₁ partant de la matrice de coût) Pour c2̃ 1 on a : u2+v₁-c21
u₁ = 2 = 3+0-3
=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
 35

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+. Sur la matrice X(2), voir sur la ligne de 0+ un
élément différent de 0 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 poursuivez 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
 36

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, n4. Cela veut dire que nous pouvons faire un contour à
partir de ces 3 sommets.

n2

n1 n5
n4

n3
 37

𝑛₁ 𝑛₂ 𝑛₃ 𝑛₄ 𝑛₅ 4 arcs partent de n1, 1 arc vers n2, 1 arc vers

n3, 1 arc vers n4 et 1 arc vers n5.
𝑛₁ 0 1 1 1 1
𝑛₂ 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.
 38

Nous aurons donc :

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

1 1 1 1 1 matrice, aucun correspondant à 0 n’a d’élément
0 1 1 0 1
encerclé sur sa ligne correspondant à 1 et sur sa
A(O) = 0 0 1 1 1
colonne correspondant à 1. Il n’y aura donc pas
0 1 0 1 1
de changement, la matrice suivante aura les
(0 0 0 0 1)
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 sa
0 1 0 1 1 colonne correspondant à 1. Donc dans la matrice
(0 0 0 0 1) 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 :

 39
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 0 1 1 1 1 1

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

1 1 1 1 0 0
A (G') = (0
*
1 1) - (0 1 0)
Pour avoir ce résultat, on a retranché les
0 0 1 0 0 1
éléments de la diagonale principale de la matrice
à (G') avec les éléments de la diagonale principale de
0 1 1 la matrice unité et avons repris les éléments hors
A* (G') = (0 0 1)
diagonale principale de la matrice à (G').
0 0 0
 40

CHAPITRE 4 : PROBLÈME DU VOYAGEUR DE COMMERCE

Considérons le graphe suivant pour tenter de comprendre le problème du voyageur de
commerce :

A partir d’un dépôt (le point en orange), quelle est la route à suivre pour visiter un ensemble de
clients (les points en vert désignent les clients). Le problème revient à chercher la route qui part
du dépôt, visite tous les clients et revient ensuite au dépôt et cette route doit être optimale c’est-
à-dire son coût doit être le plus minimal possible. Notons que chaque client doit être visité une
seule fois, pas deux fois.
Exemple : Soit la matrice de coût suivante décrivant complètement le graphe correspondant 𝒩.
1 2 3 4 5
1 ∞ 3 9 8 2
C̄ = 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
1 ∞ 3 9 8 2 2
C̄ = 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.

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
 41

1 2 3 4 5
1 ∞ 0 4 4 0
2 0 ∞ 4 0 3
C= 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 de 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
1 ∞ 01 4 4 01 sur sa ligne, il est marqué de
C= 2 00 ∞ 4 01 3 l’exposant 1, puisque 1 constitue la
3 04 5 ∞ 6 4 somme du minimum de sa ligne et de
4 00 1 04 ∞ 1 sa colonne, soit 0+1.
5 01 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
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 dans
2 3 4 5
1 0 ∞ 4 0
la matrice précédente, il devient ∞
C̄1= puisque se trouvant au croisement
2 ∞ 4 0 3
4 1 0 ∞ 1
de 3 et 1.
5 4 4 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.
 42

A ce niveau, refaire les étapes 1 et 2 c’est-à-dire choisir en premier lieu le minimum de

chaque ligne et le soustraire de toute sa ligne et en second lieu, choisir le minimum de
chaque colonne et le soustraire de toute sa colonne. Et calculer pour finir, la constante de
réduction.
Nous aurons ce résultat :
2 3 4 5
1 0 ∞ 4 0
C̄ =
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. Donc 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 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.

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 ∞

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

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
 43

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).

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

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

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
2 3 4 5
1 0 ∞ 4 0
1 0 ∞ 4 0
2 ∞ 4 0 3
∞ 2 ∞ 1 0 3
4 0 ∞ 0
4 0 ∞ ∞ 0
5 3 3 0 ∞
5 3 0 0 ∞
0 3 0 0
 44

r₂ = 4 ; Ȓ = R+r₂ = 16+4 = 20

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).

0ᶟ qui a l’exposant maximum

2 4 5 se trouve sur la 1ère ligne et la
1 0ᶟ 4 03 2ème 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
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
 45

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

 46

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