Made available in DSpace on 2016-04-29T14:32:25Z (GMT). No. of bitstreams: 1 dissertacao_ines_esteves.pdf: 1398393 bytes, checksum: 00e85c0fe28a54174670dcf548180753 (MD5) Previous issue date: 2001-05-30 / The aim of this research was studying the acquisition and the development of the prime concepts about combinatory analyses among fourteen years old teenagers finishing the elementary school. In order to do this, we developed a teaching sequence based on psychological and educational theories, which belong to problem-situations through the direct county. We dealed with two groups: the experimental and the reference ones. These had done a previous test before beginning the new concept, and then studying the combinatory analyses based on two different approaches. While the experimental group did a study through a teaching sequence prepared by us, the reference group followed the traditional approach presented by didactic books. At the end both groups did a final test whose results were analyzed observing these points of view: general fulfilment of the groups and the fulfilment by items, targets and the individual one. At last, we proceeded the analyse of the behaviour among the three pairs of students from the experimental group based on their performances during the study. The results showed that the students presented troubles solving these problems. The main faillure motives were about the misunderstanding of the order combination problems; lack of organization to number systematically the data, doubts about the identification of equivalent arithmetic species and the wrong interpretation of the problem when this presented more than one stage / O objetivo desta pesquisa consistiu em estudar a aquisição e o desenvolvimento dos primeiros conceitos de análise combinatória em adolescentes de 14 anos de idade, cursando a última série do Ensino Fundamental. Para tal, construímos uma seqüência de ensino, fundamentada em teorias psicológicas e educacionais, que parte de situações-problema através da contagem direta. Trabalhamos com dois grupos: experimental e de referência. Estes se submeteram a um pré-teste antes de serem introduzidos nesse novo conceito, para, depois, estudarem o conceito de análise combinatória, segundo duas abordagens distintas. Enquanto o grupo experimental realizou o estudo através de uma seqüência de ensino elaborada por nós, o grupo de referência seguiu a abordagem tradicional apresentada pelos livros didáticos. Por fim, os dois grupos realizaram um pós-teste, cujos resultados foram analisados sob os seguintes pontos de vista: desempenho geral dos grupos e desempenho por itens, objetivo, indivíduo. Por fim, procedemos à análise do comportamento de três duplas do grupo experimental quanto a seus desempenhos ao longo do estudo. Os resultados mostram que os alunos apresentaram dificuldade em resolver esses problemas. As principais causas de fracasso são referentes à confusão sobre a relevância da ordem, principalmente em problemas de combinação, falta de organização para enumerar os dados sistematicamente, dúvidas na identificação da operação aritmética equivalente e interpretação incorreta do problema, quando este apresenta mais de uma etapa

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.

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.

Orientador: Rubén Augusto Romero Lázaro / Banca: Jose Roberto Sanches Mantovani / Banca: Sergio Azevedo de Oliveira / Banca: Antônio César Baleeiro Alves / Banca: Eduardo Nobuhiro Asada / Resumo: O problema de planejamento de sistemas de transmissão é um problema de programação não-linear inteira mista (PNLIM) quando é usado o modelo DC. Praticamente todos os algoritmos usados para resolver este problema utilizam uma subrotina de programação linear (PL) para resolver problemas de PL resultantes do algoritmo de solução do problema de planejamento. Às vezes a resolução desses problemas de PL representa o maior esforço computacional dos algoritmos de planejamento. A particularidade desses problemas de PL é que, na solução ótima, apenas algumas restrições de desigualdade estão ativas. Este trabalho considera a formulação e a implementação computacional de vários algoritmos de PL resultantes, ou seja, os algoritmos propostos fazem modificações nos problemas de PL resultantes dos modelos de transportes e DC de maneira que apresentam uma única restrição de igualdade, a equação de balanço de potência ativa, e muitas restrições de desigualdade. É usado um algoritmo dual simplex canalizado e uma estratégia de relaxação para resolver esses problemas de PL que inicia o processo de otimização com uma única restrição de igualdade e, em cada passo, é adicionada a restrição mais violada. Portanto, a lógica de trabalho é parecida com a proposta apresentada por Brian Stott para o planejamento da operação de sistemas elétricos. Os resultados encontrados mostram um desempenho superior do algoritmo quando comparados com métodos do tipo primal simplex. / Abstract: The transmission network planning problem is a non linear integer mixed programming problem (NLIMP) which used the DC model. Most of the algorithms used to solve this problem use a linear programming subroutine (LP) to solve LP problems resulting from planning algorithms. Sometimes the resolution of these LP problems represents a major computational effort of planning algorithms. The particularity of these LP problems in optimal solution is that only some inequality constraints are binding. This work considers the formulation and the computational implementation of algorithms several of the LP problems resulting, i.e., the proposed algorithms make modifications in the LP problems resulting of the transports and DC models so that present an only equality constraint, only one equality constraint, the power flow equation, and many inequality constraints. It is used a dual simplex algorithm and a relaxation strategy to solve these LP problems_ which start the optimization process with only one equality constraint and, in each step, the most unfeasible constraint is added. Then, the logic used is similar to the proposal presented in Brian Stott for electric systems operation planning. The results show a higher performance of the algorithm when compared to primal simplex methods. / Doutor

