Orientador: João Carlos Setubal / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-26T12:21:55Z (GMT). No. of bitstreams: 1 AbreuJunior_LidioNunesde_M.pdf: 9384178 bytes, checksum: ab1f02d1d27d732c311ae88caa13f5d9 (MD5) Previous issue date: 2000 / Resumo: O assunto principal desta tese é o problema da designação: dado um grafo bipartido com custos nas arestas, obter um emparelhamento perfeito de custo mínimo. Na primeira parte do trabalho apresentamos uma revisão detalhada dos conceitos e principais resultados da literatura sobre esse problema. Na segunda parte, discutimos uma variante paramétrica, na qual cada aresta e tem seu custo dado por uma expressão do tipo ce° + ?ce?, onde ce° e ce? são constantes e ? é o parâmetro, cujo valor é real e varia. Nesta variante o objetivo é obter todas as soluções do problema para um intervalo de valores de A no menor tempo possível. Nesta parte inicialmente fazemos uma revisão de resultados da literatura que apresentam técnicas gerais para a resolução de problemas paramétricos em Otimização Combinatória. Em seguida apresentamos uma abordagem, também da literatura, específica para o problema do fluxo de custo mínimo, do qual o problema da designação é um caso especial. Esta abordagem se baseia em propriedades do algoritmo simplex de rede. Em seguida apresentamos uma nova abordagem, baseada numa relação entre o problema do fluxo de custo mínimo e o problema do ciclo de razão mínima. A complexidade desta nova abordagem é insatisfatória quando se quer resolver uma instância do problema da designação paramétrico, pois a complexidade conhecida do problema do ciclo de razão mínima é maior do que a complexidade conhecida do problema da designação. Esta nova abordagem entretanto é satisfatória do ponto de vista teórico quando aplicada ao problema do fluxo de custo mínimo paramétrico. O trabalho finaliza apresentando uma comparação experimental entre as abordagens "simplex de rede" e "ciclo de razão mínima" para o problema do fluxo mínimo paramétrico, mostrando que a primeira é muito superior à segunda. / Abstract: This dissertation is about the Assignment Problem: given an edge-weighted bipartite graph, find a perfect matching of minimum weight. In the first part of this work we present a detailed survey of the literature on this problem, including basic concepts and main results. In the second part, we discuss a parametric variant of this problem. In this variant, the weight of each edge e is given tipo ce° + ?ce?, where ce° e ce? are constants and ? is the parameter, that is, a real value that can vary. For a given range of A values we want to find all solutions to the corresponding assignment problems in the least possible time. In this part of the work we initially present a survey of techniques for solving general Combinatorial Optimization parametric problems. We then present a technique, also from the literature, for solving the parametric minimum cost flow problem, of which the assignment problem is a special case. This technique is based on the network simplex algorithm. We then present a new technique, also for solving the parametric minumum cost flow problem, based on a reduction to the minimum cost-to-time ratio cycle problem. This technique is not satisfactory for solving parametric assignment problems, because the best known algorithm for the minimum cost-to-time ratio cycle problem has worst running time than the best algorithm known for the assignment problem. It is however satisfactory from a theoretical point of view when applied to parametric minimum cost flow problems, because its running time is better than the best known running time for a certain class of inputs. We made an experimental comparison between the "network simplex" approach and the "minimum ratio cycle approach", but found that in all cases the "network simplex" approach has faster running times. / Mestrado / 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-07-28T16:47:57Z (GMT). No. of bitstreams: 1 Pereira_RicardoScachetti_M.pdf: 6018166 bytes, checksum: 5c2b8981fcc29db690171dfbebf048ec (MD5) Previous issue date: 1999 / Resumo: Neste trabalho são estudados dois problemas combinatórios que ocorrem ao utilizar uma abordagem hierárquica para definir a estratégia a ser adotada na logística de distribuição de revistas. Tipicamente, a primeira fase da logística envolve a definição da região geográfica que será alocada a cada entregador. O problema de definir estas regiões é denominado problema do distritamento (PD). Na segunda fase da logística, para cada região de entrega, é preciso encontrar uma rota que minimize a distância percorrida pelo entregador. Esta rota deve satisfazer tanto a restrição de capacidade de carga do entregador quanto as restrições de fluxo de revistas, considerando-se as demandas dos pontos de entrega e o estoque nos depósitos. O problema combinatório referente a esta fase é denominado o problema da entrega de revistas (PE). Neste trabalho propõe-se algoritmos heurísticos para ambos os problemas acima, que são modelados por meio de grafos. Para o problema da entrega de revistas é proposto ainda um algoritmo exato do tipo branck-and-cut. Este algoritmo está baseado em uma formulação de Programação Linear Inteira e em desigualdades válidas fortes adaptadas dos problemas de roteamento de veículos e de fluxo em redes com custos fixos. Além disso, propõe-se um Sistema Espacial de Apoio à Decisão (SEAD) baseado em um Sistema de Informação Geográfica (SIG) para a Logística de Distribuição de revistas que pressupõe a integração das soluções dos problemas do distritamento e da entrega. Todos algoritmos propostos são implementados e testados para um amplo conjunto de instâncias. Um protótipo do SEAD proposto é implementado através da integração das heurísticas ao SIG ArcView / Abstract: In this work we study two combinatorial problems that arise when a hierarchical approach is used to define the strategy to be adopted in the logistics of magazine distribution. Typically, the first phase of the logistics involves the definition of the geographical region to be assigned to each deliverman. The problem of defining such regions is called the district determination problem. In the second phase of the logistics, to each deliver region, we have to find a route that minimizes the distance traversed by the deliverman. This route must satisfy both the deliverman capacity and the magazine flow constraints, given the demands in the delivery points and the stocks in the depots. The combinatorial problem related to this phase is called the magazine delivery problem. In this work we propose heuristic algorithms for both problems above, which are modeled with graphs. For the the magazine delivery problem we also propose an exact branch-and-cut algorithm. This algorithm is based on an Integer Programming formulation and on strong valid inequalities adapted from the vehicle routing and fixed-charge network problems. Besides, we propose a Spatial Decision Support System (SDSS) based on a Geographical Information System (GIS) for the logistics of magazine distribution that assumes the integration of the solutions of the district determination and magazine delivery problems. All the algorithms proposed are implemented and tested over a wide set of instances. A prototype of the proposed SDSS is implemented via the integration of the heuristics to the GIS ArcView / Mestrado / Mestre em Ciência da Computação

