[pt] O Partial Digest Problem (problema de digestão parcial), também conhecido como o Turnpike Problem, consiste na construção de um conjunto de pontos na reta real dadas as distâncias não designadas entre todos os pares de pontos. Uma variante deste problema, chamada Min Distance Superset Problem (problema de superset de distância mínimo), lida com entradas incompletas em que algumas distâncias podem estar faltando. O objetivo deste problema é encontrar um conjunto mínimo de pontos na reta real, tal que as distâncias entre cada par de pontos contenham todas as distâncias de entrada. As principais contribuições deste trabalho são duas formulações de programação matemática diferentes para o Min Distance Superset Problem: uma formulação de programação quadrática e uma formulação de programação inteira. Mostramos como aplicar um método de cálculo direto de limites de valores de variáveis através de uma relaxação Lagrangeana da formulação quadrática. Também introduzimos duas abordagens diferentes para resolver a formulação inteira, ambas baseadas em buscas binárias na cardinalidade de uma solução ótima. A primeira baseia-se num subconjunto de variáveis de decisão, na tentativa de lidar com um problema de viabilidade mais simples, e o segundo é baseado na distribuição de distâncias entre possíveis pontos disponíveis. / [en] The Partial Digest Problem, also known as the Turnpike Problem, consists of building a set of points on the real line given their unlabeled pairwise distances. A variant of this problem, named Min Distance Superset Problem, deals with incomplete input in which distances may be missing. The goal is to find a minimal set of points on the real line such that the multiset of their pairwise distances is a superset of the input. The main contributions of this work are two different mathematical programming formulations for the Min Distance Superset Problem: a quadratic programming formulation and an integer programming formulation.We show how to apply direct computation methods for variable bounds on top of a Lagrangian relaxation of the quadratic formulation. We also introduce two approaches to solve the integer programming formulation, both based on binary searches on the cardinality of an optimal solution. One is based on a subset of decision variables, in an attempt to deal with a simpler feasibility problem, and the other is based on distributing available distances between possible points.

[pt] Com o novo modelo do setor elétrico implantado no início desta década, vários desafios foram impostos aos agentes dessa área. Para os agentes de distribuição, o modelo implica em procurar otimizar processos, sempre mantendo certo nível de qualidade dos serviços, monitorado pelo agente regulador. Uma das obrigações das distribuidoras é a contratação adequada de energia para fornecimento de seus clientes considerando períodos futuros. O presente trabalho tem por objetivo desenvolver uma estratégia de apoio às decisões de uma distribuidora de energia para a contratação em leilões de energia elétrica. O método contempla uma etapa de previsão de consumo de energia num horizonte de cinco anos, e a partir dos valores estimados e de outros componentes formadores dos custos de contratação, como o Valor de Referência Anual e o Preço de Liquidação de Diferenças, realiza simulações de cenários, que visam propiciar uma otimização na formação da carteira de contratos. Ao final são definidos os percentuais ótimos de contratação, que garantam o atendimento completo ao mercado cativo da distribuidora, e que minimizam os riscos de aplicações de penalidades por sub ou sobrecontratação. / [en] The implementation of the new model for the electrical sector in Brazil resulted in big challenges to the agents involves in this market. For the distributing utilities agents, in particular, the model somehow requires an optimization of all their processes but, at the same time, keeping the quality of the services supplied to their clients within the level stated by the regulator. Among these challenges, the distributing utilities, within the new model, have to perform the correct acquisition of energy from the supply utilities for future periods (up to 5 years ahead). This thesis aims to provide tools to help a distributing utility on the decision of energy acquisition on the electrical energy auctions. The approach includes a stage of energy consumption forecasts up to 5 - years - ahead and simulation stage where the demand forecasts and the energy prices series are the random variables implemented in a simulation scheme that generates possible energy acquisition scenarios. At the end, the optimal energy acquisition are obtained in such a way that the captive utility is fully contracted for the next five years where the utility penalties for under or over acquisition are minimized.

