Orientador: José Mario Martínez Perez / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica. / Made available in DSpace on 2018-08-19T04:47:30Z (GMT). No. of bitstreams: 1 Bueno_LuisFelipeCesardaRocha_D.pdf: 2718304 bytes, checksum: ca1c9aa7730e88989e17a5b89049c2ee (MD5) Previous issue date: 2011 / Resumo: Nesse trabalho serão propostos métodos de Lagrangiano Aumentado para tratar problemas com restrições do tipo LOVO, serão propostos novos métodos de Restauração Inexata e será introduzido o conceito de Equilíbrio Inverso de Nash. Teoremas sobre condições de otimalidade para problemas do tipo LOVO serão apresentados. Um algoritmo do tipo Lagrangiano Aumentado será proposto para abordar esse problema e teoremas de convergência global serão demonstrados. Resultados computacionais serão realizados para uma aplicação em otimização de carteiras em investimentos de grande impacto. Um método híbrido de Restauração Inexata será proposto combinando uma modificação, que usa o Lagrangiano Afiado como função de mérito, do método global de Fischer e Friedlander e o método local de Birgin e Martínez. Teoremas de convergência global e local serão apresentados. Um método de Restauração Inexata para problemas em que as derivadas da função objetivo não estejam disponíveis será introduzido. Nesse método todas as ferramentas da otimização tradicional serão usadas na fase de restauração e uma regularização será feita na fase de otimização. Teoremas de convergência global serão demonstrados e resultados numéricos apresentados. O conceito de Equilíbrio Inverso de Nash será introduzido e um método de Restauração Inexata será proposto para abordar esse problema. Esse método será uma extensão de um novo método de Restauração Inexata para problemas em dois níveis que também será proposto neste trabalho. Exemplos ilustrativos para uma aplicação para o problema de equilíbrio de Arrow-Debreu serão exibidos / Abstract: In this work an Augmented Lagrangian method will be proposed to deal with LOVO constraints, also some new Inexact Restoration methods will be presented and the Inverse Nash Equilibrium concept will be introduced. Theorems about optimality conditions for LOVO-like problems will be presented. Three Augmented Lagrangian algorithms will be proposed to approach this problem and global convergence theorems will be proved. Computational results will be performed for an application in portfolio optimization with impact. A modification of the Fischer-Friedlander global method using the Sharp Lagrangian as a merit function will be proposed. A hybrid Inexact Restoration method combining this modification and the Birgin-Martínez local method will be introduced. Global and local convergence theorems will be presented. An Inexact Restoration method for problems in which the derivatives of the objective function are not available will be introduced. In this method it will be used all the optimization traditional tools in the restoration process as well as a regularization strategy in the optimization phase. Global convergence theorems will be demonstrated and numerical results will be presented. The concept of Inverse Nash Equilibrium will be introduced and an Inexact Restoration method will be proposed to deal with this problem. This method is an extension of a new Inexact Restoration method for bilevel programming that will also be proposed in this work. Some illustrative examples for an application for the Arrow- Debreu equilibrium problem will be given / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientador: Antonio Carlos Moretti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-19T06:41:26Z (GMT). No. of bitstreams: 1 AraujoNeto_JoseEvangelista_M.pdf: 2884766 bytes, checksum: c57ca36e07463336bdf238ea6b35e234 (MD5) Previous issue date: 2011 / Resumo: Uma empresa de energia elétrica tem por obrigação garantir a continuidade e a qualidade do serviço prestado. A fim de incentivar a qualidade do serviço, a ANEEL introduziu penalidades nos contratos com as concessionárias de serviços públicos de transmissão de energia elétrica caso as instalações de transmissão sejam desligadas, por acidente, falha de equipamento ou manutenção programada. Abordagens tradicionais de manutenção em sistemas de transmissão de energia elétrica se baseiam em ações realizadas periodicamente, ou programadas, de acordo com uma análise de necessidades. Embora essas abordagens tenham o objetivo de melhorar o desempenho destes sistemas, geralmente não há uma avaliação precisa do impacto das ações de manutenção na confiabilidade dos mesmos relacionada aos recursos empregados, bem como penalidades legais decorrentes. O objeto assim formulado caracteriza-se como um problema de otimização combinatória com o objetivo de encontrar o encadeamento das ações de manutenções que minimizem os recursos utilizados em manutenções e garanta um nível de confiabilidade desejado para o Sistema Elétrico. Este trabalho propõe uma abordagem para enfrentar este problema baseada na relação confiabilidade/custo com a perspectiva de encontrar as melhores estratégias para a realização de manutenções em equipamentos (ativos) de transmissão de energia elétrica, apresentando um modelo matemático para a confecção de um calendário viável (que respeite às restrições do Sistema Elétrico) para programação de manutenção nestes ativos e metodologia de otimização para encontrar as melhores soluções em um determinado horizonte de planejamento / Abstract: A eletric power company is required to ensure continuity and quality of the provided service. To promote the quality of service, ANEEL introduced penalties in contracts with the electric power companies if transmission facilities are turned off by accident, equipment failure or programmed maintenance. Traditional approaches to maintenance of electric energy transmission systems are based on actions performed periodically, or programmed, in agreement with an analysis of needs. Although these approaches have the goal of improving the performance of these systems, generally there is not an accurate assessment of the impact of maintenance actions on the reliability of those actions related to the employed resources, as well as current legal penalties. The object thus formulated is characterized as a combinatorial optimization problem with the objective to find the sequence of maintenance actions that minimize the resources used in maintenance, ensuring a level of reliability desired for the Electric System. This work proposes an approach to address this problem based on the relationship reliability/ cost with the prospect of finding the best strategies for performing maintenance on equipment (assets) of electricity transmission, presenting a mathematical model for finding a feasible schedule (which respects the constraints of the Electric System) maintenance programming for these assets and optimization methodology to find the best solutions in a given planning horizon / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

