Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
162
Reve nons à notre pro blème. Effec tuons les subs ti tutions indi quées plus haut.
Nous obte nons un nou veau plan de tran sport (cf tableau cidessous), véri
fiant tou
jours les équa tions (4.1), (4.2) et (4.3) et réa li sant une solu tion de base. Après avoir
posé U II 5 0 puis éta bli le sys tème de poten tiels, cal cu lons les coûts mar gi naux :
d I, 1 5 7 1 12 2 23 5 6 ; d I, 2 5 17 1 27 2 39 5 5, etc.
Ils sont tous posi tifs et l’on a donc atteint l’opti mum. Le coût de tran sport total est :
3 529 5 coût de la solu tion anté rieure – coût fourni par la subs ti tution 5 3 535 2 6.
NB : dans le tableau sui vant, pour toute rela tion (i, j) inuti li sée (c’estàdire telle
que x ij 5 02 , on a donné la valeur numé rique du d ij asso cié : il figure en haut de la
case ij, pré cédé de son signe, qui ici est le signe 1, car l’opti mum est atteint.
L’opti mum est unique du fait que tous les coûts mar gi naux sont, ici, stric te ment
posi tifs. Si cer tains étaient nuls, on ferait appa raître d’autres solu tions équi va lentes
(grâce à des subs ti tutions de gain nul). En clair : x I,3 5 18 ; x II,1 5 9 ; x II,2 5 11 ;
x II,3 5 10 ; x II,6 5 2 ; x III,4 5 6 ; x III,5 5 5 ; x III,6 5 3 ; x IV,5 5 9 pour un coût mini mal
de 3 529 uni tés moné taires.
Remarque
(1)
1 La for mu la tion de ce pro gramme de tran sport en tant que pro -
gramme linéaire amène à intro duire N 5 m 3 n 5 24 variables puis à écrire
M 5 m 1 n 5 10 contraintes (certes liées par une rela tion de dépen dance ;
on peut sup pri mer l’une d’entre elle, ce qui amène à Mr 5 m 1 n 2 1 5 9
contraintes) ; ces contraintes étant en éga lité, on doit intro duire une variable
arti fi cielle dans cha
cune d’elles pour obte nir une base (arti
fi cielle) ini tiale ; la
réso lu tion de la « pre mière phase » par l’algo rithme du sim plexe condui rait
(après un mini mum de m 1 n 2 1 itérations) à une base réa li sable. L’avan -
tage de la méthode du stepping- stone, que nous venons de décrire, est d’évi ter
toutes les ité ra tions de cette « pre mière phase », puisqu’on part d’une base réa -
li sable ; de plus, si l’on uti lise la méthode de Balas- Hammer, la base réa li sable
ini tiale, on le sait, sera « bonne », c’est- à-dire que l’on évi tera de nom breuses
ité ra tions lors de la « seconde phase » pour atteindre l’optimum.
1. La compréhension de cette remarque sup pose la connais sance du cha pitre 8 du présent livre.
23
39
78
12
41
42
71
43
91
67
40
49
67
56
92
24
53
54
23
39
78
28
65
42
12
27
61
49
83
35
U i
17
0
12
5
10
9
2
18
6
1
11
I
II
III
IV
1
2
3
4
5
6
i
j
V j
3
9
6
32 29
49
14 56
8
5
2
5
59
54
10
16 24
I
II
III
IV
1
2
3
4
5
6
17
23
39
78
12
41
42
0
-12
1
U i
i
j V j
(1)
162
Reve nons à notre pro blème. Effec tuons les subs ti tutions indi quées plus haut.
Nous obte nons un nou veau plan de tran sport (cf tableau cidessous), véri
fiant tou
jours les équa tions (4.1), (4.2) et (4.3) et réa li sant une solu tion de base. Après avoir
posé U II 5 0 puis éta bli le sys tème de poten tiels, cal cu lons les coûts mar gi naux :
d I, 1 5 7 1 12 2 23 5 6 ; d I, 2 5 17 1 27 2 39 5 5, etc.
Ils sont tous posi tifs et l’on a donc atteint l’opti mum. Le coût de tran sport total est :
3 529 5 coût de la solu tion anté rieure – coût fourni par la subs ti tution 5 3 535 2 6.
NB : dans le tableau sui vant, pour toute rela tion (i, j) inuti li sée (c’estàdire telle
que x ij 5 02 , on a donné la valeur numé rique du d ij asso cié : il figure en haut de la
case ij, pré cédé de son signe, qui ici est le signe 1, car l’opti mum est atteint.
L’opti mum est unique du fait que tous les coûts mar gi naux sont, ici, stric te ment
posi tifs. Si cer tains étaient nuls, on ferait appa raître d’autres solu tions équi va lentes
(grâce à des subs ti tutions de gain nul). En clair : x I,3 5 18 ; x II,1 5 9 ; x II,2 5 11 ;
x II,3 5 10 ; x II,6 5 2 ; x III,4 5 6 ; x III,5 5 5 ; x III,6 5 3 ; x IV,5 5 9 pour un coût mini mal
de 3 529 uni tés moné taires.
Remarque
(1)
1 La for mu la tion de ce pro gramme de tran sport en tant que pro -
gramme linéaire amène à intro duire N 5 m 3 n 5 24 variables puis à écrire
M 5 m 1 n 5 10 contraintes (certes liées par une rela tion de dépen dance ;
on peut sup pri mer l’une d’entre elle, ce qui amène à Mr 5 m 1 n 2 1 5 9
contraintes) ; ces contraintes étant en éga lité, on doit intro duire une variable
arti fi cielle dans cha
cune d’elles pour obte nir une base (arti
fi cielle) ini tiale ; la
réso lu tion de la « pre mière phase » par l’algo rithme du sim plexe condui rait
(après un mini mum de m 1 n 2 1 itérations) à une base réa li sable. L’avan -
tage de la méthode du stepping- stone, que nous venons de décrire, est d’évi ter
toutes les ité ra tions de cette « pre mière phase », puisqu’on part d’une base réa -
li sable ; de plus, si l’on uti lise la méthode de Balas- Hammer, la base réa li sable
ini tiale, on le sait, sera « bonne », c’est- à-dire que l’on évi tera de nom breuses
ité ra tions lors de la « seconde phase » pour atteindre l’optimum.
1. La compréhension de cette remarque sup pose la connais sance du cha pitre 8 du présent livre.
23
39
78
12
41
42
71
43
91
67
40
49
67
56
92
24
53
54
23
39
78
28
65
42
12
27
61
49
83
35
U i
17
0
12
5
10
9
2
18
6
1
11
I
II
III
IV
1
2
3
4
5
6
i
j
V j
3
9
6
32 29
49
14 56
8
5
2
5
59
54
10
16 24
I
II
III
IV
1
2
3
4
5
6
17
23
39
78
12
41
42
0
-12
1
U i
i
j V j
(1)