[pt] O objetivo desta dissertação é analisar a aplicação de metodologias de alocação de capacidade firme de usinas termelétricas através da teoria dos jogos cooperativos e suas conseqüências na cooperação entre os agentes. Mostra-se que não existe uma maneira ótima, única, de se fazer esta repartição, mas existem critérios para verificar se uma metodologia de repartição específica apresenta algum aspecto inadequado. Um desses critérios é a justiça. Mostra-se que este sentido de justiça equivale a pertencer ao chamado núcleo de um jogo cooperativo, onde não há subsídio de um subgrupo por outro. O cálculo da capacidade firme ou Capacidade de Suprimento de Carga será formulado como um problema de otimização linear e serão investigadas vantagens e desvantagens de distintos métodos de alocação (benefícios marginais, última adição, Nucleolus, Shapley). A aplicação desses métodos tem um crescimento exponencial de esforço computacional, o método de Aumann- Shapley abordado em seguida fornece para o problema de alocação de capacidade firme uma solução computacional mais eficiente, embora em sua descrição aparentemente o método aumente o esforço computacional. Em seguida foram realizados resultados numéricos com sistemas genéricos de pequeno porte. / [en] The objective of this work is to investigate the application of different methodologies of allocation of firm capacity rights among thermal plants using a game-theoretic framework and the consequences in the cooperation among the agents. It is shown that there is not an optimal and unique approach to make this allocation but there are criteria to verify if a given approach presents any inadequate aspect. One of these criteria is the justice, or fairness. It is shown that a one sense of justice is equivalent to the condition of the core of a cooperative game. The calculation of the firm capacity will be formulated as a linear program and advantages/disadvantages of different allocation methods (marginal allocation, incremental allocation, Nucleolus, Shapley) will be investigated. The complexities of these methods are exponential, so it will be shown that the Aumann-Shapley (AS) scheme to the problem of allocation of capacity rights will be more efficient. Numerical results about the difference allocations in these methods are presented in general smalls systems.

[pt] A indústria do petróleo é uma das mais importantes e dinâmicas do Brasil. Em uma indústria naturalmente integrada como a petrolífera, é necessário um adequado planejamento estratégico da cadeia integrada de petróleo que contemple todos os seus processos, como a produção de petróleo, refino, distribuição e comercialização de derivados. Além disso, a indústria de petróleo está suscetível a diversas incertezas relacionadas a preço de petróleo e derivados, oferta de óleo bruto e demanda de produtos. Em face destas oportunidades e desafios, foi desenvolvido no âmbito desta dissertação um modelo de programação estocástica para o planejamento estratégico da cadeia de petróleo brasileira. O modelo contempla as refinarias e suas unidades de processos, as propriedades dos petróleos e derivados, a logística nacional e decisões de comercialização de petróleo e derivados, incluindo incertezas associadas a preço de mercado, produção de petróleo nacional e demanda interna de derivados. A partir do modelo estocástico foram formulados um modelo robusto e um modelo MinMax no intuito de comparar o desempenho e a qualidade da solução estocástica. Os modelos propostos foram aplicados a um exemplo real, com 17 refinarias e 3 centrais petroquímicas que processam 50 produtos intermediários, destinados a produção de 10 derivados associados à demanda nacional, 8 campos de exploração de petróleo, 14 produtores gás natural, 1 produtor de óleo vegetal, 13 terminais, 4 bases de distribuição e 278 arcos de transporte. Na análise de resultados foram utilizadas medidas como Valor Esperado da Informação Perfeita (EVPI) e Valor da Solução Estocástica (VSS). / [en] The oil industry is one of the most important and dynamic in Brazil. As the oil industry naturally integrated, we need an appropriate strategic planning to the oil supply chain that consider all its processes, such as oil production, refining, distribution and refined products marketing. Moreover, the oil industry is susceptible to various uncertainties regarding the oil and products price, crude oil supply and products demand. In light of these opportunities and challenges, it was developed in this dissertation a stochastic programming model for the strategic planning of the Brazilian oil supply chain. The model includes refineries and process units, oils and their products properties, logistics and national marketing decisions of oil and products, including uncertainties associated with market price, oil domestic production and refined products domestic demand. Based on the stochastic model a robust model and a MinMax model were formulated in order to compare the performance and quality of the stochastic solution. The proposed models were applied to a real example, with 17 refineries and 3 petrochemical power plants that process 50 intermediate products, intended to production of 10 final products associated to national demand, 8 oil fields, 14 natural gas producers, 1 vegetal oil producer, 13 terminals, 4 delivery points and 278 arches of transport. In the results analysis was used as measures the Expected Value of Perfect Information (EVPI) and the Value of the Stochastic Solution (VSS).

