Slide Programação Não Linear Otimização de Funções-2022 1

PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR EXEMPLO 1. Encontre os pontos críticos de f (x) e classifique-os, sendo: (a) f(x,y,z) = xy + x2z – x2 – y – z2 (b) f(x,y,z) = xy – x2 – y2 – 2x – 2y – z2 – 2z + 4 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA SOLUÇÃO EXEMPLO 1 (a). PROGRAMAÇÃO NÃO-LINEAR PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA (b) f(x,y,z) = xy – x2 – y2 – 2x – 2y – z2 – 2z + 4 SOLUÇÃO EXEMPLO 1 (b) A HESSIANA H(-2,-2,-1) É NEGATIVA DEFINIDA  (-2,-2,-1) É PONTO DE MÁXIMO. PROGRAMAÇÃO NÃO-LINEAR PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA OTIMIZAÇÃO CONDICIONADA A IGUALDADES: MULTIPLICADORES DE LAGRANGE. PROGRAMAÇÃO NÃO-LINEAR PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA EXEMPLO 2. Otimizar. f(x,y,z) = x2+ y2 + z2 s.a. x2 + y2 = 1 x + y + z = 1 PROGRAMAÇÃO NÃO-LINEAR PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA SOLUÇÃO EXEMPLO 2. PROGRAMAÇÃO NÃO-LINEAR PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA Resolvendo o determinante e polinômio no aplicativo SCILAB, obtemos: PROGRAMAÇÃO NÃO-LINEAR PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA SOLUÇÃO EXEMPLO 3. Otimizar f(x,y,z) = x^2 + 2y +z s.a. x + y^2 = 1 2x + y + z = 4 PROGRAMAÇÃO NÃO-LINEAR PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA SOLUÇÃO EXEMPLO 3. F(x,y,z,λ1,λ2) = x^2+2y+z- λ1(x+y^2-1)-λ2(2x+y+z-4) dF/dx = 2x- λ1-2λ2 dF/dy = 2 – 2y λ1- λ2 dF/dz = 1- λ2 dF/d λ1 = -x-y^2+1 dF/d λ2 = -2x-y-z+4 x=0,603; y=-0,63; z=3,42; λ1=-0,8; λ2=1 O ponto (0,603;-0,63;3,42) é ponto mínimo. PROGRAMAÇÃO NÃO-LINEAR PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR OTIMIZAÇÃO CONDICIONADA A DESIGUALDADES: CONDIÇÕES DE KARUSH-KUHN-TUCKER (KKT) As condições KKT identificam se uma solução de um problema de otimização condicionado a desigualdades é ótima ou não. Seja o problema P1: Max z = f(x1,x2,...,xn) s.a. g1(x1,x2,...,xn) <=b1 g2(x1,x2,...,xn)<= b2 ... gm(x1,x2,...,xn)<= bm x1,...,xn >=0 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR OTIMIZAÇÃO CONDICIONADA A DESIGUALDADES: CONDIÇÕES DE KARUSH-KUHN-TUCKER (KKT) PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR OTIMIZAÇÃO CONDICIONADA A DESIGUALDADES: CONDIÇÕES DE KARUSH-KUHN-TUCKER (KKT) PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR OTIMIZAÇÃO CONDICIONADA A DESIGUALDADES: CONDIÇÕES DE KARUSH-KUHN-TUCKER (KKT) SOLUÇÃO EXEMPLO 4. MAX (- z) = -x1^2 -x2^2 - x3^2 - 40x1 - 20x2. s.a. - x1 <= -50 -x1-x2<= -100 x1,x2>=0 (1) -2x1 – 40 + (λ1 + λ2) <= 0 (verificou!) (III) -2x2 – 20 + λ2 <= 0 (verificou!) (IV) -2x3 <= 0 (verificou!) (V) (2) x1(-2x1 – 40 + (λ1 + λ2)) = 0  λ1=20 (II) x2(-2x2 – 20 + λ2) = 0  λ2=120 (I) x3(-2x3) = 0 (verificou!) (VI) (3) λ1(-x1 + 50) = 0 (verificou!) (VII) λ2(-x1-x2+100)=0 (verificou!) (VIII) (4) –x1 + 50 <= 0 (verificou!) (IX) -x1-x2+100 <= 0 (verificou!) (X) (5) λ1>=0 (verificou!) (XI) λ2>=0 (verificou!) (XII) PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR OTIMIZAÇÃO CONDICIONADA A DESIGUALDADES: CONDIÇÕES DE KARUSH-KUHN-TUCKER (KKT) Outra opção: MAX (- z) = -x1^2 -x2^2 - x3^2 - 40x1 - 20x2. s.a. - x1+50 <= 0 -x1-x2+100<=0 -x1<=0; -x2<=0; -x3<=0 Considera-se 5 restrições. KKT PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR EXEMPLO 5. f(x) = x^2 é estritamente convexa e f(x) = - x^2 é estritamente côncava. Se f é convexa, -f é côncava, e vice-versa. A soma de funções convexas é uma função convexa. A soma de funções côncavas é uma função côncava. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR FUNÇÕES CONVEXAS E CÔNCAVAS PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR FUNÇÕES CONVEXAS E CÔNCAVAS PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR FUNÇÕES CONVEXAS E CÔNCAVAS SOLUÇÃO PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR Ao contrário da PL a Programação Não-Linear (PNL) sempre apresentará pelo menos uma função não linear. Seja a função objetivo ou restrição. Em um problema de PNL irrestrito com função objetivo côncava tem-se a garantia de que um máximo local é um máximo global. De forma similar, se a função objetivo é convexa tem-se a garantia que o mínimo local é mínimo global. Em um problema de PNL restrito o máximo (mínimo) global é garantido se a função objetivo é côncava (convexa) e a região de soluções viáveis é um conjunto convexo. Seja o PPNL Max f(x) s.a. gi(x) <= bi (i=1,...m) x >= 0 Para garantir que um máximo local seja um máximo global para este problema, f(x) deve ser côncava e gi(x) convexas. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR PROGRAMAÇÃO CÔNCAVA Um problema de programação não-linear é dito de programação côncava se apresenta as seguintes características: Se a otimização for de maximização. Se a função objetivo for uma função côncava. Se as restrições forem do tipo gi(x) <= bi e gi é uma função convexa. Se as restrições forem do tipo gi(x) >= bi e gi é uma função côncava. Se as restrições de igualdade forem lineares. Neste tipo de problema pode-se garantir que o máximo local é máximo global. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR PROGRAMAÇÃO CONVEXA Um problema de programação não-linear é dito de programação convexa se apresenta as seguintes características: Se a otimização é de minimização. Se a função objetivo é uma função convexa. Se as restrições são do tipo gi(x) <= bi e gi é uma função convexa. Se as restrições são do tipo gi(x) >= bi e gi é uma função côncava. Se cada restrição de igualdade é linear. Neste tipo de problema pode-se garantir que o mínimo local é um mínimo global. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR REPRESENTAÇÃO GRÁFICA EXEMPLO 8. Represente a região viável das soluções do problema abaixo. A região viável é convexa? Justifique. Sendo x1=2 e x2=6 uma solução ótima local para o problema, podemos afirmar que esta solução é ótima global? Justifique. Max z = 3x1+5x2 s.a. x1<=4 9x12 + 5x22 <= 216 x1, x2 >=0 SOLUÇÃO EXEMPLO 8. Restrição: 9x1^2 + 5x2^2 = 216, dividindo por 216,vem x1^2/24 + x2^2/43,2 = 1  elipse com centro na origem e intersecções nos eixos x1 e x2: x1 = raiz(24) e x2 = raiz(43,2) PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR REPRESENTAÇÃO GRÁFICA 6,6 4,9 4 Região viável P x1 x2 EXEMPLO 9. Represente a região viável das soluções do problema abaixo. A região viável é convexa? Justifique. Encontre a solução ótima para o problema considerando que ele é irrestrito. Esta solução é ótima para o problema restrito proposto abaixo? Justifique. Encontre a solução ótima para o problema abaixo sabendo que esta solução é um ponto da reta 3x1+ 2x2 =18. A solução encontrada é ótima global? Justifique. Max z = 126x1 – 9x12 + 182x2 – 13x22 s.a. x1 <= 4 2x2 <= 12 3x1 + 2x2 <= 18 x1, x2 >=0 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR REPRESENTAÇÃO GRÁFICA PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR REPRESENTAÇÃO GRÁFICA SOLUÇÃO EXEMPLO 9. 6 9 6 4 x1 x2 Z é côncava e a região viável é convexa  a solução (8/3, 5) é ótimo global. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR REPRESENTAÇÃO GRÁFICA EXEMPLO 10. Represente a região viável das soluções do problema abaixo. A região viável é convexa? Justifique. A solução x1=4 e x2=3 é um ótimo local do problema abaixo, podemos afirmar que esta solução é ótima global? Justifique. Max z = 3x1 +5x2 s.a. x1 <= 4 2x2 <= 14 8x1 - x12 + 14x2 – x22 <= 49 x1, x2 >=0 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO NÃO-LINEAR REPRESENTAÇÃO GRÁFICA Restrição: 8x1 – x1^2 + 14x2 – x2^2 <= 49, completando quadrados -(x1^2 – 8x1 + 16 – 16) – (x2^2 – 14x2 + 49 – 49) = 49 -(x1 – 4)^2 – (x2 – 7)^2 = -16  Circunferência com centro (4,7) e raio 4. SOLUÇÃO EXEMPLO 10. 7 4 x1 x2 Região viável Como a região viável é não convexa, não se pode afirmar que o ótimo local (4,3) é um ótimo global.