Orientador: Fernando Augusto Silva Marins / Coorientador: Aneirson Francisco da Silva / Banca: Valério Antonio Pamplona Salomon / Banca: Fabrício Maciel Gomes / Resumo: Esta dissertação trata da construção de um modelo matemático para a elaboração do quadro de horários dos cursos de graduação do CBV/IFRR. A programação de horários é um problema de otimização combinatória estudado há anos pela Pesquisa Operacional e, em termos de complexidade computacional, é tido como NP-Completo, sendo assim, é um problema que exige grande capacidade de processamento. A elaboração do quadro de horários em qualquer instituição de ensino é complexa e demanda tempo para os responsáveis por essa atividade, pois as necessidades dos professores e alunos devem ser atendidas e devem-se evitar conflitos nos horários dos professores. A instituição estudada nesta dissertação assim como outras instituições, possui particularidades institucionais, dessa forma, uma formulação geral do problema acaba não lhe sendo útil. O CBV/IFRR realiza a elaboração dos horários de forma manual, por meio de planilha eletrônica e realização de reuniões entre os gestores, o que torna difícil encontrar uma solução factível. Sendo assim, foi necessária a realização de pesquisa científica para encontrar métodos que poderiam ser aplicados ao problema. Assim, este trabalho teve como objetivo desenvolver um modelo de Programação Matemática que permitisse a elaboração dos horários para cursos de graduação do CBV/IFRR. Utilizou-se entrevistas com as Coordenações de Cursos para obtenção das informações acerca do problema tratado, tais como restrições e prioridades a serem atendidas com a programaç... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: This dissertation deals with the construction of a mathematical model for the elaboration of the timetable of the undergraduate courses of the CBV/IFRR. Time scheduling is a combinatorial optimization problem that has been studied for years by Operational Research and, in terms of computational complexity, is considered as NP-Complete, so it is a problem that requires large processing capacity. The elaboration of the timetable in any educational institution is complex and takes time for those responsible for this activity, because the needs of teachers and students must be met and avoid conflicts in the schedules of teachers. The institution studied in this dissertation as well as other institutions, has institutional features, so a general formulation of the problem ends up being of no use to it. The CBV/IFRR performs the elaboration of the schedules manually, through a spreadsheet and holding meetings between managers, which makes it difficult to find a feasible solution. Thus, it was necessary to carry out scientific research to find methods that could be applied to the problem. Thus, this work had the objective of developing a Mathematical Programming model that allowed the elaboration of the schedules for the undergraduate courses of the CBV/IFRR. We used interviews with the Course Coordinators to obtain information about the problem, such as constraints and priorities to be met with the programming of classes for teachers. This information was the basis for the construction of the conceptual model, which was used to elaborate the final mathematical model, which was implemented in the GAMS® high-level language and solved by the CPLEX® solver. The tests of the model were performed optimizing an instance with real data of the studied institution. The results obtained from the optimization were satisfactory, since it was possible to find an ... (Complete abstract click electronic access below) / Mestre

