SAAFA-76-MRRRCH
Programmation Bi-niveaux Linéaire
Existence et caracterisation des solutions du (P BL)
Beaucoup d’auteurs ont cherche à caracteriser les solutions optimales d’un (P BL) ainsi que les conditions de leur existence. Candler et Townsley [30], Bard et Falk [17] ont établi l’existence d’une solution optimale en un point extrˆeme du domaine réalisable S ; Bialas et Karwan [25, 26] ont démontré ce résultat sous l’hypothèse que S est borné. G. Savard (1989)(cité dans [12]) a également montré que dans le cas o`u la region induite est non vide, il existe au moins une solution optimale pour le (P BL) atteinte en un point extrˆeme de l’ensemble S et que ce résultat est valable mˆeme dans le cas de presence des contraintes du niveau supérieur. Pour chercher les conditions d’existence des solutions pour le (P BL) et pouvoir caractériser ces solutions, nous allons regarder un peu la géométrie de son ensemble réalisable (région induite RI). Nous considérons la formulation du (P BL) sous forme d’un programme standard, (P BL) 0 , et nous posons les hypothèses suivantes. H 1. S est un ensemble non vide et compact. H 2. R(x) est réduit à un singleton. Dans le théorème suivant, il est montré que quand le problème est écrit sous forme d’un programme mathématique standard, la région induite résultante est composée de faces connectées de S et qu’une solution se produit en un sommet. Théorème 1.1. [15] La région induite peut ˆetre écrite d’une manière équivalente comme une contrainte d’égalité linéaire composée des hyperplans de support de s
Méthodes de résolution du (P BL)
Pour la resolution du (P BL) , de nombreux algorithmes ont été mis au point et particulièrement pour le cas linéaire (voir [36]). Ces algorithmes peuvent ˆetre classés en trois principales catégories. a) Méthodes basées sur la reformulation KKT : les méthodes développées dans cette catégorie sont nombreuses et requièrent la transformation du problème en un problème d’optimisation à un seul niveau en utilisant les conditions KKT. Donc au lieu de travailler avec le problème (P BL) on travaille avec le problème (P BL)KKT . A cause de la présence des contraintes de complémentarité dans le système KKT, le problème résultant est non linéaire. Les approches développées dans cette catégorie peuvent ˆetre résumées en : – Approche basée sur la programmation entière mixte : J. Fortuny-Amat et B. McCarl [50] ont proposé, pour la résolution du problème (P BL)KKT de convertir les contraintes de complémentarité en contraintes linéaires en ajoutant des variables binaires. 21 Programmation à deux niveaux – Approche du pivot de complémentarité : le premier qui a développé un algorithme de pivot de complémentarité était Bialas et al.(voir [22]). A chaque itération, l’algorithme du pivot de complémentarité (PCP) calcule un point réalisable (x, y) pour le problème original de telle fa¸con que la fonction objectif du Leader prenne une valeur au plus égale à un nombre α. Ce paramètre est mis à jour à chaque itération et le processus s’arrˆete lorsque aucune solution réalisable ne peut ˆetre trouvée. J´udice et Faustino ont introduit un problème appelé problème de complémentarité linéaire séquentielle pour la résolution des problèmes de programmation bi-niveaux linéaires-quadratiques. Leur approche peut ˆetre vue comme une combinaison entre la technique de Branch and Bound et la méthode d’énumération de points extrˆemes (voir [56, 57, 22]). – Approche basée sur les techniques Branch and Bound : l’idée de cette approche est de supprimer le terme de complémentarité et résoudre le programme linéaire résultant. A un noeud donné de l’arbre Branch and Bound qui ne vérifie pas les contraintes de complémentarité, la séparation se fait de la manière suivante : deux noeuds seront créés, l’un avec (v, u) = 0Rn2+m2 comme une contrainte additionnelle et l’autre avec (y, w) = 0Rn2+m2 . Bard et Falk [17] et Fortuny-Amat et McCarl [50] ont développé des algorithme basés sur la technique Branch and Bound pour le cas linéaire. Cette approche a été adaptée par Bard et Moore [18] pour le cas linéaire-quadratique et par Bard [14] et Edmunds et Bard pour le cas quadratique [16]. – Approche basée sur les fonctions de pénalité : après transformation du problème original en un problème à un seul niveau, une pénalité exacte est utilisée. Dans Anandalingam et White [7][8], la fonction pénalité utilisée est la différence entre les valeurs des fonctions objectifs primale et duale du Suiveur. Campˆelo et Scheimberg [29] ont utilisé également une pénalisation, mais cette fois-ci des contraintes de complémentarité. b) Méthodes basées sur l’énumération de points extrˆemes : ces méthodes sont développées pour le cas linéaire. Une propriété importante des problèmes de programmation bi-niveaux linéaires est que les points extrˆemes de la région réalisable du (P BL) sont les points extrˆemes de la région des contraintes S et que la solution optimale du problème est l’un de ces points. En se basant sur cette idée, beaucoup d’auteurs ont développé des algorithmes pour la résolution du (P BL) . Bialas et Karwan [25] ont proposé le Kieme ` meilleur algorithme. Sous la condition que la région 22 Programmation à deux niveaux induite RI est bornée et que l’ensemble des réactions rationnelles R(x) est réduit à un singleton, cet algorithme trouve la solution globale du problème. Les mˆemes auteurs [26] ont proposé une autre méthode mais qui aboutit à une solution locale. Bard [13] a développé un algorithme de recherche grille. Cet algorithme calcule une borne inférieure et une borne supérieure de la valeur optimale cherchée. Hansen et al.[12] ont présenté un algorithme de type Branch and Bound qui n’est pas basé sur les conditions KKT du niveau inférieur, mais qui cherche à déterminer les contraintes satisfaites ainsi que les variables du suiveur égales à zero au point optimal. c) Méthodes basées sur les heuristiques : dans cette catégorie on peut trouver des algorithmes basés sur les algorithmes génétiques [90, 53], des algorithmes basés sur les réseaux de neurones [58], des algorithmes utilisant le recuit simulé. d) Autres méthodes : d’autres méthodes ont été proposées par plusieurs auteurs dans le but de résoudre le cas non linéaire sous différentes hypothèses. On peut citer : – Méthodes de descente : proposées par Vicente et al.[87] pour le cas quadratique convexe, i.e., les problèmes o`u les deux fonctions objectifs sont quadratiques et o`u les contraintes sont linéaires. Falk and Liu [48] ont également proposé un algorithme de descente appelé algorithme du Leader prédominant vu le rˆole joué par le Leader dans le processus de prise de décision. – Méthodes de fonctions de pénalité : ces méthodes sont généralement limitées au calcul des points stationnaires et optimums locaux. Les premiers auteurs ayant développé ce genre de méthodes sont Aiyoshi et Shimizu [1, 2]. Leur approche consistait en le remplacement du problème du niveau inférieur par un problème pénalisé en introduisant un paramètre de pénalité. Ishizuka et Aiyoshi [55] ont proposé une méthode à double pénalité o`u cette fois-ci les deux fonctions objectifs (les fonctions du Leader et du Suiveur) sont pénalisées. – Méthodes de région de confiance : dans ces méthodes itératives, l’idée est l’approximation, à chaque itération, du problème original par un modèle de mˆeme type [35](approximations linéaires de la fonction objectif du Leader ainsi que ses contraintes, et des approximations quadratiques de 23 Programmation à deux niveaux la fonction objectif du Suiveur). Un algorithme de région de confiance a été développé pour les problèmes sans contraintes du Leader et o`u le programme du Suiveur est convexe avec des contraintes linéaires (voir Liu et al.[59]).
|
Table des matières
Table des matières
Introduction générale
1 Programmation à deux niveaux
1.1 Formulation d’un PB
1.2 Programmation Bi-niveaux Linéaire
1.2.1 Formulation mathématique
1.2.2 Exemple de problème bi-niveaux linéaire
1.2.3 Définition du (P BL)
1.2.4 Nouvelle définition du (P BL)
1.2.5 Complexité du (P BL)
1.2.6 Propriétés du (P BL)
1.2.7 Existence et caractérisation des solutions du (P BL)
1.3 Résolution de (P BL)
1.3.1 Reformulation du (P BL)
1.3.2 Méthodes de résolution du (P BL)
2 Programmation DC
2.1 Eléments d’analyse convexe
2.1.1 Ensembles convexes
2.1.2 Fonctions convexes
2.1.3 Sous-différentiabilité
2.2 Méthode DC
2.2.1 Fonctions DC
2.2.2 Programmation DC
2.2.3 Dualité en programmation DC
2.2.4 Conditions d’optimalité en programmation DC
2.2.5 Algorithme de programmation DC : DCA
2.2.6 Optimisation DC polyédrale et convergence finie de DCA
3 Methodes de penalite
3.1 Introduction
3.2 Pénalité extérieure
3.2.1 Description de la méthode
3.2.2 Convergence de la méthode
3.3 Pénalité intérieure (barrière)
3.3.1 Description de la méthode
3.3.2 Convergence de la méthode
3.4 Pénalité exacte
3.5 Remarques sur les méthodes de pénalité
4 La méthode DC pour la résolution du (P BL) 53
4.1 Reformulation du (P BL)
4.2 Reformulation via une pénalité exacte
4.3 DCA pour la résolution du problème pénalise
4.3.1 Algorithme DCA
4.3.2 Calcul du point initial pour DCA
4.3.3 Résultats numériques
4.4 Résolution du (P BL) par les fonctions pénalite
4.4.1 Résultats théoriques
4.4.2 Algorithme PBLP
4.4.3 Résultats numériques
4.5 Conclusion
Conclusion generale
Bibliographie
Télécharger le rapport complet
