La minimisation des polynômes et la méthode adaptée du support

La minimisation des polynômes et la méthode adaptée du support

Expériences numériques

Afin d’effectuer une comparaison numérique entre la méthode adaptée et les méthodes de Linprog Solver incorporées dans Matlab Toolbox, une implémentation sous la version Matlab 8.1.0.604 a été développée. Nous avons résolu les 620 problèmes test listés dans le Tableau 4.1, le Tableau 4.2 et le Tableau 4.3 sur un ordinateur personnel avec Intel Celeron N2830 Cadencé avec CPU 2.17 GHz et 2 Go de RAM, fonctionnant sous Windows 7. La comparaison est basée sur des problèmes de programmation linéaire générés aléatoirement. La caractéristique de ces problèmes est que la solution optimale x et le vecteur c sont connus auparavant. Dans notre implémentation, les paramètres d’entrée de la procédure qui génèrent des problèmes linéaires aléatoires sont n et m, respectivement, ils représentent le nombre de variables et le nombre de contraintes.

Le solveur de programmes linéaires de Matlab est Linprog, il comporte trois algorithmes : interior-point-legacy, interior-point et dual-simplex. Les résultats numériques sont rapportés dans les tableaux 4.1, 4.2 et 4.3 où les T(s) et les «Itérs» représentent respectivement la moyenne du temps CPU en secondes et la moyenne du nombre d’itérations des dix problèmes générés pour chaque taille de problème. X La Table 4.1 rapporte les résultats numériques pour des problèmes linéaires, où chaque taille de problème vérifie n − m _ 5. T(s) Ratio et Itérs Ratio représentent, respectivement, les rapports de temps de CPU (temps de CPU de Linprog solver) / (temps de CPU de la méthode Adaptée) et les rapports d’itérations (nombre d’itérations de Linprog solver / nombre d’itérations de la méthode adaptée) pour la taille correspondante.

Paradigme des problèmes de décision multiobjectif

On peut répartir les méthodes d’optimisation multiobjectif en trois grandes familles. Ces familles sont définies en fonction de l’instant où l’on prend la décision d’effectuer ou non un compromis entre les fonctions objectif. Ces trois familles sont :

Les méthodes d’optimisation a priori : Dans ces méthodes, le compromis que l’on désire effectuer entre les différentes fonctions objectif a été déterminé avant l’exécution de la méthode d’optimisation. Pour obtenir la solution de notre problème, il suffira de faire une et une seule recherche et, en fin d’optimisation, la solution obtenue reflétera le compromis que l’on désirait effectuer entre les fonctions objectif avant de lancer la recherche. Ces méthodes sont intéressantes dans le sens où il suffit d’une seule recherche pour trouver la solution. Cependant, il ne faut pas oublier le travail de modélisation du compromis qui a été effectué avant d’obtenir ce résultat. Il ne faut pas, non plus, oublier que le décideur est « humain » et qu’il sera susceptible de constater que la solution obtenue en fin d’optimisation ne le satisfait finalement pas et qu’il souhaite maintenant, après avoir examiné cette solution, une solution qui opère un autre compromis entre les fonctions objectif.

Les méthodes d’optimisation progressive : Dans ces méthodes, on cherchera à questionner le décideur au cours de l’optimisation afin que celui-ci puisse réorienter la recherche vers des zones susceptibles de contenir des solutions qui satisfassent les compromis qu’il souhaite opérer entre les fonctions objectif. Ces méthodes, bien qu’appliquant une technique originale pour modéliser les préférences du décideur, présentent l’inconvénient de monopoliser l’attention du décideur tout au long de l’optimisation. Cet inconvénient n’est pas majeur lorsque l’on a affaire à des problèmes d’optimisation pour lesquels la durée d’une évaluation de la fonction objectif n’est pas importante. Pour les autres problèmes, l’utilisation d’une telle méthode peut être délicate. Il est en effet difficile de monopoliser l’attention du décideur pendant une période qui peut s’étendre sur plusieurs heures en lui posant, de plus, des questions toutes les dix minutes.

Caractéristiques des produits de la laiterie

