[pt] A natureza incerta e os altos incentivos econômicos do negócio de refino são forças motrizes para melhorias nos processos de planejamento das refinarias. Decisões tomadas na cadeia do petróleo diferem principalmente na gama de atividades (integração espacial) e no horizonte de planejamento (integração temporal). O objetivo desta tese é abordar o problema da integração da cadeia do petróleo sob incerteza em diferentes níveis de decisão. Modelos de programação matemática tático e operacional são propostos. O modelo tático maximiza o lucro esperado da cadeia de suprimentos e aloca metas de produção para as refinarias considerando restrições logísticas. O modelo operacional maximiza o lucro esperado de cada refinaria determinando a quantidade de material processada por unidade de processo em um dado período. Ambos os modelos são lineares estocásticos de dois estágios, onde a incerteza é incorporada nos parâmetros dominantes de cada nível (preço e demanda no nível tático e suprimento de petróleo e capacidade das unidades no nível operacional). A integração espacial é discutida no nível tático (considerando a cadeia de suprimentos), enquanto a integração temporal é discutida na interação entre os dois níveis. Duas abordagens de integração temporal são consideradas: hierárquica, onde o fluxo de informações é somente do modelo tático para o operacional, e iterativa, onde há retorno do nível operacional para o tático. Um estudo de escala industrial foi conduzido para demonstrar os benefícios da integração em ambiente estocástico. Resultados são oferecidos no contexto de um estudo usando dados da indústria brasileira do petróleo para demonstrar a eficácia das abordagens propostas. / [en] The uncertain nature and high economic incentives of the refining business are driving forces for improvements in the refinery planning process. Decisions made at the oil chain differ mainly in the range of activities (spatial integration) and planning horizon (temporal integration). This thesis purpose is to address the problem of the oil chain integration under uncertainty at different decision levels. Tactical and operational mathematical programming models are proposed. The tactical model maximizes the expected profit of the supply chain and allocates the production targets to refineries taking logistics constraints into account. The operational model maximizes the expected profit of each refinery determining the amount of material that is processed at each process unit in a given period. Both models are two-stage stochastic linear programs where uncertainty is incorporated in the dominant random parameters at each level (price and demand at the tactical level and oil supply and process capacity unit at the operational level).Spatial integration is discussed at the tactical level (considering supply chain), whereas the temporal integration is discussed in the interaction between the two levels. Two temporal integration approaches are considered: hierarchical, where the flow of information is only from the tactical to the operational model, and iterative, where there is feedback from the tactical to the operational model. An industrial scale study was conducted to discuss the benefits of integration in a stochastic environment. Results are offered in the context of a study using data from the Brazilian oil industry to demonstrate the effectiveness of the proposed approaches.

