O problema da mochila em problemas de localização e em problemas de atribuição

• Processo: 06/50364-5
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de abril de 2006
• Data de Término da vigência: 31 de dezembro de 2006
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Silvely Nogueira de Almeida Salomão Néia
• Beneficiário: Aline Aparecida de Souza Leão
• Instituição Sede: Faculdade de Ciências e Tecnologia (FCT). Universidade Estadual Paulista (UNESP). Campus de Presidente Prudente. Presidente Prudente , SP, Brasil
• Assunto(s): Programação linear inteira Problemas de localização de facilidades Decomposição de Dantzig-Wolfe Problemas de atribuição Problema da mochila
• Palavra(s)-Chave do Pesquisador: Problema Da Mochila | Problema De Atribuicao | Problema De Localizacao | Problema Quadratico Da Mochila | Programacao Inteira

Resumo

A decomposição Dantzig-Wolfe aplicada à problemas de programação linear e inteira consiste basicamente em separar o problema original em dois novos problemas, denominados por problema mestre e subproblema. Em uma boa parte dos casos, o subproblema constitui um "Problema da Mochila". No caso do problema de localização o problema da mochila é linear, ou seja, sua função objetivo é uma função linear e suas restrições são inequações lineares, mas existem casos, como no problema de atribuição de antenas celulares a centros de comutação e controle, em que o problema é não linear, o subproblema é um problema da mochila não linear, devido à não linearidade da função objetivo. Num primeiro momento, pretende-se fazer um estudo da decomposição Dantzig-Wolfe e suas propriedades duais e um estudo mais específico de métodos de resolução do problema da mochila, tratando dos casos linear e não-linear. Deverão ser trabalhados artigos que proponham algoritmos de resolução nestes dois casos, que deverá ser implementados e testados pelos alunos envolvidos neste projeto. (AU)