L'ordinateur dans un rôle de répétiteur : - HEC Montréal

L'ordinateur dans un rôle de répétiteur :

un didacticiel interactif pour accompagner l'apprentissage de l'heuristique
SÉP





Roch Ouellet

Service de l'enseignement des méthodes quantitatives de gestion

HÉC-Montréal

3000 chemin de la Côte-Sainte-Catherine

Montréal, H3T 2A7, Canada



roch.ouellet@hec.ca









1. Introduction.

La recherche d'une solution optimale d'un modèle linéaire en nombres
entiers par l'heuristique SÉP est constituée d'un certain nombre d'étapes
similaires, appelées itérations, chacune se décomposant en deux sous-
étapes : la 1re est formée de quelques décisions stratégiques, ainsi que de
la mise à jour de bornes et d'une liste ; la seconde consiste à obtenir une
solution optimale d'un modèle continu dérivé du modèle analysé et très
souvent exige de longs et fastidieux calculs. Or, si seule la première
sous-étape est jugée pertinente dans notre enseignement, on a besoin malgré
tout des résultats de la seconde pour passer à l'itération suivante et
continuer. Dans l'environnement pédagogique traditionnel, on contourne les
difficultés associées à la seconde sous-étape, soit en fournissant à
l'avance l'ensemble des solutions optimales requises pour les divers
modèles qui devront être résolus lors de l'une ou l'autre des itérations,
soit en suggérant à l'étudiant de recourir à un logiciel approprié. Mais
chacune de ces approches présentent des inconvénients majeurs. Le
didacticiel offre une 3e approche, qui consiste à accompagner pas à pas
l'usager dans la 1re sous-étape et à court-circuiter totalement la seconde
en fournissant les solutions optimales une à une, au moment jugé pertinent.
De plus, le didacticiel teste chaque choix ou réponse de l'usager lors de
la 1re sous-étape et, en cas d'erreur, l'usager est averti sans délai par
un message approprié.
2. Description d'un exemple typique.


2.1 Le modèle linéaire.

Nous illustrerons l'approche retenue par le didacticiel à l'aide d'un
exemple, tiré de [1] : il s'agit de résoudre, en utilisant le critère de la
variable la plus distante, le modèle linéaire (P) totalement en nombres
entiers suivant :

Max z = 10x1 + 12x2 + 7x3 + 9x4

sous les contraintes :

