Lista_Exercícios_aula5

Prévia do material em texto

Universidade Federal do Pampa 
Campus Bagé – Engenharia de Produção 
Pesquisa Operacional II 
Programação de Redes 
 
1. Um laboratório de manipulação presta serviços de entrega aos clientes. A empresa possui 
duas filiais e fornece serviços a seis bairros diferentes. Tendo em vista que a demanda é 
superior à capacidade de entrega da companhia, ela gostaria de saber a quais clientes 
atender, em cada filial, de maneira a minimizar o custo de entrega. As capacidades das filiais, 
as demandas dos bairros e os custos unitários de entrega são mostrados na tabela a seguir. 
Apresente o diagrama de rede e a modelagem para o problema. 
 
 
 
2. Uma empresa de consultoria precisa alocar auditores a projetos, sendo que cada projeto 
requer apenas um auditor. A empresa possui um sistema interno de avaliação de auditores, 
de modo que para cada projeto há um escore para cada um dos auditores. No escore são 
considerados: experiência, rapidez e confiabilidade. O escore de cada auditor em cada um 
dos projetos da empresa é apresentado a seguir. Desenhe o diagrama de rede e modele o 
problema PL. 
 
 
 
3. Uma companhia de TV à cabo está estudando o fornecimento do seu serviço para cinco 
regiões. As possíveis conexões e distâncias entre as áreas são apresentadas a seguir. 
Determine a rede mais econômica pelo método da Árvore Geradora Mínima. 
 
Castro	
Alves	
Getúlio	
Vargas	
Centro	 São	Judas	 Menino	
Deus	
São	José	 Capacidade	
Filial	
Centro	
7,00	 9,00	 1,00	 12,00	 7,00	 4,00	 2.500	
Filial	São	
Judas	
4,00	 5,00	 12,00	 1,00	 3,00	 8,00	 2.000	
Demanda	 1.400	 1.560	 400	 150	 870	 620	
Projeto	
Escores	
Auditor	1	 Auditor	2	 Auditor	3	 Auditor	4	
1	 11	 4	 3	 9	
2	 3	 7	 2	 3	
3	 4	 9	 6	 5	
4	 5	 4	 7	 7	
 2 
 
 
Gabarito 
 
1. 
 
 
x
13
 = quantidade enviada do Centro para Castro Alves 
x14 = quantidade enviada do Centro para Getúlio Vargas 
x15 = quantidade enviada do Centro para Centro 
x16 = quantidade enviada do Centro para São Judas 
x17 = quantidade enviada do Centro para Menino Deus 
x18 = quantidade enviada do Centro para São José 
x23 = quantidade enviada de São Judas para Castro Alves 
x24 = quantidade enviada de São Judas para Getúlio Vargas 
x25 = quantidade enviada de São Judas para Centro 
x26 = quantidade enviada de São Judas para São Judas 
x27 = quantidade enviada de São Judas para Menino Deus 
x28 = quantidade enviada de São Judas para São José 
Min Z = 7x13 + 9x14 + 1x15 + 12x16 + 7x17 + 4x18 + 4x23 + 5x24 + 12x25 + 1x26 + 3x27 + 4x28 
s.a 
-x13 - x14 - x15 - x16 - x17 - x18 = - 2.500 (nó 1) 
6	
8	
1	
5	
2	
4	
3	
10	
1	
9	
5	
7	
6	
3	
4	
3	
 
 
 
 
Ce	
1	
SJ	
2	
CA	
3	
GV
4	
Ce	
5	
(-2.500)	
(+1.400)	
(+1.560)	
(+400)	
7	
(-2.000)	
SJ	
6	
MD	
7	
SJe	
8	
(+150)	
(+870)	
(+620)	
9	
1	
12	
7	
4	
4	
5	
12	
1	
3	
8	
 3 
-x23 – x24 – x25 – x26 – x27 – x28 = - 2.000 (nó 2) 
x13 + x23 ≤ 1.400 (nó 3) 
x14 + x24 ≤ 1.560 (nó 4) 
x15 + x25 ≤ 400 (nó 5) 
x16 + x26 ≤ 150 (nó 6) 
x17 + x27 ≤ 870 (nó 7) 
x18 + x28 ≤ 620 (nó 8 ) 
 
2. 
 
 
 
 
 
3. 
 
 
A1	
A2	
A3	
A4	
P1	
P2	
P3	
P4	
(-1)	
(-1)	
(-1)	
(-1)	
(+1)	
(+1)	
(+1)	
(+1)	
11	
3	
4	
5	
4	
7	
9	
4	
3	
2	
6	
7	
9	
3	
5	
7	
MaxZ =11x11 +3x12 + 4x13 + 5x14 + 4x21 + 7x22 + 9x23 + 4x24
+3x31 + 2x32 + 6x33 + 7x34 + 9x41 +3x42 + 5x43 + 7x44
s.a
x11 + x21 + x31 + x41 =1(P1)
x12 + x22 + x32 + x42 =1(P2)
x13 + x23 + x33 + x43 =1(P3)
x14 + x24 + x34 + x44 =1(P4)
x11 + x12 + x13 + x14 =1(A1)
x21 + x22 + x23 + x24 =1(A2)
x31 + x32 + x33 + x34 =1(A3)
x41 + x42 + x43 + x44 =1(A4)
xij = (0,1)
6	1	
5	
2	
4	
3	
1	
5	
3	
4	
3