Operaciones

Solo disponible en BuenasTareas
  • Páginas : 9 (2181 palabras )
  • Descarga(s) : 0
  • Publicado : 26 de enero de 2011
Leer documento completo
Vista previa del texto
Problema de Transporte (Redes)

O Problema de Transporte consiste em determinar o menor custo (ou o maior lucro) em transportar produtos de várias origens para vários destinos.

Aplicação direta em Logística.

O Problema de Transporte é também um problema de P.L., porém devido a sua importância e ao mau desempenho do Simplex para este tipo de problema, este será estudado de maneiraespecifica.

Exemplos: 1) Transportar produtos de m fábricas para n estoques; 2) Transportar produtos de m estoques para n lojas.

Outro Exemplo Uma companhia enlata ervilhas nas suas unidades “Cannery1, Cannery2, Cannery3” e transporta as latas de ervilha por caminhão para os seus estoques “Warehouse1, Warehouse2, Warehouse3, Warehouse4”.

A tabela abaixo mostra os custos de transporte, adisponibilidade nas unidades “Cannery” e as necessidades nos estoques.

A representação esquemática abaixo ilustra o problema

A função objetivo, a ser minimizada, é:

Z = 464x11 + 513x12 + 654x13 + 867 x14 + 352x 21 + 416x 22 + 690x 23 + 791x 24 + 995x 31 + 682x 32 + 388x 33 + 685x 34

As restrições são:
x11 + x12 + x13 + x14 x21 x11 x12 x13 x14 + x21 + x22 + x23 + x24 + x22 + x23 + x24x31 + x31 + x32 + x33 + x34 + x32 + x33 + x34 = 75 = 125 = 100 = 80 = 65 = 70 = 85

com

x ij ≥ 0

(i = 1,2,3; j = 1,2,3,4)

O modelo generalizado fica:

min Z = ∑ ∑ cij x ij
i =1 j=1
n

m n

sujeito a:

j=1 m

∑ x ij = s i

disponibilidade demanda

i =1

∑ x ij = d j

x ij ≥ 0

(i = 1,..., m; j = 1,...n )

Algoritmo Como o Problema de Transporte é um problema deP.L., o Simplex pode ser utilizado. Porém, devido as características específicas do Problema de Transporte, uma versão modificada do Simplex, denominado, “Método Simplex de Transporte” torna a resolução deste tipo de problema muito mais eficiente, quando comparado ao Simplex tradicional. O algoritmo todo pode ser executado realizando operações sobre uma tabela com a seguinte forma:

cij é o custode transporte da origem i para o destino j; xij é a quantidade transportada da origem i para o destino j; dj é a demanda do destino j; si é a oferta da origem i; m é o número de origens e n é o número de destinos.

Exemplo Considere a seguinte tabela abaixo:

1o Passo: Solução Inicial Como no Simplex tradicional, faz-se necessário achar uma solução viável inicial. A maneira mais simplespara esta tarefa é através do Método do Canto Noroeste.

2o Passo: Critério de Otimalidade Como no Simplex tradicional, uma solução é analisada se pode ou não ser melhorada observando-se os coeficientes das variáveis não básicas na função-objetivo. a) Escrever a função-objetivo em termos das variáveis não básicas. Multiplicar cada restrição de linha pelo número –ui e cada restrição de coluna pelonúmero –vj e somar as novas linhas e colunas na função-objetivo de tal maneira que os coeficientes das variáveis básicas sejam todos nulos. Se xij é básico: cij - ui - vj = 0 Essas igualdades compõem um sistema de m + n – 1 equações com m + n incógintas. A solução desse sistema é obtida atribuindo-se um valor arbitrário a uma das incógnitas e calculando as demais.

De posse desses valores,calcula-se os coeficientes das variáveis não-básicas: Se xij é não-básico: coeficiente = cij - ui - vj Se todos esses valores forem não-negativos a solução é ótima. Se houver coeficientes negativos, implica que a solução poderá ser melhorada (minimizada). b) A variável que entra na base é a variável cujo coeficiente negativo tenha o maior valor absoluto. c) A introdução de uma nova variável na baseocasiona uma reação em cadeia para compensar as restrições de linha (oferta) e coluna (demanda). O valor da variável que entra deve ser o maior valor possível, sem tornar nenhuma variável básica negativa. A variável básica que tiver seu valor anulado em conseqüência da variável que entra será a variável que sai da base. d) Voltar ao item a) até que a solução seja ótima.

Continuando o exemplo,...
tracking img