[pt] O estudo de geometria, em particular área de polígonos simples, é pouco trabalhado em sala de aula, sendo assim o presente trabalho tem como finalidade apresentar o Teorema de Pick, com algumas demonstrações, como ferramenta de cálculo de área. Atenção especial é necessária para polígonos simples mas não necessariamente convexos. Além disso discutimos outros Teoremas relacionados, como Jordan e Euler. Espera-se que esta pesquisa se some a outras no sentido de contribuir para o ensino de matemática de forma qualitativa, podendo se utilizar de técnicas aqui abordadas ou ainda serem adaptadas às diversas realidades para o seu melhor aproveitamento. / [en] The study of plane geometry, in particular the computation of areas of simple polygons, is little explored in the classroom. Our aim here is to state and prove Pick s Theorem. We also present sever al examples and more than one proof. Simple polygons (which are not necessarily convex) receive special attention. We also consider some related results, such as the theorems of Jordan and Euler. It is hoped that this re e arch will contribute to the teaching of mathematics in a qualitative way.

[pt] Esta tese define os problemas das p-medianas conectadas e o de localização de facilidades não-capacitadas conectadas. Possíveis aplicações incluem problemas de planejamento regional e o projeto de redes de telecomunicações ou de transporte. Para o primeiro problema, duas formulações de programação linear inteira são apresentadas e comparadas. Um destes modelos é adaptado para o segundo problema. Para o problema das p-medianas conectadas, algoritmos aproximados são desenvolvidos. Uma estratégia de busca local híbrida é proposta. Para acelerar as iterações do algoritmo de busca local, idéias como circularidade, melhoria iterativa e o descarte de vizinhos são incorporadas. Heurísticas GRASP e VNS são desenvolvidas incluindo a utilização de um filtro com o objetivo de diminuir os tempos de processamento e do procedimento de reconexão por caminhos com o objetivo de melhorar a qualidade das soluções encontradas. Diversos testes são realizados comparando-se esses algoritmos. Os resultados mostraram a necessidade de se executar um passo adicional de pós-otimização às heurísticas GRASP e VNS propostas. / [en] In this work, the connected p-median and the connected facility location problems are defined. Applications arise in regional planning, design of telecommunications and transportation networks. For the first problem, two integer linear programming formulations are proposed. Adaptations are made in one of these formulations and are used to model the second problem. Approximation algorithms to solve the connected p-median problem are developed. A hybrid local search strategy is proposed. In order to speed up the local search iterations, ideas as circularity, first- improving strategy and discard neighbors are incorporated. A GRASP algorithm and a VNS heuristic are also proposed. A filter is used to reduce the computational time required and a path-relinking is applied to improve the results found. Computational experiments to compare the algorithms are reported. To improve these results, it is applied a post-optimization step to the GRASP and VNS heuristics.

O presente trabalho teve como objetivo analisar se uma estratégia de ensino baseada em situações-problema contribui para a aprendizagem da Análise Combinatória pelos alunos da Educação de Jovens e Adultos. A sequência de ensino elaborada e implementada procurou abordar atividades que evocassem o cotidiano dos alunos e não dependessem de fórmulas previamente estudadas. A ordem em que as atividades foram propostas visou a formalização do princípio multiplicativo, como recurso a ser utilizado na resolução de problemas de contagem. A pesquisa foi desenvolvida sob a ótica de um estudo de caso, junto a uma turma de alunos dos cursos PROEJA Agroindústria e PROEJA Informática do Instituto Federal Farroupilha – Campus Alegrete, e teve como aportes teóricos a teoria do desenvolvimento cognitivo de Piaget e a teoria dos campos conceituais de Vergnaud, os quais nos forneceram subsídios para a compreensão do desenvolvimento do raciocínio combinatório e, das dificuldades apresentadas pelos alunos. O trabalho mostrou que é possível a aprendizagem de conteúdos de Análise Combinatória pelos alunos do PROEJA, através da implementação de uma sequência de ensino baseada na resolução de problemas, frente aos quais os alunos construíram diferentes estratégias de resolução que favoreceram o desenvolvimento do seu raciocínio combinatório. / The present research aimed at analyzing to what extent a teaching strategy based on contextualized problems contributes to the learning of the Combinatorial Analysis by students from Education for Young Adults and Adults (Educação de Jovens e Adultos – EJA). The teaching sequence developed and implemented comprehended activities which evoked students’ everyday life and were not dependent on previously studied formulas. The order in which the activities were proposed aimed the formalization of the multiplication principle as a resource to be used in the resolution of counting problems. The research was developed based on a case study, in a class of the National Program for integrating the Professional Education with Basic Education in the Education for Young Adults and Adults (Programa Nacional de Integração da Educação Profissional com a Educação Básica na modalidade de Educação de Jovens e Adultos – PROEJA) from the Food Technology course and the Information technology course of the Farroupilha Federal Institute in the Campus Alegrete and had as theoretical basis the theory of cognitive development by Piaget and the theory of conceptual fields by Vergnaud, which offer groundings for understanding the development of combinatorial thinking and the difficulties presented by the students. This analysis showed that learning of Combinatorial Analysis is possible for the PROEJA students, through the implementation of a teaching sequence based on the resolution of problems, against which the students built different resolution strategies favoring the development of their combinatorial thinking.

