Optimisation entière dans un réseau de transport

Sujet proposé par Marie-Pierre Béal

beal@monge.univ-mlv.fr

Préambule

Les réseaux de transport sont une classe de problèmes d'optimisation qui peuvent se modéliser sous forme de graphes orientés, où chaque arc a un coût et chaque noeud a un poids. Ces problèmes peuvent se rencontrer dans le domaine de la logistique, pour la planification, la gestion de stocks, etc. Une solution au problème de réseau consiste à calculer pour chaque arc ij du graphe une quantité tex2html_wrap_inline137 de produit à transporter du noeud i au noeud j de telle sorte que pour chaque noeud la quantité de produit entrante moins la quantité de produit sortante soit égale au poids du noeud. Cette condition s'appelle la condition de flot. On prendra ici des poids entiers et les quantités seront aussi des entiers. On parlera dans ce cas de solution entière. Une solution optimale pour le réseau est une solution qui minimise le coût total du transport. De nombreux problèmes d'optimisation peuvent se ramener à un problème de réseau de transport, moyennant parfois un encodage habile. On donne plus loin quelques exemples avec leur modélisation sous forme de réseau. Le projet consiste à implémenter une méthode, dite du simplexe entier, qui permet d'obtenir une solution optimale entière lorsqu'il en existe une. La méthode consiste à calculer pour le graphe un arbre recouvrant qui est le support d'une solution, et à passer rapidement d'un arbre recouvrant à un arbre meilleur. Nous décrivons ci-dessous le principe de l'algorithme. On pourra se reporter à [1] pages 291 à 317 pour plus de détails. Des exemples d'application sont donnés dans la troisième section.

Détail du sujet

   figure13

Figure 1: Un réseau de transport

Nous donnons tout d'abord quelques notations pour décrire l'algorithme. Si i est un noeud, on notera tex2html_wrap_inline145 le poids d'un noeud (un entier). Le réseau est bien constitué si la somme des poids des sommets est nulle et on ne considèrera que des réseaux de ce type. Un arc du noeud i vers le noeud j est noté ij. Le coût de l'arc ij est noté tex2html_wrap_inline155 (les coûts ne sont pas forcément entiers ni forcément positifs). Une solution est constituée des valeurs positives ou nulles tex2html_wrap_inline137 pour chaque arc ij. Le coût total d'une solution est la somme pour tous les arcs ij des quantités tex2html_wrap_inline163 . Un exemple de réseau est donné dans la figure 1a, où les coûts sont soulignés et les poids de chaque noeud sont donnés sur le noeud lui-même. La figure 1b donne une solution dite solution arbre. Une solution arbre est une solution dont les valeurs sont nulles en dehors des arcs d'un arbre recouvrant. Un arbre recouvrant est une partie du graphe telle que, si on oublie l'orientation des flèches, elle constitue un graphe sans cycle et reliant tous les noeuds. L'arbre recouvrant est donné sur la figure fig:resTb et les valeurs des solutions sur les arcs de l'arbre sont indiquées.

Nous allons tout d'abord supposer que nous disposons d'une solution arbre. Elle est alors entière. Nous verrons plus loin comment en trouver une s'il en existe une. On note T l'arbre recouvrant. L'algorithme consiste à itérer les étapes suivantes :

