Copiado do site
http://www.mat.ua.pt/io/Documentos/Acetatos/CapituloII_7_2_files/frame.htm
Departamento Matemática da Universidade de Aveiron
Profa. Marli
II. Programação Linear (PL)
• Capítulo 7.2:
Resolução do Problema de Transporte (PT).


Obtenção de uma SBA inicial.
 Método do canto N-W;
 Método do mínimo da matriz de custos;
 Método de Vogel.
Obtenção da solução óptima.
 Método de Dantzig.
   
Problema de Transporte. Exemplo Protótipo
•Uns dos principais produtos da firma Lactosal é o leite.
Os pacotes de leites são empacotados
em 3 fábricas
e depois são distribuídos de camião
para quatro armazéns
Conhecendo os custos de transporte, a procura prevista
para cada armazém e as capacidades de produção de
cada fábrica, pretende-se:
OPTIMIZAR O PROGRAMA DE DISTRIBUIÇÃO DIÁRIO
DO LEITE.
   
Problema de Transporte. Exemplo Protótipo
Os dados dos custos de uma carga de leite para cada combinação fábricaarmazém e das ofertas(produção) e procuras, em cargas de camião/dia, são
os seguintes:
24 cargas diárias
de leite devem ser
produzidas e
distribuídas
Custo por carga de
camião
Armazéns
Fábricas
1
2
3
4
Oferta
1
1
2
3
4
6
2
4
3
2
4
8
3
0
2
2
1
10
Procura
4
7
6
7
   
Quadro do Problema de Transporte
Custo por carga de
camião
Armazéns
Fábricas
1
2
3
4
Oferta
1
1
2
3
4
6
2
4
3
2
4
8
3
0
2
2
1
10
Procura
4
7
6
7
Destino
Origem
1
2
1
1
2
3
Procura
x11
3
x21
x22
4
x32
7
1
2
x33
6
8
x24
x23
6
4
2
2
0
4
x14
x13
x12
Oferta
4
3
2
4
x31
3
x34
7
Para o exemplo protótipo a oferta total é igual
à procura total
10
24 =24
   
Algoritmo para a resolução do PT.
Obtenção de uma SBA
inicial
A SBA verifica
o critério de
optimalidade?
Não
Sim
FIM !!!
a solução é
óptima
Mover-se para uma SBA
"melhor"
   
Passo 1: Obtenção de uma SBA Inicial
Método do Canto Noroeste
•A variável básica escolhida é, em cada quadro,a variável
situada no canto superior esquerdo (daqui o nome do canto do
NW).
A primeira variável básica escolhida será sempre x11, depois
consoante tenha sido traçada a coluna 1 ou a linha 1,
será escolhida como variável básica x12 ou x21 respectivamente, e
assim sucessivamente até terem sido traçadas todas as linhas e todas
as colunas.
Este método é de aplicação muito fácil, mas tem como grande inconveniente o facto de
não considerar os custos na identificação da SBA inicial.
   
Exemplo Protótipo. Método do Canto Noroeste
1º. x11 =min (4,6 )= 4
2º. x12 =min (7,2 )= 2
1
3
4
3
2
4
2
1
2
4
4
3º. x22 =min (5,8 )= 5
5
3
2
0
4º. x23=min (6,3 )= 3
7
3
5º. x33=min (3,10 )= 3
6º. x34=min (7,7 )= 7
2
4
7
5
6
3
6
2
8
3
10
7
7
SBA inicial: X0 = ( 4 , 2, 0, 0, 0, 5, 3, 0, 0, 0, 3, 7 ) ; z0 = 42
   
Passo 1: Obtenção de uma SBA Inicial
Método do Mínimo da Matriz dos Custos.
•A variável básica escolhida é a variável que corresponde ao
menor custo(em caso de empate a escolha é arbitrária).
A primeira variável básica escolhida será sempre a de menor
custo, depois será escolhida como variável básica a de menor
custo no quadro resultante consoante o que foi traçado, e
assim sucessivamente, até terem sido traçadas todas as linhas
e todas as colunas.
Este método, em princípio, fornece soluções iniciais mais próximas da solução óptima
que o método anterior, já que são considerados os custos na identificação da SBA
inicial.
   
