For developers
O problema do corte de material 1D
Como cortar um conjunto de comprimentos necessários a partir de barras de material usando o mínimo de barras é o problema do corte de material 1D: um problema de otimização clássico e genuinamente difícil. Eis o que é, porque resiste à força bruta e como é resolvido na prática, incluindo na API por trás deste site.
O que é o problema do corte de material 1D
Tem peças de material de um comprimento fixo (digamos, barras de 6000 mm) e uma lista de peças necessárias, cada uma com um comprimento e uma quantidade. Um padrão de corte é uma forma de cortar uma única barra de material em algumas dessas peças; o comprimento que sobra é desperdício. O problema é escolher padrões, e quantas barras cortar em cada um, para que cada peça necessária seja produzida e o número total de barras de material, ou equivalentemente o desperdício total, seja o menor possível. Uma dimensão, porque só o comprimento importa: a lâmina atravessa toda a secção transversal, pelo que a largura e o perfil nunca entram no cálculo.
Acondicionamento de contentores 1D e porque é NP-difícil
O problema do corte de material é uma generalização do acondicionamento de contentores 1D: o acondicionamento de contentores pede para agrupar um conjunto de itens de tamanhos distintos no menor número de contentores de tamanho fixo. O corte de material é a mesma questão quando os itens se repetem em grandes quantidades, pelo que se raciocina sobre padrões em vez de itens individuais. O acondicionamento de contentores é um dos problemas clássicos NP-difíceis, e a sua forma de decisão, 'estes itens cabem em k contentores?', é NP-completa. O corte de material herda essa dificuldade.
A razão é a explosão combinatória. O número de padrões de corte distintos cresce exponencialmente com o número de tamanhos de peças, e o número de formas de distribuir quantidades por esses padrões explode por cima disso. Não existe um algoritmo conhecido que encontre a solução ótima garantida em tempo que escale polinomialmente com os dados de entrada e, a menos que P seja igual a NP, não vai haver. Por isso, os solucionadores reais não enumeram tudo; são inteligentes sobre que possibilidades podem excluir.
Como é resolvido na prática
First-fit-decreasing (FFD)
A heurística de base: ordenar as peças necessárias da mais comprida para a mais curta e, em seguida, colocar cada uma na primeira barra onde ainda cabe, abrindo uma nova barra apenas quando nenhuma tem espaço. É rápida e surpreendentemente boa, comprovadamente a rondar 11/9 do número ótimo de barras mais uma pequena constante. A maioria das ferramentas para aqui; uma boa usa FFD como ponto de partida, não como linha de chegada.
Geração de colunas (Gilmore e Gomory)
A formulação que tornou as grandes instâncias tratáveis. Gilmore e Gomory (1961) escreveram o problema com uma variável por padrão de corte e, como existem exponencialmente muitos, resolveram a relaxação linear por geração de colunas atrasada: começar com alguns padrões e gerar repetidamente o próximo mais útil, resolvendo um subproblema da mochila limitada. O limite inferior que produz é notoriamente preciso.
Branch-and-bound e branch-and-price
Para transformar essa relaxação fracionária num número inteiro de barras, é preciso procurar, mas não às cegas. O branch-and-bound explora a árvore de escolhas de inteiros enquanto usa o limite da programação linear para podar ramos inteiros que não conseguem superar o melhor plano encontrado até agora; combinado com a geração de colunas, torna-se branch-and-price, a base da maioria dos solucionadores exatos de corte de material.
Limites inferiores e uma prova
Um solucionador sério não devolve apenas um plano, calcula um limite inferior (a partir da relaxação da programação linear ou de um argumento de comprimento total mais simples) e compara. Quando um plano usa exatamente o número de barras que o limite prova serem inevitáveis, é comprovadamente ótimo: nenhum plano pode ser melhor, e o solucionador pode afirmá-lo em vez de esperar ter tido sorte.
Como o LinearCutting o resolve
O LinearCutting executa esta sequência: uma heurística rápida para um plano viável instantâneo, depois uma pesquisa orientada por limites que continua a melhorar até igualar o limite inferior (comprovadamente ótimo, e avisa-o) ou esgotar o seu tempo e devolver o melhor plano que encontrou. Também modela a física: a espessura do corte em cada corte, o aparo da ponta, retalhos de quantidade fixa e cortes em ângulo que consomem mais, porque um plano que ignora a lâmina não é apenas subótimo, está errado. Os trabalhos de referência são publicados para que possa verificar os resultados contra qualquer outra ferramenta.
É exposto como uma API JSON: envie as suas peças e material, receba de volta um plano de corte verificado com os diagramas, o desperdício, o número de ajustes e se o plano atingiu o limite ótimo. Existem clientes oficiais para Python (pip install linearcutting) e JavaScript ou TypeScript (npm install linearcutting), pelo que chamá-lo demora algumas linhas em qualquer uma das linguagens.
Resolva a partir do seu código
Não escreva um solucionador, chame um. O mesmo motor por trás da calculadora deste site é uma API JSON com clientes oficiais para Python e JavaScript, um nível público gratuito e um exemplo ao vivo que pode executar na documentação.
pip install linearcutting npm install linearcutting