2 - Examen corrige

La recherche opérationnelle et l'informatique : aller plus loin avec les
didacticiels interactifs





Roch Ouellet, MQG, HÉC-Montréal

roch.ouellet@hec.ca










1. Introduction.

L'ordinateur est de plus en plus utilisé dans l'enseignement. Mais
souvent, il joue un rôle de super-calculatrice, ou encore il sert
simplement à archiver et projeter des documents. Ces usages sont
pertinents sans doute, mais on peut aller plus loin avec l'ordinateur. Il
est possible, en effet, de confier des tâches «didactiques» à
l'ordinateur.

L'atelier visait à illustrer cette dernière affirmation en présentant deux
didacticiels utilisés dans l'enseignement de la recherche opérationnelle
dans une École de gestion. L'un reproduit l'algorithme du transport
classique, l'autre, la méthode SÉP (Branch & Bound) dans son application à
la résolution de modèles linéaires en nombres entiers. Seul le premier
sera décrit dans le présent texte.

L'apprentissage d'un algorithme se fait souvent par la résolution
d'exemples numériques simples. Notre didacticiel accompagne pas à pas
l'étudiant dans cet apprentissage par la pratique. Il effectue également
certains calculs numériques plus lourds, qui présentent peu ou pas
d'intérêt pédagogique.

Notre didacticiel teste immédiatement chacun des choix et chacune des
valeurs numériques de l'étudiant, puis donne une message d'erreur approprié
ou amène l'usager à la prochaine étape.

Le plus souvent, le néophyte qui fait ses premières armes avec un
algorithme donné se pratique avec des exemples numériques simples : dans
l'encadrement traditionnel, s'il commet une erreur, il ne peut le détecter
et il continue jusqu'à la fin de l'algorithme (l'obtention d'une solution
optimale dans le cas de l'algorithme du transport) ou jusqu'à ce qu'il se
retrouve dans un cul-de-sac. S'il consulte la solution officielle de
l'exercice, il lui est généralement difficile de déterminer précisément où
il s'est trompé. Il est en effet impossible de donner toutes les étapes et
tous les résultats intermédiaires dans une solution-papier... Le
didacticiel, lui, peut arrêter l'usager immédiatement après l'étape où est
commise l'erreur et donner un message qui indique le type de l'erreur.
Donc beaucoup de moins temps perdu - et de frustation - pour l'étudiant.

Un exposé succinct de l'algorithme du transport




2.1 Énoncé de l'exemple numérique


L'algorithme du transport sera illustré à l'aide d'un exemple numérique
simple tiré de [1], page 358. Une entreprise fabrique un certain produit
dans 3 laboratoires Li (i = 1, 2, 3) ; le produit est ensuite expédié à
des centres de distribution Cj (j = 1, 2, 3, 4, 5).

Le tableau 1 ci-dessous donne les coûts unitaires de transport cij des
laboratoires aux différents centres ; le tableau 2, les quantités Si
disponibles en chaque laboratoire Li , de même que les quantités Dj
requises en chaque centre Cj . On notera que l'offre totale (la somme des
Si ) est égale à la demande totale (la somme des Dj) : on dit que ce
problème de transport est équilibré.


|Tableau 1. Coûts unitaires de transport |
| |C1 |C2 |C3 |C4 |C5 |
|L1 |1 |8 |1 |5 |4 |
|L2 |5 |5 |3 |6 |7 |
|L3 |2 |9 |5 |9 |8 |


|Tableau 2. L'offre et la demande |
| |L1 |L2 |L3 |Total |
|Laboratoire | | | | |
|Li | | | | |
| Offre Si |240 |160 |260 |660 |
| Centre Cj |C1 |C2 |C3 |C4 |C5 | |
| Demande Dj|120 |130 |145 |125 |140 |660 |


L'objectif est d'acheminer à coût minimal les 660 unités des 3 laboratoires
aux 5 centres.






2.2 Le tableau de transport


Le problème de transport énoncé à la section précédente se modélise comme
un modèle linéaire continu. L'algorithme du simplexe permet donc d'en
calculer une solution optimale. Cependant, il existe une approche plus
efficace, qui utilise les caractéristiques particulières des problèmes de
transport. Traditionnellement, les calculs afférents à la résolution d'un
problème de transport, lorsqu'ils sont faits à la main, sont effectués sur
un gabarit (voir tableau 3 pour notre exemple) appelé tableau de
transport : ce tableau comporte une ligne pour chaque laboratoire-origine
Li et une colonne pour chaque centre-destination Cj ; de plus, des rangées
marginales (colonne de droite et ligne du bas dans le tableau 3) décrivent
l'offre et la demande. Le coût unitaire cij de Li à Cj est reporté dans
coin supérieur droit de la case (i ; j) associée.




