Estabilizacao da geracao de colunas e aplicacoes.

Resumo

O problema de corte de estoque tem sido objeto de intenso estudo nas últimas décadas. A técnica mais utilizada para a resolução desta classe de problema é a técnica de geração de colunas aplicada aos modelos de otimização linear propostos Gilmore e Golmory (1961, 1963, 1965) e variações. Um problema bastante observado na aplicação desta técnica é que durante as primeiras iterações há uma boa evolução em termos da função objetivo, porém muitas iterações finais são necessárias até que o critério de otimalidade seja verificado. Esta "calda longa" decorre de grandes variações nas variáveis duais. Para se obter a solução mais rapidamente, restrições são acrescentadas no problema dual para evitar-se grandes variações nas variáveis duais, sem que a otimalidade seja comprometida. Testes computacionais têm sido realizados, apresentando resultados promissores. Neste projeto de pesquisa, aplicaremos as idéias para estabilização da técnica de geração de colunas a problemas de corte (várias dimensões) e problemas de roteamento de veículos, considerando um modelo com algumas restrições adicionais, abrindo-se perspectivas para outros problemas onde o processo de corte e o problema de roteamento de veículos é apenas uma etapa de processos industriais e de logística. (AU)