Orientador: Helia Harumi Sato / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia de Alimentos / Made available in DSpace on 2018-08-03T21:41:18Z (GMT). No. of bitstreams: 1 Orsi_DanielaCastilho_M.pdf: 1528781 bytes, checksum: 9b24bf02927103be3fb307e39fe0a720 (MD5) Previous issue date: 2004 / Mestrado

Orientadores: Carlos Magnus Carlson Filho, Raul Vinhas Ribeiro / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-25T03:01:30Z (GMT). No. of bitstreams: 1 Sousa_MarcosAntoniode_M.pdf: 7406644 bytes, checksum: 11c6a42328bae68010cead9c0ed378eb (MD5) Previous issue date: 1999 / Resumo: Novas tecnologias, aliadas ao processo de desregulamentação e competição de mercado, vêm impondo mudanças substanciais, a um ritmo muito rápido, ao tradicional sistema de telecomunicações, e em particular à rede de acesso, segmento responsável pela comunicação entre o usuário (denominado assinante) e a sua estação telefônica. A busca de uma plataforma capaz de disponibilizar serviços diversificados e lucrativos é uma tendência a ser seguida pelas empresas operadoras do setor. A variedade de cenários possíveis e os valores fmanceiros envolvidos exigem que os planejadores disponham de ferramentas ao mesmo tempo abrangentes e flexíveis. Diante desta atual conjuntura, propõe-se neste trabalho uma metodologia de planejamento orientada à maximização de receita, descrevendo-se os procedimentos necessários a serem realizados pelo planejador para efetuar os estudos de evolução da rede para um ambiente multi-serviço. Para este fIm, modelos matemáticos de otimização que tratam da etapa de dimensionamento de equipamentos também são propostos. Especificamente, são apresentados modelos de programação linear inteira mista que tratam a expansão da rede como um problema de otimização de fluxo em rede com restrições adicionais e variáveis binárias. Como característica marcante, a metodologia permite um alto grau de interação com o planejador, flexibilidade que possibilita analisar variados aspectos do compromisso entre serviço e tecnologia, receita e custo. Resultados numéricos, fundamentados em dados reais, são apresentados e discutidos...Observação: O resumo, na íntegra, poderá ser visualizado no texto completo da tese digital / Abstract: New technologies, besides the market deregulation and competitiveness, are changing Telecommunications in a fast-paced way. The Access Network, which connects users (subscribers) to their Central Oíflces, is one of the most affected parts of the system. Operating companies now look for a network structure which is able to provide several profItable services. The diversity of evolution settings and the large fmancial amount impose the need of flexible, comprehensive decision-support tools. This work proposes a revenue-oriented planning methodology and describes ways of studying the Access Network growth in a multi-service environment. Optimization mathematical models for equipment allocation and sizing are also presented for some technologies. The mixed linear-type models deal with the planning problem as a network flow problem with additional constraints and binary decision variables. As a remarkable feature, the interactiveness of the methodology allows analyses of services, technologies, and costj revenue tradeofIs. An application to an actual network is reported...Note: The complete abstract is available with the full electronic digital thesis or dissertations / Mestrado / Mestre em Engenharia Elétrica

