P1 - OC - Gabarito - 2014-2

Prévia do material em texto

UERJ – Universidade do Estado do Rio de Janeiro 
Instituto de Matemática e Estatística. Departamento de Matemática Aplicada 
Disciplina: Otimização Combinatória. Professor: Marcos Roboredo 
2014 – 2 (Prova 1) 
1) 
 
 
 
 
 
 
 
 
 
 
 
 
 
2) 
a) 
 
 
 
s.a. 
 
 
 
 
 b) 
 
 
c) A solução é um dos pontos extremos do conjunto de soluções viáveis. Podemos verificar 
todos e identificar o que gera melhor custo na f.o. 
 
 ( ) 
 ( ) 
 ( ) 
 ( ) 
 ( ) 
 
Como o problema é de maximização, a solução ótima é ( ) 
 
 d) 
 
 
 
 
 
Base x1 x2 s1 s2 S3 Sol 
z -3 -2 0 0 0 0 
S1 2 1 1 0 0 100 
S2 1 1 0 1 0 80 
S3 1 0 0 0 1 40 
 
Entra: x1 
Min {100/2, 80/1, 40/1} = 40. Logo, S3 sai da base 
 
Base x1 x2 s1 s2 S3 Sol 
z 0 -2 0 0 3 120 
S1 0 1 1 0 -2 20 
S2 0 1 0 1 -1 40 
x1 1 0 0 0 1 40 
 
 
 Entra: x2 
Min {20/1 40/1} = 20. Logo, S1 sai da base 
 
Base x1 x2 s1 s2 S3 Sol 
z 0 0 2 0 -1 160 
x2 0 1 1 0 -2 20 
S2 0 0 -1 1 1 20 
x1 1 0 0 0 1 40 
 
Entra: S3 
Min {20/1 40/1} = 20. Logo, S2 sai da base 
 
Base x1 x2 s1 s2 S3 Sol 
z 0 0 1 1 0 180 
x2 0 1 -1 2 0 60 
S3 0 0 -1 1 1 20 
x1 1 0 1 -1 0 20 
 
 
A solução prévia é ótima. Logo, na solução ótima temos (x1, x2) = (20,60), com z=180 
 
e) Sejam D1, D2 e D3 os aumentos (ou decréscimos) no lado direito das restrições 1, 2 e 3. Resolvendo o 
simplex com estas constantes teríamos: 
 
Base x1 x2 s1 s2 S3 Sol D1 D2 D3 
z 0 0 1 1 0 180 1 1 0 
x2 0 1 -1 2 0 60 -1 2 0 
S3 0 0 -1 1 1 20 -1 1 1 
x1 1 0 1 -1 0 20 1 -1 0 
 
 
Observe que o preço dual para a restrição de pintura (restrição 1) é 1. Logo, o valor de 50 
centavos deve ser aceito sim. 
 
f) D3 =2, D1=0 e D2 = 0 
 
Antes de verificarmos o novo valor devemos verificar se estas mudanças alteram a solução. De 
acordo com a tabela anterior temos 
 
 
 
 
 
Note que os valores D3 =2, D1=0 e D2 = 0 satisfazem as equações. Logo, a nova solução ótima 
será 
 
 
 
 
Ou seja a solução ótima se manteve a mesma. Isto aconteceu porque o valor dual da restrição 3 
é 0, ou seja, não vale a pena aumentar o lado direito apenas desta restrição. 
 
g) D3 =0, D1=1 e D2 = 1 
 
Note que os valores D3 =0, D1=1 e D2 = 1 satisfazem as equações do item f. Logo, a nova 
solução ótima será 
 
 
 
 
Assim, serão fabricados 20 soldados e 61 trens 
 
3) 
Fase1: 
 
 
 
 
 
 
 
Tabela inicial: 
 
Base x1 x2 S1 S2 R1 R2 Sol 
r 0 0 0 0 -1 -1 0 
S1 4 1 1 0 0 0 21 
R1 2 3 0 -1 1 0 13 
R2 -1 1 0 0 0 1 1 
 
Retirando a inconsistência da linha r através da seguinte transformação: 
 
Linha nova r -> linha r + (linha R1 + Linha R2) 
 
Base x1 x2 S1 S2 R1 R2 Sol 
r 1 4 0 -1 0 0 14 
S1 4 1 1 0 0 0 21 
R1 2 3 0 -1 1 0 13 
R2 -1 1 0 0 0 1 1 
 
Entra: x2 
Minimo{21/1 , 13/3, 1/1} = 1. Logo, sai R2 
 
Linha nova x2 -> Linha R2 /1 
Linha nova R1 -> Linha R1 – 3* Linha nova x2 
Linha nova S1 -> Linha S1 – 1* Linha nova x2 
Linha nova r -> Linha r – 4* Linha nova x2 
 
Base x1 x2 S1 S2 R1 R2 Sol 
r 5 0 0 -1 0 -4 10 
S1 5 0 1 0 0 -1 20 
R1 5 0 0 -1 1 -3 10 
x2 -1 1 0 0 0 1 1 
 
Entra x1 
Minimo{20/5, 10/5} = 10/5. Logo sai R1 
 
Linha nova x1 -> Linha R1/5 
Linha nova r -> Linha r – 5* Linha nova x1 
Linha nova S1 -> Linha S1 – 5* Linha nova x1 
Linha nova x2 -> Linha x2 + 1* Linha nova x1 
 
Base x1 x2 S1 S2 R1 R2 Sol 
r 0 0 0 0 -1 -1 0 
S1 0 0 1 1 -1 2 10 
x1 1 0 0 -0,2 0,2 -0,6 2 
x2 0 1 0 -0,2 0,2 0,4 3 
 
Solução da fase 1 é ótima com R1 = R2 = 0. Logo, podemos ir para a fase 2 
 
Fase 2: Voltamos para o problema original que é 
 
Além disso, voltamos para a linha z e não r 
 
Tabela inicial 
 
Base x1 x2 S1 S2 Sol 
z -6 1 0 0 0 
S1 0 0 1 1 10 
x1 1 0 0 -0,2 2 
x2 0 1 0 -0,2 3 
 
Retirando a inconsistência da linha r através da seguinte transformação: 
 
Linha nova r -> linha r + 6*linha x1 -linha x2 
 
Esta equação surgiu ao se tentar zerar os coeficientes de x1 e x2 na linha z 
 
 
 
Base x1 x2 S1 S2 Sol 
z 0 0 0 -1 9 
S1 0 0 1 1 10 
x1 1 0 0 -0,2 2 
x2 0 1 0 -0,2 3 
 
Entra: S2 
Minimo{10/1} = 10. Logo, sai S1 
 
Linha nova S2 -> Linha S1/1 
Linha nova z -> linha z + 1*Linha nova S2 
Linha nova x1 -> linha x1 + 0,2*Linha nova S2 
Linha nova x2 -> linha x2 + 0,2*Linha nova S2 
 
Base x1 x2 S1 S2 Sol 
z 0 0 1 0 19 
S2 0 0 1 1 10 
x1 1 0 0,2 0 4 
x2 0 1 0,2 0 5 
 
 
Temos a solução ótima x1 = 4, x2 = 5, gerando um custo z=19 
 
 
 
 
4) a) Variáveis Básicas: x1 e S2 
 Variáveis Não Básicas: x2 e S1 
 
X1 = 4, s2=2, x2 = S1 = 0 
 
b) Sim. Pois não existem coeficientes negativos na linha z 
c) Sim. X2 tem coeficiente 0 na linha z e portanto poderia entrar na base sem alterar o custo 
da solução mas alterando o valor das variáveis da solução.