L’étude des caractéristiques des trois produits fabriqués par la laiterie Rio est une opération très importante, pour la prévision des ventes ainsi que pour le processus de modélisation des chaines logistiques. En effet, il devient difficile de déterminer la méthode adéquate de prévision si on ne connait pas la nature du produit et la période de prévision. En plus, le processus de modélisation ne peut se réaliser sans connaitre les différents objectifs à atteindre et les conditions objectives ou contraintes imposées par les déterminants des produits tels que le temps nécessaire pour l’approvisionnement, la production et la distribution ainsi que la capacité dont dispose l’entreprise et qui limite le volume de production (machines, équipements, heures de travail déterminées par la main-d’oeuvre disponible dans l’entreprise etc. . .). Il convient de noter également qu’il existe des caractéristiques communes à ces trois sortes de produits telles que les étapes de la production, la plupart de leurs composants, la période de validité ainsi que des caractéristiques différentes telles que la qualité, le coût de revient et le profit résultant de la vente de chaque unité de ces produits. Après une étude détaillée des coûts d’achat des matières premières, de leur stockage, des coûts de production et de distribution des produits finis, des différentes étapes de la production du yaourt ainsi que sa durée de validité, on a dressé le tableau suivant :

Conclusion générale

Cette thèse de recherche concerne la minimisation des polynômes par une nouvelle méthode dite méthode adaptée du support. Notre objectif a été de montrer que la méthode adaptée du support peut être utilisée efficacement dans la résolution de programmes semi-définis positifs, et en particulier pour résoudre exactement des problèmes linéaires et des problèmes quadratiques convexes. L’excellence des résultats obtenues par l’utilisation de cette approche ont pu être démontrées dans le chapitre 4. De ce fait, nous avons pu concevoir une nouvelle méthode pour résoudre un programme linéaire multiobjectif dont les variables de décision sont bornées. Pour cela, on a commencé par rappeler les notions fondamentales de l’optimisation semi-définie positive, ensuite on a défini quelques théorèmes et propriétés concernant l’optimisation quadratique convexe pour la minimisation des polynômes homogènes de degré 2 avec des contraintes linéaires, on a aussi proposé la méthode adaptée pour la résolution des programmes linéaires mono-objectif avec des variables non négatives.

Enfin, on a présenté les différents concepts utilisés en optimisation linéaire multiobjectif et nous avons étudié un programme linéaire multiobjectif à variables bornées, et ce en utilisant la méthode adaptée du support. Ainsi, nous avons proposé une nouvelle procédure de recherche d’un point efficace initial, un nouveau test d’efficacité d’une variable non basique et une nouvelle procédure de recherche de tous les points efficaces associés à notre premier point efficace, et ça en s’inspirant du travail développé par S.Radjef et M.O.Bibi [82, 70]. L’algorithme nous permet aussi de trouver les points _−efficaces, et ce en exploitant le critère de suboptimalité de la méthode adaptée en mono-objectif. Notons que la méthode adaptée du support a des propriétés intéressantes. En effet :

– Elle est innovante dans la mesure où elle essaye de s’attaquer à des situations multiobjectif pour lesquelles les méthodes de résolutions sont absentes ou artificielles. Ces situations englobent les problèmes d’optimisation en présence de nombreux critères. – Elle est axiomatisée. D’une part, elle est fondée sur des concepts tels que l’efficacité et l’efficacité qui sont motivés et justifiés par des interprétations intelligibles. D’autre part, l’analyse et les choix effectués pendant la résolution reposent sur des principes qui peuvent sembler raisonnables.

Table des matières