[pt] A presente dissertação tem por objetivo desenvolver um modelo inteligente que permita, por uma análise quantitativa e probabilística, gerar uma carteira otimizada composta de um ativo financeiro e opções sobre este ativo. Procurou-se estudar inicialmente as características da distribuição de retornos e da volatilidade das ações mais líquidas da Bolsa de Valores de São Paulo, no período de Jan/2005 a Jul/2010, através de regressões polinomiais univariadas e bivariadas. Observouse características como a de reversão a média da volatilidade, correlação da volatilidade futura com um período histórico mais longo e outro mais curto e uma relação possivelmente quadrática entre a volatilidade histórica e a volatilidade futura. Desenvolveu-se então, satisfatoriamente, uma rede neural para prever a volatilidade futura das ações, por este ser o fator mais crítico para se determinar o preço de uma opção. Utilizando-se da precificação das opções, avaliou-se o desempenho de algoritmos genéticos na otimização de carteiras estruturadas com esses derivativos, com três funções de avaliação diferentes, a fim de aumentar o potencial retorno de um investimento, minimizando seus riscos. O sistema evolucionário implementado demonstrou ser satisfatório quando comparado a carteira otimizada com diversas outras estratégias comuns de mercado, demonstrando ser uma alternativa de apoio a decisão para investidores e gestores de carteiras. / [en] This dissertation develops an intelligent, quantitative and probabilistic model to determine an optimal composition of a portfolio consisting of a financial asset and options over this asset. Initially we studied the characteristics of the historical distribution of returns and volatility of the most liquid stocks from the BOVESPA Stock Exchange, from January 2005 to July 2010, through a univariate and a bivariate polynomial regression. Characteristics such as mean reversion of volatility, strong correlation of historical and future volatility and a quadratic polynomial relationship between them were observed. A neural network was then developed to predict the future volatility of these stocks, since that is the most critical variable in determining an option´s price. Using the option pricing, we evaluated the performance of genetic algorithms in optimizing portfolios, structured with these derivatives, with three different evaluation functions in order to increase the potential return of investments while minimizing downside risks. The developed evolutionary system showed satisfactory results when the optimal portfolio was compared with several other market option strategies, demonstrating to be a relevant decision support system for investors and portfolio managers.

[pt] A crescente demanda de óleo observada nas últimas décadas tem motivado as indústrias de petróleo a explorarem novas reservas em águas cada vez mais profundas, o que representa um maior desafio operacional, de segurança e econômico. Nesse novo cenário, as condições ambientais se tornam mais severas, conferindo às unidades flutuantes movimentos de amplitude cada vez maiores. Em consequência, os risers, que são os principais componentes responsáveis pelo transporte de óleo desde o reservatório até as unidades flutuantes, passam a ser solicitados de forma mais intensa. Um grande desafio tem sido colocado para as indústrias de petróleo no sentido de desenvolverem configurações para os risers capazes de reduzir os efeitos dinâmicos que lhes são impostos e, consequentemente, viabilizarem o seu uso em águas profundas e ultraprofundas. Configurações do tipo Lazy-S, Pliant-Wave, entre outras, têm sido propostas, porém, além de complexas, demandam muita logística e apresentam elevados custos para a sua implantação. Esta dissertação propõe uma solução alternativa que consiste no estudo de configurações ótimas de risers em catenária utilizando amortecedores hidrodinâmicos. As dimensões e o posicionamento desses amortecedores são obtidos por meio de técnicas de otimização multiobjetivo, buscando-se minimizar os efeitos provocados pelas ondas de compressão ao longo dos risers e os custos envolvidos na utilização desses amortecedores, respeitando-se algumas restrições geométricas. O processo de otimização é realizado por meio do algoritmo genético NSGA-II, disponível no programa modeFRONTIER. O equilíbrio dinâmico dos risers, verificado em cada passo da otimização, é obtido por meio do programa Anflex. Exemplos representativos são utilizados para demonstrar a eficiência e a viabilidade da utilização da metodologia proposta. / [en] The growing demand for oil, observed in recent decades has motivated the oil industry to exploit new oil reserves in ever-deeper waters, representing a greater operational challenge, security and economic. In this new scenario, the environmental conditions become more severe, causing the floating units movements with increasing amplitude. Consequently, the risers, which are the main components responsible for the transport of oil from the reservoir to the floating units, shall be requested more intensely. The oil industry confronts a major challenge in order to develop riser configurations that can reduce the dynamic effects that are imposed on it and hence to enable its use in deep and ultra-deep waters. Lazy-S, Pliant-Wave, among others riser configurations, have been proposed, however, besides complex, require a lot of logistics and have high costs for their deployment. This thesis proposes an alternative solution that consists of the study of optimum catenary risers configurations using hydrodynamic dampers. The dimensions and placement of these dampers are obtained by means of multi-objective optimization techniques seeking to minimize the effects caused by compression waves over the risers and the costs involved in using these dampers, fullfilling certain geometric constraints. The optimization process is performed by the genetic algorithm NSGA-II, available at modeFRONTIER program. The dynamic equilibrium of risers, evaluated at each step of the optimization is obtained through Anflex program. Representative examples are used to demonstrate the efficiency and feasibility of using the proposed methodology.

