WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Optimisation du réseau du gaz lift dans la partie nord du champ de Hassi Messaoud


par Naima & Amel CHERAD & SID
Univesité des sciences et de la technologie Houari Boumedienne - Ingénieur d'état en recherche opérationnelle 2009
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

Chapitre 5

Approche de resolution

5.1 Introduction

La notion de complexité des problèmes est très importante, car si un problème est identiflé comme facile, on connait un algorithme fini et effi cace pour le résoudre, par contre s'il est identiflé comme étant un problème complexe il sera diffi cile de trouver un algorithme effi cace pour le résoudre, il est alors justiflé de se contenter d'exigences plus limitées: résolution approchée du problème posé, résolution d'un problème voisin plus simple.

L'exécution des méthodes dites exactes (programmation dynamique, séparation et évaluation) pour la résolution des problèmes NP-Diffciles risque de prendre un temps de calcul considérable, notamment si la taille du problème est très grande.

Afin d'éviter ce genre de situation, on se contente souvent d'une solution dite approchée donnée par certaines méthodes appelées "méthodes approchées" ou "heuristiques", et dont la valeur de la fonction objectif correspondante se rapproche de celle de la solution exacte. Vu qu'on est en présence d'un problème non linéaire assez complexe, nous proposons d'utiliser une "heuristique" comme méthode de résolution.

5.2. Heuristiques[9]

5.2 Heuristiques[9]

Definition:

Heuristique (du grec heuriskêin, << trouver >> ) est un terme de didactique qui signife l'art d'inventer, de faire des découvertes. C'est en sociologie, une discipline qui se propose de dégager les règles de la recherche scientifque. En optimisation combinatoire, théorie des graphes et théorie de la complexité, une heuristique est un algorithme qui fournit rapidement (en temps polynomial) une solution réalisable, pas nécessairement optimale, pour un problème d'optimisation NP-diffcile. Une heuristique, ou méthode approximative, est donc le contraire d'un algorithme exact qui trouve une solution optimale pour un problème donné. L'intérêt de l'heuristique étant que pour les problèmes NP-diffciles, la plupart des algorithmes exacts connus sont de complexité exponentielle et donc sans aucun intérêt en pratique. On utilise une heuristique pour obtenir une première solution réalisable dans un processus de résolution exacte. Généralement une heuristique est conçue pour un problème particulié, en s'appuyant sur sa structure propre, mais les approches peuvent contenir des principes plus généraux. On parle de métaheuristique pour les méthodes approximatives générales, pouvant s'appliquer a des différents problèmes. La qualité d'une heuristique peut s'évaluer selon deux critères scientifques :

1) Critère pratique, ou empirique: on implémente l'algorithme approximatif et on évalue la qualité de ses solutions par rapport aux solutions optimales (ou aux meilleures solutions connues). Ceci passe par la mise en place d'un benchmark (ensemble d'instances d'un même problème accessible a tous).

2) Critère mathématique: il faut s'assurer que l'heuristique garantit des performances. La garantie la plus solide est celle des algorithmes approchés, sinon il est intéressant de démontrer une garantie probabiliste, lorsque l'heuristique fournit souvent, mais pas toujours, de bonnes solutions.

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy