4.9 Les pro grammes de tran sport
153
© Dunod – Toute reproduction non autorisée est un délit.
2.
a
6
j51
x 1 j 5 9 1 9 1 0 1 0 1 0 1 0 5 18 5 a 1 ;
a
6
j51
x 2 j 5 0 1 2 1 28 1 2 1 0 1 0 5 32 5 a 2 ; etc.
3.
a
4
i 51
x i1 5 9 1 0 1 0 1 0 5 9 5 b 1 ;
a
4
i 51
x i2 5 9 1 2 1 0 1 0 5 11 5 b 2 ; etc.
et, rappelons- le, nous ne nous sommes, jus qu’à présent,
pas occupé du seul pro blème de recherche opé ra tion -
nelle que contient la ques tion, c’est- à-dire la minimi sa -
tion du coût de tran sport.
Dans chaque programme de tran sport, il y aura donc néces sai re ment une phase
d’opti mi sation. Nous allons indi quer com ment la théo rie des graphes va faci li ter le
tra vail. Monétairement, la solu tion que nous avons trou vée coûte :
9 3 12 1 9 3 27 1 2 3 39 1 28 3 78 1 c 1 5 3 49 5 3 700 u.m.
mais on peut ima gi ner, du moment qu’elle a ignoré le coût de tran sport, que des
modi fi ca
tions ulté
rieures vont pou voir amé lio rer ce coût...
Or, com ment la modi
fi ca tion la plus élé men taire se présente telle?
Admet tons qu’on veuille tran spor ter une unité de mar chan dise sur la rela tion
(I, 3) jus qu’à présent inuti li sée. Si nous réa li sions cette opé ra tion, il nous fau drait
retran cher une unité tran spor tée sur la rela tion (I, 2) et éga le ment sur la rela tion (II,
3), de manière à ne pas chan ger les totaux des x ij sur la ligne I et dans la colonne 3 ; il
fau drait aussi ajou ter une unité sur la rela tion (II, 2) de manière à réta blir l’équi libre
sur la ligne II et dans la colonne 2.
D’autre part, nous sommes en mesure d’é valuer le coût mar gi nal d I,3 de l’opé ra -
tion, puisque nous connais sons les coûts uni taires de tran sport pour toutes les rela -
tions. On a donc dans ce cas :
d I, 3 5 c I3 1 c II2 2 c I2 2 c II3 5 161 1 39 2 27 2 78 5 100 2 105 5 2 5,
Figure 4.42
Arbre asso cié à la solu tion
de base du coin Nord- Ouest.
I
II
I
II
I
II
I
II
2 28 30
9 1
1 9
2 1 28 1 30
2
3
2
3
2
3
2
3
9
0 9
0
9 9
11 19 30
27 61
39 78
Extrait du tableau
des [x ij ]
(avant modi
fi ca tion)
I
II
I
II
I
II
I
II
2 28 30
9 1
1 9
2 1 28 1 30
2
3
2
3
2
3
2
3
9
0 9
0
9 9
11 19 30
27 61
39 78
(modi fi ca tion
uni taire)
I
II
I
II
I
II
I
II
2 28 30
9 1
1 9
2 1 28 1 30
2
3
2
3
2
3
2
3
9
0 9
0
9 9
11 19 30
27 61
39 78
Extrait du tableau
des coûts [c ij ]
I
II
I
II
I
II
I
II
2 28 30
9 1
1 9
2 1 28 1 30
2
3
2
3
2
3
2
3
9
0 9
0
9 9
11 19 30
27 61
39 78
Extrait du nou veau
tableau des [x ij ]
(après modi fi ca tion
maximale)
153
© Dunod – Toute reproduction non autorisée est un délit.
2.
a
6
j51
x 1 j 5 9 1 9 1 0 1 0 1 0 1 0 5 18 5 a 1 ;
a
6
j51
x 2 j 5 0 1 2 1 28 1 2 1 0 1 0 5 32 5 a 2 ; etc.
3.
a
4
i 51
x i1 5 9 1 0 1 0 1 0 5 9 5 b 1 ;
a
4
i 51
x i2 5 9 1 2 1 0 1 0 5 11 5 b 2 ; etc.
et, rappelons- le, nous ne nous sommes, jus qu’à présent,
pas occupé du seul pro blème de recherche opé ra tion -
nelle que contient la ques tion, c’est- à-dire la minimi sa -
tion du coût de tran sport.
Dans chaque programme de tran sport, il y aura donc néces sai re ment une phase
d’opti mi sation. Nous allons indi quer com ment la théo rie des graphes va faci li ter le
tra vail. Monétairement, la solu tion que nous avons trou vée coûte :
9 3 12 1 9 3 27 1 2 3 39 1 28 3 78 1 c 1 5 3 49 5 3 700 u.m.
mais on peut ima gi ner, du moment qu’elle a ignoré le coût de tran sport, que des
modi fi ca
tions ulté
rieures vont pou voir amé lio rer ce coût...
Or, com ment la modi
fi ca tion la plus élé men taire se présente telle?
Admet tons qu’on veuille tran spor ter une unité de mar chan dise sur la rela tion
(I, 3) jus qu’à présent inuti li sée. Si nous réa li sions cette opé ra tion, il nous fau drait
retran cher une unité tran spor tée sur la rela tion (I, 2) et éga le ment sur la rela tion (II,
3), de manière à ne pas chan ger les totaux des x ij sur la ligne I et dans la colonne 3 ; il
fau drait aussi ajou ter une unité sur la rela tion (II, 2) de manière à réta blir l’équi libre
sur la ligne II et dans la colonne 2.
D’autre part, nous sommes en mesure d’é valuer le coût mar gi nal d I,3 de l’opé ra -
tion, puisque nous connais sons les coûts uni taires de tran sport pour toutes les rela -
tions. On a donc dans ce cas :
d I, 3 5 c I3 1 c II2 2 c I2 2 c II3 5 161 1 39 2 27 2 78 5 100 2 105 5 2 5,
Figure 4.42
Arbre asso cié à la solu tion
de base du coin Nord- Ouest.
I
II
I
II
I
II
I
II
2 28 30
9 1
1 9
2 1 28 1 30
2
3
2
3
2
3
2
3
9
0 9
0
9 9
11 19 30
27 61
39 78
Extrait du tableau
des [x ij ]
(avant modi
fi ca tion)
I
II
I
II
I
II
I
II
2 28 30
9 1
1 9
2 1 28 1 30
2
3
2
3
2
3
2
3
9
0 9
0
9 9
11 19 30
27 61
39 78
(modi fi ca tion
uni taire)
I
II
I
II
I
II
I
II
2 28 30
9 1
1 9
2 1 28 1 30
2
3
2
3
2
3
2
3
9
0 9
0
9 9
11 19 30
27 61
39 78
Extrait du tableau
des coûts [c ij ]
I
II
I
II
I
II
I
II
2 28 30
9 1
1 9
2 1 28 1 30
2
3
2
3
2
3
2
3
9
0 9
0
9 9
11 19 30
27 61
39 78
Extrait du nou veau
tableau des [x ij ]
(après modi fi ca tion
maximale)