Sujet de projet - Université Paris-Est Marne-la
Contents
1. Bibliographie m V Ch vtal Linear Programming W H Freeman 1983 m les transparents du cours beal Enseignement Algo4 transport pdf2. Sujet de projet MARIE PIERRE B AL ET CLAIRE DAVID Universit Paris Est Marne la Vall e L3 Informatique Algorithmique 4 marie pierre bealQ u pem fr claire david u pem fr o N Projet Caterer But du projet Le but de ce projet est d impl menter en Java imp rativement l algorithme de r seaux de transport tudi en cours en l appliquant quelques exemples en particulier l exemple des serviettes de tables Le programme devra traiter un graphe d crit dans un ficher texte sous un format d fini ci dessous On doit pouvoir sp cifier au d marrage du projet ou dans un menu quel fichier on veut traiter Modalit s Le projet est rendre pour le 1er Juin 2014 23h dernier d lai Il est faire en bin me Le projet sera rendu dans Moodle sous la forme d un zip NomiNom 2 zip contenant les fichiers et r pertoires suivant Modalit s un fichier README au format texte qui indique les noms et pr noms des membres du bin me et comment compiler et lancer le programme un jar ex cutable bin caterer jar permettant d ex cuter directement le programme un r pertoire source src contenant l ensemble des sources r unies dans le paquetage java fr upem login caterer o login est remplacer par l un des logins des membres du groupe un manuel d utilisation au format PDF le fichier docs user pdf indiquant l ensemble des fonctionnalit s et comment les faire fonctionner une documentation pour
3. co t co t co t co t co t co t Probl me des serviettes de table Example Un restaurateur pr voit sur une p riode de n jours ses besoins en serviettes de table II conna t l avance le nombre dj de serviettes qui seront utilis es le j me jour Le restaurateur peut acheter des serviettes neuves x euros par serviette ou faire laver les serviettes usag es La blanchisserie propose deux services de nettoyage un service rapide r euros par serviette retour q jours apr s et un service plus lent euros par serviette retour p jours apr ss Naturellement ona x gt r gt Lletp gt q On suppose que le restaurateur ne dispose au d part d aucune serviette devra donc commencer par en acheter quelques unes Probl me des serviettes de table Le restaurateur cherche laborer une strat gie de gestion des serviettes sur n jours en minimisant ses d penses Une solution optimale peut tre trouv e en mod lisant le probl me sous la forme d un r seau de transport Cette solution fournira au restaurateur les quantit s journali res de serviettes qui devront tre respectivement achet es lav es en service rapide et lav es en service lent Nous allons d crire la mod lisation avec les valeurs suivantes pour les constantes n 10 p 4 q 2 x 8 r 3 1 Enfin les besoins pour les dix jours sont Probl me des serviettes de table jour nombre de serviettes n cessaires 50 60 8
4. 0 70 50 60 90 80 50 100 Ha OI O1 B N Ha Mod lisation Le graphe ci dessous repr sente un r seau adapt au probl me Le j me tat situ gauche en partant du haut repr sente la situation la fin du jour j le nombre de serviettes usag es tant gal dj Le j me tat de droite repr sente la demande au d but du jour j Les tats de gauche sont des sources Ceux de droite magasin et inventaire non compris sont des puits Chaque serviette usag e peut tre envoy e au lavage service rapide arcs horizontaux de co t r au lavage service lent arcs pench s de co t ou tre gard e en attente arcs verticaux de co t nul Enfin les serviettes peuvent tre achet es arcs provenant de l tat magasin de co t x A la fin du dixi me jour le reliquat de serviettes usag es est envoy l inventaire tout comme le reliquat du magasin On suppose qu aucun client ne vole de serviette et donc que ce qui retourne l inventaire est gal au stock initial du magasin Le r seau a ainsi un vecteur de poids de somme nulle Le r seau 6900 magasin 6900 a z HAE inventaire Impl mentation On demande m d utiliser les API Java m de traiter le probl me auxiliaire m de ne pas traiter la d composition en sous probl mes cas 3 du cours On ne demande pas de programmer l impl mentation tr s optimis e du Chvatal
5. d veloppeur au format PDF le fichier docs dev pdf indiquant les choix des algorithmes et structures de donn es effectu s ainsi que les API et classes utilis es pour les impl menter On indiquera le sch ma des classes un r pertoire docs api contenant la documentation g n r e par javadoc Le programme devra tre test au moins sur les deux exemples suivants m L exemple d approvisionnement en pneux Michelin voir ci dessous m Le probl mes des serviettes de table voir ci dessous Approvisionnement en pneux Michelin Example On consid re 2 usines Michelin qui fabriquent chaque jour l une 550 pneus et l autre 350 pneus Ces usines approvisionnent 3 magasins qui doivent recevoir chaque jour respectivement 400 300 et 200 pneus Le co t de transport de chaque pneu par diff rents types de transports ou routes est donn Quelles voies doit on emprunter pour acheminer toutes les marchandises moindre co t 550 350 00 40 Format du fichier graphe Pour repr senter le r seau on lira un fichier qui aura le format suivant Les sommets seront num rot s partir de 0 5 nombre de sommets 550 350 400 300 200 2 h h kB H N amp amp 5 6 3 3 5 4 un un un arc arc arc arc arc avec avec avec avec avec avec son son son son son son le vecteur des poids
Download Pdf Manuals
Related Search