Prova Pesquisa operacional 1

Prévia do material em texto

GABARITO 
DISCIPLINA 
EPO001 - Pesquisa Operacional I 
APLICAÇÃO 
01/10/2020 
CÓDIGO 
DA PROVA P007 
 
QUESTÕES OBJETIVAS 
Questão 1.1 
Sejam as seguintes associações entre as figuras das regiões factíveis com as formulações de 
programação linear e com as soluções factíveis: 
 
 var x1 >= 0; 
var x2 >= 0; 
 
maximize z: 2*x1 + 3*x2; 
 
subject to r1: 3*x1 + x2 <= 13; 
subject to r2: 2*x2 <= 6; 
subject to r3: 2*x1 <= 10; 
 
end; 
 
De posse dessas informações, analise as seguintes afirmativas: 
I. A restrição (r2) está ativa na solução ótima. 
II. A restrição (r1) não está ativa na solução ótima. 
III. A coordenada x1 da solução ótima é dada por 3. 
IV. A coordenada x2 da solução ótima é dada por 3. 
 
Considerando as afirmativas como verdadeiras ou falsas (V ou F), assinale a alternativa correta: 
a) F – F – F – F 
b) V – F – V – F 
c) V – F – F – V 
d) F – V – F – V 
e) F – V – V – V 
 
RESOLUÇÃO 
A resposta correta é: V – F – F – V 
 
Justificativa 
Solução ótima: x1 = 3,33 e x2 = 3. Portanto, as restrições ativas são: (r1) e (r2). 
Questão 1.2 
O diagrama da Figura 3 representa dois possíveis cenários de fluxo de produtos em um centro de 
distribuição: cenário 1 - a Figura 3(A) representa o fluxo direto de carga; cenário 2 - a Figura 3(B) 
representa o fluxo passando por pontos intermediários. 
 
 
Figura 3(A): fluxos entre Oi e Dj. Figura 3(A): pontos intermediários Wk. 
 
No cenário 1, os pontos Oi correspondem a origem da carga, ao passo que Dj são os pontos de 
destino. Assuma que: 
 A variável de decisão xij corresponde ao fluxo do arco de origem Oi e destino Dj; 
 A capacidade de produção de cada ponto Oi é fi; 
 A demanda de cada ponto Dj é dj. 
 
No cenário 2, além das informações anteriores, têm-se três pontos intermediários W1, W2 e W3 pelos 
quais as cargas deverão passar. Assuma que: 
 O fluxo entre os pontos Oi e Wk é representado pelas variáveis xik e o fluxo entre os pontos Wk 
e Dj é representado pelas variáveis ykj; 
 A capacidade de produção de cada ponto Oi é fi; 
 A demanda de cada ponto Dj é dj. 
 
Os custos de transporte são dados por: cenário 1: cij; cenário 2: cik e ckj. 
 
De posse dessas informações, analise as seguintes afirmativas: 
I. Para o cenário 1, as restrições de balanço de carga no ponto O1 é dada por x11 + x12 ≥ d1. 
II. Para o cenário 1, a função objetivo de minimização dos custos considerando apenas o fluxo 
dos arcos contabilizados nas restrições de balanço de carga no ponto O1 é dada por: c11x11 + 
c12x12. 
III. Para o cenário 2, as restrições de balanço de carga no ponto W1 é dada por x11 + x12 = y11 + y12. 
IV. Para o cenário 2, a restrição que estabelece que pelo ponto W1 não passa um fluxo carga 
maior que Cap1 é dada por: x11 + x21 + x31 ≤ Cap1. 
 
Considerando as afirmativas verdadeiras ou falsas (V ou F), assinale a alternativa correta: 
a) F – F – F – F 
b) V – F – V – F 
c) V – F – F – V 
d) F – V – F – V 
e) F – V – V – V 
 
 
RESOLUÇÃO 
A resposta correta é: F – V – F – V 
 
