Aula 15 Problema Transporte

Daniel Hasan [email protected]

Pesquisa OperacionalAula 15: Problemas de Transporte

Problema de Transporte

Trata-se de um tipo especial de PL onde existe O envio de mercadoria de origens (e.g. fbricas) Para destinos (e.g. depsitos)

Podemos fazer uma representao do problema usando grafos (redes) onde: Cada origem e destino representado como um vrtice

(nodo) H uma aresta (arco) direcionada da origem para cada

destino Esta aresta tem a seguinte informao: cij xij

O custo cij e a quantidade xij a ser enviada da origem i para o destino j

Problema de Transporte [Taha, 2013, cap. 5]Representao

H uma aresta direcionada da origem para cada destino

Esta aresta tem a seguinte informao: cij xij O custo cij e a quantidade xij a ser enviada da origem i para o

destino j

1

2

n

2

m

1

Exemplo com n vrtices de origem e m vrtices destino

origem destinoc11 x11

cnm xnm

.

.

.

.

.

.

.

.

.

Problema de Transporte [Taha, 2013, cap. 5]Exemplo

A MG Auto tem trs fbricas: uma em Los Angeles, outra em Detroit e outra em Nova Orleans, e duas granes centrais de distribuio: Denver e outra em Miami. As capacidades das trs fbricas so de 1.000, 1.500 e 1.200 carros. As demandas das duas centrais de distribuio so 2.300 e 1400 carros. O custo de transporte por carro est expresso na tabela abaixo.

Denver Miami

Los Angeles 80 215

Detroit 100 108

Nova Orleans 40 68

Destino

Orig

em


Capacidade das fbricas: Los Angeles: 1.000 Detroit: 1.500 Nova Orleans: 1.200

Demanda das centrais de distribuio: Denver: 2.300 Miami: 1.400

Variveis de deciso: xij: Quantidade de carros transportados de i para j sendo que i={1,2,3}

so as origens: Los Angeles, Detroit e Nova Orleans e j = {1,2} que so os destinos: Denver e Miami

Denver (1) Miami (2)

Los Angeles (1) 80 215

Detroit (2) 100 108

Nova Orleans (3) 40 68

Destino (demanda)

Orig

em

(su p

r imen

to)




Funo objetivo



Detroit (2) 100 108


Destino (demanda)

Orig

em

(su p

r imen

to)

1

2

3 2

1

origem destino

80 x11

LosAngeles

Detroit

NovaOrleans

Denver

Miami

215 x12

100 x21

108 x2240 x31

68 x32




Funo objetivo



Detroit (2) 100 108


Destino (demanda)

Orig

em

(su p

r imen

to)

1

2

3 2

1

origem destino

80 x11

LosAngeles

Detroit

NovaOrleans

Denver

Miami

215 x12

100 x21

108 x2240 x31

68 x32

minimizar


Capacidade das fbricas:

Los Angeles: 1.000 Detroit: 1.500 Nova Orleans: 1.200 Demanda das centrais de distribuio:

Denver: 2.300 Miami: 1.400 Restries da capacidade das fbricas:

1

2

3 2

1

origem destino

80 x11

LosAngeles

Detroit

NovaOrleans

Denver

Miami

215 x12

100 x21

108 x2240 x31

68 x32




Denver: 2.300 Miami: 1.400 Restries da demanda das centrais:

1

2

3 2

1

origem destino

80 x11

LosAngeles

Detroit

NovaOrleans

Denver

Miami

215 x12

100 x21

108 x2240 x31

68 x32


Dado: xij: Quantidade de carros transportados de i para j sendo que i={1,2,3} so as origens: Los Angeles, Detroit e Nova Orleans e j = {1,2} que so os destinos: Denver e Miami

Encontrar xij para i={1,2,3} e j={1,2} de modo a:

Minimizar

Sujeito a

Problema de Transporte [Taha, 2013, cap. 5]Exemplo Balanceamento

Para que o mtodo de soluo deste problema funcione, deve haver balanceamento

Todo o recurso fornecido pela origem deve ser suprido pelo destino


Los Angeles: 1.000 Detroit: 1.500 Nova Orleans: 1.200 Total de carros: 3.700

Demanda das centrais de distribuio:

Denver: 2.300 Miami: 1.400 Total de demanda: 3.700

Caso isso no ocorra, temos que criar destinos e origens fantasmas

Problema de Transporte [Taha, 2013, cap. 5]Exemplo Criao de Origem Fantasma


Los Angeles: 1.000 Detroit: 1.000 Nova Orleans: 1.200 Total de carros: 3.200