Exemplo Protótipo.Método do Mínimo dos Custos
1º: min (cij )= c31= 0
 x31 =min (4,10)= 4
1
2º: min (cij) =c34= 1 
x34 = min ( 7, 6 )= 6
4
5º: min (cij)= c22= 3 
x22= min ( 2, 1 ) = 1
3
4
3
2
4
8 2 1
1
10
1
3º: min (ci) = c12=c23= 2
 x12 = min ( 7, 6 ) = 6
4º: min (cij) =c23= 2
 x23= min ( 6, 8 ) = 6
6
2
1
6
2
0
2
6
4
4
7
1
6
6
6
7
1
6º: min (cij) =c24= 4 
x24=min (1, 1 ) =1
SBA inicial:
X0 = ( 0 , 6, 0, 0, 0, 1, 6, 1, 4,0, 0,6) ; z = 38
   
Passo 1: Obtenção de uma SBA Inicial.
Método de Vogel
•A variável básica escolhida é, em cada quadro,a variável que
corresponde ao menor custo da linha ou coluna associada à
maior das diferenças entre os dois menores custos de cada
linha e cada coluna(em caso de empate a escolha é arbitrária).
Este método identifica uma SBA inicial, em geral, melhor do que as obtidas pelos
métodos anteriores.
   
Exemplo Protótipo.Método de Vogel.
Quadro 1
1º: acrescentar uma linha e
uma coluna, com as
diferenças entre os dois
menores custos, em coluna e
em linha respectivamente.
1
2
3
4
1
6
4
3
2
4
1
8
2º: Seleccionar a maior das
diferenças: max (diferenças)
= 3 , coluna 4.
0
2
2
1
1
3º: Seleccionar o menor dos
custos para esta coluna:
min (cij: j=4)= c34= 1
 x34= min ( 7, 10 ) = 7
1
7
4
0
7
Iteração 1:
3
0
6
7
10 3
mínimo
máximo
x34= 7
   
Exemplo Protótipo. Método de Vogel.
Quadro 2
1º: calcular as novas
diferenças relativas apenas
aos elementos não traçados
2º: Seleccionar a maior das
diferenças:
max (diferenças) = 2 e
corresponde à linha 3.
3º: Seleccionar o menor dos
custos para esta linha:
min (cij: i=3)= c31= 0
 x31= min ( 4, 3 ) = 3
1
2
3
4
4
3
2
4
0
2
2
1
3
7
0
1
4
1
7
6
1
8
2
3
0
6
mínimo
Iteração 2:
1
máximo
x31= 3
   
Exemplo Protótipo. Método de Vogel.
Quadro 3
1º: calcular as novas
diferenças relativas
apenas aos elementos
não traçados
2º: Seleccionar a maior
das diferenças :
max (diferenças) = 3
e corresponde à coluna 1.
3º: Seleccionar o menor
dos custos para esta
coluna:
min (cij: j=1) = c11= 1
 x11= min ( 1, 6 ) = 1
mínimo
1
2
3
4
4
3
2
4
0
2
2
1
1
3
1
6
1
8
5
7
1
3
4
1
7
1
6
máximo
Iteração 3:
x11= 1
   
Exemplo Protótipo. Método de Vogel
Quadro 5
As restantes
quadrículas podem ser
preenchidas
imediatamente:
x22= 2
x23= 6
1
1
2
3
4
3
2
4
2
1
5
4
2
6
2
0
3
7
2
SBA inicial:
8
6
X0 = ( 1 , 5, 0, 0, 0, 2, 6, 0, 3,0, 0,7) ; z = 36
   
