Otimização Não Linear Irrestrita

Prévia do material em texto

UNIVERSIDADE FEDERAL DE SÃO JOÃO DEL-REI 
CURSO DE GRADUAÇÃO EM ENGENHARIA MECÂNICA 
 
 
Davi Otoni Saraiva 
Jefferson Guilherme da Silva Ferreira 
João Pedro de Almeida Miguel 
João Vitor Leão Silva 
Lucas Christiano de Abreu 
Teodoro Carrilho 
Thiago Pereira Ribeiro 
Vinícius Eduardo Brasileiro Teixeira 
Yuri Antônio Alcântara Aguiar 
 
 
 
 
OTIMIZAÇÃO NÃO LINEAR IRRESTRIRA 
 
 
 
 
 
 
 
 
 
São João del-Rei 
2019
 
 
 
 
 
Davi Otoni Saraiva 
Jefferson Guilherme da Silva Ferreira 
João Pedro de Almeida Miguel 
João Vitor Leão Silva 
Lucas Christiano de Abreu 
Teodoro Carrilho 
Thiago Pereira Ribeiro 
Vinícius Eduardo Brasileiro Teixeira 
Yuri Antônio Alcântara Aguiar 
 
 
 
OTIMIZAÇÃO NÃO LINEAR IRRESTRITA 
 
 
 
Trabalho Acadêmico apresentado na Matéria de Otimização 
de Sistemas em Engenharia da Universidade Federal de São 
João del-Rei no Curso de Engenharia Mecânica 
 
Professor: M.e. Waslley Amaral Coelho 
 
 
 
 
 
São João del-Rei 
2019 
 
 
RESUMO 
Este trabalho irá discutir acerca da Otimização Não Linear Irrestrita, uma forma mais complexa 
e completa, utilizada para sistemas de engenharia mais complicados. O trabalho apresentado 
em sala, pretende explicar de forma prática aos alunos esse tipo de sistema, para que haja um 
grande entendimento da turma. A programação não linear trata-se de encontrar o x = (x1, x2, ..., 
xn). de modo a maximizar f(x), sujeito a gi(x) ≤ bi, para i = 1,2, ...., m; e x≥0. Com essa base, o 
trabalho explicará um tipo dessa programação, que não apresenta restrições, de modo que o 
objetivo seja simplesmente maximizar f(x) ao longo de todos os valores de x = (x1, x2, ..., xn). 
 
 
 
LISTA DE FIGURAS 
Figura 1 – Restrição................................................................................................................... 5 
Figura 2 – Função Côncava....................................................................................................... 6 
Figura 3 – Resumo 1.................................................................................................................. 7 
Figura 4 – Série de Taylor.......................................................................................................... 8 
Figura 5 – Resumo 2.................................................................................................................. 8 
Figura 6 – Definição Grandiente................................................................................................ 9 
Figura 7 – Resumo 3...................................................................................................................9 
 
 
 
 
SUMÁRIO 
INTRODUÇÃO ....................................................................................................................... 5 
DESENVOLVIMENTO.......................................................................................................... 6 
CONCLUSÃO..................................................................................................................... ... 10 
REFERÊNCIAS.......................................................................................................... ........... 11 
 
 
 
 
1. INTRODUÇÃO 
A Programação não linear trata-se se de um tipo de programação de problemas 
envolvendo um x = (x1, x2, ..., xn), no qual deve-se: 
 
maximizar f(x), 
 sujeito a, 
a gi(x) ≤ bi, para i = 1,2, ...., m, 
e 
x≥0, 
em que f(x) e os gi(x) são funções dadas das n variáveis da decisão. 
 Existem vários problemas de otimização não linear, que muda de acordo as 
características de f(x) e gi(x), cada uma possui diferentes algoritmos de resolução. 
A otimização irrestrita trata-se da otimização que não possui restrições, ou seja, o 
objetivo é apenas maximizar f(x) ao longo de todos os valores de x = (x1, x2, ..., xn). A 
condição necessária para que determinada solução x=x* seja ótima quando for f(x) for uma 
função diferenciável é que: 
𝝏𝒇
𝝏𝒙𝒊
= 𝟎 em x = x*, para j = 1,2, . . ., n. 
Quando f(x) for uma função côncava, essa condição também é suficiente, de forma que 
encontrar a solução para x* reduz-se a resolver o sistema de n equações obtidas 
configurando-se as n derivadas parciais iguais a zero. Quando a variável de xi não apresentar 
restrição de não negatividade, a condição precedente necessária e suficiente muda um 
pouco. 
 
Figura 1: Restrição. 
para cada j deste. 
 
 
2. DESENVOLVIMENTO 
A otimização não linear irrestrita possui dois tipos e cada uma possui seus 
métodos de resolução. O primeiro a ser mostrado é a Otimização não linear irrestrita 
com uma variável, na qual n=1 e a função diferenciável f(x) a ser maximizada é 
côncava. Portanto a condição necessária e suficiente para a determinada solução x = x* 
ser a solução ótima é: 
𝒅𝒇
𝒅𝒙
= 0 𝑒𝑚 𝑞𝑢𝑒 𝑥 = 𝑥 ∗ 
Se essa função puder ser resolvida diretamente para x*, o processo está 
concluído. Entretanto, se f(x) não for uma função particularmente simples e, portanto, a 
derivada não for apenas uma função linear ou quadrática, talvez não consiga resolver a 
equação analiticamente. 
Desse modo, serão apresentados métodos de busca para resolver a o problema 
numericamente. Esses procedimentos de busca se baseiam em uma série de soluções 
experimentais que levam a solução ótima. Agora serão apresentados os dois principais, 
o método de bissecção e o método de Newton. 
2.1. MÉTODO DE BISSECÇÃO 
Esse procedimento de busca, sempre pode ser aplicado quando f(x) for côncava, 
conforme representado na Figura 2. Ele também pode ser usado para algumas outras 
funções. Em particular, se x* representa a solução ótima, tudo que é necessário é que: 
 
Figura 2: Função Côncava 
Essas condições são satisfeitas quando f(x) for côncava, mas ela também pode ser satisfeita 
quando a segunda derivada for positiva para alguns valores de x. 
 
 
A ideia do método de bissecção é muito intuitiva, isto é, seja a derivada positiva ou negativa, 
em uma solução experimental indica em definitivo se a melhoria encontra imediatamente à 
direita ou à esquerda, respectivamente. 
x’ = solução experimental atual, 
x = limite inferior sobre x*, 
�̅� = limite superior atual sobre x*, 
Є = tolerância de erro para x*. 
Embora existam várias regras para selecionar cada nova solução experimental, aquela usada 
no método da bissecção é a regra do ponto médio, que diz simplesmente para selecionar o ponto 
médio entre dois limites atuais. 
 
 
Figura 3: Resumo 1 
2.2.MÉTODO DE NEWTON 
Embora o Método de Bissecção seja um procedimento intuitivo e simples, ele apresenta 
uma desvantagem de convergir relativamente lenta para uma solução ótima. Cada iteração 
diminui apenas pela metade a diferença entre os limites. 
 A razão básica para essa lenta convergência é o fato da única informação sobre a f(x) 
que está sendo empregada ser o valor da primeira derivada de f(x) nos respectivos valores 
experimentais de x. Informações úteis adicionais podem ser obtidas considerando a segunda 
derivada f”(x) também. É isso que o Método de Newton faz. 
 O conceito básico do método de Newton é aproximar f(x) nas vizinhanças da solução 
experimental atual por meio de uma função quadrática e, depois, maximizar a função 
aproximada exatamente para obter a nova solução experimental para iniciar a iteração 
seguinte. Essa função quadrática aproximada é obtida truncando-se a série de Taylor após 
o termo da segunda derivada. Particularmente fazendo-se xi+1 seja a solução experimental 
 
 
inicial fornecida pelo usuário para começar a iteração 1), a série de Taylor truncada para 
xi+1 ficará de acordo as imagens a seguir: 
 
 
Foto 4: Série Taylor 
 
E então temos o resumo da série 
 
 
Foto 5: Resumo 2 
2.3.MÉTODO DE BUSCA POR GRADIENTE 
Agora existem inúmeras direções possíveis para as quais se mover, elas correspondemàs possíveis taxas proporcionais nas quais as respectivas variáveis básicas podem ser 
alteradas. O objetivo é atingir eventualmente um ponto em que todas as derivadas parciais 
sejam 0. Portanto, uma metodologia natural seria usar os valores das derivadas parciais para 
 
 
selecionar a direção específica na qual se movimentar. Nessa seleção emprega-se o 
gradiente da função objetivo, conforme descrito a seguir na imagem. 
 
Foto 6: Definição Gradiente 
 A importância do gradiente reside no fato de que a mudança em que x que maximiza a 
taxa na qual f(x) aumenta é a mudança proporcional a ∇ f(x). Para expressar essa ideia 
geometricamente, a “direção” do gradiente ∇ f(x’) interpreta-se como a direção do segmento 
de reta direcionado a partir de (0,0, ..., 0) até o ponto (
𝜕𝑓
𝜕𝑥1
, 
𝜕𝑓
𝜕𝑥2
, ..., 
𝜕𝑓
𝜕𝑥𝑛
), em que calcula-se a 
𝜕𝑓
𝜕𝑥𝑗
 em xj = x
’
j. Portanto, pode-se dizer que a taxa na qual f(x) aumenta é maximizada se 
mudanças em x estiverem na direção do gradiente ∇ f(x). Uma vez que o objetivo é encontrar 
a solução viável que maximiza f(x), seria oportuno tentar se mover o máximo possível na 
direção do gradiente. 
 Com a metodologia do método de gradiente temos o seguinte resumo: 
 
Foto 7: Resumo 3 
 
 
 
3. CONCLUSÃO 
Por muitas vezes encontramos problemas práticos que envolvem a não linearidade 
irrestrita na otimização e devem ser levados em conta. É perceptível nesse trabalho que 
não existe um método genérico que resolva todos os tipos de problemas de otimização 
irrestrita, o que dificulta um pouco no estudo, por muitas vezes se tratarem de métodos 
complexos e que exigem cálculos mais avançados com derivadas parciais de muitas 
variáveis. 
Mas há atualmente um grande desenvolvimento de softwares que trabalham com esse 
tipo de programação, o que facilita ao ir trabalhar nessa área, por seriam cálculos longos e 
talvez sem uma resposta totalmente precisa. 
O estudo dessa área, por fim, deve ser tão grande as resoluções por método simplex da 
otimização linear, mesmo que mais incomum por vezes, porque são grandes as chances de 
se deparar com esses tipos de programações não lineares. 
 
 
REFENRÊNCIAS 
HILLIER, Frederick S.; LIEBERMAN, Gerald J. Programação Não Linear. In: HILLIER, 
Frederick S.; LIEBERMAN, Gerald J. Introdução a Pesquisa Operacional. 9ª. ed. rev. 
Brasil: McGraw - Hill Education, 2010. v. Único, cap. 12, p. 512-580. ISBN 9788580551181. 
 
BREGADIOLI, Gabriela F. UMA INVESTIGAÇÃO DE MÉTODOS MISTOS DE 
OTIMIZAÇÃO NÃO LINEAR. SELMAT, Bauru, ano 1, v. 25, ed. 1, 2013.