Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T18:36:28Z (GMT). No. of bitstreams: 1 Marini_BrunoConti_M.pdf: 1252984 bytes, checksum: 40439ec279501ea9ca594d950e42a229 (MD5) Previous issue date: 2011 / Resumo: Uma das formas mais econômicas e, em relação ao meio ambiente, mais seguras de se transportar combustíveis é bombeá-los através de redes de dutos. Contudo, as diversas restrições operacionais que precisam ser consideradas fazem com que o planejamento das atividades de bombeamento se transforme em um grande desafio. Dentre os diversos cenários em que o problema se apresenta, investiga-se nessa dissertação o caso de uma rede composta de um único duto onde diversos produtos são bombeados unidirecionalmente. Trata-se de uma situação real enfrentada pela Petrobras no gerenciamento da rede OSBRA. Na literatura existem propostas de vários modelos matemáticos para tratar esta instância particular do problema. Contudo, no melhor do nosso conhecimento, não existem comparações efetivas entre estes modelos e os algoritmos usados para computá-los. Nessa dissertação faz-se uma comparação aprofundada entre três desses modelos, a qual se baseia em uma metodologia sugerida pelos técnicos da Petrobras. Neste trabalho são destacadas não só as dificuldades envolvendo a implementação dos modelos, bem como as deficiências encontradas na aplicação da metodologia de comparação usada pela empresa. Propostas são feitas nessa dissertação no intuito de superar estes obstáculos / Abstract: One of the most economical and, with respect to the environment, safest ways to transport fuel is to pump them through pipeline networks. However, the several operational constraints that have to be considered turn the planning of these activities into a major challenge. Among the several cenarios in which the problem arises, in this dissertation we investigate the case of a network composed of a single pipeline through which several products are pumped unidirectionally. This is a real situation faced by Petrobras in the management of the OSBRA network. In the literature there are proposals of various mathematical models to tackle this particular instance of the problem. However, to the best of our knowledge, there are no effective comparisons of these models and of the algorithms used to compute them. In this dissertation an in-depth comparison is made between three of these models, which is based on a methodology suggested by the technical staff of Petrobras. In this work we highlight not only the difficulties involving the implementation of the models but also the deficiencies encountered in the application of the comparison methodology used by the company. Proposals are made in this dissertation in an attempt to overcome these obstacles / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Zanoni Dias / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-21T22:58:04Z (GMT). No. of bitstreams: 1 Iizuka_VictordeAbreu_M.pdf: 1453681 bytes, checksum: 1fec01321d56a93084d2597366b44422 (MD5) Previous issue date: 2012 / Resumo: A teoria da seleção natural de Darwin afirma que os seres vivos atuais descendem de ancestrais, e ao longo da evolução, mutações genéticas propiciaram o aparecimento de diferentes espécies de seres vivos. Muitas mutações são pontuais, alterando a cadeia de DNA, o que pode impedir que a informação seja expressa, ou pode expressá-la de um modo diferente. A comparação de sequências é o método mais usual de se identificar a ocorrência de mutações pontuais, sendo um dos problemas mais abordados em Biologia Computacional. Rearranjo de Genomas tem como objetivo encontrar o menor número de operações que transformam um genoma em outro. Essas operações podem ser, por exemplo, reversões, transposições, fissões e fusões. O conceito de distância pode ser definido para estes eventos, por exemplo, a distância de reversão é o número mínimo de reversões que transformam um genoma em outro [9] e a distância de transposição é o número mínimo de transposições que transformam um genoma em outro [10]. Nós trataremos os casos em que os eventos de reversão e transposição ocorrem de forma isolada e os casos quando os dois eventos ocorrem simultaneamente, com o objetivo de encontrar o valor exato para a distância. Nós criamos modelos de Programação por Restrições para ordenação por reversões e ordenação por reversões e transposições, seguindo a linha de pesquisa utilizada por Dias e Dias [16]. Nós apresentaremos os modelos de Programação por Restrições para ordenação por reversões, ordenação por transposições e ordenação por reversões e transposições, baseados na teoria do Problema de Satisfação de Restrições e na teoria do Problema de Otimização com Restrições. Nós fizemos comparações com os modelos de Programação por Restrições para ordenação por transposições, descrito por Dias e Dias [16], e com as formulações de Programação Linear Inteira para ordenação por reversões, ordenação por transposições e ordenação por reversões e transposições, descritas por Dias e Souza [17] / Abstract: The Darwin's natural selection theory states that living beings of nowadays are descended from ancestors, and through evolution, genetic mutations led to the appearance of different kinds of living beings. Many mutations are point mutations, modifying the DNA sequence, which may prevent the information from being expressed, or may express it in another way. The sequence comparison is the most common method to identify the occurrence of point mutations, and is one of the most discussed problems in Computational Biology. Genome Rearrangement aims to find the minimum number of operations required to change one sequence into another. These operations may be, for example, reversals, transpositions, fissions and fusions. The concept of distance may be defined for these events, for example, the reversal distance is the minimum number of reversals required to change one sequence into another [9] and the transposition distance is the minimum number of transpositions required to change one sequence into another [10]. We will deal with the cases in which reversals and transpositions events occur separately and the cases in which both events occur simultaneously, aiming to find the exact value for the distance. We have created Constraint Programming models for sorting by reversals and sorting by reversals and transpositions, following the research line used by Dias and Dias [16]. We will present Constraint Logic Programming models for sorting by reversals, sorting by transpositions and sorting by reversals and transpositions, based on Constraint Satisfaction Problems theory and Constraint Optimization Problems theory. We made a comparison between the Constraint Logic Programming models for sorting by transpositions, described in Dias and Dias [16], and with the Integer Linear Programming formulations for sorting by reversals, sorting by transpositions and sorting by reversals and transpositions, described in Dias and Souza [17] / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-20T15:20:18Z (GMT). No. of bitstreams: 1 Oliveira_Lucasde_M.pdf: 1308997 bytes, checksum: cc147cd3d3c9f50c61a48d83579b6c49 (MD5) Previous issue date: 2012 / Resumo: Esta dissertação tem como foco a investigação experimental de algoritmos exatos, aproximativos e heurísticos aplicados na resolução do chamado problema do corredor de comprimento mínimo (PCCM). No PCCM recebemos um polígono retilinear P e um conjunto de polígonos retilineares menores formando uma subdivisão S planar conexa de P. Uma solução para este problema, também chamada de corredor, é formada por um conjunto conexo de arestas de S, e tal que cada face interna em S possui pelo menos um ponto em sua borda que pertence a alguma aresta deste conjunto. O objetivo então é encontrar um corredor tal que a soma total dos comprimentos das arestas seja a menor possível. Trata-se de um problema NP-difícil com aplicações em áreas diversas, tais como telecomunicações, engenharia civil e projeto de circuitos VLSI. O PCCM pode ser reduzido polinomialmente a um problema em grafos denominado problema da árvore de Steiner com grupos (PASG). Considerando esta transformação, estudamos e implementamos dois métodos aproximativos, um método exato de branch-and-cut, e um método heurístico baseado na metaheurística GRASP combinada com um evolutionary path relinking (GRASP+EPR). Além disso, propomos três heurísticas de busca local que visam melhorar a qualidade de soluções do PASG. Instâncias do PCCM foram geradas aleatoriamente, nas quais aplicamos os métodos implementados. Analisamos os resultados, e apresentamos as situações onde é interessante utilizar cada método. Verificamos que o método branch-and-cut foi capaz de encontrar soluções ótimas para instâncias que julgamos ser de grande porte em tempos computacionalmente aceitáveis. O melhor algoritmo aproximativo obteve corredores que na média têm comprimento 17% maior que o comprimento ótimo. Se combinarmos este algoritmo com as heurísticas de melhoria propostas este percentual cai para a média de 3,5%. Finalmente, o GRASP+EPR consome mais tempo que este algoritmo aproximativo, entretanto, o comprimento dos corredores obtidos por ele é em média 0,9% maior que o comprimento ótimo / Abstract: This dissertation focuses on the experimental investigation of exact, approximation and heuristic algorithms applied to solve the so-called minimum length corridor problem (MLCP). In the MLCP we receive a rectilinear polygon P and a set of minor rectilinear polygons forming a connected planar subdivision S of P. A solution for this problem, also called corridor, is formed by a set of connected edges of S, and such that each inner face of S has at least one point on its your border which belongs to an edge in this set. The goal is to find a corridor such that the sum of lengths of the edges is as small as possible. This is an NP-hard problem with applications in several areas such as telecommunications, civil engineering and design of VLSI circuits. The MLCP can be polynomially reduced to a graph problem known as group Steiner tree problem (GSTP). Based on this transformation, we studied and implemented two approximation methods, an exact branch-and-cut method, and a heuristic method based on the metaheuristic GRASP combined with an evolutionary path relinking (GRASP+EPR). Furthermore, we propose three local search heuristics to improve the quality of GSTP solutions. MLCP instances were randomly generated, in which we apply the methods implemented. We analyzed the results, and present situations where it is interesting to use each method. We found that the branch-and-cut has been able to find optimal solutions for instances that we consider to be large in acceptable computational times. The best approximation algorithm obtained corridors having average length 17% higher than the optimum length. If we combine this algorithm with the improvement heuristics proposed this percentage drops to an average of 3.5%. Finally, the GRASP+EPR spent more time than this approximation algorithm, however, the length of the corridors obtained by the method is, on average, 0.9% higher than the optimum length / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Paulo de Barros Correia / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecânica / Made available in DSpace on 2018-08-27T01:59:39Z (GMT). No. of bitstreams: 1 Silva_ElisaBastos_D.pdf: 2776184 bytes, checksum: 20b2252b72c7204d062893f8dcb3d304 (MD5) Previous issue date: 2015 / Resumo: Leilões de novos empreendimentos de energia envolvem o compromisso de construí-los e o direito de explorá-los por meio de contratos de outorga. O leiloeiro, cujo objetivo é minimizar o pagamento pela energia contratada, buscando a redução de seu preço para os consumidores finais, fornece o direito de outorga da usina para o vencedor. O licitante é um investidor, e.g., uma empresa de geração que procura maximizar seu benefício com a venda de energia proveniente do empreendimento. Quando a natureza desses empreendimentos é complementar, torna-se possível proporcionar maiores benefícios aos licitantes, e maior eficiência ao leilão, caso sejam negociados em conjunto. Atualmente, o projeto de leilão instituído é composto por uma abordagem híbrida, sequencial e simultânea, que não permite a extração das sinergias entre empreendimentos. Esta tese examina duas metodologias híbridas de leilões reversos, considerando-se o ponto de vista do leiloeiro. O primeiro modelo, centralizado, é composto por duas fases: uma simultânea de lance aberto e outra combinatória de lance fechado. A fase simultânea incentiva a revelação do preço da energia, enquanto a fase combinatória oferece oportunidade aos licitantes de submeterem ofertas mais agressivas através de pacotes de empreendimentos complementares. O modelo centralizado é formulado como um problema de otimização inteiro e combinatório. A função-objetivo consiste em minimizar o pagamento, isso é, energia multiplicada pelo preço (lance) para todas as usinas. A estratégia de solução identifica os vencedores, resolvendo um problema de set-packing restrito. A segunda metodologia utiliza uma abordagem, também, em duas fases. A primeira é um projeto simultâneo de lance aberto, e a segunda fase um projeto combinatório descentralizado. Nesse modelo, a dificuldade do problema aumenta progressivamente à medida que os pacotes são ofertados. A dificuldade da alocação é distribuída entre os licitantes e, por isso, o leiloeiro não necessita resolver um problema de otimização. As metodologias propostas são aplicadas aos leilões de energia nova para o setor elétrico brasileiro. Os resultados mostram que a utilização de ambas as metodologias resolvem o problema de alocação com um tempo computacional aceitável / Abstract: Auctions for new power plants involve a commitment of constructing and the right of exploring them through power sales contracts. The auctioneer -- whose objective is to minimize the payment for the contracted energy, seeking to reduce prices for consumers -- provides the power plant's right for the winner. The bidder is an investor, for example, a generation company, which aims to maximize benefits of energy sales. When the power plant's nature is complementary, it is possible to provide more benefits to bidders and greater efficiency to the auction if these plants were traded together. Currently, the instituted auction design consists of a hybrid approach -- sequential and simultaneous -- which does not allow the extraction of synergies among plants. This thesis examines two hybrid methods of reverse auctions from the auctioneer's view point. The first model, centralized, consists of two phases: a simultaneous open bid and a combinatorial sealed bid. The simultaneous phase encourages the energy prices revelation. The combinatorial phase allows aggressive bidders to acquire bundles of complementary plants. The centralized model is formulated as an integer and combinatorial optimization problem. The objective function consists of minimizing the payment, that is, energy multiplied by the price (bid) for all plants. The solution strategy identifies the winners solving a restricted set-packing problem. The second method also uses a two phase approach. The first phase is a simultaneous open bid design and the second phase is a decentralized combinatorial design. In this model, the problem difficulty increases gradually. The allocation difficulty is distributed among the bidders; therefore, the auctioneer does not need to solve an optimization problem. The proposed methodologies are applied to new energy auctions on Brazilian electrical energy sector. The results show the use of both methods solving the problem of allocation with an acceptable computational time / Doutorado / Planejamento de Sistemas Energeticos / Doutora em Planejamento de Sistemas Energéticos

