Made available in DSpace on 2018-06-27T19:13:28Z (GMT). No. of bitstreams: 2 Ana Paula Goncalves da Fonte.pdf: 3610212 bytes, checksum: 6f01dc19dac3d3b4759b3ef10be9c017 (MD5) Ana Paula Goncalves da Fonte.pdf.jpg: 3402 bytes, checksum: 82d9444711460fe1d0705b7e124f8eb3 (MD5) Previous issue date: 2009-05-15 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This paper features, as its central investigation focus the contributions that Problem Resolution methodology, allied to the building of Image and Definition Concepts, offer to the learning and teaching process of concepts of Combinative Analysis, through a qualitative research, adopting the following methodological procedures: interactive observation in the classroom and work field diary of the teacher-researcher. The research has been developed with 35 students of the sixth semester Math full licentiate course at Pontifícia Universidade Católica, Rio Grande do Sul state, (PUCRS), Uruguaiana campus, on the second semester of 2008. The activities in the classroom followed the steps of problem resolution suggested by Onuchic (1999): Set groups, reading and teacher questions about the problems, taking notes of the results on the chalk board, plenary, consensus and concept formalization. The analysis of the resolutions presented by the students proved the contributions of this teaching strategy choice, for the growing of the Math thought can be proved. That means, the merge of the resolution problem methodology to the building of the concept image and definition give the teacher a more realistic view of the knowledge acquiring process by the student, allowing the teacher to know where there should be the readjustment of the activities adopted and the beginning of new topics. / Este trabalho apresenta como foco central de investigação as contribuições que a metodologia de resolução de problemas, aliada a construção dos conceitos imagem e definição oferecem ao processo de ensino e aprendizagem de conceitos de Análise Combinatória, por meio de uma pesquisa qualitativa, adotando os seguintes procedimentos metodológicos: observação participante em sala de aula e diário de campo da professora-pesquisadora. A pesquisa foi desenvolvida com 35 alunos do sexto semestre do curso de licenciatura plena em matemática da PUCRS-Câmpus de Uruguaiana, no segundo semestre de 2008. As atividades em sala de aula seguiram os passos da resolução de problemas., sugeridos por Onuchic (1999): Formar grupos, leitura e questionamentos do professor sobre o problema, anotação dos resultados no quadro de giz, plenária, consenso e formalização do conceito. A análise das resoluções apresentadas pelos alunos comprovaram as contribuições desta escolha de estratégia de ensino, pois o crescimento do pensar matemático pode ser comprovado. Ou seja, a união da metodologia de resolução de problemas a construção de conceito imagem e definição propiciam a professora uma visão mais real do processo aquisição do conhecimento do aluno, possibilitando ao professor saber onde deveria haver a reestruturação das atividades adotadas e o início de novos assuntos. Palavras-chave: Resolu

Orientador: Antônio 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-17T07:59:31Z (GMT). No. of bitstreams: 1 Pinto_LuisFrancodeCampos_M.pdf: 11074962 bytes, checksum: 1a81559fbea90f37c92a435180da70b3 (MD5) Previous issue date: 2010 / Resumo: Neste trabalho, foi desenvolvida uma aplicação prática de técnicas da pesquisa operacional para a resolução de um problema real de esquematização ou programação de máquinas. Este problema deriva de um flexible job shop scheduling, porém apresentando diversas características próprias, impossibilitando a aplicação de modelos disponíveis na literatura. O desempenho da utilização da combinação de um modelo de programação linear inteira mista com uma heurística de construção e uma heurística de melhoramento foi avaliado diante de cenários reais obtidos da indústria de produção de frascos plásticos. Estas técnicas provaram ser eficientes para a resolução dos casos propostos / Abstract: In this work, a practical application of operational research techniques was developed to solve a real machine scheduling or programming problem. This problem derives from a flexible job shop scheduling framework, but presents several unique characteristics, which makes it impossible to apply models available in literature. The performance of using a combination of a mixed integer programming model with a construction heuristic and a improvement heuristic was evaluated using real world scenarios obtained from the plastic bottle production industry. Theses techniques were proven efficient in resolving the proposed cases / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

