Travail d'étude et de recherche

Master $M1$ d'Informatique

Algorithmes dans les graphes : les problèmes de transbordement et de transport

Encadrement : R. Giroudeau(LIRMM)

1. Le problème de transbordement : la plus grande partie des applications de la programmation linéaire fait intervenir des modèles de réseaux ; ceci signifie que la matrice des contraintes a une forme particulière que l'on peut exploiter dans l'algorithme du simplexe. Dans ce ter, vous décriverez cette particularisation de la méthode et vous donnerez par la suite des variantes et des interprétations dans différents types de problèmes. Supposns quíl faille déterminer la façon la plus économique de satisfaire les demandes d'un certain nombre de clients à partir de stocks d'un produit unique qui sont disponibles en cetains points d'un réseau de distribution. Chaque transport donnera lieu à des coûts qui dépendront linéairement des quantités transportées. De façons plus précise soit $R=(X,U,C)$ un réseau dont chaque arc $(i,j)$ a un coût d'utilisation $c_{ij}$. En certains sommets du réseau sont localisés des clients, la demande d'un client située au sommet $i$ sera un entier positif $b_i$ : c'est la quantité que ce client désire recevoir. Pour approvisionner ces clients, nous disposons en certains autres sommets $i$ de stocks $\vert b_i\vert$ du produit demandé par les clients (les stocks disponibles seront représentés par des entiers négatifs). Nous supposerons pour l'instant que la somme des demandes est égale à la somme des stocks disponibles (ou disponibilités). Le but est de satisfaire les demandes.

   Travail à réaliser : Pour ce problème, nous allons utiliser la programmation linéaire et la notion d'arre réalisable. Vous ferez une étude théorique de ce problème.

2. Le problème de transport concerne généralement la distribution d'un certain produit à partir de plusieurs sources vers plusieurs destinations, à moindre coût. Supposons qu'il existe $m$ entrepôts où des marchandises sont stockées, et $n$ point d'achats. Soit $a_1, ~\ldots, a_m$ la quantité disponible dans les entrepôts et $b_1, \ldots, ~b_n$ la demande sur les points d'achats. Le coût unitaire de transport entre un entrepôt $i$ et un point d'achat $j$ est $c_{ij}$ (en particulier si un entrepôt $i$ ne peut subvenir à la demande d'un point d'achat alors $c_{ij}=\infty$). Nous voulons trouver l'affectation optimale qui minimise la somme des coûts de transport entre les entrpôts et les points d'achats.

   Pour ce problème, nous allons utiliser la programmation linéaire pour résoudre ce problème. Dans le but d'éviter utiliser des variables artificielles il est possible de faire appel à des algorithmes qui permettent de déterminer une solution initiale de base :

   • La méthode miniligne,
   • La méthode minicolonne,
   • Le coin Nord-Ouest,
   • La méthode de Balas-Hammer

   Après, cette phase d'amorce il est possible d'optimiser en utilisant la méthode Stepping-Stone (ou Marche-pied).

   Travail à réaliser : Dans cette partie, vous ferez une étude théorique et vous mettrez en oeuvre quelques algorithmes.