A atividade de Planejamento de Suprimento de Petróleo é um elo importante para a integração da Cadeia de Suprimento de Petróleo na PETROBRAS, uma vez que é responsável por refinar as informações do planejamento estratégico a ser implementado no nível operacional. Nesta tese, esse problema é definido e explicado em detalhes e um modelo de programação Inteira Mista é proposto para resolvê-lo. Embora os resolvedores de problemas de programação Inteira Mista tenham evoluído de forma surpreendente na última década, para esta aplicação em particular, com o modelo inicial proposto não é possível obter soluções com qualidade satisfatória em tempo computacional aceitável. Desta forma, a linha de pesquisa desta tese consistiu em investigar, em detalhe, a estrutura deste problemaa fim de encontrar reformulações mais adequadas e novos algoritmos para a solução deste problema. O foco principal desta tese é resolver de forma eficiente o problema de planejamento de suprimento de petróleo na PETROBRAS, no entanto, como subprodutos desse esforço são propostos um novo algoritmo de decomposição e reformulações que podem ser aplicados a uma ampla gama de problemas. No que diz respeito à realização do objetivo principal, todos os casos testados foram resolvidos de maneira eficiente através dos desenvolvimentos propostos. O novo algoritmo de decomposição se mostrou o método mais adequado para resolver as instâncias com mais de duas classes de navios operando em cada plataforma. Já para os casos com uma ou duas classes de navios, a formulação denominada Hull Relaxation, que tem como base uma estrutura definida neste trabalho como Cascading Knapsack Inequalities, é a melhor alternativa de solução. Tendo em vista estas alternativas de soluções, é implementado um algoritmo geral que automaticamente escolhe a melhor opção de solução, em função da estrutura do problema. Para a situação onde o número de classes de navios operando nas diversas plataformas varia entre um e quatro, pode-se usar mais de uma abordagem em paralelo e considerar como solução a alternativa mais rápida ou com melhor resultado. Este modelo está sendo testado na PETROBRAS e tem-se mostrado uma ferramenta eficaz para a integração de sua cadeia de suprimentos de petróleo, bem como permitindo a análise de cenários para a obtenção de soluções alternativas até então não exploradas.