Problemas com múltiplos objetivos são muito frequentes nas áreas de Otimização, Economia, Finanças, Transportes, Engenharia e várias outras. Como os objetivos são, geralmente, conflitantes, faz-se necessário o uso de técnicas apropriadas para obter boas soluções. A área que trata de problemas deste tipo é chamada de Otimização Multiobjetivo. Neste trabalho, estudamos os problemas dessa área e alguns dos métodos existentes para resolvê-los. Primeiramente, alguns conceitos relacionados ao conjunto de soluções são definidos, como o de eficiência, no intuito de entender o que seria a melhor solução para este tipo de problema. Em seguida, apresentamos algumas condições de otimalidade de primeira ordem, incluindo as do tipo Fritz John para problemas de Otimização Multiobjetivo. Discutimos ainda sobre algumas condições de regularidade e total regularidade, as quais desempenham o mesmo papel das condições de qualificação em Programação Não-Linear, propiciando a estrita positividade dos multiplicadores de Lagrange associados às funções objetivo. Posteriormente, alguns dos métodos existentes para resolver problemas de Otimização Multiobjetivo são descritos e comparados entre si. Ao final, aplicamos a teoria e métodos de Otimização Multiobjetivo nas áreas de Compressed Sensing e Otimização de Portfolio. Exibimos então testes computacionais realizados com alguns dos métodos discutidos envolvendo problemas de Otimização de Portfolio e fazemos uma análise dos resultados. / Problems with multiple objectives are very frequent in areas such as Optimization, Economy, Finance, Transportation, Engineering and many others. Since the objectives are usually conflicting, there is a need for appropriate techniques to obtain good solutions. The area that deals with problems of this type is called Multiobjective Optimization. The aim of this work is to study the problems of such area and some of the methods available to solve them. Firstly, some basic concepts related to the feasible set are defined, for instance, efficiency, in order to comprehend which solution could be the best for this kind of problem. Secondly, we present some first-order optimality conditions, including the Fritz John ones for Multiobjective Optimization. We also discuss about regularity and total regularity conditions, which play the same role in Nonlinear Multiobjective Optimization as the constraint qualifications in Nonlinear Programming, providing the strict positivity of the Lagrange multipliers associated to the objective functions. Afterwards, some of the existing methods to solve Multiobjective Optimization problems are described and compared with each other. At last, the theory and methods of Multiobjective Optimization are applied into the fields of Compressed Sensing and Portfolio Optimization. We, then, show computational tests performed with some of the methods discussed involving Portfolio Optimization problems and we present an analysis of the results.

