Prova Pesquisa Operacional_op2 Univesp

Prévia do material em texto

GABARITO 
DISCIPLINA 
EPO002 - Pesquisa Operacional II 
APLICAÇÃO 
26/11/2020 
CÓDIGO 
DA PROVA P008 
 
QUESTÕES OBJETIVAS 
Questão 1.1 
Uma manufatura precisa sequenciar as tarefas relacionadas às operações de produção em uma 
máquina. Os dados das tarefas são fornecidos na Tabela 1. Os tempos de setup das tarefas são dados 
na Tabela 2. A solução proposta é dada na Tabela 3. 
 
Tarefa 
Tempo 
Processamento (pi) 
Data de 
entrega (di) 
1 3 13 
2 6 6 
3 4 10 
4 5 18 
5 4 22 
Tabela 1: Dados de processamento e entrega das tarefas. 
 
Tarefa\Tarefa 1 2 3 4 5 
1 0 1 3 1 2 
2 2 0 2 2 1 
3 1 3 0 1 2 
4 2 1 1 0 1 
5 1 3 1 2 0 
Tabela 2: Dados de tempo de setup das tarefas. 
 
i|j 0 1 2 3 4 5 
0 0 0 0 0 0 1 
1 0 0 0 1 0 0 
2 1 0 0 0 0 0 
3 0 0 1 0 0 0 
4 0 1 0 0 0 0 
5 0 0 0 0 1 0 
Tabela 3: Valores de solução proposta xij. 
 
Considere que: 
(1) Parâmetros do modelo: o tempo de processamento da tarefa i é pi. O número de tarefas é n e 
igual a 5. A data de entrega da tarefa i é di. O tempo de setup entre as tarefas i e j é dado por 
sij. 
(2) Variáveis do modelo: a variável binária xij é igual a 1, se na máquina a tarefa i é sucedida pela 
tarefa j. A variável real ci é o instante de término da tarefa i. 
 
De posse das informações anteriores, marque com F ou V as afirmativas a seguir, e em seguida 
escolha a alternativa correta: 
( ) O tempo de processamento da tarefa 1 é 3 e da tarefa 3 é 4. 
( ) O tempo de setup para realizar a tarefa 5 após a tarefa 4 é 2. 
( ) A ordem de execução das tarefas é 5-4-1-3-2. 
( ) Para a solução fornecida, a tarefa 1 será finalizada com atraso 3. 
( ) O instante de término da tarefa 5 é 0. 
 
a) (F)-(V)-(V)-(V)-(F) 
b) (V)-(F)-(V)-(V)-(F) 
c) (V)-(V)-(V)-(V)-(V) 
d) (V)-(V)-(F)-(V)-(V) 
e) (F)-(F)-(F)-(F)-(F) 
 
RESOLUÇÃO 
A resposta correta é: (V)-(F)-(V)-(V)-(F) 
 
Justificativa 
(V) O tempo de processamento da tarefa 1 é 3 e da tarefa 3 é 4. 
Basta olhar os valores contidos na Tabela 1 para obter 3 e 4. 
(F) O tempo de setup para realizar a tarefa 5 após a tarefa 4 é 2. 
Basta olhar o valor contido na Tabela 2 para obter o valor 1. 
(V) A ordem de execução das tarefas é 5-4-1-3-2. 
Basta ordenar os valores contidos na Tabela 3, começando na linha cujo índice é igual ao índice da 
tarefa fictícia inicial, ou seja, 0. Depois verificar qual coluna possui valor igual à 1, isto é, a coluna com 
índice 5. De posse do valor 5, ir para a linha de mesmo índice e procurar qual o índice da coluna para 
o qual o valor é igual a 1, isto é, a coluna 4. Ao repetir esse processo até obter novamente o índice da 
tarefa fictícia 0, obtém-se: 5-4-1-3-2. 
 
