• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Mémoire de Maîtrise
DOI
10.11606/D.45.2008.tde-11042008-163904
Document
Auteur
Nom complet
Francisco Nogueira Calmon Sobral
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2008
Directeur
Jury
Birgin, Ernesto Julian Goldberg (Président)
Perez, Ana Friedlander de Martinez
Silva, Paulo José da Silva e
Titre en portugais
Programação em dois níveis: reformulação utilizando as condições KKT
Mots-clés en portugais
complementaridade
condições KKT
funções NCP
programação em dois níveis
programação não linear
Resumé en portugais
Em um problema de natureza hierárquica, o nível mais influente toma certas decisões que afetam o comportamento dos níveis inferiores. Cada decisão do nível mais influente é considerada como fixa pelos níveis inferiores, que, com tais informações, tomam decisões que maximizam seus objetivos. Essas decisões podem influenciar os resultados obtidos pelo nível superior, que, por sua vez, também anseia pela decisão ótima. Em programação matemática, este problema é modelado como um problema de programação em níveis. Neste trabalho, consideramos uma classe particular de problemas de programação em níveis: os problemas de programação matemática em dois níveis. Estudamos uma técnica de resolução que consiste em substituir o problema do nível inferior por suas condições necessárias de primeira ordem, que podem ser formuladas de diversas maneiras, conforme as restrições de complementaridade são modificadas. O novo problema torna-se um problema de programação não linear e pode ser resolvido com algoritmos clássicos de otimização. Com o auxílio de condições de otimalidade de primeira e segunda ordem mostramos as relações entre o problema original e o problema reformulado. Aplicamos a técnica a problemas encontrados na literatura, analisamos o seu comportamento e apresentamos estratégias para eliminar certos inconvenientes encontrados.
Titre en anglais
Bilevel programming: reformulation using KKT conditions.
Mots-clés en anglais
bilevel programming
complementarity
KKT conditions
NCP functions
nonlinear programming
Resumé en anglais
In problems of hierarchical nature, the choices made by the most influential level - the so-called leader - affect the behavior of the lower levels. For each one of the leader's decisions there is a response from the lower levels, which maximizes the value of their respective objectives. These optimal choices, in return, may have influence in the results achieved by the leader, which also wants to make the optimal choices. In mathematical programming, this kind of problem is described as a multilevel programming problem. The present work considers a specific kind of multilevel problem: the bilevel mathematical problem. We study a resolution technique which consists in replacing the lower level problem by its necessary first order conditions, which can be formulated in various ways, as complementarity constraints occur and are modified. The new reformulated problem is a nonlinear programming problem which can be solved by classical optimization methods. Using first and second order optimality conditions, we show the relations between the original bilevel problem and the reformulated problem. We apply the described technique to solve a set of bilevel problems taken from the literature, analyse their behavior and discuss strategies to prevent undesirable difficulties that may arise.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
dissertacao.pdf (1.04 Mbytes)
Date de Publication
2008-07-22
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
Centro de Informática de São Carlos
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2021. Tous droits réservés.