3. problema de transportes

7/25/2019 3. Problema de Transportes

1/24

14/06/20

PROBLEMA DE TRANSPORTE

Rmulo Alves Soares

([email protected])

Junho/2016

Universidade Federal do CearFaculdade de Economia, Administrao, Aturia e ContabilidadeCurso de Cincias Atuariais

Problema de transporte

O problema de transporte est relacionado com adeterminao de uma estratgia tima para a distribuio deum produto, saindo de seus centros de produo, com fbricas,para centros de recebimento, como armazns ou lojas.

Cada centro de produo, chamados de origens, capaz defornecer um nmero mximo de unidades do produto, ao que

denominamoscapacidadeoudisponibilidade.

Cada centro de recebimento, chamados dedestinos, tm umademanda mnima de unidades, a sua demanda ourequerimento.

Esse tipo de problema tambm pode ser utilizado para adeciso sobre a alocao de novas unidades de uma empresa.

2
mailto:[email protected]:[email protected]


2/24

14/06/20

Exemplo

Uma empresa que produz concreto possui trs fbricas (1, 2 e3), e atende a trs locais de construo (A, B e C)

As fbricas tm a capacidade de fornecer concreto, emtoneladas, dada pela tabela a seguir:

As demandas das construes, em toneladas, so de:

3

Fbrica Capacidade

1 300

2 300

3 100

Construo Demanda

A 200

B 200

C 300

Exemplo

O custo para transportar uma tonelada de concreto de cadauma das fbricas, para cada uma das construes demonstrado na figura a seguir:

4

1

2

3

A

B

C

43

8

75

9

4 5

5


3/24

14/06/20

Exemplo

Podemos agora representar toda a informao numa nicatabela:

5

ParaA B C Oferta

De

1 4 3 8 300

2 7 5 9 300

3 4 5 5 100

Demanda 200 200 300 700

Exemplo

Representao matemtica do problema:

Notao utilizada

xij= nmero de unidades transportada da origemipara o destinoj;

oi= oferta da origemi;

dj= demanda do destinoj;

cij= custo por unidade transportada da origemipara o destinoj.

6

Destinos

1 2 n Oferta

Origens

1 c11 c11 c1n o12 c21 c21 c2n o2 m cm1 cm2 cmn om

Demanda d1 d2 dn


4/24

14/06/20

Exemplo

Representao matemtica do problema: Seja Zo custo total de distribuio de todas as m origens para os n

destinos.

No exemplo,Zser o custo total das toneladas de concreto distribudas.

A funo objetivo do problema :

4+ 3+ 8+ 7+ 5+ 9+ 4+ 5+ 5 Nesse problema, o total da oferta e o total da demanda so iguais, ou

seja:

=

=

Isso implica que, ao distribuir toda a oferta, toda demanda seratendida, ento, as restries do problema sero equaes, ao invs deinequaes.7

Exemplo

Representao matemtica do problema:

O problema do transporte pode ser representado matematicamentecomo:

=

=

Com restries:

=

, 1,2 ,3, ,

=

, 1,2 ,3, ,

8


5/24

14/06/20

Soluo inicial de um problema detransporteMtodo do canto noroeste

Aps a representao do problema, o prximo passo para suasoluo consiste na determinao de uma soluo bsicainicial.

A soluo inicial em que todos os valores dexso nulos no vivel pra um problema de transporte.

Uma das formas de se determinar uma soluo inicial bsica

para o problema dos transportes chama-semtodo do cantonoroeste.

9

Soluo inicial de um problema detransporteMtodo do canto noroeste

Mtodo do canto noroeste:

1. Escolha a clula no canto ao extremo noroeste da tabela.

2. Aloque o mximo de produtos nesta clula, levando em considerao a

demanda da coluna e a oferta da linha.

3. Atenda toda a oferta da linha antes de mover para a prxima linha.

4. Quando toda a oferta for atendida, cheque se todos os requerimentos

esto corretos.

10


6/24

14/06/20

Exemplo

Uma fbrica de mveis produz mesas em trs locais: D, E e F. Asmesas so distribudas para armazns trs armazns diferentesA, B e C. A ofertas, demandas e os custos de transporte estorepresentados na tabela a seguir:

11

ParaA B C Oferta

De

D 5 4 3 100

E 8 4 3 300

F 9 7 5 300Demanda 300 200 200 700

Exemplo

Representao de uma tabela para o problema de transporte:

12

A B C Oferta

D 5 4 3

100

E 8 4 3 300

F 9 7 5

300

Demanda 300 200 200 700


7/24

14/06/20

Exemplo


13

A B C Oferta