O dimensionamento otimizado de sistemas de distribuição de águas tem originado centenas de trabalhos científicos nas últimas quatro décadas. Vários pesquisadores têm buscado encontrar uma metodologia capaz de dimensionar essas redes considerando diversos aspectos e incertezas características desse tipo de projeto. No entanto, os resultados da maioria das metodologias desenvolvidas não podem ser aplicados na prática. O objetivo deste trabalho é elaborar uma metodologia de dimensionamento de redes de distribuição de água considerando um enfoque multiobjetivo. A metodologia desenvolvida considera três aspectos referentes ao projeto desses sistemas: custo; confiabilidade e perdas por vazamentos. Para tanto, empregou-se um método de otimização multiobjetivo baseado em algoritmos genéticos para a geração do conjunto de soluções não-dominadas e um método multicriterial para escolha da alternativa final. Para representar os objetivos do problema, foram testadas nove funções: custo, vazamentos, entropia, resiliência, tolerância à falha, expansibilidade, efeito do envelhecimento e resilientropia, sendo que sete destas são específicas para a representação da confiabilidade. Para se avaliar as alternativas geradas foi desenvolvido um modelo de análise hidráulica que fosse capaz de trabalhar com vazamentos e com demandas dependente da pressão. Os métodos escolhidos foram o Híbrido de Nielsen e o Gradiente. Das funções testadas, a resilientropia, proposta originalmente neste trabalho, foi a que melhor se ajustou ao conceito formal de confiabilidade, representado pela função tolerância. Os resultados encontrados pela metodologia mostraram-se promissores, uma vez esta foi capaz de encontrar redes eficientes ao final das simulações. / The topic \"Optimized design of water distribution systems\" has generated hundreds of scientific publications in the last four decades. Several researchers have searched for a technology which would take into account a variety of aspects and uncertainties innate to the design of such networks. However, the results of most methodologies developed are not practical. The objective of this work is to develop a methodology for water distribution systems design that has a multi-objective focus. The methodology developed focuses in three aspects of the design of such systems: cost, reliability and losses by leaking. A multiobjective optimization method based on generic algorithms, generating a set of non-defined solutions, and a multi-criteria method for choosing the final alternative, was employed. Nine functions representing the objectives of the problem (method) were tested: cost, leakages, entropy, resilience, failure tolerance, expansibility, aging effect and resilienthropy, seven of which are specific to representing reliability. In order to evaluate the generated alternatives, a hydraulic analysis model, that could handle leakages and pressure dependent demands, was developed. The chosen methods were Nielsen\'s Hybrid, and the Gradient. Of all tested functions, resilientropy, originally proposed in this work, proved to be the one best adjusted to the formal concept of reliability, represented by the tolerance function. The results obtained by this methodology are promising, as they produced efficient distribution networks at the end of the simulations performed.

Reconhecendo-se a importância da água como recurso natural limitado e considerando-se a perspectiva de crescimento do contingente populacional urbano, faz-se necessária uma investigação dos sistemas de distribuição de água para abastecimento, por tratarem-se de infra-estruturas básicas comuns aos núcleos populacionais do mundo todo. O planejamento da reabilitação das redes de distribuição de água torna-se de fundamental importância considerando os recursos financeiros limitados e o comportamento operacional desses sistemas que são alterados ao longo do tempo devido ao processo de deterioração de seus componentes. O presente trabalho representa um esforço no sentido de considerar objetivos mais promissores na análise de reabilitação de redes. Dessa maneira, foram considerados: custo, benefício, vazamentos e confiabilidade. Este trabalho apresenta contribuições às análises multiobjetivo via algoritmos genéticos, propriciando um aprimoramento do algoritmo Multiobjective Genetic Algorithm (MOGA) e realizando investigação dos operadores (recombinação e mutação) e dos métodos Non-dominated Sorting Genetic Algorithm (NSGA), Strength Pareto Evolutionary Algorithm (SPEA) e Elitist Non-Dominated Sorting Genetic Algorithm (NSGA II). Do ponto de vista hidráulico, este trabalho introduz tanto perdas por vazamentos como demanda variável com a pressão, proporcionando uma análise mais realística do problema. Os estudos desenvolvidos para redes hipotéticas e para um sistema real, possibilitaram que soluções satisfatórias fossem obtidas, chegando-se inclusive a uma proposição do conceito de programação dinâmica para o caso multiobjetivo. / Recognizing the importance of water as a limited natural resource and considering the prospect of continued population growth, it is important to investigate water distribution systems which are common to all urban infrastructures. Planning of the water distribution network rehabilitation becomes additionally important given economic constraints and operational behavior these systems which modifies in time due to deterioration of water networks. The present work is an effort to consider the multiple objectives in the water network rehabilitation analyses. Four objectives were considered: cost minimization, benefit maximization, leakage minimization and reliability maximization. In addition, it presents some contributions to multiobjective optimization methodology by genetic algorithms, offering an improvement of Multiobjective Genetic Algorithm (MOGA). A detailed investigation is conducted on genetic operators (recombination and mutation) comparing some existing multiobjective optimization methods (Multiobjective Genetic Algorithm - MOGA, Non-dominated Sorting Genetic Algorithm - NSGA, Strength Pareto Evolutionary Algorithm - SPEA and Elitist Non-Dominated Sorting Genetic Algorithm - NSGA II). As regards the hydraulic analysis, this work introduces both leakages and pressure dependent demands in the simulations, providing a more realistic representation of actual field situations. The present study employs hypothetical networks and a real network obtaining satisfactory solutions. Further, dynamic programming concept is also incorporated into the multiobjective optimization framework.

