Download - Problema Do Transporte2
-
Copiado do site
http://www.mat.ua.pt/io/Documentos/Acetatos/CapituloII_7_2_files/frame.htm
Departamento Matemtica da Universidade de AveironProfa. Marli
-
II. Programao Linear (PL)
Captulo 7.2:
Resoluo do Problema de Transporte (PT).
Obteno de uma SBA inicial.
Mtodo do canto N-W;
Mtodo do mnimo da matriz de custos;
Mtodo de Vogel.
Obteno da soluo ptima.
Mtodo de Dantzig.
-
Problema de Transporte. Exemplo Prottipo
Uns dos principais produtos da firma Lactosal o leite.
Os pacotes de leites so empacotados
em 3 fbricas
e depois so distribudos de camio
para quatro armaznsConhecendo os custos de transporte, a procura prevista para cada armazm e as capacidades de produo de cada fbrica, pretende-se:
OPTIMIZAR O PROGRAMA DE DISTRIBUIO DIRIO DO LEITE. -
24 cargas dirias de leite devem ser produzidas e distribudas
Problema de Transporte. Exemplo Prottipo
Os dados dos custos de uma carga de leite para cada combinao fbrica-armazm e das ofertas(produo) e procuras, em cargas de camio/dia, so os seguintes:
Custo por carga de camioArmaznsFbricas1234Oferta1123462432483022110Procura4767 -
Para o exemplo prottipo a oferta total igual procura total
Quadro do Problema de Transporte
-
A SBA verifica o critrio de optimalidade?
Obteno de uma SBA inicial
FIM !!!
a soluo ptimaMover-se para uma SBA "melhor"
Sim
No
Algoritmo para a resoluo do PT.
-
Passo 1: Obteno de uma SBA Inicial
A varivel bsica escolhida , em cada quadro,a varivel situada no canto superior esquerdo (daqui o nome do canto do NW).
Mtodo do Canto Noroeste
A primeira varivel bsica escolhida ser sempre x11, depois consoante tenha sido traada a coluna 1 ou a linha 1,
ser escolhida como varivel bsica x12 ou x21 respectivamente, e assim sucessivamente at terem sido traadas todas as linhas e todas as colunas.Este mtodo de aplicao muito fcil, mas tem como grande inconveniente o facto de no considerar os custos na identificao da SBA inicial.
-
4
2
5
3
7
3
1. x11 =min (4,6 )= 4
2
2. x12 =min (7,2 )= 2
3. x22 =min (5,8 )= 5
5
4. x23=min (6,3 )= 3
3
3
7
5. x33=min (3,10 )= 3
6. x34=min (7,7 )= 7
SBA inicial: X0 = ( 4 , 2, 0, 0, 0, 5, 3, 0, 0, 0, 3, 7 ) ; z0 = 42
Exemplo Prottipo. Mtodo do Canto Noroeste
1
2
4
4
3
4
3
2
0
2
1
2
4 7 6 7
6
8
10
-
Passo 1: Obteno de uma SBA Inicial
A varivel bsica escolhida a varivel que corresponde ao menor custo(em caso de empate a escolha arbitrria).
Mtodo do Mnimo da Matriz dos Custos.
A primeira varivel bsica escolhida ser sempre a de menor custo, depois ser escolhida como varivel bsica a de menor custo no quadro resultante consoante o que foi traado, e assim sucessivamente, at terem sido traadas todas as linhas e todas as colunas.
Este mtodo, em princpio, fornece solues iniciais mais prximas da soluo ptima que o mtodo anterior, j que so considerados os custos na identificao da SBA inicial.
-
4
6
1
6
6
1
1: min (cij )= c31= 0
x31 =min (4,10)= 41
2: min (cij) =c34= 1 x34 = min ( 7, 6 )= 6
3: min (ci) = c12=c23= 2
x12 = min ( 7, 6 ) = 61
4: min (cij) =c23= 2
x23= min ( 6, 8 ) = 62
1
6
5: min (cij)= c22= 3 x22= min ( 2, 1 ) = 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
Exemplo Prottipo.Mtodo do Mnimo dos Custos
1
2
4
4
3
4
3
2
0
2
1
2
4 7 6 7
6
8
10
-
Passo 1: Obteno de uma SBA Inicial.
A varivel bsica escolhida , em cada quadro,a varivel que corresponde ao menor custo da linha ou coluna associada maior das diferenas entre os dois menores custos de cada linha e cada coluna(em caso de empate a escolha arbitrria).
Mtodo de Vogel
Este mtodo identifica uma SBA inicial, em geral, melhor do que as obtidas pelos mtodos anteriores. -
3
7
1: acrescentar uma linha e uma coluna, com as diferenas entre os dois menores custos, em coluna e em linha respectivamente.
2: Seleccionar a maior das diferenas: max (diferenas) = 3 , coluna 4.
3: Seleccionar o menor dos custos para esta coluna:
min (cij: j=4)= c34= 1
x34= min ( 7, 10 ) = 7Iterao 1: x34= 7
4 7 6 7
mximo
mnimo
Exemplo Prottipo.Mtodo de Vogel.
Quadro 11
0
0
3
1
2
4
4
3
4
3
0
2
1
2
2
1
1
1
10
8
6
-
2
4 7 6
7
1
3
1: calcular as novas diferenas relativas apenas aos elementos no traados
2: Seleccionar a maior das diferenas:
max (diferenas) = 2 e corresponde linha 3.3: Seleccionar o menor dos custos para esta linha:
min (cij: i=3)= c31= 0
x31= min ( 4, 3 ) = 3Iterao 2: x31= 3
mximo
mnimo
2
4 7 6
7
1
3
1: calcular as novas diferenas relativas apenas aos elementos no traados
2: Seleccionar a maior das diferenas:
max (diferenas) = 2 e corresponde linha 3.3: Seleccionar o menor dos custos para esta linha:
min (cij: i=3)= c31= 0
x31= min ( 4, 3 ) = 3Iterao 2: x31= 3
mximo
mnimo
Exemplo Prottipo. Mtodo de Vogel.
Quadro 21
2
3
4
4
3
4
3
8
6
0
2
1
2
1
0
0
1
1
2
1
2
3
4
4
3
4
3
8
6
0
2
1
2
1
0
0
1
1
2
-
7
1
1
1: calcular as novas
diferenas relativas
apenas aos elementos
no traados2: Seleccionar a maior
das diferenas :
max (diferenas) = 3
e corresponde coluna 1.3: Seleccionar o menor
dos custos para esta
coluna:
min (cij: j=1) = c11= 1
x11= min ( 1, 6 ) = 1Iterao 3: x11= 1
mnimo
5
mximo
Exemplo Prottipo. Mtodo de Vogel.
Quadro 34
3
4
8
6
0
2
1
2
1
2
3
2
4 7 6
3
4
3
1
1
1
1
-
As restantes quadrculas podem ser preenchidas imediatamente:
x22= 2
x23= 68
2 6
7
3
1
5
2
6
SBA inicial: X0 = ( 1 , 5, 0, 0, 0, 2, 6, 0, 3,0, 0,7) ; z = 36
Exemplo Prottipo. Mtodo de Vogel
Quadro 53
4
3
4
2
0
2
1
2
4
2
1
-
z0 = 36
X0 = ( 1 , 5, 0, 0,
0, 2, 6, 0,
3, 0, 0, 7)X0 = ( 4 , 2, 0, 0,
0, 5, 3, 0,
0, 0, 3, 7)X0 = ( 0 , 5, 1, 0,
0, 2, 6, 0,
4, 0, 0, 6)z0 = 42
z0 = 38
mais fcil
menos fcil
"pior" SBA
"melhor" SBA
Passo 1: Obteno de uma SBA Inicial.
Exemplo ProttipoMtodo
SBA inicial
f.o.
Canto do NW
Mnimo de custos
Voguel -
A soluo dual admissvel:
ui + vj- cij 0 ,
( i , j ) IB ?Passar ao passo seguinte
FIM
a soluo ptima !!!Sim
No
Determinar a soluo dual complementar
ui , vj , ( i=1,2,m , j=1,2,n ),
por resoluo do Sistema de Dantzig:
ui + vj = cij ( i , j ) IBPasso 2: Obteno da soluo ptima
Mtodo de Dantzing. Critrio de optimalidade -
Obteno da soluo ptima.Mtodo de Dantzing.
Passo 1: Critrio de optimalidade.O primeiro passo, que consiste em testar a optimalidade da SBA actual pode ser executado recorrendo Dualidade.
Para o efeito necessrio determinar a correspondente soluo dual.Enquanto na apresentao tabular do mtodo simplex esta soluo pode ser lida directamente no quadro respectivo, com a apresentao tabular do problema de transporte isso no acontece.
Contudo, atendendo simplicidade da estrutura do problema dual de transporte,
fcil determinar a soluo dual. -
u1 livre
u2 livre
u3 livre
v1 livre
v2 livre
v3 livrev4 livre
= 6
= 8 = 10= 4
= 7
= 6
= 71 2 3 4 4 3 2 4 0 2 2 1
x110 x120 x130 x140 x210 x220 x230 x240 x310 x320 x330 x340
Min z
Problema dual
Problema primal
Diagrama de Tucker
Max w
Formulao do Problema Dual de Transporte.
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1
1 1 1
1 1 1
1 1 1 -
Maximizar w = 6 u1 + 8 u2 + 10 u3 +
4 v1 + 7 v2 + 6 v3 + 7 v4
sujeito a:
u1 + v1 1
u1 + v2 2
u1 + v3 3u1 + v4 4
u2 + v1 4
u2 + v2 3
u2 + v3 2
u2 + v4 4
u3 + v1 0
u3 + v2 2
u3 + v3 2
u3 + v4 1
ui , v j livres ( i=1,2,3; j=1,2,3,4 )Formulao do Problema Dual de Transporte.
-
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
Para a SBA inicial obtida pelo Mtodo 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 varivel bsica do problema primal se encontra associada uma restrio saturada no problema dual .
Sistema de Dantzig para a SBA actual
Exemplo Prottipo. Sistema de Dantzing
-
Dado que uma das (m+n) restries do problema primal redundante, este sistema de equaes indeterminado de grau 1, pelo que a sua resoluo efectuada atribuindo um valor arbitrrio a qualquer das variveis duais e calculando a partir desta as restantes
( habitual fazer u1 =0 )v1 =1
v2 =2
u2 =1
v3 =1
u3 =1
v4 =0
u1 =0
1. Determinar a soluo dual.
Exemplo Prottipo. Obteno da soluo ptima.
Passo 1: Critrio de Optimalidadeu1 + v1 = 1
u1 + v2 = 2
u2 + v2 = 3
u2 + v3 = 2
u3 + v3 = 2
u3 + v4 = 1
-
Obteno da soluo ptima.
Esta soluo para as variveis duais pode ser obtida directamente no quadro de transporte correspondente SBA em presena.
Passo 1: Critrio de Optimalidade
Em sntese, fixando u1 =0, desloca-se em linha atravs das quadrculas correspondentes s variveis bsicas, para obter os vj. Uma vez obtidos estes, desloca-se em coluna atravs das quadrculas correspondentes s variveis bsicas para obter os ui .1. Determinar a soluo dual.
-
v1=1
v2=2
v3=1
v4=0
u3=1
u2=1
u1=0
( 1 ) u1+ v1=1
0 + v1=1( 2 ) u1+ v2=2
0 + v2=2( 4 ) u2+ v3=2
1 + v3=2( 6 ) u3+ v4=1
1 + v4=1( 3 ) u2+ v2=3
u2+ 2 =3( 5 ) u3+ v3=2
u3+ 1=21. Determinar a soluo dual.
Obteno da soluo ptima.
Passo 1: Critrio de Optimalidade1
2
4
4
3
4
3
2
0
2
1
2
6
8
104 7 6 7
24
4
2
5
3
7
3
-
Obteno da soluo ptima.
Como so satisfeitas as restries duais de igualdade do Sistema de Dantzig que correspondem s variveis primais bsicas, resta apenas verificar se as restantes restries duais de desigualdade correspondentes s variveis primais no bsicas do primal, so igualmente satisfeitas,
Passo 1: Critrio de Optimalidadeo que significa que a soluo dual admissvel e consequentemente
a soluo primal em presena ptima.
Isto equivalente a verificar que todos os custos reduzidos para as variveis no bsicas sejam no positivos.A verificao de que ui + vj cij , ( i , j ) IB , equivalente a (ui + vj ) - cij 0 ,
sendo o primeiro membro desta expresso de obteno imediata no quadro de transporte. -
Esta soluo no ptima, pois existem valores positivos para
ui + vj- cij nas quadrculas (3,1) e (3,2), o que significa que as correspondentes restries duais no esto satisfeitas.3. Existe algum ui + vj- cij > 0 , ( i , j ) IB ?
Exemplo Prottipo. Obteno da soluo ptima.
Passo 1: Critrio de Optimalidade1
2
4
3
4
3
2
2
1
2
0
6
8
104 7 6 7
24
4
4
2
5
3
7
3
v1=1
v2=2
v3=1
v4=0
u3=1
u2=1
u1=0
-4
-2
-3
-2
2
1
-
max {ui + vj - cij : ui + vj - cij> 0 }
A varivel a entrar na base escolhida de acordo com o critrio:
Em caso de empate a escolha arbitrria.
mximo
A varivel a entrar x31
Exemplo Prottipo. Obteno da soluo ptima.
Passo 2: Critrio de Entrada1
2
4
3
4
3
2
2
1
2
0
6
8
104 7 6 7
24
4
4
2
5
3
7
3
v1=1
v2=2
v3=1
v4=0
u3=1
u2=1
u1=0
-4
-2
-3
-2
2
1
-
Obteno da soluo ptima.
1. Seleccionar o percurso relativo varivel que entra atribuindo s quadrculas nele includas sinais de - ou + .
Passo 3: Critrio de Sada
Ao incrementar a varivel bsica que entra desde zero at um valor positivo 0, inicia-se um processo em cadeia" que garante que as restries de oferta e procura continuem satisfeitas. Este processo segue um percurso no quadro a partir da quadrcula da varivel que entra, onde so identificadas quais so as quadrculas 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 varivel que sai de acordo com o critrio:
min {xij percurso relativo varivel que entra : xij tem sinal -} = 0Em caso de empate a escolha arbitrria.
-
1. Seleccionar o percurso relativo varivel x31 atribuindo s quadrculas nele includas sinais de
- ou + .2. Seleccionar a varivel
que sai:
0 = min ( 4, 5, 3 ) = 3
a varivel x33 sai-
+
-
+
-
Determinar a varivel que sai.
mnimo
Exemplo Prottipo. Obteno da soluo ptima.
Passo 3: Critrio de Sadax31
-
Obteno da soluo ptima.
Passo 4: Obteno de uma nova SBAA nova SBA obtm-se adicionando e subtraindo s variveis que formam o ciclo o valor de 0, consoante estejam afectadas com ou , respectivamente;
as restantes variveis mantm os seus valores inalterados.-
+
-
1
5
2
0
7
6
x13= 3
3
x11=4 -3 = 1
x12=2 + 3 = 5
x22=5 -3 = 2
x23=3 +3 = 6
x23=3 -3 = 0
X1 = ( 1 , 5, 0, 0, z1 = 36
0, 2, 6, 0,
3, 0, 0, 7 )Exemplo Prottipo.Obteno da soluo ptima.
Passo 4: Obteno de uma nova SBA1
2
4
4
3
4
3
2
0
2
1
2
x31
4
2
5
3
7
3
-
+
-
+
-
1
2
4
4
3
4
3
2
0
2
1
2
-
v1=1
v2=2
v3=1
v4=2
u3=-1
u2=1
u1=0
( 1 ) u1+ v1=1
0 + v1=1( 2 ) u1+ v2=2
0 + v2=2( 4 ) u2+ v3=2
1 + v3=2( 6 ) u3+ v4=1
-1 + v4=1( 3 ) u2+ v2=3
u2+ 2 =3( 5 ) u3+ v1=0
u3+ 1=03
1. Determinar a soluo dual.
Exemplo Prottipo. Obteno da soluo ptima.
Iterao 2, Passo 1: Critrio de Optimalidade.1
2
4
4
3
4
3
2
0
2
1
2
6
8
104 7 6 7
24
1
5
2
6
7
-
( 6 ) u3+ v3 -2
=-1+ 1 -2= -2( 3 ) u2+ v1 -4
= 1+ 1 -4=-2( 5 ) u3+ v2-2
=-1+ 2 -2= -1( 1 ) u1+ v3 -3
= 0+ 1 -3=-2( 2 ) u1+ v4 -4
= 0+2 -4=-2(4 ) u2+ v4 -4
= 1+ 2 -4=-13
2. Calcular os custos reduzidos para as variveis no bsicas.
Exemplo Prottipo. Obteno da soluo ptima.
Iterao 2, Passo 1: Critrio de Optimalidade1
2
4
3
4
3
2
2
1
2
0
6
8
104 7 6 7
4
1
5
2
6
7
v1=1
v2=2
v3=1
v4=2
u3=-1
u2=1
u1=0
-2
-2
-1
-2
-1
- 2
-
Esta soluo ptima, pois para todas as variveis no bsicas
ui + vj - cij 0Soluo ptima: X1 =(1 , 5, 0, 0, 0, 2, 6, 0, 3, 0, 0, 7); z1 = 36
3. Existe algum ui + vj- cij > 0 , ( i , j ) IB ?
Exemplo Prottipo. Obteno da soluo ptima.
Iterao 2, Passo 1: Critrio de Optimalidade1
2
4
3
4
3
2
2
1
2
0
6
8
104 7 6 7
4
1
5
2
6
7
v1=1
v2=2
v3=1
v4=2
u3=-1
u2=1
u1=0
-2
-2
-1
-2
-1
- 2
3
Destino
Origem
1 2 3 4
1 2 3 4
Oferta
1
1
2
2
3
3
6
6
8
8
10
10
Procura
4
4
7
7
6
6
7
7
24
24
=
=
24
24
1
1
2
2
4
4
4
4
3
3
4
4
x
x
11
11
x
x
12
12
x
x
14
14
x
x
21
21
x
x
22
22
x
x
24
24
3
3
x
x
13
13
2
2
x
x
23
23
0
0
2
2
1
1
x
x
31
31
x
x
32
32
x
x
34
34
2
2
x
x
33
33
Destino
Origem
Destino
Origem
1 2 3 4
1 2 3 4
Oferta
1
1
2
2
3
3
6
6
8
8
10
10
Procura
4
4
7
7
6
6
7
7
24
24
=
=
24
24
1
1
1
1
2
2
2
2
4
4
4
4
4
4
4
4
3
3
3
3
4
4
4
4
x
x
11
11
x
x
12
12
x
x
14
14
x
x
21
21
x
x
22
22
x
x
24
24
3
3
3
3
x
x
13
13
2
2
2
2
x
x
23
23
0
0
0
0
2
2
2
2
1
1
1
1
x
x
31
31
x
x
32
32
x
x
34
34
2
2
2
2
x
x
33
33
Custo por carga de
camio
Armazns
10
1
2
2
0
3
7
4
4
4
4
4
1
1
7
3
2
2
6
2
3
3
Procura
8
2
6
1
Oferta
Fbricas
Custo por carga de
camio
Armazns
10
1
2
2
0
3
7
4
4
4
4
4
1
1
7
3
2
2
6
2
3
3
Procura
8
2
6
1
Oferta
Fbricas
6
6
8
8
10
10
4
4
7
7
6
6
7
7
24
24
1
1
2
2
4
4
4
4
3
3
4
4
4
4
2
2
5
5
3
3
2
2
3
3
2
2
1
1
7
7
2
2
3
3
0
0
-4
-2
-3