Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 EXAMEN OPTIMISATION EN INFORMATIQUE RCP104 JUIN 2009 Durée 2 heures Tout docu

1 EXAMEN OPTIMISATION EN INFORMATIQUE RCP104 JUIN 2009 Durée 2 heures Tout document autorisé. Examen écrit noté sur 14 Exercice 1 Une université vient d’acheter un nouveau supercalculateur pour les besoins d’un de ses laboratoires de recherche. L’utilisation de ce supercalculateur nécessite la présence permanente d’un technicien capable de répondre aux besoins des utilisateurs (enseignants- chercheurs et doctorants) et d’effectuer quelques travaux de programmation. Le directeur du centre de calcul est confronté au problème d’affectation d’heures de travail sur le supercalculateur aux différents techniciens. Plus précisément, il doit déterminer le nombre d’heures à affecter à chaque technicien chaque jour ouvrable de la semaine. On notera n le nombre de techniciens numérotés par un indice i allant de 1 à n. Les jours ouvrables seront numérotés par un indice j allant de 1 à 5 (pour lundi, mardi, …, vendredi) L’affectation des heures doit satisfaire un certain nombre de règles. - Règle 1 : Le centre est ouvert chaque jour de 8h à 22h et il faut qu’exactement un technicien soit présent à chaque heure. Il y a donc un total de 14 heures à assurer chaque jour. - Règle 2 : Comme les techniciens doivent assurer d’autres tâches, il ne leur reste que quelques heures de disponibilité chaque jour. Le nombre d’heures disponibles pour le technicien i le jour j sera noté Dij. - Règle 3 : Afin que les techniciens gardent leur niveau de connaissance du supercalculateur, chacun d’eux doit consacrer au minimum 8 heures par semaine à travailler sur le supercalculateur. - Règle 4 : Pour des raisons évidentes de facilité de gestion, les nombres d’heures que doit déterminer le directeur doivent être des entiers. Par ailleurs, là encore pour des raisons évidentes de budget, le directeur souhaite minimiser le coût total de l’opération. Il connaît le taux horaire de rémunération de chaque technicien i, qui sera noté Ti (ce nombre est exprimé en euros/heure) Modélisation Le directeur du centre de calcul souhaite modéliser son problème d’optimisation par un programme mathématique. Il fait appel à vous pour l’aider dans cette tâche. 1) Donner les variables du problème. 2) Donner la famille de contraintes nécessaires pour respecter la Règle 1 3) Donner la famille de contraintes nécessaires pour respecter la Règle 2 4) Donner la famille de contraintes nécessaires pour respecter la Règle 3 5) Donner la famille de contraintes nécessaires pour respecter la Règle 4 6) Donner la fonction objectif 2 7) A quel type de programme mathématique aboutissez-vous ? Application à un exemple Le directeur du centre vous fait part ensuite de ses données réelles. Le centre emploie 6 techniciens. Heures de disponibilité Dij Technicien Taux Ti 1-lundi 2-mardi 3-mercredi 4-jeudi 5-vendredi 1 10 €/h 6 0 6 0 6 2 10,10 €/h 0 6 0 6 0 3 9,90 €/h 4 8 4 0 4 4 9,80 €/h 5 5 5 0 5 5 10,80 €/h 3 0 3 8 0 6 11,30 €/h 0 0 0 6 3 8) Appliquez le modèle mathématique obtenu ci-dessus pour écrire précisément le programme mathématique (que nous appellerons (P)) à résoudre pour cet exemple. 9) Vous présentez au directeur l’affectation suivante des horaires : Heures affectées Technicien 1-lundi 2-mardi 3-mercredi 4-jeudi 5-vendredi 1 6 0 2 0 4 2 0 6 0 2 0 3 2 5 4 0 4 4 4 3 5 0 3 5 2 0 3 6 0 6 0 0 0 6 3 a) Vérifier qu’il s’agit d’une solution admissible de (P) ? Calculer son coût ? b) Que peut en déduire le directeur quant au budget minimal qu’il doit payer ? 10) Vous résolvez le problème obtenu par relaxation continue de (P) et vous obtenez les valeurs suivantes pour les variables représentant les heures effectuées. Heures affectées Technicien 1-lundi 2-mardi 3-mercredi 4-jeudi 5-vendredi 1 2 0 3 0 3 2 0 2 0 6 0 3 4 7 4 0 3 4 5 5 5 0 5 5 3 0 2 3 0 6 0 0 0 5 3 a) Dire par quel algorithme vu en cours la résolution a été effectuée. b) Que pouvez-vous en déduire sur la solution optimale de (P) et sa valeur ? 3 Méta-heuristiques On envisage de résoudre le problème à l’aide d’une méta-heuristique : le recuit-simulé. La première étape de cette méthode consiste à déterminer une solution admissible du problème. On suppose ici que le problème considéré admet une solution admissible qui a été trouvée par une heuristique gourmande. 11) Dans l’algorithme du recuit-simulé, partant d’une solution admissible du problème, on doit choisir au hasard une solution voisine de celle-ci, parmi l’ensemble de ses voisins. a) Dans un langage de programmation (type java ou C …) comment serait représentée une solution admissible ici ? b) Proposez une notion de voisinage impliquant 2 techniciens différents sur une même journée. Précisez pour cela ce qu’est une solution B voisine d’une solution A. Précisez également comment serait effectué le choix aléatoire d’une solution voisine. c) Exprimez la différence de coût ∆ entre la solution A et la solution B. 12) Considérant l’instance particulière du problème présentée dans la partie « Application à un exemple », et plus précisément la solution admissible de cette instance de la question 9, que nous appellerons solution A, proposez une solution B voisine de celle-ci. Précisez si elle détériore ou améliore la solution A. Dans l’un ou l’autre cas, indiquez si l’algorithme serait susceptible de la considérer comme nouvelle solution courante. Exercice 2 – Coupes pour la PLNE On considère le problème d’allocation de registres donné en projet, dont nous rappelons ici la modélisation sans toutefois ré-énoncer le problème : { } { } { } { } { } { } { } { } { }            ∈ ∀ ∈ ∀ ∈ ∈ ∀ ∈ ∀ ≤ − ∈ ∀ ∈ ∀ ≤ + ∈ ∀ = ∑ ∑ = ∈ ,...,K c , ,...,n i , x ,...,K c , E i,j y x x ,...,K c , E i,j x x ,...,n i x y w ic pref ij jc ic jc ic K c ic E ij ij pref 1 1 1 0 1 1 1 1 1 s.c. Min int 1 j i, (Les variables xic valent 1 si et seulement si le sommet i est de couleur c et les variables yij valent 1 si {i,j} est une arête et si les sommets i et j sont de couleurs différentes.) Le but de l’exercice est de retrouver une famille d’inégalités valides récemment proposées par Grund et Hack pour ce problème. Considérons pour cela deux sommets x et y dans le graphe associé au problème considéré tels que {x,y} soit une arête d’interférence. Supposons par ailleurs que x et y soient reliés par une chaîne constituée d’arêtes de préférences. Notons (e1, e2, …, ep) cette chaîne constituée de p arêtes de préférences. a) x et y ne peuvent être coloriés de la même couleur. Pourquoi ? b) Est-il possible que toutes les extrémités des arêtes qui composent la chaîne de préférence soit coloriées avec une même et unique couleur ? Pourquoi ? 4 c) On note i e y la variable y associée à l’arête ei : si l’arête ei est l’arête {a,b}, i e y représente la variable yab. Proposez une inégalité valide faisant intervenir les variables i e y associées aux arêtes de la chaîne de préférence. d) Dans le graphe ci-dessous, utilisant les conventions habituelles (arêtes d’interférence en trait plein, arêtes de préférence en pointillés), précisez quelle serait l’inégalité valide de la question c). 1 2 3 4 4 1 3 uploads/s3/ rcp104-exam-juin-2009.pdf