[pt] No projeto de estruturas de engenharia há, freqüentemente, incertezas associadas µas propriedades dos materiais, nas propriedades geométricas e aos carregamentos. A maneira mais comum e tradicional para se levar em conta estas incertezas é através da definição dos valores de projeto como o resultado do produto do valor característico das variáveis aleatórias por um fator parcial de segurança. Esta solução, no entanto, falha ao não permitir a quantificação da confiabilidade do projeto ótimo uma vez que um fator grande de segurança pode não significar uma confiabilidade mais alta. Para se considerar a natureza probabilística de quantidades como propriedades dos materiais, carregamentos, etc., tem-se que identificar e definir estas quantidades como variáveis aleatórias no modelo de análise. Desta maneira, a probabilidade de falha (ou a confiabilidade) de uma estrutura sujeita a uma restrição de desempenho na forma de uma função de estado limite pode, então, ser calculada e formulada como uma restrição num problema de otimização. Neste trabalho, restrição probabilísticas são incorporadas ao esquema tradicional de otimização estrutural. A formulação e os métodos numéricos para este processo, comumente chamado de otimização baseada em confiabilidade, são descritos. O objetivo principal é apresentar um sistema computacional capaz de resolver problemas de otimização de forma e de dimensões de treliças espaciais baseado em confiabilidade. Podem ser consideradas como variáveis, determinísticas ou aleatórias, as seções transversais, as coordenadas nodais, as propriedades dos materiais (módulo de elasticidade e tensão de escoamento) e os carregamentos. De maneira a tratar os problemas de instabilidade global são considerados os efeitos da não-linearidade geométrica no comportamento da estrutura e uma restrição formulada para uma função de estado limite associada na carga de colapso é incluída. Funções de estado limite referentes aos deslocamentos e nas tensões também são consideradas. A flambagem global das barras é considerada por meio da carga crítica de Euler / [en] Uncertainties associated with random variables, such as, the material proprieties and loads, are inherent to the design of structures. These uncertainties are traditionally taken into account in the project before the design by defining design values for the random variables. The design values of the random variables are obtained from statistical properties of the random variables and from partial safety factors. Once these values are defined the variables are treated as deterministic variables in the design process. This approach has been followed in the conventional design optimization and in many design codes such as the Brazilian code for the design of steel and concrete structures. This simple approach, however, does not allow an estimate of the structural reliability of the resulting project which may have a low (unsafe structure) or a very high (expensive structure) reliability. To overcome this problem a reliability analysis must be incorporated into the traditional design optimization. Design optimization, incorporating reliability analyses, has been denoted Reliability-Based Design Optimization (RBDO). In RBDO, the constraints are defined in terms of the probabilities of failure associated with some prescribed failure functions and therefore, it requires, as in the reliability analysis, the definition of the random variables and information about their statistical properties. In this work, RBDO is applied to the shape and sizing optimization of spatial trusses considering geometric nonlinearities. The constraints considered in the RBDO problem are related to the following failure mechanisms: to the global collapse (limit load), to local buckling and yield stress and to serviceability conditions (displacement bounds). The algorithms used for solving the optimization problem and for performing the reliability analysis are described.

