AULA COMPUTACIONAL

Otimizao Paramtrica (Cap. 5)

15 DE SETEMBRO DE 2008

5.1 Conceito de Otimizao5.2 Elementos Comuns em Problemas de Otimizao 5.2.1 Variveis de Deciso (Manipuladas) 5.2.2 Critrio 5.2.3 Funo Objetivo 5.2.4 Restries 5.2.5 Regio Vivel5.3 Localizao da Soluo tima5.4 Problemas e Mtodos de Otimizao5.5 Mtodo Analtico: problemas univariveis e multivariveis.

5. OTIMIZAO PARAMTRICA5.6 Mtodos Numricos: problemas univariveis e multivariveis

5.6. MTODOS NUMRICOSOs mtodos podem ser: - Diretos: utilizam apenas o valor da Funo Objetivo. - Indiretos: utilizam tambm o valor da(s) derivada(s) da Funo Objetivo (menor nmeros de tentativas mas o esforo computacional maior).So mtodos de busca por tentativas.Os pesquisadores buscam desenvolver mtodos que atendam s seguintes propriedades:

- Eficincia: resolver o mesmo problema com menor esforo. - Robustez: resolver uma variedade maior de problemas.

5.6. MTODOS NUMRICOS 5.6.1 Problemas UnivariveisMtodo da Seo ureaUtiliza dois pontos posicionados de forma a manter:

(a) simetria em relao aos limites do intervalo (b) frao eliminada constante

Mtodo da Seo ureaBase: Retngulo ureo (esteticamente perfeito, segundo os gregos)Propriedade: removendo um quadrado de lado igual ao lado menor,resulta um outro retngulo com as mesmas propores do retngulo original Razo urea

Algoritmo da Seo ureaUREAIniciarRepetir Eliminar Regio Atualizar Delta Se Convergiu Ento Finalizar Colocar Novo PontoConvergiuDelta Tolerncia

LiLsxsxiFsFiD = L s - Lixi = LiD xs= Ls- 0,618D + 0,618InicializaoIniciarRepetir Eliminar Regio Atualizar Delta Se Convergiu Ento Finalizar Colocar Novo Ponto

Modelo Matemtico:1. Q (xo - x) - W y = 02. y - k x = 0 (k = 4)Balano de Informao: V = 5, N = 2, C = 2, M = 0 G = 1 (otimizao)Avaliao Econmica:L = R - CR = pAB W yC = pB WpAB = 0,4 $/kgAB : pB = 0,01 $/kgB5.5 MTODO ANALTICO 5.5.1 Problemas univariveisExemplo: dimensionamento do extrator

2. y = k x1. W = Q (xo - x)/y Seqncia de ClculoRestries de Igualdade !!!

Funo Objetivo: L = R - C = pAB W y - pB W

0,0060,0080,0100,0120,0140,0160,0180,0200,0220102030405060L,R,C$/ax kgAB/kg ALCRxo =0, 01118Lo = 15,6Busca do ponto estacionrio:yo = 0,04472 kg AB/kg B; Wo = 1.972,3 kgB/h; Ro = 35,3 $/h; Co = 19,7 $/h; Lo = 15,6 $/hSoluo completa do problema:L = a - b x - c/x

5.6. MTODOS NUMRICOS Procedimento Geral:(c) progresso na direo de busca at deciso em contrrio. (b) explorao da vizinhana da base para inferir uma direo de busca.(a) seleo de um ponto inicial (base).Os mtodos diferem quanto forma de executar a explorao e a progresso.Alguns mtodos diretos:- Busca Aleatria- Busca por Malhas- Busca Secionada- Simplex (Poliedros Flexveis)- Hooke & Jeeves5.6.2 Problemas Multivariveis(d) finalizao

Mtodo de Hooke & JeevesALGORITMOSeno: reduzir os incrementos Estabelecer um incremento e uma tolerncia para cada varivelEscolher uma BaseRepetirExplorar a vizinhana da Base (em busca da direo provvel do timo)Se houve Sucesso em alguma direoEnto: Progredir (na direo provvel) at haver um InsucessoSeno (proximidade do timo):Se Chegou ao timoEnto: Finalizar

ExploraoTestar a Funo Objetivo em cada sentido (incrementos + i e - i) de cada direo (xi) ao redor da Base.BaseA Explorao no pode ser interrompida sem que todas as direes tenham sido testadas.Do resultado, depreender a direo provvel do timo

ExploraoBaseFunes unimodais: o sucesso num sentido dispensa o teste no outro.S: Sucesso I: Insucessobuscando mximoSucessodesnecessrio

ExploraoBaseO Sucesso numa tentativa justifica a mudana da Base para a nova posio. A Explorao continua a partir desta melhor posio.

Mtodo de Hooke & Jeeves : Fase de Progresso2522Resultado da ExploraoProgredir com duplo incremento at ocorrer um InsucessoSucesso! Mover a Base. Continuar a ProgressoInsucesso! Permanecer na Base (25)Explorao a partir da Base (25) com 1 e 2 .

A Base estar suficientemente prxima para ser declarada como o timo?Se todos os incrementos estiverem menores do que as tolerncias, SIM!: FinalizarSe algum deles estiver maior, ento este deve ser reduzido metade.Inicia-se uma nova Explorao volta da Base com os novos incrementos

1 > 1 e 2 > 2 : ainda no chegou ao timo : 1 = 1 /2 , 2 = 2 /2

1 < 1 e 2 < 2 : a Base pode ser considerada o Ponto timo

Modelo Matemtico1. Q(xo - x1) - W1 y1 = 02. y1 - k x1 = 03. Q(x1 -x2) - W2 y2 = 04. y2 - k x2 = 0 Avaliao EconmicaL = R - CR = pAB (W1 y1 + W2 y2 )C = pB (W1 + W2)pAB = 0,4 $/kgAB : pB = 0,01 $/kgBBalano de Informao: V = 8; N = 4; C = 2; G = 2 (otimizao)Exemplo: dimensionamento de 2 extratores em srie

Modelo Matemtico1. Q (xo - x1) - W1 y1 = 02. y1 - k x1 = 03. Q(x1 -x2) - W2 y2 = 04. y2 - k x2 = 0 Modelo Matemtico2. y1 = k x14. y2 = k x23. W2 = Q (x1 x2)/ y21. W1 = Q (xo - x1)/ y1Exemplo: dimensionamento de 2 extratores em srie

Incorporando as Restries de Igualdade Funo Objetivo LBuscando o ponto estacionrio:Soluo completa:y1o = 0,05428 kgAB/kgB; W1o = 1.184 kgB/hy2o = 0,03684 kgAB/kgB; W2o = 1.184 kgB/hCo = 23,68 $/h; Ro = 43,15 $/h; Lo = 19,47 $/hL = a b/x1 cx2 d x1/x2L/x1 = b/x12 d/x2 = 0L/x2 = - c + dx1/x22 = 0L = R C R = pAB (W1 y1 + W2 y2 ) C = pB (W1 + W2)2. y1 = k x14. y2 = k x23. W2 = Q (x1 x2)/ y21. W1 = Q (xo - x1)/ y1a = pAB Q xo + 2 pB Q / k = 130;b = pB Q xo/ k = 0,5;c = pAB Q = 4000;d = pB Q / k = 25

Analisando o ponto estacionrio:L/x1 = b/x12 d/x2 = 0L/x2 = - c + dx1/x22 = 0Mximo!det(H - I) = 0 1 = -0,258106 e 2 = -1,011106

Estgio 1 2 Total Soluto Recup. kg/h 64,28 43,62 107,90 Solv. Consum. kg/h 1.184 1.184 2.368 Lucro $/a 13,87 5,61 19,48

02,04,06,08,010121416180,0050,0100,0150,0200,0250,0300,0350,0020,0040,0060,0080,0100,0120,0140,0160,0180,020X2X119,50,013570,00921

Seguem-se todos os resultados possveis da Explorao em 2 dimenses

1815Sucesso: deslocar a BaseSucesso: deslocar a BaseDireo provvel do timoUnimodalidade: dispensa + 1 Direo x1Direo x2Unimodalidade: dispensa + 2

