Problema de corte de estoque unidimensional

Abstract

The one-dimensional cutting-stock problem is a classical problem from the literature that basically consists of minimize the cost of filling a demand of items to be cut from given stock lengths of given cost (GILMORE; GOMORY, 1961). In this work, we study the implementation of the simplex method with column generation to get solutions to the one-dimensional cutting stock problem, as well as heuristics procedures to get integer solutions. A heuristic procedure is also proposed. The programming was developed using the C++ language, applying the optimization software CPLEX. Computational tests were performed with randomly generated data to verify the performance of the proposed procedure.

O problema de corte de estoque unidimensional é um problema clássico da literatura que basicamente consiste em minimizar o custo de satisfazer uma demanda de itens a serem cortados de barras em estoque com determinado comprimento e custo. Nesse trabalho, estudamos a implementação do método simplex com geração de colunas para obtenção de soluções para os problemas de corte unidimensional, assim como procedimentos heurísticos para a obtenção de soluções inteiras. Um procedimento heurístico também é proposto. Toda a programação foi desenvolvida utilizando a linguagem C++, aplicando o software de otimização CPLEX. Testes computacionais foram realizados com dados gerados aleatoriamente para verificar o desempenho do procedimento proposto.