Problema de Transporte da aula de hoje Método de Vogel Penalizações Ofertas e demandas diferenciadas Variável Dummy Impossibilidade de transporte Uma, ou mais, opção de transporte

Problema de TransporteMÉTODOS QUANTITATIVOS DE GESTÃO

MQG

Aula 4

Fatec Zona Leste | MQG | Prof Celio Daroncho |

Itens da aula de hoje✓ Método de Vogel✓ Penalizações

✓ Ofertas e demandas diferenciadas✓ Variável Dummy

✓ Impossibilidade de transporte

✓ Uma, ou mais, opção de transporte não existe

Aula 04 - Problema de Transporte II 2

Método SimplexMÉTODO DE VOGEL

3


Método de Vogel✓ Trabalha com o cálculo de penalidades✓ Diferença entre os dois menores valores de custo de transporte

✓ Escolhe-se a coluna/linha de maior penalidade✓ Maior delta (Δ) de variação de preço

✓ Faz-se a opção de transportar o máximo pelo menor custo✓ Semelhante ao Custo mínimo


Problema de TransporteDEMANDA E OFERTA DIFERENTES

5


Na aula passada✓ Vimos que a oferta (σ𝑎𝑖) e a demanda (σ𝑏𝑗) deveriam se igualar,

isso para que o problema tivesse solução.


𝑖=1

𝑚

𝑎𝑖 =

𝑗=1

𝑛

𝑏𝑗


Na vida real✓ As restrições referentes a volumes de capacidade instalada (oferta)

e centro consumidores (demanda), geralmente, não se equivalem

✓ É possível encontrar casos onde a oferta é maior que a demanda e casos onde a demanda é maior que a oferta

✓ Como construir modelos quando as restrições são diferenciadas??



Oferta e demanda diferentes✓ No caso da Oferta não ser igual a demanda devemos introduzir um

destino ou uma origem fantasma (dummy) que tenha os custos dos transportes unitários iguais a zero

✓ A dummy deve ser igual à diferença entre o total ofertado e o total demandado



Oferta e demanda diferentes✓ Inserindo uma demanda ou uma oferta fantasma, garantimos que

todas as restrições do problema serão dadas por igualdade

✓ Em outras palavras, o total fabricado será virtualmente igual à demanda dos centros consumidores

✓ Esta igualdade apresentada é condição necessária e suficiente para que qualquer problema de transporte tenha solução ótima quando modelado utilizando-se de variáveis dummy



Oferta e demanda diferentes✓ A inserção do dummy não é obrigatória, porém facilitam a

interpretação do resultado de otimização

✓ Quando existe um desequilíbrio entre a oferta e demanda, podemos ter as seguintes ações e interpretações para as variáveis dummy:


Capacidade > Demanda Demanda > Capacidade

Ação – Busca de novos centros consumidores Ação – Criação de novas fábricas

Interpretação – Capacidade ociosa da fábrica Interpretação – Demanda não atendida

Vogel e DummyEXEMPLO

11


Exemplo Enunciado✓ A JK é uma fabricante de eletrodomésticos que possui três fábricas

localizadas no Rio de Janeiro, São Paulo e em Belo Horizonte e sua produção é entregue em Recife, Salvador e Manaus.

✓ Considerando os custos de transportes unitários, a capacidade de produção das fábricas e a demanda dos centros consumidores, determine quanto deve ser produzido e entregue por cada fábrica em cada centro consumidor, de forma a minimizar os custos de transporte.



Exemplo Grafo


25

30

20

20

25

15

25

23

20

Rio = 2.000

SP = 3.000

BH =1.500

Recife = 2.000

Salvador = 2.000

Manaus = 1.000


Recife Salvador Manaus Capacid.

Rio 25 20 30 2.000

SP 30 25 25 3.000

BH 20 15 23 1.500

Demanda 2.000 2.000 1.000

Exemplo Tabela


A produção é maior do que oconsumo em 1.500 unidades, assolução para isso são: reduzir aprodução, armazenar o excedente ouachar novos consumidores.


Recife Salvador Manaus Dummy

Rio 25 20 30 0

SP 30 25 25 0

BH 20 15 23 0

Demanda 2.000 2.000 1.000

Exemplo Dummy


Capacid.

2.000

3.000

1.500

1.500 6.500Inserir destino dummy, com capacidade de 1.500 e custos de transporte igual a zero (pois é fictício), de modo a equilibrar a oferta e a demanda


Recife Salvador Manaus Dummy Capacid.

Rio 0 2.000

SP 1.500 3.000

BH 0 1.500

Demanda 2.000 2.000 1.000 1.500 6.500

Exemplo Vogel | Passo 1


25

30

20 15

25

20

23

25

30 0

0

0

20 - 0= 20

25 - 0= 25

15 - 0= 15

25 - 20 = 5 20 – 15 = 5 25 – 23 = 2 0 – 0 = 0

1.500

0



Rio 0 2.000

SP 1.500

BH 0 1.500 0 0 1.500

Demanda 2.000 2.000 1.000 0 5.000



25

30

20 15

25

20

23

25

30 0

0