151218Sucesso: deslocar a BaseInsucesso: permanece na BaseSucesso: deslocar a BaseDireo provvel do timoDireo x1Direo x2Unimodalidade: dispensa + 1

15Sucesso: deslocar a Base12Insucesso: permanecer na BaseDireo provvel do timoDireo x1Direo x2Unimodalidade: dispensa + 113Insucesso: permanecer na Base

718Sucesso: deslocar a BaseInsucesso: permanecer na BaseSucesso: deslocar a BaseDireo provvel do timo15Direo x1Direo x2Unimodalidade: dispensa + 2

7Sucesso: deslocar a BaseInsucesso: permanecer na BaseDireo provvel do timo151218Sucesso: deslocar a BaseInsucesso: permanecer na BaseDireo x1Direo x2

7Sucesso: deslocar a BaseInsucesso: permanecer na BaseDireo provvel do timo15Insucesso: permanecer na BaseDireo x1Direo x21211Insucesso: permanecer na Base

7Sucesso: deslocar a BaseInsucesso: permanecer na BaseDireo provvel do timoDireo x1Direo x2Insucesso: permanecer na Base815Unimodalidade: dispensa + 2

7Insucesso: permanecer na BaseDireo provvel do timo10BaseDireo x1Direo x2Insucesso: permanecer na Base8Sucesso: deslocar a Base15Insucesso: permanecer na Base9

7Insucesso: permanecer na Base10BaseDireo x1Direo x2Insucesso: permanecer na Base8Insucesso: permanecer na Base9Insucesso: permanecer na Base5A Base deve estar prxima do timo !

Mtodo de Hooke & JeevesALGORITMOSeno: reduzir os incrementos Estabelecer um incremento e uma tolerncia para cada varivelEscolher uma BaseRepetirExplorar a vizinhana da Base (em busca da direo provvel do timo)Seno: (proximidade do timo)Se Chegou ao timoEnto: Finalizar

Funes UnimodaisO mtodo converge sempre para o nico extremo independentemente da base inicial.Os incrementos iniciais afetam apenas o nmero de tentativas.

O mtodo pode convergir para extremos locais diferentes dependendo da base inicial e dos incrementos iniciais selecionados.Funes Multimodais(a) partindo de bases iniciais diferentes pode-se alcanar extremos locais diferentes com os mesmos incrementos iniciais.(b) partindo de uma mesma base inicial pode-se alcanar extremos locais diferentes com incrementos iniciais diferentesf (x) = (x12 + x2 11)2 + (x22 + x1 7)2

Mtodo dos poliedros flexveis

um mtodo de busca multivarivel (J.A. Nelder e R. Mead, 1964, tambm chamado de Simplex), onde o pior vrtice de um poliedro com n + 1 vrtices substitudo por um novo vrtice colinear com o vrtice antigo e o centride.Centride:onde xh,j o pior vrtice.

Mtodo dos poliedros flexveis

O algoritmo envolve quatro operaes de busca, que para o caso da minimizao da funo objetivo tm as seguintes formas:

Mtodo dos poliedros flexveis

O critrio usado por Nelder e Mead para terminar a busca o seguinte:

DIMENSIONAMENTO POR SIMULAES SUCESSIVASEMPREGADO POR SOFTWARES COMERCIAISEmpregam, para dimensionamento, os mdulos ordenados para simulao.Mas exige um procedimento de otimizao: funo objetivo (a ser minimizada): diferena, em valor absoluto, entre os valores obtidos para as variveis de sada e os valores estipulados como metas variveis de projeto: as dimenses dos equipamentos

Exemplo: ExtratorFO = |x 0,008|NormalSimulaes Sucessivas

Exemplo: Extrator1. Q(xo x) W y = 0 2. y k x = 0x = Q xo / (Q + k W )Por Seo urea, 0 < W < 1.000 W = 3.750

Exemplo: Trocador de CalorT2 = T1 Q/W1Cp1 T4 = T3 + Q/W3Cp3NormalSimulaes SucessivasPor Hooke&Jeeves ...0 < A < 1.000 0 < W3 < 100.000FO = (T2 25)2 + (T4 30)2