Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
160
On peut cal cu ler la valeur de la fonc tion éco no mique pour les affec ta tions obte -
nues ; on trouve :
z 5 61 3 18 1 23 3 9 1 39 3 11 1 78 3 7 1 42 3 5 1 92 3 3 1 24 3
6 1 53 3 5 1 49 3 9 5 3 535.
Cette solu tion est donc, comme on s’y atten dait, meilleure que celle du coin
Nord- Ouest (3 700). Pour reconnaître si la solu tion de base ini tiale, obte nue par une
pro cé dure quel conque, est opti male, il faut bien entendu cal cu ler les coûts mar gi -
naux rela tifs aux rela tions inuti li sées. Il est bon d’avoir recours, à cet effet, au cal cul
des dif fé rences de poten tiel sur l’arbre repré sen ta tif de la solu tion ; c’est ce que nous
ferons en reve nant à l’exemple ci- dessus, pour le plan de transport ci-dessus.
Grâce à l’arbre de la figure 4.46, on pourra cal cu ler
tous les coûts mar gi naux par la formule :
d i,j 5 U i 1 c i,j 2 V j 5 c ij 2 (V j 2 U i )
Par exemple :
d I, 1 5 31 1 12 2 37 5 6 ;
d I, 2 5 31 1 27 2 53 5 5 ;
etc.
d II, 4 5 14 1 28 2 24 5 18 ;
etc.
Il n’est d’ailleurs pas néces -
saire de tra cer la figure ellemême ; on peut opé rer direc te -
ment sur la matrice, en ayant
soin de divi ser chaque case en
deux par ties, l’une, celle du bas,
rece vant (de façon défi ni tive)
le coût de tran sport de la rela -
tion cor res pon dante et l’autre,
celle du haut, la quan tité affec -
tée dans la solu tion courante
(chaque quan tité x ij a été cer clée
dans le tableau ci- contre).
Pour cal cu ler les poten tiels U i et V j , on choi sit alors la rela tion affec tée du coût
le plus grand [ici, (III, 3)] et l’on écrit 0 (ori gine des poten tiels) face à la ligne III, sur
la droite de la matrice, ce qui revient à poser U III 5 0 ; on a alors :
c III, 3 5 V 3 2 U III
Figure 4.46
37
53
92
24
53
56
71
43
91
67
40
42
67
56
92
24
53
54
23
39
78
28
65
42
12
27
61
49
83
35
U i
31
14
0
5
3
7
9
5
18
6
13
11
I
II
III
IV
1
2
3
4
5
6
j
i
V j
�
�
�
�
160
On peut cal cu ler la valeur de la fonc tion éco no mique pour les affec ta tions obte -
nues ; on trouve :
z 5 61 3 18 1 23 3 9 1 39 3 11 1 78 3 7 1 42 3 5 1 92 3 3 1 24 3
6 1 53 3 5 1 49 3 9 5 3 535.
Cette solu tion est donc, comme on s’y atten dait, meilleure que celle du coin
Nord- Ouest (3 700). Pour reconnaître si la solu tion de base ini tiale, obte nue par une
pro cé dure quel conque, est opti male, il faut bien entendu cal cu ler les coûts mar gi -
naux rela tifs aux rela tions inuti li sées. Il est bon d’avoir recours, à cet effet, au cal cul
des dif fé rences de poten tiel sur l’arbre repré sen ta tif de la solu tion ; c’est ce que nous
ferons en reve nant à l’exemple ci- dessus, pour le plan de transport ci-dessus.
Grâce à l’arbre de la figure 4.46, on pourra cal cu ler
tous les coûts mar gi naux par la formule :
d i,j 5 U i 1 c i,j 2 V j 5 c ij 2 (V j 2 U i )
Par exemple :
d I, 1 5 31 1 12 2 37 5 6 ;
d I, 2 5 31 1 27 2 53 5 5 ;
etc.
d II, 4 5 14 1 28 2 24 5 18 ;
etc.
Il n’est d’ailleurs pas néces -
saire de tra cer la figure ellemême ; on peut opé rer direc te -
ment sur la matrice, en ayant
soin de divi ser chaque case en
deux par ties, l’une, celle du bas,
rece vant (de façon défi ni tive)
le coût de tran sport de la rela -
tion cor res pon dante et l’autre,
celle du haut, la quan tité affec -
tée dans la solu tion courante
(chaque quan tité x ij a été cer clée
dans le tableau ci- contre).
Pour cal cu ler les poten tiels U i et V j , on choi sit alors la rela tion affec tée du coût
le plus grand [ici, (III, 3)] et l’on écrit 0 (ori gine des poten tiels) face à la ligne III, sur
la droite de la matrice, ce qui revient à poser U III 5 0 ; on a alors :
c III, 3 5 V 3 2 U III
Figure 4.46
37
53
92
24
53
56
71
43
91
67
40
42
67
56
92
24
53
54
23
39
78
28
65
42
12
27
61
49
83
35
U i
31
14
0
5
3
7
9
5
18
6
13
11
I
II
III
IV
1
2
3
4
5
6
j
i
V j
�
�
�
