Orientador: Luziane Ferreira de Mendonça / Dissertação ( mestrado profissional) - Universidade Estadual de Campionas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-17T15:32:08Z (GMT). No. of bitstreams: 1 Tavora_RogerioCarvalhoMendes_M.pdf: 4616708 bytes, checksum: 3a393a830c9e1127f5694b0a56d9fcd9 (MD5) Previous issue date: 2011 / Resumo: Comemorando os 200 anos de Academia Militar no Brasil a partir de março de 2011, estão previstas várias implementações e melhorias na estrutura de visitação da AMAN que, consequentemente, vão gerar um aumento substancial no número de grupos visitantes no ano de seu bicentenário. Diante dos fatos percebe-se a necessidade de um modelo matemático eficiente cuja finalidade seja permitir aos grupos visitantes percorrerem trajetos otimizados, ou seja, que passem pelos pontos principais de visitação no menor tempo e distância possíveis. O modelo matemático a ser adotado neste trabalho é o Problema do Caixeiro Viajante (Traveling Salesman Problem - TSP), um clássico da Otimização Combinatória pertencente 'a classe de problemas NP - difícil, que já possui eficientes algoritmos desenvolvidos. Serão utilizadas heurísticas próprias para a resolução do TSP com o intuito de se obter numericamente itinerários ótimos de visitação, considerando os diferentes grupos visitantes e suas dificuldades de acesso, dentre outras particularidades. / Abstract: Celebrating 200 years of the Military Academy in Brazil from March 2011, provides a lot of implementations and improvements in the structure of visitation of AMAN, consequently, will generate substantial growth in the number of visiting groups in the year of its bicentennial. Given the facts we see the need for an efficient mathematical model whose purpose is to allow visitors to wander paths optimized groups, ie passing through the main points of visitation in the shortest possible time and distance. The mathematical model to be adopted in this work is TSP (Traveling Salesman Problem - TSP), a classic combinatorial optimization class of problems NP - hard, that have already efficient algorithms. We will use own heuristics for solving the TSP in order to obtain numerically optimal routes for visitors, considering the various visiting groups and their difficulties of access, among other features. / Mestrado / Mestre em Matemática

Orientador: Flávio Keidi Miyazawa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-18T01:07:44Z (GMT). No. of bitstreams: 1 Queiroz_ThiagoAlvesde_D.pdf: 1460601 bytes, checksum: 0d83e25259c427329e25174c2e729e77 (MD5) Previous issue date: 2010 / Resumo: Problemas de Corte e Empacotamento são, em sua maioria, NP-difíceis e não existem algoritmos exatos de tempo polinomial para tais se for considerado P ¿ NP. Aplicações práticas envolvendo estes problemas incluem a alocação de recursos para computadores; o corte de chapas de ferro, de madeira, de vidro, de alumínio, peças em couro, etc.; a estocagem de objetos; e, o carregamento de objetos dentro de contêineres ou caminhões-baú. Nesta tese investigamos problemas de Corte e Empacotamento NP-difíceis, nas suas versões bi- e tridimensionais, considerando diversas restrições práticas impostas a tais, a saber: que permitem a rotação ortogonal dos itens; cujos cortes sejam feitos por uma guilhotina; cujos cortes sejam feitos por uma guilhotina respeitando um número máximo de estágios de corte; cujos cortes sejam não-guilhotinados; cujos itens tenham demanda (não) unitária; cujos recipientes tenham tamanhos diferentes; cujos itens sejam representados por polígonos convexos e não-convexos (formas irregulares); cujo empacotamento respeite critérios de estabilidade para corpos rígidos; cujo empacotamento satisfaça uma dada ordem de descarregamento; e, cujos empacotamentos intermediários e final tenham seu centro de gravidade dentro de uma região considerada "segura". Para estes problemas foram propostos algoritmos baseados em programação dinâmica; modelos de programação inteira; técnicas do tipo branch-and-cut; heurísticas, incluindo as baseadas na técnica de geração de colunas; e, meta-heurísticas como o GRASP. Resultados teóricos também foram obtidos. Provamos uma questão em aberto levantada na literatura sobre cortes não-guilhotinados restritos a um conjunto de pontos. Uma extensiva série de testes computacionais considerando instâncias reais e várias outras geradas de forma aleatória foram realizados com os algoritmos desenvolvidos. Os resultados computacionais, sendo alguns deles comparados com a literatura, comprovam a validade dos algoritmos propostos e a sua aplicabilidade prática para resolver os problemas investigados / Abstract: Several versions of Cutting and Packing problems are considered NP-hard and, if we consider that P ¿ NP, we do not have any exact polynomial algorithm for solve them. Practical applications arises for such problems and include: resources allocation for computers; cut of steel, wood, glass, aluminum, etc.; packing of objects; and, loading objects into containers and trucks. In this thesis we investigate Cutting and Packing problems that are NP-hard considering theirs two- and three-dimensional versions, and subject to several practical constraints, that are: that allows the items to be orthogonally rotated; whose cuts are guillotine type; whose cuts are guillotine type and performed in at most k stages; whose cuts are non-guillotine type; whose items have varying and unit demand; whose bins are of variable sizes; whose items are represented by convex and non-convex polygons (irregular shapes); whose packing must satisfy the conditions for static equilibrium of rigid bodies; whose packing must satisfy an order to unloading; and, whose intermediaries and resultant packing have theirs center of gravity inside a safety region; Such cutting and packing problems were solved by dynamic programming algorithms; integer linear programming models; branch-and-cut algorithms; several heuristics, including those ones based on column generation approaches, and metaheuristics like GRASP. Theoretical results were also provided, so a recent open question arised by literature about non-guillotine patterns restricted to a set of points was demonstrated. We performed an extensive series of computational experiments for algorithms developed considering several instances presented in literature and others generated at random. These results, some of them compared with the literature, validate the approaches proposed and suggest their applicability to deal with practical situations involving the problems here investigated / Doutorado / Doutor em Ciência da Computação