D 5 4 3

100100

E 8 4 3

300

F 9 7 5

300

Demanda 300 200 200 700

Exemplo


14

A B C Oferta

D 5 4 3

100100

E 8 4 3 300200

F 9 7 5

300

Demanda 300 200 200 700


8/24

14/06/20

Exemplo


15

A B C Oferta

D 5 4 3

100100

E 8 4 3

300200 100

F 9 7 5

300

Demanda 300 200 200 700

Exemplo


16

A B C Oferta

D 5 4 3

100100

E 8 4 3 300200 100

F 9 7 5

300100

Demanda 300 200 200 700


9/24

14/06/20

Exemplo


17

A B C Oferta

D 5 4 3

100100

E 8 4 3

300200 100

F 9 7 5

300100 200

Demanda 300 200 200 700

Exemplo


18

A B C Oferta

D 5 4 3

100100

E 8 4 3 300200 100

F 9 7 5

300100 200

Demanda 300 200 200 700


10/24

14/06/20

Exemplo

A soluo inicial dada pelo mtodo do canto noroeste :

A soluo encontrada tima?19

Rota Unidades

transportadas

Custo por

unidade

Custo

TotalDe Para

D A 100 5 500

E A 200 8 1.600

E B 100 4 400

F B 100 7 700

F C 200 5 1.000Total 4.200

Critrio de otimalidade

Mtodo destepping-stone

Para determinar se uma soluo tima pelo mtodo destepping-stone preciso:

1. Selecionar uma clula vazia.

2. A partir dessa clula, trace um caminho fechado de volta at aclula inicial. S so permitidos movimentos horizontais ouverticais e s permitido mudar direo nas clulas preenchidas.

3. Adicione um sinal de (+) clula inicial e em seguida alterne entresinais de (-) e (+) sempre que houver mudana na direo.

4. Calcule um ndice de melhoria, Iij, adicionando os custos dasclulas que receberam um sinal de (+) ou (-), levando emconsiderao esse sinal.

5. Faa o procedimento para todas as clulas vazias.

Se todos os ndicesIijforem maiores que ou iguais a zero, a soluo tima;

Caso contrrio, a soluo poder ser melhorada.

20


11/24

14/06/20

Exemplo

Escolhendo a clulaCDB

(Rota de D para B)

21

A B C Oferta

D 5 Incio 4 3

100100 +

E 8 4 3

300200 100

F 9 7 5

300100 200

Demanda 300 200 200 700

Exemplo Escolhendo a clulaCDB(Rota de D para B)

22

A B C Oferta

D 5 Incio 4 3

100100 +

E 8 4 3

300200 100

F 9 7 5

300100 200

Demanda 300 200 200 700


12/24

14/06/20

Exemplo


(Rota de D para B)

23

A B C Oferta

D 5 Incio 4 3

100100 - +

E 8 4 3

300200 100

F 9 7 5

300100 200

Demanda 300 200 200 700

Exemplo Escolhendo a clulaCDB(Rota de D para B)

24

A B C Oferta

D 5 Incio 4 3

100100 - +

E 8 4 3

300200 + 100

F 9 7 5

300100 200

Demanda 300 200 200 700


13/24

14/06/20

Exemplo


(Rota de D para B)

25

A B C Oferta

D 5 Incio 4 3

100100 - +

E 8 4 3

300200 + 100 -

F 9 7 5

300100 200

Demanda 300 200 200 700

4 5 + 8 4 +3

Exemplo Escolhendo a clulaCDC(Rota de D para C)

26

A B C Oferta

D 5 4 Incio 3

100100 +

E 8 4 3

300200 100

F 9 7 5

300100 200

Demanda 300 200 200 700


14/24

14/06/20

Exemplo

Escolhendo a clulaCDC

(Rota de D para C)

27

A B C Oferta

D 5 4 Incio 3

100100 +

E 8 4 3

300200 100

F 9 7 5

300100 200

Demanda 300 200 200 700


28

A B C Oferta

D 5 4 Incio 3

100100 - +

E 8 4 3

300200 100

F 9 7 5

300100 200

Demanda 300 200 200 700


15/24

14/06/20

Exemplo


(Rota de D para C)

29

A B C Oferta

D 5 4 Incio 3

100100 - +

E 8 4 3

300200 + 100

F 9 7 5

300100 200

Demanda 300 200 200 700


30

A B C Oferta

D 5 4 Incio 3

100100 - +

E 8 4 3

300200 + 100 -

F 9 7 5

300100 200

Demanda 300 200 200 700


16/24

14/06/20

Exemplo


(Rota de D para C)

31