On montre (par de l'algèbre linéaire élémentaire) que lorsqu'il n'existe plus d'arc entrant, la solution arbre obtenue est optimale (y compris parmi les solutions non arbres et non entières). Une solution optimale arbre pour l'exemple suivi est donnée figure fig:resTf.

Plusieurs problèmes peuvent théoriquement se présenter lors de l'exécution. On peut, au cours d'une itération, trouver un arc entrant, puis un arc sortant tel que tex2html_wrap_inline197 soit nul. La nouvelle solution n'améliore pas la précédente dans ce cas. Ce cas est dit dégénéré. Lorsqu'un tel cas se présente on le traite comme le cas non dégénéré en espérant que l'on ne stagnera pas trop longtemps. Les cas de cyclage ne sont pas exclus mais ils sont très rares. On ne s'en préoccupera pas. Il existe des stratégies pour les éviter. Enfin il reste à trouver une solution arbre de départ pour pouvoir enclencher la recherche d'une solution optimale. Cette étape se déroule de la façon suivante :

Exemples d'application

Un premier exemple d'application est celui de l'assignation. Un directeur de département d'informatique répartit les cours à assurer par les enseignants. Il y a quatre cours : algorithmique, logique, compilation et système, et quatre professeurs P1, P2, P3 et P4. Chaque professeur va donner un cours. Le directeur évalue par une note de 0 à 20 l'aptitude de chaque professeur pour chaque cours.

displaymath223

Son objectif est d'attribuer chaque cours à un unique professeur de telle sorte que la somme totale des évaluations correspondantes soit maximale. Le problème de l'assignation se modélise sous forme d'un réseau de transport (voir [1] page 341). On remarquera que le fait que la solution optimale obtenue par application de l'algorithme soit entière est essentiel. Le directeur ne souhaite pas qu'un tiers d'un cours soit donné par un professeur et les deux tiers restants par un autre.

Un autre exemple d'application est le problème des serviettes de table. Le problème des serviettes de table peut s'énoncer de la façon suivante : un restaurateur prévoit sur une période de n jours ses besoins en serviettes de table. Il connaît à l'avance le nombre tex2html_wrap_inline233 de serviettes qui seront utilisées le jème jour. Le restaurateur peut acheter des serviettes neuves (x francs par serviette) ou faire laver les serviettes usagées. La blanchisserie propose deux services de nettoyage, un service rapide (r francs par serviette, retour q jours après) et un service plus lent (l francs par serviette, retour p jours après). Naturellement, on a x > r > l et p > q.

On suppose que le restaurateur ne dispose au départ d'aucune serviette. Il devra donc commencer par en acheter quelques unes. Le restaurateur cherche à élaborer une stratégie de gestion pour satisfaire ses besoins sur n jours en minimisant ses dépenses.

Une solution optimale peut être trouvée en modélisant le problème sous la forme d'un réseau de transport. Cette solution fournira au restaurateur les quantités journalières de serviettes qui devront être respectivement achetées, lavées en service rapide et lavées en service lent. Nous allons décrire la modélisation avec les valeurs suivantes pour les constantes n=10, p=4, q=2, x=8, r=3, l=1. Enfin les besoins pour les dix jours sont :

displaymath224

Le graphe de la figure 1 représente un réseau adapté au problème.

   figure59

Figure 2: Le réseau des serviettes de table

Les poids sont indiqués à côté des noeuds. Le jème état situé à gauche en partant du haut représente la situation à la fin du jour j, le nombre de serviettes usagées étant égal à tex2html_wrap_inline233 . Le jème état de droite représente la demande au début du jour j. Les états de gauche sont des noeuds de poids négatifs, ceux de droite (magasin et inventaire non compris) ont des poids positifs. Chaque serviette usagée peut être envoyée au lavage service rapide (arcs horizontaux de coût r), au lavage service lent (arcs penchés de coût l), ou être gardée en attente (arcs verticaux de coût nul). Enfin les serviettes peuvent être achetées (arcs provenant de l'état magasin de coût x). A la fin du dixième jour, le reliquat de serviettes usagées est envoyé à l'inventaire tout comme le reliquat du magasin. On suppose qu'aucun client ne vole de serviette et donc que ce qui retourne à l'inventaire est égal au stock initial du magasin. Le réseau a ainsi un vecteur de poids de somme nulle.

Travail demandé

Le travail demandé consiste à implémenter l'algorithme décrit. Il n'est pas exigé de tenir compte des cas particuliers rares. Une bonne implémentation doit permettre des itérations rapides. Il faut pour cela pouvoir passer rapidement d'un arbre recouvrant à un autre. Ceci peut se faire en essayant de ne pas recalculer tout l'arbre recouvrant et tous les prix. Une implémentation adaptée est décrite en [1]. Il n'est pas demandé (ni interdit) de suivre cette implémentation. Il existe aussi des stratégies sur les choix des arcs entrant et sortant pour améliorer les temps de calcul et éviter les cycles.

Le programme sera validé par des tests sur des exemples de réseaux. Il est demandé de traiter un petit graphe : par exemple celui décrit figure 1, et de calculer une solution optimale pour le problème des serviettes de table. Vous pouvez résoudre le problème de l'assignation sur des tables plus grosses et comparer les temps de calcul. Vous pourrez aussi tester votre programme sur d'autres exemples d'application de votre choix.

Références

1
Vasek Chvátal, Linear Programming, Freeman, 1983.


Fri Dec 6 17:15:50 MET 1996