[pt] A atividade de gerenciamento de reservatórios é uma tarefa essencial que visa o desafio da otimização da explotação de reservatórios de petróleo. Como resposta a tal desafio a indústria de óleo e gás vem desenvolvendo novas tecnologias, como a de poços inteligentes. Esses poços tem objetivo de baratear as operações de restaurações mais corriqueiras através do controle de sua tecnologia. Assim, este trabalho trata do desenvolvimento de campos inteligentes e apresenta um sistema de apoio à decisão capaz de otimizar, através de algoritmos evolucionários, o processo de controle da tecnologia de poços inteligentes considerando incertezas de falha e geológica. Além disso, o sistema se propõe a apoiar na tomada de decisão pelo uso ou não de poços inteligentes, dado um reservatório pronto para ser explorado ou para receber investimentos de expansão. O controle da tecnologia de poços inteligentes (IWT - Intelligent Wells Technology) empregado nesse estudo, refere-se à operação de abertura e fechamento dos dispositivos (válvulas) existentes nesses tipos de poços. Através da otimização com algoritmos genéticos se busca uma estratégia de controle pró-ativo, em outras palavras, agir antes do efeito, onde se busca nos tempos iniciais de produção uma configuração de válvulas que seja capaz de: atrasar a chegada da frente de água aos poços produtores, antecipar a produção de óleo ou melhorar a recuperação de óleo do campo; em conseqüência, uma operação que leve à maximização do valor presente líquido (VPL). O emprego de estratégias de controle que visam beneficiar a completação identifica o campo como inteligente. Outros trabalhos abordam o problema de otimização de controle de válvulas em poços inteligentes, porém eles utilizam métodos clássicos de otimização que limitam o número de válvulas ou ainda otimizam estratégias sem considerar os intervalos de tempo desejados para manutenção das válvulas. O modelo evolucionário empregado nesse estudo, baseado em algoritmos genéticos, consegue formular uma estratégia de controle para todas as válvulas presentes em uma determinada configuração de produção, em qualquer intervalo de tempo desejado, atendendo ao critério econômico de maximizar o VPL. Para apoiar a tomada de decisão, pelo uso ou não de poços inteligentes, consideram-se incertezas de falha e geológica. O modelo proposto foi avaliado em três reservatórios petrolíferos, sendo o primeiro um reservatório sintético, e os outros dois reservatórios mais complexos com características mais próximas das reais. Os resultados encontrados indicam que o modelo proposto permite alcançar boas estratégias de controle que levam a um aumento do VPL. A principal contribuição deste trabalho é a concepção e implementação de um sistema baseado em técnicas inteligentes capaz de apoiar no desenvolvimento e gerenciamento de reservatórios petrolíferos inteligentes considerando incertezas. / [en] The reservoir management is an important task that aims at the optimization of oil reservoir exploitation. To support this challenging mission, the oil and gas industry has been developing new technologies such as intelligent wells. The purpose of these wells is to reduce costs of the most common restoring operations by control of their actuators. Thus, this work deals with intelligent fields development and presents a decision support system able to optimize, by using evolutionary algorithms, the intelligent wells technology control process considering geological and technical uncertainties. In addition, the system gives support for the decision of rather to use or not intelligent wells, given a reservoir ready to be explored or to receive expansion investments. The control of Intelligent Wells Technology (IWT), as applied in this study, refers to the opening and closing operations of valves in these types of wells. An optimization based on genetic algorithms is used to produce a pro-active control strategy, that is, one that anticipates the actions to be taken in present time in order to achieve better results in the future. Such a strategy proposes a valve configuration that will be able to: delay the water cut on producer wells, advance the oil production or benefit the oil recuperation. As a result, the obtained configuration leads to a maximization of the NPV (Net Present Value). The usage of control strategies that aim to benefit completion identifies the oil field as intelligent. Other works also deal with valve control optimization problems in intelligent wells. However, they use classical optimization methods; these methods limit the number of valves or optimize strategies without considering time. The evolutionary model, based on genetic algorithm, applied in this study, can formulate a control strategy for all valves in a certain production configuration, for any desired time interval, according to the economical criteria of NPV maximization. In order to support the decision making for the use or not of intelligent wells, technical and geological uncertainties are considered. The proposed model was evaluated in three oil reservoirs. The first one is a synthetic reservoir, simple and not real; the other two are more complex with close to real characteristics. The results obtained indicate that the proposed model allows good control strategies that increase the NPV. The main contribution of this work is the conception and implementation of a system based on intelligent techniques that is able to support the development and management of intelligent oil reservoirs considering uncertainties.