Nas últimas décadas, diversas propostas de técnicas e de processos visando aumentar a sustentabilidade da agricultura ganharam evidência. Tais propostas geram novos modelos de planejamento em que devem ser considerados aspectos técnicos e ecológicos de produção, bem como o acesso de pequenos agricultores familiares ao mercado consumidor. Neste tipo de planejamento da produção, a rotação de culturas desempenha um papel fundamental, pois contribui para a manutenção dos recursos produtivos, para a minimização do uso de recursos não-renováveis e para o controle biológico da população de herbívoros, patógenos e plantas espontâneas. Nesta tese abordamos dois problemas de Programação de Rotação de Culturas (PRC) focados na produção de base sustentável de hortaliças: o problema de PRC com restrições de Adjacências (PRC-A) e o problema de PRC com atendimento da Demanda (PRC-D). O planejamento da produção de hortaliças é complexo pois envolve, em geral, um grande número de culturas com limitações específicas quanto à época de plantio e com períodos de cultivo e produtividades muito variáveis. A programação de rotação de culturas para as áreas de plantio é formulada como um modelo de otimização 01 e, para os dois problemas, em cada programação considera se tanto aspectos técnicos (época de plantio e colheita etc.) quanto ecológicos (adubação verde, pousio etc.). No problema PRC-A o objetivo é a maximização da ocupação das áreas produtivas em que as restrições de plantio são estendidas às áreas adjacentes. Como a formulação matemática para o problema tem, em geral, um número muito grande de restrições e variáveis, com matriz de restrições esparsa e bloco-diagonal, o modelo é reformulado com a Decomposição DantzigWolfe, o que permitiu sua resolução por procedimentos baseados em geração de colunas, heurísticos e exatos. No problema PRC-D desejase suprir a demanda de um conjunto de hortaliças tendo-se disponível um conjunto de áreas heterogêneas. As culturas passíveis de plantio, bem como as suas produtividades, dependem da área considerada. O problema foi formulado como um modelo de otimização linear em que cada variável está associada a uma programação de rotação de culturas. O modelo contém potencialmente um número grande de programações de rotação e é resolvido por geração de colunas. Experimentos computacionais usando instâncias baseadas em dados reais confirmam a eficácia dos modelos e das metodologias propostos para os problemas / Over the last decades, various proposals for techniques and processes to increase agricultural sustainability have been put forward. These proposals bring new planning models in which technical and ecological production aspects must be considered, as well as the access of small farmers to the consumer market. In this type of agricultural production planning, crop rotation plays a fundamental role as it contributes to maintaining productive resources, to reducing the use of non-renewable resources, and to biologically controlling the population of herbivores, pathogens and spontaneous plants. In this thesis, two problems concerning the Crop Rotation Schedule (CRS) focusing on sustainable production vegetables are addressed: the problem of the CRS having Adjacent constraints (CRS-A) and the problem of the CRS under Demand constraints (CRS-D). Production planning of vegetables is complex as it generally involves a large number of crop species having specific limitations regarding the planting season and very varied production times and productivity. The crop rotation schedule problem is formulated as an optimization model 0-1, and for both problems, in each schedule technical (planting and harvesting season etc.) and ecological (green manure, fallow etc.) aspects are considered. Concerning the CRS-A problem, the aim is to maximize the occupation of cropping areas in which planting constraints are extended to adjacent areas. As the mathematical formulation for the problem generally has a large number of restrictions and variables and the structure of the constraint matrix of the problem is sparse and block-diagonal, the model has been reformulated using the Dantzig-Wolfe Decomposition strategy, which has enabled the use of a heuristic and exact procedures based on the column generation approach for its resolution. In the CRS-D problem, the aim is to meet the market demands for vegetables having a set of heterogeneous cropping areas available. The potential planting crops, as well as their productivity, depend on the considered cropping area. The problem is formulated as an optimization linear model in which each variable is associated to a crop rotation schedule. The model may include a large number of rotation schedules and is solved by the column generation approach. Computational experiments using instances based on real-world data confirm the efficiency of models and methodologies proposed for the problems