A B C Oferta

D 5 4 Incio 3

100100 - +

E 8 4 3

300200 + 100 -

F 9 7 5

300100 + 200

Demanda 300 200 200 700


32

A B C Oferta

D 5 4 Incio 3

100100 - +

E 8 4 3

300200 + 100 -

F 9 7 5

300100 + 200 -

Demanda 300 200 200 700

3 5 + 8 4 + 7 5 +4


17/24

14/06/20

Exemplo

Escolhendo a clulaCEC

(Rota de E para C)

33

A B C Oferta

D 5 4 3

100100

E 8 4 Incio 3

300200 100 - +

F 9 7 5

300100 + 200 -

Demanda 300 200 200 700

3 4 + 7 5 +1

Exemplo Escolhendo a clulaCFA(Rota de F para A)

34

A B C Oferta

D 5 4 3

100100

E 8 4 3

300200 - 100 +

F Incio 9 7 5

300+ 100 - 200

Demanda 300 200 200 700

9 7 + 4 8 2


18/24

14/06/20

Exemplo

ndices de melhoria obtidos:

Como h um ndice negativo, IFA, isso significa que o custo pode serdiminudo se o destinoAfor atendido pela origemF.

35

9 7 + 4 8 2 3 4 + 7 5 +1 3 5 + 8 4 + 7 5 +4 4 5 + 8 4 +3

Nova soluo bsica

Redistribuindo os produtos

36

A B C Oferta

D 5 4 3

100100

E 8 4 3

300200 100

F 9 7 5

300100 200

Demanda 300 200 200 700


19/24

14/06/20

Nova soluo bsica


37

A B C Oferta

D 5 4 3

100100

E 8 4 3

300100 200

F 9 7 5

300100 200

Demanda 300 200 200 700

Exemplo

A nova soluo encontrada :


Rota Unidades

transportadas

Custo por

unidade

Custo

TotalDe Para

D A 100 5 500

E A 100 8 800

E B 200 4 800

F A 100 9 900

F C 200 5 1.000

Total 4.000


20/24

14/06/20

Nova soluo bsica


(Rota de D para B)

39

A B C Oferta

D 5 Incio 4 3

100100 - +

E 8 4 3

300100 + 200 -

F 9 7 5

300100 200

Demanda 300 200 200 700

4 5 + 8 4 +3

Nova soluo bsica Escolhendo a clulaCDC(Rota de D para C)

40

A B C Oferta

D 5 4 Incio 3

100100 - +

E 8 4 3

300100 200

F 9 7 5

300100 + 200 -

Demanda 300 200 200 700

3 5 + 9 5 +2


21/24

14/06/20

Nova soluo bsica

Escolhendo a clulaCEC

(Rota de E para C)

41

A B C Oferta

D 5 4 3

100100

E 8 4 Incio 3

300100 - 200 +

F 9 7 5

300100 + 200 -

Demanda 300 200 200 700

3 8 + 9 5 1

Nova soluo bsica Escolhendo a clulaCFB(Rota de E para C)

42

A B C Oferta

D 5 4 3

100100

E 8 4 3

300100 + 200 -

F 9 Incio 7 5

300100 - + 200

Demanda 300 200 200 700

7 4 + 8 9 +2


22/24

14/06/20

Exemplo


Como h um ndice negativo, IEC, isso significa que o custo pode serdiminudo se o destinoCfor atendido pela origemE.

43

7 4 + 8 9 +2 3 8 + 9 5 1 3 5 + 9 5 +2 4 5 + 8 4 +3

Nova soluo bsica Redistribuindo os produtos

44

A B C Oferta

D 5 4 3

100100

E 8 4 3

300100 200

F 9 7 5

300100 200

Demanda 300 200 200 700


23/24

14/06/20

Nova soluo bsica


45

A B C Oferta

D 5 4 3

100100

E 8 4 3

300200 100

F 9 7 5

300200 100

Demanda 300 200 200 700

Exemplo

A nova soluo encontrada :


Rota Unidades

transportadas

Custo por

unidade

Custo

TotalDe Para

D A 100 5 500

E B 200 4 800

E C 100 3 300

F A 200 9 1.800

F C 100 5 500

Total 3.900


24/24

14/06/20

Exemplo


Como no h ndices negativos, a soluo encontrada tima.

47

7 5 + 3 4 +1 8 9 + 5 3 +1 3 5 + 9 5 +2 4 5 + 9 5 + 3 4 +2

Referncia

MOORI, Jamshid. Transportation and assignment problems.University of Kwazulu-Natal, 2013. Disponvel em:.

48

3. problema de transportes

Documents