4.9 Les pro grammes de tran sport
161
© Dunod – Toute reproduction non autorisée est un délit.
d’où :
V 3 5 c III, 3 2 0 5 92 2 0 5 92,
et, par suite, l’ins crip tion du poten tiel 92 sous la colonne 3 au bas de la matrice.
Du fait que U III 5 0, on a immé dia te ment V 4 5 24 et V 5 5 53, puisque les rela tions
(III,4) et (III,5) sont affec tées. Ayant V 5 5 53, on obtient :
U IV 5 V 5 2 c IV, 5 5 53 2 40 5 13,
et ainsi de suite. La pro cé dure équi vaut très exac te ment à celle que l’on a pra ti -
quée sur l’arbre de la figure 4.48, mais elle évite le recours à un son tracé.
Pour cal cu ler alors le coût mar gi nal d’une liai son inuti li sée, on la repère
d’abord sur le tableau (la par tie haute de la case étant vide), par exemple (III, 2), et
l’on lit c III,2 5 56. On a :
d III, 2 5 U III 1 c III, 2 2 V 2 5 0 1 56 2 53 5 3,
car on remarque que U III est le poten tiel lu sur la ligne III à droite de la matrice,
alors que V 2 est celui que l’on lit au bas de la colonne 2, sous la matrice.
Le lec teur s’exer cera à cal cu ler de cette façon tous les coûts mar gi naux. Il en
trou vera un seul néga tif (c’est- à-dire un seul éco no mi que ment inté res sant) ; c’est :
d III, 6 5 0 1 54 2 56 5 22.
Il faut ensuite, pour tout coût mar gi nal néga tif δ ij , rechercher le cycle de subs ti -
tution per met tant de réa
li ser la modification du tran sport auquel il cor
res pond. C’est
le cycle unique qu’on obtient en rajoutant à l’arbre (Fig. 4.46) l’arête [ij] ; quand un
tel cycle ne comporte que 4 arêtes, il est aisé de le trouver directement sur le tableau
des [x ij ] de la solution de base courante.
Dans le cas présent, posons un signe 1 dans la case (III,6) ; il nous faut un signe
– en (II,6), un signe 1 en (II,3) et, enfin, un signe – en (III,3). On contrôle d’ailleurs
que 54 2 42 1 78 2 92 5 22. Les cases mar quées sont asso ciées aux arcs du cycle
de subs ti tution. Cherc hons main te nant la quan tité maximale déplaçable : les signes
–, dans les cases (II, 6) et (III, 3), per mettent de consta ter que si l’on peut dimi nuer de
5 la quan tité ins crite en (II,6), en revanche on ne peut dimi nuer que de 3 celle por tée
en (III,3) : fina le ment, il est seule ment pos sible de dépla cer trois uni tés. Le résul
tat
de cette subs ti tution sera 3 3 (22) 5 26, c’est- à-dire un gain total de 6. La solu tion
obte nue alors a pour coût : 3 529 ; nous mon trons plus bas qu’elle est opti male.
S’il y avait plu sieurs d i, j néga tifs, on cal cu le rait le gain rela tif à cha cune des subs ti -
tutions pos sibles et l’on choi si rait de réa li ser celle qui apporte le gain total le plus grand.
Par fois, plu sieurs subs ti tutions sont pos sibles simul ta né ment et rien n’empêche
alors de les réa
li ser ensemble ; il suf fit qu’elles se tra duisent par des cycles de subs
ti tution indé pen dants (sans arcs ni sommets com muns).
Exer cice. Le lec teur pourra s’exer cer, en par tant de la solu tion de base obte nue
par la méthode du coin Nord- ouest. Il trou vera 5 coûts mar gi naux néga tifs, dont les
deux plus inté res sants peuvent être réa li sés ensemble, fai sant tom ber le coût total
du tran sport à 3 607. Après avoir effec tué ces subs ti tutions simul ta nées, il trou vera
encore deux subs ti tutions com pa tibles, l’ame nant au coût total de 3 529.
161
© Dunod – Toute reproduction non autorisée est un délit.
d’où :
V 3 5 c III, 3 2 0 5 92 2 0 5 92,
et, par suite, l’ins crip tion du poten tiel 92 sous la colonne 3 au bas de la matrice.
Du fait que U III 5 0, on a immé dia te ment V 4 5 24 et V 5 5 53, puisque les rela tions
(III,4) et (III,5) sont affec tées. Ayant V 5 5 53, on obtient :
U IV 5 V 5 2 c IV, 5 5 53 2 40 5 13,
et ainsi de suite. La pro cé dure équi vaut très exac te ment à celle que l’on a pra ti -
quée sur l’arbre de la figure 4.48, mais elle évite le recours à un son tracé.
Pour cal cu ler alors le coût mar gi nal d’une liai son inuti li sée, on la repère
d’abord sur le tableau (la par tie haute de la case étant vide), par exemple (III, 2), et
l’on lit c III,2 5 56. On a :
d III, 2 5 U III 1 c III, 2 2 V 2 5 0 1 56 2 53 5 3,
car on remarque que U III est le poten tiel lu sur la ligne III à droite de la matrice,
alors que V 2 est celui que l’on lit au bas de la colonne 2, sous la matrice.
Le lec teur s’exer cera à cal cu ler de cette façon tous les coûts mar gi naux. Il en
trou vera un seul néga tif (c’est- à-dire un seul éco no mi que ment inté res sant) ; c’est :
d III, 6 5 0 1 54 2 56 5 22.
Il faut ensuite, pour tout coût mar gi nal néga tif δ ij , rechercher le cycle de subs ti -
tution per met tant de réa
li ser la modification du tran sport auquel il cor
res pond. C’est
le cycle unique qu’on obtient en rajoutant à l’arbre (Fig. 4.46) l’arête [ij] ; quand un
tel cycle ne comporte que 4 arêtes, il est aisé de le trouver directement sur le tableau
des [x ij ] de la solution de base courante.
Dans le cas présent, posons un signe 1 dans la case (III,6) ; il nous faut un signe
– en (II,6), un signe 1 en (II,3) et, enfin, un signe – en (III,3). On contrôle d’ailleurs
que 54 2 42 1 78 2 92 5 22. Les cases mar quées sont asso ciées aux arcs du cycle
de subs ti tution. Cherc hons main te nant la quan tité maximale déplaçable : les signes
–, dans les cases (II, 6) et (III, 3), per mettent de consta ter que si l’on peut dimi nuer de
5 la quan tité ins crite en (II,6), en revanche on ne peut dimi nuer que de 3 celle por tée
en (III,3) : fina le ment, il est seule ment pos sible de dépla cer trois uni tés. Le résul
tat
de cette subs ti tution sera 3 3 (22) 5 26, c’est- à-dire un gain total de 6. La solu tion
obte nue alors a pour coût : 3 529 ; nous mon trons plus bas qu’elle est opti male.
S’il y avait plu sieurs d i, j néga tifs, on cal cu le rait le gain rela tif à cha cune des subs ti -
tutions pos sibles et l’on choi si rait de réa li ser celle qui apporte le gain total le plus grand.
Par fois, plu sieurs subs ti tutions sont pos sibles simul ta né ment et rien n’empêche
alors de les réa
li ser ensemble ; il suf fit qu’elles se tra duisent par des cycles de subs
ti tution indé pen dants (sans arcs ni sommets com muns).
Exer cice. Le lec teur pourra s’exer cer, en par tant de la solu tion de base obte nue
par la méthode du coin Nord- ouest. Il trou vera 5 coûts mar gi naux néga tifs, dont les
deux plus inté res sants peuvent être réa li sés ensemble, fai sant tom ber le coût total
du tran sport à 3 607. Après avoir effec tué ces subs ti tutions simul ta nées, il trou vera
encore deux subs ti tutions com pa tibles, l’ame nant au coût total de 3 529.