El manejo del lote de maíz tiene una influencia decisiva en la cantidad y calidad del silaje. La digestibilidad de los componentes del vegetal también varía por efecto del genotipo. Por lo tanto, la morfología o arquitectura del cultivo condiciona su calidad. Gran parte de la selección se ha realizado en materiales destinados a la producción de grano, careciéndose de suficiente información sobre el comportamiento de los demás componentes de la planta, así como también sobre la respuesta de la calidad. Nuestras necesidades de genotipos generalmente no son coincidentes con las de países del hemisferio norte, requiriendo realizar tareas de investigación y desarrollo que respondan a demandas regionales y muchas veces coyunturales. Debido a razones genéticas y económicas, el mejoramiento del maíz para silaje debería combinar la mejora alcanzada en el maíz para grano con las necesidades específicas de los híbridos para silaje. La estabilidad en la producción es una cualidad esencial, sobre todo cuando el maíz se destina a silaje, ya que su área de siembra no coincide con los ambientes agronómicos más adecuados para expresar su máximo potencial. En condiciones no óptimas se obtienen rendimientos bajos y antieconómicos. Esta situación determina que la selección de genotipos debe tener en cuenta los criterios de interacción genotipo × ambiente (G × A) y de estabilidad-adaptabilidad. Se han utilizado un amplio número de métodos multivariantes para analizar los ensayos multilocales y estimar la estabilidad de una determinada variable. En alguno de ellos se superan las limitaciones de la regresión lineal, pero los resultados son, a menudo, difíciles de interpretar en relación con la interacción G × A. Otras técnicas multivariantes, o combinaciones de las mismas, ofrecen una información biológica relevante y son estadísticamente confiables, como el AMMI. Los objetivos de la tesis fueron: a.- Cuantificar el efecto ambiental, genético y su respectiva interacción sobre los caracteres cuali-cuantitativos que condicionan la aptitud forrajera. b.- Detectar posibles grupos heteróticos para aptitud forrajera entre las líneas evaluadas y sugerir la formación de potenciales patrones heteróticos. c.- Identificar líneas endocriadas aptas para intervenir en la formación de híbridos con aptitud forrajera. d.- Diferenciar líneas endocriadas a través de la respuesta a los cambios ambientales de los híbridos donde intervienen. Como hipótesis se propuso que la variabilidad de la aptitud forrajera entre líneas endocriadas de maíz tiene condicionada su expresión por el efecto ambiental. Esta variabilidad y su interacción con el ambiente se manifiesta solamente en caracteres relacionados con el rendimiento y no con la calidad. En consecuencia, se generan aptitudes diferenciales, según se evalúen sus cruzamientos para producción de grano o de forraje. La determinación de valores genéticos en las fracciones que componen la planta, tales como los efectos y las variancias de las ACG (Aptitud Combinatoria General) y ACE (Aptitud Combinatoria Específica), como sus interacciones con el ambiente, permitirían planear estrategias de mejoramiento con mayores probabilidades de éxito. Se seleccionaron diez líneas endocriadas de maíz que representan un amplio rango de orígenes raciales, madurez, y tipo de grano. Se evaluaron los 45 cruzamientos provenientes de un esquema dialélico sin recíprocos, generados por las 10 líneas endocriadas y tres testigos comerciales destacados por su aptitud forrajera en 6 ambientes de la Provincia de Buenos Aires durante 3 años. Se evaluaron caracteres de importancia forrajera relacionados con la morfología de la planta, su rendimiento y la calidad nutricional. Para el análisis estadístico se realizó un ANVA para todas las variables y de acuerdo a los resultados se realizaron los análisis de AMMI y Coordenadas Principales en aquellas variables que resultaron significativas. Posteriormente se calcularon las ACG y ACE y su Importancia Relativa (IRAC). El análisis combinado a través de las localidades para casi todas las variables evaluadas mostró alta significancia estadística para Ambientes, Genotipos y su respectiva interacción. Se encontraron diferencias significativas entre Genotipos, tanto para los Cruzamientos como para los Testigos, para todas las variables, con excepción de las relacionadas con la calidad. Las interacciones G × A para las variables relacionadas con la digestibilidad fueron significativas, aunque de bajo valor. El efecto ambiental explicó más del 50 % de variabilidad de los tratamientos para aquellas variables relacionadas con la espiga y otras variables tales como Altura de Planta, Índice de Cosecha y Digestibilidad de Caña+Hojas. Para las variables asociadas a la caña + hojas y a la planta completa, el efecto “Genotipo” fue el más importante superando el 45 % de la variabilidad de los tratamientos. La interacción G × A explicó un porcentaje bajo de la variación de los tratamientos (entre el 7 al 20 %). Los residuales más altos fueron para las variables asociadas a la planta completa (RT, RDT y DT), indicando un mayor ruido o altos efectos no predecibles. Los ambientes demostraron un patrón de comportamiento diferencial frente a las variables de calidad y de cantidad. Se aplicaron los análisis posdictivos y predictivos de AMMI para validar los valores generados en el Análisis de Varianza. De esta forma se pudo despejar de los efectos significativos el ruido generado por el error ambiental. El ACOOP permitió destacar a.- los genotipos superiores y en que ambiente sobresalieron; b.- identificar a los genotipos estables observando aquellos que, consistentemente, sobresalieron en los ciclos sucesivos conforme se fueron incorporando nuevos ambientes y c.- discriminar la capacidad y representatividad de los ambientes testeados. La técnica es más confiable cuando los genotipos se prueban en ambientes extremos. La varianza de la ACG excedió considerablemente a la de la ACE para todos caracteres agronómicos evaluados y para los relacionados con la calidad, en cruzamientos Flint × Dentados, excepto para el rendimiento en grano. Por lo tanto, podría ser posible explotar la variabilidad genotípica tanto para el componente vegetativo como para grano. Se verificó la existencia de un neto predominio de los efectos aditivos, en todas las variables evaluadas, exceptuando las relacionadas con la calidad de los componentes de la planta. Las metodologías empleadas (AMMI y ACOOP) han permitido el cumplimiento de los objetivos planteados en su totalidad. Esta última se evidenció como la más adecuada que él para seleccionar genotipos destacados simultáneamente por producción y estabilidad. La magnitud de la interacción G × A no tendría mayoritariamente una explicación biológica, pudiendo ser considerada como ruido y, por consiguiente, podría ser disminuida controlando las variables experimentales. Contrariamente, las variables asociadas a producción de grano, ciclo y altura de planta fueron mayormente influidas por el ambiente. El porcentaje de determinación calculado para las variables asociadas a la cantidad y calidad de caña+hojas señaló un importante componente genético que supera en magnitud dos veces el valor del componente ambiental y de su interacción G × A. Esto indicaría que es posible avanzar en los programas de selección relacionados con el aumento de la producción de materia seca, y de su calidad, más fácilmente que en el pasado se ha hecho con las variables asociadas a la producción de grano. Se detectaron varios patrones heteróticos potenciales, capaces de generar híbridos competitivos, en rendimiento y estabilidad, tales como Reid-BSSS (B84 y A632) × materiales argentinos flint bastante antiguos (ZN6 y P465), ya utilizados para grano, pero sin información hasta la fecha para planta completa. Se evidenció una capacidad diferencial en los genotipos para aportar avances en cada uno de los componentes del vegetal (Espiga o caña+hojas). La digestibilidad del componente vegetativo (Caña + hojas) y el rendimiento de espiga deben ser los objetivos principales en la búsqueda de variabilidad. Se considera, que al no rechazar la hipótesis enunciada, surge la necesidad de desarrollar nuevos genotipos que posean características propias, diferenciadas netamente de las deseadas para materiales graníferos.

Made available in DSpace on 2014-06-11T19:30:52Z (GMT). No. of bitstreams: 0 Previous issue date: 2005-04-29Bitstream added on 2014-06-13T19:00:51Z : No. of bitstreams: 1 hashimoto_shm_dr_ilha.pdf: 3505990 bytes, checksum: 86eb5da27160760afefec6614a16a090 (MD5) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / O problema de planejamento de sistemas de transmissão é um problema de programação não-linear inteira mista (PNLIM) quando é usado o modelo DC. Praticamente todos os algoritmos usados para resolver este problema utilizam uma subrotina de programação linear (PL) para resolver problemas de PL resultantes do algoritmo de solução do problema de planejamento. Às vezes a resolução desses problemas de PL representa o maior esforço computacional dos algoritmos de planejamento. A particularidade desses problemas de PL é que, na solução ótima, apenas algumas restrições de desigualdade estão ativas. Este trabalho considera a formulação e a implementação computacional de vários algoritmos de PL resultantes, ou seja, os algoritmos propostos fazem modificações nos problemas de PL resultantes dos modelos de transportes e DC de maneira que apresentam uma única restrição de igualdade, a equação de balanço de potência ativa, e muitas restrições de desigualdade. É usado um algoritmo dual simplex canalizado e uma estratégia de relaxação para resolver esses problemas de PL que inicia o processo de otimização com uma única restrição de igualdade e, em cada passo, é adicionada a restrição mais violada. Portanto, a lógica de trabalho é parecida com a proposta apresentada por Brian Stott para o planejamento da operação de sistemas elétricos. Os resultados encontrados mostram um desempenho superior do algoritmo quando comparados com métodos do tipo primal simplex. / The transmission network planning problem is a non linear integer mixed programming problem (NLIMP) which used the DC model. Most of the algorithms used to solve this problem use a linear programming subroutine (LP) to solve LP problems resulting from planning algorithms. Sometimes the resolution of these LP problems represents a major computational effort of planning algorithms. The particularity of these LP problems in optimal solution is that only some inequality constraints are binding. This work considers the formulation and the computational implementation of algorithms several of the LP problems resulting, i.e., the proposed algorithms make modifications in the LP problems resulting of the transports and DC models so that present an only equality constraint, only one equality constraint, the power flow equation, and many inequality constraints. It is used a dual simplex algorithm and a relaxation strategy to solve these LP problems_ which start the optimization process with only one equality constraint and, in each step, the most unfeasible constraint is added. Then, the logic used is similar to the proposal presented in Brian Stott for electric systems operation planning. The results show a higher performance of the algorithm when compared to primal simplex methods.