3x1 + 2x2 + 4x3 + 5x4 ( 8

2x1 + 4x2 + 1x3 + 6x4 ( 5

xj ( 0 pour j = 1, 2,
3, 4

xj entier pour j = 1, 2,
3, 4




2.2 L'arbre d'énumération.

Rappelons brièvement le principe de l'heuristique SÉP (séparation et
évaluation progressive). En un 1er temps, on résout la relaxation continue
(P0) obtenue du modèle (P) en omettant les contraintes d'intégrité. Une
solution optimale de (P0), de même que la valeur correspondante z0 de la
fonction-objectif, sont reportées dans le n?ud supérieur de l'arbre
d'énumération (voir figure 1). Cette solution, qui est calculée en tenant
compte seulement des contraintes technologiques de (P) et des contraintes
de non-négativité, ne satisfera pas aux contraintes d'intégrité, à moins
d'un hasard faramineux ou de propriétés particulières du modèle (P). C'est
d'ailleurs le cas dans notre exemple : on observe, en effet, que deux
variables ne sont pas entières dans le n?ud-source de la figure 1 :

x1 = 2,4 et x3 = 0,2.

L'idée de base de l'heuristique SÉP consiste à diviser de façon itérative
la région admissible du modèle continu (P0), c'est-à-dire l'ensemble des
solutions qui satisfont à toutes les contraintes de (P0), puis à analyser
une à une les sous-régions résultantes. Dans la version de l'heuristique
SÉP utilisée par le didacticiel et exposée dans [1], on sépare la région
admissible en fonction des valeurs de l'une des variables non entières de
la solution optimale affichée dans le n?ud. Laquelle ? Divers critères
peuvent présider au choix de la variable de séparation. Nous avons retenu
dans l'exemple le critère de la variable la plus distante, qui recommande
d'utiliser une variable qui est éloignée le plus possible de l'entier le
plus près. Ici, il s'agit de x1 . Et nous convenons de diviser la région
admissible de (P0) en trois portions, selon que la variable de séparation
x1 satisfait à l'une ou l'autre des trois conditions suivantes :

x1 ( 2 et 2 < x1 < 3 et x1 ( 3.

La sous-région centrale, celle qui correspond à la condition « 2 < x1 <
3 », ne contient évidemment aucune solution admissible de (P), puisque x1
ne peut y prendre de valeurs entières. Elle peut donc être éliminée a
priori. Restent les deux sous-régions extrêmes, qui devront être analysées
séparément. C'est pourquoi deux branches émergent du n?ud (P0) dans la
figure 1 ; les conditions définissant les sous-régions sont reportées dans
la figure, à côté des branches. Chacune de ces conditions est ajoutée,
tout à tour, au modèle (P0) du n?ud à séparer : il en résulte un nouveau
modèle continu, noté (P1) dans le premier cas et (P2) dans le second.
Puis, ces modèles (P1) et (P2) sont résolus.
Figure 1. Arbre d'énumération de l'exemple de base

















































Dans le n?ud (P2) de la figure 1 associé à la condition « x1 ( 3 », il est
indiqué que cette sous-région ne contient aucune solution admissible. La
solution optimale de (P) appartient donc nécessairement à l'autre sous-
région, celle qui est définie par l'inéquation « x1 ( 2 » . On commence
donc une nouvelle itération, mais cette fois avec le modèle (P1), lequel,
rappelons-le, est obtenu de la relaxation continue (P0) en lui adjoignant
la contrainte « x1 ( 2 » définissant la branche. La variable de séparation
dans ce cas est x3 , et on divise la sous-région en trois portions à partir
des trois conditions suivantes :

x3 ( 0 et 0 < x3 < 1 et x3 ( 1.

Ici encore, la partie centrale est éliminée a priori, car, à l'évidence,
elle ne contient aucune solution entière. Les deux autres définissent des
modèles continus (P3) et (P4). Posant successivement h = 3, puis h = 4, on
résout le modèle (Ph) et on reporte dans le n?ud (Ph) de la figure la
solution optimale obtenue, de même que la valeur correspondante zh de la
fonction-objectif.

On débutera une nouvelle itération avec l'un ou l'autre des n?uds (P3) ou
(P4). Lequel ? Il est raisonnable de traiter en 1er lieu le n?ud qui
offre le meilleur potentiel, tel que mesuré par la fonction-objectif z.
Ici, le hasard a voulu que la valeur optimale de z soit la même, soit 23,
dans les deux n?uds. On choisit alors de façon arbitraire, disons (P3) :
on sépare d'abord (P3), puis (P4). On se retrouve ainsi avec les noeuds
numérotés 5, 6, 7 et 8. Ce dernier sera «éliminé» comme nous le verrons en
section 2.3. Mais finissons-en d'abord avec l'arbre d'énumération de la
figure 1. Le prochain n?ud à séparer sera celui qui offre le meilleur
potentiel parmi ceux qui restent disponibles - en attente selon la
terminologie de la recherche opérationnelle. Il s'agit de (P5), dont la
valeur optimale z5 = 21,5 est supérieure à celles des n?uds 6 et 7. Cette
séparation engendre les n?uds 9 et 10. On poursuit en séparant (P6),
obtenant les n?uds 11 et 12. Puis on arrête ! Pourquoi ?

C'est qu'on est convaincu à ce moment-là d'avoir découvert une solution
optimale de (P). Les motifs qui justifient cette conclusion sont exposés à
la section suivante.




2.3 Le tableau des séparations.

Le tableau des séparations (voir le tableau 1) accompagne l'arbre
d'énumération et indique comment le «gérer». Ce tableau contient une
«ligne» pour chaque séparation effectuée dans l'arbre. Les deux premières
colonnes reprennent les données de l'arbre d'énumération. Mais les trois
autres apportent des informations additionnelles, que nous expliquons
maintenant.

La 5e et dernière colonne énumère la liste des n?uds qui, à la fin de
chacune des itérations, sont en attente d'être séparés. La liste initiale
est formée du seul n?ud (P0). Une fois séparé, (P0) n'est évidemment plus
en attente ; les n?uds candidats pour la liste suivante sont donc (P1) et
(P2). Mais, comme nous l'avons déjà mentionné, il est inutile de
rechercher une solution optimale du modèle (P) dans une sous-région qui ne
contient aucune solution admissible. Nous en avons conclu que le n?ud (P2)
peut être éliminé a priori de la liste des n?uds en attente. Et c'est
pourquoi la seconde liste se résume au n?ud (P1). Après la séparation de
(P1), la liste est formée de (P3) et de (P4) ; ensuite, (P3) est séparé et
enlevé de la liste, les n?uds (P5) et (P6) s'ajoutant à la liste.

La liste des n?uds en attente s'allongeait depuis la séparation de (P1),
mais la tendance s'inverse à partir de celle de (P4). Notons qu'il est
souhaitable qu'il en soit ainsi, sinon le processus risquerait de se
prolonger indéfiniment. Car l'heuristique SÉP s'arrête quand le liste des
n?uds en attente est vide. Dans l'exemple, elle prend fin après la
séparation de (P7).

Tableau 1. Tableau des séparations de l'exemple de base

|Séparation |Valeurs |N?uds | z ( z* ( | Noeuds |
|No N?ud |optimales |éliminés |Erreur! Signet |en attente |
|Contraintes | | |non | |
| | | |défini._Erreur! | |
| | | |Signet non | |
|