The purpose of this dissertation was to create a safety compliance model which would advance the state of the art of safety compliance models and provide management with a practical tool which can be used in making safety decisions in an environment where multiple objectives exist. A goal programming safety compliance model (OSHA Model) was developed to fulfill this purpose. The objective function of the OSHA Model was designed to minimize the total deviation from the established goals of the model. These model goals were expressed in terms of 1) level of compliance to OSHA safety and health regulations, 2) company accident frequency rate, 3) company accident cost per worker, and 4) a company budgetary restriction. This particular set of goals was selected to facilitate management's fulfillment of its responsibilities to OSHA, the employees, and to ownership. This study concludes that all the research objectives have been accomplished. The OSHA Model formulated not only advances the state of the art of safety compliance models, but also provides a practical tool which facilitates management's safety and health decisions. The insight into the relationships existing in a safety compliance decision system provided by the OSHA Model and its accompanying sensitivity analysis was demonstrated by the empirical application during the research. The optimal solution values showed what could be accomplished with a given objective structure and the existing safety and health functional relationships. The optimal solution values obtained during the sensitivity analysis showed how sensitive the model is to the uncertainties relating to goal structures and the specific exogenous and endogenous parameter values. This new insight available to management can provide a scientific base upon which the total system decisions can be made.

CAPES; ANP / Este trabalho apresenta o desenvolvimento de estruturas de otimização para auxílio na tomada de decisão de atividades de planejamento e scheduling em dutos. Dois problemas são estudados: (i) O primeiro sistema envolve um duto que interliga uma refinaria até um parque de tancagem operando o transporte de diversos produtos. Visto que a resolução de todo o problema em um único modelo de otimização tornou-se inviável devido a complexidade computacional, uma abordagem de solução alternativa é proposta para a obtenção do scheduling do duto, utilizando apenas modelos PLIM (Programação Linear Inteira Mista). O primeiro modelo proposto obtém a sequência de envio dos produtos e seus respectivos volumes. Fixando-se essas variáveis, o segundo modelo PLIM, já presente na literatura, é capaz de obter o scheduling final do duto em poucos segundos. Além disso, a qualidade da solução obtida através do sequenciamento PLIM mostrou-se superior ao sequenciamento heurístico previamente apresentado na literatura; (ii) O segundo sistema é composto por uma rede com 30 dutos que interliga diversas áreas incluindo 4 refinarias, 2 terminais portuários, 2 clientes finais e 6 terminais de distribuição que recebem ou enviam diversos produtos derivados de petróleo. A rede em estudo possui características particulares que devem ser tratadas como, por exemplo, restrições locais, pulmão, reversão de fluxo, horossazonalidade e troca de turno dos operadores. Além disso, os dutos são compartilhados por diferentes produtos que utilizam rotas distintas. Dessa forma, paradas de bombeio devem ser avaliadas. Considerando-se que a complexidade da rede de dutos é sensivelmente maior que a realização do scheduling de um único duto, a decomposição desse problema se torna imprescindível. Detalhes do scheduling da rede devem ser obtidos, incluindo sequência de bombeamento em cada nó, volume das bateladas, restrições de tancagem e distribuição no tempo, sempre respeitando uma série de restrições operacionais. Dessa forma, a carga computacional para a determinação de um scheduling de curto prazo (short-term scheduling) com o cenário considerado é relevante. São propostos três modelos PLIM para esse problema: modelo de planejamento, modelo de alocação e sequenciamento e, finalmente, o modelo de temporização. A saída de um modelo PLIM é utilizada como entrada para outras estruturas e/ou modelos PLIM que são utilizados de forma hierárquica para a obtenção da solução desejada. Muitas análises foram realizadas por intermédio das soluções obtidas, que são apresentadas em tempo computacionalmente reduzido para cenários da indústria petrolífera. / This work addresses the problem of developing optimization structurres to aid the operational decision-making of planning and scheduling activities in real-world pipelines. Two problems are studed: (i) The first one contemplates a pipeline connecting a refinery and a depot. The pipeline transports various products. An alternative solution approach is proposed to obtain the pipeline scheduling, using only MILP (Mixed Integer Linear Programming) models. Since the resolution of the entire problem in a unique optimization model became too hard due to the high computational complexity, the problem decomposition is developed. The first proposed model provides the punping product-sequence and its volume, respectively. Fixing these variables, the MILP model is able to obtain the final scheduling of the pipeline in few seconds. The quality of the solution obtained by the MILP sequencing model is better than a previous heuristic sequencing published. (ii) The second system is composed by a network with 30 pipelins that connect different areas including 4 refineries, 2 harbors, 2 final clients, and 6 distribution terminals. They receive or send many oil derivatives. The studied pipeline network has particular features to be processed as, for instance, local constraints, surge tank operation, flow reverse operational, seasonal costs, and work shifts. Also, the pipelines are shared by different products that use different routes. In this way, pumping stoppages should be evaluated. Considering that the pipeline network complexity is higher than the unique pipeline scheduling procedure, the problem decomposition becomes essential. Scheduling details must be given, including pumping sequence in each node, volume of batches, tankage constraints and timing issues, while always respecting a series of operational constraints. Moreover, the computacional burden to determine a a short-term scheduling for the considered scenario is a difficult task. Three MILP models are proposed to address this problem: planning model, allocation and sequencing model and,finally, the timing model. The output of a model is used as input to other structures and/or MILP models. These models are managed in a hierarchical manner to obtain the desired solution. Many insights have been derived from the obtained solutions, which are given in a reduced computational time for oil industrial-size scenarios.

