1) Resolver o PPL abaixo, usando o - Prof. Sérgio Mayerle

Universidade Federal de Santa Catarina
EPS7005 – Pesquisa Operacional
Prova I
(02/05/2012)
1) Resolver o PPL abaixo, usando o método Simplex.
Min
z = 20 x1 + 15 x2
s.a:
2 x1 + x2 ≥ 20
x1 + 2 x2 ≥ 16
x1 + x2 ≥ 2
x1 ≥ 4
(3 pontos)
x2 ≥ 8
2) Considere o PPL abaixo. Verifique se a solução ( x1 , x2 , x3 , x4 , x5 ) = (0,11,9,0,0) é ótima.
Max z = 4 x1 + 4 x2 + 6 x3 + 4 x4 − 2 x5
2 x1 + x2 + x3 + x4 ≤ 20
s.a:
x2 + x4 + x5 ≤ 15
x1 + 2 x3 + x4 + x5 ≤ 18
x1 , x2 , x3 , x4 , x5 ≥ 0
(2 pontos)
3) A fábrica WW produz 2 tipos de whisky, Glorius Blend e Super Blend, a partir de 3 maltes
importados: Sir Roses, Highland Wind e Old Frenzy. Os fornecedores só conseguem garantir 2.000
litros de Sir Roses, 2.500 litros de Highland Wind e 1.200 litros de Old Frenzy, ao preço de 350, 250
e 200 euros por barril de 100 litros. Um litro de Glorious Blend é vendido por 3,40 euros, enquanto
que para um litro de Super Blend esse valor é de 3,80 euros. Por questões de sabor e qualidade, é
necessário que o Glorious Blend contenha pelo menos 60% de Sir Roses e no máximo 20% de Old
Frenzy. Do mesmo modo, o Super Blend terá que conter pelo menos 15% de Sir Roses e no
máximo 60% de Highland Wind. Admitindo-se que não existam outros custos de produção,
encontre as quantidades a produzir de cada mistura de modo a maximizar o lucro do processo.
(2 pontos)
4) Sete mil e quinhentos soldados formam um exército que precisa cruzar simultaneamente o
Mediterrâneo. Dois tipos de embarcações estão disponíveis, com as seguintes características:
Característica
Consumo de combustível por viagem
Tripulação necessária
Capacidade
Tipo 1
Tipo 2
12.000 litros
7.000 litros
250 pessoas
100 pessoas
2.000 soldados 1.000 soldados
Apenas 55.000 litros de combustível e 900 tripulantes estão disponíveis. Destes, 300 estão
habilitados a operar as embarcações do tipo 1, 400 estão habilitados a operar embarcações do
tipo 2, enquanto o restante poderá ser usado em qualquer um dos dois tipos de embarcação. O
exército pagará à companhia de navegação US$ 20.000,00 por cada viagem em embarcação do
tipo 1 e US$ 10.000,00 por cada viagem em embarcação do tipo 2. Assumindo que a companhia de
navegação possua um número suficiente de embarcações dos tipos 1 e 2, formule um modelo de
programação linear que minimize o custo total desta operação.
(3 pontos)
GABARITO
Questão 01: Construindo o PPL dual, tem-se:
Max
w = 20 y1 + 16 y2 + 2 y3 + 4 y4 + 8 y5
s.a:
2 y1 + y2 + y3 + y4 ≤ 20
y1 + 2 y2 + y3 + y5 ≤ 15
y1 , y2 , y3 , y4 , y5 ≥ 0
Resolvendo o PPL dual através do tableau:
Encontra-se a seguinte solução ótima para o problema primal:
Questão 2: Considerando a solução fornecida, tem-se o seguinte valor para as variáveis de folga:
S1 = 20 − x2 − x3 = 20 − 11 − 9 = 0
S 2 = 15 − x2 = 15 − 11 = 4
S3 = 18 − 2 x3 = 18 − 2 × 9 = 0
Portanto, a variável de folga S2 precisa estar na base, com a seguinte partição:
 x2 
xB =  x3 
 S 2 
1 1 0 
B = 1 0 1 
0 2 0 
 x1 
x 
 4
xR =  x5 
 
 S1 
 S3 
2 1 0 1 0
R =  0 1 1 0 0 
1 1 1 0 1 
 1 0 −0,5
B =  0 0 0, 5 
 −1 1 0, 5 
−1
cBT = [ 4 6 0]
cRT = [ 4 4 −2 0 0]
 1 0 −0, 5  20  11
xˆB = B b =  0 0 0,5  15  =  9 
 −1 1 0,5  18   4 
−1
 1 0 −0,5  2 1 0 1 0 
∆z = c − c B R = [ 4 4 −2 0 0] − [ 4 6 0]  0 0 0, 5   0 1 1 0 0  =
 −1 1 0, 5   1 1 1 0 1 
T
R
T
B
−1
∆z = [ −5 −1 −3 −4 −1]
Portanto, a partição obtida corresponde a base ótima.
Questão 3: Os dados do problema encontram-se no diagrama abaixo, juntamente com o modelo:
Sir Roses
2.000 litros
€ 350 / barril
Highland Wind
2.500 litros
€ 250 / barril
Old Frenzy
1.200 litros
€ 200 / barril
Max 3, 4( x11 + x21 + x31 ) + 3,8( x12 + x22 + x32 ) −
3,5( x11 + x12 ) − 2,5( x21 + x22 ) − 2( x31 + x32 )
s.a :
x11 + x12 ≤ 2000
x21 + x22 ≤ 2500
x31 + x32 ≤ 1200
x11 ≥ 0, 6( x11 + x21 + x31 )
x31 ≤ 0, 2( x11 + x21 + x31 )
x12 ≥ 0,15( x12 + x22 + x32 )
x22 ≤ 0, 6( x12 + x22 + x32 )
xij ≥ 0 ∀i, j
onde:
xij = quantidade do malte i no whisky j
Glorious Blend
€ 3,40 / litro
Sir Roses > 60%
Old Frenzy < 20%
Super Blend
€ 3,80 / litro
Sir Roses > 20%
Highland Wind < 60%
Questão 4: Considere as seguintes variáveis:
x1 = Número de embarcações/viagens do tipo 1 a serem contratadas;
x2 = Número de embarcações/viagens do tipo 2 a serem contratadas;
t1 = Número de tripulantes polivalentes alocados às embarcações do tipo 1;
t2 = Número de tripulantes polivalentes alocados às embarcações do tipo 2;
Min
s.a:
z = 20.000 x1 + 10.000 x2
12.000 x1 + 7.000 x2 ≤ 55.000
t1 + t2 ≤ 200
250 x1 ≤ 300 + t1
100 x2 ≤ 400 + t2
2.000 x1 + 1.000 x2 ≥ 7.500
x1 , x2 , t1 , t2 ≥ 0 e x1 , x2 , t1 , t2 ∈ ℤ
(1)
(2)
(3)
(4)
(5)
(6)
(7)
Na formulação acima a função (1) minimiza os custos da operação; a restrição (2) garante não se
gastar mais combustível que o disponível; a restrição (3) limita o número de tripulantes
polivalentes; as restrições (4) e (5) limitam o número de viagens em embarcações do tipo 1 e 2,
considerando a disponibilidade de tripulantes; a restrição (6) assegura o transprte de todos os
soldados; e a condição (7) garante a não-negatividade e integridade das variáveis.