Slide - Programação Não Linear - Métodos - 2024-1

UNIVERSIDADE FEDERAL DO PARANÁ (UTFPR) Câmpus Medianeira Curso: Engenharia de Produção Departamento de Produção e Administração (DAPRO) Disciplina: Pesquisa Operacional PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR MÉTODO DE NEWTON Usado na otimização de problemas irrestritos com uma única variável. A ideia do método é trabalhar com uma aproximação quadrática da função objetivo f(x). Para tanto, trunca-se a série de Taylor após o termo da segunda derivada, assim temos: 𝑓 𝑥𝑖+1 ≈ 𝑓 𝑥𝑖 + 𝑓′ 𝑥𝑖 . 𝑥𝑖+1 − 𝑥𝑖 + 𝑓′′ 𝑥𝑖 . (𝑥𝑖+1−𝑥𝑖)2 2 , sendo 𝑥𝑖 a solução inicial. Derivando 𝑓 𝑥𝑖+1 , obtém-se 𝑓′ 𝑥𝑖+1 ≈ 𝑓′ 𝑥𝑖 + 𝑓′′ 𝑥𝑖 . 𝑥𝑖+1 − 𝑥𝑖 , pois 𝑥𝑖 , 𝑓 𝑥𝑖 , 𝑓′ 𝑥𝑖 e 𝑓′′ 𝑥𝑖 são constantes. Fazendo a derivada igual a zero, vem: 𝑓′ 𝑥𝑖 + 𝑓′′ 𝑥𝑖 . 𝑥𝑖+1 − 𝑥𝑖 = 0. Isolando 𝑥𝑖+1, obtemos: 𝑥𝑖+1 = 𝑥𝑖 − 𝑓′(𝑥𝑖) 𝑓′′(𝑥𝑖) . Regra de parada: 𝑥𝑖+1 − 𝑥𝑖 ≤ 𝜀 (𝑒𝑟𝑟𝑜) OBS.: assegurar que a função objetivo é côncava quando o problema é de maximização e convexa para problemas de minimização. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR MÉTODO DE NEWTON EXEMPLO 1. Utilizar o método de newton para minimizar f(x) = 3x4 – 8x3 + 6x2 + 2, com x1 = -0,5 (solução inicial) e 𝜀 = 0,0001. 𝑥𝑖+1 = 𝑥𝑖 − 12𝑥𝑖 3 − 24𝑥𝑖 2 + 12𝑥𝑖 36𝑥𝑖 2 − 48𝑥𝑖 + 12 = 𝑥𝑖 − 𝑥𝑖 3 − 2𝑥𝑖 2 + 𝑥𝑖 3𝑥𝑖 2 − 4𝑥𝑖 + 1 SOLUÇÃO EXEMPLO 1. 𝑥𝑖+1 = 𝑥𝑖 − 𝑓′(𝑥𝑖) 𝑓′′(𝑥𝑖) SOLUÇÃO: xi = -0,0000373 e f(xi) = 2,000000008, com erro <= 0,0001 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR MÉTODO DO GRADIENTE Pode ser usado em otimização irrestrita de problemas com variáveis múltiplas. Considere o problema de maximização de uma função f(x) , com x = (x1,...,xn), côncava e diferenciável, sendo o sistema de equações: 𝜕𝑓 𝜕𝑥1 = 0 ⋮ 𝜕𝑓 𝜕𝑥𝑛 = 0 difícil de ser resolvido analiticamente. Devendo-se então aplicar um método numérico, sendo o método do gradiente uma das opções. Considerando-se que f(x) cresce mais rapidamente na direção do seu gradiente (𝛻f(x)), busca-se uma sequência de pontos xk e xk+1 , tais que: 𝒙𝑘+1 = 𝒙𝑘 + 𝑟𝑘𝛻𝑓(𝒙𝑘), onde 𝑟𝑘 > 0 é o tamanho ótimo do degrau em xk. Para se determinar 𝑟 = 𝑟𝑘 , maximiza a função ℎ 𝑟 = 𝑓[𝒙𝑘 + 𝑟𝑘𝛻𝑓(𝒙𝑘)] . O procedimento termina quando 𝛻𝑓(𝒙𝑘) = 0, com certa tolerância ε. EXEMPLO 2. Use o método do gradiente para 𝑀𝑎𝑥 𝑓 𝑥1, 𝑥2 = 4𝑥1 + 6𝑥2 − 2𝑥1 2 − 2𝑥1𝑥2 − 2𝑥2 2. Solução inicial: 𝑿𝟎 = 1,1 . PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR SOLUÇÃO EXEMPLO 2. MÉTODO DO GRADIENTE 𝜕𝑓 𝜕𝑥1 = 4 – 4x1 – 2x2 𝜕𝑓 𝜕𝑥2 = 6 – 4x2 – 2x1 X𝟎 = (1,1). 1º Iteração: 𝛻(f(1,1)) = (-2,0). 𝑿𝟏 = 𝑿𝟎 + r 𝛻(f(𝑿𝟎)) = (1,1) + r(-2,0) ➔ 𝑿𝟏 = (1 – 2r, 1) H(r) =f(𝑿𝟏) = 4(1 – 2r) + 6 – 2(1 – 2r)^2 – 2(1 – 2r) – 2 H’(r) = -8 -4(1 – 2r)(-2) + 4 = 0 ➔ 1 – 2r = 4/8 ➔ r = ¼ ➔ X1 = (1/2, 1) 2º Iteração: 𝛻(f(1/2,1) = (0,1). X2 = X1 + r 𝛻(f(X1)) = (1/2, 1) + r(0,1). X2 = (1/2, 1 + r) H(r) = f(X2) =2+6+6r-1/2-1-r-2(1+r)^2 = 13/2+5r-2-4r-2r^2 = 9/2 + r – 2r^2. H’(r) = 1 – 4r = 0 ➔ r = 1/4 ➔ X2 = (1/2, 5/4) e assim por diante até X=(0,335; 1,328), aproximadamente. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR SOLUÇÃO EXEMPLO 2. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR MÉTODOS NUMÉRICOS P/ OTIMIZAÇÃO COM RESTRIÇÕES. MÉTODO DAS FUNÇÕES DE PENALIDADES Seja o problema: Min f(x) s.a. gi(x)<=0 , com i=1,…,l hj(x) = 0 , com j=1,…,m Usando o método das penalidades, o problema pode ser transformado em irrestrito. Assim, pode-se escrever o problema na forma: Min F(x,μ) = f(x) + Q(x), sendo Q(x) uma função de penalidade que é formada por g(x) e h(x). Q(x) =𝑟ℎ σ𝑗=1 𝑚 (ℎ𝑗(𝒙) 2) + 𝑟𝑔(σ𝑖=1 𝑙 (max 0, 𝑔𝑖 𝒙 )2) Onde r>=0 e é atualizado pelo produto: rk+1 = rk.C, sendo C > 1. Assim, r tende para infinito no processo iterativo. Violação na restrição de igualdade implica em penalidade do termo rh[hj(x)]2. Se g(x)<=0, a expressão Max{0,g(x)} é nula, caso contrário tem-se a penalidade rg[g(x)]2. O processo de otimização inicia-se em um ponto x0 que pode estar na região factível ou não. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR MÉTODOS NUMÉRICOS P/ OTIMIZAÇÃO COM RESTRIÇÕES. MÉTODO DAS FUNÇÕES DE PENALIDADES PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR MÉTODOS NUMÉRICOS P/ OTIMIZAÇÃO COM RESTRIÇÕES. MÉTODO DAS FUNÇÕES DE PENALIDADES EXEMPLO 3. Min f(x1,x2) = (x1 – 2)4 + (x1 – 2x2)2 s.a. x12 – x2 = 0. Usando o método das penalidades. Fazer x1 = (0,0) (solução inicial), 𝑟1 = 0,1 e C = 10. Parar o algoritmo quando (x12 – x2)2 < 0,00001. SOLUÇÃO EXEMPLO 3. Min F = (x1 – 2)4 + (x1 – 2x2)2 + r(x12 – x2)2 Otimizando F por um método de otimização irrestrito, obtém-se: x1=0,946 e x2=0,894, aproximadamente. Exemplo 4 Min f(x1,x2) = (x1 – 2)2 + (x1 – 2x2)2 s.a. x2 – x1 2 >= 0 Solução: Min f(x1,x2) = (x1 – 2)^2 + (x1 – 2x2)^2 + r(max{0, -x2 + x1^2})^2 . x1=0,816 e x2=0,665 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR MÉTODOS NUMÉRICOS P/ OTIMIZAÇÃO COM RESTRIÇÕES. MÉTODO DAS FUNÇÕES DE PENALIDADES PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR PROGRAMAÇÃO QUADRÁDITCA A F.O. tem variável com grau 2 e as restrições são lineares. Seja o problema: Max f(X) = CTX + XTQX s.a. AX <= b X >=0 ou -X <= 0 (para aplicar as KKT) Sendo XTQX : forma quadrática. Considera-se Q matriz simétrica e negativa definida, sendo f estritamente côncava. Aplicando as condições KKT, obtém-se −𝟐𝑸 𝑨𝑇 −𝑰𝑴 𝟎 𝑨 𝟎 𝟎 𝑰𝑠 . 𝑿 𝚲 𝑴 𝑺 = 𝑪 𝒃 𝜇𝑗𝑥𝑗 = 0 = 𝜆𝑖𝑠𝑖 para todo i e j. 𝑿, 𝜦, 𝜧, 𝑺 ≥ 𝟎 Obs.: ao escolher uma variável Não básica para entrar na base, não considere a não básica cuja variável de complementaridade (pares: (𝜇𝑗, 𝑥𝑗) e (𝜆𝑖, 𝑠𝑖)) já seja variável básica. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR PROGRAMAÇÃO QUADRÁDITCA Suponha um PNL com 2 variáveis e 2 restrições (<=), já com a inserção das folgas: 𝑀𝑎𝑥 𝑧 = 𝑐1𝑥1 + 𝑐2𝑥2 + 𝑑1𝑥12 + 𝑑2𝑥22 + 𝑑3𝑥1𝑥2 s.a. 𝑎11𝑥1 + 𝑎12𝑥2 + 𝑠1 = 𝑏1 𝑎21𝑥1 + 𝑎22𝑥2 + 𝑠2 = 𝑏2 −𝑥1 ≤ 0 𝑒 − 𝑥2 ≤ 0 −𝟐𝑸 𝑨𝑇 −𝑰𝑴 𝟎 𝑨 𝟎 𝟎 𝑰𝑠 . 𝑿 𝚲 𝑴 𝑺 = 𝑪 𝒃 −2𝑑1 −𝑑3 𝑎11 𝑎21 −1 0 0 0 −𝑑3 −2𝑑2 𝑎12 𝑎22 0 −1 0 0 𝑎11 𝑎21 𝑎12 𝑎22 0 0 0 0 1 0 0 0 0 0 0 1 𝑥1 𝑥2 𝜆1 𝜆2 𝜇1 𝜇2 𝑠1 𝑠2 = 𝑐1 𝑐2 𝑏1 𝑏2 𝑄 = 𝑑1 𝑑3/2 𝑑3/2 𝑑2 , 𝐴 = 𝑎11 𝑎12 𝑎21 𝑎22 , 𝐼 = 1 0 0 1 , 𝑋 = 𝑥1 𝑥2 , Λ = 𝜆1 𝜆2 , Μ = 𝜇1 𝜇2 , 𝑆 = 𝑠1 𝑠2 , 𝐶 = 𝑐1 𝑐2 𝑒 𝑏 = 𝑏1 𝑏2 Forma Matricial 𝑀𝑎𝑥 𝑧 = 𝐶𝑇𝑋 + 𝑋𝑇𝑄𝑋 s.a. 𝐴𝑋 + 𝐼𝑆 = 𝑏 −𝐼𝑋 ≤ 0 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR PROGRAMAÇÃO QUADRÁDITCA EXEMPLO 6. 𝑀𝑎𝑥 𝑓 𝑥1, 𝑥2 = 15𝑥1 + 30𝑥2 + 4𝑥1𝑥2 − 2𝑥1 2 − 4𝑥2 2 s.a. 𝑥1 + 2𝑥2 ≤ 30. 𝑥1, 𝑥2 ≥ 0. Solução: Forma Matricial 𝑀𝑎𝑥 𝑓 𝑥1, 𝑥2 = 15 30 𝑥1 𝑥2 + (𝑥1 𝑥2) −2 2 2 −4 𝑥1 𝑥2 s.a. (1 2) 𝑥1 𝑥2 + 1 𝑠1 = 30 −1 0 0 −1 𝑥1 𝑥2 ≤ 0 0 −𝟐𝑸 𝑨𝑇 −𝑰𝑴 𝟎 𝑨 𝟎 𝟎 𝑰𝑠 . 𝑿 𝚲 𝑴 𝑺 = 𝑪 𝒃 𝟒 −𝟒 𝟏 −𝟏 𝟎 𝟎 −𝟒 𝟖 𝟐 𝟎 −𝟏 𝟎 𝟏 𝟐 𝟎 𝟎 𝟎 𝟏 𝒙𝟏 𝒙𝟐 𝝀𝟏 𝝁𝟏 𝝁𝟐 𝒔𝟏 = 𝟏𝟓 𝟑𝟎 𝟑𝟎 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR REFERÊNCIAS. ABENSUR, Eder O. Pesquisa Operacional para cursos de Engenharia de Produção. São Paulo: Blucher, 2018. COLIN, Emerson C. Pesquisa Operacional: 170 Aplicações em Estratégia, Finanças, Logística, Produção, Marketing e Vendas São Paulo: Atlas, 2019T HILLIER, Frederick S.; LIEBERMAN, Gerald J. Introdução à Pesquisa Operacional. Porto Alegre: AMGH, 2013. LACHTERMARCHER, Gerson. Pesquisa Operacional na Tomada de Decisões. São Paulo: Pearson Prentice Hall, 2009. LOESCH, Claudio; HEIN, Nelson. Pesquisa Operacional: Fundamentos e Modelos. São Paulo: Saraiva, 2009. TAHA, Hamdy A. Pesquisa Operacional. São Paulo: Pearson Prenticce Hall, 2008. ZORNIG, Peter. Introdução à Programação Não Linear. Brasília: Universidade de Brasília, 2011.