Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
152
blème éco no mique. Décrivons- la néan moins pour intro duire les élé ments théo riques
de la ques tion.
Il s’agit de la pro cé dure dite du coin Nord- Ouest, consis tant à tran spor ter d’abord
sur la rela tion (I, 1) (qui est le coin Nord- Ouest du tableau) la quan tité maximale
pos sible, c’est- à-dire le mini mum du couple (demande, dis po ni bi lité), soit ici min(9,
18) 5 9 ; puis, le dépôt 1 étant servi et l’usine I étant encore appro vi sion née de 9
uni tés, à tran spor ter sur la rela tion (I, 2), min(11, 9) 5 9. Cette fois, c’est l’usine I
dont le stock est épuisé, mais il manque 2 uni tés au dépôt 2, qu’on ache mi nera sur la
rela tion (II, 2) et ainsi de suite… On aboutit au tableau ci-dessous :
On constate que, dans le cas
géné ral, cette pro cé dure se tra -
duit, à chaque choix d’une rela -
tion, par l’éli mi na tion d’une
des ti nation ou bien d’une ori -
gine et, par fois, des deux (sauf
tou te fois lors de la der nière
affec tion : au coin Sud- Est,
pour laquelle on achève de ser -
vir le der nier dépôt en épui sant
le stock de la der nière usine).
Elle donne une solu tion sans
cycle, qui est ici une solu tion
de base.
En effet, elle a conduit ici à sélec tion ner en tout m 1 n 2 1 rela tions uti li sées pour
les tran sports, alors qu’on ne tran sporte rien sur les autres, ce qui cor res pond bien à la
condi tion selon laquelle il faut exac te ment n # m 2 1 n 1 m 2 12 5 1 n 2 12 1 m 2 12
variables nulles dans la solu tion.
Dans l’exemple ci- dessus, m 5 4, n 5 6 ; on doit avoir 3 3 5 5 15 « zéros »
(c’est- à-dire x ij nuls) dans la solu tion : on le vérifie aisément.
La figure 4.42 montre que le graphe du tran
sport effec
tif est bien un arbre puisque
nous avons un graphe sans cycle (ou encore connexe) de N 5 n 1 m som mets et
N 2 1 5 n 1 m 2 1 arêtes (rap
pe lons que, par défi ni tion, un arbre est connexe et
sans cycle). Ses 9 arêtes représentent les 9 liaisons (i, j) telles que : x ij > 0.
Bien entendu, le tableau ci-dessus donnant les quantités transportées x ij vérifie les
équa tions (4.1), (4.2) et (4.3) :
1.
a
4
i 51
a i 5 18 1 32 1 14 1 9 5 73 ;
a
6
j51
b j 5 9 1 11 1 28 1 6 1 14 1 5 5 73,
car on avait pris a
4
i 51
a i 5 a
6
j51
b j : l’offre est, ici, égale à la demande ;
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
2
3
4
5
6
I
i j
II
III
IV
9
11
28
6
14
5
4
5
4
10
9
9
2
28
2
18
32
14
a i
b j
solu tion de base obte nue par la
méthode du coin Nord- Ouest : tableau des [x ij ]
152
blème éco no mique. Décrivons- la néan moins pour intro duire les élé ments théo riques
de la ques tion.
Il s’agit de la pro cé dure dite du coin Nord- Ouest, consis tant à tran spor ter d’abord
sur la rela tion (I, 1) (qui est le coin Nord- Ouest du tableau) la quan tité maximale
pos sible, c’est- à-dire le mini mum du couple (demande, dis po ni bi lité), soit ici min(9,
18) 5 9 ; puis, le dépôt 1 étant servi et l’usine I étant encore appro vi sion née de 9
uni tés, à tran spor ter sur la rela tion (I, 2), min(11, 9) 5 9. Cette fois, c’est l’usine I
dont le stock est épuisé, mais il manque 2 uni tés au dépôt 2, qu’on ache mi nera sur la
rela tion (II, 2) et ainsi de suite… On aboutit au tableau ci-dessous :
On constate que, dans le cas
géné ral, cette pro cé dure se tra -
duit, à chaque choix d’une rela -
tion, par l’éli mi na tion d’une
des ti nation ou bien d’une ori -
gine et, par fois, des deux (sauf
tou te fois lors de la der nière
affec tion : au coin Sud- Est,
pour laquelle on achève de ser -
vir le der nier dépôt en épui sant
le stock de la der nière usine).
Elle donne une solu tion sans
cycle, qui est ici une solu tion
de base.
En effet, elle a conduit ici à sélec tion ner en tout m 1 n 2 1 rela tions uti li sées pour
les tran sports, alors qu’on ne tran sporte rien sur les autres, ce qui cor res pond bien à la
condi tion selon laquelle il faut exac te ment n # m 2 1 n 1 m 2 12 5 1 n 2 12 1 m 2 12
variables nulles dans la solu tion.
Dans l’exemple ci- dessus, m 5 4, n 5 6 ; on doit avoir 3 3 5 5 15 « zéros »
(c’est- à-dire x ij nuls) dans la solu tion : on le vérifie aisément.
La figure 4.42 montre que le graphe du tran
sport effec
tif est bien un arbre puisque
nous avons un graphe sans cycle (ou encore connexe) de N 5 n 1 m som mets et
N 2 1 5 n 1 m 2 1 arêtes (rap
pe lons que, par défi ni tion, un arbre est connexe et
sans cycle). Ses 9 arêtes représentent les 9 liaisons (i, j) telles que : x ij > 0.
Bien entendu, le tableau ci-dessus donnant les quantités transportées x ij vérifie les
équa tions (4.1), (4.2) et (4.3) :
1.
a
4
i 51
a i 5 18 1 32 1 14 1 9 5 73 ;
a
6
j51
b j 5 9 1 11 1 28 1 6 1 14 1 5 5 73,
car on avait pris a
4
i 51
a i 5 a
6
j51
b j : l’offre est, ici, égale à la demande ;
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
2
3
4
5
6
I
i j
II
III
IV
9
11
28
6
14
5
4
5
4
10
9
9
2
28
2
18
32
14
a i
b j
solu tion de base obte nue par la
méthode du coin Nord- Ouest : tableau des [x ij ]