Baixe o app para aproveitar ainda mais
Prévia do material em texto
Capítulo 5 Problema da designação e do transbordo Pesquisa Operacional I Jhoab Negreiros 1 CAPÍTULO 5 Problema da designação e do transbordo 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. Exemplo 1. 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: R1 - R$ 100.000,00, R2 - R$ 80.000,00, R3 – R$ 60.000,00 e R4 – R$ 90.000,00. Exemplo 2. Resolva este exemplo 2 supondo que não seja possível enviar o vendedor 3 para a região 2. Capítulo 5 Problema da designação e do transbordo Pesquisa Operacional I Jhoab Negreiros 2 2 O Problema do Transbordo O problema de transbordo reconhece que pode ser mais barato despachar mercadorias com a utilização de nós intermediários ou transientes antes de chegar ao destino final. Esse conceito é mais geral do que o do problema de transporte normal, no qual são permitidas apenas expedições diretas entre uma origem e um destino. Exemplo 3. Ocorre transbordo na rede da figura a seguir porque seria concebível que a quantidade total de carros fornecida, de 2.200 pelas montadoras M1 (1.000) e M2 (1.200) passasse por qualquer um dos nós da rede antes de chegar a seus destinos nos nós C1 (800), C2 (900) e C3 (500) que representam três concessionárias. Quanto a isso, cada nó da rede que tenha arcos de entrada, bem como de saída (T1, T2, C1 e C2), agem como uma origem e também como um destino, e é denominado nó de transbordo. Os nós restantes são nós de fornecimento puros (M1 e M2) ou nós de demanda puros (C3). M1 – T1 � 3 M1 – T2 � 4 M2 – T1 � 2 M2 – T2 � 5 T1 – T2 � 7 T1 – C1 � 8 T1 – C2 � 6 T2 – C2 � 4 T2 – C3 � 9 C1 – C2 � 5 C2 – C3 � 3 O problema de transbordo pode ser convertido em um problema de transporte simples com seis origens (M1, M2, T1, T2, C1 e C2) e cinco destinos (T1, T2, C1, C2 e C3). As quantidades fornecidas e demandadas nos diferentes nós são calculadas por • Fornecimento em nó de suprimento puro igual fornecimento original; • Demanda em um nó de demanda puro igual demanda original; • Fornecimento em um nó de transbordo igual fornecimento original mais quantidade tampão; • Demanda em um nó de transbordo igual demanda original mais quantidade tampão; A quantidade tampão deve ser suficientemente grande para permitir que todas as unidades de fornecimento (ou de demanda) originais passem por qualquer um dos nós de transbordo. Seja a quantidade tampão desejada; então � �� �������� ��� �������� ����� � 1.000 � 1.200 ��� 800 � 900 � 500� � 2.200 �� �� Usando o tampão e os custos unitários de expedição dados na rede, construímos o problema de transporte simples equivalente como mostra a tabela a seguir. Capítulo 5 Problema da designação e do transbordo Pesquisa Operacional I Jhoab Negreiros 3 T1 T2 C1 C2 C3 M1 3 4 Infinito Infinito Infinito M2 2 5 Infinito Infinito Infinito T1 0 7 8 6 Infinito T2 Infinito 0 Infinito 4 9 C1 Infinito Infinito 0 5 Infinito C2 Infinito Infinito Infinito 0 3 Solução final do problema de transbordo obtida via Solver do Excel. T1 T2 C1 C2 C3 M1 M2 T1 T2 C1 C2 3 Atividades Exercício 1. 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 2. A rede mostrada na figura a seguir dá as rotas de expedição dos nós 1 e 2 para os nós 5 e 6, passando pelo nós 3 e 4. Os custos unitários d expedição são mostrados nos respectivos arcos. Resolva o problema de transbordo correspondente. (Observação: R$ 1,00 de (3) – (4) e R$ 3,00 (4) – (3)) Capítulo 5 Problema da designação e do transbordo Pesquisa Operacional I Jhoab Negreiros 4
Compartilhar