Os problemas de gerenciamento da qualidade da água envolvem diversas aspirações dos usuários envolvidos, quer sejam eles os que usam o recurso hídrico para diluição de seus efluentes ou para seu consumo. Portanto, é raro que os modelos matemáticos usados para auxílio nas tomadas de decisões sejam expressos em termos de um único objetivo, como a maximização da eficiência econômica. Para o aproveitamento de um determinado sistema hídrico, deve ser considerada a distribuição eqüitativa, o uso racional, a maximização da eficiência econômica, a minimização dos impactos ambientais, entre outros. Neste contexto, três modelos de otimização multiobjetivo foram propostos e foram considerados a maximização da carga lançada pelas fontes poluidoras, a melhora qualitativa da água, e a minimização da magnitude das violações dos padrões de qualidade da água. A principal contribuição deste trabalho está na incorporação de uma restrição ao modelo de otimização multiobjetivo. A restrição proposta representa um índice que tem o intuito de distribuir eqüitativamente a eficiência do tratamento necessária entre as fontes de poluição. Sem a consideração de uma medida de eqüidade, a tentativa de maximizar a quantidade de efluentes lançados resultaria numa alocação de grandes quantidades de efluentes passíveis de serem lançados pelos usuários localizados mais a montante do rio, enquanto que os usuários à jusante deveriam tratar seus efluentes com um nível máximo de eficiência. O método utilizado para solucionar o problema foi o non-dominated sorting genetic algorithm e este estudo teve sua aplicação na bacia do rio Atibaia, SP. As soluções apresentadas pela otimização demonstram e comprovam os conflitos existentes e a competição entre os critérios considerados. O algoritmo genético demonstrou ser uma técnica efetiva para solucionar problemas de otimização multiobjetivo em aplicações de gerenciamento da qualidade da água, identificando as variáveis de decisão e a frente Pareto. / Problems of water quality management involve many aspirations of the users engaged, those that use water for wastewater dilution or for their consumption. Therefore, it is uncommon that decision-making mathematical models used are expressed in terms of a single objective, like the maximization of economic efficiency. Using a particular water system, one should consider the equitable distribution, the rational use, the maximization of economic efficiency, the minimization of environmental impacts, among others parameters. In this context, three models of multiobjective optimization were proposed and considered to maximize the wastewater discharge by point sources, the qualitative improvement of the water, minimizing the magnitude of the violations of water quality standards. The main contribution of this work was the incorporation of a restriction on the multiobjective optimization model. The proposed restriction is an index that intends to distribute equitably the efficiency of treatment needed between pollution sources. Without considering equity measure, the attempt to maximize waste discharge would result in an allocation of large quantities of waste to the upstream users, while the downstream dischargers would be required to treat their effluents at levels of maximum possible efficiency. The method used to solve the problem was the non-dominated sorting genetic algorithm (NSGA) and the case study was implemented in the Atibaia river basin, SP. The solutions presented by the optimization show and prove the existing conflicts and competition among the criteria considered. The genetic algorithm has been shown to be an effective technique for solving problems of multiobjective optimization in applications of water quality management, identifying the decision variables in Pareto front.

