Neste trabalho desenvolvemos o estudo da álgebra linear, secções cônicas e aplicações. Apresentamos os conceitos mais importantes da álgebra linear, estudando os espaços vetorias, subespaços vetoriais, matriz de mudança de base, transformações lineares e produto interno. O principal resultado do trabalho é o teorema espectral que fornece ferramentas para se estudar as secções cônicas não elementares, ou seja, aquelas nas quais uma parábola, elipse ou hipérbole são apresentadas com seus eixos não paralelos aos eixos coordenados do plano cartesiano. Uma vez de posse deste teorema é mostrado um processo prático no qual transformamos uma equação ax2 +bxy +cy2 +dx +ey + g = 0 na equação k1 (x\')2 + k2 (y\')2 + (dx1 + ey1) x\' + (dx2 + ey2) y\' + g = 0 sem o termo misto xy, onde após a eliminação deste, podemos deduzir a equação da cônica identificando assim esta curva. Apresentamos exemplos de cônicas com eixos paralelos e não paralelos aos coordenados do plano cartesiano e utilizamos o software geogebra para visualização. Também discutimos algumas aplicações das cônicas como trajetória de corpos celestes (planeta Terra e um cometa), princípio de reflexão da parábola mostrando o porquê das antenas e dos captadores de ondas sonoras serem parabólicos. Demonstramos um teorema que denominei de identificador de uma curva cônica pois com ele é possível classificar a cônica sem realizar o processo prático, apenas para isso identificamos através da equação ax2 +bxy + cy2 +dx + ey +g = 0, quais os valores de a;b e c e feito isto calculamos o discriminante b2 - 4ac, analisamos os sinais e a nulidade, ou seja, se é maior que zero, menor que zero ou igual a zero, assim é possível classificar a cônica. / The paper develops the study of linear algebra, conic sections and applications. I present the most important concepts of linear algebra, studying vector spaces, vector subspaces, base change matrix, linear transformations, internal product. The main result of the work is the spectral theorem, which provides tools to study the non-elementary conic sections, that is, those in which a parabola, ellipse or hyperbola are presented with their axes not parallel to the cartesian planes coordinate axes. Using this theorem we show a practical process in which we transform an equation ax2 +bxy + cy2 +dx +ey +g = 0 into the equation k1 (x\')2 +k2 (y\')2 + (dx1 +ey1) x\' (dx2 + ey2) y\' +g = 0 without the mixed term xy, where after its elimination we can deduce the conic equation thus identifying the curve we are looking for. I present examples of conic with parallel and non-parallel axes to the coordinates of the Cartesian plane and use the geogebra software for visualization. I discuss some applications of the conic as a trajectory of celestial bodies (planet Earth and a comet), principle of reflection of parabola showing why the antennas and sound wave pickups are parabolics. I demonstrate a theorem that I named the identifier of a conic curve, with it it is possible to classify the conic without realizing the practical process only for this. I identify through the equation ax2 +bxy + cy2 +dx + ey + g = 0, what are the values of a;b, and c and, with this done, I compute the discriminant b2 - 4ac and analyze the signs and the nullity, that is, if it is greater than zero, less than zero or equal to zero, therefore is possible to classify the conic.

Irregular cutting and packing problems, with convex and non-convex polygons, are found in many industries such as metal mechanics, textiles, of shoe making, the furniture making and others. In this thesis we study the two-dimensional version of these problems, where we want to allocate a set of items, without overlap, inside one or more containers, limited or unlimited, so as to optimize an objective function. In this document we study the knapsack problem, placement problem, strip packing problem, cutting stock problem and bin packing problem. For these problems, the heuristic methods and mathematical programming models are proposed and presented very promising results, surpassing in many cases the best results in the specialized literature. This thesis is organized as follows. In Chapter 1, we present a review of the studied problems, the value proposition for this thesis with the main contributions and ideas. In Chapter 2, we propose a metaheursitic for the strip packing problem with irregular items and circles. Then, in Chapter 3, we present a generic heuristic for the allocation of irregular items that may be weakly or strongly heterogeneous and will be allocated in a container (output maximization problems) or multiple containers (input minimization problems). In Chapter 4, we propose a solution method for the cutting stock problem with deterministic demand and stochastic demand. In Chapters 5 and 6, we present mathematical programming models for the strip packing problem. Finally, in Chapter 7, we present a conclusion and a concise direction for future works. / Os problemas de corte e empacotamento de itens irregulares, polígonos convexos e não convexos, são encontrado em diversas indústrias, tais como a metal-mecânica, a têxtil, a de calçados, a moveleira e outras. Nesta tese estudamos a versão bidimensional destes problemas, na qual desejamos alocar um conjunto de itens, sem sobreposição, no interior de um ou mais recipientes, limitados ou ilimitados, de modo a otimizar uma função objetivo. Neste trabalho estudamos o problema da mochila, o problema do assentamento, o problema empacotamento em faixa, o problema de corte de estoque e o problema de empacotamento de contêineres. Para estes problemas, os métodos heurísticos e modelos de programação matemática propostos e apresentam resultados muito promissores, ultrapassando em muitos casos os melhores resultados da literatura especializada. Esta tese esta organizada da seguinte maneira. No Capítulo 1, apresentamos uma revisão dos problemas estudados, a proposta de valor deste doutorado com as principais contribuições e ideias. No Capítulo 2, propomos uma meta-heurística para o problema de empacotamento em faixa para itens irregulares e círculos. Em seguida, no Capítulo 3 apresentamos uma heurística genérica para a alocação de itens irregulares que podem ser fracamente ou fortemente heterogêneos e serão alocados em um recipiente (problema de maximização de saída) ou de múltiplos recipientes (problemas de minimização de entrada). O Capítulo 4 propõem um método de solução para o problema de corte de estoque com demanda conhecida e demanda estocástica. Nos Capítulos 5 e 6 apresentamos modelos de programação matemática para o problema de corte de itens irregulares em faixa. Finalmente, no Capítulo 7, apresentamos a conclusão e uma sucinta direção para os trabalhos futuros.

O problema de empacotamento de itens irregulares com balanceamento da carga é encontrado no carregamento de aviões, caminhões e navios. O objetivo é empacotar itens irregulares utilizando o menor número de recipientes possível de forma que os recipientes estejam balanceados, que os itens não se sobreponham e estejam inteiramente contidos no recipiente. Neste trabalho, propomos três heurísticas bases com três variações cada para o problema com recipientes retangulares e irregulares. As heurísticas utilizam abordagens diferentes para representar os itens e para fazer o balanceamento. Uma das heurísticas utiliza malha para representação dos itens e faz o balanceamento dividindo o recipiente em quadrantes e revezando a alocação dos itens entre eles de forma que o balanceamento é feito de forma indireta. Tal heurística resolve o problema tanto para recipientes retangulares quanto irregulares. A segunda heurística utiliza a representação dos itens por polígonos e impossibilita a sobreposição de itens utilizando a técnica do nofit polygon. A heurística constrói a solução item por item, sem posições fixas e a cada item alocado, os itens são deslocados em direção ao centro de gravidade desejado do recipiente. Esta heurística resolve apenas problemas com recipientes retangulares. A última heurística é uma adaptação da heurística anterior para a resolução do problema com recipientes irregulares, de forma que o problema é resolvido em duas fases. Cada heurística base possui três variações cada, totalizando nove heurísticas. As heurísticas foram comparadas com outro trabalho da literatura e conseguiram melhorar os resultados para nove das dezenove instâncias testadas. / The irregular bin packing problem with load balancing is found in the loading of airplanes, trucks and ships. The aim is to use as few bins as possible to pack all the items so that all bins are balanced, items do not overlap and are fully contained in the bin. In this work, we propose three base heuristics with three variations each for the problem with rectangular and irregular bin. The three heuristics use different approaches to represent the items and to balance the bin. One of the heuristics uses a grid to represent the items and does the balancing by dividing the container into quadrants and alternating the allocation of items between them so that the balancing is done indirectly. Such heuristic solves the problem for both rectangular and irregular bins. The second heuristic uses the representation of items by polygons and uses the nofit polygon technique. The heuristic constructs the solution item by item, with no fixed positions and with each item allocated, the items are shifted towards the desired center of gravity of the bin. This heuristic only solves problems with rectangular bins. The last heuristic is an adaptation of the previous one to solve the problem with irregular bins, so that the problem is solved in two phases. Each base heuristic has three variations, totaling nine heuristics. The heuristics were compared with other work in the literature and managed to improve the results for nine of the nineteen instances tested.

Irregular cutting and packing problems, with convex and non-convex polygons, are found in many industries such as metal mechanics, textiles, of shoe making, the furniture making and others. In this thesis we study the two-dimensional version of these problems, where we want to allocate a set of items, without overlap, inside one or more containers, limited or unlimited, so as to optimize an objective function. In this document we study the knapsack problem, placement problem, strip packing problem, cutting stock problem and bin packing problem. For these problems, the heuristic methods and mathematical programming models are proposed and presented very promising results, surpassing in many cases the best results in the specialized literature. This thesis is organized as follows. In Chapter 1, we present a review of the studied problems, the value proposition for this thesis with the main contributions and ideas. In Chapter 2, we propose a metaheursitic for the strip packing problem with irregular items and circles. Then, in Chapter 3, we present a generic heuristic for the allocation of irregular items that may be weakly or strongly heterogeneous and will be allocated in a container (output maximization problems) or multiple containers (input minimization problems). In Chapter 4, we propose a solution method for the cutting stock problem with deterministic demand and stochastic demand. In Chapters 5 and 6, we present mathematical programming models for the strip packing problem. Finally, in Chapter 7, we present a conclusion and a concise direction for future works. / Os problemas de corte e empacotamento de itens irregulares, polígonos convexos e não convexos, são encontrado em diversas indústrias, tais como a metal-mecânica, a têxtil, a de calçados, a moveleira e outras. Nesta tese estudamos a versão bidimensional destes problemas, na qual desejamos alocar um conjunto de itens, sem sobreposição, no interior de um ou mais recipientes, limitados ou ilimitados, de modo a otimizar uma função objetivo. Neste trabalho estudamos o problema da mochila, o problema do assentamento, o problema empacotamento em faixa, o problema de corte de estoque e o problema de empacotamento de contêineres. Para estes problemas, os métodos heurísticos e modelos de programação matemática propostos e apresentam resultados muito promissores, ultrapassando em muitos casos os melhores resultados da literatura especializada. Esta tese esta organizada da seguinte maneira. No Capítulo 1, apresentamos uma revisão dos problemas estudados, a proposta de valor deste doutorado com as principais contribuições e ideias. No Capítulo 2, propomos uma meta-heurística para o problema de empacotamento em faixa para itens irregulares e círculos. Em seguida, no Capítulo 3 apresentamos uma heurística genérica para a alocação de itens irregulares que podem ser fracamente ou fortemente heterogêneos e serão alocados em um recipiente (problema de maximização de saída) ou de múltiplos recipientes (problemas de minimização de entrada). O Capítulo 4 propõem um método de solução para o problema de corte de estoque com demanda conhecida e demanda estocástica. Nos Capítulos 5 e 6 apresentamos modelos de programação matemática para o problema de corte de itens irregulares em faixa. Finalmente, no Capítulo 7, apresentamos a conclusão e uma sucinta direção para os trabalhos futuros.

Neste trabalho desenvolvemos o estudo da álgebra linear, secções cônicas e aplicações. Apresentamos os conceitos mais importantes da álgebra linear, estudando os espaços vetorias, subespaços vetoriais, matriz de mudança de base, transformações lineares e produto interno. O principal resultado do trabalho é o teorema espectral que fornece ferramentas para se estudar as secções cônicas não elementares, ou seja, aquelas nas quais uma parábola, elipse ou hipérbole são apresentadas com seus eixos não paralelos aos eixos coordenados do plano cartesiano. Uma vez de posse deste teorema é mostrado um processo prático no qual transformamos uma equação ax2 +bxy +cy2 +dx +ey + g = 0 na equação k1 (x\')2 + k2 (y\')2 + (dx1 + ey1) x\' + (dx2 + ey2) y\' + g = 0 sem o termo misto xy, onde após a eliminação deste, podemos deduzir a equação da cônica identificando assim esta curva. Apresentamos exemplos de cônicas com eixos paralelos e não paralelos aos coordenados do plano cartesiano e utilizamos o software geogebra para visualização. Também discutimos algumas aplicações das cônicas como trajetória de corpos celestes (planeta Terra e um cometa), princípio de reflexão da parábola mostrando o porquê das antenas e dos captadores de ondas sonoras serem parabólicos. Demonstramos um teorema que denominei de identificador de uma curva cônica pois com ele é possível classificar a cônica sem realizar o processo prático, apenas para isso identificamos através da equação ax2 +bxy + cy2 +dx + ey +g = 0, quais os valores de a;b e c e feito isto calculamos o discriminante b2 - 4ac, analisamos os sinais e a nulidade, ou seja, se é maior que zero, menor que zero ou igual a zero, assim é possível classificar a cônica. / The paper develops the study of linear algebra, conic sections and applications. I present the most important concepts of linear algebra, studying vector spaces, vector subspaces, base change matrix, linear transformations, internal product. The main result of the work is the spectral theorem, which provides tools to study the non-elementary conic sections, that is, those in which a parabola, ellipse or hyperbola are presented with their axes not parallel to the cartesian planes coordinate axes. Using this theorem we show a practical process in which we transform an equation ax2 +bxy + cy2 +dx +ey +g = 0 into the equation k1 (x\')2 +k2 (y\')2 + (dx1 +ey1) x\' (dx2 + ey2) y\' +g = 0 without the mixed term xy, where after its elimination we can deduce the conic equation thus identifying the curve we are looking for. I present examples of conic with parallel and non-parallel axes to the coordinates of the Cartesian plane and use the geogebra software for visualization. I discuss some applications of the conic as a trajectory of celestial bodies (planet Earth and a comet), principle of reflection of parabola showing why the antennas and sound wave pickups are parabolics. I demonstrate a theorem that I named the identifier of a conic curve, with it it is possible to classify the conic without realizing the practical process only for this. I identify through the equation ax2 +bxy + cy2 +dx + ey + g = 0, what are the values of a;b, and c and, with this done, I compute the discriminant b2 - 4ac and analyze the signs and the nullity, that is, if it is greater than zero, less than zero or equal to zero, therefore is possible to classify the conic.

O problema de empacotamento de itens irregulares com balanceamento da carga é encontrado no carregamento de aviões, caminhões e navios. O objetivo é empacotar itens irregulares utilizando o menor número de recipientes possível de forma que os recipientes estejam balanceados, que os itens não se sobreponham e estejam inteiramente contidos no recipiente. Neste trabalho, propomos três heurísticas bases com três variações cada para o problema com recipientes retangulares e irregulares. As heurísticas utilizam abordagens diferentes para representar os itens e para fazer o balanceamento. Uma das heurísticas utiliza malha para representação dos itens e faz o balanceamento dividindo o recipiente em quadrantes e revezando a alocação dos itens entre eles de forma que o balanceamento é feito de forma indireta. Tal heurística resolve o problema tanto para recipientes retangulares quanto irregulares. A segunda heurística utiliza a representação dos itens por polígonos e impossibilita a sobreposição de itens utilizando a técnica do nofit polygon. A heurística constrói a solução item por item, sem posições fixas e a cada item alocado, os itens são deslocados em direção ao centro de gravidade desejado do recipiente. Esta heurística resolve apenas problemas com recipientes retangulares. A última heurística é uma adaptação da heurística anterior para a resolução do problema com recipientes irregulares, de forma que o problema é resolvido em duas fases. Cada heurística base possui três variações cada, totalizando nove heurísticas. As heurísticas foram comparadas com outro trabalho da literatura e conseguiram melhorar os resultados para nove das dezenove instâncias testadas. / The irregular bin packing problem with load balancing is found in the loading of airplanes, trucks and ships. The aim is to use as few bins as possible to pack all the items so that all bins are balanced, items do not overlap and are fully contained in the bin. In this work, we propose three base heuristics with three variations each for the problem with rectangular and irregular bin. The three heuristics use different approaches to represent the items and to balance the bin. One of the heuristics uses a grid to represent the items and does the balancing by dividing the container into quadrants and alternating the allocation of items between them so that the balancing is done indirectly. Such heuristic solves the problem for both rectangular and irregular bins. The second heuristic uses the representation of items by polygons and uses the nofit polygon technique. The heuristic constructs the solution item by item, with no fixed positions and with each item allocated, the items are shifted towards the desired center of gravity of the bin. This heuristic only solves problems with rectangular bins. The last heuristic is an adaptation of the previous one to solve the problem with irregular bins, so that the problem is solved in two phases. Each base heuristic has three variations, totaling nine heuristics. The heuristics were compared with other work in the literature and managed to improve the results for nine of the nineteen instances tested.

Os problemas de empacotamento de itens irregulares são problemas de corte e empacotamento, nos quais peças irregulares de menor tamanho (que chamamos de itens) devem ser empacotados inteiramente em uma peça grande (que chamamos de placa), obedecendo a restrições de nãosobreposição e minimizando as dimensões da placa. Para garantir a não-sobreposição, fazemos uso de retas separadoras, quer dizer, retas que separam um item de outro. Apresentamos modelos de programação não-linear para problemas de empacotamentos de itens regulares e irregulares que rotacionam livremente. Os itens podem ser círculos, polígonos convexos e não-convexos. A principal vantagem dos modelos é a simplicidade, já que estes utilizam somente conceitos básicos de geometria. Usamos o algoritmo de programação não-linear IPOPT (um algoritmo de tipo de pontos interiores), que faz parte da COIN-OR, para a resolução dos problemas. Testes computacionais foram executados usando instâncias conhecidas da literatura e os resultados foram comparados com resultados apresentados na literatura, obtidos com outras metodologias que também usam rotações livre, mostrando que nossos modelos são competitivos. Propomos também o uso de parábolas separadoras para a verificação de não-sobreposição na modelagem do problema, o que pode trazer ganhos computacionais e melhor qualidade de soluções. / The irregular packing problems are cutting and packing problems, in which smaller irregular pieces (which we call items) should be packaged entirely in one large piece (which we call a plate), obeying non-overlapping constraints and minimizing the dimensions of the plate. To ensure non-overlapping, we make use of separation lines, that is, lines that separate one item from another. We present nonlinear programming models for problems of packing regular and irregular items that rotate freely. The items can be circles, convex and nonconvex polygons. The main advantage of the models is their simplicity, because they use only basic geometry concepts. We use the nonlinear programming algorithm IPOPT (an algorithm of interior points type), which is part of COIN-OR, to solve the problems. Computational tests were performed using known instances of the literature and the results were compared with results presented in the literature, obtained with other methodologies that also use free rotations, showing that our models are competitive. We also propose the use of separating parabola to avoid items overlaping in the models, which could provide greater computational eficiency as well as solutions with better quality.

Os problemas de empacotamento de itens irregulares são problemas de corte e empacotamento, nos quais peças irregulares de menor tamanho (que chamamos de itens) devem ser empacotados inteiramente em uma peça grande (que chamamos de placa), obedecendo a restrições de nãosobreposição e minimizando as dimensões da placa. Para garantir a não-sobreposição, fazemos uso de retas separadoras, quer dizer, retas que separam um item de outro. Apresentamos modelos de programação não-linear para problemas de empacotamentos de itens regulares e irregulares que rotacionam livremente. Os itens podem ser círculos, polígonos convexos e não-convexos. A principal vantagem dos modelos é a simplicidade, já que estes utilizam somente conceitos básicos de geometria. Usamos o algoritmo de programação não-linear IPOPT (um algoritmo de tipo de pontos interiores), que faz parte da COIN-OR, para a resolução dos problemas. Testes computacionais foram executados usando instâncias conhecidas da literatura e os resultados foram comparados com resultados apresentados na literatura, obtidos com outras metodologias que também usam rotações livre, mostrando que nossos modelos são competitivos. Propomos também o uso de parábolas separadoras para a verificação de não-sobreposição na modelagem do problema, o que pode trazer ganhos computacionais e melhor qualidade de soluções. / The irregular packing problems are cutting and packing problems, in which smaller irregular pieces (which we call items) should be packaged entirely in one large piece (which we call a plate), obeying non-overlapping constraints and minimizing the dimensions of the plate. To ensure non-overlapping, we make use of separation lines, that is, lines that separate one item from another. We present nonlinear programming models for problems of packing regular and irregular items that rotate freely. The items can be circles, convex and nonconvex polygons. The main advantage of the models is their simplicity, because they use only basic geometry concepts. We use the nonlinear programming algorithm IPOPT (an algorithm of interior points type), which is part of COIN-OR, to solve the problems. Computational tests were performed using known instances of the literature and the results were compared with results presented in the literature, obtained with other methodologies that also use free rotations, showing that our models are competitive. We also propose the use of separating parabola to avoid items overlaping in the models, which could provide greater computational eficiency as well as solutions with better quality.