Orientador: Jose Plinio de Oliveira Santos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-05T07:47:09Z (GMT). No. of bitstreams: 1 Bovo_Eduardo_M.pdf: 3427598 bytes, checksum: 757ebc9282f3c010e155c26ec46fb42a (MD5) Previous issue date: 2005 / Resumo: Neste trabalho são desenvolvidos conceitos algébricos, analíticos e combinatórios que culminam no Teorema de Enumeração de Pólya; bem como são fornecidas muitas de suas aplicações em enumeração de padrões (grafos, colorações geométricas, tipos e permutações, etc). Tal teorema clássico, que tem suas bases em Teoria dos Grupos, utiliza fundamentalmente o conceito de funções geradoras, o que permite grande generalidade e computabilidade de resultados. Finalmente são apresentadas algumas generalizações do resultado principal, aplicações destas e também uma importante interpretação probabilística / Abstract: In this dissertation we present algebraic, analytic and combinatorial results that are used to prove Polya's Enumeration Theorem. Applications to counting patterns (graphs, colourings, permutations, etc.) are given. This classical Theorem has its foundations on the theory of groups and uses, mainly, the concept of generating functions which allows great generality and computability of results. At the end some generalizations of the main theorem are given including applications and, aiso, an important probabilistic interpretation / Mestrado / Combinatoria Enumerativa / Mestre em Matemática Aplicada

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-08-05T15:44:02Z (GMT). No. of bitstreams: 1 Domingos_AlinePaulino_M.pdf: 2016351 bytes, checksum: 82db83a7778962c2c07b6ea4ac7e6514 (MD5) Previous issue date: 2005 / Resumo: As novas tecnologias de transmissão trazem maior flexibilidade e eficiência à rede de acesso, tornando-a capaz de atender o contínuo crescimento de demanda por serviços de telecomunicações. Uma alternativa de evolução conveniente em muitos casos é o provimento de serviços através de redes wireless fixas. Estas redes, conhecidas genericamente como FWA (Fixed Wireless Access), podem reduzir os investimentos da infra-estrutura de acesso. Neste trabalho apresentamos uma nova abordagem para o planejamento de sistemas FWA utilizando um modelo de programação linear mista baseado na representação em grafos. Devido à alta complexidade associada à resolução de problemas deste tipo através de métodos exatos, propomos um tratamento baseado em algoritmos genéticos (GA). A partir de uma formulação exata, mostramos como especificar os componentes principais de um GA: cromossomo, codificação da solução, avaliação de fitness, estrutura da população e operadores genéticos (processo de cruzamento e mutação). No problema tratado, as variáveis de decisão foram codificadas para um cromossomo especializado e eficiente. Além disto, o problema da infactibilidade de alternativas geradas foi contornado por um método de descarte. Garante-se também para cada alternativa a maximização da demanda atualizada (o que proporciona maior rentabilidade). Uma aplicação do método é relatada / Abstract: New transmission technologies give more flexibility and efficiency to the Access network, which is supposed to deal with the continuous growth of demand for telecommunication services. Operator companies need to innovate their networks in order to provide broadband services. Therefore, the network planning is essential to achieve the best performance under minimum cost. An alternative of evolution that seems to be interesting is the provision of services through fixed wireless networks. These networks, generically known as FWA (Fixed Wireless Access), can reduce the infrastructure access cost. In this paper, we present a new approach to the planning of FWA systems. First, we develop an optimization model with binary decision variables. The mathematical formulation to the model is also stated. Because solving mixed integer problems through exact methods is a complex task, we adopt a strategy based on genetic algorithms (GA). Thus, we show how to specify the main components of a GA: chromosome, solution coding, fitness assessment, population structure, and genetic operators (crossover and mutation process), in order to specialize the technique to the FWA planning problem. Besides, chromosome feasibility is ensured. An application of the proposed method is also reported. / Mestrado / Otimização / Mestre em Engenharia Elétrica

