Métodos de Solução para PNL Irrestrita com uma Única Variável

Universidade do Estado de Santa CatarinaUDESC Centro de Ciências Tecnológicas CCT Engenharia de Produção e Sistemas Pesquisa Operacional IIPOP2001 Prof Dr Adalberto J Tavares Vieira Métodos de Solução para PNL Irrestrita com uma Única Variável A estimativa do zero da função YfX é feita a partir do ponto médio do intervalo analisado Ele começa com a determinação dos pontos a e b que definem um intervalo onde existe uma solução Métodos de Solução Método da bissecção busca unidirecional A solução está contida ou na seção entre a e x0 ou na seção entre x0 e b Definese então como novo intervalo a seção que contém a raiz e seu ponto central será então a nova segundo estimativa O processo segue dessa forma até que se obtenha a precisão desejada Métodos de Solução Método da bissecção busca unidirecional ALGORITMO Escolha um intervalo a b que contenha a raiz A primeira estimativa da solução será x0 a b2 Verifique se a estimativa atende a precisão requerida Não atendendo determine um novo intervalo que contém a raiz Métodos de Solução Método da bissecção busca unidirecional ALGORITMO Isso pode ser obtido verificando o sinal do produto fafx0 Se fafx00 então a solução está entre x0 e a Se fafx00 então a solução está entre x0 e b Selecione o novo subintervalo que contém a raiz e determine a nova estimativa xi calculando o ponto médio dos intervalos Métodos de Solução Método da bisseção busca unidirectional ALGORITMO Precisão Requerida Erro ou tolerância Consideramos como precisão neste método a aproximação entre xi e α Assim a precisão terá sido atingida quando α xi ε Como não conhecemos α adotamos como precisão a diferença b α 2 ε Métodos de Solução Método da bisseção busca unidirecional Exemplo 07 Seja fx x³ x 1 Intervalo inicial atribuído 1 2 Considerandose ε 0002 fa₀ 1 fb₀ 5 fx 3x² 1 fa₀ fb₀ 5 0 Sinal da derivada constante fa₀ 2 e fb₀ 11 Métodos de Solução Método da bisseção busca unidirecional Exemplo 07 fx x³ x 1 Cálculo da 1ª aproximação x₁ a₀b₀2 100000020000002 x₁ 1500000 fx₁ 15³ 15 1 0875000 Teste de Parada fx₁ 0875 0875000 0002 Escolha do Novo Intervalo fa₀fx₁ 10875 0875 logo a₁a₀1000000 e b₁x₁1500000 Métodos de Solução Método da bissecção busca unidirecional Exemplos 07 fx x³ x 1 k ak bk fak fbk xk1 fxk1 0 10000000 20000000 10000000 50000000 15000000 08750000 1 10000000 15000000 10000000 08750000 12500000 0296875 2 12500000 15000000 02968750 08750000 13750000 0224609 3 12500000 13750000 02968750 02246090 13125000 0051514 4 13125000 13750000 00515144 02246090 13437500 0082611 5 13125000 13437500 00515144 00826110 13281250 0014576 6 13125000 13281250 00515144 00145760 13203125 0018711 7 13203125 13281250 00187100 00145760 132421875 0002128 Métodos de Solução Método de Newton O método de Newton ou método de NewtonRaphson também é um método numérico cujo objetivo é determinar uma função iteração que acelere a convergência na estimativa das raízes de uma função não linear fx É geralmente bem mais rápido que o método da bissecção Para que a convergência seja satisfatória o valor inicial estimado deve ser adequado isto é suficientemente próximo da raiz da função Métodos de Solução Método de Newton Umas das condições de convergência é que φx M I para todo e qualquer x pertencente ao intervalo I Onde I é um intervalo centrado na raiz A convergência do método será mais rápida quanto menor for φξ onde ξ é a raiz da função O que o método de Newton faz para tentar garantir e acelerar a convergência é escolher pela função de iteração a função φx tal que φξ0 Método de Newton Geometricamente temos Dado o ponto xk fxk traçamos a reta Lkx tangente a curva neste ponto Lkx fxk fxkx xk Lkx é um modelo linear que aproxima a função fx numa vizinhança de xk Encontrando o zero deste modelo temos Método de Newton Lkx é um modelo linear que aproxima a função fx numa vizinhança de xk Encontrando o zero deste modelo temos xk1 xk fracfxkfxk chute inicial Graficamente temos Método de Newton Exemplo Considere fx x2 x 6 ξ2 e x0 15 Fórmula recursiva xk1 xk fracfxkfxk xk fracxk2 xk 62xk 1 Temos pois x0 15 x1 20625 x2 200076 x3 200000 PNL Irrestrita com MÚLTIPLAS Variáveis Analogamente ao exemplo anterior esse modelo é simplesmente escrito em termos da função objetivo PNL sem restrições porém buscando maximizar ou minimizar uma função não linear com n variáveis max ou min f x1x2x3xn PNL Irrestrita com MÚLTIPLAS Variáveis Para encontrar a solução ótima de fx1x2xn representada pelo vetor x xx1x2xn basta resolver de forma analítica o seguinte sistema de n equações com n incógnitas x1 fx1x2xn0 x2 fx1x2xn0 xn fx1x2xn0 em que xi fx1x2xn para i1n representam as derivadas parciais de fx1x2xn em relação à xi PNL Irrestrita com MÚLTIPLAS Variáveis Analogamente ao problema de PNL irrestrita com uma única variável para determinar se a solução ótima é um ponto de máximo mínimo ou inflexão calculamse as derivadas parciais de primeira ordem n1 segunda ordem n2 e assim por diante para cada variável xi até que a derivada parcial na ordem n nxi n fx seja uma constante com sinal positivo negativo ou nulo Se n é par e nxi n fx0 para cada xi os pontos de x são com certeza de mínimo Se n é par e nxi n fx0 para cada xi os pontos de x são com certeza de máximo Se n é ímpar para cada xi os pontos de x são com certeza de inflexão PNL Irrestrita com MÚLTIPLAS Variáveis Determine a solução ótima para a função e identifique se são pontos de máximo mínimo ou inflexão fx1x23x124x2218x116x210 PNL Irrestrita com MÚLTIPLAS Variáveis Primeiramente calculamse as derivadas parciais da função fx1x2 em relação à x1 e x2 respectivamente fracpartialpartial x1fx1x26x118 fracpartialpartial x2fx1x28x216 Para determinar a solução ótima da função fx1x2 basta igualar a zero cada uma das equações anteriores obtendo x1 e x2 respectivamente 6x1180 rightarrow x13 8x2160 rightarrow x22 Para identificar se x são pontos de máximo ou mínimo n é par basta calcular a derivada parcial de segunda ordem de fx e verificar seu sinal fracpartial2partial x12fx13x2260 fracpartial2partial x22fx13x2280 Métodos de Solução PNL Irrestrita com Múltiplas Variáveis Os métodos de solução de problemas de PNL irrestrita com múltiplas variáveis podem ser classificados como métodos de busca direta e métodos de descida ou indiretos Métodos de Solução PNL Irrestrita com Múltiplas Variáveis Métodos de Busca Direta São métodos que minimizam ou maximizam uma função com múltiplas variáveis sem o uso da derivada da função objetivo Em geral os métodos que usam derivadas convergem mais rapidamente quando comparados aos métodos de busca direta Dentro os métodos de busca direta destacamse método de busca aleatória método de busca seccionada método de Hooke e Jeeves com busca linear método de Rosenbrock e método simplex Métodos de Solução PNL Irrestrita com Múltiplas Variáveis Método de Busca Aleatória É um método que utiliza números aleatórios para encontrar a solução ótima São menos eficientes comparados a outros métodos de busca direta Não exige chutes iniciais Método de Busca Seccionada O método utiliza várias direções de busca porém a cada vez a busca é feita em uma única direção utilizando métodos unidimensionais Métodos de Solução PNL Irrestrita com Múltiplas Variáveis Método de Hooke e Jeeves com busca linear É uma adaptação do método original proposto por Hooke e Jeeves utilizando buscas lineares Esse método realiza dois tipos de busca exploratória e progressiva A busca exploratória estima a direção provável do ponto extremo a partir de um ponto inicial Já a busca progressiva percorre essa direção enquanto o valor da função objetivo diminuir minimização ou aumentar maximização Método de Rosenbrock Segundo Brandão 2010 o método de Rosenbrock não utiliza buscas lineares mas sim passos discretos ao longo das direções de busca É uma adaptação do método de Hooke e Jeeves em que em vez da busca ocorrer na direção dos eixos das coordenadas utilizamse novas direções ortogonais Método Simplex Avalia a função objetivo para cada um dos pontos extremos do polígono simplex Métodos de Descida ou Métodos Indiretos São métodos que utilizam a primeira eou a segunda derivada da função objetivo para definir as direções de busca Dentre eles destacamse método de Newton método do QuaseNewton método do gradiente e método do gradiente conjugado Método de Newton Utiliza a segunda derivada da função objetivo para definir a direção de busca Se a função objetivo é quadrática o mínimo da função é encontrado em apenas uma iteração Método do QuaseNewton É uma variante do método de Newton que calcula apenas a primeira derivada da função objetivo Uma vez que a segunda derivada não é necessária o método do QuaseNewton é muitas vezes mais eficiente que o método de Newton Método do Gradiente Também conhecido como método da inclinação descendente steepest descent ou da descida mais íngreme problema de minimização Chamado de subida mais íngreme em inglês steepest ascent É um método simples que usa os gradientes para direcionar a busca Utiliza apenas a primeira derivada da função objetivo no processo de busca Porém muitas vezes a busca estaciona em ótimos locais Método do Gradiente Para entender a concepção básica deste método a figura abaixo é apresentada Método do Gradiente Na faixa entre a e b e entre c e d a derivada gradiente da função é positiva e na faixa entre b e c a derivada gradiente da função é positiva Observe que xb é um ponto de máximo e que xc é um ponto de mínimo Um procedimento recursivo que levaria ao valor de x em que a função assume seu valor máximo ou seja xb seria aquele que partindo de condições iniciais entre a e b caminharia para a direita na direção de b e que partindo de condições iniciais entre b e c caminharia para a esquerda na direção de b portanto o procedimento recursivo caminha sempre na mesma direção do gradiente da função Métodos de Solução PNL Irrestrita com Múltiplas Variáveis Método do Gradiente Um procedimento recursivo que levaria ao valor de x em que a função assume seu valor máximo ou seja xb seria aquele que partindo de condições iniciais entre a e b caminharia para a direita na direção de b e que partindo de condições iniciais entre b e c caminharia para a esquerda na direção de b portanto o procedimento recursivo caminha sempre na mesma direção do gradiente da função Xk1 Xk λfXk onde λ é um escalar positivo Métodos de Solução PNL Irrestrita com Múltiplas Variáveis Método do Gradiente Por outro lado um procedimento recursivo que levaria ao valor de x em que a função assume seu valor mínimo xc seria aquele que partindo de condições iniciais entre b e c caminharia para a direita direção de c e que partindo de condições iniciais entre c e d caminharia para a esquerda direção de c portanto o procedimento recursivo caminha sempre na direção contrária à do gradiente da função Xk1 Xk λfXk onde λ é um escalar positivo Métodos de Solução PNL Irrestrita com Múltiplas Variáveis Método do Gradiente Exemplo fx xx² 100 Derivada da função gx fx 3x² 100 Raízes x 5774 Aplicando x 5774 na segunda derivada temos F5774 6x5774 0 PONTO DE MÁXIMO F5774 6x5774 0 PONTO DE MÍNIMO fx xx² 100 O método do gradiente de subida mais ingreme é neste exemplo descrito pelo procedimento recursivo Xk1 Xk λxk² 100 com λ 0 e para k 0 1 2 com X0 chute inicial Adoptando este algoritmo com X0 10 e λ 01 resulta O exemplo demonstra que a escolha de um valor adequado de λ é primordial para a convergência do procedimento Por inspeção verificase que quando se utiliza o chute inicial igual 10 ou 10 na busca do ponto de mínimo o procedimento só converge com valores de λ menores do que 006 além disto verificase que este valor mínimo de λ pode depender do chute inicial adotado Método do Gradiente Exemplo 2 De uma longa folha de metal de 30 cm de largura devese fazer uma calha dobrando as bordas perpendicularmente à folha Quantos centímetros devem ser dobrados de cada lado de modo que a calha tenha capacidade máxima Método do Gradiente Exemplo 2 A capacidade de escoamento de água da calha é formalmente a vazão QAv é a vazão cm³s A é a área da seção cm² v é a velocidade do fluído cms QAvAv Método do Gradiente Exemplo 2 Supondo v constante a vazão tornase diretamente proporcional à área da seção Portanto maximizando A implica em maximizar QAv fx x302x 30x2x² Por inspeção do gráfico anterior verificase que a função alcança o máximo óptimo em x 75 Método do Gradiente Exemplo 2 Resolvendo pelo método do gradiente Xk1 Xk λfXk onde λ é um escalar positivo fx x302x 30x2x² fx 304x xi1 xi t304xi resíduo xi1xi Processo iterativo cessa quando resíduo é menor que precisão desejada critério de parada Para t01 1ª iteração x0 3 x1 3 0130 43 12 resíduo42 2ª iteração x1 12 x2 12 0130 412 372 resíduo252 19ª iteração x19 74982 x20 74982 t30 474982 74998 resíduo00016 Método do Gradiente Exemplo 2 Resolvendo pelo método do gradiente O gráfico da esquerda mostra o caminho de busca trajetória da solução ótima realizada pelo algoritmo para t 01 e da direita para t 04 trajetória é função do tamanho do passo Deve existir um tamanho de passo ótimo Método do Gradiente Exemplo 2 Resolvendo pelo método do gradiente A solução ótima será alcançada mais rapidamente quanto menos a Função Objetivo for avaliada Para isso vamos fazer sem perda de generalidade algumas alterações no Método do Gradiente substituindo xi1 por Zt ou seja uma expressão que é função do tamanho do passo t e xi por simplesmente x O Método então fica Zt x tfx x tfx Métodos de Solução PNL Irrestrita com Múltiplas Variáveis Substituindo Zt em fx temos gt fZt Igualando a derivada de gt em relação a t a zero gt0 e então resolvendo para t encontrase uma função que descreve os valores ótimos de t para cada solução x No exemplo Zt fica Zt x t30 4x Substituindo Zt em f fica gt 30x 900t 240xt 2x² 16x²t 480xt² 1800t² 32x²t² gt 900 240x 16x² 960t 3600t 64x²t Resolvendo para t 1ª iteração t 025x²30 4x R 75 x0 3 x1 3 02530 43 75 Programação Não Linear COM RESTRIÇÃO Métodos de Solução PNL Irrestrita com Múltiplas Variáveis Programação Não Linear COM RESTRIÇÃO Multiplicadores de Lagrange Segundo Winston 2004 os multiplicadores de Lagrange podem ser utilizados para resolver problemas de PNL em que todas as restrições estão escritas na forma de igualdade Considere o seguinte problema de PNL max ou min zfx1x2xn sujeito a g1x1x2xnb1 g2x1x2xnb2 gmx1x2xnbm x1x2xn0 Multiplicadores de Lagrange Para resolver o problema 710 multiplicase cada iésima restrição gix1x2xnbi por uma constante λi denominada multiplicador de Lagrange λibigix1x2xn Essas equações são adicionadas à função objetivo formando a chamada Lagrangiana Lx1x2xnλ1λ2λmfx1x2xnmi1λibigix1x2xn Para encontrar os valores de x1x2xn e λ1λ2λm calculamse as derivadas parciais da Lagrangiana e as mesmas são igualadas a zero L xj0 j1n L λi0 i1m Programação Não Linear COM RESTRIÇÃO Outros métodos de solução para problemas de PNL métodos de busca direta método do gradiente reduzido generalizado e métodos de plano de corte e métodos de busca indireta métodos sequenciais de maximização e minimização sem restrições e métodos de transformações de variáveis Exemplos Winston2004 Uma empresa de pneus quer investir em dois novos equipamentos a prensa plana x e a linha de raspa y Cada unidade de prensa plana e cada unidade de linha de raspa adquirida requer a compra de 2 novos adaptadores A empresa já decidiu que vai comprar 12 adaptadores O lucro obtido a partir dos novos equipamentos pode ser representado pela função Determinar a solução ótima e verificar se esta é uma função convexa ou estritamente convexa côncava ou estritamente côncava convexa e côncava simultaneamente ou nenhuma delas Exemplo Winston2004 O modelo pode ser representado matematicamente como max z fxy x² y² xy 6x 2y sujeito a 2x 2y 12 O modelo pode ser representado matematicamente como max z fxy x² y² xy 6x 2y sujeito a 2x 2y 12 xy 0 A Lagrangiana Lxyλ de 713 pode ser calculada como Lxyλ x² y² xy 6x 2y λ12 2x 2y Funções Convexas e Côncavas com Duas Variáveis A classificação se uma função é convexa ou estritamente convexa ou côncava ou estritamente côncava depende dos elementos da diagonal principal de H além do cálculo do seu determinante Det H conforme mostra a Tabela 71 Tabela 71 Classificação das funções com duas variáveis a partir da matriz H para x₁ x₂ S Classificação ²fx₁² Convexa 0 Estritamente convexa 0 Côncava 0 Estritamente côncava 0 Novamente cabe listar duas observações em relação à classificação listada anteriormente a Se fx é uma função linear e consequentemente Det H 0 ²fx₁² 0 e ²fx₂² 0 a função é simultaneamente convexa e côncava em S b Se Det H 0 para alguns valores de x₁ x₂ S a função não é nem convexa nem côncava em S Condições de KarushKuhnTucker As condições de KarushKuhnTucker KKT podem ser aplicadas para verificar se uma determinada solução de um problema de PNL é ou não um óptimo local De início o problema de PNL deve estar representado matematicamente como max z fx1 x2 ldots x sujeito a g1x1x2ldotsx leq b1 g2x1x2ldotsx leq b2 vdots gmx1x2ldotsx leq bm x1 x2 ldots x geq 0 Condições de KarushKuhnTucker Segundo Colin 2007 a solução x1 x2 ldots xn de 721 é um óptimo local se e somente se existirem as constantes lambda1 lambda2 ldots lambdam que satisfaçam as seguintes condições Condição 1 de KKT fracpartial fx1 x2 ldots xnpartial xi sumi1m lambdai fracpartial gix1 x2 ldots xnpartial xi leq 0 j1ldotsn Condição 2 de KKT xj left fracpartial fx1 x2 ldots xnpartial xj sumi1m lambdai fracpartial gix1 x2 ldots xnpartial xj right 0 j1ldotsn Condição 3 de KKT lambdai bi gix1 x2 ldots xn 0 i1ldotsm Condição 4 de KKT lambdai geq 0 i1ldotsm Qualquer solução x1 x2 ldots xn que satisfaz as quatro condições de KKT é chamada ponto de KKT Condições de KarushKuhnTucker Exemplo Considere o seguinte problema de PNL max z x12 x22 4x1 2x2 sujeito a x1 x2 leq 12 x2 leq 6 x1 x2 geq 0 Verifique as condições de KKT e determine o óptimo local Resposta Verificase que todas as demais condições são atendidas de modo que a solução x1 x2 lambda1 e lambda2 12 0 28 0 com z192 é um máximo local Veremos na próxima seção que essa solução também é a óptima global Condições de KarushKuhnTucker As condições de KKT são condições necessárias para encontrar o ótimo local de um problema de PNL mas não garantem que o ótimo local seja um ótimo global Para um problema de maximização de PNL se fx₁x₂xₙ é uma função côncava e gᵢx₁x₂xₙ para i1m são funções convexas então qualquer ponto x₁x₂xₙ que satisfaça as condições de KKT ótimo local é também um ótimo global Para um problema de minimização de PNL se fx₁x₂xₙ e gᵢx₁x₂xₙ para i1m são funções convexas então qualquer ponto x₁x₂xₙ que satisfaz as condições de KKT ótimo local é também um ótimo global