Tarefa 1 2 3 4 5 
Tempo de processo (pi) 3 6 4 5 4 
Tempo de setup (sij) 2 3 3 2 0 
Data entrega (di) 13 6 10 18 22 
Ordem processo 3 5 4 2 1 
Instante Término (Ci+pj+sij) 16 32 23 11 4 
Atraso (Max(di-Ci,0)) 3 26 13 0 0 
 
(V) Para a solução fornecida, a tarefa 1 será finalizada com atraso 3. 
De acordo com a Tabela da solução detalhada, o valor é 3. 
(F) O instante de término da tarefa 5 é 0. 
De acordo com a Tabela da solução detalhada, o valor é 4. 
 
 
Questão 1.2 
Em uma empresa deseja elaborar uma grade horária de modo que haja um número mínimo de 
funcionários trabalhando em cada dia da semana, conforme dados da Tabela 1. Além disso, um 
acordo entre os colaboradores e a empresa obriga que um funcionário trabalhe por cinco dias 
consecutivos e tire folga por dois dias consecutivos. Esse problema foi modelado como um problema 
de programação linear cuja função objetivo é minimizar o número de funcionários sujeito às restrições 
de um número mínimo de funcionários por dia. A variável de decisão é Ni e corresponde ao número 
de funcionários que começa a trabalhar no dia i, i = 1, 2, ..., 7. 
 
Dia Dom Seg Ter Qua Qui Sex Sab 
# 13 15 12 17 12 11 16 
Tabela 1: Número mínimo de funcionários por dia da semana. 
 
Uma solução para os dados da Tabela 1 é dada na Tabela 2. 
 Domingo Segunda Terça Quarta Quinta Sexta Sábado 
N1 1 1 1 1 1 
N2 3 3 3 3 3 
N3 0 0 0 0 0 
N4 5 5 5 5 5 
N5 3 3 3 3 3 
N6 0 0 0 0 0 
N7 8 8 8 8 8 
Tabela 2: Solução proposta para o problema do número de funcionários. 
 
Considere as afirmações como verdadeiras (V) ou falsas (F), e em seguida escolha a alternativa correta: 
( ) A restrição relativa ao dia de Segunda está ativa na solução proposta. 
( ) A restrição relativa ao dia de Terça não está ativa na solução proposta. 
( ) O número total de colaboradores no dia de Domingo é 1. 
( ) O número total de colaboradores que começa a trabalhar na Segunda é 3. 
( ) O número total de colaboradores necessários para todos os dias é 20. 
 
a) (V)-(F)-(F)-(V)-(V) 
b) (F)-(F)-(F)-(V)-(V) 
c) (V)-(V)-(F)-(V)-(V) 
d) (V)-(F)-(V)-(V)-(V) 
e) (V)-(F)-(F)-(F)-(V) 
 
RESOLUÇÃO 
A resposta correta é: (V)-(F)-(F)-(V)-(V). 
 
Justificativa 
O quadro no qual as variáveis são reunidas para verificar o atendimento das restrições de demanda 
mínima de pessoal é dado por: 
 Domingo Segunda Terça Quarta Quinta Sexta Sábado 
N1 1 1 1 1 1 
N2 3 3 3 3 3 
N3 0 0 0 0 0 
N4 5 5 5 5 5 
N5 3 3 3 3 3 
N6 0 0 0 0 0 
N7 8 8 8 8 8 
Total 17 15 12 17 12 11 16 
Demanda 13 15 12 17 12 11 16 
 
 
Questão 1.3 
Uma empresa de varejo está revendo o posicionamento de seus centros de distribuição (CDs) de modo 
a melhor atender seus clientes. Foi observado que esse problema pode ser modelado como um 
problema de p-medianas capacitado. Foi verificado que a solução atual proposta para esse problema é 
dada na Figura 1. 
Figura 1: Proposta de alocação entre os CDs (quadrados) e os clientes (círculos). 
 
A alocação inicialmente proposta não necessariamente observou as capacidades dos CDs e a demanda 
dos clientes dadas nas Tabelas 1 e 2, respectivamente. 
 