Orientador: Marcia A. Gomes Ruggiero / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-05T23:37:23Z (GMT). No. of bitstreams: 1 Haeser_Gabriel_M.pdf: 906525 bytes, checksum: ea7e3eb42abe6b8b451f99c4c63a3da4 (MD5) Previous issue date: 1996 / Resumo: Neste trabalho estudamos a teoria de algumas heurísticas para otimização global, e também a generalização do algoritmo genético de Aarts, Eiben e van Hee. Propomos um algoritmo para otimização global de problemas canalizados e diferenciáveis utilizando simulated annealing e o solver local GENCAN. Experimentos numéricos com o problema OVO ( Order- Value Optimization) são apresentados, e também com 28 problemas clássicos da literatura. Para problemas de otimização com restrições, apontamos idéias de como utilizar solvers locais e heurísticas globais em busca de bons algoritmos para otimização global, e propomos um algoritmo baseado em simulated annealing com solver local ALGENCAN / Abstract: In this work we study the theory behind some classical heuristics for global optimization, and a generalization of genetic algorithms from Aarts, Eiben and van Hee. We propose an algorithm for global optimization of box-constrained differentiable problems, using simulated annealing and the local solver GENCAN. Numerical experiments are presented for the OVO problem (Order-Value Optimization) and 28 classical problems. For general nonlinear programming problems, we mention some ideas of how to use local solvers and global heuristics towards good algorithms for global optimization, we also propose an algorithm based on simulated annealing with local solver ALGENCAN / Mestrado / Otimização / Mestre em Matemática Aplicada

Orientador: Raul Vinhas Ribeiro / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T02:43:23Z (GMT). No. of bitstreams: 1 AraujoNeto_FranciscoCiliaode_M.pdf: 1886300 bytes, checksum: 7f7be0f39b44f4f0126206eb89016e20 (MD5) Previous issue date: 2005 / Resumo: Com o amadurecimento da tecnologia de multiplexação por comprimentos de onda ¿ WDM (Wavelength Division Multiplexing) e a crescente popularização de aplicações multidifusão, como teleconferência, o suporte a esse tipo de transmissão na camada WDM é um tópico importante a ser estudado. Uma particularidade no roteamento de comunicações multidifusão, devido ao alto custo, é o limite no número de comutadores (switches) capazes de dividir o sinal de luz para mais de um destino. Esse limite introduz o problema de alocação desse tipo de comutador nos nós da rede de forma a facilitar o roteamento multidifusão. Além de considerações sobre o aspecto topológico da rede, outras particularidades do problema de roteamento e alocação de comprimentos de onda são as degenerações da camada física da rede óptica, que proporcionam algumas restrições de potência no sinal óptico. Esse trabalho apresenta uma heurística para solução de dois problemas. O problema de alocação de divisores do sinal de luz (splitters), de roteamento e de alocação de comprimento de onda para comunicações multidifusão e o problema de roteamento e alocação de comprimentos de onda considerando restrições de potência na camada física da rede óptica. Experimentos indicam que a heurística proposta apresenta um bom compromisso entre rapidez e qualidade de solução / Abstract: Due to the WDM (Wavelength Division Multiplexing) technology maturity and the growing popularization of multicast applications, such as teleconference, the support to this type of transmission in WDM layer must be exploited. An issue in routing multicast connections, due to the high cost, is the limited number of switches capable of divide the light signal to more than one destination. This limit introduces the allocation problem of these kind of switches in the nodes of network with objective of facilitate the multicast routing. Despite these topologic issues of the network, other particularities of the routing and wavelength assignment problem are the power issues in the physical layer, which take some power restrictions in optical signal. This work presents a heuristic to solve two problems. The problem of Splitter placement, multicast routing and wavelength assignment and the problem of routing and wavelength assignment with power issues in physical layer in optical network. Experiments indicate that the heuristic presents a good tradeoff between quality and time solution / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Antonio Carlos Moretti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-06T12:59:52Z (GMT). No. of bitstreams: 1 Sousa_VaniaNobrede_M.pdf: 984501 bytes, checksum: f58d5baf5c8e4dc8e704f4cb9aa47c6b (MD5) Previous issue date: 2006 / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

