Corte linear. Problema de corte unidimensional

Corte unidimensional de barras com tipos de perfil, estoque limitado e largura de corte. Plano para cada barra, sobras, aproveitamento do material e dois objetivos de otimização.

Esta página existe graças aos esforços das seguintes pessoas:

Timur

Timur

Criado: 2026-11-22 12:35:55, Ultima atualização: 2026-11-22 14:08:13
Creative Commons Attribution/Share-Alike License 3.0 (Unported)

Este conteúdo é licenciado de acordo com a Licença Creative Commons de Atribuição/CompartilhaIgual 3.0 (Unported). Isso significa que você pode redistribuir ou modificar livremente este conteúdo sob as mesmas condições de licença e precisa atribuir ao autor original colocando um hyperlink para este trabalho no seu site. Além disto, favor não modificar qualquer referência ao trabalho original (caso houver) que estiverem contidas neste conteúdo.

Corte linear é a distribuição de peças por barras, armaduras, tubos ou outros materiais de comprimento determinado. As peças podem mudar de lugar: o que importa não é a posição inicial na lista, mas quais delas devem ser cortadas da mesma barra.

A calculadora abaixo cria um plano para vários tipos de perfil, considera as quantidades disponíveis e a largura de corte e depois mostra a sobra de cada barra. Os valores padrão podem ser apagados; servem apenas como exemplo. As fórmulas e um pouco de teoria estão abaixo da calculadora.

PLANETCALC, Corte linear de barras

Corte linear de barras

Material de partida

Tipo de perfilComprimentoQuantidade
Itens por página:

Peças

Tipo de perfilComprimentoQuantidade
Itens por página:

Quando o critério principal empata, é escolhido o plano com o melhor critério secundário.
Comprimento adicional reservado para cada peça alocada; nas mesmas unidades dos comprimentos nas tabelas.
Estado
 
Barras utilizadas
 
Peças alocadas
 
Total de peças
 
Comprimento do material utilizado
 
Comprimento das peças alocadas
 
Largura de corte total
 
Sobras totais
 
Aproveitamento do material, %
 
Limite inferior do número de barras
 
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.

Material de partida, peças e perfis

Material de partida é a barra original, e uma peça é o pedaço que se pretende obter. As tabelas usam os seguintes campos:

  1. Tipo de perfil identifica o material ou produto laminado, por exemplo «Armadura A500C». Uma peça só pode ser colocada em material com o mesmo tipo de perfil. Uma armadura de aço e um tubo de alumínio não devem ser misturados no mesmo plano, mesmo que seus comprimentos combinem convenientemente.
  2. Comprimento é o comprimento do material ou da peça. Todos os comprimentos devem usar as mesmas unidades: se forem escolhidos metros, 80 centímetros são escritos como 0,8.
  3. Quantidade é o número de posições idênticas. A calculadora expande esse número em peças ou barras individuais, portanto uma linha «comprimento 3, quantidade 2» significa duas peças de comprimento 3.

A sobra é a parte de uma barra utilizada que não se transformou em peça nem foi consumida pelo corte. Ela ainda pode ser aproveitada, por isso nem sempre é correto chamá-la de perda irrecuperável. As barras não utilizadas não entram nas sobras.

Um exemplo com duas barras

Suponhamos que temos uma barra de 12 metros e outra de 9 metros. Precisamos de quatro peças: 8, 7, 4 e 2 metros.

Um plano completo tem o seguinte aspecto:

Material Peças Sobra
12 m 8 + 4 m 0 m
9 m 7 + 2 m 0 m

O comprimento total das peças é 21 metros, exatamente igual ao comprimento do material utilizado. O aproveitamento do material é de 100%. Este é o exemplo padrão da calculadora, mas, naturalmente, uma sobra nula não é prometida para outros dados.

Por que considerar a largura de corte

Ao serrar, uma pequena parte do material se transforma em aparas. Essa medida chama-se largura de corte (kerf). Se ela for ignorada, um belo plano na tela pode não caber numa barra real.

