Respostas
Resposta:
introdução de variáveis de folga sem acarretar qualquer dificuldade acrescida
50 3. Problema de Programação Matemática com Restrições de Complementaridade
ao problema. Como veremos neste e em capítulos posteriores, em muitas aplicações do
MPEC as matrizes E e M são quadradas, sendo E a identidade e M \u2208 PSD. A existência
de restrições de complementaridade na formulação anterior do MPEC faz com que este
problema também se designe por Problema de Programação Matemática com Restrições
de Complementaridade. Consoante a função f seja linear ou não linear este problema é
designado por MPEC linear ou não linear, respectivamente.
Na formulação original do MPEC, y é a variável (de desenho) do primeiro nível e z é a
variável (de estado) do segundo nível. Na formulação linear do MPEC (3.4) as restrições de
equilíbrio constituem um problema linear complementar paramétrico com parâmetro y e com
as variáveis primárias z e w a satisfazer
0 \u2264 z \u22a5w \u2265 0
Estas restrições são equivalentes a
zi = 0 \u2228 wi = 0 \u2200i
Podemos assim concluir que o MPEC (3.4) é um problema de optimização NP-difícil, uma vez
que a determinação de uma sua solução admissível é um GLCP, que tem essa complexidade
[69].
3.2 Redução de um Problema de Dois Níveis a um Programa
com Restrições de Complementaridade
Nos problemas de programação de dois níveis existe uma hierarquia de problemas de optimi-
zação onde as restrições de um dos problemas (o chamado problema do nível superior ou do
primeiro nível) são definidas em parte por um segundo problema de optimização paramétrico
(o problema do nível inferior ou do segundo nível). Este tipo de problemas ocorre em diversas
sendo o primeiro mais utilizado, uma vez que na sucessão desses