Optimisation sur l'ensemble efficace d'un problème multi-objectifs: Cas discret

Extrait du document

De nombreux secteurs de l'industrie (mecanique, chimie, telecommunications, environnement, transport, etc.) sont concernes par des problemes complexes de grande dimension mettant en jeu des objectifs (criteres) tres importants (prot, co^uts, delai, qualite de service, etc.) a atteindre et pour lesquels les decisions doivent ^etre prises de facon rationnelle et logique. La modelisation traditionnelle n'a connu que des modeles d'optimisation a objectif unique jusqu'a l'apparition d'une nouvelle vision plus proche de la realite et qui consiste a modeliser les problemes de sorte que tous les objectifs pertinents soient pris en consideration. Cette philosophie de multiplicite d'objectifs ou l'optimisation multicriteres semble tres raisonnable et contribue ecacement a l'elaboration de nouveaux systemes d'aide a la decision, qui visent a faciliter la t^ache des decideurs devant des choix complexes, qui s'averent souvent ^etre con ictuels. Dans la pratique, une classe tres importante de problemes peuvent ^etre modeliser sous forme de programmes lineaires multi-objectifs (Multiobjective Objective Lineair Programming)(MOLP) ou les criteres et les contraintes sont tous lineaires et les variables de decision peuvent prendre des valeurs continues, discretes et binaires. Cette famille de modelisation possede un heritage tres riche accumule par la programmation mathematique unicritere, considerablement developpee depuis une cinquantaine d'annees, lorsque G. B. Dantzig proposa l'algorithme du simplexe. L'optimisation lineaire multi-objectifs possede ses racines au 19ieme siecle dans les travaux en economie de Edgeworth et Pareto (1896). Elle a ete utilisee initialement en economie et dans les sciences de management, et graduellement appliquee aux sciences pour l'ingenieur. Contrairement a l'optimisation classique mono-objectif, la solution d'un probleme multi-objectifs n'est pas une solution unique, mais un ensemble de solutions, connu comme l'ensemble des solutions Pareto Optimales ou bien solutions ecaces, orant un bon compromis entre les dierentes fonctions objectifs a optimiser, a partir de lesquelles, il est impossible d'augmenter la valeur d'un objectif sans diminuer d'au moins un autre. Dans de nombreuses situations reelles modelisables par la programmation lineaire multi-objectifs, les variables de decision ne peuvent prendre que des valeurs entieres, dans ce cas on parle, de programmation lineaire multi-objectifs en nombres entiers (MOILP) dont le domaine de decisions n'est plus convexe, ce genre de problemes appartiennent a la classe de l'optimisation non convexe. L'importance de cette famille de problemes d'optimisation a pousse Rokafellar [23] a dire : "The great watershed in optimization isn't between linearity or non linearity but between convexity and nonconvexity". Une preoccupation majeure dans la mise en uvre des systemes d'aide multicriteres a la decision est la denition d'un formalisme permettant de re eter delement les choix du decideur. Dans beaucoup de cas, les criteres sont en con it, sans compter la taille des calculs informatiques impliques dans les algorithmes, la taille de l'ensemble des solutions ecaces habituellement considerable tendent a saturer le decideur jusqu'au point le choix de sa solution preferee devient une mission impossible. En eet, l'enumeration de tout l'ensemble des solutions ecaces n'est pas appropriee car, les decideurs ne sont pas souvent interesses par toutes les solutions ecaces mais d'un sous-ensemble de solutions repondant a certaines preferences. Par consequent, le probleme de l'optimisation d'une fonction lineaire sur l'ensemble des solutions ecaces qui est aujourd'hui, l'un des concepts importants et interessants de la programmation multi-objectifs, il semblait un moyen fructueux pour eviter de tels preoccupations an de mesurer les preferences des decideurs, et distinguer parmi les nombreuses solutions ecaces. Dans le cadre de ce memoire, nous nous sommes interesses au probleme de l'optimisation d'une fonction lineaire sur l'ensemble des solutions ecaces d'un probleme de la programmation lineaire multi-objectifs en nombres entiers. Ce present travail s'articule autour de quatre chapitres. Dans le premier chapitre, des notions de base sur l'optimisation multi-objectifs lineaire en nombre entiers ainsi que quelques methodes de resolution basees sur la theorie de la norme de Tchebychev sont presentees, les principaux resultats de la programmation uni-critere discrete, ou les techniques de separation et evaluation "branch & bound" sont rappelees. Le deuxieme chapitre propose une presentation detaillee du probleme de l'optimisation d'une fonction lineaire sur l'ensemble des solutions ecaces d'un probleme de la programmation lineaire multi-objectifs en nombre entiers. Plus precisement, nous decrivons en detail les deux seuls methodes existantes a savoir Abbas & Chaabane [1] et celle de Jorge [28] illustree par un exemple didactique. Dans le troisieme chapitre, nous abordons notre contribution dans le domaine de l'optimisation d'un critere lineaire sur l'ensemble des points ecaces d'un probleme lineaire multi-objectifs en nombres entiers en se basant sur la resolution d'un programme de la norme de Tchebychev, nous allons discute plusieurs formes equivalentes de ce norme et leurs avantages dans la caracterisation des solutions ecaces. Le quatrieme chapitre est consacre a une validation experimentale de l'algorithme propose, notre implementation est testee sur des exemples de la litterature et des instances generees aleatoirement a l'aide d'un programme que nous avons developpe et implemente sous l'environnement Matlab 7.7. Enn, nous terminons par une conclusion generale en resumant les dierentes demarches suivies dans ce travail et quelques perspectives de recherche.

Introduction générale Chapitre 1 Chapitre 2 Chapitre 3 Conclusion

Donne ton avis !

Ta note :

1 2 3 4 5

Rédige ton avis

Votre commentaire a bien été ajouté. Merci de votre participation !

Vous devez donner une note pour valider votre avis.

Le formulaire n'est pas valide. Vérifiez le commentaire et le captcha.