Résumé
Introduction générale
I Optimisation mono-objectif
1 L’optimisation semi-définie positive (SDP)
1.1 Préliminaires matriciels
1.1.1 Notations.
1.1.2 Matrices semi-définies positives.
1.2 Optimisation SDP.
1.3 Définitions primale et duale du problème.
1.3.1 Le problème primal.
1.3.2 Le problème dual
1.4 Réalisabilités primale et duale.
1.5 Exemples de modélisation SDP
1.6 Programmation linéaire .
2 Minimisation des polynômes homogènes de degré 2
2.1 Introduction
2.2 Notions de base sur les polynômes
2.2.1 Notations.
2.2.2 Propriétés.
2.2.3 Degré d’un polynôme.
2.2.4 Polynômes remarquables
2.3 Minimisation des polynômes homogènes de degré 2.
2.4 Minimisation d’un polynôme homogène d’ordre 2 sur un simplexe standard.
3 La méthode adaptée pour la résolution d’un programme quadratique convexe
3.1 Introduction
3.2 Programmation quadratique convexe.
3.2.1 Les formes quadratiques
3.2.2 Notion de convexité.
3.2.3 Problème quadratique convexe (PQC)
3.3 Position du problème et définitions
3.4 Formule d’accroissement de la fonction objectif
3.5 Critère d’optimalité.
3.6 Critère de suboptimalité
3.7 Méthode de résolution
3.7.1 Construction de la direction d’amélioration adaptée l.
3.7.2 Calcul du pas maximal θ0
3.7.3 Estimation de suboptimalité
3.7.4 Changement de support
3.8 Algorithme de résolution
3.9 Exemple numérique
4 La méthode adaptée pour la résolution d’un programme linéaire
4.1 Introduction
4.2 Position du problème et définitions
4.2.1 Position du problème
4.2.2 Définitions.
4.3 Critère d’optimalité
4.4 Critère de suboptimalité
4.5 Méthode de résolution
4.5.1 Construction d’une nouvelle solution réalisable
4.5.2 Calcul de β(¯ x, JB)
4.5.3 Changement de support
4.6 Algorithme de la méthode
4.7 Étude d’un exemple numérique
4.8 Expériences numériques
4.9 Conclusions
II Optimisation multiobjectif
5 Préliminaires et considérations théoriques
5.1 Introduction .
5.2 Concepts et terminologie
5.2.1 Les alternatives et les critères
5.2.2 Paradigme des problèmes de décision multiobjectif
5.2.3 Les différentes problématiques multiobjectif.
5.3 Les structures de préférences.
5.3.1 Les relations binaires et les ordres.
5.3.2 Les structures de préférences
5.4 L’espace de décision et l’espace objectif.
5.5 L’optimisation multiobjectif.
5.6 Les concepts d’optimalité
5.6.1 Optimalité de Pareto.
5.6.2 Optimalité au sens de Slater
5.7 Définitions
5.7.1 La surface du compromis
5.7.2 Représentation de la surface du compromis sur Matlab pour un problème à deux fonctions objectif
5.7.3 Fonction utilité
5.7.4 Point idéal.
5.7.5 Table des gains
5.7.6 Point nadir
6 Quelques méthodes d’optimisation multiobjectif
6.1 La méthode de pondération
6.2 La méthode du compromis.
6.3 Les méthodes hybrides
6.4 La méthode dite du “but à atteindre”
6.5 La méthode dite du “but programmé”.
6.6 La méthode du Simplexe Multiobjectif.
6.6.1 Trouver une solution de base réalisable
6.6.2 Trouver un point extrême efficace
6.6.3 Générer l’ensemble des points extrêmes efficaces
6.6.4 Exemple numérique.96
7 La méthode adaptée du support pour la résolution d’un programme linéaire multiobjectif
7.1 Introduction
7.2 Position du problème et définitions générales
7.3 Définition des solutions efficaces et leurs propriétés.
7.4 Définition des solutions –efficaces et leurs propriétés
7.5 Procédure de recherche d’un point efficace initial.
7.5.1 Trouver un point efficace initial en utilisant la méthode d’Isermann
7.5.2 Trouver un point efficace initial en utilisant la procédure de Benson-Radjef-Bibi.106
7.6 Recherche des solutions efficaces
7.6.1 Test d’efficacité d’une variable non basique.
7.6.2 Construction de la nouvelle solution efficace.
7.7 L’algorithme de la méthode
7.8 Exemple numérique
7.9 Exemple sur la modélisation mathématique de la chaîne logistique
7.9.1 Présentation de la laiterie
7.9.2 Caractéristiques des produits de la laiterie
7.9.3 Résolution du modèle à l’aide de la méthode adaptée du support
7.10 Conclusion
Conclusion générale
Bibliographie
Annexe
A Introduction
B Utilisation du langage du logiciel Matlab
C Implémentation de la méthode adaptée multiobjectif sous Matlab
C.1 Génération des programmes aléatoires
C.2 Méthode de Benson
C.3 Choix du critère k0

Télécharger le rapport complet