Chapitre 5. Les modèles de transport

1. Structure d'un fichier : Un exemple Le module « Transportation » de STORM permet de traiter les problèmes de transport. On utilisera un exemple tiré de La recherche opérationnelle, 2e édition de Nobert, Ouellet et Parent. Le problème retenu, « Sporcau », est décrit dans la section 7.4.1, à partir de la page 345. Les données relatives au problème de Sporcau peuvent être regroupées sous forme d'un tableau de transport. La figure 5-1 présente le tableau de transport de Sporcau tel qu'illustré à la page 347 du livre.

C1 C2 C3 C4 C5 Si

1 8 1 5 4 L1 240 5 5 3 6 7 L2 160 2 9 5 9 8 L3 260 Dj 120 130 145 125 140 660

Figure 5-1 Tableau de transport associé au problème de Sporcau

Résoudre ce problème de transport consiste à trouver un plan d'acheminement à coût minimal des laboratoires-origines Li aux centres-destinations Cj. Indiquons maintenant comment résoudre le problème de Sporcau à l'aide de STORM. Tout d’abord,

lancer STORM, puis ouvrir le fichier Sporcaut.dat en cliquant sur l'icône de la barre d'outils WINDOWS et en sélectionnant le répertoire Données\NopWStorm\7e. La zone de travail devrait ressembler à celle de la figure 5-2.

Version du 28/08/02 Chapitre 5. Les modèles de transport Page 5.2

Figure 5-2 La fenêtre décrivant le tableau de transport de Sporcau

- Les lignes L1, L2 et L3 correspondent aux laboratoires-origines et les colonnes C1, C2, C3, C4 et C5 aux centres-destinations. Les noms des lignes et des colonnes peuvent être modifiés. De plus, on peut inverser lignes et colonnes si on le juge approprié, par exemple pour améliorer la visibilité des données : ainsi, lorsque le problème comporte 6 origines et 10 destinations, le tableau dépasse les dimensions de la fenêtre de travail ; cependant, le tableau «transposé», qui comporte 10 lignes et 6 colonnes, entre tout entier dans la fenêtre.

- Le coût unitaire de transport associé à chaque couple origine-destination occupe la cellule correspondante. Par exemple, il en coûte 3 centaines de dollars pour transporter une tonne de produits de L2 à C3. Dans le présent exemple, il est possible d’expédier de tout laboratoire-origine à tout centre-destination. Lorsque ce n'est pas le cas, on inscrit un point (.) dans les cellules concernées, ce qui correspond à un coût unitaire infini.

- Dans la colonne SUPPLY, on retrouve les quantités disponibles à chaque laboratoire-origine L1, L2 et L3.

- La ligne DEMAND contient les demandes à satisfaire par les centre-destinations C1, C2, C3, C4 et C5.

- Aucune donnée n'est acceptée dans les cellules de la ligne ou de la colonne dénommées DUMMY. Les rangées DUMMY servent en fait à partitionner le tableau et à indiquer la possibilité qu’une origine ou une destination fictive soit ajoutée par STORM lorsque le problème n'est pas équilibré. Un exemple de problème non équilibré est présenté à la section 4.

Centres-destinations Quantité

disponible

Laboratoires- origines

Demande

Version du 28/08/02 Chapitre 5. Les modèles de transport Page 5.3

2. Résolution d'un fichier pré-existant

Pour résoudre le problème de transport associé au fichier Sporcaut.dat, cliquer sur l'icône de la barre d'outils STORM, ou encore sur le menu Process et la commande Execute de ce menu. La boîte de dialogue affichée devrait ressembler à celle de la figure 5-3.

Figure 5-3 La boîte de dialogue « Transportation : Report Options »