O objetivo deste trabalho é propor um procedimento híbrido para a solução do problema de formação de células de manufatura com réplicas de máquinas. Constrói-se um modelo matemático de otimização multiobjetivo cujos valores das funções-objetivo são obtidos por meio da execução de um modelo de simulação de eventos discretos, o qual representa um sistema de manufatura celular. Em seguida, geram-se soluções eficientes segundo o conceito de otimalidade de Pareto através de um processo de busca por valores ótimos executado por um algoritmo genético. Três funções-objetivo conflitantes são consideradas: inventário em processo, movimentação intercelular e investimento total em máquinas. Um algoritmo de análise de agrupamento é utilizado para a redução do conjunto final de soluções. A eficácia do procedimento é avaliada mediante a aplicação a dois casos da literatura. Os resultados obtidos são analisados e comentados. Conclui-se, por fim, que o procedimento é capaz de gerar um conjunto de configurações sub-ótimas equivalentes para as células de manufatura, representando aproximadamente os trade-offs entre as três funções-objetivo. / The purpose of this work is to propose a hybrid procedure for solving the manufacturing cell formation problem. A multiobjective optimization model is built whose objective function values are realized by running a discrete-event simulation model, which represents a cellular manufacturing system. Thereafter, efficient solutions are generated following the Pareto optimality concept through a search for optimum values carried out by a genetic algorithm. Three conflicting objective functions are considered, namely, work-in-process, intercell moves and total machine investment. A clustering algorithm is applied to the final solution set so as to reduce it. The procedure efficacy is evaluated via its application to two cases from the literature. The obtained results are analyzed and commented. Finally, it is concluded that the procedure is capable of generating a set of equivalent sub-optimal manufacturing cell configurations, representing approximately the trade-offs betvveen the objective functions adopted.

Made available in DSpace on 2016-08-10T10:40:24Z (GMT). No. of bitstreams: 1 Roberto Capparelli Marcal.pdf: 1385634 bytes, checksum: 037e447d80e3c2c33c23560ac2c75dca (MD5) Previous issue date: 2015-03-05 / This study aimed to construct a model for the simultaneous optimization of the topology and design of compressed air pipeline networks. The proposed model consists of two parts; the objective functions and a set of constraints. This model is a nonlinear mixed multiobjective programming. The function of this model is to optimize the diameters of the tubes and the topology of an air system under study, presenting a set of effective solutions while minimizing costs and pressure drop, given the constraints that enable each point of air consumption is treated in their minimum requirements of flow and pressure. For the verification of the proposed model behavior, data from a small network and obtained were applied efficient solutions for decision making. / Este trabalho teve como objetivo a construção de um modelo para a otimização simultânea da topologia e do dimensionamento de redes de ar comprimido. O modelo proposto é composto de duas partes: as funções objetivos e um conjunto de restrições. Este modelo é um modelo de programação não linear misto multiobjetivo. A função deste modelo é otimizar os diâmetros e a topologia dos tubos de uma rede de ar em estudo, apresentando um conjunto de soluções eficientes minimizando os custos e a perda de carga e atendendo as restrições que possibilitem que cada ponto de consumo de ar comprimido seja atendido em seus requerimentos mínimos de vazão e pressão. Para a verificação do comportamento do modelo proposto, foram aplicados dados de uma rede de pequeno porte e obtidos as soluções eficientes para a tomada de decisão.

