O Problema de Transportes
Optimização em Redes e Não Linear – p. 1/1
Problema de Transportes
O método simplex para o P.T.
1. Determinar uma sol. bás. admiss. inicial.
2. Testar a optimalidade da sol. actual.
Para isso calcular os custos reduzidos zij − cij para cada
var. não básica. Se todos zij − cij ≤ 0, então ST OP a sol.
é óptima, caso contrário continuar no Passo 3.
3. Seleccionar as variáveis de entrada e de saída da base.
4. Obter a nova sol. bás. admiss. e repetir o Passo 2.
Optimização em Redes e Não Linear – p. 2/1
Problema de Transportes
Passo 1. Obtenção de uma sol. bás. admiss. inicial
Como escolher o valor para exactamente m + n − 1 var. bás. ?
1. Método do canto superior esquerdo ou do canto noroeste (NW)
tornar bás. a var. x11 atribuindo-lhe o maior valor possível
x11 = min{a1 , b1 } esgotando ou a origem 1 ou o destino 1
no caso 1, a linha 1 deixa de ser considerada e tornamos
bás. a var. x21 atribuindo-lhe o maior valor possível
x21 = min{a2 , (b1 − x11 )} esgotando ou a origem 2 ou o
destino 1
Optimização em Redes e Não Linear – p. 3/1
Problema de Transportes
no caso 2, a coluna 1 deixa de ser considerada e tornamos
bás. a var. x12 atribuindo-lhe o maior valor possível
x12 = min{(a2 − x11 ), b2 } esgotando ou a origem 1 ou o
destino 2
em cd passo do mét. esgotamos ou uma origem ou um
destino e continuamos no caso 1 na mesma coluna e linha
seguinte, no caso 2 na mesma linha e coluna seguinte
no máx. obtemos n + m − 1 var. positivas que não formam
ciclo
Optimização em Redes e Não Linear – p. 4/1
Problema de Transportes
se esgotarmos simultaneamente uma origem e um destino,
podemos atribuir um zero à próxima var. da mesma linha ou
da mesma coluna e continuar como anteriormente
Desvantagem: não tem em conta a matriz dos custos.
Exemplo
5
3
2
100
4
2
1
50
80 30 40
Optimização em Redes e Não Linear – p. 5/1
Problema de Transportes
2. Método do mı́nimo da matriz de custos
em cd passo do mét. torna-se bás. a var. a que corresponde o menor
custo da matriz
considere o exemplo anterior
3. Método de Vögel
Em cada passo do mét. torna-se bás. a var. a que corresponde o menor
custo da linha ou coluna associada à maior das diferenças entre os dois
menores custos de cada linha e cada coluna.
Exemplo
8
3
5
9
200
1
7
4
6
700
3
8
2
4
100
250
350
200
200
Optimização em Redes e Não Linear – p. 6/1
Problema de Transportes
Passo 2. Testar a optimalidade da sol. bás. admiss. actual
cálculo dos custos reduzidos zij − cij para cd var. não
básica
se zij − cij ≤ 0 para todas as var., ST OP a sol. actual é
óptima, senão continuar no Passo 3.
há dois modos de cálculo dos custos reduzidos
(use o exemplo usado no mét. de Vögel, mas det. a sol. bás.
admiss. inicial através do mét. canto noroeste)
Optimização em Redes e Não Linear – p. 7/1
Problema de Transportes
1. Método de Stepping-Stone
baseia-se no mét. simplex
construção do ciclo associado a cd var. não bás.
cálculo dos custos reduzidos zij − cij para cd var. não
básica em que
zij − cij =
X
−(⊕/ ⊖ ck1 k2 ) − cij
xk1 k2 v.b.ciclo
Optimização em Redes e Não Linear – p. 8/1
Problema de Transportes
2. Método de Dantzig
baseia-se nos resultados da dualidade
construir um vector (u, v) que verifique as cond. de
complement. de slacks para isso
const. um sist. com m + n − 1 equações: se xij é
var. bás. então ui + vj = cij
como uma das m + n rest. do prob. primal é
redundante, este sistema é indeterminado, pelo
que se fixa o valor de uma das var. duais a zero
resolução do sist.
Optimização em Redes e Não Linear – p. 9/1
Problema de Transportes
cálculo dos custos reduzidos zij − cij para cd var. não
básica em que
zij − cij = ui + vj − cij
Optimização em Redes e Não Linear – p. 10/1
Problema de Transportes
Passo 3. Seleccionar as var. de entrada e saı́da na base
escolher a var. a entrar na base: determinar xkl tal que
zkl − ckl = max{zij − cij , zij − cij > 0}
construir o ciclo correspondente à var. de entrada na
base xkl
escolher a var. a sair da base: determinar
θ = min{xij , xij tem sinal ⊖ no ciclo de xkl }
Optimização em Redes e Não Linear – p. 11/1
Problema de Transportes
Passo 4. Obter a nova sol. bás. admissı́vel
alterar apenas o valor das var. no ciclo da var. xkl que
entra na base
xij =
(
xij + θ
xij − θ
se xij tem sinal ⊕ no ciclo
se xij tem sinal ⊖ no ciclo
novo valor da f.o. é
z = z − θ(zkl − ckl )
Optimização em Redes e Não Linear – p. 12/1