Estabilização da geração de colunas aplicada no problema de corte de estoque

Autor(es)

Marco Antonio Lozano Porta Lopes

• Tipo de documento: Dissertação de Mestrado
• Imprenta: São Carlos.
• Instituição: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Data de defesa: 2006-03-14

Membros da banca

Marcos Nereu Arenales; Robinson Samuel Vieira Hoto; Franklina Maria Bragion de Toledo

• Orientador: Marcos Nereu Arenales

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 (AU)

• Processo FAPESP: 03/12009-0 - Estabilizacao da geracao de colunas aplicada ao problema de corte de estoque.
• Beneficiário: Marco Antonio Lozano Porta Lopes
• Modalidade de apoio: Bolsas no Brasil - Mestrado