Problemas de Transporte

Prévia do material em texto

Vitória LimaProblemas de
Transporte
Introdução
É um problema de programação linear que tem como objetivo minimizar os custos de transporte de
produtos, obedecendo limites de demanda e oferta.
Restrições dos problemas
O montante ofertado dever ser igual ao total demandado. No caso de oferta > demanda, deve ser
introduzido um destino fantasma. E no caso de demanda > oferta, dever ser introduzida uma
fonte de oferta fantasma.
a) As fábricas não podem produzir mais que suas capacidades instaladas;
b) Os centros de distribuição não desejam receber volumes acima de suas demandas.
A implementação das restrições de igualdade pode acontecer de duas formas para permitir a
aplicação do método:
1.
Método do Transporte
obtenção de uma solução inicial (método regra do canto noroeste e o processo do custo mínimo)
processo de melhoria da solução (método stepping-stone e método u-v)
O método do transporte divide-se em duas etapas:
1.
2.
Qualquer equação do sistema formada pelas restrições do modelo
Pode ser obtida por uma combinação linear das demais, indicando que só existem (m+n-1) equações
independentes daquele sistema. Para garantir que esta é uma solução viável inicial é preciso que:
a) a solução satisfaça as m + n restrições do modelo;
b) seja forma por m+n-1 variáveis;
c) seja um ponto extremo do conjunto de soluções viáveis (não possa ser obtida por nenhuma
combinação convexa de quaisquer outras soluções viáveis do problema ou ainda não forma um
circuito fechado, no quadro de soluções, com as suas variáveis básicas).
Modelo Matemático
Teorema
Somando-se as m restrições de oferta, obtém-se: 
Somando-se as n restrições de demanda, obtém-se: 
Assim, temos que 
Regra do Canto Noroeste
Iniciar pela célula superior esquerda (canto noroeste do quadro);
Colocar nessa célula a maior quantidade permitida pela oferta e demanda correspondentes;
 Atualizar os valores da oferta e da demanda que foram modificados pelo passo 2;
 Seguir para a célula a direita se houver alguma oferta restante e voltar ao passo 2. Caso
contrário, seguir para a célula inferior e voltar ao passo 2.
1.
2.
3.
4.
Vitória Lima
Localizar no quadro de custos o menor custo que não tenha oferta ou demanda nula;
 Colocar na célula correspondente do quadro de soluções a maior quantidade permitida pela
oferta e demanda correspondentes;
 Atualizar os valores da oferta e da demanda que foram modificados pelo passo 2 e voltar ao
passo 1. 
1.
2.
3.
O processo continua até que sejam esgotadas as ofertas de todas as origens e supridas as demandas de
todos os destinos. Neste método a solução inicial depende das ofertas, das demandas e dos custos dos
transportes.
A aplicação da regra está concluída quando a célula inferior direita do quadro de soluções for
alcançada. Neste método a solução inicial é obtida sem se levar em consideração os custos
dos transportes, depende apenas exclusivamente das ofertas das origens e das
demandas dos destinos.
Processo do Custo Mínimo
MÉTODO “U-V”
Seja o modelo do transporte:
Para rescrever a função objetivo apenas em função das variáveis não básicas é preciso eliminar as
variáveis básicas da função objetivo. Para isso deve-se somar a função objetivo múltiplos das
restrições do modelo.
Vitória Lima
Sejam u1, u2, ..., um os valores (a determinar) pelos quais se devem multiplicar a 1.a, 2.a,..., m.a
equações de restrição de oferta, respectivamente, antes de somá-las à função objetiva. Sejam v1, v2,...,
vm os múltiplos análogos para cada uma equação de restrição de demanda.
Somando-se esses múltiplos das restrições à função objetivo, ela transforma-se em:
e assim, 
Logo, conhecida uma solução viável básica, deve-se ter para cada uma das (m+n-1)
variáveis básicas, de modo a eliminá-las da função objetivo que ficará expressa apenas em função das
variáveis não-básicas.
Usa-se os mesmos critérios do método simplex para determinar se a solução encontrada é básica e a
variável que entra e a variável que sai da base.
Vitória Lima