A presente pesquisa foi desenvolvida para entender como ocorre o processo de ensino e aprendizagem da Combinatória, no caso particular dos problemas de contagem de agrupamentos de objetos, considerado difícil por professores e alunos; e para elaborar e experimentar uma proposta didática, com potencial para trazer algo novo ao processo. Com base na Teoria dos Campos Conceituais de Vergnaud, delineou-se os esquemas de um grupo de alunos do ensino médio: resolvem problemas de contagem direta, mas não resolvem os que exigem multiplicação e divisão. Com a análise de outros trabalhos correlatos, pode-se concluir que o ensino tem melhores chances de iniciar com a resolução de problemas, e não a partir de formulários e definições. Consequência deste estudo, foi organizada e posta em prática uma sequência didática que parte da vivência do “jogo de pôquer”. Entende-se o baralho (sem coringas) como um conjunto de 52 objetos, a partir do qual devemos formar agrupamentos de 5 objetos (“mãos”). Os problemas propostos gerados pelo jogo podem ser resolvidos com as quatro operações aritméticas. Ao final, constatou-se evolução nos esquemas dos alunos, que passaram a utilizar a multiplicação com significado e a utilizar uma organização gráfica adequada para as soluções. Mas ainda apareceram erros no uso da divisão, que foram analisados para poder-se oferecer ao professor/leitor, compreensão das dificuldades. / This research was conducted to understand how the teaching and learning of Combinatorics is, in the particular case of counting issues and groupings of objects, which is considered difficult by teachers and students. Also aims to develop and experience a didactic proposal, with the potential to bring something new to the process. Based on Vergnaud's theory of Conceptual Fields, it was outlined schemes of a group of high school students: they solve problems of direct counting, but do not solve problems that require multiplication and division. With the analysis of other related work, we can conclude that a better way of teaching would be starting with problem solving, and not from formulas and definitions. As a result of this study a teaching sequence that takes advantage of the experience of the poker game, was organized and implemented. It is understood the deck (without wildcards) of 52 cards, from which we form groups of 5 objects ("hands"). The proposed problems generated by the game can be solved with the four arithmetic operations. At the end of our experience, we discover changes in the schemes of the students, who start using multiplication meaning and an organization suitable for finding solutions. We notice that still errors appeared in the use of division, which were analyzed in order to offer the teacher / reader the understanding of the difficulties of the students.

Uma revisão dos algoritmos e conjuntos de instâncias presentes na literatura do Problema da Mochila com Repetições (PMR) é apresentada nessa dissertação de mestrado. Os algoritmos e conjuntos de instâncias usados são brevemente descritos nesse trabalho, afim de que o leitor tenha base para entender as discussões. Algumas propriedades bem conhecidas e específicas do PMR, como a dominância e a periodicidade, são explicadas com detalhes. O PMR é também superficialmente estudado no contexto de problemas de avaliação gerados pela abordagem de geração de colunas aplicada na relaxação contínua do Bin Packing Problem (BPP) e o Cutting Stock Problem (CSP). Múltiplos experimentos computacionais e comparações são realizadas. Para os conjuntos de instâncias artificiais mais recentes da literatura, um simples algoritmo de programação dinâmica, e uma variante do mesmo, parecem superar o desempenho do resto dos algoritmos, incluindo aquele que era estado-da-arte. O modo que relações de dominância é aplicado por esses algoritmos de programação dinâmica têm algumas implicações para as relações de dominância previamente estudadas na literatura. O autor dessa dissertação defende a tese de que a escolha dos conjuntos de instâncias artificiais definiu o que foi considerado o melhor algoritmo nos trabalhos anteriores. O autor dessa dissertação disponibilizou publicamente todos os códigos e conjuntos de instâncias referenciados nesse trabalho. / A review of the algorithms and datasets in the literature of the Unbounded Knapsack Problem (UKP) is presented in this master's thesis. The algorithms and datasets used are brie y described in this work to provide the reader with basis for understanding the discussions. Some well-known UKP-speci c properties, such as dominance and periodicity, are described. The UKP is also super cially studied in the context of pricing problems generated by the column generation approach applied to the continuous relaxation of the Bin Packing Problem (BPP) and Cutting Stock Problem (CSP). Multiple computational experiments and comparisons are performed. For the most recent arti cial datasets in the literature, a simple dynamic programming algorithm, and its variant, seems to outperform the remaining algorithms, including the previous state-of-the-art algorithm. The way dominance is applied by these dynamic programming algorithms has some implications for the dominance relations previously studied in the literature. In this master's thesis we defend that choosing sets of arti cial instances has de ned what was considered the best algorithm in previous works. We made available all codes and datasets referenced in this master's thesis.

