Faculdade de Engenharia “Eng. Celso Daniel”
Engenharia de Produção
Pesquisa Operacional II
Profa. Dra. Lílian Kátia de Oliveira
5a lista de exercícios
1. Um casal, Eve e Steven querem dividir suas tarefas domésticas (fazer compras, cozinhar, lavar louças e
lavar roupas) entre eles, de tal maneira que cada um tenha 2 tarefas e o tempo total gasto para realizar tais
tarefas seja mínimo. Suas eficiências sobre estas tarefas diferem de acordo com a tabela abaixo:
Eve (1)
Steven
(2)
Tempo Necessário por semana
Fazer
Lavar
Cozinhar
Lavar
Compras
Louça
(B)
Roupa (D)
(A)
(C)
4.5 hs
7.8 hs
3.6 hs
2.9 hs
4.9 hs
7.2 hs
4.3 hs
3.1 hs
Formule o modelo de Programação Linear Inteira para este problema e resolva-o.
2. Uma companhia está estudando um projeto de expansão que consiste em construir uma nova fábrica em Los
Angeles ou San Francisco, ou mesmo talvez em ambas as cidades. A companhia está considerando também
a construção de um novo estoque, mas a escolha da localização é restrita a cidade onde a nova fábrica será
construída. O lucro total previsto com a construção em cada cidade e o capital requerido é dado na tabela
abaixo:
Variável
Lucro
Previsto (em
milhões R$)
Capital
Requerido (em
milhões R$)
Fábrica Los Angeles
x1
9
6
Fábrica San
Francisco
x2
5
3
Estoque Los Angeles
x3
6
5
Estoque San
Francisco
x4
4
2
A companhia dispõe de apenas R$10 milhões para investir. Escreva o modelo para este problema. Qual
combinação de alternativas maximiza o lucro previsto total?
3. Uma empresa de laticínios produz queijos e leite. Parte do transporte da produção é feito pela própria
empresa, enquanto o restante é terceirizado. O atual parque de veículos da empresa está obsoleto e será
modernizado. Dois tipos de novos veículos são considerados para a substituição dos atuais. Apenas queijos
podem ser transportados através de veículos do tipo A, em um total de no máximo 100 (x100 kg) por mês.
Queijos e leite podem ser transportados por veículos do tipo B, em um total mensal de no máximo 50 (x100
kg) de queijo e 20 (x 100 l) de leite. A compra de um veículo do tipo A proporciona uma economia mensal
de 1000 (x1 R$) em relação à contratação externa da distribuição. Para um veículo do tipo B, a economia
mensal é de 700 (x1 R$). A empresa deseja maximizar suas economias mensais. A demanda diária mínima a
ser transportada é de 2425 (x100 kg) de queijo e de 510 (x100 l) de leite. De modo a evitar investimentos em
capacidade ociosa, foi determinado que a capacidade da frota não deve exceder a demanda diária mínima.
Determinar o número de veículos de cada tipo que devem ser adquiridos.
4. Resolva graficamente o problema anterior (exercício 3).
5. Resolva graficamente o seguinte problema:
Max 3x1 + 3x2
s.a.
x1 + 4 x2 ≤ 12
6 x1 + 4 x2 ≤ 24
x1 , x2 ≥ 0 e inteiros
6. Resolva o exercício 3 utilizando o algoritmo Branch-and-Bound.
7. Resolva o problema abaixo utilizando o algoritmo Branch-and-Bound.
Max 5 x1 + 3 x2 + 6 x3 + 6 x4 + 2 x5
sujeito a:
5 x1 + 4 x2 + 7 x3 + 6 x4 + 2 x5 ≤ 15
x1 , x2 , x3 , x4 , x5 ∈ {0,1}
2