CAPES; ANP / Este trabalho apresenta o desenvolvimento de estruturas de otimização para auxílio na tomada de decisão de atividades de planejamento e scheduling em dutos. Dois problemas são estudados: (i) O primeiro sistema envolve um duto que interliga uma refinaria até um parque de tancagem operando o transporte de diversos produtos. Visto que a resolução de todo o problema em um único modelo de otimização tornou-se inviável devido a complexidade computacional, uma abordagem de solução alternativa é proposta para a obtenção do scheduling do duto, utilizando apenas modelos PLIM (Programação Linear Inteira Mista). O primeiro modelo proposto obtém a sequência de envio dos produtos e seus respectivos volumes. Fixando-se essas variáveis, o segundo modelo PLIM, já presente na literatura, é capaz de obter o scheduling final do duto em poucos segundos. Além disso, a qualidade da solução obtida através do sequenciamento PLIM mostrou-se superior ao sequenciamento heurístico previamente apresentado na literatura; (ii) O segundo sistema é composto por uma rede com 30 dutos que interliga diversas áreas incluindo 4 refinarias, 2 terminais portuários, 2 clientes finais e 6 terminais de distribuição que recebem ou enviam diversos produtos derivados de petróleo. A rede em estudo possui características particulares que devem ser tratadas como, por exemplo, restrições locais, pulmão, reversão de fluxo, horossazonalidade e troca de turno dos operadores. Além disso, os dutos são compartilhados por diferentes produtos que utilizam rotas distintas. Dessa forma, paradas de bombeio devem ser avaliadas. Considerando-se que a complexidade da rede de dutos é sensivelmente maior que a realização do scheduling de um único duto, a decomposição desse problema se torna imprescindível. Detalhes do scheduling da rede devem ser obtidos, incluindo sequência de bombeamento em cada nó, volume das bateladas, restrições de tancagem e distribuição no tempo, sempre respeitando uma série de restrições operacionais. Dessa forma, a carga computacional para a determinação de um scheduling de curto prazo (short-term scheduling) com o cenário considerado é relevante. São propostos três modelos PLIM para esse problema: modelo de planejamento, modelo de alocação e sequenciamento e, finalmente, o modelo de temporização. A saída de um modelo PLIM é utilizada como entrada para outras estruturas e/ou modelos PLIM que são utilizados de forma hierárquica para a obtenção da solução desejada. Muitas análises foram realizadas por intermédio das soluções obtidas, que são apresentadas em tempo computacionalmente reduzido para cenários da indústria petrolífera. / This work addresses the problem of developing optimization structurres to aid the operational decision-making of planning and scheduling activities in real-world pipelines. Two problems are studed: (i) The first one contemplates a pipeline connecting a refinery and a depot. The pipeline transports various products. An alternative solution approach is proposed to obtain the pipeline scheduling, using only MILP (Mixed Integer Linear Programming) models. Since the resolution of the entire problem in a unique optimization model became too hard due to the high computational complexity, the problem decomposition is developed. The first proposed model provides the punping product-sequence and its volume, respectively. Fixing these variables, the MILP model is able to obtain the final scheduling of the pipeline in few seconds. The quality of the solution obtained by the MILP sequencing model is better than a previous heuristic sequencing published. (ii) The second system is composed by a network with 30 pipelins that connect different areas including 4 refineries, 2 harbors, 2 final clients, and 6 distribution terminals. They receive or send many oil derivatives. The studied pipeline network has particular features to be processed as, for instance, local constraints, surge tank operation, flow reverse operational, seasonal costs, and work shifts. Also, the pipelines are shared by different products that use different routes. In this way, pumping stoppages should be evaluated. Considering that the pipeline network complexity is higher than the unique pipeline scheduling procedure, the problem decomposition becomes essential. Scheduling details must be given, including pumping sequence in each node, volume of batches, tankage constraints and timing issues, while always respecting a series of operational constraints. Moreover, the computacional burden to determine a a short-term scheduling for the considered scenario is a difficult task. Three MILP models are proposed to address this problem: planning model, allocation and sequencing model and,finally, the timing model. The output of a model is used as input to other structures and/or MILP models. These models are managed in a hierarchical manner to obtain the desired solution. Many insights have been derived from the obtained solutions, which are given in a reduced computational time for oil industrial-size scenarios.

