Baixe o app para aproveitar ainda mais
Prévia do material em texto
OTIMIZAÇÃO Modelagem de Sistemas Ambientais Prof. Ariel O. Gomes Otimização Desejo de maximizar ou minimizar alguma função a qual denomina-se função objetivo Encontrar o projeto que melhor represente a melhor solução para ao problema Simulação e Otimização Simulação é o processo de representar matematicamente um sistema, e realizar experimentações para prever seu comportamento quando sujeito a determinadas condições. Ex: Modelos chuva-vazão, modelo de reservatórios, modelos de redes hidráulicas, modelos de redes de fluxo... Otimização é a determinação das condições que resultam no melhor desempenho do sistema. Normalmente envolve a execução de diversas simulações. Exemplos de algoritmos: programação linear, não-linear, dinâmica, técnicas de inteligência artificial... CONSTRUÇÃO DE MODELOS MATEMÁTICOS 4 Sistema Real Definição e Descrição do Problema Modelo Matemático Solução do Modelo Implementação da Solução Simplificação Decisão Teórica x Política Revisão ELEMENTOS DE UM MODELO MATEMÁTICO DE OTIMIZAÇÃO DECISÕES Identificar quais decisões efetivamente resolvem o problema. O que não conhecemos no problema? RESTRIÇÕES Identificar quais as restrições que limitam as decisões a tomar OBJETIVOS Definir objetivos capazes de indicar que uma decisão é preferível a outras 5 Encontrar o valor dos parâmetros de um modelo matemático que resultem em uma boa concordância entre dados observados e calculados. Gupta et al. ELEMENTOS DE UM MODELO MATEMÁTICO DE OTIMIZAÇÃO ▪ Função Objetivo: Constitui-se da função a ser maximizada ou minimizada . Pode ser chamada de função multiobjetivo quando leva em consideração vários critérios a serem otimizados ▪ Restrições: representam as condições que devem ser satisfeitas, podendo ser de igualdade ou desigualdade. ▪ Problema irrestrito: não tem restrições Ponto ótimo: caracterizado pelo valar da variáveis de projeto que otimizam a função objetivo e satisfazem as restrições; Determine as dimensões de um canal retangular para transportar um vazão Q, com declividade I e comprimento L conhecidos. Deseja-se determinar a altura H e a largura B conforme ilustra a figura, tal que o custo total da obra seja mínimo. Admite-se que o custo total do canal seja composto de : custo de instalação ( R$/m3 escavado) e custo de revestimento ( R$/m2 de superfície) H B Dados: Q L I C1: custo de escavação ( R$/m3) C2: custo de revestimento (R$/m2) T1: volume de escavação T2: área de revestimento H B Dados: Q L I B e H: variáveis de decisão Custo Total da Obra: função objetivo a minimizar! Minimizar: C1.T1 + C2.T2 Sujeito a: B>0 H>0 Q: equação de Maning C1: custo de escavação ( R$/m3) C2: custo de revestimento (R$/m2) T1: volume de escavação T2: área de revestimento Minimizar: C1.T1 + C2.T2 Sujeito a: B>0 H>0 Q: equação de Maning Se B e H são variáveis de decisão. Então Colocar a função objetivo em função de B e H T1= B.H.L T2=(B+2H).L Q = (1/n)(B.H). {[(B.H)/(B+2H)]^2/3}. I^(1/2) Então fica: Minimizar: C1.BHL+ C2.(B+2H).L Sujeito a: Q - (1/n)(B.H).{[(B.H)/(B+2H)]^2/3}. I^(1/2)=0 B>0 H>0 ▪ Maximizar benefícios líquidos ▪ Minimizar custos de projetos ▪ Minimizar tempo de atendimento de demanda ▪ Minimizar o consumo de água ▪ Maximizar a qualidade Ambiental ▪ Minimizar Perdas ▪ Minimizar Impactos Ambientais ▪ Encontrar o mínimo ou o máximo de uma função 0 20 40 60 80 100 120 140 160 0 10 20 30 ▪ Encontrar pontos da função em que a derivada é zero. ▪ Vantagens: pode ser rápido, é mais elegante) ▪ Desvantagens: problemas de recursos hídricos apresentam funções de picos múltiplos, funções descontínuas, ausência da forma analítica da função, por exemplo 0 20 40 60 80 100 120 140 160 0 10 20 30 2x.cx.ba)x(F ++= 0 dx dF = ▪ Superfícies de resposta complexas ▪ Pontos extremos mal definidos ▪ Regiões planas ▪ Muitos ótimos locais ▪ Ótimo global apenas pouco melhor do que os ótimos locais ▪ Cálculo analítico, ▪ Método de Lagrange ▪ Método Gráfico ▪ Técnicas numéricas ▪ Busca aleatória ▪ Busca direta ▪ Mistos ▪ Vantagens: funções descontínuas; picos múltiplos ▪ Desvantagens: demorado; não existe garantia de atingir o ponto ótimo global 0 20 40 60 80 100 120 140 160 0 10 20 30 “Ótimo” ▪ Estratégia de caminhar “morro acima” 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Máximo global Máximo local Função objetivo: F(x1,x2) x1 x2 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Início: ponto coordenadas (parâmetros) aleatórias X1=valor aleatório entre a e b X2=valor aleatório entre c e d 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Determina direção de busca: exemplo x2=x2+0,3; x1=x1 Função objetivo melhorou? Não, então tenta no outro sentido. 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 F.O melhorou? Sim, então continua no mesmo sentido 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 F.O melhorou? Sim, então continua no mesmo sentido 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 F.O melhorou? Sim, então continua no mesmo sentido 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 F.O melhorou? Não, então volta para o ponto anterior... F.O melhorou? Sim, então continua no mesmo sentido 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 ...e muda a direção de busca. 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 E assim segue até encontrar um ponto em que não existe direção de busca que melhore o valor da FO 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Rosenbrock: Método um pouco mais eficiente Direção de busca é a que potencialmente dará maior incremento da FO 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Limitação da busca direta: Ótimos locais Região que atrai solução para o ótimo local Tentativa de contornar problema: Busca direta com inicialização múltipla 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Várias tentativas; espera se que o ótimo global seja a melhor solução testada. Problema: Ineficiente e ineficaz quando a FO tem muitos ótimos locais ▪ Programação linear (Simplex) ▪ Programação não-linear ▪ Programação dinâmica ▪ Algoritmos genéticos ▪ Caminhos de formiga ▪ … ▪ Definição da faixa de validade dos parâmetros ▪ geração aleatória de pontos (conjuntos de parâmetros) ▪ avaliação das funções objetivo para cada ponto ▪ reprodução, evolução ▪ conjuntos com melhores F.O. têm maior chance de contribuir na reprodução Inspiração na natureza •Conceitos de população, reprodução e gerações •Filhos são semelhantes aos pais •Os pais mais “adaptados” tem maior probabilidade de gerar filhos •Os filhos não são completamente iguais aos pais Algumas regras gerais dos algoritmos genéticos ▪ Na natureza:indivíduos mais adaptados têm maior probabilidade de sobreviver até chegar à fase reprodutiva e de participar do processo de reprodução. ▪ No algoritmo: pontos com maior FO têm maior probabilidade de serem escolhidos para participar dos complexos. 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Passo 1 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Passo 2 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Passo 3 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Passo 4 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Passo 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Passo 6 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Passo 7 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Passo 8 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Passo 9 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Passo 10 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Passo 20 ▪ Considerar mais de uma FO. ▪ Calibração de modelos hidrológicos distribuídos ▪ Otimização de sistemas de reservatórios de usos múltiplos (controle de cheias x regularização de vazão) ▪ Vazão e evapotranspiração Problemas e formulação da função objetivo, declaração das variáveis e restrições. Um sistema biológico de tratamento de águas residuárias necessita de nutrientes para a fase de crescimento de bactérias. As necessidades nutricionais das bactérias estão na tabela ao lado: Component e quantidade (mg) N 80 P 70 K 100 glicose 60 Você deve pegar 4 soluções para compor a solução a ser injetada no reator, que contém as seguintes quantidades de cada componente por litro de solução (ver tabela ao lado). Ou seja, 1 litro de solução A contém 10 mg de N, 8 mg de P, 15 mg de K e 20 mg de glicose. Componen te Solução(mg) A B C D N 10 5 9 10 P 8 7 6 6 K 15 3 4 7 glicose 20 2 3 9 Solução Custo($/L) A 100 B 800 C 1200 D 3500 Os custos unitários das soluções são os seguintes: Deseja-se saber as quantidade de A, B, C e D na composição a ser injetada no reator, de maneira a atender as necessidades nutricionais das bactérias à custo mínimo O Governo Federal colocou 20 ha (hectare) de terras desmatadas à disposição de produtores locais. Estimula-se que tal área seja utilizada para o plantio de soja e algodão. Calcula-se que há 1200 homens-horas disponíveis durante o período de semeadura; e que são necessários 20 homens- horas por hectare de soja e 120 homens-horas por hectare de algodão. Oferece-se ainda uma linha máxima de crédito de $ 6.000 (seis mil dólares), dividida da seguinte forma: $ 600,00 (seiscentos dólares) por hectare de soja e $ 200,00 (duzentos dólares) por hectare de algodão. Como organizar essa área de plantio se é sabido que as margens de lucro esperadas são $ 50,00 (cinqüenta dólares) por hectare de soja e $ 25,00 (vinte e cinco dólares) por hectare de algodão? Objetivo: Maximização do lucro Alternativas: produção de soja (x1) produção de algodão (x2) Restrições: área; disponibilidade de mão-de-obra; crédito Estrutura matemática: sujeito a A solução ótima é : Exemplo 3: Produção de Aço vs. Ambiente Uma empresa de aço emite para a atmosfera três tipos de contaminantes: ◼partículas ◼óxido sulfúrico ◼hidrocarbonetos A produção de aço inclui duas fontes principais de contaminação: ◼ os altos- fornos para produzir o ferro-gusa (ferro de primeira fundição ainda não purificado) ◼os fornos abertos para converter o ferro em aço De acordo com decisões governamentais a fábrica tem de reduzir anualmente a emissão dos contaminantes como a seguir se indica: Exemplo 3: Produção de Aço vs. Ambiente(2) Contaminante Redução requerida no nível anual de emissão (em milhares de toneladas) A:Partículas 60 B: Óxido sulfúrico 150 C: Hidrocarbonetos 125 Exemplo 3: Produção de Aço vs. Ambiente(3) Para reduzir a emissão os engenheiros propõem as seguintes medidas: ◼ Aumentar a altura das chaminés ◼ A utilização de filtros nas chaminés ◼ Incluir certos aditivos nos combustíveis Cada medida tem associado os seguintes custos anuais na sua implementação em milhares de Euros: Método de redução Altos fornos Fornos abertos Chaminés mais altas 8 10 Filtros 7 6 Melhores combustíveis 11 9 Exemplo 3: Produção de Aço vs. Ambiente(4) Com as medidas propostas vai ser possível eliminar as quantidades anuais dos contaminantes A, B e C nas seguintes quantidades (em milhares de toneladas): Chaminés mais altas Filtros Melhores combustíveis Contaminante Altos fornos Fornos Abertos Altos fornos Fornos Abertos Altos fornos Fornos Abertos Partículas 12 9 25 20 17 13 Óxido sulfúrico 35 42 18 31 56 49 Hidrocarbonetos 37 53 28 34 29 20 Estas medidas podem ser implementadas na sua totalidade ou parcialmente.
Compartilhar