O problema de Planejamento da Expansão de Sistemas de Distribuição (PESD) visa determinar diretrizes para a expansão da rede considerando a crescente demanda dos consumidores. Nesse contexto, as empresas distribuidoras de energia elétrica têm o papel de propor ações no sistema de distribuição com o intuito de adequar o fornecimento da energia aos padrões exigidos pelos órgãos reguladores. Tradicionalmente considera-se apenas a minimização do custo global de investimento de planos de expansão, negligenciando-se questões de confiabilidade e robustez do sistema. Como consequência, os planos de expansão obtidos levam o sistema de distribuição a configurações que são vulneráveis a elevados cortes de carga na ocorrência de contingências na rede. Este trabalho busca a elaboração de uma metodologia para inserir questões de confiabilidade e risco ao problema PESD tradicional, com o intuito de escolher planos de expansão que maximizem a robustez da rede e, consequentemente, atenuar os danos causados pelas contingências no sistema. Formulou-se um modelo multiobjetivo do problema PESD em que se minimizam dois objetivos: o custo global (que incorpora custo de investimento, custo de manutenção, custo de operação e custo de produção de energia) e o risco de implantação de planos de expansão. Para ambos os objetivos, são formulados modelos lineares inteiros mistos que são resolvidos utilizando o solver CPLEX através do software GAMS. Para administrar a busca por soluções ótimas, optou-se por programar em linguagem C++ dois Algoritmos Evolutivos: Non-dominated Sorting Genetic Algorithm-2 (NSGA2) e Strength Pareto Evolutionary Algorithm-2 (SPEA2). Esses algoritmos mostraram-se eficazes nessa busca, o que foi constatado através de simulações do planejamento da expansão de dois sistemas testes adaptados da literatura. O conjunto de soluções encontradas nas simulações contém planos de expansão com diferentes níveis de custo global e de risco de implantação, destacando a diversidade das soluções propostas. Algumas dessas topologias são ilustradas para se evidenciar suas diferenças. / The Distribution System Expansion Planning (DSEP) problem aims to determine guidelines to expand the network considering the growing demand of customers. In this context, the distribution companies have to propose actions for improvements in the distribution system in order to adjust the supply of energy to the standards required by regulators. Traditionally minimizing the global cost of expansion plans is the only goal that is considered, thus reliability and robustness issues are neglected. As a result, the optimal expansion plans lead the distribution system to configurations that are vulnerable to high load shedding under the occurrence of contingencies in the network. This work aims to develop a methodology to insert reliability and risk issues to the traditional DSEP problem in order to maximize the robustness of the network and hence mitigate the system damages caused by contingencies. We formulated a multi-objective model of the problem that compromises two objectives: minimization of the global cost (that comprises investment cost, maintenance cost, operational cost, and production cost) and minimization of the deployment risk of expansion plans. For both objectives, we formulated mixed integer linear models which are solved using CPLEX accessed through GAMS. To manage the search for optimal solutions, we chose to implement in C++ language two Evolutionary Algorithms (EAs): Non-dominated Sorting Genetic Algorithm-2 (NSGA2) and Strength Pareto Evolutionary Algorithm-2 (SPEA2). The effectiveness of both algorithms was verified through simulations of the expansion planning of two test systems, adapted from the literature. The set of solutions that has been found contains expansion plans with different levels of global cost and deployment risk. Some of these topologies are depicted to show this diversity of the proposed solutions.

Orientadora: Ana Carolina Lorena. / Dissertação (mestrado) - Universidade Federal do ABC. Programa de Pós-Graduação em Engenharia da Informação.

O objetivo deste trabalho é propor um procedimento híbrido para a solução do problema de formação de células de manufatura com réplicas de máquinas. Constrói-se um modelo matemático de otimização multiobjetivo cujos valores das funções-objetivo são obtidos por meio da execução de um modelo de simulação de eventos discretos, o qual representa um sistema de manufatura celular. Em seguida, geram-se soluções eficientes segundo o conceito de otimalidade de Pareto através de um processo de busca por valores ótimos executado por um algoritmo genético. Três funções-objetivo conflitantes são consideradas: inventário em processo, movimentação intercelular e investimento total em máquinas. Um algoritmo de análise de agrupamento é utilizado para a redução do conjunto final de soluções. A eficácia do procedimento é avaliada mediante a aplicação a dois casos da literatura. Os resultados obtidos são analisados e comentados. Conclui-se, por fim, que o procedimento é capaz de gerar um conjunto de configurações sub-ótimas equivalentes para as células de manufatura, representando aproximadamente os trade-offs entre as três funções-objetivo. / The purpose of this work is to propose a hybrid procedure for solving the manufacturing cell formation problem. A multiobjective optimization model is built whose objective function values are realized by running a discrete-event simulation model, which represents a cellular manufacturing system. Thereafter, efficient solutions are generated following the Pareto optimality concept through a search for optimum values carried out by a genetic algorithm. Three conflicting objective functions are considered, namely, work-in-process, intercell moves and total machine investment. A clustering algorithm is applied to the final solution set so as to reduce it. The procedure efficacy is evaluated via its application to two cases from the literature. The obtained results are analyzed and commented. Finally, it is concluded that the procedure is capable of generating a set of equivalent sub-optimal manufacturing cell configurations, representing approximately the trade-offs betvveen the objective functions adopted.