Passo 1: Obtenção de uma SBA Inicial.
Exemplo Protótipo
mais fácil
Método
SBA inicial
"pior" SBA
z0 = 42
Canto do NW
menos fácil
f.o.
Mínimo de custos
X0 = ( 4 , 2, 0, 0,
0, 5, 3, 0,
0, 0, 3, 7)
Voguel
X0 = ( 0 , 5, 1, 0,
0, 2, 6, 0,
4, 0, 0, 6)
X0 = ( 1 , 5, 0, 0,
0, 2, 6, 0,
3, 0, 0, 7)
z0 = 38
z0 = 36
"melhor"
SBA
   
Passo 2: Obtenção da solução óptima
Método de Dantzing. Critério de optimalidade
Determinar a solução dual complementar
ui , vj , ( i=1,2…,m , j=1,2…,n ),
por resolução do Sistema de Dantzig:
ui + vj = cij ( i , j )  IB
A solução dual é
admissível:
ui + vj- cij 0 ,
( i , j )  IB ?
Sim
FIM
a solução é
óptima !!!
Não
Passar ao passo seguinte
   
Obtenção da solução óptima.Método de Dantzing.
Passo 1: Critério de optimalidade.

O primeiro passo, que consiste em testar a optimalidade da
SBA actual pode ser executado recorrendo à Dualidade.
Para o efeito é necessário determinar a correspondente solução
dual.

Enquanto na apresentação tabular do método simplex esta
solução pode ser lida directamente no quadro respectivo, com
a apresentação tabular do problema de transporte isso não
acontece.
Contudo, atendendo à simplicidade da estrutura do problema
dual de transporte,
é fácil determinar a solução dual.
   
Formulação do Problema Dual de Transporte.
Custo por carga de
camião
Armazéns
Fábricas
1
2
3
4
Oferta
1
1
2
3
4
6
2
4
3
2
4
8
3
0
2
2
1
10
Procura
4
7
6
7
u1 livre
u2 livre
u3 livre
v1 livre
v2 livre
v3 livre
v4 livre
Min z
Diagrama de Tucker
Problema primal
x110 x120 x130 x140 x210 x220 x230 x240 x310 x320 x330 x340
1
1
1
1
1
1
1
1
1
1
1
1
3
1
4
1
1
1
4
3
1
1
1
2
1
1
1
1
1
2
4
1
0
2
2
Max w
=
=
=
=
=
=
=
6
8
10
4
7
6
7
1
Problema dual
   
Formulação do Problema Dual de Transporte.
Custo por carga de
camião
Armazéns
Fábricas
1
2
3
4
Oferta
1
1
2
3
4
6
2
4
3
2
4
8
3
0
2
2
1
10
Procura
4
7
6
7
Maximizar w = 6 u1 + 8 u2 + 10 u3 +
4 v1 + 7 v2 + 6 v3 + 7 v4
sujeito a:
u1
u1
u1
u1
+ v1
u2
u2
u2
u2
+ v2
+ v3
+ v4
+ v1
+ v2
+ v3
+ v4
u3 + v1
u3
+ v2
u3
+ v3
u3
+ v4












1
2
3
4
4
3
2
4
0
2
2
1
ui , v j livres ( i=1,2,3; j=1,2,3,4 )
   
Exemplo Protótipo. Sistema de Dantzing
Para a SBA inicial obtida pelo Método do Canto N-W
X0 = ( 4 , 2, 0, 0, 0, 5, 3, 0, 0, 0, 3, 7 ) tem-se:
De acordo com a
propriedade dos desvios
complementares, a cada
variável básica do problema
primal se encontra associada
uma restrição saturada no
problema dual .
Sistema de Dantzig
para a SBA actual
x11= 4
u1 + v1
= 1
x12 = 2
u1 + v2
= 2
x22 = 5
u2 + v2
= 3
x23 = 3
u2 + v3
= 2
x33 = 3
u3 + v3 = 2
x34 = 7
u3 + v4
= 1
   
Exemplo Protótipo. Obtenção da solução óptima.
Passo 1: Critério de Optimalidade
1º. Determinar a solução dual.
Dado que uma das (m+n)
restrições do problema primal é
redundante, este sistema de
equações é indeterminado de
grau 1, pelo que a sua resolução
é efectuada atribuindo um valor
arbitrário a qualquer das
variáveis duais e calculando a
partir desta as restantes
( é habitual fazer u1 =0 )
u1 =0
u1 + v1
= 1
v1 =1
u1 + v2
= 2
v2 =2
u 2 + v2
= 3
u2 =1
u2 + v3
= 2
v3 =1
u3 + v3
= 2
u3 =1
u3 + v4
= 1
v4 =0
   