Facilidade 1 2 3 4 5 6 
Capacidade 10 10 10 10 10 10 
Tabela 1: Valores de capacidade de cada CD. 
 
Cliente 1 2 3 4 5 6 7 8 9 10 11 12 13 14 
Demanda 2 1 3 4 3 4 2 1 3 6 3 3 3 1 
Tabela 2: Valores de demandas de cada cliente. 
 
A formulação matemática é dada pelas Equações (1)-(6). 
Min 
 Ii Jj
jiji xd ,,
 
(1) 
S.a.: Jj , 1, =
Ii
jix
 
(2) 
 J ,I , ,  jiyx iji (3) 
 

=
Ii
i py
 
(4) 
 I ,, 

iyQxq ii
Jj
jij
 
(5) 
 
JI
ij Bx  , 
I
i By  
(6) 
 
Em que: xi,j é uma variável binária que indica se o cliente j está conectado no CD i (= 1) ou não (=0), y i é 
uma variável binária que indica se um CD i foi aberto (= 1) ou não (= 0), dij é a distância entre o cliente j 
e o CD i, p é o total de CDs que devem ser abertas, qj é a demanda do cliente j e Qi é a capacidade do 
CD i. 
 
De posse dessas informações, as afirmativas como verdadeiras (V) ou falsas (F), e em seguida escolha a 
alternativa correta: 
I. A restrição de alocação do cliente 2 em um CD é x1,2 + x2,2 + x3,2 + x4,2 + x5,2 + x6,2 = 1. 
II. A restrição relativa ao atendimento do cliente 3 pelo CD 5, apenas se o CD 5 estiver aberto, é 
dada por x5,3 ≤ y5. 
III. A solução proposta na Figura 1 é factível em relação à restrição de capacidade do CD 1. 
IV. A solução proposta na Figura 1 é tal que a restrição de capacidade máxima do CD3 não está na 
igualdade. 
V. Para a solução proposta têm-se: x5,14 = 1 e x5,1 = 0. 
 
a) (F)-(V)-(V)-(V)-(F) 
b) (V)-(F)-(F)-(V)-(V) 
c) (V)-(V)-(V)-(V)-(F) 
d) (V)-(V)-(F)-(V)-(V) 
e) (F)-(F)-(F)-(F)-(F) 
 
 
RESOLUÇÃO 
A resposta correta é: (V)-(V)-(V)-(V)-(F). 
 
Justificativa 
I. Verdadeira, pois decorre de 
Jj , 1, =
Ii
jix
 para j = 2. 
II. Verdadeira, pois decorre de 
J ,I , ,  jiyx iji para (CD) i = 5 e (cliente) j = 3. 
III. Verdadeira. Da Figura 1 pode ser obtido que os clientes 2, 3 e 4 são atendidos pelo CD 1. Da Tabela 
2, obtém-se que: 
Cliente 1 2 3 4 5 6 7 8 9 10 11 12 13 14 
Demanda 2 1 3 4 3 4 2 1 3 6 3 3 3 1 
 
