Se connecter / S'enregistrer
Votre question

Optimisation et Recherche opérationnelle : quel algo ?

Tags :
  • Programme
  • Programmation
Dernière réponse : dans Programmation
25 Mars 2006 20:44:45

Salut à tous !

Je me tourne vers vous aujourd'hui, car je suis dans une impasse. Je dois réaliser un projet dans le cadre d'un cours intitulé "Optimisation et recherche opérationnelle".

Comme vous vous en doutez, nous étudions dans cette matière, différentes méthodes d'optimisation. Au programme, nous avons :

- programmation linéaire
- programmation en nombres entiers : méthode des coupes
- application des graphes à la Recherche Opérationnelle : programmation dynamique, recherche arborescente
- méthodes heuristiques : algorithme de descente et du kangourou, recuit simulé, méthode tabou.
- optimisation distribuée : colonie de fourmis, intelligence en essaim
- optimisation de processus stochastiques
- théories des jeux
- algorithme génétique

Pour le moment, nous n'en sommes qu'au premier point, c'est à dire la programmation linéaire. Cependant, les profs nous ont déja donné le sujet de notre projet, et pour cause, il est compliqué et long à réaliser. Nous pouvons utiliser la méthode que nous voulons, du moment que les résultats obtenus sont bons. Nous pouvons même utiliser une méthode qui n'est pas au programme du cours.

Je dois rendre la spécification de ce projet pour le 12 avril. Nous avons eu le sujet cette semaine, et je ne vois meme pas par où commencer...

Je vais quand meme vous parler du sujet :D 

Il s'agit d'écrire un programme, dans le langage de notre choix, qui permettra de gérer les emplois du temps de notre école de meilleure façon qu'ils ne le sont actuellement. On fournira 2 fichiers texte au programme. Le premier contient la liste de tous les cours, TD et TP et les jours et horaire de leur plannification. Le second contient la liste des étudiants, et les unité de valeurs (cours) auxquelles il est inscrit.
Le programme devra calculer la meilleure façon de répartir les différents étudiants dans les différents cours, TD et TP, afin qu'il y ait le moins d'incompatibilité possible (2 TD en meme temps par exemple).

Vous pouvez voir le sujet détaillé du projet en suivant ce lien : www.ifrance.com/brigadenord/sujet.pdf

Mon problème est le suivant : je ne sais pas du tout quel algorithme utiliser pour gérer ce problème, étant donné que je n'en connais aucun. J'ai cherché sur internet, mais je ne trouve rien qui explique clairement le fonctionnement d'un des algorithme cité plus haut, et je dois connaitre le fonctionnement de tous, si je veux choisir le plus adapté...

Ma question : est-ce que quelqu'un pourrait me diriger vers un algorithme qu'il sait adapté à ce projet, ou m'expliquer le fonctionnement des algos cité plus haut ?

D'avance merci pour le coup de main.

Nicolas

Autres pages sur : optimisation recherche operationnelle algo

a b L Programmation
25 Mars 2006 22:43:36

Au lieu de trouver un algo existant, cherche un algo ;-)
A ta place, je programmerais en orienté objet (j'aurais fait ça dans tous les cas de RO :-P ) , je noterais bien l'ensemble des règles, je mettrais en place une architecture de graphe en imposant les règles obligatoire, et là où est la difficulté, je chercherais à tout optimiser avec une heuristique. Mais bon, je fais peut-être complètement fausse route, j'ai pas regardé en détail ton sujet :-D
26 Mars 2006 00:20:40

moui enfin pour écrire un algo dans ce genre qui tienne la route, il faut en avoir étudié quelques uns je pense.
Sinon, je compte programmer ça en java, donc pour l'orienté objet, je suis d'accord :) 
Tom's guide dans le monde
  • Allemagne
  • Italie
  • Irlande
  • Royaume Uni
  • Etats Unis
Suivre Tom's Guide
Inscrivez-vous à la Newsletter
  • ajouter à twitter
  • ajouter à facebook
  • ajouter un flux RSS