4.9 Les pro grammes de tran sport
159
© Dunod – Toute reproduction non autorisée est un délit.
Le plan de tran sport [x ij ] qui en résulte :
9
11
28
6
14
5
9
11
7
5
3
6
5
a i
18
18
32
14
73
9
9
I
II
III
IV
1
2
3
4
5
6
i
j
b j
a) véri    fie 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
et a a i 5 a b j
2) a
6
j51
x 1j 5 0 1 0 1 18 1 0 1 0 1 0 5 18 5 a 1
a
6
j51
x 2j 5 9 1 11 1 7 1 0 1 0 1 5 5 32 5 a 2 , etc.
3) a
4
i 51
x i1 5 0 1 9 1 0 1 0 5 9 5 b 1
a
4
i 51
x i2 5 0 1 11 1 0 1 0 5 11 5 b 2
a
4
i 51
x i3 5 18 1 7 1 3 1 0 5 28 5 b 3 , etc.
b) en outre, le nombre des rela tions inuti li sées est de 15 ; il est pré ci sé ment égal à :
nm 2 1 n 1 m 2 12 5 6 3 4 2 1 6 1 4 2 12 5 24 2 9 5 15,
la solu tion obte nue n’est donc pas dégénérée.
On a bien affaire à une solu tion de base. Ce que l’on véri   
fie en tra    çant le graphe 
biparti asso cié : c’est bien un arbre.
• Deuxième phase : optimisa tion de la solu tion de base par la méthode
du « stepping- stone ».
On ne sait pas encore si la solu tion obte nue opti mise la fonc tion éco no mique (4.4) :
z 5 a
i
a
j
c ij # x ij 5 12x 11 1 27x 12 1 61x 13 1 c
1 23x 21 1 39x 22 1 c 1 40x 45 1 49x 46 .