Introdução à Programação Não Linear

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 PROGRAMAÇÃO NÃO LINEAR Programação Não Linear Introdução a Otimização Não Linear Introdução a Otimização Não Linear OTIMIZAÇÃO Procurar a melhor solução possível para um determinado problema de programação matemática Introdução a Otimização Não Linear No mundo real podemos nos deparar com problemas nos quais as RESTRIÇÕES e as FUNÇÕES OBJETIVOS NÃO SÃO LINEARES Ex Custo de Transporte unitário por km rodado não será necessariamente linear Análise de investimento em ações Problemas de mix de produção variação da margem de lucro por produto de acordo com a quantidade vendida Introdução a Otimização Não Linear Os problemas de PNL são difíceis de serem resolvidos porém comuns na prática Os algoritmos de PNL são os mais diversos e mais complexos Os problemas de PNL podem ser classificados PNL irrestrita com uma única variável ou com múltipla variáveis PNL com restrição inclui programação côncava convexa quadrática e separável Introdução a Otimização Não Linear Na Programação Não Linear PNL Não existe um método de resolução que sobressaia dentre outros Existe vários métodos de soluções de problemas de PNL Em função do número de variáveis de decisão Pelo uso ou não da derivada Pela presença ou não das restrições irrestrito ou restrito Introdução a Otimização Não Linear A formulação de um modelo de programação matemática pode ser representada como Introdução a Otimização Não Linear Multiplicadores de Lagrange Método do Gradiente Programação Quadrática Condições KarushKuhn Tucker Método de Newton Método das variáveis não coordenadas Linearização de funções separáveis Uso de Metaheurísticas Substituição Gráfico Introdução a Otimização Não Linear O principal conceito envolvido em PNL é o da taxa de variação derivadas e gradientes E o grande problema que dificulta a obtenção de soluções ótimas GLOBAL são os mínimos e máximos extremos locais da função objetivo GERANDO OS ÓTIMOS LOCAIS Introdução a Otimização Não Linear Se conhecermos o princípio de busca da solução ÓTIMA da maioria dos métodos existentes para problemas de PNL O vetor gradiente fornece a direção de maior taxa de variação da função escolhese arbitrariamente um ponto qualquer uma possível solução e caminhase nesta direção para um próximo ponto outra solução que teoricamente é melhor que a anterior Introdução a Otimização Não Linear Porém se a solução inicial escolhida arbitrariamente estiver fora da região de convergência da solução ótima o resultado será apenas uma solução subótima Introdução a Otimização Não Linear Exemplo 𝑀𝑖𝑛𝑍sin𝑥12cos𝑥23 𝑟𝑒𝑠𝑡𝑟𝑖çõ𝑒𝑠𝑥13𝑥220 7𝑥14𝑥245 𝑥1𝑥20 Analisando a função objetivo e as restrições qual método é uma alternativa viável nessa solução Introdução a Otimização Não Linear Introdução a Otimização Não Linear Solução Gráfica de um Problema de Programação Linear Como o espaço de soluções contém um número infinito de pontos é necessário um procedimento formal para identificar a solução ótima Taha2007 Para analisar a direção em que a função objetivo decresce função de minimização diferentes valores foram atribuídos por tentativa e erro Introdução a Otimização Não Linear TEOREMA 32 Outro importante teorema afirma que uma solução ótima de um problema de programação linear está sempre associada a um vértice ou ponto extremo do espaço de soluções Para problemas de programação linear com uma única solução ótima a função objetivo atinge seu ponto máximo ou mínimo em um ponto extremo do conjunto convexo K Introdução a Otimização Não Linear Introdução a Otimização Não Linear Esse teorema não é válido para problemas de PNL Aqui a solução ótima pode assumir qualquer valor no conjunto de soluções factíveis seja na fronteira mas não necessariamente em um ponto extremo ou no interior da região viável Essa característica aumenta a complexidade de solução dos problemas de programação não linear A seguir alguns exemplos com essas características baseados nos trabalhos de Hillier e Lieberman 2005 e Lachtermacher2009 Introdução a Otimização Não Linear Otimização Não Linear Método de Solução Gráfica Função Objetivo linear e restrições não lineares Considere Determinaremos a solução gráfica e se a solução ótima é um ponto extremo da região de aceitação Solução Repare que o espaço de soluções factíveis passa a ser representado não apenas por retas incluindo também curvas ou funções não lineares primeira restrição A solução ótima nesse caso não corresponde mais a um ponto extremo da região factível como ocorria nos problemas de PL mas encontrase na sua superfície Função Objetivo linear e restrições não lineares CASO 1 Neste exemplo todas as restrições são lineares porém a função objetivo é uma função quadrática Função Objetivo linear e restrições não lineares Função Objetivo linear e restrições não lineares Esta função pode ser reescrita como Função Objetivo linear e restrições não lineares CASO 2 Analogamente ao exemplo anterior a função objetivo é uma função quadrática nesse caso uma elipse podendo ser reescrita como Pode ocorrer ainda um segundo caso com as mesmas condições do exemplo anteriorfunção objetivo não linear e restrições lineares em que a solução ótima encontra se no interior da região viável e não na sua superfície Função Objetivo linear e restrições não lineares Como as restrições não se alteram em relação ao exemplo anterior o conjunto de soluções factíveis é o mesmo Função Objetivo linear e restrições não lineares Portanto para os três casos analisados a solução ótima não corresponde a um ponto extremo da região factível sendo um ponto na superfície ou no interior da região factível Essa característica torna os problemas de PNL muito mais complexos quando comparados aos problemas de PL já que um conjunto infinito de soluções deve ser testado até se encontrar a solução ótima Otimização Não Linear Método por substituição Método por substituição Exemplo 1 𝑀𝑎𝑥𝑍2𝑥8𝑦 restrições2𝑥22𝑦20 𝑥5 𝑥𝑦0 x5 y 0 𝑥0 Região factível PASSO 1 Pegamos a primeira inequação e igualamos a 20 ou seja transformamos numa equação 2𝑥22𝑦20 2𝑦202𝑥22 𝑦10𝑥2 PASSO 2 De posse dessa informação substituímos na função objetivo Logo 𝑍2𝑥810𝑥2 𝑍2𝑥808𝑥2 Método por substituição PASSO 3 Derivamos a função Z em X 𝑍2𝑥808𝑥² 2028𝑥 16𝑥2 Igualando a ZERO para determinar o valor de x 𝑥 1 8 dz dx dz dx Método por substituição Método por substituição PASSO 4 Voltando em Y temos 𝑦10 PASSO 5 Determinar o valor de Z 𝑍2𝑥8𝑦 𝑍2 8 80125 8 1 2 639 64 1 8 639 64 Método por substituição 𝑍2 8 80125 Esse é um ponto de mínimo ou de máximo Como podemos descobrir O valor da segunda derivada 16𝑥2 16 logo é ponto de máximo Função côncava 8 1 639 64 d z dx dz dx 2 2 Método por substituição 𝑦 9984375 𝑥 0125 𝑧80125 639 64 8 1 Função côncava correspondendo a um ponto de máximo 0 dx 2 2 d z Funções Convexas e Côncavas Uma função fx é convexa se um segmento de reta que une dois pontos dessa função está na superfície ou acima dela Uma função fx é côncava se um segmento de reta que une dois pontos dessa função está na superfície ou abaixo dela Se um segmento de reta une mais do que dois pontos dessa função ela não é nem convexa nem côncava Funções Convexas e Côncavas Os métodos para identificar se uma função é convexa ou côncava variam em função do número de variáveis no modelo uma única variável duas variáveis e mais de duas variáveis Funções Convexas e Côncavas Funções Convexas e Côncavas com uma Única Variável Funções Convexas e Côncavas Funções Convexas e Côncavas com uma Única Variável Funções Convexas e Côncavas Funções Convexas e Côncavas com uma Única Variável Exemplo Determine se as funções a seguir são convexas ou estritamente convexas côncavas ou estritamente côncavas convexas e côncavas simultaneamente ou nenhuma delas em um conjunto convexo S a 𝑓 𝑥 𝑥6 b 𝑓 𝑥 2𝑥4𝑥 2 2 fx0estritamente côncava fx0estritamente convexa Funções Convexas e Côncavas Para uma função fx1x2 com 2 variáveis determinase se ela é convexa ou côncava em um conjunto convexo S por meio da matriz Hessiana H que corresponde a uma matriz quadrada22 das derivadas parciais de segunda ordem da função Funções Convexas e Côncavas Pode ser definida como 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 Funções Convexas e Côncavas Exemplo Determine se a função abaixo é convexa ou estritamente convexa côncava ou estritamente côncava convexa e côncava simultaneamente ou nenhuma delas em um conjunto convexo S Hfx₁x₂²fx²₁²fx₂x₁²fx₁x₂²fx²₂4 4 4 4 Já o determinante de Hfx₁x₂ é 44440 Concluise portanto que fx₁x₂ é uma função côncava em S Se Det H 0 para alguns valores de x₁x₂ S a função não é nem convexa nem côncava em S fx₁x₂ 3x²₁ 2x²₂ 2x₁x₂ Funções Convexas e Côncavas F 𝑥 𝑥 2𝑥 2𝑥 𝑥 3𝑥 5𝑥 2𝑥 1 2 1 2 1 2 2 2 Máx 𝑥 𝑥 detH 12 estritamente côncava 6 1 6 7 1 1 2 2 Funções Convexas e Côncavas com múltiplas variáveis Otimização Não Linear Irrestrita Programação Não Linear Irrestrita Os problemas de programação não linear irrestrita podem ser divididos em dois tipos com uma única variável ou com múltiplas variáveis Programação Não Linear Irrestrita Os problemas de PNL irrestrita como o próprio nome diz não contêm restrições de forma que o modelo é simplesmente escrito em termos da função objetivo que busca maximizar ou minimizar uma função não linear com uma única variável x 𝐦𝐚𝐱 𝒐𝒖 𝐦𝐢𝐧𝒇𝒙 Programação Não Linear Irrestrita max𝑜𝑢min𝑓𝑥 Considere fx uma função diferenciávelou derivável que tem derivada Para que uma determinada solução de fx seja ótima xx ela deve satisfazer a seguinte condição 𝑑𝑓𝑥 dx 0 Programação Não Linear Irrestrita Programação Não Linear Irrestrita Exemplo Determine a solução ótima para a função e identifique se x é um ponto de mínimo ou máximo 𝑓 𝑥 10𝑥 4 Otimização Não Linear Métodos de Solução PNL Irrestrita Métodos de Solução Método da bisseção busca unidirecional O método da bisseção bisectionmethod é um método numérico bastante simples que busca determinar a raiz x de uma função fx não linear isto é determinar a solução analítica da equação fx 0 As raízes da função fx também podem ser determinadas de forma gráfica correspondendo aos valores de x em que a função intercepta o eixo horizontal do gráfico Como limitação do método da bisseção a convergência na determinação da raiz da função fx é muito lenta Métodos de Solução Método de Newton O método de Newton ou método de Newton Raphson também é um método numérico cujo objetivo é determinar uma função iteração que acelere a convergência na estimação das raízes de uma função não linear fx É geralmente bem mais rápido que o método da bisseçã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