A Tabela 1 fornece a capacidade do CD 1 como igual a 10 e, portanto, a demanda de todos osclientes 
pode ser atendida (1 + 3 + 4 = 8), e essa restrição é factível. 
IV. Verdadeira. Da Figura 1 pode ser obtido que os clientes 5 e 6 são atendidos pelo CD 3. Da Tabela 2, 
obtém-se que: 
Cliente 1 2 3 4 5 6 7 8 9 10 11 12 13 14 
Demanda 2 1 3 4 3 4 2 1 3 6 3 3 3 1 
A Tabela 1 fornece a capacidade do CD 3 como igual a 10 e, portanto, a demanda de ambos os clientes 
pode ser atendida (3 + 4 = 7), e essa restrição é factível e não está na igualdade. 
V. Verdadeira, pois de fato o CD 5 atende ao cliente 14 (x5,14 = 1), mas não ao cliente 1 (x5,1 = 0), pela 
figura 1, x5,1 = 1, portanto, o item V é falso. 
 
 
Questão 1.4 
Uma transportadora está planejando a melhor rota para atender seus clientes de modo a minimizar a 
distância percorrida. Como só dispõe de um caminhão, foi aplicado o modelo do problema do caixeiro 
viajante (PCV) sem as restrições de sub-rotas, de modo que a solução obtida foi como dada na Figura 
1. 
Figura 1: Solução PCV com sub-rotas. 
Considere que: 
(1) Os clientes são representados pelos círculos; 
(2) Parâmetros do modelo: o custo de conexão entre o cliente i e o cliente j é dado por cij. O 
número de cidades é n é igual a 7. 
(3) Variáveis do modelo: a variável binária xij é igual a 1, se o caminhão faz o percurso que tem 
origem na cidade i e vai para a cidade j. 
(4) Uma restrição clássica de eliminação de sub-rotas com 2 arcos é dada por: xik + xkj  1. 
(5) Uma restrição de eliminação de sub-rotas sequencial é dada por: .
1−+− nnxuu ijji . 
 
De posse das informações anteriores, marque com F ou V as afirmativas a seguir e em seguida escolha 
a alternativa correta: 
( ) A solução da Figura 1 é tal que x12 = 1, x23 = 1, x34 = 1, x41 = 1, x65 = 1, x57 = 1, x76 = 1. 
( ) A solução da Figura 1 é tal que a restrição de sub-rota de 2 arcos x12 + x21  1 é satisfeita. 
( ) A solução da Figura 1 é tal que a restrição de sub-rota de 3 arcos x65 + x57 + x76  2 é satisfeita. 
( ) Para eliminar a sub-rota de 3 arcos, basta utilizar a restrição sequencial dada por: 
67 6556 +− xuu . 
 
a) (V)-(V)-(V)-(V) 
b) (F)-(F)-(V)-(F) 
c) (V)-(V)-(F)-(F) 
d) (V)-(V)-(F)-(V) 
e) (F)-(V)-(F)-(V) 
RESOLUÇÃO 
A resposta é: V – V – F – V. 
 
Justificativa 
(V) A solução da Figura 1 é tal que x12 = 1, x23 = 1, x34 = 1, x41 = 1, x65 = 1, x57 = 1, x76 = 1. 
(V) A solução da Figura 1 é tal que a restrição de sub-rota de 2 arcos x12 + x21  1 é satisfeita. 
(F) A solução da Figura 1 é tal que a restrição de sub-rota de 3 arcos x65 + x57 + x76  2 não é satisfeita. 
(V) Para eliminar a sub-rota de 3 arcos, basta utilizar a restrição sequencial dada por: 
67 6556 +− xuu . 
 
 
QUESTÕES DISSERTATIVAS 
 
Questão 2 
Em uma manufatura existem 4 máquinas e 6 produtos que podem ser produzidos. O roteiro do fluxo 
de produção de cada um dos 6 produtos através de cada uma das 4 máquinas, e o respectivo tempo 
necessário para produzir uma unidade de cada produto, é como dado na Tabela 1. 
 
Prod Etapa 1 Etapa 2 
 
Maq. T Maq. T 
1 M1 3 M2 1 
2 M4 2 M2 2 
3 M1 1 M3 3 
4 M4 3 M3 1 
5 M1 2 M4 2 
6 M2 1 M3 3 
Tabela 1: Roteiro de produção de cada produto. 
 
As disponibilidades de tempo de cada uma das 4 máquinas são dadas na Tabela 2. 
 
Máquina M1 M2 M3 M4 
Disp.(t) 13 10 10 14 
Tabela 2: Disponibilidade de tempo de cada uma das máquinas. 
 
O lucro a ser obtido com cada unidade de produto manufaturado é fornecido na Tabela 3. 
 
Produto P1 P2 P3 P4 P5 P6 
Lucro($) 4 7 3 6 2 5 
Tabela 3: Lucro obtido com cada produto manufaturado. 
 