La section « Starting Solution » de la boîte de dialogue « Transportation : Report Options » permet de spécifier la procédure de calcul pour la solution de base admissible initiale. STORM offre le choix entre les 4 méthodes heuristiques suivantes : - coin nord-ouest (Northwest Corner); - pénalités (Vogel's Method); - coûts minimaux (Matrix Minimum); - variante de la méthode des coûts minimaux (Row Minimum). STORM numérote 1 la solution de base admissible obtenue selon la méthode retenue. La 2e section de la boîte de dialogue offre le choix entre aller directement à une solution optimale, « Go to Optimal Solution », ou aller à la solution de base résultant de la prochaine itération, « Go to Next Solution ». La 3e section de la boîte de dialogue est active seulement après que l’on ait cliqué sur les boutons « Go to Optimal Solution » ou « Go to Next Solution ». Cette section fonctionne essentiellement comme la section correspondante de la boîte de dialogue « Integer Programming: Report Options » (voir la section 4 du chapitre 2). Pour obtenir une description de la solution de base courante, il suffit de cocher les cases « Summary » ou « Detail » de la section « Generate Reports », puis de cliquer sur OK. Les figures 5-4 et 5-5 ci-dessous donnent les rapports détaillé et sommaire associés à une solution optimale de Sporcau.

Version du 28/08/02 Chapitre 5. Les modèles de transport Page 5.4

La 4e section, « Show Tableau », de la boîte de dialogue permet d’afficher le tableau de transport associé à la solution de base courante. La figure 5-6 ci-dessous donne le tableau de transport associé à une solution optimale de Sporcau. Cette section est active seulement si le problème de transport étudié comporte un maximum de 6 origines et un maximum de 6 destinations. 3. Rapports et interprétation des résultats Le rapport détaillé Le rapport détaillé décrit la solution de base courante. La figure 5-4 donne le rapport détaillé associé à une solution optimale du problème de Sporcau. On y trouve, pour chaque couple (Li ; Cj) : • le nombre d’unités expédiées du laboratoire-origine Li au centre-destination Cj (Amount) ; • le coût unitaire de transport entre Li et Cj (Unit Cost) ; • le produit des deux données précédentes (Cell Cost) ; • le coût marginal de la variable xij associée (Reduced Cost). Lorsqu’un coût marginal est suivi d'un astérisque, la variable xij associée est variable de base dans la solution courante. L’avant-dernière ligne donne le coût total de la solution courante ; et la dernière, le nombre d’itérations. Noter que STORM compte l’obtention du tableau initial comme une itération ; que le nombre d’itérations pour obtenir une solution optimale particulière dépend de la méthode heuristique retenue pour calculer la solution de base initiale. Le rapport sommaire Le rapport sommaire fournit les mêmes informations que le rapport détaillé, en omettant toutefois la colonne Reduced Cost, ainsi que les lignes correspondant aux variables hors-base dans la solution courante. La figure 5-5 donne le rapport sommaire associé à une solution optimale du problème de Sporcau.

Version du 28/08/02 Chapitre 5. Les modèles de transport Page 5.5

Figure 5-4 Rapport détaillé d’une solution optimale de Sporcau

Figure 5-5 Rapport sommaire d’une solution optimale de Sporcau

Version du 28/08/02 Chapitre 5. Les modèles de transport Page 5.6

Le tableau de calcul Le bouton « Show Tableau », qui permet d’obtenir le tableau de calcul associé à la solution de base courante, est actif seulement si le problème de transport étudié comporte un maximum de 6 origines et un maximum de 6 destinations. La figure 5-6 présente le tableau de calcul associé à une solution optimale du problème de Sporcau. Le coût unitaire de transport de chaque couple origine-destination occupe le coin supérieur gauche de la case correspondante. Dans le coin inférieur droit d’une case (i ; j) apparaît, sur fond noir, la valeur de la variable xij s’il s’agit d’une case de base, et, sur fond gris, le coût marginal de la variable xij s’il s’agit d’une case hors-base. Le tableau de la figure 5-6 est optimal puisque le problème traité en est un de minimisation et que le coût marginal de chaque variable hors-base est non négatif. Dans les cases de la dernière colonne, « U(I) \ SUPPLY », on retrouve les valeurs des variables duales ui dans le coin supérieur gauche ainsi que les quantités totales expédiées à partir des différents laboratoires-origines. De même, dans les cases de la dernière ligne, « V(J) DEMAND », apparaissent dans le coin supérieur gauche les valeurs des variables duales vj et les quantités totales reçues par les différents centres-destinations.

Figure 5-6 Tableau optimal de Sporcau

En recourant au bouton « Go to Next Solution », on peut connaître les solutions de base intermédiaires et les tableaux de calcul correspondants, pourvu que la taille du problème traité ne dépasse pas les limites mentionnées précédemment. Les figures 5-7 et 5-8 donnent, la 1re, le rapport détaillé, la seconde, le tableau de calcul associés à la solution initiale du problème de Sporcau quand on retient la méthode des coûts minimaux. (On comparera la figure 5-8 avec le tableau 7-33 de La recherche opérationnelle.)

Version du 28/08/02 Chapitre 5. Les modèles de transport Page 5.7

Figure 5-7 Solution initiale à partir de la procédure des coûts minimaux

Figure 5-8 Tableau de calcul associé à une solution de base non optimale

Version du 28/08/02 Chapitre 5. Les modèles de transport Page 5.8

La solution de base représentée à la figure 5-8 n’est pas optimale et STORM affiche le cycle de changement pour la prochaine itération, en inscrivant des signes « + » et « − » dans les cases formant ce cycle ; de plus, la variable entrante x31 est indiquée par un signe « + » de couleur verte dans la case correspondante, la variable sortante x23, par un signe « − » de couleur verte. Pour obtenir le tableau de calcul associé à la solution de base résultant de la prochaine itération, cliquer sur le bouton « Next » au bas de la boîte de dialogue « Process Monitor ». On revient alors à la boîte de dialogue « Transportation : Report Options » ; il suffit alors de cliquer sur « Go to Next Solution », puis sur « Show Tableau ».

4. Équilibrage d'un problème de transport Lorsqu'un problème de transport n'est pas équilibré, STORM s'occupe d'ajouter une origine fictive ou une destination fictive selon le cas. À titre d'exemple, prenons le problème PRO7-15d tiré de Problèmes résolus de recherche opérationnelle. Pour résoudre ce problème de transport, il faut d'abord ajouter une usine fictive dont la capacité est de 45 unités pour équilibrer le problème. La figure 5-9 présente le tableau optimal résultant lorsque la solution de base initiale est obtenue par la méthode du coin nord-ouest. Une usine fictive dénommée DUMMY a été ajoutée.

Figure 5-9 Ajout d’une origine fictive pour équilibrer un problème

Version du 28/08/02 Chapitre 5. Les modèles de transport Page 5.9

5. Contraintes sur les données numériques

Ni le nombre d’origines, ni le nombre de destinations ne doivent dépasser 30. Les quantités disponibles aux origines et les demandes à satisfaire aux destinations, c'est-à-dire les données de la colonne SUPPLY et de la ligne DEMAND, doivent être des nombres entiers. Si le problème étudié comporte des valeurs non entières pour les disponibilités ou les demandes, il faut les convertir en nombres entiers : par exemple, lorsque la quantité disponible d'un produit aux différentes origines est mesurée en tonnes à une décimale près, il faut ré-exprimer les données en dixièmes de tonnes - ou encore en kilogrammes - afin que les disponibilités soient des nombres entiers (il faut ajuster les coûts unitaires pour tenir compte de la conversion, en les multipliant par 10 - ou par 1000).

6. Saisie des données

Nous indiquons maintenant comment créer une feuille de données STORM pour le module de transport. Convenons d’utiliser à nouveau le tableau de transport de Sporcau décrit à la figure 5-1.

Tout d’abord, lancer STORM, puis cliquer sur l'icône de la barre d'outils WINDOWS. La boîte de dialogue « Module List » s’affiche. Sélectionner le module « Transportation » et cliquer sur OK. La boîte de dialogue « Transportation : Model Parameters » affichée devrait ressembler à celle de la figure 5-10.

Figure 5-10 La boîte de dialogue « Transportation : Model Parameters » La boîte de dialogue « Transportation : Model Parameters » sert à préciser les caractéristiques générales du problème et indiquera à STORM les dimensions de la feuille de saisie. La barre d'état, située au bas de l'écran, donne les instructions sur les paramètres à entrer. Initialement (voir figure 5-10), elle affiche « Enter a descriptive title for this data ».

Version du 28/08/02 Chapitre 5. Les modèles de transport Page 5.10

Écrire le titre du modèle, puis entrer le nombre d'origines (Number of Rows), ainsi que le nombre de destinations (Number of Columns). L'écran devrait ressembler à celui de la figure 5-11.

Figure 5-11 La boîte de dialogue « Transportation : Model Parameters » une fois complétée L'objectif du problème considéré consistant à minimiser le coût total, il n'est pas nécessaire de modifier la valeur par défaut « MIN » de la case « Objective type ». De plus, à moins que les quantités acheminées ne soient soumises, sur certaines routes, à des restrictions maximales et que l'on veuille fournir cette information à STORM, on laissera inchangée la valeur par défaut « UNCP » de la case « Capacitated ». Finalement, dans le cas d’un problème non équilibré, on laissera également inchangée la donnée par défaut « NONE » de la case « Bounds » à moins que l'on souhaite ajouter des contraintes sur les quantités minimales expédiées à partir d'une origine ou vers une destination. La figure 5-11 décrit donc correctement les paramètres du problème de Sporcau. Pour continuer, cliquer sur OK. La feuille de saisie de données de dimension voulue et dont les cellules contiennent les valeurs par défaut s'affiche alors à l'écran (voir figure 5-12).

Figure 5-12 Feuille de saisie avec valeurs par défaut

Version du 28/08/02 Chapitre 5. Les modèles de transport Page 5.11

La barre d'état en bas de l'écran indique la nature des données attendues par STORM dans la cellule qui est surlignée. Elle donne également un message d’erreur lorsque la donnée fournie par l’usager n’est pas acceptable. On entrera les diverses données du problème dans n’importe quel ordre, jusqu’à ce que la feuille de saisie soit identique à celle représentée à la figure 5-2. Il suffit évidemment de modifier les valeurs par défaut qui ne conviennent pas. Rappelons (voir section 5.5) que les valeurs dans les cellules de la colonne SUPPLY et la ligne DEMAND doivent être des nombres entiers. Il est recommandé de donner des noms mnémotechniques aux origines (ROW 1, ROW 2, …) et aux destinations (COLUMN 1, COLUMN 2, …). Un nom peut comprendre jusqu'à 10 caractères (lettres, chiffres, certains caractères spéciaux). STORM accepte les minuscules, mais il les affiche en majuscules. Les accents sont acceptés, sauf au début et à la fin du nom.

Une fois le modèle complété, cliquer sur l'icône , ou encore sur le menu File puis sur la commande Save As… de ce menu, pour enregistrer le fichier UNTITLED1 sous un nouveau nom. Pour plus de précisions sur la procédure de sauvegarde des fichiers, se référer à la section 5 du chapitre 1. Noter finalement que le seul paramètre modifiable directement à partir de la boîte de dialogue « Transportation : Model Parameters » est l'objectif du problème. Pour augmenter ou diminuer le

nombre d'origines, utiliser les icônes et : STORM ajustera automatiquement la valeur du paramètre « Number of Rows » de la boîte de dialogue « Transportation : Model Parameters ».

De même, pour augmenter ou diminuer le nombre de destinations, utiliser les icônes et .