Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
158
spor ter à la rela tion qui com porte le plus petit coût de la matrice (ici I, 1), puis pas ser
à celle à laquelle cor res pond le plus petit coût dans le reste du tableau, et ainsi de
suite (méthode MINITAB), on pré fère rechercher une rela tion telle que, si l’on ne
lui affecte pas la quan tité la plus grande pos sible, on sera obligé, dans la suite du
pro blème, d’affec ter cette quan tité, à une ou plu sieurs rela tions de coût de beau coup
supé rieur.
Puis on passe à la rela tion qui est dési gnée par la dif fé rence maximale dans le tableau
res tant (cf tableau “2
e
pas” ci-dessus), et ainsi de suite.
• 2
e
pas. Sur la matrice réduite, la dif fé rence maximale est 17, ce qui amène à affec ter
la quan tité 18 à la rela tion (I, 3) satu rant ainsi la ligne I, qui disparaît du problème.
a i
j i
18
32
14 3
16
1
� �
9 11 10 14 5 49
44 4 13 13 7
Dc
Dℓ
Dℓ
1 2 3 5 6
67 56 92 53 54
71 43 91 40 49
23
�
39 78 65 42
3
e
pas
II
III
IV
b j �
�
a i
j i
18
32
14 3
16
1
� �
11 10 14 5 40
4 13 13 7
2 3 5 6
56 92 53 54
39 78 65 42
43 91 40 49
4
e
pas
II
III
IV
b j �
�
�
Dc
• 3
e
pas. Le tableau res tant fait appa raître la dif fé rence maximale 44, cor res pon dant à
la rela tion (II,1). On y affec te la quan tité 9, ce qui sature la colonne 1, qui disparaît.
• 4
e
pas. Au qua trième pas, le tableau res tant se pré sente comme il est indi qué
ci-dessus. Deux colonnes four nissent la même dif fé rence maximale : 13 ; les rela -
tions (II,3) et (IV, 5) leur cor res pondent, avec des affec ta tions pos sibles de 10 et 9
res pec ti ve ment.
Trois solu tions sont ici accep tables, que nous ne dis cu te rons pas plus à fond :
1) affec ter 10 à la rela tion (II, 3) ;
2) affec ter 9 à la rela tion (IV, 5) ;
3) faire les deux affec ta tions en même temps (elles sont indépendantes).
Tout à fait arbi trai re ment,
(1)
déci dons d’affec ter 9 à la rela tion (IV,5), ce qui sature
la ligne IV.
À ce moment, grâce aux affec ta tions pra ti quées, quatre rela tions sont uti li sées et
quatre ran gées sont satu rées. En conti nuant ainsi, on affecte ensuite 11 en (II, 2), 5
en (II, 6), 5 en (III, 5), 7 en (II, 3) et, enfin, 3 en (III, 3).
1. Les autres affec ta tions condui sant ici direc te ment à l’opti mum, nous pri ve raient de la pos si bi
lité d’expo ser concrè te ment la deuxième phase de réso lu tion des pro blèmes de tran sport.
(1)
158
spor ter à la rela tion qui com porte le plus petit coût de la matrice (ici I, 1), puis pas ser
à celle à laquelle cor res pond le plus petit coût dans le reste du tableau, et ainsi de
suite (méthode MINITAB), on pré fère rechercher une rela tion telle que, si l’on ne
lui affecte pas la quan tité la plus grande pos sible, on sera obligé, dans la suite du
pro blème, d’affec ter cette quan tité, à une ou plu sieurs rela tions de coût de beau coup
supé rieur.
Puis on passe à la rela tion qui est dési gnée par la dif fé rence maximale dans le tableau
res tant (cf tableau “2
e
pas” ci-dessus), et ainsi de suite.
• 2
e
pas. Sur la matrice réduite, la dif fé rence maximale est 17, ce qui amène à affec ter
la quan tité 18 à la rela tion (I, 3) satu rant ainsi la ligne I, qui disparaît du problème.
a i
j i
18
32
14 3
16
1
� �
9 11 10 14 5 49
44 4 13 13 7
Dc
Dℓ
Dℓ
1 2 3 5 6
67 56 92 53 54
71 43 91 40 49
23
�
39 78 65 42
3
e
pas
II
III
IV
b j �
�
a i
j i
18
32
14 3
16
1
� �
11 10 14 5 40
4 13 13 7
2 3 5 6
56 92 53 54
39 78 65 42
43 91 40 49
4
e
pas
II
III
IV
b j �
�
�
Dc
• 3
e
pas. Le tableau res tant fait appa raître la dif fé rence maximale 44, cor res pon dant à
la rela tion (II,1). On y affec te la quan tité 9, ce qui sature la colonne 1, qui disparaît.
• 4
e
pas. Au qua trième pas, le tableau res tant se pré sente comme il est indi qué
ci-dessus. Deux colonnes four nissent la même dif fé rence maximale : 13 ; les rela -
tions (II,3) et (IV, 5) leur cor res pondent, avec des affec ta tions pos sibles de 10 et 9
res pec ti ve ment.
Trois solu tions sont ici accep tables, que nous ne dis cu te rons pas plus à fond :
1) affec ter 10 à la rela tion (II, 3) ;
2) affec ter 9 à la rela tion (IV, 5) ;
3) faire les deux affec ta tions en même temps (elles sont indépendantes).
Tout à fait arbi trai re ment,
(1)
déci dons d’affec ter 9 à la rela tion (IV,5), ce qui sature
la ligne IV.
À ce moment, grâce aux affec ta tions pra ti quées, quatre rela tions sont uti li sées et
quatre ran gées sont satu rées. En conti nuant ainsi, on affecte ensuite 11 en (II, 2), 5
en (II, 6), 5 en (III, 5), 7 en (II, 3) et, enfin, 3 en (III, 3).
1. Les autres affec ta tions condui sant ici direc te ment à l’opti mum, nous pri ve raient de la pos si bi
lité d’expo ser concrè te ment la deuxième phase de réso lu tion des pro blèmes de tran sport.
(1)