Problèmes de flots
213
Le problème consiste à transporter toutes les disponibilités (donc à satisfaire toutes les
demandes) de façon à minimiser le coût de transport total.
9.5.2. Programmation linéaire
Le problème tel qu'il vient d'être posé, se met facilement sous la forme d'un programme
linéaire.
Appelons en effet
la quantité transportée entre et . On a les équations :
ce qui fait
relations linéaires pour les
, en fait
relations
indépendantes, du fait de l'égalité
j
n
j
i
m
i
b
a
1
=
1
=
=
On a évidemment par ailleurs
Enfin, il s'agit de minimiser la fonctionnelle linéaire
ij
ij
j
i
x
c
C
,
=
On est donc en présence d'un programme linéaire à
variables et
contraintes. On pourrait résoudre ce problème par l'algorithme du simplexe ( le fait que
les
doivent être des entiers n'est pas gênant : on démontre que si les , ,
sont
entiers, ce qui n'est pas restrictif en recherche opérationnelle, alors la solution du
programme linéaire est entière).
Mais l'algorithme du simplexe n'est pas le plus performant pour ce type de problème. On
préfère utiliser des procédures fondées sur les concepts de flots.