[pt] A determinação automática e ótima de uma topologia é um passo muito importante dentro do processo da otimização de estruturas. Normalmente, a busca da topologia ótima é o primeiro passo para a definição da configuração da estrutura, pois é nela que é encontrada uma distribuição ótima de material dentro de um domínio pré-estabelecido. Esta dissertação tem como objetivo apresentar uma metodologia simples de otimização topológica, dado um sistema estrutural, definido por suas condições de apoio, carregamento e um domínio de projeto. Tipicamente, um problema de otimização topológica procura obter uma conectividade ótima da estrutura em um domínio de projeto visando minimizar a flexibilidade (ou maximizar a rigidez) com restrição no volume total da estrutura. Desde a introdução dos métodos de homogeneização o campo de pesquisa na área de otimização topológica aumentou e novos critérios estão sendo desenvolvidos. Nesta dissertação é apresentada uma metodologia para a solução de problemas de otimização topológica de estruturas no meio contínuo. A parametrização do tensor constitutivo é feita através de materiais do tipo SIMP (Solid Isotropic Microstruture with Penalty). O problema matemático proposto é o de minimização do volume total da estrutura com restrição no trabalho externo, além de obedecer implicitamente às restrições de equilíbrio e conectividade da estrutura. A análise estática da estrutura é realizada pelo Métodos dos Elementos Finitos utilizando o programa FEMOOP (Finit Element Method - Object Oriented Program) desenvolvido pelo grupo de pesquisa em computação gráfica do DEC/PUC-Rio. Vários métodos são sugeridos para a resolução do problema matemático de otimização topológica. Entre eles encontram-se métodos puramente heurísticos e métodos amparados por uma base matemática sólida. Nesta dissertação, o problema de otimização topológica é resolvido através de técnicas de programação matemática e é resolvido através da técnica de programação seqüencial convexa, utilizando o algoritmo do Método das Assíntotas Móveis (MMA). O desenvolvimento de um programa de computador em otimização topológica, permitiu determinar de maneira automática uma topologia ótima, bem como o estudo de algoritmos de solução e critérios de otimização topológica foi de grande importância para uma maior compreensão de modelos estruturais. / [en] Automatic and optimal determination of a topology is a crucial step in the process of structural optimization. Usually, the search for an optimal topology is the first step for the definition of the structure layout, found as an optimal distribution of material inside of a pre- established domain. This dissertation has as an objective to present a simple methodology for topology optimization, given a structural system, defined by support conditions, load and a design domain.Typically, a problem of topology optimization tries to obtain an optimum connectivity of the structure in a design domain, seeking to minimize the compliance (or maximize the stiffness) with constraints over the total volume of the structure. Since the introduction of homogenization methods,the research field in the area of topology optimization increased and new criteria are being developed.In this dissertation a methodology is presented for the solution of problems of topology optimization of structures in a continuum medium. The parametrization of the constitutive tensor is made through materials of the type SIMP (Solid Isotropic Microstruture with Penalty). The proposed mathematical problem is of minimization of the total volume of the structure with constraint to the external work while obeying implicitly the equilibrium constraints and connectivity of the structure. The static analysis of the structure is accomplished by the Finite Elements Method using the program FEMOOP (Finite Element Method - Object Oriented Program) developed by the research group in computer graphics of DEC/PUC-Rio.Several methods are suggested for the resolution of the mathematical problem of topology optimization. Among them there are some purely heuristic and others aided by a solid mathematical base. In this dissertation, the problem of topology optimization is solved through techniques of mathematical programming, applying the technique of convex sequential programming, using the algorithm of the Method of Moving Asymptots (MMA).The development of a computer program in topology optimization allowed us to determine automatically an optimal topology, and the study of solution algorithms and criteria of topology optimization were of great importance to a larger understanding of structural models.