There are many real cases where a company needs to determine the price of its products so as to maximise its revenue or profit.<p>To do so, the company must consider customers' reactions to these prices, as they may refuse to buy a given product or service if its price is too high. This is commonly known in literature as a pricing problem.<p>This class of problems, which is typically bilevel, was first studied in the 1990s and is NP-hard, although polynomial algorithms do exist for some particular cases. Many questions are still open on this subject.<p><p>The aim of this thesis is to investigate mathematical properties of pricing problems, in order to find structural properties, formulations and solution methods that are as efficient as possible. In particular, we focus our attention on pricing problems over a network. In this framework, an authority owns a subset of arcs and imposes tolls on them, in an attempt to maximise his/her revenue, while users travel on the network, seeking for their minimum cost path.<p><p>First, we provide a detailed review of the state of the art on bilevel pricing problems. <p>Then, we consider a particular case where the authority is using an unit toll scheme on his/her subset of arcs, imposing either the same toll on all of them, or a toll proportional to a given parameter particular to each arc (for instance a per kilometre toll). We show that if tolls are all equal then the complexity of the problem is polynomial, whereas in case of proportional tolls it is pseudo-polynomial.<p>We then address a robust approach taking into account uncertainty on parameters. We solve some polynomial cases of the pricing problem where uncertainty is considered using an interval representation.<p><p>Finally, we focus on another particular case where toll arcs are connected such that they constitute a path, as occurs on highways. We develop a Dantzig-Wolfe reformulation and present a Branch-and-Cut-and-Price algorithm to solve it. Several improvements are proposed, both for the column generation algorithm used to solve the linear relaxation and for the branching part used to find integer solutions. Numerical results are also presented to highlight the efficiency of the proposed strategies. This problem is proved to be APX-hard and a theoretical comparison between our model and another one from the literature is carried out. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished