Slide - Condição de Segunda Ordem - Pesquisa Operacional 2 - 2023-2

22/11/2023 Pesquisa Operacional II Pesquisa Operacional II Diogo 59 Pesquisa Operacional II Lembrando - Exercício Diogo 60 59 60 22/11/2023 “7= f(y) =x3- y3 + Oxy * Todos os pontos de D sao 9 pontos interiores! *-D=R * Pela Regra de Fermat, se ha extremo, este @€ um ponto critico. Of (x, y) 2 ay 8 +9y =0 x2 = —3y Pontos criticos: (0,0) e (3, —3) 0 x, 2=— WHFCY) _ 9 _, 3y2 40x =0 yn = 3x dy * Os pontos (0,0) e (3,—3) sao candidatos a extremos locais. Pra classifica-los, precisamos das condi¢des de segunda ordem. 1D} [oy=X0) Pesquisa Operacional II 61 61 Condicoes de Segunda Ordem 1D} [oy=X0) Pesquisa Operacional II 62 62 22/11/2023 . ~ 7 Condicdo de segunda ordem (uma variavel) * Condicdo de segunda ordem (funcdo de uma variavel): seja uma funcio f: D C R > R de classe C* e a um ponto critico de f no interior de D. 1D} [oy=X0) Pesquisa Operacional II 63 63 . ~ 7 Condicdo de segunda ordem (uma variavel) * Condicio de segunda ordem (funcio de uma variavel): seja uma funcaio f: D C R > R de classe C? e a um ponto critico de f no interior de D. * Se f(a) > 0, x = aéum ponto de minimo local de f; 1D} [oy=X0) Pesquisa Operacional II 64 64 22/11/2023 . ~ 7 Condicdo de segunda ordem (uma variavel) * Condicdo de segunda ordem (funcdo de uma variavel): seja uma funcio f: D C R > R de classe C* e a um ponto critico de f no interior de D. * Se f(a) > 0, x = aéum ponto de minimo local de f; * Se f(a) < 0, x = a éum ponto de maximo local de f; 1D} [oy=X0) Pesquisa Operacional II 65 65 . ~ 7 Condicdo de segunda ordem (uma variavel) * Condicio de segunda ordem (funcio de wma variavel): seja uma funcaio f: D C R > R de classe C? e a um ponto critico de f no interior de D. * Se f(a) > 0, x = aéum ponto de minimo local de f; * Se f(a) < 0, x = aéum ponto de maximo local de f; * Se f’"(a) = 0, x = a pode ser um ponto de maximo local, de minimo local ou de sela de f. Assim, as condicdes de segunda ordem nao conseguem classificar 0 ponto critico a. 1D} [oy=X0) Pesquisa Operacional II 66 66 22/11/2023 e ~ a A e Condicdo de segunda ordem (n variaveis) * Condicdo de segunda ordem (funcdo de n variaveis): seja uma funcio f: D C R” de classe C?, p um ponto critico no interior de D e seja D?f (p) a matriz Hessiana da fungao f no ponto p. 1D} [oy=X0) Pesquisa Operacional II cys 67 e ~ a A e Condicdo de segunda ordem (n variaveis) * Condicio de segunda ordem (funcio de n variaveis): seja uma funcio f: D C R” de classe C?, p um ponto critico no interior de D e seja D*f (p) a matriz Hessiana da fungao f no ponto p. a) Se D?f(p) é uma matriz positiva definida, entao p é um ponto de minimo local de f; 1D} [oy=X0) Pesquisa Operacional II 68 68 Condicdo de segunda ordem (n variaveis) * Condicdo de segunda ordem (funcdo de n variaveis): seja uma funcio f: D C R” de classe C?, p um ponto critico no interior de D e seja D?f (p) a matriz Hessiana da fungao f no ponto p. a) Se D?f(p) é uma matriz positiva definida, entao p é um ponto de minimo local de f; b) Se D*f(p) é uma matriz negativa definida, entao p é um ponto de maximo local de f; 1D} [oy=X0) Pesquisa Operacional II 69 69 Condicdo de segunda ordem (n variaveis) * Condicio de segunda ordem (funcio de n variaveis): seja uma funcio f: D C R” de classe C?, p um ponto critico no interior de D e seja D*f (p) a matriz Hessiana da fungao f no ponto p. a) Se D?f(p) é uma matriz positiva definida, entao p é um ponto de minimo local de f; b) Se D?f(p) é uma matriz negativa definida, entéo p é um ponto de maximo local de f; c) Se D*f(p) é uma matriz indefinida, entao p é um ponto de sela de f, assim, é¢ um ponto critico que nao é minimo local nem maximo local de f; 1D} [oy=X0) Pesquisa Operacional II 70 70 Condicdo de segunda ordem (n variaveis) * Condicdo de segunda ordem (funcdo de n variaveis): seja uma funcio f: D C R” de classe C?, p um ponto critico no interior de D e seja D?f (p) a matriz Hessiana da fungao f no ponto p. a) Se D?f(p) é uma matriz positiva definida, entao p é um ponto de minimo local de f; b) Se D*f(p) é uma matriz negativa definida, entao p é um ponto de maximo local de f; c) Se D*f(p) é uma matriz indefinida, entdo p é um ponto de sela de f, assim, 6 um ponto critico que ndo é minimo local nem maximo local de f; d) Se D?f(p) éuma matriz positiva semidefinida ou negativa semidefinida, ent&o p é um ponto de maximo local, minimo local ou de sela de f. 1D} [oy=X0) Pesquisa Operacional II val 71 M de uma Matrizes 72 22/11/2023 Menores de uma matriz ¢ Seja A uma matriz n X n. Um menor de ordem k é 0 determinante de uma submatriz k x k de A obtida removendo-se n — k linhas e n — k colunas de A. Q414 442 43 A=|421 422 423 431 432 433 ¢ Menores de ordem 1: © |aqy/, lai2l, lai3l, la2i/, la22I, |a23], lazil, lasal, laz3l |A| denota o determinante de A 1D} [oy=X0) Pesquisa Operacional II 73 73 Q4, A42 A43 A=|421 422 423 431, 432 433 * Menores de ordem 1: © layil lai, lish, la2il, la22l, la23l, lasil, las2l, |az3| ¢ Menores de ordem 2: . a | la | a a | lan a a | an a | 432 433171431 33171431 A321’ 1A32 9331’ 1431 A331’ 1A31 Ag2l’ . an a | an a | an | A22 A231’1A21 Az31’1A21 Az? ¢ Menor de ordem 3: Q44 Aya 43 © 14214 422 923 Q31 32 33 |A| denota 0 determinante de A 1D} [oy=X0) Pesquisa Operacional II rE 74 Menores principais de uma matriz . vm menor principal de ordem k 6 um menor de ordem k no qual as linhas e colunas removidas possuem 0 mesmo indice. 441 42 43 A=1]421 422 423 431 432 433 * Menores principais de ordem 1: * |ay1I laz2l, lassl * Menores principais de ordem 2: . la | a al a | 432 433171431 4331’1d21 A2z2 * Menor principal de ordem 3: 441 A2 43 © {421 422 423 a a a Sh SSS |A| denota o determinante de A 1D} [oy=X0) Pesquisa Operacional II vie) 75 Menores principais lideres HAL denote o determinants ce ¢ Um menor principal lider de ordem k 6 um menor principal de ordem k onde foram removidas as ultimas n — k linhas en — k colunas. A141 412 43 A= |%21 422 423 431 432 433 * Menor principal lider de * Menor principal lider ¢ Menor principal lider de ordem 1: de ordem 2: ordem 3: ° [ail . a a M1 2 443 A21 422 © {421 422 423 A313 432 33 1D} [oy=X0) Pesquisa Operacional II 76 76 Positividad Matri Quadrati 1D} [oy=X0) Pesquisa Operacional II wah 77 * Seja A uma matriz n X n simétrica. Denote por |A;,| o menor principal lider de ordem k de A. 1. A éuma matriz positiva definida se, e somente se, todos os menores principais lideres de A sao maiores do que zero. 2. A éuma matriz negativa definida se, e somente se, todos os menores principais lideres de ordem impar sdo menores do que zero e todos os menores principais lideres de ordem par sdo maiores do que zero. 3. Aéuma matriz positiva semidefinida se, e somente se, todos os menores principais de A sdo maiores ou iguais a zero. 4, Aéuma matriz negativa semidefinida se, e somente se, todos os menores principais de ordem impar sdo menores ou iguais a zero e todos os menores principais de ordem par sdo maiores Ou iguais a zero. 5. Se Ando se enquadra em nenhum dos 4 casos anteriores, entao A 6 uma matriz indefinida. 1D} [oy=X0) Pesquisa Operacional II 78 78 Voltand Exercici 1D} [oy=X0) Pesquisa Operacional II 79 79 Condicdo de segunda ordem (n variaveis) * Condicio de segunda ordem (funcio de n variaveis): seja uma funcio f: D C R” de classe C?, p um ponto critico no interior de D e seja D* f (p) a matriz Hessiana da fungao f no ponto p. a) Se D?f(p) é uma matriz positiva definida, entao p é um ponto de minimo local de f; b) Se D?f(p) é uma matriz negativa definida, entéo p é um ponto de maximo local de f; c) Se D*f(p) é uma matriz indefinida, entao p é um ponto de sela de f, assim, é¢ um ponto critico que nao é minimo local nem maximo local de f; d) Se D?f(p) é uma matriz positiva semidefinida ou negativa semidefinida, entéo p é um ponto de maximo local, minimo local ou de sela de f. 1D} [oy=X0) Pesquisa Operacional II 80 80 22/11/2023 ~7= — 73 _ 473 * Todos os pontos de D sao * Pontos criticos: 2 f& y) x y* + 9xy pontos interiores! - (0,0) “D= R2 ¢ Pela Regra de Fermat, se ha . (3, -3) extremo, este € um ponto , critico. 6x 9 2 _ Df%y=|9 _éy| _fo 9 p2f(3,-3) =[28 2 D*F(0,0)=|5 | f3-3)=[9 il * |0| =0 * [18] = 18 0 9 ~ (18 9] _ 492 _ 92 - (0 8) = 81 [5 ial = 187-97 > 0 * Como um menor principal de ordem par é menor * Todos os menores principais lideres sdo positivos. do que zero, temos uma matriz indefinida no Matriz é positiva definida no ponto. ponto. * (3,—3) €um minimo local de f. * (0,0) 6 um ponto é de sela de f. 1D} [oy=X0) Pesquisa Operacional II rai 81 Condic¢cdao de segunda ordem * Descobrimos que p = (3, —3) € um minimo local de f. * Porém, ele é um minimo global? * As condigées de segunda ordem estabelecem um critério para definir se um ponto critico p €é um extremo local, mas nada afirmam sobre a globalidade do ponto critico. * Uma forma de garantir a globalidade de um ponto critico é através do estudo da concavidade da fung¢ao objetivo f. 1D} [oy=X0) Pesquisa Operacional II ty 82 22/11/2023 e ew e e Condicdes de Otimalidade 1D} [oy=X0) Pesquisa Operacional II rey 83 Otimalidade * Sejam f:U Cc R” > R uma funcdo de classe C* definida em um subconjunto convexo U de R" e p € U um ponto critico de f: 1D} [oy=X0) Pesquisa Operacional II 29 84 22/11/2023 Otimalidade Pi Conjunto Conjunto convexo n&o-convexo * Sejam f: U C IR” > R uma fungi de classe C+ definida em um subconjunto convexo U de R" e p € U um ponto critico de f: 1D} [oy=X0) Pesquisa Operacional II 85 85 Otimalidade * Sejam f:U Cc R” > R uma funcdo de classe C* definida em um subconjunto convexo U de R" e p € U um ponto critico de f: e Se f éuma funcgado convexa em U, entao p é um ponto de minimo global de f em U. e Se f éuma funcgdo céncava em U, entao p é um ponto de maximo global de f em U. 1D} [oy=X0) Pesquisa Operacional II 86 86 22/11/2023 Concavidade de funcdes * Seja f:U C R” > R uma funcao de classe C? definida em um subconjunto convexo e aberto U de R". * f &uma funcdo convexa em U se, e somente se, a matriz hessiana D2 f (p) é positiva semidefinida para todo p € U. * f &uma funcgdo céncava em U se, e somente se, a matriz hessiana D2 f (p) é negativa semidefinida para todo p € U. 1D} [oy=X0) Pesquisa Operacional II ve 87 Voltando ao exemplo i el ; P 3_ 3 5 pa °Zz=f%y) =x —y° + Ixy i as ~ 7 [ 1 * Temos que p = (3,—3) 6 um minimo local . | * Nesse ponto, z = —27 ie ——s * Esse ponto é um minimo global? 7 * Ora, se fizermos x = Dey > 3, alcancamos um valor mais negativo! * Assim, p nado é um minimo global nesse problema! 1D} [oy=X0) Pesquisa Operacional II tte} 88 22/11/2023 Pesquisa Operacional II Otimização Não Linear Problemas com 1 restrição de igualdade Diogo 91 Pesquisa Operacional II Condição de primeira ordem em um problema restrito... • Pela regra de Fermat, se um ponto de extremo (local) 𝒑 está no interior da região 𝐷, então a solução é um ponto crítico de 𝑓, ou seja, ∇𝑓 𝒑 = 𝟎. • Entretanto, se essa solução não é um ponto no interior do conjunto admissível, não é necessário que 𝒑 seja um ponto crítico!! ∇𝑓 𝒙∗ = (3; 5), dessa forma, 𝒙∗ não é um ponto crítico. Assim, a regra de Fermat não pode ser aplicada para caracterizar todos os pontos da região! Diogo 92 91 92 22/11/2023 Uma restricao de igualdade 1D} [oy=X0) Pesquisa Operacional II ey 93 Uma restricdo de igualdade * Digamos que o problema possui apenas uma restrigdo de igualdade. * Deseja-se maximizar f(x) sujeitoa x € D = {x € R"|hA(x) = c}. * Nesse caso, os pontos viaveis estao necessariamente sobre a regiao definida pela restri¢ao. ¢ Aregra de Fermat nAo se aplica. IS feq 1D} [oy=X0) Pesquisa Operaciona! = . 94 94 22/11/2023 Uma restricdo de igualdade * Para um ponto p ser um extremo local de f, ¢ necessario que a curva de nivel de f tangencie a curva de nivel de h no ponto p. Vejamos graficamente. 1D} [oy=X0) Pesquisa Operacional II 95 95 Uma restricdo de igualdade * Para um ponto p ser um extremo local de f, ¢ necessario que a curva de nivel de f tangencie a curva de nivel de h no ponto p. Vejamos graficamente. max f (x1, X2) Sujeito a: (%1,%2) ED= {(%1, x2) E R?|A((x1, x2) = c} X2 C4 > C3 > C2 > Cy KR 8 fe; feq . hee ™ Pesquisa Operacional II so ey 96 22/11/2023 Uma restricdo de igualdade * Para um ponto p ser um extremo local de f, ¢ necessario que a curva de nivel de f tangencie a curva de nivel de h no ponto p. Vejamos graficamente. max f (x1, X2) Sujeito a: (x1, %2) ED= {(%1, x2) E R2|h((x1, x2)) = c} Xz C4 > C3 > C2 > Cy \ q € um extremo local? Ss Ir i 0 ™M hee Pesquisa Operacional II VA 97 Uma restricdo de igualdade * Para um ponto p ser um extremo local de f, ¢ necessario que a curva de nivel de f tangencie a curva de nivel de h no ponto p. Vejamos graficamente. max f (x1, X2) Sujeito a: (x1,%2) € D = {(x1, x2) € R?|A((x1,x2)) = c} Xz C4 > C3 > C2 > Cy q € um extremo local? Resposta: Nao. Pontos onde a curva de nivel de f e a curva de nivel ‘Si de h se interceptam transversalmente ndo podem fne ser extremos locais de f em D. f=zq 0 ™M hee Pesquisa Operacional II soe} 98 22/11/2023 Uma restricdo de igualdade * Para um ponto p ser um extremo local de f, ¢ necessario que a curva de nivel de f tangencie a curva de nivel de h no ponto p. Vejamos graficamente. max f (%1, X2) Sujeito a: (x%1,X2) € D = {(%1, x2) € R2|h( (x1, X2)) =c} Xz C4 > C3 > C2 > Cy Por outro lado, a curva de nivel de f que passa por p é tangente a curva de nivel de h (que define o SX conjunto admissivel D. iad ey 0 ™M hee Pesquisa Operacional II 99 99 Uma restricdo de igualdade * Para um ponto p ser um extremo local de f, ¢ necessario que a curva de nivel de f tangencie a curva de nivel de h no ponto p. Vejamos graficamente. max f (x1, X2) Sujeito a: (%1,%2) € D = {(%1, x2) € R?|A((x1, x2) =c} Xz C4 > C3 > C2 > Cy Por outro lado, a curva de nivel de f que passa por p é tangente a curva de nivel de h (que define o conjunto admissivel D. fmc Como usar essa informagao ao nosso favor? fe; ey 0 ™M hee Pesquisa Operacional II 100 100 * Para um ponto p ser um extremo local de f, ¢ necessario que a curva de nivel de f tangencie a curva de nivel de h no ponto p. Vejamos graficamente Sujeito a: (x1, X2) EeD= {(x1, 2) E R2|h((x1, x2)) = c} TEOREMA Xz C4 > C3 > C2 > Cy Seja F:D Cc R™ > R uma fungao de classe Ck comk > 1. Se p é um ponto regular de F, ou seja, VF (p) # 0, entao o gradiente VF (p)é perpendicular em p 4 hiperficie de nivel: _ F, = {x € D|F(x) =k = F(p)} fe; feq Fae, de F que passa por p. : hec - Pesquisa Operacional II 101 101 1. Se Vh(p) ¥ 0, entdo sabemos que esse gradiente é perpendicular a curva de nivel h = c no ponto p. re 2. Se Vf(p) # 0, ent&o sabemos que esse gradiente é perpendicular a curva de nivel f = c3 no ponto p. (0 * Ora, as curvas de nivel h = ce f =cz3 sao tangentes em p. * Logo, Vh(p) e Vf (p) devem ser paralelos em p. * Dessa maneira, deve existir um numero real A tal que: Vf (p) =A x Vh(p) Essa condicéo funciona como um filtro de primeira ordem para extremos do conjunto admissivel construido com uma restric¢4o de igualdade. 1D} [oy=X0) Pesquisa Operacional II 102 102 22/11/2023 103 Multiplicadores de Lagrange Sejam f eh funcées de classe C1 de n variaveis e seja p um extremo (maximo ou minimo) local de f no conjunto admissivel D = {x € R"|hA(x) = c} Suponha que p Satisfaga a seguinte condi¢do de regularidade: Vh(p) #0 Entdo existe um numero real A* (o multiplicador de Lagrange) tal que (p, 2*) € IR*? é ponto critico do langrangeano: L(x,A) = f(x) — Ax [h(x) - ¢] Em outras palavras: ob 4") =0 ob a) =0 OL 4") =0 ax, J=0, «, Ox, 0 = 0, 54 = 1D} [oy=X0) Pesquisa Operacional II 104 104 22/11/2023 L(x,Aa) = f(x) —Ax [h(x) -—c] Ou seja, existe A tal que: Vf(p) = a" x Vh(p) No ponto p: A(x) =c . OL(%A) _ Of (x) __ 4 Oh(X) _ oS! Ox, ~ 0x1 A Oxy ~ 0 . OL(%A) _ Of (x) _ 4 Oh(X) _ Ox2 ~ OX2 A Ox2 ~ 0 f —=—— Vf(p)=% x Vh(—p) . ILA) _ OF (XK) _ 4 Oh(X) _ axn ~OXn A Oxn 0 AL(x,A) — 2 ot = h(x) +c = 0 da (2) —— = h(@x)=c 1D} [oy=X0) Pesquisa Operacional II 105 105 Exercicio 1D} [oy=X0) Pesquisa Operacional II mele} 106 22/11/2023 max f (x1,%2) = %4%X2 Sujeito a: (x1,%2) € D = {(x1, x2) € R*|h(x1, x2) = x1 + 4x2 = 8} Passo 1: As funcdes f e h sdo de classe C1 como soma e multiplicacdo de funcées de classe C?. Passo 2: Devemos verificar a condicao de regularidade. oh oh Vh(X1,%X2) = Dae, KU 2) Fee, Ma X2) = (14) Assim, Vh(x1,X2) # (0,0) para todo ponto (x1, x2) do conjunto admissivel. Passo 3: Escrever o Lagrangeano L(Xq,%X2,A) = f (1,2) — ALA, X2) — €] L(X4,X2,A) = 4X2 — A(x, + 4x2 — 8) 1D} [oy=X0) Pesquisa Operacional II 107 107 max f (x1,X2) = %1%2 Sujeito a: (x1,X2) € D = {(x1,%2) € R*|h(xy, x2) = x1 + 4x2 = 8} L(X4,X2,A) = 4X2 — A(x, + 4x2 — 8) Passo 4: Escrever o sistema de condicdes de primeira ordem. OL Bx, MU X24) = 0 X2 _ A = 0 OL —— (X1,X2,A) = 0 > x, -41 =0 Ox: x1 + 4x, -8 =0 OL gq 1X2 VD = 0 1D} [oy=X0) Pesquisa Operacional II 108 108 22/11/2023 max f (x1,%2) = %4%X2 Sujeito a: (x1,%2) € D = {(x1, x2) € R*|h(x1, x2) = x1 + 4x2 = 8} L (x4, X2,A) = X4xX2 — A(x, + 4x2 _ 8) x2—- A =0 Condic6des de primeira ordem: x,-41 =0 xy + Ax2 —-8=0 Passo 5: Resolver o sistema * De(1), x2 =A ¢ Substituindo em (2), temos x; = 4x2 * Substituindo em (3), 8x2 = 8 > x2 = 1 © xy = 4XX2 PX, = 4 © A=Hx27A=1 1D} [oy=X0) Pesquisa Operacional II 109 109 max f (x1,X2) = %1%2 Sujeito a: (x1,X2) € D = {(x1,%2) € R*|h(xy, x2) = x1 + 4x2 = 8} L(X4,X2,A) = 4X2 — A(x, + 4x2 — 8) X2 _ A = 0 Condic6des de primeira ordem: x, -42=0 xy + 4x2 _— 8 = 0 Passo 5: Solucao: x, =4,x, =1,A=1 Passo 6: Conclusao * O tnico ponto candidato a solucao 6tima é 0 ponto (4,1). Porém, nem todo ponto que satisfaz as condigées de primeira ordem é um 6timo. ¢ Estudaremos adiante como classificar pontos criticos do Lagrangeano. 1D} [oy=X0) Pesquisa Operacional II 110 110 22/11/2023 max f (%1,%2) = xf x2 Sujeito a: (x1, X%2) € D = {(%1, x2) € R*|A(xy, x2) = 2x7 + x3 = 3} 111 m restricdes de igualdade 112 22/11/2023 Param restricdes de igualdade * Quando temos m restrigdes de igualdade restringindo 0 conjunto viavel h(x) =C, i= 1,2, weyM a condigao de regularidade passa a ser de que a matriz jacobiana de h no ponto p possua uma submatriz m X m invertivel. dp) 9) [Vhi(p)] Ox, OXn [Vim (p)l| ,, |tm@®) atm) Ox, OXn Jaxn * Ou seja: * O posto da matriz é igual ao numero de restricdes, m. * Amatriz escalonada equivalente nao possui linhas nulas. 1D} [oy=X0) Pesquisa Operacional II 113 113 Multiplicadores de Lagrange Sejam f e hy, ..., hm fungdes de classe C1 de n variaveis e seja p um extremo (maximo ou minimo) local de f no conjunto admissivel D = {x € R"|hy(®) = C4, ..., Am (X) = Cm} Suponha que p satisfaga a seguinte condi¢do de regularidade: o posto da matriz jacobiana de h no ponto p é igual ao numero de restrigdes: m. * Ent&o existe numeros reais A}, ..., Aj, (os multiplicadores de Lagrange) tais que o ponto (p, A*) € R"*™ é ponto critico do langrangeano: L(x, A) = f(x) — A, x [hy (x) — cy] — + — Am X [Am () - Cr] * Em outras palavras: OL a") =0 aL a") =0 ax, D, =0, wey ax, D, =U, aL 2°) =0 aL a") =0 at P, =U, wey Am D, = 1D} [oy=X0) Pesquisa Operacional II any 114 22/11/2023 L(x,A) = f(x) ~~ Ay x [hy (x) _ cy] ~ Am x [Am (x) _ Cml No ponto p: « GLGA) _ Of) yg Ala@) _ ON) _ y Ox, ~ Ox, Ay Ox, Am Ox, 0 . OLGA) _ ax) _ 4 am) _ Mm) _ g ~~ Vf (p) = a, x Vhi(p) + Am X Vim) Oxn ~ Oxn 1 Oxn mM axn ~ SOLA) a — a, hw) +c, =0 : Ou seja, existem A}, ..., Aj, tais que: 2 OLGA) _ =~9 >—A(®) =¢, j=1,...,m. Big tm (X) + Cm = 0 a Vf (p) = Aj x Vay (p) + Ain X Vim (p) hwy - Nm() = Cm 1D} [oy=X0) Pesquisa Operacional II 115 115 Exercicio 1D} [oy=X0) Pesquisa Operacional II a) 116 max XyZ sujeito a: x?+y%=1 x+z=1 1D} [oy=X0) Pesquisa Operacional II aay) 117 max XyZ sujeito a: x?+y%=1 x+z=1 Passo 1: As funcdes f, h, e hz so de classe C1 como somae multiplicagado de fungdes de classe C1. 1D} [oy=X0) Pesquisa Operacional II aes} 118 22/11/2023 max XyZ sujeito a: x?+y%=1 x+z=1 Passo 2: Condic¢do de regularidade. dhy Oh, Oh, Oh, Oh, Oly dx dy dz a dy de) _px 2y 9 Oh, Ah, dh, Oh, Ohz Oh 1 0 1 ‘dx dy dz dx dy dz Se x = 0, temos de h, que y = +1; Se x # 0, escalonando a matriz teremos: A matriz fica: Modo [2x 2y 9 _ 2x by 0 _ rt 2y 0 | = ~ 1 0O 1 —-— 0 2y —-2x li 0 | lo +2 al 0 2x | Y O posto da matriz é 2! O posto da matriz é 2! 1D} [oy=X0) Pesquisa Operacional II 119 119 max XyZ . sujeito a: Passo 3: Lagrangeano. x2+y%=1 x =4 L(x, y, Z, Ay, Az) = xyz — A, (x? + yy? —1) -A,(x +z-1) Passo 4: Condi¢des de primeira ordem: OL Fy OY % Av Aa) = 0 yz—2ax—a,=0, (1) xz—2A,y = 0, (2) OL xy —a, = 0 (3) a— (x,y, 2, 44,42) = 0 ae ay rt" x2 +y2=1, (4) x+z=1, (5) OL 9p Z,A4,42) = 0 OL aa, 1” A142) = 0 OL Bay Av Aa) =0 1D} [oy=X0) Pesquisa Operacional II aye) 120 22/11/2023 max XyZ yz —2A,x -—Az, = 0, (1) sujeito a: Passo 5: Resolver o sistema xz — 2Ay = 0, (2) xe+y?=1 xy — A, =0, (3) x+z=1 x2 +y%=1, (4) x+z=1, (5) * Sey=0: * De (2) temos que xz = 0 * De (3) temos que Az = 0 * De(4)temosx =+1ou —1. °* Sex=-1: * De (5), temos que z = 1 — (—1) = 2 > Contradi¢ao, pois xz = 0! * Sex =1: * De (5), temos que z = 0. * De (1), temos que A, = 0. * Conclusdo: a dnica solugao possivel quando y = 0 é p = (1,0,0,0,0). 1D} [oy=X0) Pesquisa Operacional II sal 121 max xyz yz —2A,4x —A, = 0, (1) sujeito a: Passo 5: Resolver o sistema xz — 2A,y = 0, (2) xe+y%=1 xy —A, =0, (3) x+z=1 x? +y? =1, (4) x+z=1, (5) * Sey#0: = <2 De (2) temos que A, = oy * De (3) temos que Az = xy * Substituindo em (1) temos: yz — vx —xy=0 > y?z-x*z-xy* =0 * De (4) temos y2 = 1 — x? * De (5), temos quez=1-—x * Substituindo na expressdo obtida de (1), temos: (1 — x2)(1 — x) —x?(1 —x) —x(1 —x?) =0 * Como1—x? = (1—x)(1 +x), temos:(1 — x?)(1 —x) —x?(1-—x) -—x(1-—x)(1+x) =0 * Colocando (1 — x) em evidéncia: * (l-x)[1-—2x? -—x% -—x(1+x)] = (-x)( —x - 3x?) =0 1D} [oy=X0) Pesquisa Operacional II apy) 122 22/11/2023 max XyZ yz —2A,x -—Az, = 0, (1) sujeito a: Passo 5: Resolver o sistema xz — 2Ay = 0, (2) x*ty2=1 xy — A, = 0, (3) x+z=1 x2 4+y?2 =1, (4) x+z=1, 5 * Sey #0: (9) * (1-x)(—x-—3x?)=0, logo: x=1 ou x= os ou x= NS * Sabemos que y* =1—x?, z=1-x, Ay => Az = xy. * Nossas solugdes para y # 0 sdo: (228 V22 -2Vv13 7+ Vi3 82+ 22V13 16+ V3) 6 , 6 , 6 12 , 9 (= = VI3_ | V22—-2v13 7+ Vi3 -V/82 + 22V13 “16+ V3) 6 , 6 , 6 12 , 9 (= —vi3 ¥22+2V13 7-Vi3 —J82-22V13 -/16 - 13) 67 6 “6! 12 , 9 (228 22+ 2V13 7-13 82 -22V13 vis—Vi3) 6 + 6 , 6 12 , 9 1D} [oy=X0) Pesquisa Operacional II 123 123 max xyz yz —2A,4x —A, = 0, (1) sujeito a: Passo 5: Resolver o sistema xz — 2A,y = 0, (2) x? +y2=1 xy —A, =0, (3) x+z=1 x? +y? =1, (4) x+z=1, (5) Passo 6: Nossos candidatos a maximo (importante: garantidas as condicdes de regularidade) estdo entre: (228 V22 - 2V13 7+VB3) 6 , 6 , 6 (228 22 = 2v13 7 +V15 ) 6 , 6 , 6 (228 V22 + 2v13 1-5) 6 , 6 , 6 (228 V22 + 2V73 =v) 6 oF 6 , 6 (1,0,0) 1D} [oy=X0) Pesquisa Operacional II 124 124 22/11/2023 125 Teorema de Weierstrass * Toda fungdo f: K C R” > R continua definida no conjunto compacto K (nao-vazio) possui pelo menos um maximo global e pelo menos um minimo global em K. * Um subconjunto K Cc R” é compacto se ele é limitado e fechado. 1D} [oy=X0) Pesquisa Operacional II 126 126