[pt] A penetração crescente de geração de energia renovável combinada com o desenvolvimento de baterias eficazes, capazes de estocar energia no curto prazo, demandam a representação horária (ou até sub horária) de modelos de despacho de operação. A necessidade de representar intervalos de tempo tão curtos implicaria no aumento significativo da dimensão do problema, possivelmente o tornando intratável computacionalmente. Nesta dissertação, é proposto um método capaz de levar em consideração tais pequenos intervalos de tempo, evitando o aumento considerável de esforço computacional para problemas de despacho hidrotérmico. Este método consiste em calcular a representação analítica da função custo imediato que é então aplicada no contexto de programação dinâmica dual estocástica (SDDP). A função representa os custos operativos imediatos em função da decisão ótima de geração hidrelétrica total. Como a função de custo imediato é linear por partes, ela possui estrutura muito semelhante à utilizada para aproximar a função de custo futuro (conjunto de cortes). São apresentados resultados da aplicação do método em sistemas de energia reais. / [en] The increasing penetration of renewable generation plants in electric systems, combined with the development of effective short-term energy storage batteries, demand scheduling to be represented on an hourly basis or even in smaller time intervals. Multistage stochastic optimization in such time resolution would imply in the increase of the problem s dimension, which might result in the impossibility of solving such problems. This work presents a method that is able to take into account such small time intervals while avoiding the considerable increase of computational effort. This method consists in calculating the analytical representation of the immediate cost function that is applied in the context of stochastic dual dynamic programming (SDDP). The function represents immediate operation costs as a function of the total hydroelectric generation optimal decision. As the immediate cost function is piecewise linear, it leads to a structure very similar to the one used to approximate the future cost function (cut sets). Results of the application of the method in real electric systems are presented.

[pt] Os problemas de transporte marítimo são alvo de extensa bibliografia e constituem uma importante área de aplicação da programação matemática. Em particular, o transporte de granéis - entre os quais o petróleo e seus derivados - vem sendo estudado na Petrobrás há mais de duas décadas. Apesar dos esforços despendidos, os escopos das aplicações são ainda algo limitados e os resultados práticos relativamente escassos. O presente trabalho contribui para sistematização da área, definindo uma hierarquia de problemas de transporte marítimo, padronizando conceitos e notação e desenvolvendo modelos para cada classe de aplicação. São discutidos também alguns métodos de solução e propostos procedimentos para incrementar seus desempenhos. Dois destes métodos, designados por modelo de rotas e modelo de recobrimento, são implementados para instâncias de porte real e os resultados obtidos são analisados. / [en] Sea transportation problems have been the object of extensive literature and constitute an important area for the application of mathematical programming techniques. Bulk commodities transportation, particulary of oil and its by-products, has been studied at Petrobras for over two decades. Despite all efforts, the application scopes are still rather limeted and practical results relatively scarce. The present study contributes for a systenatization in the area, defining a hierarchy of sea transportation problems, standardizing concepts and terminology and developing models for each class of application. Some solution methods are also discussed and procedures are proposed to develop their performance. Two of these methods, named Routing model and instances and the results attained are anlysed.

