next up previous
suivant: L'algorithme de Ford & monter: Application du problème de précédent: Application du problème de

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 :

    $\displaystyle \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 :

    $\displaystyle \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 : 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
\begin{figure}
\leavevmode
\begin{center}
\psfig{figure=res5.eps,height=10.0cm}
\end{center}
\end{figure}


next up previous
suivant: L'algorithme de Ford & monter: Application du problème de précédent: Application du problème de
Bruno Garcia 2000-12-17