Este trabalho trata de um problema de programação da produção em fundições de pequeno porte, que consiste em programar as ligas que devem ser produzidas em cada período do planejamento e como tais ligas devem ser usadas para a produção de itens sob encomenda, de modo que atrasos e custos operacionais sejam minimizados. Devido à certa incerteza nos dados do problema, a estratégia de horizonte rolante foi empregada. Este problema é representado por um modelo matemático de programação linear inteira mista. Neste trabalho foi desenvolvida uma heurística do tipo residual para obter uma boa solução inteira factível do problema, partindo da solução contínua encontrada pelos métodos relaxe-e-fixe e busca local / This work addresses a planning production problem that arises in small market-driven foundries, which consists of programming a number of alloys that have to be produced in each period of the planning horizon and how these alloys should be used to producing ordered items, in such way that delays and operational costs are minimized. Due to uncertainties in the problem data, the strategy of rolling horizon was used. This problem is modeled as a mixed integer linear programe. In this work we developed a residual typed heuristic in order to obtain a good feasible integer solution of the problem, which are built from the continuous solution found by relax-and-fix and local search methods. Keywords: Lot-sizing problems, mixed integer linear programming, production planning in foundries

Neste trabalho, apresentamos um estudo sobre o problema de dimensionamento de lotes com múltiplas plantas, múltiplos itens e múltiplos períodos. As plantas têm capacidade de produção limitada e a fabricação de cada produto incorre em tempo e custo de preparação de máquina. Nosso objetivo é encontrar um plano de produção que satisfaça a demanda de todos os clientes, considerando que a soma dos custos de produção, de estoque, de transporte e de preparação de máquina seja a menor possível. Este trabalho tem duas contribuições centrais. Primeiramente, propomos a modelagem do problema de dimensionamento de lotes com múltiplas plantas utilizando o conceito de localização de facilidades. Para instâncias de pequena dimensão, os testes computacionais mostraram que a resolução do problema remodelado apresenta, como esperado, resultados melhores que o modelo original. No entanto, seu elevado número de restrições e de variáveis faz com que as instâncias de maiores magnitudes não consigam ser resolvidas. Para trabalhar com instâncias maiores, propomos um método híbrido (math-heurística), que combina o método relax-and-fix, com a restrição de local branching. Testes computacionais mostram que o método proposto apresenta soluções factíveis de boa qualidade para estas instâncias / In this work, we present a study about the multi-plant, multi-item, multi-period lot-sizing problem. The plants have limited capacity, and the production of each item implies in setup times and setup costs. Our objective is to find a production plan which satisfies the demand of every client, considering that the sum of the production, stocking, transport and setup costs is the lowest possible. This work has two main contributions. Firstly, we propose the multi-plant lot-sizing problem modeling using the facility location concept. For small dimension problems, computational tests showed that the remodeled problem resolution presents, as expected, better results than the original model. However, the great number of restrictions and variables make bigger instances to be intractable. To work with the bigger dimension instances, we propose a hybrid method (math-heuristic), which combines the relax-and-fix method and the local branching restriction. Computational tests show that the proposed math-heuristic presents good quality feasible solutions for these instances