Orientador: Paulo Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-05T20:11:19Z (GMT). No. of bitstreams: 1 Garcia_ViniciusJacques_D.pdf: 1756755 bytes, checksum: e845cc09a5de807da958e9792684e777 (MD5) Previous issue date: 2005 / Resumo: Depois da regulamentação do setor elétrico brasileiro, a qualidade no fornecimento de energia ganhou maior importância por parte das concessionárias. Neste contexto, o problema de restauração do serviço tem particular relevância pela relação com a freqüência e duração das interrupções no fornecimento: através de alterações na configuração original da rede, busca-se reduzir a carga não atendida sem deixar de observar as restrições de capacidade dos alimentadores, de queda de tensão nas barras de carga e de radialidade da rede. Considerando o caráter temporário destas manobras, torna-se desejável reduzir o grau de intervenção de modo a facilitar a restauração da configuração original. Nesta tese é considerado o problema multiobjetivo de restauração do serviço que compreende a minimização da carga sem fornecimento e do número de chaves manipuladas. Depois da definição matemática do problema, da revisão da literatura especializada e da descrição de um "framework" para problemas relacionados, são descritas duas heurísticas, uma construtiva e outra de melhoramento. A seguir, apresentam-se duas metaheurísticas para o problema, uma Busca Tabu e um Algoritmo Evolutivo, ambas baseadas em otimização de Pareto. Por fim, por meio de estudos práticos com sistemas de distribuição brasileiros, avalia-se experimentalmente a aplicabilidade das abordagens propostas / Abstract: After the Brazilian electric power market regulation, quality of service became a crucial concern of utilities. In fact, the service restoration has a particular importance since it is closely related to frequency and duration of service interruption: through network reconfigurations, one aims to reduce the non supplied load while respecting constraints like feeder and voltage limits as well as the maintenance of a radial structure. Considering that this emergency state is transitory existing only until the fault is eliminated, it is convenient to reduce the number of switching operations in order to make the return back to the original configuration easy. This work considers the multiobjective service restoration to minimize both the load not supplied and the number of switching operations. After defining the mathematical formulation proposed and presenting the bibliographical survey with the description of a new framework to related problems, two new heuristics are presented, one for constructive search and another one for neighborhood search. Next, two metaheuristics especially developed for the referred problem are described, both based on Pareto optimization. Finally, the effectiveness of these proposed methods are proved in a set of five systems, three of them referring to actual Brazilian systems / Doutorado / Automação / Doutor em Engenharia Elétrica

Orientador: Carlos Alberto de Castro Junior / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T10:50:00Z (GMT). No. of bitstreams: 1 Guimaraes_MarcosAntoniodoNascimento_M.pdf: 908712 bytes, checksum: d5cf1733a05a1a20b87eb0c7abf094fb (MD5) Previous issue date: 2005 / Resumo: A reconfiguração de sistemas de distribuição consiste na alteração da topologia da rede através do fechamento e abertura de chaves instaladas em pontos estratégicos da rede. Normalmente o procedimento é utilizado para fins de isolamento de faltas, minimização de perdas de potência ativa e balanceamento de cargas entre os alimentadores. Esse problema é de difícil resolução devido ao grande número de variáveis envolvidas e das restrições impostas, sendo a restrição de radialidade a de mais difícil representação matemática. O problema pode ser classificado como um problema de programação não linear inteiro misto (PNLIM) e apresenta o fenômeno de explosão combinatorial. Este trabalho tem como principal objetivo o desenvolvimento de um algoritmo de Busca Tabu para a reconfiguração de sistemas de distribuição de energia elétrica tendo como objetivo a maximização da margem de segurança com relação à estabilidade de tensão (ou margem de carregamento). São apresentados resultados para sistemas de 14 barras, 32 barras, 69 barras, 84 barras e os sistemas reais de 135 barras e 202 barras / Abstract: The network reconfiguration consists in modifying the topology of the network through the closing and opening of switches installed in strategical points. The reconfiguration of distribution systems is usually done to isolate faults, minimize real power losses, or to balance the load among feeders. This problem is difficult due to the great number of variables involved and the imposed constraints, being the constraint of radial structure of more difficult mathematical representation. The problem can be classified as nonlinear mixed integer programming problems with combinatorial explosion. The main objective of this work is to develop a Tabu Search algorithm for the reconfiguration of distribution systems for voltage stability margin enhancement. Results for the systems: 14 buses, 32 buses, 69 buses, 84 buses and the real systems 135 bus and 202 bus are presented and discussed. / Mestrado / Sistemas de Energia Eletrica / Mestre em Engenharia Elétrica

