Resolução do Problema da Mochila

UNIVERSIDADE ESTADUAL PAULISTA
CAMPUS DE GUARATINGUETÁ

Resolução do Problema da Mochila pelo Método de Branch & Bound e pelo Método da Programação Dinâmica

Guaratinguetá - 2013.

RESUMO A Pesquisa Operacional é uma ciência que objetiva fornecer ferramentas quantitativas ao processo de tomada de decisões. Dentre as várias disciplinas que integram esta ciência destacam-se a Programação Linear, uma técnica de otimização que faz parte da rotina diária de planejamento de várias empresas assim diversos softwares foram desenvolvidos para auxiliar este planejamento e a Programação Dinâmica, é uma técnica matemática útil para criar uma seqüência de decisões inter-relacionadas. Ela fornece um procedimento sistemático para determinar a combinação de decisões ótimas.1
Este trabalho visa consolidar os conceitos de Programação Linear Inteira e Programação Dinâmica e a partir deles, buscar a solução de um Problema da Mochila, relacionando os resultados obtidos pelos dois métodos.

SUMÁRIO

TABELA DE QUADROS .................................................................................................4 OBJETIVO ............................................................................................................5 INTRODUÇÃO TEÓRICA .....................................................................................5 Programação Linear .........................................................................................6 Programação Dinâmica ....................................................................................7 Problema da Mochila: “Knapsack problem”.......................................................7 PROBLEMA PROPOSTO .....................................................................................8 Resolução Método Branch and Bound