4.9 Les pro grammes de tran sport
155
© Dunod – Toute reproduction non autorisée est un délit.
ce qui résume en fait le cal cul ci- dessous asso cié au cycle de subs ti tution de la rela -
tion (I, 6), qui est de lon gueur 8 ; on obtient ce cycle en rajou tant l’arc (I, 6) à l’arbre
ci- dessus : [I, 6, IV, 5III, 4, II, 2, I] :
d I,6 5 c I6 2 c IV6 1 c IV5 2 c III5 1 c III4 2 c II4 1 c II2 2 c I2
5 35 2 49 1 40 2 53 1 24 2 28 1 39 2 27 5 219.
Nous pro fi
terons de toutes ces remarques dans les appli
ca tions.
On en déduit une méthode d’amé lio ra tions suc ces sives de la solu tion ini tiale,
per met tant de pas ser d’une solu tion de base à une autre solu tion de base plus éco -
no mique, qui néces si tera, à chaque étape, de déter mi ner tous les coûts mar gi naux
d i,j , pour les rela tions inuti li sées, et, d’après les quan ti tés déplaçables sur le cycle
de subs ti tution, le gain total cor res pon dant à cha cun de ceux qui sont néga tifs. On
choi sira à chaque pas la meilleure modi fi ca tion pos sible. Si tous les d i, j deviennent
non- négatifs, on peut mon trer qu’on a atteint l’opti mum. Cet opti mum sera unique si
tous les d i, j sont stric te ment posi tifs à la der nière étape ; il y aura plu sieurs solu tions
équi va lentes si cer tains sont égaux à 0.
La démons tra tion de la conver gence de cet algo rithme, qui serait très aisée si le
coût total du tran sport dimi nuait stric te ment à chaque étape, est com pro mise par le
fait qu’il se pré sente, comme on le verra ci- dessous, des risques de retour à une solu -
tion déjà ren contrée anté rieu re ment, si le coût total de tran sport ne varie pas pour
cer tains échanges : il s’agit du cas de solu tions dégénérées.
Remarque. Jus qu’à présent nous n’avons pas encore envi sagé le cas où la
solu tion ini tiale obte nue ne serait pas une solu tion de base, c’est- à-dire com -
por te rait plus de zéros qu’il n’en faut.
Tel serait le cas du pro blème consi déré plus haut si l’on échan geait la pre mière
ligne contre la troi sième et la pre mière colonne contre la cin quième avant
d’appli quer la méthode du coin Nord- Ouest.
Tableau des c ij (réordonné)
Tableau des x ij
5 1 2 3 4 6
14 9 11 28 6 3
53
65
65
40 71
23
12 27 61 49 35
42
49
67
28
78
39
43 91
67 56 92 26 54
14 9 11 28 6 5
9 9
2 28 2
4 5
i j
5 1 2 3 4 6
i j
9
14
18
32
9
14
14
18
32
III
I
II
IV
III
I
II
IV
b j
b j
a i
a i
On obtien drait une solu tion dégénérée, avec 16 zéros au lieu de 15, dont le graphe
com pren drait deux sous- arbres, ce qui ne per met trait plus de cal cu ler tous les d i,j .
Bien entendu, une telle solu tion dégénérée peut se pré sen ter aussi à une ité ra -
tion quel conque de la réso lu tion du pro blème.
155
© Dunod – Toute reproduction non autorisée est un délit.
ce qui résume en fait le cal cul ci- dessous asso cié au cycle de subs ti tution de la rela -
tion (I, 6), qui est de lon gueur 8 ; on obtient ce cycle en rajou tant l’arc (I, 6) à l’arbre
ci- dessus : [I, 6, IV, 5III, 4, II, 2, I] :
d I,6 5 c I6 2 c IV6 1 c IV5 2 c III5 1 c III4 2 c II4 1 c II2 2 c I2
5 35 2 49 1 40 2 53 1 24 2 28 1 39 2 27 5 219.
Nous pro fi
terons de toutes ces remarques dans les appli
ca tions.
On en déduit une méthode d’amé lio ra tions suc ces sives de la solu tion ini tiale,
per met tant de pas ser d’une solu tion de base à une autre solu tion de base plus éco -
no mique, qui néces si tera, à chaque étape, de déter mi ner tous les coûts mar gi naux
d i,j , pour les rela tions inuti li sées, et, d’après les quan ti tés déplaçables sur le cycle
de subs ti tution, le gain total cor res pon dant à cha cun de ceux qui sont néga tifs. On
choi sira à chaque pas la meilleure modi fi ca tion pos sible. Si tous les d i, j deviennent
non- négatifs, on peut mon trer qu’on a atteint l’opti mum. Cet opti mum sera unique si
tous les d i, j sont stric te ment posi tifs à la der nière étape ; il y aura plu sieurs solu tions
équi va lentes si cer tains sont égaux à 0.
La démons tra tion de la conver gence de cet algo rithme, qui serait très aisée si le
coût total du tran sport dimi nuait stric te ment à chaque étape, est com pro mise par le
fait qu’il se pré sente, comme on le verra ci- dessous, des risques de retour à une solu -
tion déjà ren contrée anté rieu re ment, si le coût total de tran sport ne varie pas pour
cer tains échanges : il s’agit du cas de solu tions dégénérées.
Remarque. Jus qu’à présent nous n’avons pas encore envi sagé le cas où la
solu tion ini tiale obte nue ne serait pas une solu tion de base, c’est- à-dire com -
por te rait plus de zéros qu’il n’en faut.
Tel serait le cas du pro blème consi déré plus haut si l’on échan geait la pre mière
ligne contre la troi sième et la pre mière colonne contre la cin quième avant
d’appli quer la méthode du coin Nord- Ouest.
Tableau des c ij (réordonné)
Tableau des x ij
5 1 2 3 4 6
14 9 11 28 6 3
53
65
65
40 71
23
12 27 61 49 35
42
49
67
28
78
39
43 91
67 56 92 26 54
14 9 11 28 6 5
9 9
2 28 2
4 5
i j
5 1 2 3 4 6
i j
9
14
18
32
9
14
14
18
32
III
I
II
IV
III
I
II
IV
b j
b j
a i
a i
On obtien drait une solu tion dégénérée, avec 16 zéros au lieu de 15, dont le graphe
com pren drait deux sous- arbres, ce qui ne per met trait plus de cal cu ler tous les d i,j .
Bien entendu, une telle solu tion dégénérée peut se pré sen ter aussi à une ité ra -
tion quel conque de la réso lu tion du pro blème.