Baixe o app para aproveitar ainda mais
Prévia do material em texto
Capítulo 2 Problema do Transporte Pesquisa Operacional II Jhoab Negreiros 1 CAPÍTULO 2 Problema do Transporte 1 Problema do Transporte Um problema bastante comum que muitas vezes pode ser modelado como um problema de programação linear é o problema de transporte. Este problema envolve o transporte de alguma carga de diversas fontes a diversos pontos de destino. Dados o custo da distribuição entre cada fonte e destino, as produções das fontes e as capacidades dos destinos pretendem-se minimizar o custo total do transporte. 2 O Problema do Transporte como um PPL Nos dois exemplos a seguir é mostrado como modelar um problema do transporte utilizando a mesma estrutura que é aplicada nos problemas clássicos de programação linear. Exemplo 1. Uma firma comercial tem 40 unidades de mercadoria no depósito D1 e 50 unidades no depósito D2. Deve enviar 30 unidades ao cliente A e 40 ao cliente B. Os gastos de transporte por unidade de mercadoria estão indicados no esquema abaixo. De que maneira deve enviar essas mercadorias para que o gasto com transporte seja mínimo? Capítulo 2 Problema do Transporte Pesquisa Operacional II Jhoab Negreiros 2 Exemplo 2. Uma empresa produz televisão em 3 fábricas: São Paulo, João Pessoa e Manaus. Os pontos principais de revenda, com as respectivas encomendas mensais são: Rio de Janeiro 6.000 unidades Salvador 5.000 unidades Aracajú 2.000 unidades Maceió 1.000 unidades Recife 3.000 unidades A produção máxima mensal em cada fábrica é: São Paulo 10.000 unidades João Pessoa 5.000 unidades Manaus 6.000 unidades O custo de transportes das fábricas até as revendas é dado pelo quadro abaixo: R$ por 1.000 unidades de TV. Para De Rio de Janeiro (1) Salvador (2) Aracaju (3) Maceió (4) Recife (5) (1) São Paulo 1.000 2.000 3.000 3.500 4.000 (2) João Pessoa 4.000 2.000 1.500 1.200 1.000 (3) Manaus 6.000 4.000 3.500 3.000 2.000 Determinar o número de unidades produzidas em cada fábrica e entregues a cada revenda, a fim de minimizar o custo de transporte. Capítulo 2 Problema do Transporte Pesquisa Operacional II Jhoab Negreiros 3 3 Modelos de Transporte O modelo de transporte pode ser representado por uma matriz em que as linhas representam os centros produtores e as colunas, os centros distribuidores, ou seja, Centro consumidor 1 Centro consumidor 2 ⋯ Centro consumidor n Centro produtor 1 ��� ��� ⋯ ��� Centro produtor 2 ��� ��� ⋯ ��� ⋮ ⋮ ⋮ ⋱ ⋮ Centro produtor m ��� ��� ⋯ ��� em que � define a quantidade produzida na origem � e é consumida no destino �. A definição do modelo de transporte é: �� � =��� � � �� � �� Sujeita as restrições: • Restrições de origens; �� = � ; � = 1,2, … ,� � �� • Restrições de destinos; �� = � ; � = 1,2, … , � � �� • Restrições de não negatividade. � ≥ 0; � = 1,2, … ,�; � = 1,2, … , � em que: � = destinos � = origens � = produção da origem � � = demanda do destino � � = quantidade enviadas de � para � � = custo de transporte de � para � Capítulo 2 Problema do Transporte Pesquisa Operacional II Jhoab Negreiros 4 Para que o modelo do transporte tenha solução viável, é necessário que o total de oferta seja igual ao total da demanda, ou seja, �� =�� � �� � �� No caso de oferta maior que demanda, introduz-se uma variável representando uma demanda fictícia, indicando a necessidade de um novo centro consumidor e o custo de transporte de todas as origens para esse destino fictício é nulo. A demanda desse destino é dada pela diferença entre o total ofertado e total demandado. No caso de demanda maior que oferta, introduz-se uma oferta fictícia, indicando a necessidade de uma nova fábrica e o custo de transporte de todos os destinos para essa origem fictícia é nulo. A oferta dessa origem é dada pela diferença entre o total ofertado e o total demandado. Agora os dois exemplos iniciais será resolvidos novamente via Solver, mas dessa vez utilizando a estrutura de matrizes. Exemplo 3. Resolva o Exemplo 1 utilizando a estrutura matricial. Exemplo 4. Resolva o Exemplo 2 utilizando a estrutura matricial. 4 Atividades Exercício 1. No quadro de transporte a seguir, a terceira linha mostra às necessidades nos destinos e a quarta coluna as disponibilidades nas origens. Os outros dados representam custos unitários de transporte das origens para os respectivos destinos. 15 20 15 150 12 20 15 300 100 150 200 Determinar o plano de transporte que minimiza o custo total das transferências. Exercício 2. Resolva o exercício 1 novamente considerando o quadro abaixo. 15 20 15 150 12 20 15 250 170 150 230 Capítulo 2 Problema do Transporte Pesquisa Operacional II Jhoab Negreiros 5 Exercício 3. Uma Companhia despacha caminhões de grãos provenientes de três silos para quatro moinhos. As quantidades fornecidas e as demandas aliadas aos custos unitários de transporte por caminhões nas diferentes rotas estão resumidas na tabela a seguir. Moinho 1 2 3 4 Fornecimento 1 10 8 20 11 15 Silo 2 12 7 9 20 25 3 13 14 16 18 10 Demanda 5 15 15 15 Exercício 4. Resolva novamente o exercício 3 supondo que as seguintes situações: (a) Não é possível enviar caminhões do Silo 2 para o Moinho 2 (b) É possível enviar no máximo 5 caminhões do Silo 2 para o Moinho 2
Compartilhar