0

25 - 20= 5

25 - 25= 0

20 - 15= 5

25 - 20 = 5 20 – 15 = 5 25 – 23 = 2

1.50020 - 15= 50

500



Rio

0

500 0 2.000

SP 1.500

BH 0 1.500 0 0

Demanda 2.000 1.000 0 3.500



25

30

20 15

25

20

23

25

30 0

0

0

25 - 20= 5

25 - 25= 01.500

0

50030 – 25 = 5

0

1.500

25 – 20 = 530 – 25 = 5



Rio 1.500 500 0 0

SP 0 1.500

BH 0 1.500 0 0

Demanda 2.000 1.000 0 3.000



25

30

20 15

25

20

23

25

30 0

0

0

30 - 25= 5

30 – 25 = 5 30 – 25 = 5

1.500

0

0

1.500 30 - 25= 50

500



Rio 1.500 500 0 0

SP 500 0 1.000 1.500

BH 0 1.500 0 0

Demanda 1.000 0 1.500



25

30

20 15

25

20

23

25

30 0

0

0

30 - 25= 51.500

0

0

0

500

0

0 0



Rio 1.500 500 0 0

SP 500 0 1.000 1.500

BH 0 1.500 0 0

Demanda 1.000 1.500 6.500

Exemplo Vogel | Final


25

30

20 15

25

20

23

25

30 0

0

0

3.000

1.500

2.000

2.000

2.000

𝑍 = 1500 × 25 + 500 × 20 + 500 × 30 + 1000 × 25 + 1500 × 0 + 1500 × 15 = 110.000

ExercícioESTE É COM VOCÊS

22


Exercício✓ A Empresa JK é uma empresa fabricante de eletrodomésticos que possui três

fábricas, uma no Rio de Janeiro, uma em São Paulo e uma em Belo Horizonte. A produção da empresa deve ser entregue em Recife, Salvador e Manaus.

✓ Considerando os custos de transportes unitários, a capacidade de produção das fábricas e a demanda dos centros consumidores, determine quanto deve ser produzido e entregue por cada fábrica em cada centro consumidor, de forma a minimizar os custos de transporte.

✓ Utilize o método de Vogel



Recife Salvador Manaus Capacid.

Rio 15 18 25 2.000

SP 22 20 24 2.500

BH 17 10 30 1.200

Demanda 3.000 2.000 1.500

Exercício Tabela


Problema de TransporteIMPOSSIBILIDADE DE TRANSPORTE

25


Impossibilidade de transporte✓ Dentro de uma realidade é possível acontecer a impossibilidade de

transporte entre uma fábrica e um distribuidor

✓ Se esta condição está presente no modelo, precisamos garantir que na solução final teremos este valor na solução ótima igual a zero

✓ O objetivo do modelo de transportes é minimizar o custo total. Assim, se atribuirmos um custo unitário muito alto na célula correspondente, estaremos criando uma penalidade ou multa para o valor de Z, caso esta variável seja diferente de zero ✓ lembrando que ela não pode ser negativa



Impossibilidade de transporte✓ Na programação matemática, esta multa é chamada de “Big M” e é

representada por um M (maiúsculo)

✓ Quando resolvermos manualmente, podemos trabalhar com o próprio M

✓ Porém, na solução eletrônica o M é substituído por um número muito grande (100.000, por exemplo)


Impossibilidade de TransporteEXEMPLO

28


Exemplo Grafo


5

8

3

6

4

5

7

2

5

4

6

F1 = 30

F2 = 50

F3 =40

CD1 = 30

CD2 = 20

CD3 = 40

CD4 = 30

Inexistente


𝑍 = 30 × 3 + 30 × 4 + 20 × 5 + 10 × 4 + 30 × 6 = 530

CD1 CD2 CD3 CD4 Oferta

F1 0 0 30 0 30

F2 30 20 0 0 50

F3 0 0 10 30 40

Demanda 30 20 40 30 120

Exemplo Tabela


5

4

6 2

5

8

4

7

3 6

M

6

ExercícioESTE É COM VOCÊS

31


Exemplo Enunciado✓ Uma empresa tem fábricas em três locais diferentes (F1, F2 e F3),

que abastecem quatro (D1, D2, D3 e D4) armazéns distantes unsdos outros. As capacidades das fábricas em um certo período detempo são 70, 90 e 115 unidades e as necessidades dos armazéns,no mesmo período de tempo, são 50, 60, 70 e 95 unidades. Oscustos unitários para cada encaminhamento fábrica-armazém estãoexpostos na tabela a seguir✓ Extraído de:✓ Novaes, Antônio Galvão, Métodos de Otimização: aplicações aos transportes. Edgar

Blücher, São Paulo, 1978.



D1 D2 D3 D4

F1 17 20 13 12

F2 15 21 26 25

F3 20 14 15 17

Demanda 50 60 70

Exemplo Tabela


Oferta

70

90

115

95 275

Documents

Problema de Transporte da aula de hoje Método de Vogel Penalizações Ofertas e demandas diferenciadas Variável Dummy Impossibilidade de transporte Uma, ou mais, opção de transporte