2.3 Une solution de base admissible initiale


Le tableau 3 donne une solution admissible initiale du problème de
transport exposé aux tableaux 1 et 2. Cette solution recommande, entre
autres, que :

o des 240 unités disponibles en L1 , 120 soient expédiées à chacun des
centres C1 et C2 ;

o 120 des 130 unités requises en C2 proviennent de L1 et les 10 autres, de
L2 .

Mathématiquement, la solution concrète décrite au tableau 3 est représentée
par la solution algébrique x, où xij dénote le nombre d'unités expédiées du
laboratoire-origine Li au centre-destination Cj : dans notre exemple
numérique, x11 = 120 et x12 = 120 et x22 = 10, etc. Par convention, la
variable xij est nulle lorsqu'aucun nombre n'est reporté dans la case
(i ; j) : par exemple, x13 = x14 = x21 = 0... Le coût total z associé à
une solution x s'obtient comme le produit scalaire des coûts unitaires cij
et des quantités expédiées xij . Le coût total associé à la solution du
tableau 3 s'élève à 3 795 unités monétaires :

z = (i (j cij xij = (1(120) + (8(120) + (5(10) + ( + (8(140) = 3
795.


|Tableau 3. Solution de base admissible initiale |
|Origine |Destination |Offre |
| |C1 |C2 |C3 |C4 |C5 | |
| | | 1 | | 8 | | 1 | | 5 | |4 | |
|L1 | | | | | | | | | | | |
| |120 |120 | | | |240 |
| | | 5 | | 5 | | 3 | | 6 | |7 | |
|L2 | | | | | | | | | | | |
| | |10 |145 |5 | |160 |
| | | 2 | | 9 | | 5 | | 9 | |8 | |
|L3 | | | | | | | | | | | |
| | | | |120 |140 |260 |
|Demande |120| |130| |145| |125| |140| |660 |


La solution initiale du tableau 3 a été obtenue à l'aide d'une heuristique
appelée méthode du coin nord-ouest, la terminologie provenant du fait que
la 1re attribution se fait dans la case (1 ; 1) associée à la route L1 - C1
et située en haut et à gauche (le coin nord-ouest sur une carte
géographique). Pour les attributions subséquentes, on se déplace d'une
case vers la droite ou vers le bas. À chaque étape, on reporte dans la
case courante la valeur maximale permise par la structure du problème :
ainsi, au départ, on se place dans la case (1 ; 1) et on recommande
d'expédier 120 unités de L1 à C1 puisque cette valeur représente la
quantité maximale requise en C1 ; ensuite, la colonne 1 étant saturée (la
demande en C1 est comblée), on se déplace à la case adjacente (1 ; 2)
située à droite et on attribue à la route L1 - C2 les 120 unités du
laboratoire L1 non encore utilisées. Cette fois, c'est la ligne 1 qui
devient saturée (toutes les unités disponibles en L1 ont déjà été
attribuées) : on descend et on s'en va à la case adjacente (2 ; 2)...

La solution initiale du tableau 3 possède certaines propriétés
structurelles qu'on résume en disant qu'il s'agit d'une solution de base.
La théorie mathématique garantit qu'un problème de transport équilibré
admet toujours une solution optimale qui est une solution de base.
L'algorithme du transport s'appuie sur cette propriété : le c?ur de cet
algorithme consiste à transformer une solution de base admissible en une
nouvelle solution de base admissible dont le coût total soit inférieur ou
égal à celui de l'ancienne solution.
Un aspect essentiel des solutions de base est la répartition des mn cases
du tableau de transport en deux catégories : m + n ( 1 cases de base et
(mn ( m ( n + 1) cases hors base, où m dénote le nombre de lignes-origines
et n, le nombre de colonnes-destinations. De plus, la variable xij
associée à toute case (i ; j) hors base est nulle par définition. Dans la
solution de base du tableau 3, les 3+5(1 = 7 cases de base sont celles où
sont reportées les quantités à expédier ; les 15(7 = 8 autres sont hors
base et l'absence de valeur reportée implique que la variable xij
correspondante est nulle.




2.4 Comment améliorer une solution de base : le cycle de changement


L'algorithme du transport cherche à «améliorer» la solution de base
courante, à diminuer la valeur de z associée. Techniquement, on calcule
d'abord l'impact sur z de la décision de forcer une case hors base à
devenir case de base ; puis, on choisit une des cases hors base qui diminue
z au rythme le plus rapide.

Considérons, à titre d'exemple, la case hors base (1 ; 3) du tableau 3 ;
et convenon