O adensamento populacional que as metrópoles vivenciam contribui para reduzir a disponibilidade específica de água, medida em m³/hab.ano. Adicionalmente a este evento, quando o crescimento urbano ocorre de forma não planejada, isso impacta também a qualidade dos mananciais. Esses dois efeitos ocorrem de forma combinada, sobretudo na Região Metropolitana de São Paulo (RMSP). Como consequência observam-se opções de ampliação da capacidade de produção de água potável sucessivamente mais custosas, seja por processos mais caros para o tratamento de um manancial mais poluído, próximo ao centro consumidor, seja pela maior distância de um manancial não poluído, e maiores custos com obras, como ocorre atualmente na implantação do Sistema Produtor São Lourenço (SPSL). Esse processo de encarecimento das opções para ampliação do sistema centralizado de produção de água potável persistirá na RMSP, conforme a população continue a aumentar nas próximas décadas. Existem fontes alternativas com disponibilidade satisfatória, como a água residuária, que quando adequadamente tratadas, podem ser direcionadas para usos que não demandam água potável. Essa possibilidade tem sido aproveitada de forma crescente pelo mercado imobiliário em edifícios, através da instalação de sistemas prediais de água não potável (SPANP), e há diferentes tecnologias disponíveis se consolidando com custos em tendência de queda. Nesse contexto, o objetivo da pesquisa é formular um modelo matemático de tomada de decisão para verificar se a utilização de SPANP são viáveis em relação à implantação do SPSL. Para o desenvolvimento da pesquisa, realizou-se revisão bibliográfica para avaliar as experiências de implantação de SPANP com fonte de águas cinzas em diferentes localidades, bem como para estabelecer a comparação de produção de água potável em macroescala em relação à produção de água não potável em microescala. Foram coletados dados quanto aos custos de construção, operação e manutenção de um SPANP em operação em um edifício na RMSP, e o mesmo para o SPSL. Por meio dos princípios da Programação Inteira, foi formulado um modelo para a indicação de qual opção de sistema apresenta o menor custo total acumulado durante os 20 primeiros anos de operação. Foram simulados cinco cenários com a alteração das principais variáveis que influenciam o comportamento da viabilidade das opções, sendo que as simulações foram realizadas com o uso do software LINDOTM. Em quatro dos cinco cenários simulados, o SPSL foi a opção de menor custo acumulado no 20o ano de operação, indicando a maior probabilidade do mesmo ser a opção de implantação mais econômica no presente. No entanto, devido à tendência de encarecimento das alternativas de ampliação do sistema centralizado de produção de água potável e de redução de custos dos SPANP, essa conclusão não pode ser adotada automaticamente quanto ao próximo sistema centralizado de água potável planejado para ser implantado. / The population agglomeration phenomenon that the metropolises pass through, reduces the water availability measured by the indicator m³/hab.year. Additionally, when urban growth happen in an unplanned way, it also impacts the quality of the water sources. These two effects occur in a combined way, especially in the São Paulo Metropolitan Region (SPMR). As a consequence, the options for expanding the production capacity of drinking water are successively more costly, either by more expensive processes for the treatment of a more polluted source, near the consumer center, or by the larger distance of an unpolluted source, and higer costs with construction, as it is currently happening in the implementation of the São Lourenço Producer System (SLPS). The process that is turning expensive the options for expanding the centralized drinking water system will persist in the SPMR as the population continues to increase in the coming decades. There are alternative sources with satisfactory availability, such as wastewater, which when properly treated, can be directed to uses that do not require potable water. This possibility has been used more and more by the real estate market in buildings, through the installation of non-potable water systems (NPWS), and there are different technologies available in consolidation with falling costs. Thus, the objective of the research is to formulate a mathematical decision making model to verify if the use of NPWS are viable in relation to the implementation of the SLPS. For the development of the research, a bibliographical review was carried out to evaluate the experiences of implementation of NPWS with source of gray water in different localities, as well as to establish the comparison of production of drinking water in macro scale in relation to the production of non-potable water in micro scale. Data were collected on the costs of construction, operation and maintenance of NPWS in a building in the SPMR, and the same for SLPS. Through the principles of Integer Programming, a model was formulated to indicate which system option has the lowest accumulated total cost during the first 20 years of operation. Five scenarios were simulated with the change of the main variables that influence the viability behavior of the options, the simulations were performed using LINDOTM software. In four of the five simulated scenarios, SLPS was the lowest accumulated cost option in the 20th year of operation, indicating that it is more likely to be the most economical deployment option in the present. However, due to the rising cost of alternatives for the expansion of the centralized drinking water production system and the cost reduction of NPWSs, this conclusion cannot be automatically adopted for the next centralized drinking water system planned to be implemented.

