Le problème du transbordement, Le problème du débit maximal

Cette séance de cours présente le problème du débit maximal, motivé par l'époque de la guerre froide, où l'armée américaine a étudié le réseau ferroviaire de Moscou à Berlin. L’objectif est de déterminer le nombre maximum de trains pouvant être transportés entre ces villes. La séance de cours explique comment calculer le débit maximal à travers un réseau en analysant les capacités des arcs. Il passe ensuite au problème de transbordement, dans le but de minimiser le coût total du transport en optimisant le flux atteignant la destination. Le concept de circulation est introduit, et la séance de cours détaille la formulation du problème de transbordement, y compris l'ajout d'un arc artificiel pour suivre le flux. Les contraintes sur la conservation des flux et les capacités d'arc sont discutées, conduisant à la représentation mathématique du problème.