No description available.

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

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 : 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

Dissertação apresentada para obtenção do grau de Doutor em Matemática Aplicada, na Universidade do Porto

ALVES, Vanderli de Araújo. Sobre o princípio fundamental da contagem. 2015. 77 f. Dissertação (Mestrado em Matemática em Rede Nacional) – Centro de Ciências, Universidade Federal do Ceará, Juazeiro do Norte, 2015. / Submitted by Erivan Almeida (eneiro@bol.com.br) on 2015-12-15T13:31:19Z No. of bitstreams: 1 2015_dis_vaalves.pdf: 1280752 bytes, checksum: 91a26a85badc862df920dacbee5f17f9 (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2015-12-15T13:37:37Z (GMT) No. of bitstreams: 1 2015_dis_vaalves.pdf: 1280752 bytes, checksum: 91a26a85badc862df920dacbee5f17f9 (MD5) / Made available in DSpace on 2015-12-15T13:37:37Z (GMT). No. of bitstreams: 1 2015_dis_vaalves.pdf: 1280752 bytes, checksum: 91a26a85badc862df920dacbee5f17f9 (MD5) Previous issue date: 2015 / We presented The Fundamental Principle Count (PFC) as a consequence of the Principle Finite Induction (PIF) and as the application (PFC), we presented the resolution of various problems involving count, arrangements, combinations and permutations. The main objective of this work is to present the logical-mathematical reasoning that involves counting notion avoiding to give the leadership that is customarily given to mathematical formulas. To this end, we solve various problems without using mathematical formulas, giving priority to direct application of the PFC. / Neste trabalho apresentamos o Princípio Fundamental da Contagem (PFC) como uma consequência do Princípio de Indução Finita (PIF) e, como aplicação do (PFC), apresentamos a solução de vários problemas envolvendo contagem, arranjos, permutações e combinações. O principal objetivo do trabalho é apresentar o raciocínio lógico-matemático que envolve a noção de contagem evitando dar o protagonismo que costumeiramente é dado as fórmulas matemáticas no ensino básico. Neste intuito, resolvemos vários problemas sem fazer uso de fórmulas matemáticas, priorizando a aplicação direta do PFC.

SILVA,Carina Brunehilde Pinto da. Análise combinatória : concentrando o ensino na resolução de problemas. 2013. 52 f. Dissertação (Mestrado em Matemática em Rede Nacional) – Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2013. / Submitted by Rocilda Sales (rocilda@ufc.br) on 2013-07-09T15:40:29Z No. of bitstreams: 1 2013_dis_cbpdasilva.pdf: 940945 bytes, checksum: a51608721c6a795b759e56a9c7458ffc (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2013-07-09T15:41:17Z (GMT) No. of bitstreams: 1 2013_dis_cbpdasilva.pdf: 940945 bytes, checksum: a51608721c6a795b759e56a9c7458ffc (MD5) / Made available in DSpace on 2013-07-09T15:41:17Z (GMT). No. of bitstreams: 1 2013_dis_cbpdasilva.pdf: 940945 bytes, checksum: a51608721c6a795b759e56a9c7458ffc (MD5) Previous issue date: 2013 / The Combinatory Analysis is the technical set used to solve counting problems. It's useful when is necessary to know how much elements are in a set finite, without the need to list each one. In this work, let's discuss the way in which this important matter is taught to high school students, and give suggestions to make it better. At the end, is suggested an educational software, of our own authorship, which is able to solve counting problems. It was developed to help and to stimulate the teacher performance during the classes. / A Análise Combinatória é o conjunto de técnicas para a resolução de problemas de contagem. É usada quando é preciso conhecer a quantidade de elementos de um conjunto finito, sem necessidade de elencar cada um. Neste trabalho, discute-se a maneira como este assunto tão importante é apresentado para os alunos que cursam o Ensino Médio, a fim de aprimorá-la. Ao final do trabalho, é sugerido um software educacional, de própria autoria, capaz de resolver problemas de contagem, com a finalidade de auxiliar e dinamizar o desempenho do professor em sala de aula.

Orientador: Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-21T02:04:11Z (GMT). No. of bitstreams: 1 Bussamra_NeusaMaria_M.pdf: 7956815 bytes, checksum: 30f982df17de113ac832a5c2c381886d (MD5) Previous issue date: 1995 / Resumo: Nos países onde os sistemas de eleição de representantes seguem o modelo distrital, a topografia dos distritos políticos eleitorais é de fundamental importância pois a sua manipulação pode vir a favorecer alguns partidos políticos em detrimento de outros. Na tentativa de combater esta prática, estes países delegam a tarefa de estabelecer distritos eleitorais a comissões neutras, multipartidárias, que desde os anos 60 vêm envolvendo especialistas em pesquisa operacional em seus trabalhos. Esta tese revisa os principais métodos encontrados na literatura para a resolução do problema do distritamento eleitoral que é, do ponto de vista matemático, um problema complexo de otimização combinatórial. É apresentada uma nova metodologia de solução do problema baseada em técnicas heurísticas, bem como os resultados de sua aplicação à cidade de Campinas / Abstract: This thesis revises the most important methods proposed to solve the political districting problem, a hard combinatorial optimization problem and proposes a new methodology based on heuristic techniques. The method combines the solution of a p-median problem in order to generate an initial feasible solution and an improvement procedure that makes use of a ?-interchange mechanism. Computational results on many instances are provided / Mestrado / Mestre em Engenharia Elétrica

Orientador: Reginaldo Guirardello / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Quimica / Made available in DSpace on 2018-07-27T15:25:01Z (GMT). No. of bitstreams: 1 Franceira_SergioNorival_M.pdf: 3731488 bytes, checksum: d7857c421064b5382fefae40ea456256 (MD5) Previous issue date: 2001 / Resumo / Abstract / Mestrado / Desenvolvimento de Processos Químicos / Mestre em Engenharia Química