Capítulo_3_-_Problema_da_Desig

Prévia do material em texto

Capítulo 3 Problema da Designação 
Pesquisa Operacional II Jhoab Negreiros 
1
 
 
 
 
 
 
 
 
 
 
 
 
 
 
CAPÍTULO 3 
Problema da Designação 
 
 
 
 
 
 
 
3.1 Problema da Designação 
 
 
Um caso especial do modelo de transporte é aquele em que cada origem tem uma unidade 
disponível e cada destino necessita também de uma única unidade, por exemplo, 
 
• Várias fábricas e vários destinos sendo que uma fábrica abastecerá apenas um destino; 
• Vários funcionários e várias tarefas, designar um funcionário para cada tarefa; 
• Várias obras e várias firmas, uma obra para cada firma. 
 
Modelo Matemático 
 
Minimizar ou maximizar a função 
∑∑
= =
=
m
i
n
j
ijij xcZ
1 1 
Sujeitas as restrições 
 
1
1
=∑
=
n
j
ijx
 para i = 1, 2, ..., m 
Capítulo 3 Problema da Designação 
Pesquisa Operacional II Jhoab Negreiros 
2
 
1
1
=∑
=
m
i
ijx
 para j = 1, 2, ..., n 
 
0≥xij para i = 1, 2, ..., m e para j = 1, 2, ..., n 
Note que ��� só pode ter valores zero ou um. 
 
Exemplo 1. O quadro representa os custos de transportes de uma máquina dos locais de depósito 
para as fábricas onde deverão ser instaladas. Designar uma máquina para cada fábrica com o 
menor custo total possível no programa: 
 
 
F1 F2 F3 F4 
L1 10 12 15 16 
L2 14 12 13 18 
L3 10 16 19 15 
L4 14 12 13 15 
 
Exemplo 2. O quadro representa as eficiências (capacidade de atingir o potencial da cada região) 
de quatro vendedores testados em quatro regiões. Os potenciais de vendas nas regiões são 
conhecidos. Designar um vendedor para cada região para maximizar o valor total das vendas. 
 
R1 R2 R3 R4 
V1 70% 60% 80% 90% 
V2 70% 80% 70% 90% 
V3 60% 90% 60% 70% 
V4 70% 80% 70% 80% 
 
Potencial de vendas em milhares de R$: R1=100, R2=80, R3=60 e R4=90. 
 
Resolva este exemplo supondo que não seja possível enviar o vendedor 3 para a região 2. 
 
3.2 Atividades 
 
Exercício 1. Quatro locais L1, L2, L3 e L4 necessitam de um equipamento. Existem quatro 
equipamentos disponíveis, um em cada um dos depósitos D1, D2, D3 e D4. As quilometragens 
entre os locais necessitados e os depósitos estão no quadro: 
 
Depósitos 
Locais 
L1 L2 L3 L4 
D1 100 120 130 140 
D2 80 70 120 90 
D3 100 80 100 110 
D4 90 90 120 80 
 
Capítulo 3 Problema da Designação 
Pesquisa Operacional II Jhoab Negreiros 
3
Exercício 2. Resolva o exercício 1, supondo que não seja possível expedir do depósito 1 para o 
local 3. 
 
Exercício 3. Resolva o exercício 1 novamente, supondo que não seja possível expedir do armazém 
1 para o local 1. 
 
Exercício 4. A empresa de ar condicionado Top Clima tem seis instalações programadas para o 
próximo mês. Ela poderá realizar no máximo duas instalações com pessoal próprio, e solicitou a 
quatro empreiteiras cadastradas o orçamento para cada um das obras e a disponibilidade para o 
serviço. O quadro a seguir resume os dados coletados. 
 
Empreiteiras 
Obras - Orçamentos em 1.000 unidades monetárias Disponibilidade: 
Número de obras 1 2 3 4 5 6 
A 12 20 25 30 22 20 2 
B 15 20 22 26 18 20 2 
C 16 24 26 22 21 21 2 
D 14 25 24 28 24 20 2 
Top Clima 13 25 30 27 20 15 2 
 
(a) Qual o plano de instalação de menor custo? 
(b) Resolva o problema supondo que cada empreiteira deve realizar pelo menos uma obra. 
(c) Resolva o problema supondo que a empreiteira Top Clima realize duas obras. 
(d) Resolva o problema supondo que a empreiteira Top Clima realize duas obras e as demais 
realize cada uma única obra. 
 
Exercício 5. A Top Clima tem anotado o número de horas estimadas pelas empreiteiras para 
realizar o serviço 
 
Empreiteiras 
Obras 
1 2 3 4 5 6 
A 200 250 300 310 280 230 
B 250 240 350 260 250 220 
C 220 260 380 250 260 250 
D 200 200 320 300 250 210 
 
A semana tem 40 horas de trabalho normal e a Top Clima pretende entregar as obras em seis 
semanas. A programação de hora extra onera o custo da obra em 20% da proporção de horas 
Capítulo 3 Problema da Designação 
Pesquisa Operacional II Jhoab Negreiros 
4
extras em relação ao total de horas, sobre o valor da obra. Que mudanças isto traz na 
programação? (Item (a) do exercício 4) 
 
Exercício 6. Devido às características das obras dos problemas 4 e 5, Top Clima exclui a 
possibilidade de algumas empresas realizarem determinadas obras (problemas de capacitação 
técnica, exigências específicas de clientes etc.) 
 
Empreiteira Obras excluídas 
A 5 e 6 
B 4 e 5 
C 1 e 4 
 
Qual a programação se usarmos também essas novas condições? 
 
Exercício 7. (No exercício 5) Se a Top Clima resolvesse por uma questão política atribuir a obra 6 
à empreiteira C, qual o custo desta política? 
 
Exercício 8. (No exercício 5) E no caso de a Top Clima atribuir o obra 6 à empreiteira D? Qual o 
custo desta decisão?