Baixe o app para aproveitar ainda mais
Prévia do material em texto
Pesquisa Operacional Rafael Pinheiro Amantea, D.Sc. rafael.amantea@prof.una.br Aula – O problema de Transporte – Metodologia de solução para o “problema de transporte padrão” Exemplo Moinho Silo 1 2 3 4 Oferta 1 10 2 20 11 15 2 12 7 9 20 25 3 4 14 16 18 10 Demanda 5 15 15 15 Tabela simplex transporte Exemplo Destino Moinhos oferta u 1 2 3 4 O ri ge m Silo1 10 2 20 11 15 Silo2 12 7 9 20 25 Silo3 4 14 16 18 10 Demanda 5 15 15 15 Z = v Procedimento genérico para construir uma solução BV inicial. PASSO 1 : Regra do ponto extremo noroeste comece selecionando x11 (isto é, inicie no ponto extremo noroeste da tabela simplex de transporte). A partir daí, se xij for a última variável básica selecionada então selecione a seguir xi,j+1 (isto é movimente-se uma coluna para a direita) caso a origem i tiver qualquer oferta remanescente. Caso contrário, selecione xi+1,j em seguida (isto é movimente-se uma linha para baixo). Ponto extremo noroeste !!! Iniciamos daqui !!!! Destino Moinhos oferta u 1 2 3 4 O ri ge m Silo1 10 2 20 11 15 Silo2 12 7 9 20 25 Silo3 4 14 16 18 10 Demanda 5 15 15 15 Z = v Procedimento genérico para construir uma solução BV inicial. PASSO 2 : Faça com que esta alocação seja suficientemente grande para consumir com exatidão a oferta remanescente em sua linha ou a demanda remanescente em sua coluna (aquela que for menor). Passo 3: Elimine esta linha ou coluna (aquela que tiver menor oferta ou demanda remanescente) de considerações adicionais. Observe que para problemas de transporte com m origens e n destinos o número de variáveis básicas é = m + n – 1 ! SOLUÇÃO BV INICIAL Destino Moinhos oferta u 1 2 3 4 O ri ge m Silo1 10 2 20 11 15 5 10 Silo2 12 7 9 20 25 5 15 5 Silo3 4 14 16 18 10 10 Demanda 5 15 15 15 Z = 520 v Procedimento genérico para construir uma solução BV inicial. PASSO 4: Se apenas uma linha ou uma única coluna permanecer para consideração, então o procedimento é concluído selecionando-se toda variável remanescente (isto é, aquelas variáveis que não foram nem previamente selecionadas para ser básicas, nem eliminadas para consideração pela eliminação de suas linhas ou colunas) associada àquela linha ou coluna a ser básica com a única alocação viável. Caso contrário retorne a etapa 1. Completando a tabela inicial As variáveis básicas já foram determinadas!!! Ver slide 8 !!! Próximo passo: Completando a tabela inicial : estabelecendo os valores de u e v Variável Básica Equação ( u, v) Solução ui + vj = cij para cada (i,j) tal que xij seja básica X22 u2 + v2 = 7 Faça u2 = 0 v2 = 7 X23 u2 + v3 = 9 u2 = 0 v3 = 9 X24 u2 + v4 = 20 u2 = 0 v4 = 20 x12 u1 + v2 = 2 v2 = 7 u1 = -5 X11 u1 + v1 = 10 u1 = -5 v1 = 15 x34 u3 + v4 = 18 v4 = 20 u3 = -2 Destino Moinhos oferta u 1 2 3 4 O ri ge m Silo1 10 2 20 11 15 -5 5 10 Silo2 12 7 9 20 25 0 5 15 5 Silo3 4 14 16 18 10 -2 10 Demanda 5 15 15 15 Z = v 15 7 9 20 Completando a tabela inicial a partir de u e v Variável não Básica Equação ( u, v) Solução X cij - ui - vj ____________ X13 ____________ 16 X14 ____________ -4 X21 ____________ -3 X31 ____________ -9 X32 ____________ 9 x33 ____________ 9 Variável que entra na base!!! Destino Moinhos oferta u 1 2 3 4 O ri ge m Silo1 10 2 20 11 15 -5 5 10 16 -4 Silo2 12 7 9 20 25 0 -3 5 15 5 Silo3 4 14 16 18 10 -2 -9 9 9 10 Demanda 5 15 15 15 Z = 520 v 15 7 9 20 O Método Simplex para o problema de transporte. PASSO 1: Encontrar a variável básica que entra: selecione a variável não básica xij com maior valor negativo (em termos absolutos) de cij – ui – vj . PASSO 2: Estipular a variável básica que sai: identifique a reação em cadeia necessária para manter a viabilidade quando a variável básica que entra é aumentada. A partir das células doadoras, selecione a variável básica com menor valor. Passo 3: Estabelecer a nova solução BV: acrescente o valor da variável básica que sai para a alocação para cada célula receptora. Subtraia esse valor da alocação para cada célula doadora. Variável básica que entra: (passo 1) Variável que entra na base!!! Variável básica que sai: (passo 2) Variável que sai da base!!! Teste de otimalidade: Uma solução é ótima se e somente se cij – ui – vj ≥ 0 para todo ij tal que xij seja não básica. Recalcular ui e vj !!! Nova iteração (variável que entra) Nova iteração (variável que sai) Fim – Solução Ótima (cij – ui – vj ≥ 0 para todo ij tal que xij seja não básica) Recalcular ui e vj !!! Bibliografia Introdução à Pesquisa Operacional; 9ª Edição Autor: Frederick S. Hillier; Gerald J. Lieberman Editora: McGraw-Hill
Compartilhar