Nessa tese consideramos problemas de alocação e precificação de itens, onde temos um conjunto de itens e um conjunto de compradores interessados em tais itens. Nosso objetivo é escolher uma alocação de itens a compradores juntamente com uma precificação para tais itens para maximizar o lucro obtido, considerando o valor máximo que um comprador está disposto a pagar por um determinado item. Em particular, focamos em três problemas: o Problema da Compra Máxima, o Problema da Precificação Livre de Inveja e o Leilão de Anúncios de Segundo Preço. O Problema da Compra Máxima e o Problema da Precificação Livre de Inveja modelam o problema que empresas que vendem produtos ou serviços enfrentam na realidade, onde é necessário escolher corretamente os preços dos produtos ou serviços disponíveis para os clientes para obter um lucro interessante. Já o Leilão de Anúncios de Segundo Preço modela o problema enfrentado por empresas donas de ferramentas de busca que desejam vender espaço para anunciantes nos resultados das buscas dos usuários. Ambas as questões, tanto a precificação de produtos e serviços quanto a alocação de anunciantes em resultados de buscas, são de grande relevância econômica e, portanto, são interessantes de serem atacadas dos pontos de vista teórico e prático. Nosso foco nesse trabalho é considerar algoritmos de aproximação e algoritmos de programação inteira mista para os problemas mencionados, apresentando novos resultados superiores àqueles conhecidos previamente na literatura, bem como determinar a complexidade computacional destes problemas ou de alguns de seus casos particulares de interesse. / In this thesis we consider allocation and pricing problems, where we have a set of items and a set of consumers interested in such items. Our objective is to choose an allocation of items to consumers, considering the maximum value a consumer is willing to pay in a specific item. In particular, we focus in three problems: the Max-Buying Problem, the Envy-Free Pricing Problem and the Second-Price Ad Auction. The Max-Buying Problem and the Envy-Free Pricing Problem model a problem faced in reality by companies that sell products or services, where it is necessary to correctly choose the price of the products or services available to clients in order to obtain an interesting profit. The Second-Price Ad Auction models the problem faced by companies that own search engines and desire to sell space for advertisers in the search results of the users. Both questions, the pricing of items and services and the allocation of advertisers in search results are of great economical relevance and, for this, are interesting to be attacked from a theoretical and a practical perspective. Our focus in this work is to consider approximation algorithms and mixed integer programming algorithms for the aforementioned problems, presenting new results superior than the previously known in the literature, as well as to determine the computational complexity of such problems or some of their interesting particular cases.