Além das informações anteriores, é importante considerar que um número grande pode ser 
representado pelo valor M grande e que, no máximo, 3 produtos podem ser escolhidos. Para os 
dados fornecidos anteriormente, pede-se: 
(A) Escreva a restrição de limitação de utilização da máquina 1. 
(B) Escreva a restrição de limitação de utilização da máquina 2. 
(C) Escreva a restrição de limitação do número máximo de produtos. 
(D) Escreva a restrição de só se produzir o produto 3 se ele estiver no portfólio. 
(E) Escreva a função objetivo. 
 
RESOLUÇÃO 
(A) Escreva a restrição de limitação de utilização da máquina 1. 
M1: 3x1 + 1x3 + 2x5 <= 13 
(B) Escreva a restrição de limitação de utilização da máquina 2. 
M2: 1x1 + 2x2 + 1x6 <= 10 
(C) Escreva a restrição de limitação do número máximo de produtos. 
C1: y1 + y2 + y3 + y4 + y5 + y6 ≤ 3 
(D) Escreva a restrição de só se produzir o produto 3 se ele estiver no portfólio. 
L3: x3 ≤ My3 
(E) Escreva a função objetivo. 
Max z = 4x1 + 7x2 + 3x3 + 6x4 + 2x5 + 5x6 
 
 
Rubricas | critérios de correção 
Cada um dos itens vale 1,0. 
 
 
Questão 3 
Um fazendeiro tem 3.600 m de cerca e quer delimitar um campo retangular que está na margem de 
um rio reto. Ele não precisa cercar ao longo do rio. A Figura 1 ilustra essa situação. Visando encontrar a 
maior área possível, fornecer: 
 
(A) A correspondente dimensão x (lado menor) do campo. 
(B) A correspondente dimensão y (lado maior) do campo. 
(C) A correspondente valor da área do campo. 
(D) Caso o lado do Rio também tenha que ter cerca, a Figura 2 ilustra isso, qual será o valor do 
lado maior do campo? 
(E) Caso o lado do Rio também tenha que ter cerca, a Figura 2 ilustra isso, qual será o valor da 
área do campo? 
Figura 1: Campo retangular que possui um dos lados na margem de um rio. 
 
Figura 2: Campo retangular que possui todos os lados. 
 
RESOLUÇÃO 
A dedução geral desse problema é dado a seguir. Considera-se que a, b e P são valores dados e deseja-
se maximizar o valor de A. 
A área A é dada na equação (1) e a equação geral do perímetro P é dada pela equação (2). 
A = xy (1) 
ax + by = P (2) 
A área máxima é obtida colocando-se a variável y em evidência na equação (2) para a equação (3). 
y = (P – ax)/b (3) 
Utilizando a equação (3) na equação (1), têm-se: 
A = x (P – ax)/b = (Px – ax2)/b (4) 
A área máxima será obtida com A’(x) = 0: 
(P – 2ax) = 0 → x* = P/2a (5) 
A equação (5) aplicada na equação (2), fornece: 
a (P/2a) + by = P → by = P – P/2 → by = P/2 → y* = P/2b (6) 
Por fim, a área máxima a ser obtida é dada por: 
A* = x*y* = (P/2a)*(P/2b) → A* = P2/(4ab) (7) 
A partir das fórmulas fornecidas, é possível obter a seguinte tabela geral: 
Cenário a b x* y* A* 
1 - Sem cerca no rio 2 1 P/4 P/2 P2/8 
2 - Cerca de todos os lados 2 2 P/4 P/4 P2/16 
 
Das deduções anteriores, e P = 3.600 m, têm-se: 
(A): x* = 3600/4 = 900 m. 
(B): y* = 3600/2 = 1800 m. 
(C): A* = 1.620.000 m2 
(D): x* = y* = P/4 = 900 m. 
(E): A* = x*y* = 810.000 m2. 
 
Rubricas | critérios de correção 
Ao obter os valores corretos em cada item, obtém a pontuação total do item (2,0).