O objetivo de projetos de reforma agrária é redistribuir terras de grandes latifúndios para terrenos menores, com destino à agricultura familiar. Um dos principais problemas do Instituto Nacional de Colonização e Reforma Agrária (INCRA) é subdividir uma parcela grande de terra em lotes menores que são balanceados com relação a certos atributos. Este problema é difícil por que precisa considerar diversas restrições legais e éticas. As soluções atuais são auxiliadas por computador, mas manuais, demoradas e suscetíveis a erros, tipicamente produzindo lotes retangulares de áreas similares mas que são injustos com relação a critérios como aptidão do solo ou acesso a recursos hidrográficos. Nesta dissertação, nós propomos um algoritmo genético para gerar subdivisões justas de forma automática. Nós apresentamos um algoritmo construtivo guloso randomizado baseado em locação-alocação para gerar soluções iniciais, assim como operadores de mutação e recombinação que consideram especificidades do problema. Experimentos com 5 instâncias reais e 25 instâncias geradas artificialmente confirmam a efetividade dos diferentes componentes do método proposto, e mostram que ele gera soluções mais balanceadas que as atualmente usadas na prática. / The goal of agrarian reform projects is the redistribution of farmland from large latifundia to smaller, often family farmers. One of the main problems the Brazilian National Institute of Colonization and Agrarian Reform (INCRA) has to solve is to subdivide a large parcel of land into smaller lots that are balanced with respect to certain attributes. This problem is difficult since it considers several constraints originating from legislation as well as ethical considerations. Current solutions are computer-assisted, but manual, time-consuming and error-prone, leading to rectangular lots of similar areas which are unfair with respect to soil aptitude and access to hydric resources. In this thesis, we propose a genetic algorithm to produce fair land subdivisions automatically. We present a greedy randomized constructive heuristic based on location-allocation to generate initial solutions, as well as mutation and recombination operators that consider specifics of the problem. Experiments on 5 real-world and 25 artificial instances confirm the effectiveness of the different components of our method, and show that it leads to fairer solutions than those currently applied in practice.