Demanda: 3.700

1

2

3 2

1

origem destino

80 x11

LosAngeles

Detroit

NovaOrleans

Denver

Miami

215 x12

100 x21

108 x2240 x31

68 x32



Los Angeles: 1.000 Detroit: 1.000

Nova Orleans: 1.200 Fbrica Fictcia: 500

Total de carros: 3.200 (+500 fictcia) Demanda: 3.700

1

2

32

1

origem

destino

80 x11

LosAngeles

Detroit

NovaOrleans

Denver

Miami

215 x12

100 x21

108 x2240 x31

68 x32

4Fictcia

0 x42

0 x41



Los Angeles: 1.000 Detroit: 1.000

Nova Orleans: 1.200 Fbrica Fictcia: 500

Total de carros: 3.200 (+500 fictcia) Demanda: 3.700

1

2

32

1

origem

destino

80 x11

LosAngeles

Detroit

NovaOrleans

Denver

Miami

215 x12

100 x21

108 x2240 x31

68 x32

4Fictcia

0 x41

0 x42

0 x41

Como esta fbrica noexiste, o custo dela zero.

Porm, podemos deixar o customuito alto para um destino especfico

caso quisessemos que um destino no sofressetanto com a escassez de carros

Problema de Transporte [Taha, 2013, cap. 5]Exemplo Criao de Destino Fantasma

Produo Total: 3.700 carros Demanda das centrais de distribuio:

Denver: 2.300 Miami: 1.000 Total de demanda: 3.300

1

2

3 2

1

origem destino

80 x11

LosAngeles

Detroit

NovaOrleans

Denver

Miami

215 x12

100 x21

108 x2240 x31

68 x32



Denver: 2.300 Miami: 1.000 Local Fictcio: 400 Total de demanda: 3.300 (+400 fictcia)

1

2

3

2

1

origem destino

80 x11

LosAngeles

Detroit

NovaOrleans

Denver

Miami

215 x12

100 x21108 x22

40 x3168 x32

3Fictcia

0 x130 x23

0 x33



Denver: 2.300 Miami: 1.000 Local Fictcio: 400 Total de demanda: 3.300

1

2

3

2

1

origem destino

80 x11

LosAngeles

Detroit

NovaOrleans

Denver

Miami

215 x12

100 x21108 x22

40 x31 68 x32

3Fictcia

0 x130 x23

0 x33

Custo tambm zero. caso quisessemos que uma fbrica esgotassetodo seu estoque, colocamos um custo muito

alto em sua aresta.

Modelagem quando noh caminho entre uma origem e um destino

1

2

3 2

1

origem destino

80 x11

LosAngeles

Detroit

NovaOrleans

Denver

Miami

M x12

100 x21

108 x2240 x31

68 x32

Ex: Caso no h caminho entre Los Angeles e Miami, coloque um custo M bem alto de Los Angeles para Miami

Soluo para o Problema de transporte [Taha, 2013]

1) Determine uma soluo bsica inicial vivel e passe para etapa 2

2) Use a condio de otimalidade do mtodo simplex para determinar a varivel que entra na base. Se a condio de otimalidade for satisfeita, pare.

3) Use a condio de viabilidade do mtodo simplex para determinar a varivel que sai da base.

Soluo para o Problema de Transporte [Taha, 2013]Representao da Tabela

Origem Destino1 Destino2 Produo (fornecimento)

Origem1 x11 x12

Origem2 x21 x22

Origem3 x31 x32Demanda

c11 c12

c11 c22

c32c31

Soluo para o Problema de Transporte [Taha, 2013]Representao da Tabela para Problemas de Transporte

Origem Destino1 Destino2 Produo (fornecimento)

Origem1 x11 x12

Origem2 x21 x22

Origem3 x31 x32Demanda

c11 c12

c11 c22

c32c31

Capacidade de produo das fbricas:


Denver: 2.300 Miami: 1.400Minimizar

Soluo para o Problema de Transporte [Taha, 2013]Representao da Tabela para Problemas de Transporte

Origem Denver Miami Produo (fornecimento)

Los Angeles x11 x12 1.000

Detroit x21 x22 1.500

Nova Orleans x31 x32 1.200Demanda 2.300 1.400

80 215

100 108

6840




Soluo Bsica Inicial





80 215

100 108

6840




Soluo Bsica Inicial





80 215

100 108

6840

Canto noroeste:

1) Aloque o mximo possvel em x11

2) Caso a linha no haja mais fornecimento possvel, passe para a prxima linha. Caso no haja mais demanda para esta coluna, passe para a prxima coluna.