Orientador: Jose Plinio O. Santos / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-06T21:44:47Z (GMT). No. of bitstreams: 1 CunhaFilho_Jair_D.pdf: 2442598 bytes, checksum: 0971fb5486221b670201a5115f273171 (MD5) Previous issue date: 2006 / Resumo: Neste trabalho, tratamos de algumas variações dos Diagramas de Ferrers, onde apresentamos, em especial, uma que consiste de um diagrama hexagonal infinito, com cada hexágono dotado das diagonais que passam pelo seu centro. O resultado envolve uma subseqüência da seqüência de Fibonacci fazendo contagem em termos de partições. Apresentamos, também, interpretaçoes das partições planas com duas e três linhas em termos de partições ordinárias com partes tomadas em multiconjuntos, exibindo, em cada caso, as respectivas bijeções. No caso das partições planas com duas linhas, exibimos uma bijeção entre a interpretq,ção obtida e uma interpretação já conhecida. Finalmente, apresentamos bijeções entre algumas interpretações combinatórias, envolvendo números de Fibonacci e Pell. Encerramos, exibindo uma classe de partições, onde, para valores particulares de um parâmetro, obtemos como corolários resultados conhecidos / Abstract: Tn this thesis we study some variations of the Ferrers Diagram where we present, in particular, one that involves a infinite hexagonal diagram including the diagonals going through the center. The result involves a subsequence of. the Fibonacci numbers where one uses partitions. We present, also, interpretations of plane partitions with two and three !ines, in terms of the ordinary partitions, with parts taken frorp multisets giving, in each case, the corresponding bijections. Tn the case of the plane partitions with two !ines a bijection between our interpretation and one already known is given. We have combinatorial results related to Fibonacci and Pell numbers. At the end we present a class of partitions where, for particular values of the parameter, we get results already known / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-07T08:02:12Z (GMT). No. of bitstreams: 1 Andrade_CarlosEduardode_M.pdf: 1512396 bytes, checksum: aac3459428d8f61b130828587f727265 (MD5) Previous issue date: 2006 / Resumo: Problemas de corte e empacotamento aparecem freqüentemente na indústria e comércio, e sua solução de forma otimizada pode trazer grandes ganhos em diversos setores.Um problema muito comum, notadamente no setor têxtil e do papel, é o corte de um rolo ou faixa de um determinado material para obtenção de itens menores, onde temos por objetivo utilizar a menor extensão do rolo/faixa possível. Este problema, conhecido como Problema de Empacotamento Bidimensional em Faixas (PEBF), é tido como um problema de otimização combinatória de difícil resolução. Neste trabalho, apresentamos um algoritmo exato para o PEBF restrito a cortes de dois estágios (PEBF2). O algoritmo usa a técnica de branch-and-price, que utiliza, por sua vez, heurísticas baseadas em algoritmos aproximados para a obtenção de limitantes superiores. O algoritmo se mostrou eficaz na obtenção de soluções para instâncias de pequeno e médio porte / Abstract: Cutting and packing problems are common problems that occur in many industry and business process. Their optimized resolution leads to great profits in several sectors. A common problem, that occur in textil and paper industries, is to cut a strip of some material to obtain several small items, using the minimum length of material. This problem, known by Two Dimensional Strip Packing Problem (2SP), is a hard combinatorial optimization problem. In this work, we present an exact algorithm to 2SP, restricted to two staged cuts (known by Two Dimensional Level Strip Packing, 2LSP). The algorithm uses the branch-and-price technique, and heuristics based on approximation algorithms to obtain upper bounds. The algorithm obtained optimal or almost optimal for small and moderate sized instances / Mestrado / Mestre em Ciência da Computação

Orientador: Jose Plinio de Oliveira Santos / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-14T00:20:04Z (GMT). No. of bitstreams: 1 Silva_Robsonda_D.pdf: 897208 bytes, checksum: 5d17d33a20271484f3f7853e008443db (MD5) Previous issue date: 2009 / Resumo: No presente trabalho, apresentamos provas bijetivas para algumas identidades. A principal ferramenta utilizada _e a representação para partições como matrizes de duas linhas introduzida em [9] e [10]. Também apresentamos algumas conseqüências desta representação e a extendemos a outros casos. Uma prova bijetiva para uma identidade envolvendo os Números Triangulares e apresentada ao final. / Abstract: In this work, we show bijective proofs for some identities. The main tool is the two-line matrix representation for partitions introduced in [9] and [10]. We also present some consequences of this representation and we also extend it to other cases. A bijective proof for an identity involving the Triangular Numbers is given at the end. / Doutorado / Matematica Discreta / Doutor em Matemática Aplicada