Problème des gants
En recherche opérationnelle, le problème des gants[1] (aussi appelé le problème des préservatifs[2]) est un problème d'optimisation utilisé comme exemple de ce que la solution la moins coûteuse conduit souvent à une augmentation importante du temps opérationnel, alors que la solution la plus rapide n'amène qu'à une augmentation modérée du coût[3].
Énoncé du problème[modifier | modifier le code]
M docteurs doivent chacun examiner les mêmes N patients, en portant des gants pour éviter la contamination. Chaque gant peut être réutilisé indéfiniment, mais la même face d'un gant ne peut être en contact qu'avec une seule personne. Les gants peuvent être portés les uns sur les autres, et retournés.
Le nombre minimum de gants nécessaires, G(M, N) est alors donné par :
- G(M, N) = M + N − 2 si M et N ≥ 2
- G(M, 1) = M
- G(1, N) = N
- G(1, 1) = 1
Procédure détaillée[modifier | modifier le code]
Une approche naïve est d'associer un gant à chaque couple médecin-malade, obtenant donc G(M, N) = MN. Mais en exploitant les deux faces des gants, et le fait qu'il n'est pas nécessaire de les utiliser simultanément, ce nombre peut être significativement réduit.
En attribuant à chaque personne (patient ou médecin) son gant (soit M + N gants en tout), on obtient une bien meilleure solution : à chaque rencontre, le médecin enfile son gant, puis par dessus le gant du patient ; ainsi, chaque personne ne touche jamais qu'une surface de son propre gant (intérieure pour les médecins et extérieure pour les patients); cette solution est meilleure que la précédente dès qu'il y a plus d'un médecin et un patient.
La durée totale des examens dans ce schéma est K · max(M, N), où K est la durée de chaque examen individuel ; c'est la même durée que dans le version naïve à MN gants. Dans ce cas, disposer de plus de ressources ne fait pas gagner de temps.
Il est possible d'optimiser le nombre G(M, N) par une distribution initiale asymétrique des gants ; le meilleur schéma est :
- Le médecin # 1 porte N gants les uns sur les autres, visite les N patients et leur laisse le gant (extérieur) qu'il a utilisé.
- Les médecins # 2 à (M − 1) portent chacun leur gant, et le recouvrent du gant laissé au patient pour chaque visite.
- Le dernier médecin # M enfile le gant du premier patient (ne touchant que sa face stérile) puis le recouvre successivement des gants des autres patients.
Cette méthode utilise (1 · N) + ((M − 1 − 1) · 1) + (1 · 0) = M + N − 2 gants, et il n'est pas possible de faire mieux.
Le temps nécessaire correspond alors à :
- N visites successives pour mettre les gants,
- max(M − 2, N) visites intermédiaires car elles peuvent être faites en parallèle,
- et les N visites finales.
Donc un temps de K · (2N + max(M − 2, N)) ; ainsi gagner deux gants peut allonger le temps jusqu'à un facteur 3 ; selon le critère préféré, la procédure d'optimisation est très différente.
Autres facteurs[modifier | modifier le code]
L'énoncé ne rend pas très clair la question de savoir si une face contaminée d'un gant ne risque pas de contaminer une autre face en contact avec elle. Inversement, il est évidemment possible d'améliorer la solution si, comme c'est le cas pour des gants chirurgicaux, les gants sont réversibles. Ainsi, dans la version graveleuse traditionnelle généralisée par Ilan Vardi, les trois mathématiciens parviennent à honorer sans risque la même prostituée en n’utilisant que deux préservatifs[2],[4].
Références[modifier | modifier le code]
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Glove problem » (voir la liste des auteurs).
- (en) Eric W. Weisstein, « Glove Problem », sur MathWorld.
- (en) Ilan Vardi, The Condom Problem, Ch. 10 de Computational Recreations in Mathematica. Redwood City, CA: Addison–Wesley, pp. 203–222, 1991. (ISBN 0-201-52989-0) [lire en ligne].
- A. Hajnal et A. H. G. Rinnooy Kan, Interfaces between Computer Science and Operations Research, Mathematisch Centrum, , « An Algorithm to Prevent the Propagation of Certain Diseases at Minimum Cost ».
- Dans ce cas (M = 3 et N = 1), la solution est d'utiliser les deux préservatifs l'un sur l'autre pour le premier mathématicien, le préservatif extérieur seul pour le deuxième, et de réenfiler les deux préservatifs après avoir retourné le préservatif intérieur pour le dernier mathématicien.