O objetivo principal deste trabalho foi criar um modelo matemático para determinar, em nível estratégico, os locais no Brasil mais apropriados à instalação de tanques de álcool combustível (anidro e hidratado) e seus respectivos volumes. O modelo de programação inteira-mista desenvolvido baseou-se na organização do sistema de distribuição de álcool, enfocando sua logística, e considerando questões de oferta, demanda, infra-estrutura de transporte e armazenagem, além de custos de transporte, armazenagem e investimentos em tanques. O modelo foi formulado considerando o horizonte temporal dos meses do ano-safra canavieiro de 2006/2007. Essa formulação reflete as sazonalidades de produção, demanda e estoques do álcool. O modelo de transporte foi enfatizado na minimização dos custos logísticos da cadeia distribuição de álcool combustível dos produtores aos consumidores. Dois cenários e a análise de sensibilidade de suas respostas abordaram a questão estocástica do problema. O primeiro analisou o panorama atual do mercado de álcool, logo não considerou a possibilidade de criação de novos tanques. A idéia desse cenário foi apresentar a consistência da modelagem e ressaltar as condições de infra-estrutura existente de transporte e armazenagem para álcool combustível. Foi feita uma análise de sensibilidade em relação a custos de transporte e restrições de armazenagem para checagem das respostas e para a comparação das práticas atuais de mercado. No segundo cenário, considerou-se a possibilidade de criação de novos tanques procurando identificar os locais mais apropriados para construção dessas estruturas e seu dimensionamento. A análise de sensibilidade em relação a custos de transporte e restrições de armazenagem foi feita para confirmar o potencial de cada localização. Os resultados indicaram a localização inapropriada das bases de distribuição de álcool no país. Destacaram-se também os baixos níveis de fretes de transferência em função das limitações de infraestrutura do sistema de distribuição de álcool. Tanto que as principais localizações de novos tanques disseram respeito a bases no interior da região Centro-Sul, destinos cujos custos de transporte de coleta e entrega são mais competitivos. Em relação aos novos tanques de álcool hidratado houve a indicação das cidades de: Cascavel - PR, Umuarama - PR, Maringá - PR, Lages - SC, Sinop - MT, Limeira - SP e Sorocaba - SP. Para o caso do álcool anidro os novos investimentos sugeridos foram nas cidades de: Londrina - PR, Cascavel - PR, Guarapuava - PR, Lajes - SC, Santa Maria - RS, Araçatuba - SP, Sinop - MT, Vilhena - RO, Montes Claros - MT, Dourados - MS, Gurupi - TO e Teresina - PI. Somado a isso houve a alocação de praticamente todo o custo de armazenagem às usinas. Finalmente, as soluções para a localização de novos investimentos dos tanques de álcool foram todas em regiões de bases de distribuição, já que as usinas estão bem servidas em relação à capacidade de armazenagem. / The main purpose of this research is to develop a mathematical model intended for strategic analysis of the optimal location and considering suitable volumes for storage ethanol (anhydrous and hydrous) tanks. The Mixed Integer Program - MIP model was based on Brazilian ethanol distribution system. The model considered market parameters as supply, demand, and infrastructure parameters on transportation, storage values as well as their expenses. New construction ethanol tanks expenses also were considered. The months along the sugarcane crop year period of 2006/2007 were referred into the modeling formulation. This formulation allows a seasonal storage, production and demand patterns analysis. Transportation model is the main concern in the total logistics cost minimization from producers to consumers. The model stochastic formulation was elaborated by creating two simulated scenarios and developing a sensitivity analysis. The purpose of the first scenario was to check the model consistency and explore the current ethanol transport and storage infrastructure without considering the possibility of new tank installation. Based on these results, a sensitivity analysis regarding transportation expenses and storage restrictions was elaborated in order to make a comparison with current market practices. In the second scenario, it was considered the construction of new ethanol tanks and the identification of the most suitable places bearing in mind volume capacities. Based on these results, a sensitivity analysis regarding transportation expenses and storage restrictions was elaborated in order to check each location consistency. Results indicated that mills are mostly responsible for ethanol (anhydrous and hydrous) storages maintenance types and that the existing geographic organization of terminals and fuel distributors is inappropriate for ethanol distribution in Brazil. Transportation low flows among terminals and fuel distributors also indicated lack of a better infrastructure for ethanol distribution. The model indicated that main location results for installation of new tanks would be located especially in the countryside of the centersouth states, where allocation and distribution of ethanol from mills to the consumer market would be more competitive. In relation to the new hydrous ethanol tanks, the model indicated appropriated locations for the cities of: Cascavel - PR, Umuarama - PR, Maringá - PR, Lages - SC, Sinop - MT, Limeira - SP e Sorocaba - SP. In the other hand, for anhydrous ethanol, new investments suggested in: Londrina - PR, Cascavel - PR, Guarapuava - PR, Lajes - SC, Santa Maria - RS, Araçatuba - SP, Sinop - MT, Vilhena - RO, Montes Claros - MT, Dourados - MS, Gurupi - TO e Teresina - PI. Finally, the model indicated that the best locations for the establishment of new ethanol tanks would be located in fuel distributors\' bases, once results confirmed that mills have enough storage capacity.