Cette recherche visait à étudier le potentiel des transformations de représentation sémiotique d´enregistrements dans une analyse combinatoire de la proposition de l´enseignement intégré sur la résolution pour les étudiants de 2e année de l´école secondaire problème. Le cadre théorique de cette recherche a été liée à l´enseignement et l´apprentissage des cours de mathématiques en utilisant la Représentation Sémiotique registres, les niveaux de connaissance attendus des étudiants et de dépannage. Pour le développement de cette étude ont été utilisés aspects méthodologiques de génie didactique. L´analyse a été développé à partir d´un point de vue qualitatif. Participé à cette étude, les élèves de la deuxième année de l´école secondaire de la State College Victoire de Santa Maria à Aracaju / SE. Il a été prouvé dans l´application de la séquence d´enseignement que l´enseignement basé sur les leçons de l´expérience qui stimule la mobilisation des dossiers sémiotiques et les activités liées à la quotidienne de l´étudiant a contribué efficacement à l´enseignement et l´apprentissage de l´analyse combinatoire. / A presente pesquisa teve como objetivo geral investigar o potencial das transformações dos registros de representação semiótica em uma proposta de ensino de Análise Combinatória construída com base na resolução de problemas para alunos da 2º série do ensino médio. O referencial teórico desta investigação esteve relacionado com o processo de ensino e aprendizagem da disciplina matemática, utilizando os Registros de Representação Semiótica, Níveis de conhecimento esperados dos estudantes e Resolução de Problemas. Para o desenvolvimento desse estudo foram utilizados aspectos metodológicos da Engenharia Didática. A análise se desenvolveu numa perspectiva qualitativa. Participaram dessa pesquisa os alunos da segunda série do ensino médio do Colégio Estadual Vitória de Santa Maria em Aracaju/SE. Ficou comprovado na aplicação da sequência didática que o ensino baseado em experiências de aulas que estimule a mobilização dos registros semióticos e com atividades relacionadas ao cotidiano do discente contribuiu de forma efetiva para o ensino e a aprendizagem de Análise Combinatória.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Counting techniques studied in basic education aim at the resolutions os simplest combinatorial problems. In this work, we present the generating functions, a powerful tool to solving more complex problems of counting. In this way, we discuss the contents of combinatorial analysis through the study of generating functions, proposing a didactic sequence on the subject for teachers of basic education can expand and diversify their teaching strategies, by means of this counting method. / As t ecnicas de contagem estudadas na educação b ásica visam as resolu ções de problemas combinat órios mais simples. Neste trabalho, apresentaremos as funções geradoras, uma poderosa ferramenta para solucionar problemas mais complexos de contagem. Destaforma, abordaremos o conte udo de an alise combinat ória atrav és do estudo de funções sgeradoras, propondo uma sequência did ática sobre o tema para que os professores da educação b ásica possam ampliar e diversi car as suas estrat égias de ensino, a a partir deste novo método de contagem.

