Slide - Programação Não Linear - 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 OTIMIZAÇÃO DE FUNÇÕES COM MÚLTIPLAS VARIÁVEIS SEM RESTRIÇÃO Seja f(x1,x2,...,xn) uma função A⊂ℝn em ℝ, diferenciável num ponto (x01,x02,...,x0n) interior ao domínio A. Se (x01,x02,...,x0n) é um ponto de máximo relativo ou mínimo relativo de f(x1,x2,...,xn), então, necessariamente, as derivadas parciais de primeira ordem da função f nesse ponto são iguais a zero. 𝜕𝑓 𝜕𝑥1 𝑥01, 𝑥02, … , 𝑥0𝑛 = 𝜕𝑓 𝜕𝑥2 𝑥01, 𝑥02, … , 𝑥0𝑛 = ⋯ = 𝜕𝑓 𝜕𝑥𝑛 𝑥01, 𝑥02, … , 𝑥0𝑛 = 0 Ou 𝛻𝑓(𝑥01, 𝑥02, … , 𝑥0𝑛) = 0 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA MATRIZ HESSIANA Seja f(x1,x2,...,xn) uma função definida em A⊂ℝn em ℝ , a matriz H= H(x1,x2,...,xn)= 𝜕2𝑓 𝜕𝑥12 𝜕2𝑓 𝜕𝑥1𝜕𝑥2 … 𝜕2𝑓 𝜕𝑥1𝜕𝑥𝑛 𝜕2𝑓 𝜕𝑥2𝜕𝑥1 𝜕2𝑓 𝜕𝑥22 … 𝜕2𝑓 𝜕𝑥2𝜕𝑥𝑛 ⋮ 𝜕2𝑓 𝜕𝑥𝑛𝜕𝑥1 ⋮ 𝜕2𝑓 𝜕𝑥𝑛𝜕𝑥2 ⋱ … ⋮ 𝜕2𝑓 𝜕𝑥𝑛2 é chamada de matriz hessiana de f. CONDIÇÃO SUFICIENTE DE MÁXIMO E MÍNIMO. Seja f(x1,x2,...,xn) uma função definida num conjunto A⊂ℝn em ℝ. Se (x01,x02,...,x0n) é um ponto crítico interior da função f, então: * Se H(x01,x02,...,x0n) é uma matriz definida positiva, o ponto (x01,x02,...,x0n) é um ponto de mínimo da função f. * Se H(x01,x02,...,x0n) é uma matriz definida negativa, o ponto (x01,x02,...,x0n) é um ponto de máximo de f. * Se H(x01,x02,...,x0n) é uma matriz indefinida, então o ponto (x01,x02,...,x0n) não é nem ponto de máximo nem ponto de mínimo de f. * Se det H(x01,x02,...,x0n) = 0, nada se pode afirmar. PROGRAMAÇÃO NÃO-LINEAR PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA MATRIZ POSITIVA E NEGATIVA DEFINIDA. Seja a matriz A de ordem n A = 𝑎11 𝑎12 𝑎13 … 𝑎1𝑛 𝑎21 𝑎22 𝑎23 … 𝑎2𝑛 𝑎31 ⋮ 𝑎𝑛1 𝑎32 ⋮ 𝑎𝑛2 𝑎33 ⋮ 𝑎𝑛3 … ⋱ … 𝑎3𝑛 ⋮ 𝑎𝑛𝑛 , A é positiva definida, se 𝑎11 > 0, 𝑎11 𝑎12 𝑎21 𝑎22 > 0 , 𝑎11 𝑎12 𝑎13 𝑎21 𝑎22 𝑎23 𝑎31 𝑎32 𝑎33 > 0, ... , det(A) >0. A matriz A é negativa definida, se 𝑎11 < 0, 𝑎11 𝑎12 𝑎21 𝑎22 > 0, 𝑎11 𝑎12 𝑎13 𝑎21 𝑎22 𝑎23 𝑎31 𝑎32 𝑎33 < 0, ... , det(A) > 0 ou <0 se a ordem da matriz A for respectivamente par ou ímpar. Caso contrário a matriz A será indefinida. 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). 𝜕𝑓 𝜕𝑥 = 𝑦 + 2𝑥𝑧 − 2𝑥 = 0 𝜕𝑓 𝜕𝑦 = 𝑥 − 1 = 0 𝜕𝑓 𝜕𝑧 = 𝑥2 − 2𝑧 = 0 ⟹ 𝑥 = 1 ⟹ 𝑧 = 1 2 ⟹ 𝑦 = 1 𝐻 𝑥, 𝑦, 𝑧 = 2𝑧 − 2 1 2𝑥 1 0 0 2𝑥 0 −2 𝐻 1,1,1/2 = −1 1 2 1 0 0 2 0 −2 −1 = −1 < 0 −1 1 1 0 = −1 < 0 −1 1 2 1 2 2 2 0 −2 = 2 > 0 ⟹ 𝐻 é 𝑖𝑛𝑑𝑒𝑓𝑖𝑛𝑖𝑑𝑎 ⟹ 1,1, 1 2 é 𝑝𝑜𝑛𝑡𝑜 𝑑𝑒 𝑠𝑒𝑙𝑎 PROGRAMAÇÃO NÃO-LINEAR PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA OTIMIZAÇÃO CONDICIONADA A IGUALDADES: MULTIPLICADORES DE LAGRANGE. Considere o problema de maximizar ou minimizar a função f(x1,x2,...,xn) sujeita às condições g1(x1,x2,...,xn) = c1 , g2(x1,x2,...,xn) = c2, ... , gm(x1,x2,...,xn) = cm , com m <= n-1. Se (𝑥1 ∗, 𝑥2 ∗, … , 𝑥𝑛∗) é solução do problema e se f(x1,x2,...,xn) e gi(x1,x2,...,xn), i=1,...,m, possuem derivadas parciais de primeira ordem contínuas em uma vizinhança de (𝑥1 ∗, 𝑥2 ∗, … , 𝑥𝑛∗) , então existem 𝜆1 ∗, 𝜆2 ∗, … , 𝜆𝑚 ∗ tais que ( 𝑥1 ∗, 𝑥2 ∗, … , 𝑥𝑛∗, 𝜆1 ∗, 𝜆2 ∗, … , 𝜆𝑚 ∗ ) deve ser um ponto crítico da função de Lagrange generalizada. F(x1,x2,...,xn,λ1,λ2, ... , λm) = f(x1,x2,...,xn) – σ𝑖=1 𝑚 𝜆𝑖(𝑔𝑖(𝑥1, … , 𝑥𝑛) − 𝑐𝑖). O ponto crítico x* = ( 𝑥1 ∗, 𝑥2 ∗, … , 𝑥𝑛∗, 𝜆1 ∗, 𝜆2 ∗, … , 𝜆𝑚 ∗ ) deve satisfazer a igualdade 𝜕𝐹 𝜕𝑥1 = 𝜕𝐹 𝜕𝑥2 = ⋯ = 𝜕𝐹 𝜕𝑥𝑛 = 𝜕𝐹 𝜕𝜆1 = ⋯ = 𝜕𝐹 𝜕𝜆𝑚 = 0 PROGRAMAÇÃO NÃO-LINEAR PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA CLASSIFICAÇÃO DO PONTO CRÍTICO Seja o determinante de Hancock 𝑃 = 𝐹11 − 𝑡 𝐹12 𝐹21 𝐹22 − 𝑡 … 𝐹1𝑛 … 𝐹2𝑛 𝑔11 𝑔21 … 𝑔𝑚1 𝑔12 𝑔22 … 𝑔𝑚2 ⋮ ⋮ 𝐹𝑛1 𝐹𝑛2 ⋱ ⋮ … 𝐹𝑛𝑛 − 𝑡 ⋮ ⋮ ⋱ ⋮ 𝑔1𝑛 𝑔2𝑛 … 𝑔𝑚𝑛 𝑔11 𝑔12 𝑔21 ⋮ 𝑔𝑚1 𝑔22 ⋮ 𝑔𝑚2 … 𝑔1𝑛 … ⋱ … 𝑔2𝑛 ⋮ 𝑔𝑚𝑛 0 0 … 0 0 ⋮ 0 0 ⋮ 0 … ⋱ … 0 ⋮ 0 = 0 Onde: 𝐹𝑖𝑗 = 𝜕2 𝜕𝑥𝑖𝜕𝑥𝑗 𝐹( 𝑥1 ∗, 𝑥2 ∗, … , 𝑥𝑛∗, 𝜆1 ∗, 𝜆2 ∗, … , 𝜆𝑚 ∗ ) 𝑔𝑖𝑗 = 𝜕 𝜕𝑥𝑗 𝑔𝑖( 𝑥1 ∗, 𝑥2 ∗, … , 𝑥𝑛∗) PROGRAMAÇÃO NÃO-LINEAR As raízes de 𝑃 determinam se o ponto crítico x* é máximo ou mínimo. x* é ponto de máximo se todas as raízes de P forem negativas. x* é ponto de mínimo se todas as raízes de P forem positivas. Se P possui raízes positivas e negativas, x* não é ponto de máximo nem de mínimo. 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 SOLUÇÃO EXEMPLO 2. F(x,y,z,λ1,λ2)= x^2 + y^2 + z^2 – λ1(x^2 + y^2 – 1) – λ2(x + y + z – 1) 𝜕𝐹 𝜕𝑥 = 2x – 2xλ1 – λ2 = 0 ➔ 2x(1 – λ1) = λ2 (1) 𝜕𝐹 𝜕𝑦 = 2y – 2yλ1 – λ2 = 0 ➔ 2y(1 – λ1)=λ2 (2) 𝜕𝐹 𝜕𝑧 = 2z – λ2 = 0 ➔ λ2 = 2z (3) 𝜕𝐹 𝜕λ1 = -x^2 – y^2 + 1 = 0 (4) 𝜕𝐹 𝜕λ2 = -x – y – z + 1 = 0 (5) Dividindo (1) por (2), vem x = y, substituindo em (4), vem: x=y= ± 2 2 . De (5), tiramos z = -2x + 1 ➔ z=∓ 2 + 1. De (3), tiramos λ2=∓2 2 + 2. PROGRAMAÇÃO NÃO-LINEAR De (1), tiramos λ1=(2x – λ2)/2x λ1= ± 2− ∓2 2+2 ± 2 = ±3 2−2 ± 2 . 2 2 = ±6−2 2 ±2 λ1=3 ∓ 2 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA SOLUÇÃO EXEMPLO 2. Para classificar os pontos em máximo e mínimo, usa-se o determinante de Hancock P= 𝐹11 − 𝑡 𝐹12 𝐹13 𝑔11 𝑔21 𝐹21 𝐹22 − 𝑡 𝐹23 𝑔12 𝑔22 𝐹31 𝑔11 𝑔21 𝐹32 𝑔12 𝑔22 𝐹33 − 𝑡 𝑔13 𝑔23 𝑔13 0 0 𝑔23 0 0 = 2 − 2𝜆1 − 𝑡 0 0 2𝑥 1 0 2 − 2𝜆1 − 𝑡 0 2𝑦 1 0 2𝑥 1 0 2𝑦 1 2 − 𝑡 0 1 0 0 0 1 0 0 Se todas as raízes de P são negativas, x é ponto de máximo. Se todas são positivas, x é mínimo. Se P possui ambas as raízes (+ e -), x não é Max e nem mín. PROGRAMAÇÃO NÃO-LINEAR f(x,y,z) = x2+ y2 + z2 s.a. x2 + y2 = 1 x + y + z = 1 F(x,y,z,λ1,λ2)= x^2 + y^2 + z^2 – λ1(x^2 + y^2 – 1) – λ2(x + y + z – 1) 𝜕𝐹 𝜕𝑥 = 2x – 2xλ1 – λ2 = 0 𝜕𝐹 𝜕𝑦 = 2y – 2yλ1 – λ2 = 0 𝜕𝐹 𝜕𝑧 = 2z – λ2 = 0 𝜕𝐹 𝜕λ1 = -x^2 – y^2 + 1 = 0 𝜕𝐹 𝜕λ2 = -x – y – z + 1 = 0 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA SOLUÇÃO EXEMPLO 2. Verificando o ponto (− 2 2 , − 2 2 , 1 + 2) , λ1=3 + 2 e λ2=2 2 + 2 Resolvendo o determinante e polinômio no aplicativo SCILAB, obtemos: Resultado: det_P= - 18,485281 – 4t Raiz_t = - 4,62 Como a raiz do polinômio é negativa, chega-se a conclusão que ( − 2 2 , − 2 2 , 1 + 2) é ponto de máximo. PROGRAMAÇÃO NÃO-LINEAR 2 − 2𝜆1 − 𝑡 0 0 2𝑥 1 0 2 − 2𝜆1 − 𝑡 0 2𝑦 1 0 2𝑥 1 0 2𝑦 1 2 − 𝑡 0 1 0 0 0 1 0 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) As condições KKT identificam se uma solução de um problema de otimização condicionado a desigualdades é ótima ou não. Para o problema: 𝑀𝑎𝑥 𝑓 𝑿 ; 𝑠. 𝑎. 𝑔 𝑿 ≤ 0 As KKT são: (1): 𝜆𝑖 ≥ 0, 𝑖 = 1, … , 𝑚 (𝑁º 𝑑𝑒 𝑟𝑒𝑠𝑡𝑟𝑖çõ𝑒𝑠) (2): 𝛻𝑓 𝑿 − 𝜆𝑖𝛻𝑔𝑖 𝑿 = 0 (3): 𝜆𝑖𝑔𝑖 𝑿 = 0 (4): 𝑔𝑖 𝑿 ≤ 0 EXEMPLO 3. Use as condições KKT para mostrar que os valores x1=50 x2 = 50 e x3 = 0 são coordenadas de um ótimo local para o problema abaixo: 𝑀𝑖𝑛 𝑧 = 𝑥1 2 + 𝑥2 2 + 𝑥3 2 + 40𝑥1 + 20𝑥2 s.a. 𝑥1 ≥ 50 𝑥1 + 𝑥2 ≥ 100 𝑥1, 𝑥2, 𝑥3 ≥ 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) Solução exemplo 3: 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 (1): 𝜆𝑖 ≥ 0, 𝑖 = 1, … , 𝑚 (𝑁º 𝑑𝑒 𝑟𝑒𝑠𝑡𝑟𝑖çõ𝑒𝑠) 1.1 𝜆1 ≥ 0; 1.2 𝜆2 ≥ 0; 1.3 𝜆3 ≥ 0; 1.4 𝜆4 ≥ 0; 1.5 : 𝜆5≥ 0 (2): 𝛻𝑓 𝑿 − 𝜆𝑖𝛻𝑔𝑖 𝑿 = 0 2.1 : −2𝑥1 − 40 + 𝜆1 + 𝜆2 + 𝜆3 = 0; 2.2 : −2𝑥2 − 20 + 𝜆2 + 𝜆4 = 0; 2.3 : −2𝑥3 + 𝜆5 = 0. (3): 𝜆𝑖𝑔𝑖 𝑿 = 0 3.1 : 𝜆1 −𝑥1 + 50 = 0; 3.2 : 𝜆2 −𝑥1 − 𝑥2 + 100 ; = 0 3.3 : 𝜆3 −𝑥1 = 0; 3.4 : 𝜆4 −𝑥2 = 0; 3.5 : 𝜆5 −𝑥3 = 0. (4): 𝑔𝑖 𝑿 ≤ 0 4.1 : −𝑥1 + 50 ≤ 0; 4.2 : −𝑥1 − 𝑥2 + 100 ≤ 0; 4.3 : −𝑥1 ≤ 0; 4.4 : −𝑥2 ≤ 0; 4.5 : −𝑥3 ≤ 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.