SVOR logo  SATW logo

Concours d'Optimisation 2010

Concours reservé aux étudiants des gymnases de Suisse

 

Description de concours

en français (pdf), en français (docx)

 

Affiche

en français (pdf), en français (pptx)

 

Download

  • Le problème
  • Fichier de soumission des solutions

    •  

     

    Introduction

     

    La recherche d’un plan d’expéditions à coût minimum dans un réseau est un problème complexe, dû au grand nombre de solutions possibles. En effet, même s’il est facile de trouver une solution admissible à un tel problème, prouver l’optimalité d’une solution s’avère très difficile.

    Le problème d’envois de colis dans un réseau obtenu par Facebook est un exemple de problèmes abordés par la Recherche Opérationnelle. Dans de tels problèmes, l’énumération complète de toutes les solutions admissibles pour déterminer la solution optimale ne fonctionne que pour des réseaux de petites tailles. Pour ce type de problèmes, la Recherche Opérationnelle offre des méthodes qui déterminent la solution optimale sans pour autant évaluer chacune des solutions possibles.

    La Recherche Opérationnelle est une science qui se situe à mi-chemin entre l’Informatique et les Mathématiques et qui regroupe un ensemble de méthodes d’aide à la décision dans le but de résoudre des problèmes d’optimisation, comme celui de la détermination d’un plan d’envois de colis à coût minimum.

    Dans le but de promouvoir la Recherche Opérationnelle parmi les futurs universitaires suisses, la Société Suisse de Recherche Opérationnelle (ASRO) organise cette année un concours qui est lié aux réseaux sociaux obtenus via Facebook.

     

    Formulation du concours

     

    Michel et Emma sont amis sur Facebook. Bientôt, ce sera l'anniversaire d'Emma, et Michel désire organiser une fête pour cette occasion. Michel utilise Facebook pour identifier les 16 amis qu’Emma et lui ont en commun, dans divers pays. Grâce au visionneur de relations entre amis communs trouvé sur le site

    http://danielmclaren.net/node/77

    Michel obtient le graphe de la Figure 1, lui permettant de visualiser facilement qui est ami avec qui (sur Facebook).

    Le défi de Michel est de trouver des cadeaux originaux pour Emma. Actuellement en voyage en Afrique du Sud pour suivre la coupe du monde de football, Michel trouve sur un marché local une collection de masques africains dont Emma est une collectionneuse passionnée.

    Le cadeau est donc tout trouvé ! Et pour que l'effet soit total, chaque invité arrivera à la fête avec un masque qu'il/elle offrira à Emma.

    Malheureusement, l'acheminement des masques en Suisse s'avère compliqué. Il est impossible de ramener tous ces cadeaux par avion. Michel décide donc de les expédier par la poste.

    Figure 1: Graphe des relations entre les amis communs de Michel et Emma. Deux personnes sont reliées si elles se connaissent.

     

    Cependant, effectuer 16 envois individuels serait beaucoup trop coûteux, dû à une taxe sur l'emballage, et le risque de perdre un des masques serait trop élevé. Par conséquent, Michel décide d'envoyer un unique paquet à l'un des amis communs, qui aura la  responsabilité de faire parvenir les masques à chacun des autres invités.

    Comme le graphe l'illustre, tous les invités ne se connaissent pas entre eux. Et Michel désire organiser l'expédition de telle manière à ce que les masques soient envoyés uniquement entre personnes qui se connaissent (voir l'exemple ci-dessous).

    Evidemment, si cette répartition n'est pas correctement organisée, elle va aussi coûter une fortune ! Michel se trouve donc face à un problème d'optimisation: il doit décider à qui envoyer le paquet contenant les 16 cadeaux pour Emma et, de plus, expliquer à cette  personne comment organiser la distribution, en réexpédiant les cadeaux et les instructions de manière à payer le moins possible en frais d'envois.

    Chacun des amis habite dans une des trois zones tarifaires de la poste: la zone grise (G), la zone jaune (J) et la zone mauve (M). Les frais d'envois sont repris ci-dessous :

     

    Michel doit donc décider à qui envoyer les 16 masques et comment ceux-ci doivent être réexpédiés de manière à ce que chaque ami arrive à la fête muni d’un masque et que les frais d’envois soient minimaux.

    Formellement, les points que Michel doit observer lors de sa décision sont :

    1.      le colis qu’il envoie depuis l’Afrique contient les 16 cadeaux, et n’est envoyé qu’à une seule personne ;

    2.      un envoi entre deux invités n’est possible que si ces deux personnes se connaissent mutuellement sur Facebook, c’est-à-dire s’ils sont reliés dans la Figure 1 ;

    3.      les cadeaux ne sont pas nominatifs, et peu importe quel masque est offert par quel invité ;

    4.      plusieurs réexpéditions d’un même masque sont éventuellement possibles ;

    5.      une personne peut envoyer un paquet contenant plusieurs masques à une autre personne ;

    6.      le coût de chaque paquet est calculé en fonction de la zone de l’envoyeur, celle du destinataire ainsi que du nombre de masques dans le colis (par exemple, envoyer 3 masques de « J » à « M » coûte 6€) ;

    7.      le total des frais d’envois est la somme des coûts d’envois de  toutes les personnes envoyant au moins un paquet.

     

    Question Principale :     A qui Michel doit-il envoyer le paquet contenant les 16 masques et comment les masques sont-ils réexpédiés pour obtenir la solution la moins coûteuse ? Quel est le coût de la solution ?

    Question Subsidiaire : Combien de buts seront marqués durant l’intégralité de la coupe du monde en Afrique du Sud ? Attention, les buts marqués lors des séances de tir aux buts en phase finale ne comptent pas !

     

    Exemple

    Le plan d’expédition ci-dessous permet aux 16 amis de Michel et Emma de recevoir un paquet. Le coût total des envois se monte à 145€. Existe-t-il un autre plan d’expéditions dont la somme des frais d’envois est inférieure à 145€ ? Oui … A vous de la trouver !

     

    Expéditeur

    Groupe

    Destinataire

    Groupe

    Nbr. de masques

    Coût

    Michel

     

    Moshe

    G

    16

    32 €

    Moshe

    G

    Eric

    M

    3

    9 €

    Moshe

    G

    Maya

    G

    12

    36 €

    Maya

    G

    Carolina

    J

    9

    27 €

    Maya

    G

    Charisma

    J

    1

    3 €

    Maya

    G

    Matteo

    M

    1

    3 €

    Carolina

    J

    Gautier

    G

    3

    9 €

    Carolina

    J

    Benjamin

    M

    3

    6 €

    Carolina

    J

    Javier

    M

    2

    4 €

    Eric

    M

    Mogens

    M

    2

    2 €

    Gautier

    G

    Antonio

    M

    1

    3 €

    Gautier

    G

    Jelena

    J

    1

    3 €

    Benjamin

    M

    Jacques

    G

    1

    3 €

    Benjamin

    M

    Fafa

    J

    1

    2 €

    Javier

    M

    Veronica

    J

    1

    2 €

    Mogens

    M

    Sebastian

    M

    1

    1 €

     

     

     

     

     

     

     

     

     

     

    Coût Total

    145 €

     

     

    Organisation du concours

    Les données complètes du concours sont disponibles sur Internet à l'adresse www.asro.ch.

     

    Votre solution (question principale) et la réponse à la question subsidiaire sont à envoyer à l'adresse e-mail info@asro.ch au moyen du fichier Excel Solution_Concours_ASRO_2010.xls, disponible sur le site. Veuillez également y indiquer vos coordonnées, ainsi qu’une brève description de la méthode de résolution utilisée.

    Le délai de participation est fixé au dimanche 6 juin 2010.

     

    Règlement

    Le concours est réservé aux étudiant(e)s des gymnases de Suisse.

    L'ASRO encourage les étudiant(e)s à implémenter un modèle ou un programme informatique visant à trouver la meilleure solution à la question 1. Néanmoins une recherche «manuelle» est également admise.

    Seules les réponses reçues dans les délais seront prises en considération.

    L'ASRO retiendra les cinq solutions admissibles dont le total des frais d’envois est le plus faible (question principale). À qualité de solution égale, les vainqueurs seront départagés sur la base de la question subsidiaire. Si cela ne suffit pas, les vainqueurs seront désignés par tirage au sort.

     

    Prix

    Le concours est doté de cinq prix représentant un montant global de 2'000 CHF.

    1er   prix :           600 CHF

    2ème prix :           500 CHF

    3ème prix :           400 CHF

    4ème prix :           300 CHF

    5ème prix :           200 CHF

    L’ASRO contactera les vainqueurs dans le courant du mois de juillet 2010.