Orientadores: Christiano Lyra Filho, Celso Cavellucci / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-13T03:27:30Z (GMT). No. of bitstreams: 1 Reis_PauloAlexandre_M.pdf: 462293 bytes, checksum: 3e3ba986f1d06695ded61d98139be232 (MD5) Previous issue date: 2007 / Resumo: Abordagens tradicionais de manutenção de sistemas de distribuição de energia elétrica se baseiam em ações realizadas periodicamente, ou programadas, de acordo com uma análise de necessidades e prioridades após inspeções. Embora essas abordagens tenham o objetivo de melhorar a confiabilidade dos sistemas, geralmente não há uma avaliação precisa do impacto das ações de manutenção na confiabilidade dos mesmos. O planejamento de manutenções pode ser realizado sob a perspectiva da confiabilidade com abordagens recentes chamadas RCM (reliability centered maintenance - manutenção baseada em confiabilidade). Essas abordagens procuram estabelecer uma ligação rigorosa entre manutenção e confiabilidade. Este trabalho propõe uma abordagem de manutenção baseada em confiabilidade com a perspectiva de encontrar as melhores estratégias para manutenções de redes de distribuição de energia elétrica; apresenta um modelo matemático e metodologia de otimização para encontrar as melhores estratégias de manutenções em um determinado horizonte de estudo. O problema formulado caracteriza-se como um problema de otimização combinatória com o objetivo de encontrar as ações de manutenção que minimizem os recursos utilizados em manutenções preventivas e corretivas, garantindo um nível de confiabilidade desejado para o sistema. O trabalho desenvolve duas alternativas para solução do problema: a primeira abordagem foi construída a partir do método GRASP (greedy randomized adaptive search procedure); a segunda abordagem é um método de computação evolutiva com busca local. Estudos de casos em redes de porte real avaliam as duas alternativas de solução. Os resultados realçam aspectos significativos da abordagem desenvolvida. / Abstract: Traditional approaches to electric power distribution systems maintenance are based on activities performed at regular intervals, or scheduled after analysis of needs end priorities identified after inspections. Although these maintenances activities are carried out to improve reliability, usually such approaches do not explicitly consider the impact of maintenance activities on reliability. Maintenance planning can be guided by reliability with recent approaches known as RCM (reliability centered maintenance). A RCM approach tries to establish a rigorous link between maintenance and reliability. This work proposes a reliability centered maintenance approach to unveil the best maintenance schedule for electric power distribution networks; it presents a mathematical model and optimization methods to find the best maintenance schedule along a given planning horizon. The problem is formulated as a combinatorial optimization problem with the objective of finding the maintenance activities that minimize the resources allocated to preventive and corrective maintenance, making sure the system meets a reliability target. The work proposes two heuristic methods to solve the problem: the first one is a GRASP method (Greedy Randomized Adaptive Search Procedure); the other one is an evolutionary computation method with local search. Realistic case studies are used to evaluate both methods. The results highlight meaningful aspects of the proposed approaches. / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T07:24:38Z (GMT). No. of bitstreams: 1 Piva_Breno_M.pdf: 1251793 bytes, checksum: bf559620a7bdefeec032b5c87d196b5b (MD5) Previous issue date: 2009 / Resumo: O problema do Máximo Subgrafo Induzido Comum (MSIC) pertence a classe NP-difícil e possui aplicações em diversas áreas. Apesar de sua complexidade, ainda é importante conhecer soluções exatas para instâncias deste problema. Os algoritmos exatos encontrados na literatura buscam resolvê-lo através de técnicas de backtracking ou através de sua redução para o problema da Clique Máxima. Neste trabalho procuramos dar uma solução exata para o MSIC, tratando-o diretamente através da utilização de modelos de Programação Linear Inteira (PLI) e técnicas de combinatória poliédrica. Assim, realizamos um estudo teórico do poliedro do MSIC e fomos capazes de encontrar algumas desigualdades válidas fortes, inclusive com provas de que algumas delas representam facetas daquele poliedro. Adicionalmente, provamos que existe uma equivalâencia entre o modelo PLI aqui apresentado para o MSIC e uma formulação bem conhecida para o problema da Clique Máxima. Posteriormente, foram implementados algoritmos de Branch-and-Bound (B&B) e Branch-and-Cut (B&C) utilizando as desigualdades encontradas e algumas técnicas para tentar tornar os algoritmos mais eficientes. Experimentos foram executados com os algoritmos implementados neste trabalho e, também, com um algoritmo já existente para resolver o problema da Clique, chamado Cliquer. Os resultados foram comparados e, dentre os algoritmos de PLI, constatamos que o mais eficiente foi aquele que utilizou uma formulação para o MSIC que chamamos de Clique-IS, utilizando B&B e técnicas mais básicas que outros algoritmos. Este algoritmo mostrou-se mais eficiente, inclusive, que um algoritmo PLI com um modelo baseado no problema da Clique Máaxima. Este fato sugere que para uma abordagem baseada em PLI, vale a pena utilizar uma formulação do MSIC diretamente, ao invés de uma que se apóie na redução deste para o problema da Clique Máxima. Ja a comparaçao do melhor algoritmo desenvolvido neste trabalho com o Cliquer, mostrou que este último é mais eficiente. Para que um algoritmo baseado em PLI (utilizando uma formulação com as mesmas variáveis usadas por nós) tivesse alguma chance de vencer um algoritmo combinatório como o Cliquer, seria necessário conhecer mais desigualdades que estivessem ativas na solução ótima do problema / Abstract: The Maximum Common Subgraph problem (MSIC) is in MV-hard and has applications in several fields. Despite its complexity, it is still important to know exact solutions for instances of this problem. The exact algorithms found in literature try to solve it through backtracking techniques or through its reduction to the Maximum Clique problem. In this work we try to give an exact solution to MSIC by addressing it directly, using Linear Integer Programming (PLI) and polyhedral combinatorics techniques. So, we performed a study of the MSIC polyhedron and we were able to find some strong valid inequalities, including some that were proven to define facets of that polyhedron. Additionally, we proved that an equivalence between the PLI model presented here for MSIC and a well known formulation for the Maximum Clique problem exists. Later, Branch-and-Bound (B&B) and Branch-and-Cut (B&C) algorithms were implemented using the inequalities found and some techniques to try to render the algorithms more efficient. Experiments were performed with the algorithms implemented in this work and, also, with an already existing algorithm to solve the Maximum Clique problem, called Cliquer. The results were compared and, among the PLI algorithms, we found that the most efficient was the one that used the formulation which we called Clique-IS, using B&B and more basic techniques than other algorithms. This algorithm was even more efficient than a PLI algorithm with a Clique-based model. This fact suggests that for a PLI approach it is worth to use a formulation based on the MSIC polyhedron instead of one based on its reduction to the Maximum Clique problem. The comparison of the best algorithm developed in this work with Cliquer, though, showed that the latest is more efficient. In order to some PLI-based algorithm (using a formulation with the same variables used by us) to have any chance of outperforming a combinatorial algorithm like Cliquer, it would be necessary to know more inequalities that are active in the problem's optimal solution / Mestrado / Otimização Combinatoria / Mestre em Ciência da Computação

