Baixe o app para aproveitar ainda mais
Prévia do material em texto
Capítulo 4 Problema do Transporte Pesquisa Operacional I Jhoab Negreiros 1 CAPÍTULO 4 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 No exemplo 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 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 Capítulo 4 Problema do Transporte Pesquisa Operacional I Jhoab Negreiros 2 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. 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, … , � � �� Capítulo 4 Problema do Transporte Pesquisa Operacional I Jhoab Negreiros 3 • 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 � 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 2. Resolva o Exemplo 1 utilizando a estrutura matricial. 4 Atividades Exercício 1 – 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. Capítulo 4 Problema do Transporte Pesquisa Operacional I Jhoab Negreiros 4 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 2. Resolva novamente o exercício 1 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 Exercício 3. Resolva novamente o exercício 1 supondo o novo quadro. Moinho 1 2 3 4 Fornecimento 1 10 8 20 11 20 Silo 2 12 7 9 20 20 3 13 14 16 18 10 Demanda 12 20 14 20 Exercício 4. Resolva novamente o exercício 3, garantindo que cada silo receba pelo menos metade do seu pedido.
Compartilhar