Remerciez-le!

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

Devoir de recherche operationnelle g3 def

RECHERCHE OPERATIONNELLE DEVOIR DE MAISON EXERCICE Les sommets ici sont désignés par les modules de m m ? ? ? m Les arêtes représentent les incompatibilités entre les di ?érents modules i et j M ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Modélisons donc la solution à l ? aide d ? un graphe C Le degré minimum d ? un sommet du graphe est Le module M est de degré donc pas d ? incompatibilité Il peut être programme dans l ? un des créneaux horaires Nous avons à résoudre un problème de coloration des sommets La résolution du graphe fait apparaitre trois couleurs donc nous avons nécessairement créneaux horaires CRENEAUX HORAIRES MODULES M -M -M -M M -M M -M -M EXERCICE C Les sommets représentent les personnes a b c ? h Les arêtes représentent les incompatibilités entre la personnes i et la personne j A B C D E F G H A ? ? ? ? B ? ? ? C ? ? ? ? ? D ? ? ? E ? ? ? F ? ? ? G ? ? ? ? H ? ? ? ? ? ? ? Modélisons donc la solution à l ? aide d ? un graphe C Nous avons a ?aire à un problème de coloration des sommets Après résolution du graphe dans graph magics nous avons quatre couleurs de sommets Nous pouvons donc réserver au minimum quatre chambres CHAMBRES TABLEAU RECAPITULATIF PERSONNES A-D-F B-E-G C H EXERCICE C PROFESSEUR P P P CLASSES C C C Modélisons le problème sous forme de graphe A P C A A P A C A A A P C A Les sommets sont représentés par les professeurs pi et les classes ci Une arête sera dé ?nie par le fait qu ? un professeur pi donne une heure de cours a la classe cj avec i P P P et j C C C Il s ? agit d ? un problème de coloration des arêtes parce qu ? on veut savoir quel professeur pi doit donner une heure de cours a une classe cj On va transformer le graphe précèdent pour avoir un problème de coloration de sommets C Il s ? agit d ? un problème de coloration des arêtes Après interprétation du graphe nous retiendrons cinq plages horaire Couleur a a Couleur a Couleur a a Couleur a Couleur a EMPLOI DU TEMPS PLAGES C C C HORAIRE PLAGE P P P PLAGE P PLAGE P P PLAGE P PLAGE P C EXERCICE Les sommets sont représentés par les étudiants i Bj Cd Dv Fl Em et les Enseignants j I M F A Les arrêts seront dé ?nis par le fait que les étudiants i passent à l ? oral avec un professeur j Bj a a Cd a a Dv a Em a a Fl a a