Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
150
Entre m ori gines (dépôts) et n des ti nations (clients) consti tuant les som mets d’un
graphe biparti, (rap pe lons qu’un graphe est dit biparti si ses som mets sont par ta gés
en deux classes, à l’inté rieur de cha cune des quelles les som mets ne sont pas deux à
deux adja cents), on peut tra cer m 3 n arcs qui sym bo lisent les liai sons que l’on peut
employer pour tran spor ter des mar chan dises de chaque ori gine vers chaque des ti -
nation. On pour rait aussi com plé ter ce graphe sans boucle par une entrée et une sor tie
pour obte nir un réseau de tran sport. Mais le pro blème que l’on se pose main te nant
n’est plus celui du flot opti mal, et cette trans
for
ma tion ne serait ici d’aucune uti
lité.
En effet dans les programmes de tran sport, les capa ci tés des arcs sont sup po sées
illi mi tées, mais chaque arc est valué par le coût uni taire du tran sport sur la liai son
qu’il repré sente. Ce que l’on cherche est une solu tion à coût mini mal.
Dès 1776, G. Monge s’était atta qué à ce pro blème, mais en continu, c’est- à-dire
en consi dé rant le dépla ce
ment de volumes infi ni té si maux dv ; il avait dû bâtir la théo -
rie nou velle des congruences de nor males pour le résoudre.
Aujourd’hui, on envi sage le pro blème dis cret qui consiste à tran spor ter des uni tés
indi vi sibles (m
3
ou tonnes par exemple) et ainsi le pro blème se for mule en nombres
entiers. Sous cette forme, c’est A. Tolstoï qui l’a publié en 1939, L.V. Kantorovitch
et F.L. Hitchcock le pré ci sant de nou veau en 1941, avec Koopmans.
Pra ti que ment et sans perte de géné ra lité, on se ramène tou jours au cas où l’offre
égale la demande : le total géné ral des quan ti tés dis po nibles aux ori gines cor res pond
au total géné ral des demandes aux dif fé rentes des ti nations. S’il n’en était pas ainsi, il
suf fi rait de créer soit une des ti nation fic tive (cas de l’excès des dis po ni bi li tés) soit une
ori gine fic
tive (cas de l’excès des demandes), en affec
tant à ce som met fic tif la dif fé
rence entre les deux totaux géné raux et en valuant les rela tions nou velles par un coût
nul, de manière à ne pas trou bler le pro ces sus de minimi sa tion du coût de tran sport des
quan ti tés effec ti ve ment tran spor tées.
À titre d’exemple, nous exa mi ne rons le pro blème sui vant : assu rer, au moindre
coût, les tran sports des quan ti tés deman dées aux dépôts (clients) numé ro tés de 1 à 6,
à par tir des usines de I à IV, connais sant les dis po ni bi li tés de ces usines et les coûts
de tran sport uni taires de toute ori gine à toute des ti nation.
Matrice des coûts uni taires
1
2
3
4
5
6
I
i j
(b j )
II
III
Quantités
demandées
Quantités
disponibles (a i )
IV
18
32
14
9
73
9
11
28
6
14
5
12
27
61
49
83
35
23
39
78
28
65
42
67
56
92
24
53
54
71
43
91
67
40
49
150
Entre m ori gines (dépôts) et n des ti nations (clients) consti tuant les som mets d’un
graphe biparti, (rap pe lons qu’un graphe est dit biparti si ses som mets sont par ta gés
en deux classes, à l’inté rieur de cha cune des quelles les som mets ne sont pas deux à
deux adja cents), on peut tra cer m 3 n arcs qui sym bo lisent les liai sons que l’on peut
employer pour tran spor ter des mar chan dises de chaque ori gine vers chaque des ti -
nation. On pour rait aussi com plé ter ce graphe sans boucle par une entrée et une sor tie
pour obte nir un réseau de tran sport. Mais le pro blème que l’on se pose main te nant
n’est plus celui du flot opti mal, et cette trans
for
ma tion ne serait ici d’aucune uti
lité.
En effet dans les programmes de tran sport, les capa ci tés des arcs sont sup po sées
illi mi tées, mais chaque arc est valué par le coût uni taire du tran sport sur la liai son
qu’il repré sente. Ce que l’on cherche est une solu tion à coût mini mal.
Dès 1776, G. Monge s’était atta qué à ce pro blème, mais en continu, c’est- à-dire
en consi dé rant le dépla ce
ment de volumes infi ni té si maux dv ; il avait dû bâtir la théo -
rie nou velle des congruences de nor males pour le résoudre.
Aujourd’hui, on envi sage le pro blème dis cret qui consiste à tran spor ter des uni tés
indi vi sibles (m
3
ou tonnes par exemple) et ainsi le pro blème se for mule en nombres
entiers. Sous cette forme, c’est A. Tolstoï qui l’a publié en 1939, L.V. Kantorovitch
et F.L. Hitchcock le pré ci sant de nou veau en 1941, avec Koopmans.
Pra ti que ment et sans perte de géné ra lité, on se ramène tou jours au cas où l’offre
égale la demande : le total géné ral des quan ti tés dis po nibles aux ori gines cor res pond
au total géné ral des demandes aux dif fé rentes des ti nations. S’il n’en était pas ainsi, il
suf fi rait de créer soit une des ti nation fic tive (cas de l’excès des dis po ni bi li tés) soit une
ori gine fic
tive (cas de l’excès des demandes), en affec
tant à ce som met fic tif la dif fé
rence entre les deux totaux géné raux et en valuant les rela tions nou velles par un coût
nul, de manière à ne pas trou bler le pro ces sus de minimi sa tion du coût de tran sport des
quan ti tés effec ti ve ment tran spor tées.
À titre d’exemple, nous exa mi ne rons le pro blème sui vant : assu rer, au moindre
coût, les tran sports des quan ti tés deman dées aux dépôts (clients) numé ro tés de 1 à 6,
à par tir des usines de I à IV, connais sant les dis po ni bi li tés de ces usines et les coûts
de tran sport uni taires de toute ori gine à toute des ti nation.
Matrice des coûts uni taires
1
2
3
4
5
6
I
i j
(b j )
II
III
Quantités
demandées
Quantités
disponibles (a i )
IV
18
32
14
9
73
9
11
28
6
14
5
12
27
61
49
83
35
23
39
78
28
65
42
67
56
92
24
53
54
71
43
91
67
40
49