Orientador: Hermano Medeiros Ferreira Tavares / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia de Campinas / Made available in DSpace on 2018-07-14T10:14:41Z (GMT). No. of bitstreams: 1 Fernandes_JurandirFernandoRibeiro_M.pdf: 1417230 bytes, checksum: 224752d7b734e31e1e123b2ba4ad9a84 (MD5) Previous issue date: 1974 / Resumo: Trata o presente trabalho do desenvolvimento de algorítmos que aplicados aos modelos de otimização COSE I e COSE II reduzem a interferência do operador. tanto no fornecimento como no manuseio de dados envolvidos naqueles modelos. Faz-se também uma contribuição de carater de otimização, anexada ao algorítmo do COSE II. Algumas sugestões para futuros trabalhos também são feitas. / Abstract: Not informed. / Mestrado / Mestre em Ciências

Orientador : Clovis Perin Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-15T00:29:53Z (GMT). No. of bitstreams: 1 Lombardo_DeniseHelena_M.pdf: 1993606 bytes, checksum: ed3e7afb38488684a314e43b42a8e549 (MD5) Previous issue date: 1986 / Resumo: Esta dissertação envolve o estudo de dois problemas de otimização combinatória: O Problema do Caixeiro Viajante (PCV) e o Problema do Carteiro Chinês (PCC). Dada uma rede (ou grafo), primeiro problema consiste em determinar uma rota circular mínima que passa em cada nó e o segundo em determinar uma rota circular mínima que passa em cada linha da rede. Embora ambos problemas sejam da classe NP-"árduo" (NP- hard ), o problema do Carteiro Chinês é apresentado na literatura como um problema menos "difícil" de ser resolvido. O interesse em estudar o PCV e o PCC partiu do grande numero de publicações em revistas e livros técnicos de Pesquisa Operacional a respeito destes problemas. Além disto, estes problemas são de importância no estudo da determinação de rotas de veículos onde se procura obter rotas que devem ser utilizadas por uma frota de veículos para satisfazer determinadas demandas (ou restrições) tanto nos nós quanto nas linhas; por exemplo, coleta de lixo de n cidades / Abstract: Not informed / Mestrado / Mestre em Matemática Aplicada

Orientador : Jose Norberto W. Dachs / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-14T23:23:17Z (GMT). No. of bitstreams: 1 Montalvao_Walmir_M.pdf: 2820737 bytes, checksum: b72ec69f13e72e9ae031b451b00fe2d0 (MD5) Previous issue date: 1978 / Resumo: Este trabalho tem como finalidade: 1) Revisão da Literatura sobre Operação Evolutiva (OPEV), uma técnica de Otimização Experimental. 2) Descrição da técnica numa forma didática. A técnica é pouco empregada no Brasil e o texto poderia servir de roteiro para difusão da mesma. 3) Uma aplicação prática onde os conceitos assimilados pudessem ser empregados. 4) Simulação de um processo para treinamento de pessoas durante um curso. Isso sanaria a dificuldade de treinamento no próprio processo. No Capítulo 1 é dada uma idéia de sistemas e modelos. Depois é caracterizada a técnica OPEV como uma Otimização Experimental. No Capítulo 2 são apresentados os princípios estatísticos necessários à OPEV. Nos Capítulos 3 e 4 sao detalhados os procedimentos OPEV para delineamentos fatoriais 2² e 2³. No Capítulo 5 é apresentado um exemplo de aplicação da da OPEV na Otimização de uma Centrífuga. No Capítulo 6 é proposto o jogo da OPEV. No apêndice 1 estão contidos alguns comentários e indicações sobre uma referência bibliográfica mais completa. No apêndice 2 aparece o manual de uso do programa que realiza o jogo / Abstract: The scope of this work is: 1) To review the literature on, Evolutionary Operation, an experimental optimization technique. 2) To describe the technique in a didatical way as it is of little use in Brazil and the text could become a mean of spreading, its use. 3) A practical application in witch the EVOP technique is used. 4) Simulation of a process for personel training in an EVOP course. this would avoid problems of training in the physical process itself. In the 1st chapter an idea of systerms and models is presented and then EVOP is introduced as an experimental optimization technique. In the 2nd chapter the statistica principles on which EVOP is based are presented. In the 3rd and 4th chapters the EVOP procedure is detailed for 2² and 2³ factorial designs. In the 5th chapter an application is made using EVOP in the optimization of a centrifugal pump. The 6th chapter is the EVOP game. The 1st Appendix contains cornrnents on the bibliography. The 2nd Appendix is a manual of the EVOP game program / Mestrado / Mestre em Matemática Aplicada

