Remerciez-le!

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

RECHERCHE OPERATIONNELLE DEVOIR DE MAISON EXERCICE 1 1) Les sommets ici sont dé

RECHERCHE OPERATIONNELLE DEVOIR DE MAISON EXERCICE 1 1) Les sommets ici sont désignés par les modules de {m1 ; m2 ;……….m9 } Les arêtes représentent les incompatibilités entre les différents modules (i et j) M 1 2 3 4 5 6 7 8 9 1 0 × × 2 × 0 × × 3 × 0 × × 4 × 0 × × 5 × × × 0 × × 6 0 × × 7 0 9 × × × × 0 × 9 × × 0 Modélisons donc la solution à l’aide d’un graphe : 1 2) Le degré minimum d’un sommet du graphe est 2. Le module M7 est de degré 0, donc pas d’incompatibilité. Il peut être programme dans l’un des créneaux horaires 3) Nous avons à résoudre un problème de coloration des sommets. 4) La résolution du graphe fait apparaitre trois (03) couleurs, donc nous avons nécessairement (03) créneaux horaires. CRENEAUX HORAIRES MODULES 01 M1-M5-M7-M9 02 M2-M8 03 M3-M4-M6 EXERCICE 2 1 1) 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 : 1 2) Nous avons affaire à un problème de coloration des sommets. 3) Après résolution du graphe (dans graph magics), nous avons quatre (04) couleurs de sommets. Nous pouvons donc réserver au minimum quatre (04) chambres. TABLEAU RECAPITULATIF CHAMBRES PERSONNES 01 A-D-F 02 B-E-G 03 C 04 H EXERCICE 3 1 PROFESSEUR {P1, P2, P3} CLASSES {C1, C2, C3} 1) Modélisons le problème sous forme de graphe.  Les sommets sont représentés par les professeurs (pi) et les classes (ci)  Une arête sera définie par le fait qu’un professeur (pi) donne une (01) heure de cours a la classe (cj) avec : i ={P1 ;P2 ;P3} et j={ C1 ;C2 ;C3} 2) 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. 1 P1 C1 P2 C2 P3 C3 A1 A3 A4 A2 A5 A6 A7 A8 2) Il s’agit d’un problème de coloration des arêtes. 3) Après interprétation du graphe nous retiendrons cinq (05) plages horaire :  Couleur 1 (a1 ; a3)  Couleur 2 (a2)  Couleur 3 (a4 ; a7)  Couleur 4 (a5)  Couleur 5 (a6) EMPLOI DU TEMPS PLAGES HORAIRE C1 C2 C3 PLAGE1 P1 P2 P3 PLAGE2 P2 PLAGE3 P3 P2 PLAGE4 P2 PLAGE5 P2 1 EXERCICE 4 1) 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éfinis par le fait que les étudiants (i) passent à l’oral avec un professeur (j). 2) Il s’agit d’un problème de coloration des arêtes parce qu’on veut savoir quel élève (i) doit composer dans quelle matière (j) nous allons transformer le graphe précèdent pour avoir un graphe de coloration des sommets s. 1 Bj Cd Dv Em Fl M F A I a2 a3 a4 a1 a6 a5 a7 a8 a9 a10 3) Résolution du problème : A l’aide de notre graphe nous obtenons le résultat suivant : - 1(a1 ;a3 ;a5) - 2(a2 ;a4 ;a7) - 3(a6 ;a8 ;a9) et - 4 (a10). Ce qui donne le planning suivant : HEURES MATIERES INFORMATIQUE MATHEMATIQU E ANGLAIS FRANCAIS PLAGE1 DAVID CEDRIC BENJAMIN PLAGE2 EMY CEDRIC BENJAMIN PLAGE3 FLORENCE EMY DAVID PLAGE4 FLORENCE 1 Minimal Nr. of Colors needed - 4 # Vertex Color 1 A1 1 2 A2 2 3 A3 1 4 A4 2 5 A5 1 6 A6 3 7 A7 2 8 A8 3 9 A9 3 10 A10 4 EXERCICE 5 1) Les sommets représentent les animaux {a ;……..j} , Une arête représente l’incompatibilité de cohabitation entre un animal (i) et un animal (j). Il s’agit d’un Problème de Coloration des Sommets. 1 Apres interprétation du graphe, nous notons trois (03) couleurs d’où 03 enclos. ENCLOS ANIMAUX 1 A C D G I 2 B E F H 3 J 1 EXERCICE 6 1) Les sommets sont représentés par les élèves : {Adrien ; Sophie ; Charlotte ; Mathieu} et les matières {mathématique, physique, biologie, français, anglais, espagnole, histoire} Une arête sera définie par le principe qu’un élève (i) passe dans une matière (j) Nous avons un problème de coloration d’arêtes. Modélisons donc la solution à l’aide d’un graphe : Nous allons transformer le graphe précèdent pour avoir un graphe de coloration des sommets. 1 So Ch Mt Ad M P B A H F E A5 A7 A3 A4 A6 a1 a10 A2 a11 A8 A9 a12 2) Déterminons le nombre de plage à l’aide du graphe afin qu’un élève n’ait pas à passer 2 tests simultanément. 1 Résultats : 03 couleurs à savoir : (a1 ; a5 ;a8 ;a10) (a2 ;a4 ;a9 ; a11) (a3 ;a6 ;a7 ;a12) d’où 03 plages horaire. Le nombre minimal de plage horaire à prévoir est donc 3 Adrien Sophie Charlotte Mathieu 1ere plage Mathématique s Biologie anglais Physiques 2eme plage Physiques Mathématiques Espagnol Français 3eme plage Anglais Français Mathématiques Histoires 1 EXERCICE 7 Les sommets sont représentés par classes {a ;b ;c ; …..g} ; Une arête représentera une impossibilité pour une classe (i) de passer un examen au même moment qu’une classe(j). 1) Il s’agit d’un problème de Coloration des sommets 1 Minimal Nr. of Colors needed - 3 # Vertex Color 1 a 1 2 b 2 3 c 3 4 d 1 5 e 1 6 f 2 7 g 3 2)Le nombre minimal est de créneau horaire est 3 CRENAUX HORAIRES EXAMENS 1 a, d, e 2 b, f 3 c, g 1 Exercice 8 1) Modélisons donc la solution à l’aide d’un graphe : Il s’agit d’un problème de coloration des arêtes 1 a4 a5 a6 a8 a7 A9 a10 a2 a3 a11 a1 A12 Nous allons transformer le graphe précèdent pour avoir un graphe de coloration des sommets. 2) Par jour on peut effectuer cinq (05) examens selon notre graphe. Jour 1 : 5 examens (M1 ; M3 ; M2 ; M5 ; M6) ; Jour 2 : 4 examens (M2 ; M4 ; M5 ; M3) ; Jour 3 : 3 examens (M5 ; M4 ; M3). 3) Le nombre minimal de jour pour passer tous les examens est 3 1 EXERCICE 9 1) Il s’agit d’un problème de coloration des arêtes dans lequel un étudiant (i) doit composer dans une seule matière (j) par jour. Nous allons transformer le graphe précèdent pour avoir un graphe de coloration des sommets. 1 a11 a12 a10 a9 a8 a7 a6 a5 a4 a3 a2 a1 2) Nous avons trois (03) couleurs après traitement de notre graphe d’où trois (03) jours minimal nécessaires : 1er jour : (a12 ;a8 ;a6 ;a5 ;a3) 2ème jour : (a11 ;a10 ;a7 ;a2) 3ème jour : (a9 ;a4 ;a1). TABLEAU RECAPITULATIF PLAGE/ JOURS ETUDIANTS DUPON T DUPON D DURAN D DUVA L DUPUI S 1 M C A D S 2 A S M D 3 F D C 1 3) Jour 1 : (F ; D ; A ; M ; S) Jour 2 : (A ; C ; S ; D) Jour 3 : (M ; C ; D) Le nombre maximal d’épreuves que l’on peut organiser en un jour est 5 épreuves. 1 EXERCICE 10 (VOIR EXERCICE 6) 1 EXERCICE 11 1_ Les sommets sont représentés par les produits i : {P1,P2,P3,P4,P5,P6} et les arêtes seront définies par le fait que chaque produit n’est pas miscible à un autre dans le même ensemble Il s’agit d’un problème de coloration des sommets. 2_ Déterminons le nombre de wagons nécessaire au transport des six (6) produits - Résolution avec GRAPH MAGICS a) d) Trois wagons seront nécessaires au transport des six (6) produits. Ci- dessous les tableaux récapitulatifs : Wagons Produits 1 P1, P5 2 P2, P4, P6 3 P3 1 EXERCICE 12 1) Modélisons la situation à l’aide d’un graphe : Les sommets du graphe représentent les stations et les arêtes représentent les liaisons entre les stations distantes de moins de 150 km Il s’agit d’un problème de coloration des sommets 1) Dressons notre tableau de compatibilité en vue de déterminer le nombre de canaux : A B C D E F A X X X B X X X C X X D X E X X X F X X Nous déterminons trois (03) couleurs qui traduisent 03 canaux distincts qui sont : CANAL1 : F ; uploads/s3/ devoir-de-recherche-operationnelle-g3-def.pdf