Problème de transport simple

Soit $n$ sites de fabrication $F_i$ de $m$ produits $P_k$ devant être acheminés vers $q$ sites de consommation $C_j$ . Chaque couple $(F_i,\,P_k)$ est caractérisé par la capacité de production $f_{ik}$. Réciproquement, chaque couple $(C_j,\,P_k)$ est muni de la demande $d_{jk}$ en produit $P_k$ sur le site $C_j$. Finalement, chaque couple $F_i,\,C_j$ est défini par le coût d'acheminement $c^k_{ij}$ d'un produit depuis son site de fabrication vers le lieu de consommation ainsi que par $l^k_{ij}$ et $u^k_{ij}$, quantités respectives minimales et maximales et par produit devant être délivrées d'un site à l'autre. Ces quantités modélisent des contraintes qui peuvent être du type contractuel (pour les limites inférieures) ou bien refléter la saturation des lignes de transport. Ce problème ultra classique se modélise aisément comme un problème de flot de coût minimum par le réseau suivant.

1. Tout d'abord, chaque site de fabrication $F_i$ est représenté par une source de contribution :
   $$\forall\:i\,\in\,1..n \qquad b(F_i)= \sum_{k=1}^m f_{ik}$$

2. A l'autre bout du réseau, chaque site de consommation est représenté par un puits de contribution :
   $$\forall\:j\,\in\,1..q \qquad b(C_j)= - \sum_{k=1}^m d_{jk}$$

3. Les produits sont, quand-à-eux, représentés par deux ensembles de sommets :
   • Le premier modélise les associations fabricant/produit. Chaque sommet $F_i$ est relié au sommet $fp_{ik}$ si et seulement si il fabrique le produit $P_k$. La capacité de ces arcs est fixée à $f_{ik}$, capacité maximale de fabrication du produit $k$ par $i$.
   • Le second modélise les associations consommateur/produit. Chaque sommet $C_j$ est relié aux sommets $cp_{jk}$ associés aux produits qu'il consomme par des arcs de capacité $d_{jk}$.
   Finalement les arcs de transport relient les sommets $fp_{ik}$ aux sommets $cp_{jk}$ de même produit $P_k$. Leurs capacités sont $l^k_{ij}$ et $u^k_{ij}$ alors que leur coût est fixé à $c^k_{ij}$.

La recherche du flot maximal à coût minimal sur ce réseau garantit l'optimalité de la solution. Il suffit alors de suivre les chaînes de flot pour retracer le trajet des marchandises. La figure suivante montre un cas à trois fabricants, deux produits et deux consommateurs. Il est à noter que la taille du graphe peut devenir très importante avec le nombre d'acteurs mis en jeu.

Figure 5.6: Modélisation du problème de transport simple par un réseau