A calculadora usa uma regra conservadora: uma largura de corte é reservada para cada peça. Se peças de comprimento L_1,\ldots,L_n forem colocadas numa barra e a largura de corte for k, o comprimento ocupado será

U=\sum_{i=1}^{n}L_i+nk

em que n é o número de peças na barra. O plano só é admissível quando U\leq L, onde L é o comprimento do material. A sobra é calculada como

R=L-U

Por que nk e não (n-1)k? A regra n-1 serve quando uma barra é dividida completamente em n partes. Mas se restar uma sobra depois da última peça, ainda é preciso separá-la dela. Para não criar uma exceção oculta no caso de coincidência exata dos comprimentos, a calculadora sempre reserva um corte por peça.

Por exemplo, duas peças de 5 metros com largura de corte de 1 metro precisam de 12 metros, e não de uma barra de 10 metros. Esse plano requer duas barras, se estiverem disponíveis.

O que exatamente é otimizado

«Otimização» tem aqui dois sentidos diferentes. É possível gastar menos barras ou deixar menos material nas barras utilizadas. Esses objetivos nem sempre coincidem.

Suponhamos que exista uma barra de 12 metros e duas de 5 metros, e sejam necessárias duas peças de 3 metros:

  1. Número mínimo de barras. As duas peças cabem numa barra de 12 metros. A sobra é de 6 metros, mas as duas barras curtas permanecem intactas.
  2. Mínimo de sobras totais. Cada peça é colocada na sua própria barra de 5 metros. Duas barras são usadas, mas as sobras totais são de apenas 4 metros.

Por isso a calculadora permite escolher o objetivo. Por padrão, o mínimo de sobras está selecionado. Quando o critério principal empata, usa-se o secundário: primeiro compara-se a sobra total ou o número de barras e depois o inverso.

Para avaliar o resultado, é útil o aproveitamento do material — a proporção do comprimento das peças acabadas no comprimento do material utilizado:

\eta=\frac{\sum_i \ell_i}{\sum_b L_b}\cdot100\%

em que \ell_i é o comprimento da i-ésima peça e L_b é o comprimento da b-ésima barra utilizada. A largura de corte não entra no numerador. Portanto, aproveitamento do material, parcela de corte e parcela de sobra somam 100%.

Por que não se pode simplesmente prometer o melhor plano

Este é um problema de corte unidimensional (one-dimensional cutting-stock problem), próximo do problema de empacotamento em contêineres (bin packing problem). Na formulação clássica, é preciso colocar um conjunto dado de objetos no número mínimo de contêineres idênticos. O nosso problema considera ainda materiais de diferentes comprimentos, quantidades limitadas e compatibilidade de perfis.

Mesmo o empacotamento clássico é NP-difícil.1 Isso não significa que seja impossível obter uma resposta exata. Para um conjunto pequeno, podem-se enumerar as variantes; problemas grandes são resolvidos com programação inteira e geração de padrões de corte.2 Mas um solucionador exato desse tipo exigiria limites próprios e uma implementação muito mais complexa.

A calculadora usa heurísticas — regras que constroem rapidamente um bom plano, mas não demonstram sua otimalidade. Por isso, o resultado deve ser lido como «melhor plano encontrado», e não «melhor de todos os planos possíveis».

Como o algoritmo funciona

Primeiro, o problema é separado por tipo de perfil. Isso não é uma aproximação: uma peça não pode passar para material de outro perfil de qualquer forma. Em seguida, quatro variantes de construção são executadas para cada perfil:

  1. peças por comprimento decrescente ou crescente;
  2. ao abrir uma nova barra, primeiro a mais curta adequada ou primeiro a mais longa adequada.

Para a peça seguinte, a regra do melhor ajuste (best fit) escolhe a barra já aberta onde restará menos espaço após a alocação. Se nenhuma servir, outra barra não utilizada é aberta.