O problema de Planejamento da Expansão de Sistemas de Distribuição (PESD) visa determinar diretrizes para a expansão da rede considerando a crescente demanda dos consumidores. Nesse contexto, as empresas distribuidoras de energia elétrica têm o papel de propor ações no sistema de distribuição com o intuito de adequar o fornecimento da energia aos padrões exigidos pelos órgãos reguladores. Tradicionalmente considera-se apenas a minimização do custo global de investimento de planos de expansão, negligenciando-se questões de confiabilidade e robustez do sistema. Como consequência, os planos de expansão obtidos levam o sistema de distribuição a configurações que são vulneráveis a elevados cortes de carga na ocorrência de contingências na rede. Este trabalho busca a elaboração de uma metodologia para inserir questões de confiabilidade e risco ao problema PESD tradicional, com o intuito de escolher planos de expansão que maximizem a robustez da rede e, consequentemente, atenuar os danos causados pelas contingências no sistema. Formulou-se um modelo multiobjetivo do problema PESD em que se minimizam dois objetivos: o custo global (que incorpora custo de investimento, custo de manutenção, custo de operação e custo de produção de energia) e o risco de implantação de planos de expansão. Para ambos os objetivos, são formulados modelos lineares inteiros mistos que são resolvidos utilizando o solver CPLEX através do software GAMS. Para administrar a busca por soluções ótimas, optou-se por programar em linguagem C++ dois Algoritmos Evolutivos: Non-dominated Sorting Genetic Algorithm-2 (NSGA2) e Strength Pareto Evolutionary Algorithm-2 (SPEA2). Esses algoritmos mostraram-se eficazes nessa busca, o que foi constatado através de simulações do planejamento da expansão de dois sistemas testes adaptados da literatura. O conjunto de soluções encontradas nas simulações contém planos de expansão com diferentes níveis de custo global e de risco de implantação, destacando a diversidade das soluções propostas. Algumas dessas topologias são ilustradas para se evidenciar suas diferenças. / The Distribution System Expansion Planning (DSEP) problem aims to determine guidelines to expand the network considering the growing demand of customers. In this context, the distribution companies have to propose actions for improvements in the distribution system in order to adjust the supply of energy to the standards required by regulators. Traditionally minimizing the global cost of expansion plans is the only goal that is considered, thus reliability and robustness issues are neglected. As a result, the optimal expansion plans lead the distribution system to configurations that are vulnerable to high load shedding under the occurrence of contingencies in the network. This work aims to develop a methodology to insert reliability and risk issues to the traditional DSEP problem in order to maximize the robustness of the network and hence mitigate the system damages caused by contingencies. We formulated a multi-objective model of the problem that compromises two objectives: minimization of the global cost (that comprises investment cost, maintenance cost, operational cost, and production cost) and minimization of the deployment risk of expansion plans. For both objectives, we formulated mixed integer linear models which are solved using CPLEX accessed through GAMS. To manage the search for optimal solutions, we chose to implement in C++ language two Evolutionary Algorithms (EAs): Non-dominated Sorting Genetic Algorithm-2 (NSGA2) and Strength Pareto Evolutionary Algorithm-2 (SPEA2). The effectiveness of both algorithms was verified through simulations of the expansion planning of two test systems, adapted from the literature. The set of solutions that has been found contains expansion plans with different levels of global cost and deployment risk. Some of these topologies are depicted to show this diversity of the proposed solutions.