Aula 7 - Algoritmo para solução de problemas

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