Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
156
La manière de remé dier à cette situa tion est simple. Elle
consiste à « reconnec ter » les sous- arbres, de manière à obte -
nir de nou veau un arbre.
Dans le présent cas (fig. 4.45), cela peut se faire de 8 de façons
différentes ; par exemple on peut ajou ter un arc (III, 1), repré -
sen tant le tran sport fic tif d’une quan tité très petite, e . 0.
Une fois l’opti mum obtenu, on fera e 5 0. On obtient alors
une solution de base, non dégénérée, pour laquelle on peut
calculer les 15 d i,j .
9
9
2
28
2
4
5
III
I
II
IV
5
1
2
3
4
6
i j
14
9
14
18
32
9
14
28
11
6
5
Remarque pra tique impor tante. Lorsque, dans un pro blème dégé néré, si un
d i,j est négatif et si la seule quan tité associée dépla çable vaut ε, il ne fau drait
pas en conclure que l’on a atteint l’opti mum et l’on doit pour suivre l’algo -
rithme (en veillant à ne pas retom ber sur une solu tion anté rieure). On montre
en effet que le cri tère d’optimalité pour une solu tion est que tout coût mar gi nal
d i,j de liai son non employée 1 x ij 5 02 doit être posi tif ou nul.
Réso lu tion pra tique du pro blème de tran sport
• Pre mière phase (obten tion d’une solu tion de base ini tiale)
Il est bien évident que si la solu tion de base ini tiale du pro blème a été construite en
tenant compte des faits éco no miques, c’est- à-dire en essayant d’obte nir un coût total
peu élevé, la pro cé dure d’opti mi sation décrite au para graphe pré cé dent risque d’être
consi dé ra ble ment abré gée.
Les pra ti ciens ont pro posé un très grand nombre d’heu ris tiques pour par ve nir
à fournir une bonne pre mière solu tion de base. Com men çons par les heu ris tiques
« gour mandes » : cer tains ont pré co nisé la pro cé dure MINI LI, consis tant à affec ter
la quan tité maximale à la rela tion de coût unitaire mini mal dans la pre mière ligne,
puis à la rela tion de coût mini mal, parmi celles qui sub sistent, dans la seconde
ligne, etc., ou encore MINICO (méthode cor res pon dante uti li sant, cette fois, les
coûts unitaires mini maux en colonne). Plus uti le ment, l’affec ta tion successive
aux rela tions de coûts mini maux crois sants du tableau, en par tant du mini mum
minimorum, a ses par ti sans : c’est la pro cé dure MINITAB.
Figure 4.45
156
La manière de remé dier à cette situa tion est simple. Elle
consiste à « reconnec ter » les sous- arbres, de manière à obte -
nir de nou veau un arbre.
Dans le présent cas (fig. 4.45), cela peut se faire de 8 de façons
différentes ; par exemple on peut ajou ter un arc (III, 1), repré -
sen tant le tran sport fic tif d’une quan tité très petite, e . 0.
Une fois l’opti mum obtenu, on fera e 5 0. On obtient alors
une solution de base, non dégénérée, pour laquelle on peut
calculer les 15 d i,j .
9
9
2
28
2
4
5
III
I
II
IV
5
1
2
3
4
6
i j
14
9
14
18
32
9
14
28
11
6
5
Remarque pra tique impor tante. Lorsque, dans un pro blème dégé néré, si un
d i,j est négatif et si la seule quan tité associée dépla çable vaut ε, il ne fau drait
pas en conclure que l’on a atteint l’opti mum et l’on doit pour suivre l’algo -
rithme (en veillant à ne pas retom ber sur une solu tion anté rieure). On montre
en effet que le cri tère d’optimalité pour une solu tion est que tout coût mar gi nal
d i,j de liai son non employée 1 x ij 5 02 doit être posi tif ou nul.
Réso lu tion pra tique du pro blème de tran sport
• Pre mière phase (obten tion d’une solu tion de base ini tiale)
Il est bien évident que si la solu tion de base ini tiale du pro blème a été construite en
tenant compte des faits éco no miques, c’est- à-dire en essayant d’obte nir un coût total
peu élevé, la pro cé dure d’opti mi sation décrite au para graphe pré cé dent risque d’être
consi dé ra ble ment abré gée.
Les pra ti ciens ont pro posé un très grand nombre d’heu ris tiques pour par ve nir
à fournir une bonne pre mière solu tion de base. Com men çons par les heu ris tiques
« gour mandes » : cer tains ont pré co nisé la pro cé dure MINI LI, consis tant à affec ter
la quan tité maximale à la rela tion de coût unitaire mini mal dans la pre mière ligne,
puis à la rela tion de coût mini mal, parmi celles qui sub sistent, dans la seconde
ligne, etc., ou encore MINICO (méthode cor res pon dante uti li sant, cette fois, les
coûts unitaires mini maux en colonne). Plus uti le ment, l’affec ta tion successive
aux rela tions de coûts mini maux crois sants du tableau, en par tant du mini mum
minimorum, a ses par ti sans : c’est la pro cé dure MINITAB.
Figure 4.45