Exercícios de Programação Inteira

Prévia do material em texto

MB-244 - PRINCÍPIOS DA PESQUISA OPERACIONAL 
LISTA DE EXERCÍCIOS 9 – PROGRAMAÇÃO INTEIRA 
 
1. Um fabricante de sapatos possui 6 máquinas. A tabela abaixo sumariza os custos 
variáveis e de set-up das máquinas, assim como sua capacidade. O fabricante recebeu 
uma encomenda de 1.800 pares de sapato. Formule o problema que determina quais 
máquinas ele deve usar se o objetivo é minimizar o custo de produção. 
 
MÁQ CUSTO DE SET-UP ($) CUSTO VARIÁVEL ($) CAPACIDADE (PARES) 
1 1000 21 500 
2 950 23 600 
3 875 25 750 
4 850 24 400 
5 800 20 600 
6 700 26 800 
 
2. Resolva os PPI pelo método branch-and-bound: 
 
a) Max 2x1 + 3x2 
 S.A. x1 + 3x2  8,25 
 2,5x1 + x2  8,75 
 x1, x2  0 
 x1, x2 inteiros 
 
b) Max 5x1 + 4x2 
 S.A. x1 + x2  5 
 10x1 + 6x2  45 
 x1, x2  0 
 x1, x2 inteiros 
 
c) Min 5x1 + 4x2 
 S.A. 3x1 + 2x2  5 
 2x1 + 3x2  7 
 x1, x2  0 
 x1, x2 inteiros 
 
4. Mostre graficamente que o seguinte PPI não tem nenhuma solução viável e então 
verifique o resultado usando o branch-and-bound. 
 
Maximizar z = 2x1 + x2 
 S.A. 10x1 + 10x2  9 
 10x1 + 5x2  1 
 x1, x2  0 e inteiras 
 
5. Um tabuleiro de jogo consiste em nove quadrados iguais (3X3). Você deve encher 
cada quadrado com um número entre 1 e 9 de modo tal que a soma dos números em 
cada linha, cada coluna e cada diagonal seja igual a 15. Além disso, os números em 
todos os quadrados devem ser distintos. Formule o problema com de PLI para 
determinar a designação de números a quadrados. 
 
6. Equipamentos de 7 tipos diferentes, pesando p1 = 40, p2 = 50, p3 = 30, p4 = 10, p5 = 10, 
p6 = 40 e p7 = 30 kg, devem ser transportados em uma motocicleta com capacidade para 
100 kg. Lucra-se L1=40, L2=80, L3=10, L4=10, L5=4, L6=20 e L7=60 unidades 
monetárias, respectivamente, para cada tipo de equipamento transportado. Formule o 
problema e resolva utilizando uma estratégia Branch & Bound para encontrar o valor da 
combinação mais lucrativa a ser transportada na motociclieta. 
 
7. Uma fábrica de papel produz bobinas de papel com 70 polegadas de largura. Os 
clientes, porém, solicitam bobinas (do mesmo comprimento) com largura menor. O 
pedido de hoje são 125 bobinas de 20 polegadas e 100 bobinas de 23 polegadas. 
Formule o problema e resolva utilizando uma estratégia Branch & Bound para encontrar 
a solução que minimiza as perdas geradas pelos cortes.