Orientador : Jose Antonio Cordeiro / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-16T18:43:01Z (GMT). No. of bitstreams: 1 Moraes_AiporeRodriguesde_M.pdf: 2008378 bytes, checksum: 0519b492fb644a0372a4023ab123ace4 (MD5) Previous issue date: 1987 / Resumo: Não informado / Abstract: Not informed / Mestrado / Mestre em Estatística

Made available in DSpace on 2014-06-12T17:41:01Z (GMT). No. of bitstreams: 2 arquivo7681_1.pdf: 6929267 bytes, checksum: 5ccc4db7998ef087e9b54b77aed9cb70 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2004 / Modificações no cenário do setor elétrico brasileiro têm incentivado novos estudos em geração distribuída. Com a ocorrência de uma maior oferta de combustível, proporcionada por medidas estratégicas do governo, diversos grupos de pesquisa se focam no estudo da cogeração de energia usando este combustível. Estes fatos incentivaram a criação do projeto COGENCASA que consiste no estudo de uma planta de microcogeração para uso residencial instalada na UFPE. Os componentes da planta são uma microturbina, um grupogerador, um chiller de compressão, um chiller de absorção, um termoacumulador de água quente, um termoacumulador de água fria e uma câmara climatizada. Este projeto tem a intenção de realizar estudos comparativos das performances dos equipamentos e de realizar a otimização financeira da planta através de um modelo criado em Matlab e Simulink. O projeto COGENCASA é apenas descrito neste trabalho por ter motivado a criação do modelo para a realização da otimização financeira da planta. A modelagem dos equipamentos e os principais componentes do modelo são explanados neste trabalho. A otimização é realizada sobre a forma de operação dos equipamentos de acordo com um módulo de configuração de tarefas que possibilita uma estratégia de utilização dos equipamentos para atender demandas térmicas e elétricas variáveis, ou seja, o modelo realiza simulações dinâmicas. Este módulo é um dispositivo que recebe as demandas e as características dos equipamentos e, através de chaves, determinam a forma de funcionamento dos equipamentos. Neste trabalho são realizados estudos de casos de simulação e de otimização. Ocorre a simulação com a variação das chaves e também de condições alheias à de projeto. É realizada a otimização de um grupo de chaves a fim de obter a melhor máquina térmica para a planta e é realizada a otimização sobre a máquina térmica ótima obtida com condições alheias à de projeto. Diversas análises são realizadas através das performances dos equipamentos e dos valores presentes llíquidos. Cenários são criados de acordo com as condições financeiras de aquisição de alguns equipamentos que podem ser modificadas no futuro próximo. Também são estudadas situações para decisão de investimento entre o sistema de cogeração e o sistema convencional. O módulo de configuração de tarefas usa 27 chaves (26 binárias e 1 com 5 posições) para determinar o comportamento do sistema. Desta forma é possível gerar 335544320 (2^26)*5) modos de operação. Com o método de otimização usado, busca exaustiva, o ponto ótimo seria encontrado após muitos anos de simulação (caso cada simulação durasse 10 segundos). Uma das intenções dos estudos de casos é avaliar se existem chaves que tenham predominância sobre as outras na obtenção do Valor Presente Líquido ótimo. A ocorrência deste fato possibilita a criação de um mapa com as chaves mais relevantes e a sua implementação no modelo poderá reduzir drasticamente o tempo de execução

Orientador: Ana Friedlander / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-03T21:43:04Z (GMT). No. of bitstreams: 1 Castro_SuzanaLimadeCampos_D.pdf: 670086 bytes, checksum: 39482c058bfedab0f6014a5cec07211f (MD5) Previous issue date: 2004 / Doutorado / Doutor em Matemática Aplicada