Obtenção da solução óptima.
Passo 1: Critério de Optimalidade
1º. Determinar a solução dual.
•Esta solução para as variáveis duais pode ser obtida
directamente no quadro de transporte correspondente à SBA
em presença.
Em síntese, fixando u1 =0, desloca-se em linha através das
quadrículas correspondentes às variáveis básicas, para obter
os vj. Uma vez obtidos estes, desloca-se em coluna através
das quadrículas correspondentes às variáveis básicas
para obter os ui .
   
Obtenção da solução óptima.
Passo 1: Critério de Optimalidade
1º. Determinar a solução dual.
(2)
(4)
u1+ v2=2
 0 + v2=2
(6)
u2+ v3=2
 1 + v3=2
u3+ v4=1
 1 + v4=1
(1)
u1+ v1=1
 0 + v1=1
(3)
u2+ v2=3
 u2+ 2 =3
(5)
u3+ v3=2
 u3+ 1=2
v1=1
u1=0
v2=2
1
4
v3=1
v4=0
2
3
3
2
4
2
1
4
2
4
u2=1
5
2
0
u3=1
3
7
3
4
7
6
7
6
8
10
24
   
Obtenção da solução óptima.
Passo 1: Critério de Optimalidade
•Como são satisfeitas as restrições duais de igualdade do
Sistema de Dantzig que correspondem às variáveis primais
básicas, resta apenas verificar se as restantes restrições duais
de desigualdade correspondentes às variáveis primais não
básicas do primal, são igualmente satisfeitas,
o que significa que a solução dual é admissível e
consequentemente
a solução primal em presença é óptima.
Isto é equivalente a verificar que todos os custos reduzidos
para as variáveis não básicas sejam não positivos.
A verificação de que ui + vj  cij , ( i , j )  IB , é equivalente a (ui + vj ) - cij  0 ,
sendo o primeiro membro desta expressão de obtenção imediata no quadro de
transporte.
   
Exemplo Protótipo. Obtenção da solução óptima.
Passo 1: Critério de Optimalidade
3º. Existe algum ui + vj- cij > 0 , ( i , j )  IB ?
v1=1
u1=0
Esta solução não é
óptima, pois existem
valores positivos para
ui + vj- cij nas
quadrículas (3,1) e
(3,2), o que significa
que as correspondentes
restrições duais não
estão satisfeitas.
u2=1
u3=1
1
4
v2=2
2
5
0
4
3
4
-3
2
1
7
3
7
4
2
2
1
v4=0
-4
3
4
2
3
-2
2
-2
v3=1
6
7
6
8
10
24
   
Exemplo Protótipo. Obtenção da solução óptima.
Passo 2: Critério de Entrada
A variável a entrar na base é escolhida de acordo com o critério:
max {ui + vj - cij : ui + vj - cij> 0 }
Em caso de empate
a escolha é
arbitrária.
v1=1
u1=0
u2=1
máximo
u3=1
A variável a entrar
é
1
4
v2=2
2
5
0
4
3
8
2
1
7
6
6
4
-3
3
7
4
2
2
1
v4=0
-4
3
4
2
3
-2
2
-2
v3=1
7
10
24
x31
   
Obtenção da solução óptima.
Passo 3: Critério de Saída
• 1º. Seleccionar o percurso relativo à variável que entra atribuindo
às quadrículas nele incluídas sinais de - ou + .
Ao incrementar a variável básica que entra desde zero até um valor positivo 0,
inicia-se um “processo em cadeia" que garante que as restrições de oferta e
procura continuem satisfeitas. Este processo segue um percurso no quadro a partir
da quadrícula da variável que entra, onde são identificadas quais são as
quadrículas onde será preciso subtrair o valor 0, (com sinal -) e aquelas onde será
preciso adiciona-lo (com sinal +).
Tudo com o objectivo de as somas em cada linha e coluna permanecerem
inalteradas.
2º. Seleccionar a variável que sai de acordo com o critério:
min {xij  percurso relativo à variável que entra : xij tem sinal -} = 0
Em caso de empate a escolha é arbitrária.
   