[pt] Diversos problemas em engenharia, aprendizado de máquina e economia podem ser resolvidos através de Programação Semidefinida (SDP). Potenciais aplicações podem ser encontradas em telecomunicações, fluxo de potência e teoria dos jogos. Além disso, como SDP é uma subclasse de otimização convexa, temos uma série de propriedades e garantias que fazem da SDP uma tecnologia muito poderosa. Entretanto, dentre as diferentes subclasses de otimização convexa, SDP ainda permanece como uma das mais desafiadoras. Instancias de larga escala ainda não podem ser resolvidas pelos atuais softwares disponíveis. Nesse sentido, esta tese porpõe um novo algoritmo para resolver problemas de SDP. A principal contribuição deste novo algoritmo é explorar a propriedade de posto baixo presente em diversas instancias. A convergência desta nova metodologia é provada ao mostrar que o algoritmo proposto é um caso particular do Approximate Proximal Point Algorithm. Adicionalmente, as variáveis ótimas duais são disponibilizadas como uma consequência do algoritmo proposto. Além disso, disponibilizamos um software para resolver problemas de SDP, chamado ProxSDP. Três estudos de caso são utilizados para avaliar a performance do algoritmo proposto. / [en] Many problems of interest can be solved by means of Semidefinite Programming (SDP). The potential applications range from telecommunications, electrical power systems, game theory and many more fields. Additionally, the fact that SDP is a subclass of convex optimization brings a set of theoretical guarantees that makes SDP very appealing. However, among all sub-classes of convex optimization, SDP remains one of the most challenging in practice. State-of-the-art semidefinite programming solvers still do not efficiently solve large scale instances. In this regard, this thesis proposes a novel algorithm for solving SDP problems. The main contribution of this novel algorithm is to achieve a substantial speedup by exploiting the low-rank property inherent to several SDP problems. The convergence of the new methodology is proved by showing that the novel algorithm reduces to a particular case of the Approximated Proximal Point Algorithm. Along with the theoretical contributions, an open source numerical solver, called ProxSDP, is made available with this work. The performance of ProxSDP in comparison to state-of-the-art SDP solvers is evaluated on three case studies.

[pt] Neste trabalho estudamos uma classe de problemas de otimização estocástica com incertezas endógenas que é formulado como um problema de programação não-linear inteira (MINLP). Esta classe de problemas difere dos problemas de otimização estocástica geralmente estudados na literatura pelo fato de que que a distribuição de probabilidade dos parâmetros aleatórios depende das decisões tomadas. Apesar de discutido dentro do contexto do problema de logística humanitária, a metodologia proposta e os resutados obtidos são válidos para uma classe geral de problemas que agrega uma variedade de aplicações. Em particular, propõe-se (i) uma técnica de convexificação de polinômios de variáveis binárias, (ii) um algoritmo de geração de cortes e (iii) a incorporação dos conceitos de importance sampling dentro do contexto de otimização estocástica de modo a permitir a solução de grandes instâncias do problema. Os resultados computacionais apresentados demonstram as vantagens da metodologia proposta ao permitir a solução de instâncias significativamente maiores que aquelas atualmente apresentadas em trabalhos relacionados. / [en] In this work we study a class of stochastic programming problems with endogenous uncertainty – i.e., those in which the probability distribution of the random parameters is decision-dependent – which is formulated as a mixed integer non-linear programming (MINLP) problem. Although discussed in the context of the humanitarian logistics problem, the proposed methodology and obtained results are also valid for a more general class of problems which comprehends a variety of applications. In particular, we propose (i) a convexification technique for polynomials of binary variables, (ii) an efficient cutgeneration algorithm and (iii) the incorporation of importance sampling concepts into the stochastic programming framework so as to allow the solution of large instances of the problem. Computational results demonstrate the effectiveness of the proposed methodology by solving instances significantly larger than those reported in related works.