Os planos obtidos são melhorados localmente:3

  1. Remoção de uma barra. O algoritmo tenta transferir suas peças para outras barras já utilizadas. Se conseguir, a barra é liberada.
  2. Trocas. Se uma transferência simples não ajudar, o algoritmo tenta um número limitado de trocas de peças e repete a remoção.
  3. Substituição do material. Se o mesmo grupo de peças couber numa barra não utilizada mais curta e do mesmo perfil, a substituição é feita.

Resta apenas comparar as variantes pelo objetivo escolhido. Não há tentativas aleatórias: repetir o cálculo com os mesmos dados produz o mesmo plano.

Limite inferior do número de barras

Para um perfil, o comprimento total das peças pode ser dividido pelo maior comprimento de material disponível e arredondado para cima:

B_0=\left\lceil\frac{\sum L_i}{L_{\max}}\right\rceil

em que B_0 é o limite inferior do número de barras e L_{\max} é o comprimento máximo disponível para este perfil. Os limites dos perfis são somados.

O limite é propositalmente simples: não considera a largura de corte, os limites de quantidade nem combinações inconvenientes de comprimentos. Se o plano encontrado usar exatamente B_0 barras, está demonstrado que seu número é mínimo. Disso não decorre que as sobras sejam mínimas.

Como ler o resultado

O plano de corte contém uma linha por barra utilizada. A entrada «8 + 4» significa duas peças dos comprimentos correspondentes; sua ordem de corte não influencia o consumo de material. Cada linha repete o comprimento das peças, a reserva de corte, a sobra e o aproveitamento do material.

O resumo por perfil ajuda a verificar a distribuição entre os tipos de material. Material não utilizado mostra o estoque restante. Se nenhum plano completo for encontrado, a tabela Peças não alocadas enumera o que o algoritmo não conseguiu alocar.

O que isso significa na prática? Talvez realmente não haja material suficiente ou uma peça seja mais comprida que qualquer barra adequada. Mas também é possível que a heurística não tenha encontrado um plano existente. Portanto, «não foi encontrado um plano completo» não prova que o corte seja impossível.

Limitações

  1. A otimalidade não é garantida. A admissibilidade do plano e todo o balanço de comprimentos são verificados, mas não se verifica se o resultado é mínimo entre todos os planos possíveis.
  2. Os perfis não são misturados. Seus nomes são comparados exatamente, incluindo maiúsculas e minúsculas. Substituir um material por outro exige uma decisão de engenharia separada, não uma regra de empacotamento.
  3. As peças não são divididas. Cada peça deve caber inteiramente numa única barra.
  4. Novas sobras não se transformam automaticamente em material de partida. Se precisar usá-las num trabalho posterior, adicione manualmente as sobras adequadas à tabela de material.
  5. Limites de entrada. São suportadas até 100 barras e 100 peças depois de expandir as quantidades, com até seis casas decimais. Este é um limite do cálculo no navegador, não uma propriedade do problema.
  6. Somente o comprimento é considerado. Custo de compra, cortes das extremidades, dispositivos de fixação, sobra útil mínima, ordem de operação da máquina e tempo de corte não fazem parte do modelo.

Se, em vez de comprimento, forem fornecidas largura e altura de retângulos, trata-se de outro problema. Para isso existe a calculadora de empacotamento bidimensional. Para contêineres idênticos sem perfis e sem plano por barra, podem ser úteis as calculadoras Problema de empacotamento e Problema de empacotamento 2.


  1. Richard E. Korf. A New Algorithm for Optimal Bin Packing. AAAI 2002. Definições do problema, heurísticas e complexidade. Artigo. ↩

  2. P. C. Gilmore, R. E. Gomory. A Linear Programming Approach to the Cutting-Stock Problem. Operations Research, 1961. Padrões de corte e geração de colunas. Artigo. ↩

  3. A. C. F. Alvim, C. C. Ribeiro, F. Glover, D. J. Aloise. A hybrid improvement heuristic for the one-dimensional bin packing problem. Journal of Heuristics, 2004. Um exemplo de combinação de construção e melhoria local dos planos. Artigo. ↩

URL copiado para a área de transferência
PLANETCALC, Corte linear. Problema de corte unidimensional

Comentários