5. Flots et tensions
Voici un problème bien formalisé, et pour lequel la formalisation est utile.
Le problème des affectations, des transports, des flots et des tensions révèle sous ses différents noms les multiples facettes d'une même réalité algébrique rencontrée historiquement dans des cadres très différents. Empruntons deux exemples caractéristiques à Claude Berge.
Affectation optimale du personnel (D. Votaw et A. Orden). Considérons p ouvriers a1, a2, ..., ap que l'on veut répartir sur q machines b1 , ..., bq. Le rendement de l'ouvrier ai sur la machine b j est donné par un nombre kij. Comment affecter les ouvriers aux machines pour maximiser le rendement total ?
Problème des trajets maritimes à vide (B. O. Koopmans). Considérons le trafic des cargos en 1913 : certains ports, comme Lisbonne, San Francisco, Athènes, Yokohama, exportent peu et importent beaucoup ; d'autres ports, tels New York, La Plata, Odessa, Rotterdam, exportent beaucoup et importent peu. Il faudra donc envoyer les cargos à vide le long des lignes maritimes usuelles, de façon à satisfaire les demandes en navires vides de New York, La Plata, etc. Connaissant la longueur li de la traversée sur la ligne maritime i, on veut minimiser le coût de ce rapatriement.
La formalisation mathématique de ces problèmes nécessite une série de définitions.
On appelle graphe de transport un graphe orienté où l'on distingue deux sommets, la sortie et l'entrée, et un arc qui les relie. Dans un tel graphe, à tout couple de sommets quelconques (xi, xj) liés par un arc, on affecte deux nombres bij et cij (bij ≤ cij) appelés capacités inférieure et supérieure de l'arc.
Supposons que les arcs désignent des chemins à sens unique le long desquels on fait circuler des personnes en nombre supérieur à b
… pour nos abonnés, l'article se prolonge sur 5 pages…