Made available in DSpace on 2015-04-11T14:02:41Z (GMT). No. of bitstreams: 1 rainer.pdf: 3537323 bytes, checksum: 46bd81628ce774393ea9334f7287a55f (MD5) Previous issue date: 2013-03-27 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation presents a study on scheduling problems with earliness and tardiness penalties on identical parallel machines, considering independent and weighted jobs with arbitrary processing times. An analysis of the major mathematical formulations in integer programming is given, and presented the main results from the literature. An integer mathematical formulation based on network flow model was also proposed for the problem, which can be applied on single and parallel machines without idle time. Exact methods of implicit enumeration were studied and applied for the problem through the integer linear programming solver CPLEX and the UFFLP library and, mainly, algorithmic strategies of global optimization based on local search heuristic and path-relinking technique were developed. The computational experiments shows that the proposed algorithmic strategies are competitive in relation to existing results from the literature for single-machine scheduling, involving instances based on OR-Library benchmark for 40, 50, 100, 150, 200 and 300 jobs, where all the optimal values were found, and, mainly, being the best algorithmic strategy for multiprocessor environments, involving 2, 4 and 10 identical parallel machines. / Esta dissertação apresenta um estudo sobre problemas de escalonamento com penalidades de antecipação e atraso em máquinas paralelas, considerando tarefas independentes, ponderadas e de tempos de execução arbitrários. Uma análise sobre as principais formulações matemáticas em programação inteira é dada, bem como apresentados os principais resultados da literatura. Uma formulação matemática de programação inteira baseada no modelo de fluxo em redes também foi proposta para o problema, que pode ser aplicada em ambientes mono e multiprocessado sem tempo ocioso. Métodos de enumeração implícita foram estudados e aplicados aos problemas em questão através do resolvedor de programação linear inteira CPLEX e da biblioteca UFFLP, principalmente, estratégias algorítmicas aproximadas de otimização global baseadas em heurísticas de busca local e técnica de reconexão de caminhos foram desenvolvidas. Os experimentos computacionais mostram que as estratégias propostas são competitivas em relação aos resultados existentes na literatura para ambientes de escalonamento monoprocessados, envolvendo instâncias baseadas no benchmark da OR-Library para 40, 50, 100, 150, 200 e 300 tarefas, onde todos os ótimos foram encontrados, e, principalmente, sendo a melhor estratégia apresentada para ambientes multiprocessados, envolvendo 2, 4 e 10 máquinas paralelas idênticas.

O problema de dimensionamento de lotes, objeto desse estudo, considera um ambiente composto por múltiplas plantas independentes, múltiplos itens e múltiplos períodos. O ambiente de produção tem capacidade limitada e as plantas podem produzir os mesmos itens. Cada planta tem uma demanda própria e é permitida a transferência de lotes entre as plantas, o que envolve um certo custo. Este problema tem como caso particular o de dimensionamento de lotes com máquinas paralelas. O objetivo desta dissertação é propor uma heurística baseada na meta-heurística GRASP (Greedy Randomized Adaptive Search Procedures). Além disso, uma estratégia path relinking foi incorporada ao GRASP como uma fase de melhoria do algoritmo. Para verificar a eficiência da heurística proposta, os seus resultados são comparados aos da literatura tanto no caso de máquinas paralelas quanto no de múltiplas plantas. Como resultado, o problema de múltiplas plantas obteve melhores resultados quando comparado aos da heurística da literatura. Com relação ao problema de máquinas paralelas, a heurística proposta se mostrou competitiva / The lot sizing problem, which is the aim of this study, considers an environment consisting of multiple independent plants, multiple items and multiple periods. The production environment has limited capacity and the plants can produce the same items. Each plant has its own demand and the lot transfers between the plants are permitted, which involves a certain cost. This problem has as a particular case the parallel machines lot sizing problem. The objective of this dissertation is to propose a heuristic based on the GRASP (Greedy Randomized Adaptive Search Procedures). Furthermore, a path relinking phase is embedded in the GRASP to obtain better performance. To verify the efficiency of the proposed heuristic, its results were compared with the literature as for the multi-plant as for parallel machines problem. Computational tests showed that the proposed heuristic performed better than other literature heuristic concerning the multiplant problem. Concerning the parallel machines, the heuristic is competitive