Escalonamento de processos é um tipo de problema de otimização combinatória no qual devemos alocar máquinas à tarefas por períodos específicos de tempo. A literatura contém diversos estudos propondo técnicas para resolver modelos de escalonamento de processos como o job shop e o open shop. Esses modelos permitem que os passos no processo produtivo sejam ou completamente ordenados ou sem ordenação alguma. Com o aumento da complexidade das aplicações industriais no encontramos, mais recentemente, diversos trabalhos que propõe problemas de escalonamento de processos mais gerais para modelar mais precisamente os processos produtivos. O mixed shop, group shop e partial shop são exemplos de tais modelos. Nesse trabalho nós propomos uma busca tabu iterada para o partial shop, que é um modelo geral que inclui diversos modelos mais restritivos. Os componentes novos mais importantes da técnica são o gerador de solução inicial, a vizinhança e o limite inferior para a vizinhança. Em experimentos computacionais nós conseguimos demonstrar que a heurística genérica e única é capaz de competir, e as vezes superar, as técnicas de estado de arte desenvolvidas especificamente para partial, open, mixed e group shop. Algumas vezes uma máquina é o gargalo de um processo produtivo, e é replicada. Na literatura o caso das máquinas paralelas foi incluído em diversas extensões de problemas de escalonamento de processos. Nessa tese nós também propomos uma técnica para escalonar as máquinas paralelas, sem incluí-las explicitamente na representação do problema. Nós usamos técnicas gerais para os casos sem máquinas paralelas para produzir uma busca heurística tabu rápida, e estado da arte, para o caso do job shop com máquinas paralelas. / Shop scheduling is a combinatorial optimization type of problem in which we must allocate machines to jobs for specific periods time. A set of constraints defines which schedules are valid, and we must select one that minimizes or maximizes an objective function. In this work we use the makespan, which is the time the last job finishes. The literature contains several studies proposing techniques to solve shop problems such as the job shop and open shop. These problems allow the steps of the production processes to be either fully ordered or not ordered at all. With increasing complexity and size of industrial applications we find, more recently, several works which propose more general shop problems to model the production processes more accurately. The mixed shop, group shop and partial shop are examples of such problems In this work we propose an iterated tabu search for the partial shop, which is a general problem and includes several other more restrictive shop problems. The most important novel components of the solver are the initial solution generator, the neighbourhood, and the lower bound for the neighbourhood. In computational experiments we were able to show that the general partial shop solver is able to compete with, and sometimes surpass, the state-of-the-art solvers developed specifically for the partial, open, mixed and group shops. Sometimes a machine is a bottleneck in the production process, and is replicated. In the literature the parallel machines case has being included in several extensions of shop problems. In this thesis we also propose a technique to schedule the parallel machines heuristically, without including them explicitly in the representation of the problem. We use general techniques for the non-parallel machine cases to produce a fast tabu search heuristic results for the job shop with parallel machines.

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção. / Made available in DSpace on 2013-07-15T23:34:21Z (GMT). No. of bitstreams: 1 213308.pdf: 1767196 bytes, checksum: 35f6a544210e481c8ff2120e3be71f91 (MD5) / Este trabalho tem foco no plano de operação de empresas de transporte rodoviário regional de passageiros, visando à alocação da frota e dos condutores. Tem por objetivo desenvolver um modelo dinâmico, que permita corrigir os desvios ocorridos durante a execução do plano ao longo do horizonte de planejamento em tempo computacional razoável. Ambos os modelos, o de programação da frota e o de condutores, se resolvem através de um processo seqüencial de aplicação do algoritmo húngaro, e os resultados obtidos são comparados com limites inferiores, calculados pela relaxação de algumas restrições do problema. O modelo desenvolvido foi aplicado aos dados de uma empresa que atua nos estados de Santa Catarina e Rio Grande do Sul e os resultados obtidos são analisados.

Made available in DSpace on 2014-11-10T11:09:49Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-02-21Bitstream added on 2014-11-10T11:57:58Z : No. of bitstreams: 1 000794283.pdf: 7208938 bytes, checksum: 1b544d878aece0ee249ef10a5642c261 (MD5) / Neste trabalho o problema de Planejamento de Sistemas de Distribuição de Energia Elétrica (PSDEE) de Média Tensão é formulado em três modelos de programação não linear inteiro misto (PNLIM). O primeiro modelo realiza o planejamento estático de curto prazo que consiste em definir quais linhas serão instaladas e/ou recondutoradas e quais subestações serão construídas e/ou repotencializadas permitindo reconfigurar a rede já existente. Nesse contexto, o modelo matemático é mono-objetivo e minimiza custos de instalações de novos equipamentos e custos com operação do sistema sujeitos a um conjunto de restrições físicas, operacionais e econômicas. O segundo modelo é multiestágios e realiza o planejamento dinâmico de longo prazo considerando as mesmas ações de planejamento do modelo estático, mas define quando essas ações serão executadas. O terceiro modelo é multiobjetivo, além de realizar o planejamento dinâmico de longo prazo em diferentes estágios considerando custos de investimentos e operação inclui custos de confiabilidade da rede expressos em termos da energia não suprida. Para solução destes modelos são propostos diferentes versões do algoritmo de busca dispersa (BD), sendo duas mono-objetivo adaptadas para a solução dos modelos estáticos de curto prazo e dinâmico de longo prazo e a terceira multiobjetivo. A BD é uma técnica de busca evolucionária com estrutura flexível que permite o desenvolvimento de diversas implementações, com diferentes graus de complexidade. Como contribuição são detalhadas todas as etapas fundamentais do algoritmo na aplicação dos três modelos do problema de PSDEE utilizando o algoritmo de codificação sequencial aditiva e uma heurística para a seleção eficiente de condutores. O método é calibrado usando um sistema teste da literatura de 54 barras através de diversas simulações. A BD mostra-se competitiva ... / In this work the problem of Planning Electric Power Distribution Systems (PEPDS) of Medium Voltage is formulated in three mixed integer nonlinear programming (MINLP) models. The first model performs the static short-term planning that is to determine which lines will be installed and/or reconductive and substations which will be built and/or allowing repotentiated reconfigure the existing network. In this context, the mathematical model is mono objective and minimizes installation costs of new equipment and operating costs of the system subject to a set of physical, operational and economic constraints. The second model is multistage and performs dynamic long-term planning based on the same actions in planning the static model, but it defines when these actions are performed. The third model is multi objective, and it perform the dynamic long-term planning at different stages of considering investments and operating costs that it includes costs of network reliability expressed in terms of unserved energy. This way to solve these models are proposed different versions of Scatter Search (SS) algorithm, two adapters for the solution of static models of short term and long term dynamic multi objective mono, and third goal. The BD is an evolutionary search technique with a flexible structure which allows the development of diverse implementations of changeable degrees of complexity. As detailed contribution are all key steps of the algorithm in the application of the three models of the problem PEPDS using the additive sequential encoding algorithm and a heuristic for efficient selection of drivers. The method is calibrated using a testing systems of 54 buses through various simulations literature system. SS is exposed presenting optimal competitive good quality solution for mono objective to multi objective models and model. It is capable of finding a set of efficient solutions with commitment ...

Made available in DSpace on 2014-12-02T11:16:57Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-03-07Bitstream added on 2014-12-02T11:20:50Z : No. of bitstreams: 1 000796432.pdf: 2742498 bytes, checksum: 09b36b02c6140a3459c1567ce5096e34 (MD5) / Neste trabalho apresenta-se uma proposta para alocação de fontes renováveis em microrredes de energia elétrica para sistemas autônomos em corrente contínua através de um modelo matemático escrito como um problema quadrático inteiro misto (PQIM). O propósito do modelo matemático é minimizar os investimentos na instalação das fontes renováveis de energia e os custos relacionados com as perdas elétricas, atendendo as restrições de demandas de potências do sistema, limite da queda de tensão, capacidade de corrente dos condutores, máxima potência gerada pelo tipo de fonte renovável de energia alocada, capacidade máxima do número de fontes renováveis de energia a serem alocados em cada nó do sistema em estudo. Para resolver o problema foram utilizadas duas técnicas de solução. Primeiramente, foi usado o algoritmo de Branch and Bound (B&B) com a implementação do problema através da linguagem de modelagem algébrico (AMPL) e solucionado através do solver de otimização CPLEX, posteriormente o PQIM foi resolvido através do algoritmo genético Chu-Beasley implementado no MATrix LABoratory (MATLAB). Para o algoritmo de B&B implementou-se um método de redução do espaço de busca (EBCR), a fim de diminuir o tempo computacional. Para a validação do modelo matemático proposto, utilizou-se sistemas testes reais de 20, 99 e 297 nós, os quais são parte de um projeto de iluminação pública de um loteamento de residências populares do município de Ilha Solteira - SP, considerando alimentação em corrente contínua / This study mainly presents a proposal for allocation of renewable energy sources in a microgrid for autonomous electric systems that uses direct current through a mathematical model written as a mixed integer quadratic problem ( PQIM ). The purpose of the mathematical model is to minimize the investment at the renewable energy installation and the costs related to electrical losses, attending the restrictions of system powers demands, the voltage drop limit, the current capacity of conductors, the maximum power generated by type of renewable energy allocated, the maximum capacity of the number of renewable energy sources to be allocated on each node of the system under study. To solve the problem two solution techniques were used. First, was used the Branch and Bound algorithm (B&B) with the implementation of the problem through the language of algebraic modeling (AMPL) and solved by the solver optimization CPLEX , subsequently the PQIM was solved through Chu-Beasley genetic algorithm implemented in Matrix Laboratory (MATLAB). For the B&B algorithm, was implemented a method for reducing the search space(EBCR) in order to reduce computational time . To validate the proposed mathematical model , was used a real test system with 20, 99 and 297 nodes, which is part of a project of public lighting of a popular residential subdivision in Ilha Solteira - SP , considering power in direct current