problème des déblais et des remblais

Deux tas de terre doivent combler deux trous. Plusieurs trajets sont possibles, mais transporter une tonne sur quatre kilomètres coûte davantage que sur un kilomètre. Il faut donc décider quelle quantité part de chaque tas et où elle arrive.

Le problème des déblais et des remblais cherche la répartition qui satisfait exactement les besoins tout en rendant minimale la somme de tous les transports. Cette « brouette de Monge » est devenue le modèle d'une question bien plus générale : déplacer au mieux une masse, une distribution ou des ressources.

Le problème des déblais et des remblais est un problème d'optimisation du transport. Des sources possèdent des quantités de masse à enlever et des destinations réclament des quantités à apporter. Un plan admissible précise la masse envoyée sur chaque liaison. Dans la version équilibrée, la masse totale disponible égale la masse totale demandée ; chaque offre et chaque demande doit alors être satisfaite.

Pour des sources numérotées par i et des destinations numérotées par j, la quantité transportée de i vers j est notée par le nombre x_ij. Le coût d'une unité sur cette liaison est noté c_ij. Le coût total du plan est ${\sum }_{i,j}{c}_{ij}{x}_{ij}\backslash sum\_\{i,j\}\; c\_\{ij\}x\_\{ij\}$. Il faut minimiser cette somme sous les contraintes x_ij ≥ 0, somme des envois de chaque source égale à son offre, et somme des arrivées à chaque destination égale à sa demande. Quand c_ij représente une distance, le coût s'exprime par exemple en tonnes-kilomètres ; d'autres coûts sont possibles.

Monge formalise en 1781 une version où chaque portion de masse reçoit une destination, sans fractionnement d'un même point source. La formulation de Kantorovich, développée pendant la Seconde Guerre mondiale, remplace cette application par un plan de transport qui peut répartir la masse. Cette relaxation linéaire relie le problème à la programmation linéaire et à la recherche opérationnelle. Dans un cadre abstrait, les sources et les destinations deviennent des mesures ; le transport optimal intervient alors aussi en théorie de la mesure et en géométrie riemannienne.

Deux déblais A et B contiennent 4 t et 6 t ; deux remblais X et Y demandent 5 t chacun. Les distances sont de 1 km entre A et X, 4 km entre A et Y, 3 km entre B et X, et 1 km entre B et Y.

Données : offres de 4 t et 6 t ; demandes de 5 t et 5 t ; coût égal à la masse en tonnes multipliée par la distance en kilomètres. Le schéma matérialise les masses transportées par l'épaisseur des traits.

1. A envoie ses 4 t à X par la liaison de 1 km.
2. Il manque alors 1 t à X ; B lui envoie cette tonne par la liaison de 3 km.
3. Les 5 t restantes de B vont à Y par la liaison de 1 km.
4. Le coût total vaut $4\times 1+1\times 3+5\times 1=124\backslash times1+1\backslash times3+5\backslash times1=12$ t·km.

Pour contrôler l'optimalité, appelons x la masse envoyée de A vers X. Les contraintes imposent alors 4 − x de A vers Y, 5 − x de B vers X et 1 + x de B vers Y, avec 0 ≤ x ≤ 4. Le coût est $x+4(4-x)+3(5-x)+(1+x)=32-5xx+4(4-x)+3(5-x)+(1+x)=32-5x$. Il décroît jusqu'à x = 4 : le minimum est donc bien 12 t·km.

Sur un chantier, on mesure les volumes à évacuer et à apporter, puis les distances ou les coûts réels entre zones. Un plan de transport est préférable à l'envoi vers le site le plus proche lorsque plusieurs capacités et plusieurs besoins interagissent.

En logistique, le même modèle répartit des quantités entre entrepôts et points de livraison. Si les trajets passent par un réseau avec des capacités intermédiaires, un modèle de flot à coût minimal est plus adapté ; le plan biparti suffit lorsque seuls comptent les départs, les arrivées et leurs coûts directs.

Pour comparer deux distributions de données, le transport optimal mesure le travail nécessaire pour transformer l'une en l'autre selon un coût choisi. Une distance statistique plus simple est préférable si la position des valeurs ne porte aucune proximité pertinente.

Problème d'affectation. Une affectation associe généralement chaque agent à une seule tâche, souvent avec des quantités unitaires. Le transport autorise des offres et des demandes supérieures à une unité : dans l'exemple, B répartit 6 t entre X et Y.

Plus court chemin. Le plus court chemin cherche un itinéraire entre un départ et une arrivée dans un réseau. Le problème des déblais et des remblais choisit simultanément plusieurs quantités et plusieurs couples source-destination ; quatre distances directes ne se réduisent donc pas à un unique trajet.

Terrassement physique. Les déblais et remblais désignent aussi les terres retirées et ajoutées sur un chantier. Le problème mathématique ne décrit pas toutes les opérations de terrassement : il isole leur répartition sous un coût et des contraintes donnés.

Totaux incompatibles. Dans la version équilibrée, 10 t offertes doivent répondre à 10 t demandées. Si l'offre vaut 10 t et la demande 9 t, aucun plan ne peut satisfaire toutes les égalités. Il faut autoriser un surplus, ajouter un dépôt fictif ou employer un modèle de transport non équilibré.

La solution de Monge peut ne pas exister. Si une source est modélisée par un atome indivisible de 6 t, elle ne peut pas être envoyée à la fois vers X et Y par une application de Monge. Le plan de Kantorovich accepte la répartition de 1 t et 5 t utilisée dans l'exemple.

Un optimum n'est pas forcément unique. Si plusieurs liaisons ont des coûts qui se compensent exactement, des plans distincts peuvent atteindre le même minimum. Un solveur qui retourne un plan optimal n'établit donc pas, à lui seul, son unicité ; il faut examiner les coûts réduits ou les autres solutions admissibles.

La distance n'est qu'un modèle de coût. Deux trajets de même longueur peuvent différer par leur prix, leur durée ou leur capacité. Si ces effets comptent, remplacer la distance par un coût pertinent ou enrichir les contraintes évite de déclarer optimal un plan seulement court.

L'article Deux siècles et demi de transport optimal replace le problème de Monge et ses développements dans une histoire mathématique plus large.

L'article La programmation linéaire approfondit le cadre dans lequel les quantités transportées, le coût et les contraintes deviennent un programme linéaire.

La fiche Monge Gaspard présente le mathématicien qui a formalisé le problème des déblais et des remblais en 1781.