Orientador: Helenice de Oliveira Florentino Silva / Coorientador: Daniela Renata Cantane / Banca: Adriano Rogerio Bruno Tech / Banca: Marco Antonio Gandolfo / Banca: Kleber Pereira Lanças / Banca: Antonio Roberto Balbo / Resumo: A cana-de-açúcar foi introduzida no Brasil no período colonial e transformou-se em uma das principais culturas da economia brasileira. O Brasil não é apenas o maior produtor de cana-de-açúcar, é também o primeiro do mundo na produção de açúcar e o segundo na produção de etanol, e conquista, cada vez mais, o mercado externo com o uso do biocombustível como alternativa energética. Essa posição foi alcançada devido ao crescimento acelerado nos últimos anos e contribuiu para o surgimento de problemas relacionados à logística de transporte, ao processo de produção, ao manejo e a tomada de decisão. Os problemas gerados por essa situação aos gestores do setor sucroalcooleiro são grandes e ferramentas para auxílio nas tomadas de decisões, manejos otimizados e para a obtenção de estimativas são necessárias. Dentro desse contexto, é abordado neste trabalho um estudo do manejo da colheita da cana-de-açúcar nas unidades agrícolas que compõem a usinas, propondo uma metodologia para auxiliar no planejamento otimizado da colheita da cana-de-açúcar de forma a maximizar a produção de POL (porcentagem em massa de sacarose aparente contida na cana-de-açúcar), a produção de cana-de-açúcar e respeitando restrições impostas pela usina. O processo de otimização foi realizado utilizando o Algorítmo Genético (AG), heurística utilizada em problemas combinatoriais de grande porte com grandes complexidades computacionais. Os períodos de colheita dos talhões pertencentes a uma unidade agrícola da usina foram planejados alcançando a máxima produtividade em um horizonte de planejamento de quatro anos. Os resultados numéricos obtidos são apresentaodos e discutidos no final do trabalho, mostrando que esta metodologia é uma importante ferramenta para auxilio dos gestores de usinas nas tomadas de decisões quanto ao planejamento da colheita da cana-de-açúcar / Abstract: Sugarcane was introduced in Brazil in the colonial period and it has become one of the most important crop for the Brazilian economy. Brazil is not only the largest sugarcane producer, but it is also the first in sugar production and the second in ethanol production and, increasingly, it has been conquering the international market with the biofuel use as an alternative energy. This position has been achieved due to accelerated growth in the last years and it has contributed to the emergence of issues related to logistical transport production process, management and decision making. The problems caused by this situation to the sugarcane management are large and tools to aid in decision making, management optimization and estimate are necessary. Within that context it is discussed, in this paper, a study of the sugarcane management harvest in the mills, proposing a methodology to assist in sugarcane harvest planning in order to maximize the POL in sugarcane, sugarcane productivity and respect the restrictions imposed by the mill. The optimization process was accomplished using GA, heuristic used in large combinatorial problems with computational complexity. Periods of harvesting in stands which belong to a mill were planned and the highest productivity was achieved in a four year planning. The results are presented and discussed at the end of this study, showing that this approach is an important tool to aid managers plants in decision-making in planning the harvest of sugarcane / Doutor

Orientadora: Carina Alves / Banca: Cintya Wikn de Oliveira Benedito / Banca: Fernando Eduardo Torres Orihuela / Resumo: Com os avanços da computação, a matemática discreta passou a ser objeto de novas e mais complexas pesquisas. Uma das razões é que os fundamentos da computação encontram-se nos princípios da matemática discreta. No que se refere aos centros de pesquisa, cada vez são mais numerosos e avanlçdos os trabalhos que visam dar sistematicidade e rigor aos princípios da matemática discreta como aqueles já conquistados pela matemática contínua. Nesse contexto, nossa proposta no presente trabalho, ao atuar na formação de base relativa ao ensino da matemática discreta no ensino médio, foi apresentar um texto que ao mesmo tempo compilasse tópicos que jé existe a respeito e, também, introduzisse novas questões e teorias que colocassem em compasso ensino médio com os significativos avanços da matemática discreta produzida nos grandes centros mundiais. Dentro dessas novas questões e teorias, privilegiamos a introdução das funções geradoras como assunto a ser abordado no ensino médio como aprendizado para eventuais desenvolvimentos posteriores no ensino superior, tanto das faculdades de matemática quanto das faculdades de computação. O presente trabalho apresenta-se como obra de base, redigida em linguagem acessível a professores e alunos do ensino médio, sem abrir mão do rigor necessário próprio dos estudos matemáticos / Abstract: Not available / Mestre

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

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.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / No problema do Caminho MÃnimo com RestriÃÃo ProbabilÃstica de Atraso MÃximo visamos considerar o fator tempo no projeto de rotas de transporte de cargas em malhas viÃrias a custo mÃnimo, atentando à crescente incerteza nos tempos de percurso dessas rotas em malhas reais, e observÃ-lo tendo em mente estratÃgias de qualidade de serviÃo, de forma a obtermos um compromisso entre o custo de percurso e a conformidade ao prazo de chegada ao destino. Realizamos um estudo de problemas relacionados na literatura da Ãrea de otimizaÃÃo em redes de transporte, de forma a tentarmos conhecer melhor o problema a ser estudado, sobre o qual nÃo tomamos conhecimento de trabalhos existentes. Desenvolvemos um esquema para enumeraÃÃo de partiÃÃes do espaÃo de soluÃÃes do problema, que utiliza uma decomposiÃÃo em L para selecionar partiÃÃes de forma inteligente, e que à auxiliado por soluÃÃes de relaxaÃÃes do problema de forma a obter cotas para o custo Ãtimo. AlÃm disso, desenvolvemos algumas estratÃgias de ramificaÃÃo e de poda para um esquema de Branch-and-Bound, com uma fase de prÃ-processamento, de forma a tentar resolver o problema diretamente. Os resultados computacionais obtidos demonstram que somos competitivos com a ferramenta comercial utilizada para comparaÃÃo em instÃncias de menor porte para o problema. Para as demais instÃncias, essa ferramenta se mostrou mais eficiente quanto ao tempo necessÃrio para a resoluÃÃo. / In the Probabilistic Delay Constrained Shortest Path problem we aim to consider the time factor in the design of cargo routing paths in road networks at minimum cost, considering the increasing uncertainty in travel times of these routes in real networks, and keeping in mind strategies of quality of service, in order to obtain a compromise between the travel costs and the compliance of the arrival time at the destination. We conducted a study of related problems in the literature of transport networks optimization, in order to better understand the problem to be addressed, about which we are not aware of existing works. We developed a scheme for enumerating partitions of the solution space of this problem, which uses an L decomposition to select these partitions wisely, and is aided by solutions to relaxations of the problem to obtain bounds for the optimal cost. In addition, we developed some branching and pruning strategies for a Branch-and-Bound scheme, with a pre-processing phase, in order to try and solve the problem directly. The computational results show that we are competitive with the commercial tool used for comparison in the smaller instances. For the remaining instances, this tool is more efficient in the time required for solving the problem.

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.

[pt] Consideramos o Problema Quadrático da Mochila 0-1 (QKP), que consiste em maximizar uma função booleana quadrática sujeito a uma restrição de capacidade linear. O problema possui aplicações em várias áreas, como por exemplo, telecomunicações. engenharia financeira, problemas de localização e teoria dos grafos (clique máximo). Propomos um algoritmo de Branch-and-Bound para resolver exatamente QKP, baseado em Relaxação Lagrangeana. Inicialmente, linearizamos a formulação do problema acima, e em seguida, aplicamos a técnica de relax-and-cut dinamicamente à relaxação contínua do problema, utilizando algumas classes de desigualdades válidas. O método do subgradiente é usado neste processo. Propomos também uma nova heurística primal para QKP, que obtém soluções melhores do que heurísticas propostas anteriormente, encontrando a solução ótima em todas as instâncias que consideramos. A boa qualidade dos limites superior e inferior é traduzida em gap`s pequenos no nó raiz da árvore de enumeração (em geral, menor do que 1%, inclusive para instâncias difíceis). Isto, aliado a testes de fixação de variáveis, permite resolver exatamente QKP em poucos nós da árvore de enumeração. Introduzimos uma maneira de gerar instâncias aleatórias mais difíceis do que as instâncias na literatura. Apresentamos resultados computacionais para instâncias geradas aleatoriamente (instâncias da literatura, e as novas instâncias mais difíceis) para QKP de tamanhos e densidades diferentes; e também para instâncias conhecidas do problema de clique máxima. / [en] We consider the 0-1 Quadratic Knapsack Problem (QKP), which consists of maximizing a quadratic Boolean function subject to a linear capacity constraint. The problem has applications in several areas such as telecommunications, financial engineering, location problems, graph theory (Max Clique). We propose a Branch-and-Bound algorithm to solve the QKP to optimality based on lagrangian Relaxation. Initially, we linearize the formulation of the problem given above and then we relax-and-cut dinamicaly its continous relaxation using a few classes of valid inequalities. In the process the Subgradient Method is applied. We also propose a new primal heuristic for the QKP that has improved upon previous approaches, and finds an optimal solution for all of the instances we considered. The good quality of our upper and lower bounds is translated into small gaps at the root node of the enumeration tree (usually below 1%, even for difficult instances). That, coupled with tests for fixing variables, allowed optimality to be proven within only a few nodes of the enumeration tree. We provide a way to randomly generate instances of the QKP harder than those in the literature. We report computational results for randomly generated instances (the ones in the literature and the new harder ones) of QKP with different densities and sizes; and also for Known instances of Max Clique problems.