Les hypothèses

On considère un graphe orienté quelconque de n points. On appelle source un noeud du graphe qui fournit des marchandises, et puits un noeud qui demande des marchandises. On suppose que la somme du nombre de marchandises fournies est égal à la somme du nombre de marchandises demandées. De plus, chaque arc de graphe possède un coût.

On veut transporter les marchandises des sources aux puits en suivant bien sûr les arcs du graphe. On appelle solution toute façon de réaliser ce transport. S'il en existe au moins une, on désire également déterminer la solution la plus économique.

Considérons l'exemple d'un graphe de 7 noeuds numérotés ayant pour sources 6 et 7, et pour puits 3, 4 et 8. 6 fournit 9 marchandises et 7 fournit 15 marchandises. 3 demande 6 marchandises, 4 demande 10 marchandises et 5 demande 8 marchandises. Le graphe et le côut de ces arcs sont décrits par la figure 1.1.

 

Figure 1.1: Le graphe avec le coût de tous ces arcs

Une solution quelconque du problème peut être décrite par la figure 1.2.

 

Figure: Les arcs utilisés avec le nombre de marchandises transitant sur celles-ci

Le coût de cette solution est : $2 \times 18 + 1 \times 28 + 7 \times 5 + 2 \times 44 + 1 \times 38 + 6 \times 98 + 15 \times 59 = 1698$.
Ce n'est pas une solution optimale.