On stabilizing column generation for cutting stok problem / Estabilização da geração de colunas aplicada no problema de corte de estoque

AUTOR(ES)

Marco Antonio Lozano Porta Lopes

DATA DE PUBLICAÇÃO

2006

RESUMO

O problema de corte de estoque consiste em cortar objetos maiores, disponíveis em estoque, para produzir uma quantidade especificada de peças menores, de modo que uma certa função objetivo seja otimizada. Um modelo de otimização linear tem sido amplamente utilizado na solução deste problema desde os anos 60, que incorpora parte da estrutura combinatória inerente ao problema na construção das colunas da matriz de restrições. As colunas são construídas a cada iteração do Método Simplex, chamando-se geração de colunas. Apesar do método Simplex ser largamente utilizado para este tipo de problema, apresenta baixa convergência quando próximo da otimalidade, pouco melhorando a função objetivo. Assim, estratégias para aceleração do Método Simplex faz-se necessário, uma maneira consiste na redução do espaço dual, com a introdução de restrições (colunas no primal) que evite grandes variações nas variáveis duais, chamadas cortes duais. Neste trabalho, generalizamos duas famílias de cortes duais recentemente publicadas e analisamos o impacto computacional desses cortes duais sobre a convergência do Método Simplex

ASSUNTO(S)

colunm generation problema de corte de estoque aceleração e estabilização cutting stok problem aceleration and stabilization geração de colunas

Documentos Relacionados

• Geração de colunas para problemas de corte em duas fases
• O problema de corte de estoque multiperíodo
• Geração de colunas para o problema de dimensionamento de lotes de produção com limitações de capacidade
• The cutting stock problem under stochastic demand
• AN ALGORITHM WITH COLUMN AND CUT GENERATION FOR THE CAPACITATED VEHICLE ROUTING PROBLEM