Orientador: Hermano Medeiros Ferreira Tavares / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia / Made available in DSpace on 2018-07-15T13:06:39Z (GMT). No. of bitstreams: 1 Souza_CarlosRodriguesde_M.pdf: 2041617 bytes, checksum: daca38d2468e7ace0fd34682817c19ac (MD5) Previous issue date: 1977 / Resumo: Algoritmos de programação linear e de programação linear por partes foram preparados para a aplicação em alguns aspectos do planejamento da expansão dos sistemas de potência e, no que diz respeito a operação desses sistemas, em remanejamento de geração de potência ativa associado, quando neces¬sário, a corte nas demandas (load shedding) ou à utilização da inércia térmica das linhas de transmissão, visando obter um modo de operação satisfatório / Abstract: Upper bounded variables linear programming and piecewise linear programming algorithms have been prepared for application in some system planning aspects and for use in real power generation rescheduling related, if necessary, to load shedding or to the utilization of heat capacity of some transmission lines in order to get to a satisfactory operating condition / Mestrado / Mestre em Engenharia Elétrica

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-09T00:31:09Z (GMT). No. of bitstreams: 1 Vignatti_AndreLuis_M.pdf: 1110014 bytes, checksum: 4a8c19589a3914eb255c6938623be094 (MD5) Previous issue date: 2006 / Resumo: Neste trabalho estudamos a interação entre duas áreas: otimização combinatória e compartilhamento de custos (cost-sharing), que é a arte de dividir os custos associados a construção e manutenção de uma solução a qual um grupo de usuários é beneficiado. Apresentamos algoritmos para problemas de projeto de redes, tendo como objetivo principal os problemas ¿Connected Facility Location¿ e ¿Rent-or-Buy¿. Estes dois problemas são NP-difíceis, pois têm como caso particular o problema da arvore mínima de Steiner, que tambem é NP-dificil. Na primeira parte do trabalho, temos a seguinte questão como motivação: ¿Como projetar uma boa rede, ou seja, uma rede que satisfaça todas as propriedades do problema e ao mesmo tempo minimize o custo de construção desta rede?¿ 'E nesta parte que os algoritmos de aproximação entram em ação. Uma vez que esse custo for determinado, na segunda parte do trabalho, uma outra questão surge: ¿Como dividir esse custo entre todos os usuários que participam da rede de uma maneira ¿justa¿? Nesta parte, usaremos o compartilhamento de custos juntamente com as tecnicas de algoritmos de aproximação para responder a essa questão / Abstract: We consider the interplay of two areas: combinatorial optimization and cost-sharing in network design problems. In the first, we are interested to find a solution with small cost. In the second we would like to share the solution cost between its users. We present algorithms for the problems ¿Connected Facility Location¿ and ¿Rent-or-Buy¿. These two problems are NP-hard, since they have as a particular case the minimum Steiner tree problem, which is a known NP-hard problem. In the first part of this work, we have the following question as motivation: ¿how to design a good network, i.e., one that satisfies all problem requirements and minimize the overall network construction cost?¿ In this part, approximation algorithms takes action. Once this cost is determinated, in the second part of the work, another question arises: ¿How to distribute this cost among all users that participate in the network in a ¿fair¿ way? In this part, we will use cost-sharing together with approximation algorithms techniques to answer this question / Mestrado / Teoria da Computação / Mestre em Ciência da Computação