Orientador: Cristiane Nespoli Morelato França / Banca: José Roberto Nogueira / Banca: Dayene Miralha de Carvalho Sano / Resumo: O presente trabalho tem o objetivo de apresentar o Princípio Fundamental da Contagem (PFC) através da metodologia de Resolução de Problemas, dando ênfase na prática pedagógica com questões da Olimpíada Brasileira de Matemática das Escolas Públicas (OBMEP). Tendo como base essa concepção de ensino, elaboramos uma sequência didática que trouxe, dentro do tema da Análise Combinatória, o PFC, a qual aplicamos em uma sala do 6º ano do Ensino Fundamental - Anos Finais, na Escola Estadual "Parque das Nações", localizada no munícipio de Bastos, interior de São Paulo. Tal sequência foi composta por questões da OBMEP adaptadas, levando em conta o fato de que elas contemplam os conteúdos, as competências e habilidades que fazem referência ao PFC e estão presentes no Currículo do Estado de São Paulo: Matemática e Suas Tecnologias (CESPMT) e nos Parâmetros Curriculares Nacionais (PCN). As atividades desenvolvidas apresentaram situações desafiadoras, eram contextualizadas de modo a se aproximar da realidade do aluno e permitir a utilização de materiais didáticos concretos, além de favorecer a socialização, o debate de ideias e o enriquecimento do currículo. No decorrer do trabalho prático, no que diz respeito ao PFC, verificamos que os alunos foram capazes de identificar as decisões que deveriam ser tomadas e traçar estratégias para resolver o problema. Além disso, eles também perceberam a importância da ordem em que essas decisões deveriam ser tomadas para tornar menos complexo o procedimento... / Abstract: The present work has the objective of presenting the Fundamental Principle of Counting (FPC) through the Problem Solving methodology, emphasizing pedagogical practice with issues of the Brazilian Olympiad of Mathematics of Public Schools (OBMEP). Based on this conception of teaching, we elaborated a didactic sequence that brought, within the theme of Combinatorial Analysis, the FPC, which we apply in a room of the 6th year of elementary school - Final Years, at the "Parque das Nações" State School, located in the municipality of Bastos, in the interior of São Paulo. This sequence was made up of adapted OBMEP issues, taking into account the fact that they contemplate the contents, skills and abilities that refer to the FPC and are present in the São Paulo State Mathematics and Technology Technologies Curriculum and National Curricular Parameter. The activities developed presented challenging situations, were contextualized in order to approach the reality of the student and to allow the use of concrete didactic materials, besides favoring the socialization, the debate of ideas and the enrichment of the curriculum. In the course of the practical work, with regard to the FPC, we found that the students were able to identify the decisions that should be made and to devise strategies to solve the problem. In addition, they also realized the importance of the order in which these decisions should be made to make the resolution procedure less complex, always starting with the one with the most restrictions. In the evaluation of the results obtained from the application of the selected activities, we perceive an improvement both in the learning and the motivation of the students, and that, therefore, it is advisable to work, from the beginning of Elementary School, with emphasis in the FPC, through Troubleshooting / Mestre

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.