Exemplo Protótipo. Obtenção da solução óptima.
Passo 3: Critério de Saída
Determinar a variável que sai.
1º. Seleccionar o percurso
relativo à variável x31
atribuindo às quadrículas
nele incluídas sinais de
- ou + .
2º. Seleccionar a variável
que sai:
0 = min ( 4, 5, 3 ) = 3
 a variável x33 sai
-
+
x31
+
-
mínimo
   
Obtenção da solução óptima.
Passo 4: Obtenção de uma nova SBA
A nova SBA obtém-se adicionando e subtraindo às variáveis
que formam o ciclo o valor de 0, consoante estejam
afectadas com
-
ou
+ , respectivamente;
as restantes variáveis mantêm os seus valores inalterados.
   
Exemplo Protótipo.Obtenção da solução óptima.
Passo 4: Obtenção de uma nova SBA
1
- 4
3
4
3
2
4
2
1
2 +
4
X1 = ( 1 , 5, 0, 0, z1 = 36
0, 2, 6, 0,
3, 0, 0, 7 )
2
- 5
3 +
2
0
x31
3 -
7
x12=2 + 3 = 5
x23=3 +3 = 6
x11=4 -3 = 1
x22=5 -3 = 2
1
1
3
4
3
2
4
2
1
5
4
x23=3 -3 = 0
x13= 3
2
6
2
0
3
2
0
7
   
Exemplo Protótipo. Obtenção da solução óptima.
Iteração 2, Passo 1: Critério de Optimalidade.
1º. Determinar a solução dual.
(2)
(4)
u1+ v2=2
 0 + v2=2
(6)
u2+ v3=2
 1 + v3=2
u3+ v4=1
 -1 + v4=1
(1)
u1+ v1=1
 0 + v1=1
(3)
u2+ v2=3
 u2+ 2 =3
(5)
u3+ v1=0
 u3+ 1=0
v1=1
u1=0
1
1
v3=1
v4=2
2
3
3
2
4
2
1
4
5
4
u2=1
u3=-1
v2=2
2
6
2
0
7
3
4
7
6
7
6
8
10
24
   
Exemplo Protótipo. Obtenção da solução óptima.
Iteração 2, Passo 1: Critério de Optimalidade
2º. Calcular os custos reduzidos para as variáveis não básicas.
(4 )
(2)
(1)
u1+ v3 -3
= 0+ 1 -3=-2
(3)
u2+ v1 -4
= 1+ 1 -4=-2
u1=0
u2=1
(5)
u3+ v2-2
=-1+ 2 -2= -1
(6)
u3+ v3 -2
=-1+ 1 -2= -2
u3=-1
u2+ v4 -4
= 1+ 2 -4=-1
u1+ v4 -4
= 0+2 -4=-2
v1=1
1
1
v2=2
2
2
0
4
6
4
-1
2
-2
7
4
2
2
-1
v4=2
-2
3
4
3
3
-2
5
-2
v3=1
6
1
7
6
8
10
7
   
Exemplo Protótipo. Obtenção da solução óptima.
Iteração 2, Passo 1: Critério de Optimalidade
3º. Existe algum ui + vj- cij > 0 , ( i , j )  IB ?
v1=1
u1=0
Esta solução é
óptima, pois para
todas as variáveis
não básicas
ui + vj - cij  0
u2=1
u3=-1
1
1
v2=2
2
2
0
4
6
4
-1
2
-2
7
4
2
2
-1
v4=2
-2
3
4
3
3
-2
5
-2
v3=1
6
1
7
6
8
10
7
Solução óptima: X1 =(1 , 5, 0, 0, 0, 2, 6, 0, 3, 0, 0, 7); z1 = 36
   