Justificativa 
I. Para o cenário 1, as restrições de balanço de carga no ponto Oi são dadas por xi1 + xi2 ≤ fi, em 
que i é i-ésimo nó de origem para i = 1, para i = 2: xi1 + xi2 + xi3 ≤ fi, para i = 3: xi2 + xi3 ≤ fi. 
II. Para o cenário 1, a função objetivo de minimização dos custos considerando apenas o fluxo dos 
arcos contabilizados nas restrições do Item (A) é dada por: ci1xi1 + ci2xi2, em que i é o i-ésimo nó 
de origem para i = 1, para i = 2: ci1xi1 + ci2xi2 + ci3xi3, para i = 3: ci2xi2 + ci3xi3. 
III. Para o cenário 2, a restrição de balanço de carga no ponto Wk é dada por x1k + x2k = yk1 + yk2, em 
que k é o k-ésimo nó intermediário para k = 1 e 3, mas para k = 2, têm-se: x1k + x2k + x3k = yk1 + yk2 
+ yk3. 
IV. Para o cenário 2, a restrição que estabelece que pelo ponto Wk não passa um fluxo carga maior 
que Capk é dada por: x1k + x2k ≤ Capk para k = 1 e 3, mas para k = 2, têm-se: x1k + x2k + x3k ≤ Capk. 
 
 
Questão 1.3 
O modelo matemático do problema de designação é dado pelas Eqs (1)-(4). 
 
 
Min 
∑ ∑ 𝑝𝑖𝑗𝑥𝑖𝑗
2
𝑗=1
2
𝑖=1
 
 
(1) 
 
S.A. 
∑ 𝑥𝑖𝑗 = 1
2
𝑗=1
 
 
,i 
 
(2) 
 
∑ 𝑥𝑖𝑗 = 1
2
𝑖=1
 
 
,j 
 
(3) 
 𝑥𝑖𝑗 ≥ 0 ,i, j (4) 
 
Em que: xij – alocação do professor i para a disciplina j (1 – sim e 0 - não), pij – preferência do professor 
i pela disciplina j. 
A solução ótima obtida por meio de um programa de computador retornou a Tabela 1 com valores 
para a variável xij. O índice i de xij é relacionado com as linhas e o índice j é relacionado com as colunas, 
ambos da Tabela 1. 
 
i\j 1 2 3 4 5 6 7 
1 0 1 0 0 0 0 0 
2 0 0 1 0 0 0 0 
3 1 0 0 0 0 0 0 
4 0 0 0 0 0 1 0 
5 0 0 0 0 0 0 1 
6 0 0 0 0 1 0 0 
7 0 0 0 1 0 0 0 
Tabela 1: valores de xij para a solução ótima obtida. 
 
De posse dessas informações, analise as seguintes afirmativas: 
I. A alocação ótima indica que a disciplina 3 será ministrada pelo professor 2. 
II. A alocação ótima indica que o professor 7 deverá ministrar a disciplina 5. 
III. A equação (2) para i igual a 5 garante que a disciplina 5 será alocada a um único professor. 
IV. A equação (3) para i igual a 3 garante que o professor 3 será alocado a uma única disciplina. 
 
Considerando as afirmativas verdadeiras ou falsas (V ou F), assinale a alternativa correta: 
a) V – F – F – F 
b) V – F – V – F 
c) V – F – F – V 
d) F – V – F – V 
e) F – V – V – V 
 
RESOLUÇÃO 
A resposta correta é: V – F – F – F 
 
Justificativa 
Resumo das alocações de acordo com a solução ótima: 
Professor 1 2 3 4 5 6 7 
Disciplina 2 3 1 6 7 5 4 
 
Portanto, com base no quadro, a afirmativa (i) é verdadeira e afirmativa (ii) é falsa. 
Com relação às equações: 
(A) A Equação (2), para um dado i, garante que o i-ésimo professor seja alocado a uma única 
disciplina. 
(B) A Equação (3), para um dado j, garante que a j-ésima disciplina seja alocada a um único 
professor. 
Desse modo, as afirmativas (iii) e (iv) são falsas. 
 
 
Questão 1.4 
A formulação do problema de programação linear que minimiza os custos de produção e estoque 
que atende às restrições é dada pelas Eq. (1)-(5). 
 
 
Min 
 ∑ 𝑐𝑡𝑥𝑡 + 𝑓𝑡𝑦𝑡