Soluo Bsica Inicial


Los Angeles 1.000 x12 1.000



80 215

100 108

6840

Canto noroeste:



Soluo Bsica Inicial



Detroit 1.300 x22 1.500


80 215

100 108

6840

Canto noroeste:



Soluo Bsica Inicial



Detroit 1.300 200 1.500


80 215

100 108

6840

Canto noroeste:



Soluo Bsica Inicial


Los Angeles 1.000 1.000

Detroit 1.300 200 1.500

Nova Orleans 1.200 1.200Demanda 2.300 1.400

80 215

100 108

6840

Canto noroeste:



Escolha da varivel que entra

Usando as soluo bsica atual temos que descobrir, para cada varivel x ij no bsica, o seu coeficiente multiplicador na linha da funo objetivo da tabela simplex

Primeiramente, temos que resolver a equao ui + vj = cij pra cada varivel bsica: xij, onde:

ui: origem vj: cada destino cij: o coeficiente de custo atual de cada varivel xij

Para resolver o sistema de equaes, escolha uma linha qualquer e defina u i = 0

Por exemplo, u1 = 0

Assim, como sabemos cij, conseguimos descobrir os valores de ui e vj

Depois disso, para cada varivel no bsica xij descobrimos seu coeficiente multiplicador fazendo ui vi - cij

A varivel que entra ser com o maior multiplicador positivo (j que estamos fazendo uma minimizao)


Origem Denver (v1) Miami (v2)Produo

(fornecimento)

Los Angeles (u1) 1.000 1.000

Detroit (u2) 1.300 200 1.500

Nova Orleans (u3) 1.200 1.200Demanda 2.300 1.400

80 215

100 108

6840



(fornecimento)

Los Angeles (u1) 1.000 1.000

Detroit (u2) 1.300 200 1.500


80 215

100 108

6840

Para cada varivel no basica, faa: ui + vi - cij



(fornecimento)

Los Angeles (u1) 1.000 1.000

Detroit (u2) 1.300 200 1.500


80 215

100 108

6840


20

-127



(fornecimento)

Los Angeles (u1) 1.000 1.000

Detroit (u2) 1.300 200 1.500


80 215

100 108

6840


20

-127

Varivel que entra (maior valor positivo): x31

Varivel que sai


(fornecimento)

Los Angeles (u1) 1.000 1.000

Detroit (u2) 1.300 200 1.500


80 215

100 108

6840

Aumentando a varivel x31, dispara uma reao em cadeia para compensar as mudanas nas demaisvariveis bsicas com o objetivo de continuar satisfazendo as restriesde oferta e demanda.A primeira varivel bsica a chegar a zero a varivel bsica que sai

20

-127



(fornecimento)

Los Angeles (u1) 1.000 1.000

Detroit (u2) 1.300 200 1.500


80 215

100 108

6840


20

-127

Varivel que entra (maior valor positivo): x31

Varivel que sai


(fornecimento)

Los Angeles (u1) 1.000 1.000

Detroit (u2) 1.300 200 1.500

Nova Orleans (u3) 1.200 1.200 1.200Demanda 2.300 1.400

80 215

100 108

6840

20

-127

Varivel que sai


(fornecimento)

Los Angeles (u1) 1.000 1.000

Detroit (u2) 1.300 200 1.500


80 215

100 108

6840

20

-127

Varivel que sai


(fornecimento)

Los Angeles (u1) 1.000 1.000

Detroit (u2) 1.300 1.400 1.500


80 215

100 108

6840

20

-127

Varivel que sai


(fornecimento)

Los Angeles (u1) 1.000 1.000

Detroit (u2) 100 1.400 1.500


80 215

100 108

6840

20

-127

Varivel que sai: x32

2 Iterao Varivel que entra na base


(fornecimento)

Los Angeles (u1) 1.000 1.000

Detroit (u2) 100 1.400 1.500


80 215

100 108

6840

-127

Recalcular ui e vi para definir qual varivel que entra

-20

Como todos os coeficientes so negativos, a soluo tima

Recalcular ui e vi para definir qual varivel que entra

2 Iterao Varivel que entra na base


(fornecimento)

Los Angeles (u1) 1.000 1.000

Detroit (u2) 100 1.400 1.500


80 215

100 108

6840

-127

-20

1

2

3 2

1

origem destino

1.000

LosAngeles

Detroit

NovaOrleans

Denver

Miami

1001.400

1.200

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46

Documents

Aula 15 Problema Transporte