Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/331710
Type: TESE DIGITAL
Degree Level: Mestrado
Title: Variações do método de Gilmore e Gomory aplicado ao problema de corte e empacotamento
Title Alternative: Variations in Gilmore and Gomory's algorithm applied to the one-dimensional cutting stock problem
Author: Marques, João Gabriel Oliveira, 1993-
Advisor: Moretti, Antonio Carlos, 1958-
Abstract: Resumo: O problema de corte e empacotamento unidimensional tem sido estudado por diversos pesquisadores desde a década de 1960. Em diversas modificações propostas ao longo de anos de pesquisa, grande parte dos trabalhos modifica o modelo matemático do problema de corte, e continua, em algum estágio, utilizando o método de Gilmore e Gomory de geração de colunas para obtenção de uma solução ótima do problema relaxado. Os autores citam em seus trabalhos que o desempenho do método pode ser melhorado no que tange o subproblema da mochila por meio de propriedades algébricas da programação linear e do método simplex, principalmente relacionadas às condições de otimalidade. Baseado nas sugestões dos autores, foram propostas cinco variações no modelo do subproblema da mochila originalmente proposto por Gilmore e Gomory. As variações sugeridas foram testadas para diversas classes de exemplares do problema de corte presentes na literatura e foram comparadas com o método original. Em algumas das variações ouve redução no número de colunas geradas e, portanto, no número de iterações do método, mas, como subproblema da mochila pode ser resolvido em tempo pseudo-polinomial, ocorreu que nestas variações o tempo computacional aumentou consideravelmente. Em uma das variações o tempo computacional foi reduzido significativamente, mas, em contrapartida, o número de colunas geradas foi extremamente alto. Assim, de maneira geral, as modificações propostas no subproblema da mochila do método de geração de colunas acarretam em benefícios, seja no número total de colunas geradas, seja no tempo computacional exigido

Abstract: The one-dimensional cutting stock problem has been broadly researched since the 1960. Throughout years of research many modifications focused mainly on the mathematichal model itself, which often uses Gilmore and Gomory's column generation algorithm to find an optimum solution to the relaxed cutting problem. These authors explain that the algorithm's performance can be enhanced on the knapsack subproblem through a number of algebraic properties from linear programming and the simplex method, mainly related with optimality conditions. Following their suggestions, we developed five variations of the knapsack subproblem formerly proposed by Gilmore and Gomory. The variations were tested for classes of one-dimensional cutting stock problems widely used in related papers and were compared with the original algorithm. Some variations effectively reduced columns generation, and so number of iterations, but increased total running time, once the knapsack subproblem can be solved in pseudo-polynomial time. One variation reduced total running time, but significantly increased the number of generated columns. Therefore we generalize that variations on the knapsack subproblem from the column generation algorithm can result in benefits, either in computational time or in amount of generated columns
Subject: Problema de corte de estoque
Programação linear
Simplex (Matemática)
Language: Português
Editor: [s.n.]
Citation: MARQUES, João Gabriel Oliveira. Variações do método de Gilmore e Gomory aplicado ao problema de corte e empacotamento. 2018. 1 recurso online ( 53 p.). Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Ciências Aplicadas, Limeira, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/331710>. Acesso em: 3 set. 2018.
Date Issue: 2018
Appears in Collections:FCA - Tese e Dissertação

Files in This Item:
File SizeFormat 
Marques_JoaoGabrielOliveira_M.pdf1.52 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.