MÉTODOS DE SOLUÇÕES. Muitos são os métodos utilizados na literatura para encontrar soluções de problemas biní- veis. Para alguns desses problemas, mais de uma técnica é usada para resolvê-los. Os métodos são: de máxima descida, métodos de pontos extremos, métodos de branch and bound, métodos de penalidades, técnicas de restauração inexata, regiões de confiança, entre outros. A seguir é descrita a ideia principal de alguns deles. Os métodos baseados em direções de descida calculam uma direção que faz produto interno negativo com o gradiente da função objetivo do primeiro nível e em seguida escolhem o tamanho do passo que será dado nesta direção para que o novo ponto seja viável. Os passos são repetidos até que alguma condição de otimalidade seja satisfeita. Nesta classe, estão os métodos que incluam direções de descida que são projetados para calcular pontos estacionários e mínimos locais. Um exemplo clássico é o algoritmo de máxima descida estendido para problemas de programação biníveis não lineares apresentados por (SAVARD; XXXXXX, 1994). O método dos pontos extremos, também conhecido como o algoritmo K-ésimo melhor vér- tice ou Kth-best foi introduzido por Xxxxxx e Xxxxxx (1978) para resolver o PPB linear. Dado que o PPB é linear, é possível mostar que sua solução encontra-se em um dos vértices de sua região viável. O funcionamento do algoritmo consiste em caminhar pelos vértices do poliedro em busca de vértice (xK, yK) com menor valor de F(x, y) e que pertença à região induzida ℜ. O método de branch and bound é amplamente utilizado para PPB convexos. Em Bard (1988) o algoritmo foi projetado para resolver eficientemente o PPB quando a função objetivo do nível superior e o conjunto de restrições são convexos, e o problema do nível inferior é um problema de programação quadrática. Embora esteja associado a grandes esforços com- putacionais ele também é capaz de calcular mínimos globais. Várias abordagens exploram a complementaridade entre os multiplicadores e as variáveis de folga que surgem a partir das condições KKT do problema de nível inferior. De acordo com Xxxxxxx e Xxxxxxx (1994), esse é o caso dos algoritmos propostos por Xxxx e Xxxx (1982) e Fortuny-Amat e XxXxxx (1981) para o caso linear, Bard e Xxxxx (1990) para o caso linear-quadrático e Al-Khayyal, Xxxxx e Parda- los (1992), Bard (1988) e Xxxxxxx e Bard (1991) para o caso quadrático. Usando diferentes estratégias de ramificação, Xxxxxx, Xxxxxxx e Xxxxxx (1992) propuseram um algoritmo Branch and Bound para a soluç...
