Discussion :

[thibault67100]

Bonjour, je suis actuellement élève de deuxieme année de prepa maths et j'ai quelques bases en python.
Dans le cadre de mes concours, j'aimerais ( dans les grandes lignes ) créer un programme infomatique qui en fonction de la répartiton de la population dans une région donné, me donne le meilleur emplacement pour construire une centrale de nucléaire, afin de limiter les pertes par effet joule lors du transport de l'électricité. Malheureusement je ne sais pas du tout par ou commencer, et surtout, comment " modeliser" la région et ses paramètres ?
Est ce que quelqu'un serait capable de m'indiquer le début du chemin à suivre ?
Merci d'avance,
Thibault

[petchi]

Hello,

Je te conseille de t'informer sur "l'aide à la décision multicritère".
Ce terme regroupe un ensemble de méthode permettant de comparer plusieurs solution ayant des paramètres spatiaux.

L'algorithme OWA (ordered weighted averaging)
et
L'algorithme AHP (Analytic hierarchy process)
pourront intéresser.

Afin de déterminer l'importance des différents paramètres qui vont te permettre de choisir le meilleur emplacement tu peux également étudier le concept des "fuzzy set" qui pourra t'être utile.

Est ce que tu as un nombre discret de possibilité pour l'emplacement ou est ce que l'emplacement peut être n'importe quels points de l'espace. Si tu as un nombre infini de possibilité tu vas devoir "rasterisé", discrétiser le territoire.

Tu peux encore faire quelque recherche sur les problèmes de type "location allocation" pour trouver d'autre méthode.

[petchi]

Ho et visiblement tu auras besoin de créer les paramètres qui vont te servir a déterminer le meilleur emplacement:

Pour cette partie je te recommande d'utiliser PostGIS, une extension de postgreSQL optimiser pour les requêtes spatiales. (si tu veux pas exemple créer un paramètre: densité de population)

De plus si tu veux être réalistes tu devrais encore intégrer d'autre paramètres (en plus de: densité de population et longueur de câble électrique) du genre impossible de construire sur une forêt (paramètre binaire: forêt = 1 ou 0) ou impossible de construire si la pente > 2% (paramètre binaire pente > 2% = 1 ou 0)... etc

tu peux lire ce papier pour plus d'info:

"Integrating multicriteria analysis and geographic information systems: the ordered weighted averaging (OWA) approach" en anglais.

Bon courage

[dourouc05]

Ça ne serait pas plus simple d'implémenter un facility location avec une seule installation ? La population pourrait être modélisée avec des points dont la demande est proportionnelle à la population (ou la demande totale pour la commune, si tu as ces infos). Pour cette approche, tu peux regarder https://en.wikipedia.org/wiki/Facility_location_problem et les formulations sous forme de programmes mathématiques (http://support.sas.com/documentation...er_sect019.htm) ou des approches plus algorithmiques comme le calcul d'un barycentre (moyenne des points où la demande est concentrée, pondérée par la demande).

[FR119492]

Salut.

le meilleur emplacement pour construire une centrale de nucléaire, afin de limiter les pertes par effet joule lors du transport de l'électricité

L'énoncé du problème me semble curieux. En effet, il est évident que la solution mathématiquement optimale serait de construire ta centrale nucléaire au centre de la ville la plus peuplée, ce qui me semble conduire à quelques dangers.
Jean-Marc Blanc

[Flodelarab]

Bonjour

Au centre ? Pourquoi au centre ? Les 3/4 de la population habitent à l'est.

Et si tu réponds "alors, prenons le barycentre", ce n'est pas bon non plus. Si tu mets un long fil en commun pour 10 personnes (fil qui se sépare à l'extrémité) tu auras moins d'effet Joule que 10 fils pour 10 personnes proches.

[theodorandaipieds]

Ce problème est généralement connu sous le nom du "problème de la caserne des pompiers" (problème NP-hard, très compliqué donc)

Une méthode approximant une solution très satisfaisante est disponible dans le mémoire-projet d'un étudiant de la Louvain School of Management (UCL/Belgique) : "Réalisation d'un logiciel d'aide au groupage d'aide des expéditions chez Magotteaux SA" (directeur: Philippe Chevalier, année académique 2003/2004).

Une bonne aide si tu débutes dans la programmation combinatoire est le livre de "Integer programming" (Laurence Wolsey, Wiley-Interscience ,1998). Cela reste une référence pour une initiation.

Bon amusement.

[ChipsAlaMenthe]

Voilà comment j'aurais procédé pour ce problème.

Etant donné que je connais la répartition de la population, je définierai mon territoire en matrice. Chaque case de la matrice contiendrait un nombre, qui serait plus grand en fonction du nombre de personnes qu'elle inclut (et qui correspondrait donc au nombre de personne, il s'agit donc du "poids").

Ensuite, tout dépend des paramètres et contraintes dont tu dispose, mais globalement il y aura une limite concernant le nombre de centrales (que ce soit limité dans l'énoncé ou simplement par la population totale, par exemple 1 centrale doit fournir de l'énergie pour environ 10000 personnes).

Tu devras ensuite placer chaque centrale sur les cases de la matrice que tu as dessiné. Et là il faudra les placer au bon endroit ^^.
Chaque case alimentée par la centrale devra être marquée.
Après l'algorithme est de trouver celui qui dispersera le mieux les centrales pour qu'elles aient un maximum de point toutes ^^.
Il n'en existe pas beaucoup, mes souvenirs sont assez lointains du coup je ne peux pas t'aider plus loin. Si ça me reviens je te fais signe .

[jzyra]

Bonjour,

J'aurais découpé mon terrtoire géographique en zones que j'aurais stocké dans une martice 2D.
Chaque cellules de ma matrice permet de stocker des informations utilent pour évaluer le risque (densité de population...).
Il faut ensuite une fonction d'évaluation qui va te permettre en fonction d'une cellule donnée (position x et y de la matrice) évalué le risque du placement d'une centrale sur cette zone.

Une fois cette fonction d'évaluation implémentée, tu peux ensuite utiliser un algorithme d'optimisation qui va te permettre de rechercher de façon intélligente la zone comportant le moins de risques.
Il existe plusieurs algorithme pour faire ça : recuit simulé, optimisation par essaims particulaires, recherche par tabous, recherche tabou...

[prgasp77]

globalement il y aura une limite concernant le nombre de centrales (que ce soit limité dans l'énoncé ou simplement par la population totale, par exemple 1 centrale doit fournir de l'énergie pour environ 10000 personnes).

des informations utilent pour évaluer le risque (densité de population...).

Vous vous égarez. Relisez le problème :

le meilleur emplacement pour construire une centrale de nucléaire, afin de limiter les pertes par effet joule lors du transport de l'électricité

@thibault : tu es en face de ce qui s'appelle un Motorway Problem ; et voici une vidéo récréative sur une solution physique (avec des bulles de savon) :
www.youtube.com/watch?v=dAyDi1aa40E