[pt] Nos últimos anos, nota-se uma forte tendência no Brasil de oferta de petróleos cada vez mais pesados e ácidos em contraposição a uma crescente demanda de derivados mais leves dentro de especificações mais rígidas. Dessa forma, o Brasil se depara com a necessidade em adaptar suas refinarias e rede logística a esse novo perfil. Nesse contexto é importante a avaliação da cadeia integrada de petróleo e derivados no longo prazo, visando auxiliar a tomada de decisão em relação aos projetos que devem ser considerados na carteira de investimentos. Por se tratar de uma decisão de longo prazo, é importante levar em consideração as incertezas relacionadas aos parâmetros considerados, como: oferta e preço de petróleos, demanda e preço de derivados e outros. Assim, tornase possível a avaliação de uma carteira de projetos de investimentos considerando os riscos existentes. Este trabalho propõe apresentar uma metodologia de otimização sob incerteza, que utilize programação estocástica em conjunto com técnicas de otimização de portfólio, aplicada ao estudo de uma carteira de investimentos na área de abastecimento de petróleo. O estudo é focado em um modelo de programação linear que maximiza o resultado presente líquido esperado ao longo de um horizonte de tempo estipulado, dado um nível de risco aceitável. Foram propostas duas abordagens de medida de risco: Conditional Value-at-Risk (CVaR) e Minimax. A partir dos resultados numéricos, ficou comprovado que a decisão otimizada de investimento na área de petróleo e derivados apresenta variação com o nível de risco que se pretende assumir. / [en] Over the last years, a strong trade-off between crude oil offer and oil product demand has been posed in Brazil: while the oil produced in Brazil is getting heavier, its` products must be light, constrained by rigid specifications. Hence, the country needs to adapt its refineries and logistic network to this new profile. In this context, a long term analysis of the integrated oil chain is a relevant task. This analysis helps the decision maker to choose projects that should be considered in portfolio investment. During the decision process, it is important to take into account uncertainties related to some parameters: crude oil prices, crude oil offer, product prices, expected demand and others. By doing that, it is possible for the analyst to evaluate a project portfolio considering risks. The present work proposes a methodology for optimization under uncertainty, applied to the study of a portfolio investment for the downstream oil industry, employing both stochastic programming and portfolio optimization techniques. The study is focused on a linear programming model that maximizes the expected net present value (NPV) along the specified time horizon and risk level. Two approaches have been proposed to measure risk: Conditional Value-at-Risk (CVaR) and Minimax. The results show that the investment choice in the oil chain varies with the imposed risk level.

[pt] Planejar a expansão de sistemas de transmissão de energia elétrica constitui uma tarefa complexa dentro do planejamento do setor elétrico. De acordo com os critérios vigentes, hoje no Brasil, procura-se abordar o problema através de um enfoque de programação matemática. É feito um estudo das técnicas em uso e dos modelos de análise de redes de transmissão. Em seguida é proposta uma nova metodologia para resolver o problema, levando em conta a cultura dos planejadores que podem, assim, interagir com os programas, aperfeiçoando o planejamento. Foi elaborado um modelo de programação inteira, capaz de gerar inúmeras alternativas de planejamento para um dado ano. Estas alternativas são analisadas e concatenadas, obtendo-se o planejamento ao longo do tempo. Apresenta-se um caso real, do planejamento da expansão do sistema sul do Brasil, comparando-se os resultados obtidos com os de outras metodologias. / [en] The plannification of the transmission system expansion is a very complex problem. In this work it is proposed a mathematical programming model to solve it, taking in account the restrictions established by the brazilian electric sector. It is shown the characteristics of some technics for solving the problem and a brief description of the transmission network analysis methods is also presented. It is proposed a new methodology to solve the planning problem, taking in account the planners experience. They are able to interfere on the process interacting with the program looking fot better solutions. An integer programming model was developped to obtain Several distinct expanded configurations for every year of the planning horizon. These configurations are analysed and then linked year, to obtain an expansion policy of the transmission sistem. It is presented the actual planning of the southern brazilian system, and the result obtained by this model are compared with those obtained by other methodologies.

[pt] As técnicas tradicionais de otimização de consultas em banco de dados possuem como heurística fundamental a organização dos predicados de uma consulta em dois tipos principais: predicados simples e predicados envolvendo junção(join) de tabelas. Como príncipio geral considera-se a priori os predicados envolvendo junção bem mais caros do que os predicados simples, e também que não existam diferenças significativas entre os tempos de processamento dos predicados simples, o que leva o otimizador a executar primeiro os predicados simples(em uma ordem qualquer), a fim de se diminuir a quantidade de tuplas que seriam necessárias à execução da junção. Essa consideração que se aplica bem à maioria das aplicações convencionais de banco de dados, passou a não se aplicar mais à novas aplicações que envolviam o preprocessamento de dados e/ou funções complexas nos predicados que não envolviam junções. Dessa forma esses novos predicados simples passaram a ter um tempo de processamento não mais desprezível em relação aos predicados que envolviam junções e também em relação a outros predicados simples. Dessa forma a heurística principal de otimização não se aplicava mais e tornou-se necessário o desenvolvimento de novas técnicas para resolver consultas que envolvessem esse novo tipo de predicado, que passou a ser chamado de predicado caro. O presente trabalho tem dois objetivos principais: apresentar um framework que possibilite o desenvolvimento, teste e análise integrada de algoritmos para o processamento de predicados caros, e analisar o desempenho de quatro implementações de algoritmos baseados na abordagem Cherry Picking, cujo o objetivo é explorar a dependência entre os dados que compõem as consultas. Os experimentos são conduzidos em consultas envolvendo predicados conjuntivos (AND) e a idéia geral é tentar avaliar os atributos em uma ordem que minimize o custo de avaliação geral das tuplas. / [en] Traditional database query optimization technique have as its main heuristic the organization of predicates in two main types: selection predicates and join predicates. Join predicates are considered much more expensive than selection predicates. In additional, it's also considered that there's no big difference among the costs of different selection predicates, what makes the optimizer executes them first in any order, reducing the number of tuples necessary to execute join predicates.This assumption, that is well applied in traditional database applications, becomes invalid in respect of recent database applications, that executes complex functions over complex data in selection predicates. In this cases, selection predicates are considered more expensive than join predicates and their costs cannot be considered equivalent anymore. This makes the main heuristic of push down selections invalid for these kind of new selection predicates which calls for new optimization techniques. These type of cue named expensive predicates. This work has two main objectives: Present a software that makes possible the development, test and integrat analisys of different algorithms for evaluating expensive predicates and analyse the performance of four algorithm's implementations that are based on Cherry Picking strategy, which aims at exploring the data dependency between input values to expensive predicates. The experiments considered conjunctive(AND) queries, and the general idea is to try evaluate the attributes in a order that minimizes the general cost of the tuples.

[pt] A principal contribuição desta tese consiste no desenvolvimento de uma heurística híbrida, robusta e eficiente, para o problema de empacotamento unidimensional. A heurística proposta utiliza os seguintes componentes: limites inferiores e superiores do número de caixas; reduções; abordagem dual para a obtenção de soluções iniciais; heurísticas para redistribuição dos pesos; e busca tabu. O outro objetivo desta tese é a aplicação desta heurística para a solução do problema de escalonamento em processadores paralelos idênticos. São apresentados resultados computacionais obtidos sobre centenas de problemas testes da literatura. / [en] We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several components: lower and upper bounds; reductions, construction of initial solutions by reference to the dual problem;heuristics for load redistribution based on dominance, differencing, and unbalancing; and tabu search. We also investigate the application of this hybrid heuristic to the problem of task scheduling on identical parallel processors. Computational results on hundreds of benchmark test problem are presented.

[pt] Neste trabalho estudamos o problema de planejamento hidrotérmico para um sistema onde as hidrelétricas estão em paralelo, buscando estender os resultados obtidos por Bortolossi, Pereira e Tomei. Com uma conveniente formulação contínua, estabelecemos um teorema que garante a existência de solução para este problema, e caracterizamos os ótimos interiores. / [en] In this work we study the problem of hydrothermal scheduling for a system where the hydroelectric power stations are disposed in parallel, trying to extend the results obtained by Bortolossi, Pereira e Tomei. With a convenient continuous formulation, we establish a theorem that guarantees the existence of solution to this problem, and characterize the interior optimums. / [es] En este trabajo estudiamos el problema de planeamiento hidrotérmico para un sistema donde las hidroeléctricas están en paralelo, com el objetivo de extender los resultados obtenidos por Bortolosi, Pereira y Tomei. Con una formulación contínua conveniente, establecemos un teorema que garantiza la existencia de solución para este problema, y caracterizamos los óptimos interiores.

[pt] Esta tese reúne as técnicas estatísticas indicadas para a modelagem da média e da dispersão das características de qualidade de processos e produtos, em experimentos fatoriais não replicados, resultando na definição de um roteiro integrado e detalhado de análise. A motivação vem de que, apesar de haver várias publicações sobre regressão linear clássica, modelos lineares generalizados (MLG), transformação da resposta e planejamento de experimentos, não existe um texto que reúna e descreva em detalhe todos os aspectos da modelagem da média e da dispersão em experimentos fatoriais. Os poucos textos sobre esse assunto não descrevem vários aspectos importantes em estudos dessa natureza, por exemplo, como são aplicados os testes de significância dos coeficientes dos MLG, e quais são as estatísticas e os gráficos indicados para verificar a adequação do modelo. Ademais, nada foi encontrado na literatura sobre a identificação de modelos em experimentos fatoriais. Todos esses aspectos são detalhados nessa tese. Uma vez construído o modelo, é mostrado como usá-lo para obter as condições ótimas de operação dos processos e produtos. Além do cumprimento desse objetivo principal, a tese traz algumas contribuições adicionais; a saber: a) aponta limitações em todos quatro métodos da literatura que se propõem a escolher a transformação mais adequada para a resposta. Esses métodos não produziram resultados satisfatórios quando houve interações significativas entre os fatores; b) propõe a utilização de métodos de transformação da resposta como fonte de indicação da função de ligação a ser usada nos modelos lineares generalizados; e c) propõe a utilização da função de log-verossimilhança para uma escolha conjunta da distribuição de probabilidade e da função de ligação, nos modelos lineares generalizados. / [en] This thesis puts together the statistical techniques indicated for modelling the mean and dispersion of quality characteristics of products and processes via unreplicated factorial experiments, resulting in the definition of an integrated and detailed script for the analysis. It was motivated by the fact that, although there are many publications about classic linear regression, generalized linear models (GLMs), response transformation and design of experiments, there is no one text which put together and describe in detail all the aspects of the modelling of the mean and the dispersion in factorial experiments. The few texts on the subject do not describe a number of important aspects in studies of this nature, e.g. how significance tests for the coefficients in GLMs should be applied and which are the statistics and plots indicated for checking model adequacy. In addition, nothing was found in the literature about model identification in factorial experiments. All these aspects are detailed in this thesis. Once the model is built, we show how to use it in order to obtain the optimal operating conditions for products and processes. Besides achieving this main objective, the thesis brings some additional contributions, namely: a) it points out limitations in all the four methods in the literature which have the purpose of selecting the most adequate transformation of the response; b) it proposes using response transformation methods as a source of indication of the link function to use in GLMs, and c) it proposes using the loglikelihood function for the joint choice of the probability distribution and of the link function in GLMs.

[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] O desempenho de protocolos de múltiplos acesso em redes de dados, no que diz respeito a parâmetros como vazão, retardado e probabilidade de rejeição de pacotes, representa um dos fatores primordiais na comparação entre diversos tipos de sistemas propostos, no sentido de se buscar uma otimização do uso do canal de transmissão. Tendo em vista a dificuldade de se fazer um modelo analítico que represente bem os protocolos existentes, utilizam-se, normalmente, formulações simplificadas para o cálculo dos parâmetros desejados, ou recorre-se a um modelo de simulação, que necessita de maior tempo de computação pra obtenção dos resultados. Com o objetivo de se obter uma análise mais precisa dos protocolos de múltiplo acesso utilizados em redes de dados foram desenvolvidos modelos a partir de um método proposto por S.M.Meerkov e J.T.Lim. estes modelos consideram estações com buffers transmitindo mensagens que possuem um ou mais pacotes em canais com retardo, utilizando a distribuição de probabilidades do tamanho destas mensagens. É proposta também a retirada da hipótese simplificadora usualmente feita em análises envolvendo o protocolo ALOHA- Segmentado, de que a primeira transmissão de cada pacote é também feita com retardo. Esta metodologia é novamente aplicada para modelar um protocolo híbrido, que combina transmissões utilizando o modo S- ALOHA e um modo de reserva. São apresentados, também, modelos e resultados de simulação para validação dos modelos analíticos propostos. / [en] The performance of multiple access protocols in data networks, whit respect to parameters like throughput, delay and probability of packet rejection, is one of the major factor when comparing different types of proposed systems during an optimization process of the transmission channel. Due to difficulties in developing an analitical model that can make a good representation of the existing protocols, usally simprified formulations are used to evauate the desired parameters, or instead, simulations models are created, requiting more time of CPU to obtain the results. Having the objective of obtaing a more precise analitical tool for evaluating the multiple access protocols used in data networks models have been developed, based on the method proposed by S.M.Meerkov and J.T.Lim. these models consider stations having buffers and transmitting messages with one or more packets through delay channels, according to the distribuition of probabilities of the size of these messages. It is also proposed a model which do not present the hypothesis ususally used to simplify the Slotted-ALOHA (S-ALOHA) protocol, with respect to the need of having a delayed first transmission of a packet. The reffered combines transmittions in S-ALOHA mode and in a reervation mode. Simulation models and results are also used for validation of the proposed analitical models.

[pt] Este trabalho está relacionado ao problema da utilização eficiente da órbita de satélite geoestacionários. Neste problema, os satélites devem ser alocados adequadamente na órbita, obedecendo a limites de interferência máxima, de modo a satisfazer os requisitos de desempenho dos sistemas. Algumas técnicas para a determinação das posições orbitais de satélites existentes e planejados são mencionadas. Um novo modelo matemático para a otimização das posições orbitais dos satélites, baseado na minimização de uma função objetivo associada à interferência total que afeta cada um dos sistemas, é proposto. Finalmente, alguns resultados obtidos através da aplicação deste modelo são analisados e comparados a outros resultados disponíveis. / [en] This work is related to the problem of efficiently using the geoestationary satellite orbit in an interference limited environment. Some techniques to determine the orbital positions of existing and planned satellites are mentioned. A new mathematical model for optimizing satellite orbital positions based on the minimization of an objective function associated to the total interference affecting each system is proposed. Finally, results obtained through the application of this model are analysed and compared to other available results.