4
𝑡=1
+ ∑ 𝑔𝑡𝐼𝑡
4
𝑡=0
 
 
(1) 
S.a. 𝐼0 = 10 (2) 
 𝐼𝑡 = 𝐼𝑡−1 + 𝑥𝑡 + 𝑦𝑡 − 𝑑𝑡, t (3) 
 𝑥𝑡 ≤ 𝑢𝑡, t (4) 
 𝐼𝑡 , 𝑥𝑡 , 𝑦𝑡 ≥ 0, t (5) 
 
Em que: xt é a quantidade de lotes produzidos com o quadro regular para o período t; yt é a 
quantidade de lotes produzidos com o mão de obra temporária para o período t; It é a quantidade de 
lotes armazenados no período t; dt é a demanda de lotes no período t; ut é o limite de produção de 
lotes empregando quadro regular de funcionários no período t; ct é o custo de produção por lote 
utilizando os quadros regulares no período t; ft é o custo de produção por lote utilizando mão de obra 
temporária no período t; gt é o custo de estoque por lote no período t. Considere todos os custos 
iguais a 1. 
Uma solução encontrada para esse problema foi condensada na Tabela 1. 
 
Variável Meses 
T 0 1 2 3 4 
xt - 30 30 30 25 
yt - 0 30 45 0 
It 10 0 0 0 0 
dt 40 60 75 25 
Tabela 1: resumo dos valores das variáveis para a solução ótima encontrada. 
 
De posse dessas informações, analise as seguintes afirmativas: 
I. O número de lotes produzidos pelo quadro regular de funcionários no período 3 é de 30 lotes. 
II. Não existe produção pela mão de obra temporária no período 3. 
III. O estoque no último período é zero. 
IV. A produção total no terceiro período é de 75 lotes. 
V. O custo total de produção regular mais temporária é igual a 190. 
 
Considerando as verdadeiras ou falsas (V ou F), assinale a alternativa correta: 
a) V – F – F – F – F 
b) V – F – V – F – V 
c) V – F – F – V – F 
d) F – V – F – V – V 
e) V – F – V – V – V 
 
RESOLUÇÃO 
A resposta correta é: V – F – V – V – V 
 
Justificativa 
A produção pelamão de obra temporária no período 3 é de 45 lotes, conforme a Tabela 1. 
 
 
QUESTÕES DISSERTATIVAS 
 
Questão 2 
Seja o modelo de programação linear dado pelas Equações (1)-(6). 
 
Max 3𝑥1 + 2𝑥2 (1) 
S.a.: 𝑥1 + 𝑥2 ≤ 9 (2) 
 3𝑥1 + 𝑥2 ≤ 18 (3) 
 𝑥1 ≤ 7 (4) 
 𝑥2 ≤ 6 (5) 
 𝑥1, 𝑥2 ≥ 0 (6) 
 
a) Desenhe corretamente as restrições. 
b) Sombreie a região factível corretamente. 
c) Associe corretamente no gráfico o nome das restrições às retas desenhadas. 
d) Marque no gráfico a solução ótima do problema. 
e) Calcule a coordenada do ponto ótimo. 
 
Área para desenho: 
 
 
X2 
 
10 
 
 
8 
 
 
6 
 
 
4 
 
 
2 
 
 
0 
 
 
-2 
 
 
 
-2 0 2 4 6 8 10 X1 
 
 
RESOLUÇÃO 
 