[pt] Consideramos o Problema Quadrático da Mochila 0-1 (QKP), que consiste em maximizar uma função booleana quadrática sujeito a uma restrição de capacidade linear. O problema possui aplicações em várias áreas, como por exemplo, telecomunicações. engenharia financeira, problemas de localização e teoria dos grafos (clique máximo). Propomos um algoritmo de Branch-and-Bound para resolver exatamente QKP, baseado em Relaxação Lagrangeana. Inicialmente, linearizamos a formulação do problema acima, e em seguida, aplicamos a técnica de relax-and-cut dinamicamente à relaxação contínua do problema, utilizando algumas classes de desigualdades válidas. O método do subgradiente é usado neste processo. Propomos também uma nova heurística primal para QKP, que obtém soluções melhores do que heurísticas propostas anteriormente, encontrando a solução ótima em todas as instâncias que consideramos. A boa qualidade dos limites superior e inferior é traduzida em gap`s pequenos no nó raiz da árvore de enumeração (em geral, menor do que 1%, inclusive para instâncias difíceis). Isto, aliado a testes de fixação de variáveis, permite resolver exatamente QKP em poucos nós da árvore de enumeração. Introduzimos uma maneira de gerar instâncias aleatórias mais difíceis do que as instâncias na literatura. Apresentamos resultados computacionais para instâncias geradas aleatoriamente (instâncias da literatura, e as novas instâncias mais difíceis) para QKP de tamanhos e densidades diferentes; e também para instâncias conhecidas do problema de clique máxima. / [en] We consider the 0-1 Quadratic Knapsack Problem (QKP), which consists of maximizing a quadratic Boolean function subject to a linear capacity constraint. The problem has applications in several areas such as telecommunications, financial engineering, location problems, graph theory (Max Clique). We propose a Branch-and-Bound algorithm to solve the QKP to optimality based on lagrangian Relaxation. Initially, we linearize the formulation of the problem given above and then we relax-and-cut dinamicaly its continous relaxation using a few classes of valid inequalities. In the process the Subgradient Method is applied. We also propose a new primal heuristic for the QKP that has improved upon previous approaches, and finds an optimal solution for all of the instances we considered. The good quality of our upper and lower bounds is translated into small gaps at the root node of the enumeration tree (usually below 1%, even for difficult instances). That, coupled with tests for fixing variables, allowed optimality to be proven within only a few nodes of the enumeration tree. We provide a way to randomly generate instances of the QKP harder than those in the literature. We report computational results for randomly generated instances (the ones in the literature and the new harder ones) of QKP with different densities and sizes; and also for Known instances of Max Clique problems.

[pt] A indústria de petróleo no Brasil ganhou um novo dinamismo com a recente descoberta de grandes reservas petrolíferas em águas profundas. No horizonte 2011-2015 são previstos inúmeros investimentos na cadeia produtiva de petróleo para suportar a dimensão desta nova operação. Diante deste contexto, o apoio à tomada de decisões de investimento na cadeia logística downstream da indústria de petróleo ganha particular importância e o uso de um instrumento de análise que comporte sua complexidade passa a ser fundamental. Dessa forma, a presente dissertação propõe um modelo de programação linear inteira mista (PLIM) que foi desenvolvido para permitir a avaliação de diferentes alternativas de investimento na rede logística existente, sejam elas em expansão das capacidades de transporte, de movimentação, de atracação ou de estocagem. Estas funcionalidades do modelo foram avaliadas através de dois estudos de caso que fazem uso de dados reais da malha logística brasileira de petróleo e derivados. O primeiro estudo avalia a viabilidade do projeto de ampliação de trechos de um duto que abastece diversas bases de distribuição e expõe a interdependência no investimento em cada um deles. Já o segundo avalia as sinergias nos projetos de ampliação da capacidade de movimentação em um terminal marítimo e de aumento da capacidade de transporte do duto que liga este a uma base de distribuição. Em ambos os estudos foi realizada uma análise de sensibilidade do Valor Presente Líquido do projeto em relação ao seu custo de investimento, permitindo fundamentar a escolha do decisor. / [en] The oil industry in Brazil has gained new momentum with the recent discovery of large oil reserves in deep waters. Between 2011 and 2015 numerous investments in the oil production chain are expected in order to support the scale of this new operation. Given this context, investment decisions in the oil industry downstream supply chain gain importance and the use of an analytic tool that encompasses its complexity becomes crucial. Thus, this master thesis proposes a mixed linear programming model (MILP) that was developed to allow evaluation of different investment alternatives in the existing logistics network, whether they approach expanding the transportion, berthing, handling or storage capacities. These features of the model were evaluated through two case studies that use real data of the Brazilian oil and derivatives logistic network. The first case study evaluates the feasibility of the project to expand sections of a pipeline that supplies several distribution centers and exposes the interdependence of investment in each one of them. The second case study evaluates the synergies in two projects: the first one to expand the berthing capacity of vessels in a marine terminal and the second to increase the transport capacity of the pipeline linking it to a distribution center. In both studies a sensitivity analysis of Net Present Value of the project relative to its investment cost was performed, allowing to justify the choice of the decision-maker.

[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 eficiência com que uma empresa é capaz de produzir seus produtos é fundamental para sua sobrevivência em mercados cada vez mais competitivos. A presente dissertação apresenta uma proposta de minimização dos custos de produção e estoques para a otimização das decisões de Planejamento e Controle de Produção. O problema consiste em analisar as compensações entre estoque de antecipação e a contratação de pessoal adicional e/ou horas extras para suprir a demanda em momentos de pico. O objetivo é avaliar os trade-offs existentes entre os custos de hora extra e de estoques para reagir em períodos de oscilação de demanda, com o objetivo de criar um modelo de apoio à decisão de gestão da produção. Um estudo de caso é apresentado para um produto de varejo do ramo farmacêutico. O caso foi modelado por programação matemática linear e programado em sistema AIMMS. A partir dos resultados encontrados, verificou-se que com a implantação do modelo foram obtidas soluções balanceadas, com a otimização dos recursos da produção, que permite a empresa planejar antecipadamente as suas operações de maneira a minimizar os investimentos em estoques e os custos de utilização de hora-extra em termo de famílias de produtos. / [en] The ability of a company to produce their products is essential for their survival in increasingly competitive markets. The present work proposes to minimize the production and inventory costs in order to optimize the production planning and control system decisions. The problem consists in understanding the benefits between anticipation inventory and employment levels and/or overtime in order to reach non-constant, time varying demand, considering fixed sale and production capacity. We create a mixed linear programming (MLP) model to support the decisions and adjustments in planning process and production management. This study applies to a specific retail product of a pharmaceutical industry and is implemented in the AIMMS modeling language. From the results, we can say that the implementation of this model is very useful and can help to find better solutions and improve the optimization of resources, which allows the company to anticipate its decisions and minimize the investments in inventories and costs of using overtime in terms of product families.

[pt] O objetivo deste trabalho é apresentar as formulações variações para o problema de análise limite e o desenvolvimento do processo de resolução, que envolve o método dos elementos finitos e as técnicas de programação matemática. As formulações variacionais são apresentadas em três versões: estática, cinemática e mista. Estas formulações são derivadas a partir da proposição das relações constitutivas na forma de pseudo-potenciais conjugados. Esses princípios são discretizados através do método dos elementos finitos. São propostos dois algoritmos iterativos de programação matemática para a solução do problema. Os algoritmos podem ser aplicados tanto para o comportamento plástico descrito por funções de escoamento lineares como não lineares. Nas aplicações numéricas são analisados corpos em estado plano de tensão, deformação e com simetria de revolução. / [en] The aim of this work is to present variational formulations for the limit analysis problem and solution procedures using the finite element method and mathematical programming techniques. The variational formulations are presented in three versions: static, kinematical and mixed. These formulations are derived from the proposition of the constitutive relationship in the form of conjugate pseudopotencials. Finite element discretizations are proposed for each of the three continuous problems. Two iterative mathematical programming algorithms are prosed to solve the problem. These algorithms can be applied to the plastic behavior described by a set of linear or non-linear yield functions. Limit analysis in plane strain, plane stress and axissymetric solids are considered in the numerical examples.

[pt] Esta dissertação teve como objetivo principal verificar a aplicabilidade da metodologia de análise de envoltória de dados - DEA (Data Envelopment Analysis) - ao setor de saneamento, avaliando a eficiência das 71 maiores empresas prestadoras de serviços de água e esgoto no Brasil, segundo o número de ligações ativas de água. Adicionalmente, foi gerada uma ordenação das empresas segundo suas eficiências relativas e procurou-se indicar o aumento mínimo necessário, em cada tipo de produto, que as empresas consideradas ineficientes teriam que realizar para se tornarem eficientes. O trabalho apresenta um breve histórico do setor de saneamento no País, desde o início das primeiras empresas até o projeto atual de modernização. Descrevem-se também os conceitos e modelos básicos da DEA, necessários para entendimento do texto. A DEA foi aplicada aos dados do Sistema Nacional de Informações sobre Saneamento. Os resultados são interpretados buscando-se ressaltar o potencial da metodologia para obtenção de indicadores de desempenho úteis para órgãos formuladores de políticas públicas e agências de financiamento. Análises adicionais foram feitas buscando testar a validade dos modelos, detectar a presença de economias de escala e avaliar a robustez dos resultados. Concluiu-se que a metodologia pode ser adequadamente empregada para análise do setor e auxiliar as políticas de concessão de financiamentos, oferecendo indicações iniciais para o estabelecimento de metas para melhorias. / [en] This thesis seeks to test the applicability of the DEA (Data Envelopment Analysis) methodology for assessing the managerial efficiency of Brazilian water and sewage companies. This objective was pursued by evaluating the efficiency of the 71 largest companies of water services in Brazil, in terms of the number of properties served. Additionally, the companies were ranked according to their relative efficiency, and for each inefficient company it was estimated how much increase in each one of the outputs would be necessary for rendering it efficient. The text presents a brief history of the sanitation sector in Brazil, and reviews the basic DEA concepts and models necessary for understanding the analyses.The DEA was performed on the data collected by the Sistema Nacional de Informações sobre Saneamento (Brazilian National Sanitation Information System). The results were interpreted stressing the potential of DEA for generating performance indicators useful for public policies and funding agencies. Further analyses were made in order to test the validity of the model, detect likely economies of scale and to assess the robustness of the results.The results suggest that DEA can be adequate for analyzing the target industry, and for contributing to public policy formation and funding decisions by offering relevant indicators for setting improvement goals.

[pt] O presente trabalho propõe uma formulação para o projeto ótimo de pilares de edifícios altos de concreto armado. São variáveis de projeto as dimensões da seção transversal e a armadura longitudinal dos pilares e a resistência característica do concreto. A fim de reduzir o tamanho desta classe de problema, a estratégia de solução em multinível é aplicada. O problema é então subdividido em um problema global de otimização conectado a uma série de subproblemas individuais de otimização. No problema global são determinadas as dimensões da seção transversal de todos os pilares e a resistência característica do concreto, enquanto que nos subproblemas individuais são determinadas apenas as armaduras longitudinais dos pilares. As variáveis dos subsistemas são freqüentemente chamadas de variáveis locais, enquanto que as variáveis do sistema global, responsáveis pela interação entre os grupos de variáveis, são denominadas variáveis globais ou de acoplamento. A função objetivo do problema de otimização é o custo total das colunas do edifício. Os edifícios são modelados como pórticos espaciais e a não-linearidade geométrica é considerado na análise estrutural. A hipótese de diafragma rígido é adotada para o comportamento das lajes e a rigidez à torção é desprezada em todas as barras do pórtico. Cargas permanentes, acidentais e devidas ao vento são aplicadas ao modelo. Restrições relativas aos estados limite último e de utilização, bem como restrições relativas aos limites máximos e mínimos atribuídos a cada variável, são impostas ao problema de otimização. Adicionalmente, impõem-se restrição sobre o parâmetro de instabilidade, caso este parâmetro seja empregado na determinação dos esforços globais de 2a ordem. Os estados limite são definidos de acordo com o código brasileiro para projeto de estruturas de concreto NBR-6118 (2003). O problema de otimização proposto é resolvido empregando-se técnicas de programação matemática. / [en] This work proposes a formulation for the optimum design of columns of reinforced concrete tall buildings. The design variables are the dimensions of the cross-sections and the amount of longitudinal reinforcement in the columns and the concrete characteristic resistance. Aiming at reducing the size of this class of problem, the multilevel optimization technique is applied so that the problem is subdivided into a global problem connected with a series of dependent subproblems. In this kind of problem, the design variables are subdivided into two groups, namely, the group of the so called global variables, represented here by the cross-section dimensions of the columns and by the concrete characteristic resistance, and the group of local variables, represented here by the areas of the longitudinal steel reinforcement in the cross-sections of the columns. Consequently, a global optimization problem is defined for the global variables, at the global level, and local independent optimization sub- problems are defined for the local design variables, at the local levels, following each iteration at the global level. The objective function of the optimization problem is the total cost of the columns of the building. The buildings are modeled as three dimensional frames and geometric nonlinear behavior is considered in the structural analysis. The assumption of rigid diaphragm is adopted for the structural behavior of the slabs and the torsional stiffness of elements is neglected. Dead, live and wind loads are applied to the model. Constraints related to ultimate and serviceability limit states, as well as lateral constraints, are imposed to the design variables. The limit states are defined according to the Brazilian Code for reinforced concrete structures NBR-6118 (2003). The solution of the optimization problem is obtained using Mathematical Programming techniques.