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
 
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

Modélise d abord les différentes composantes:
élèves, cours, heures.
 
Ensuite tu devrais trouver une structure en matrice ou en graphe sur laquelle appliquer un algorithme de plus court chemin ou de flot maximal.

Sans être indiscret, c'est où que tu apprends ça ? et en quelle année ?
...je te répondrai avec un bon post d'ici quelques jours, là j'ai pas le temps . Mais j'ai déjà fait de la RO, je connais donc bien le truc.

Intéressant comme travail et programme alléchant .
 
Bon concernant ton problème, sache qu'il est très connu !
C'est très lié au domaine de la recherche opérationnelle car il met en jeu
beaucoup de contraintes et les problèmes d'affectation sont NP-Complets.
De nos jours, les algorithmes utilisés pour résoudre ces problèmes très
difficiles sont étudiés dans le domaine de la recherche opérationnelle.
De façon très succinte et très gloable voilà comment t'introduire le domaine de
la RO.On distingue 2 grandes familles d'algorithmes pour résoudre ce genre de
problème :
 
1) Les algorithmes exacts qui permettent d'optimiser sur une fonction objective
à l'optimal (maximiser ou miniser sa valeur)
Avantage de cette approche : son optimalité sur un problème à la base
NP-Difficile.
Inconvénient : souvent les temps de résolution jusqu'à l'optimal sont trop longs.
 
2) Les algorithmes approchés interviennent donc pour fournir des résultats
approximatifs, cad non optimaux mais fournissant une bonne solution en un temps
raisonnable souvent.
Avantage : fourni de bonnes solutions en un temps raisonnable.
Inconvénient : l'optimalité, bien que non exclue, n'a aucune chance d'être
trouvée
tellement l'espace de recherche est énorme.
 
Cependant ton problème n'a pas de fonction objectif à optimiser. Dans ton cas,
il suffit de trouver juste une affectation qui satisfait les contraintes.
Solution pouvant être trouvée avec la programmation linéaire...et je vois pas
avec quoi d'autre
 
Concernant ton programme :
 
1) programmation linéaire : il s'agit de la résolution de problème
d'optimisation. Tu définis les contraintes de ton problème à satisfaire sous
forme d'équations mathématiques. Une fonction objective à optimiser en général
est définie, cad maximiser ou minimiser sa valeur. On obtient donc un système
d'équations contenant aussi tes variables que tu cherches et dont tu connaîtras
leur valeur après résolution du programme linéaire. Contrainte importante : on
considère en programmation linéaire "simple" que tes variables appartiennent à
l'ensemble des réels et sont positives ou nulles.
 
2) programmation en nombres entiers : méthode des coupes Alors là c'est une UE
putain de chaud !. Si vous poussez un peu dans le domaine, on sort très vite de
l'informatique pour tomber dans le domaine des mathématiques appliquées. Autant
l'idée de cette UE est très simple à comprendre (ce qu'on cherche à faire)
autant l'apport de solution est difficile. En général, cette UE est plutôt
enseignée en DEA car très orientée recherche, très théorique et en plein coeur
de la recherche dans le domaine de la recherche opérationnelle. Bon, quelle est
l'idée ? En fait c'est de la programmation linéaire généralisée. C'est à dire
que le domaine des variables du système d'équation est N (programmation linéaire
en nombres entiers) ou bien certaines appartiennent à N et d'autres à R
(programmation linéaire mixte). La grosse difficulté est donc que des variables
peuvent appartenir à N. La résolution d'un programme linéaire se fait
généralement par la méthode du simplexe. Cependant cette dernière suppose que
les variables appartiennent à R. Or si on veut que certaines variables
appartiennent à N, on doit trouver une façon de sorte que la méthode du simplexe
fournisse une valeur réelle (ce qui est toujours le cas) et en plus entière (ce
qui est rarement le cas). Donc pour cela, on doit approché du mieux possible le
polyèdre (défini par le système d'équation) délimitant l'ensemble des valeurs
entières possibles que peuvent prendre les variables entières. Après une petite
étude sur la théorie des polyèdres, on sait que le polyèdre délimitant
l'ensemble des solutions entières est inclus dans le polyèdre délimitant
l'ensemble des solutions continues. A partir de là, on essai de "tailler" le
polyèdre délimitant l'ensemble des solutions continues afin de se rapprocher le
plus possible du polyèdre délimitant l'ensemble des solutions entières. Ce
"taillage" est affectué à l'aide de ce que l'on nomme "coupes". En fait ce n'est
ni plus ni moins que des contraintes que l'on génère et que l'on rajoute au
programme linéaire. Ces nouvelles contraintes garantissant un polyèdre
délimitant l'ensemble des solutions continues plus proche de celui délimitant
l'ensemble des solutions entières sans "tailler" ce dernier sinon, certaines
solutions réalisables du problème de départ seraient ignorées. Cependant on sait
que ce "taillage" sera loin d'être parfait, c'est à dire que l'inclusion du
polyèdre délimitant l'ensemble des solutions entières dans le polyèdre
délimitant l'ensemble des solutions continues ne sera pas parfaite (il existera
de l'espace entre les deux). Par conséquent, une prochaine étape est nécessaire
pour la résolution d'un programme linéaire en nombres entiers : la recherche
arborescente de type Branch and Bound. Bref, j'aurais encore beaucoup à
raconter sur le sujet. Mais il faudrait finir par faire des dessins car les
choses deviennent compliquées et je vais te perdre si je vais plus loin (puis ca
deviendra long après ). En l'heure actuelle, on en est à la résolution de
programme linéaire en nombres entiers avec des méthodes arborescentes nommées
"Branch-Cut-and-Price" (cf. google pour plus d'info). Et là ça devient balèze le
truc !
 
3) programmation dynamique : alors ça je connais pas mais c'est peut être
l'algorithme de génération de colonne quand on dispose de trop de variable dans
le programme linéaire, c'est ca ? (je doute quand même).
recherche arborescente : recherche meilleur-d'abord, profondeur-d'abord et
largeur-d'abord en général.
 
4) méthodes heuristiques,  algorithme génétique , colonie de fourmis : ce sont des algorithmes de résolution approximative.
 
5) optimisation de processus stochastiques  et théories des jeux : jamais
étudié.
 
Voilà .

bonjour,
 
 je travaille sur un théme sous l'optimisation de positionnement des dispositifs d'écoute du réseau AEP
Les couches de données : les canalisations de type poli ligne(arcs) et les Vannes de type point(sommets)
On a 2 types du pré-localisateur T1 et T2
-       Chaque type du pré-localisateur écoute les fuites d’une distance de la canalisation dans n'import quel direction
-       Chaque matériau du canal  dépend de facteur de transmission (poids)
j'ai besoin d'ecrire un algorithme en recherche opérationnelle répond à Comment on peut installer ces pré-localisateurs sur le réseau
et Si on a N pré-localisateurs ou en peut les installer au cours du réseau
 
Merci d'avance