Rubricas | critérios de correção 
a) (26,64%): Desenhar corretamente as restrições (6,66% por reta correta). 
b) (6,66%): Sombrear a região factível corretamente. 
c) (39,96%): Associar corretamente no gráfico o nome das restrições às retas desenhadas (6,66% 
por reta correta). 
d) (6,66%): Marcar no gráfico a solução ótima do problema. 
e) (19,98%): Calcular coordenada do ponto ótimo. 
 
 
Questão 3 
A formulação do problema de programação linear que minimiza os custos de produção e estoque 
que atende às restrições é dada pelas Eq. (1)-(5). 
 
 
Min ∑ 𝑐𝑡𝑥𝑡 + 𝑓𝑡𝑦𝑡
4
𝑡=1
+ ∑ 𝑔𝑡𝐼𝑡
4
𝑡=0
 
 
(1) 
S.a. 𝐼0 = 10 (2) 
 𝐼𝑡 = 𝐼𝑡−1 + 𝑥𝑡 + 𝑦𝑡 − 𝑑𝑡, t 
(3) 
 𝑥𝑡 ≤ 𝑢𝑡, t 
(4) 
 𝐼𝑡 , 𝑥𝑡 , 𝑦𝑡 ≥ 0, t 
(5) 
 
Em que: xt é a quantidade de lotes produzidos com o quadro regular para o período t; yt é a 
quantidade de lotes produzidos com o mão de obra temporária para o período t; It é a quantidade de 
lotes armazenados no período t; dt é a demanda de lotes no período t; ut é o limite de produção de 
lotes empregando quadro regular de funcionários no período t; ct é o custo de produção por lote 
utilizando os quadros regulares no período t; ft é o custo de produção por lote utilizando mão de obra 
temporária no período t; gt é o custo de estoque por lote no período t. Considere todos os custos iguais 
a 1. 
Uma solução encontrada para esse problema foi condensada na Tabela 1. 
 
Variável Meses 
T 0 1 2 3 4 
xt - X1 15 15 15 
yt - 15 Y2 60 10 
It 10 0 0 I3 0 
dt 40 60 75 D4 
Tabela 1: resumo dos valores das variáveis para a solução ótima encontrada. 
 
De posse das informações anteriores, responda: 
a) Qual o valor X1 de lotes produzidos pelo quadro regular de funcionários? 
b) Qual o valor Y2 de lotes produzidos pela mão de obra temporária no período 2? 
c) Qual o estoque I3 no período 3? 
d) Qual a demanda D4 no quarto período? 
e) Qual o custo total de produção regular mais temporária? 
 
RESOLUÇÃO 
Todas as questões podem ser resolvidas observando diretamente a Tabela 1 (dt = It-1 + xt + yt - It) 
a) Qual o valor X1 de lotes produzidos pelo quadro regular de funcionários? 
Resp. 15 lotes (40=10+x1+15-0; x1=15). 
b) Qual o valor Y2 de lotes produzidos pela mão-de-obra temporária no período 2? 
Resp. 45 lotes (60=0+15+Y2-0; Y2=45). 
c) Qual o estoque I3 no período 3? 
Resp. zero lotes (75=0+15+60-I3; I3=0). 
d) Qual a demanda D4 no quarto período? 
Resp. 25 lotes (D4=0+15+10-0=25). 
e) Qual o custo total de produção regular mais temporária? 
Resp. 190 (X1+X2+X3+X4+Y1+Y2+Y3+Y4+I4)*1 
 
Variável Meses 
T 0 1 2 3 4 
xt - 15 15 15 15 
yt - 15 45 60 10 
It 10 0 0 0 0 
dt 40 60 75 25 
Tabela 1: resumo dos valores das variáveis para a solução ótima encontrada. 
 
Rubricas | critérios de correção 
a) (20%): Qual o valor X1 de lotes produzidos pelo quadro regular de funcionários? 
b) (20%): Qual o valor Y2 de lotes produzidos pela mão-de-obra temporária no período 2? 
c) (20%): Qual o estoque I3 no período 3? 
d) (20%): Qual a demanda D4 no quarto período? 
e) (20%): Qual o custo total de produção regular mais temporária?