Universidade Federal de Itajubá - iepg.unifei.edu.br · Pesquisa Operacional ... unidade dummy que iguale a oferta a demanda. ... uma grande quantidade de peças na cidade de Baependi

1

1

Pesquisa Operacional

Instituto de Engenharia de Produção e Gestão

Universidade Federal de Itajubá

Prof. Dr. José Arnaldo Barra Montevechi

Redes

2

Problemas de rede• Casos especiais de problemas de programação

linear que são mais bem analisados através de uma representação gráfica.

• Importantes problemas de otimização, tais como problemas de logística e de energia, produção e outros, são eficientemente resolvidos e modelados como problemas de rede.

2

3

Problemas de rede• Modelos de rede facilitam a visualização das

relações entre os componentes do sistema, aumentando o entendimento do problema e de seus possíveis resultados.

• É uma modelagem muita usada.

4

Terminologia• Redes, nós e arcos:

NósArcos

3

5

Problemas de rede(Classificação usual)

• Problemas de transporte e rede de distribuição;

• Problemas de menor caminho;

• Problemas de fluxo máximo.

6

Problemas de Distribuição

• Problemas que consideram múltiplas fontes, centros consumidores e locais intermediários por onde os produtos simplesmente passam são denominados problemas de distribuição.

• O problema de transporte já estudado é uma simplificação do problema de rede de distribuição.

4

7

Problemas de Distribuição – exemplo

• Uma montadora de carros esta iniciando as suas operações no Brasil, construindo 2 fábricas: uma na Bahia e outra em São Paulo. A montadora esta estudando a forma de distribuição de seus carros para as diversas revendas, localizadas nos estados: Goiás, Rio de Janeiro, Minas Gerais, Paraná, Santa Catarina e Rio Grande do Sul, que minimize o custo total de distribuição.

8


• As capacidades instaladas de cada uma das fábricas, as demandas das revendas, bem como os custos unitários de transporte entre fábricas e revendas estão evidenciados no diagrama a seguir.

5

9


350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20Oferta (capacidade das fábricas)

(1100)

Demandas

(1400)

10

• Existem 2 maneiras básicas de resolver este problema. A primeira consiste em inserir uma unidade dummy que iguale a oferta a demanda.

• A segunda forma de resolver é seguir a Regra do Fluxo Balanceado para cada nó da rede. Este método dispensa o uso de unidades dummys. O desequilíbrio entre oferta e demanda total étratado através de restrições maior ou igual ou de menor ou igual.


6

11


• Regra do fluxo balanceado:

Entradas – Saídas = Oferta ou Demanda do Nó

Oferta = Demanda

Entradas – Saídas ≤ Oferta ou Demanda do Nó

Oferta < Demanda

Entradas – Saídas ≥ Oferta ou Demanda do Nó

Oferta > Demanda

Tipo de Restrição:Hipótese:

Situação do exemplo

12

Primeiro passo: Variáveis de decisão

Quantidades de veículos enviados de cada fábrica para cada distribuidor

350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20

7

13

Primeiro passo: Variáveis de decisão• X13 – número de carros enviados

de BA para MG.• X14 – número de carros enviados

de BA para RJ.• X15 – número de carros enviados

de BA para GO.• X23 – número de carros enviados

de SP para MG.• X24 – número de carros enviados

de SP para RJ.• X26 – número de carros enviados

de SP para PR.• X27 – número de carros enviados

de SP para SC.• X28 – número de carros enviados

de SP para RS.• X34 – número de carros enviados

de MG para RJ.• X35 – número de carros enviados

de MG para GO.• X78 – número de carros enviados

de SC para RS.

350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20

14

Segundo passo: função objetivoObjetivo: Minimizar os custos de distribuição

• min Z = 25X13 + 30X14 + 40X15 + 20X23 + 15X24 + 20X26 + 35X27 + 50X28 + 20X34 + 20X35 + 20X78

350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20

• X13 – BA para MG.• X14 – BA para RJ.• X15 – BA para GO.• X23 – SP para MG.• X24 – SP para RJ.• X26 – SP para PR.• X27 – SP para SC.• X28 – SP para RS.• X34 – MG para RJ.• X35 – MG para GO.• X78 – SC para RS.

8

15

Terceiro passo: restrições

• Restrição 01 – nó 01• - X13 - X14 - X15 ≤ - 500

350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20

Entradas – Saídas = Oferta ou Demanda do NóOferta = Demanda

Entradas – Saídas ≤ Oferta ou Demanda do NóOferta < Demanda

Entradas – Saídas ≥ Oferta ou Demanda do NóOferta > Demanda



16


350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20• Restrição 02 – nó 02

• – X23 – X24 – X26 – X27 – X28 ≤ - 600

9

17


• Restrição 03 – nó 03• X13 + X23 – X34 – X35 ≤ 200

350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20

18


• Restrição 04 – nó 04• X14 + X24 + X34 ≤ 350

350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20

10

19


• Restrição 05 – nó 05• X15 + X35 ≤ 150

350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20

20


• Restrição 06 – nó 06• X26 ≤ 300

350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20

11

21


• Restrição 07 – nó 07• X27 – X78 ≤ 150

350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20

22


• Restrição 08 – nó 08• X28 + X78 ≤ 250

350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20

12

23

Quarto passo: Restrições adicionais

Para completar a formulação do problema:• Xij >= 0

• i = 1; 2; ....

24

Solução pelo Solver

Problemas de rede de distribuição

Distribuição de carros

De Para Custo Unidades Nó Fluxo liquido Oferta/Demanda1 3 25 0 1 0 -5001 4 30 0 2 0 -6001 5 40 0 3 0 2002 3 20 0 4 0 3502 4 15 0 5 0 1502 6 20 0 6 0 3002 7 35 0 7 0 1502 8 50 0 8 0 2503 4 20 03 5 20 07 8 20 0

Custo Total = 0

350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20

Variáveis de decisão

Informações conhecidas

13

25


Problemas de rede de distribuição

Distribuição de carros

De Para Custo Unidades Nó Fluxo liquido Oferta/Demanda1 3 25 0 1 0 -5001 4 30 0 2 0 -6001 5 40 0 3 0 2002 3 20 0 4 0 3502 4 15 0 5 0 1502 6 20 0 6 0 3002 7 35 0 7 0 1502 8 50 0 8 0 2503 4 20 03 5 20 07 8 20 0

Custo Total = 0

350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20

Fórmula*

26

Solução pelo Solver(Função Objetivo)

14

27

Solução pelo Solver(Restrições)

• Restrição 01 – nó 01• - X13 - X14 - X15 ≤ - 500

350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20

28


• Restrição 01 – nó 01• - X13 - X14 - X15 ≤ - 500

350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20

Entradas Saídas

15

29

Solução pelo Solver(Todas as Restrições)

30


(Solução)

350

50

35

20

15

20

30

25

20

20

BA1

SP2

MG3

RJ4

PR6

SC7

RS8

GO5-500

-600

200

150

300

150

250

40

20

16

31

Problema do Menor Caminho

• Problema que representa um outro caso especial de problemas de redes, em que os arcos significam a distância entre 2 pontos (nós).

• Quando deseja-se achar a rota que une estes pontos com a distância mínima possível, tem-se um problema de menor caminho.

32

Problema do Menor Caminho

• Nestes problema existem sempre 2 nós especiais chamados de origem e destino. Entre um nó de origem e um nó de destino geralmente existem nós intermediários, que podem representar cidades que conectam rodovias, subestações em problemas de distribuição de energia, etc...

17

33

• Um fabrica de artigos de decoração, localizada em Lambari, deve entregar uma grande quantidade de peças na cidade de Baependi. A empresa quer saber qual o caminho que seu caminhão deve fazer para minimizar a distância percorrida.

Problema do Menor Caminho - Exemplo

34

Problemas de Menor Caminho – exemplo

1 6

4

5

3

2

50 Km

Lambari Baependi

Três Corações S. Thomé das Letras

Caxambu

São Lourenço

44 Km

27 Km

4 Km

45 Km

37 Km

41 Km

18

35

• A modelagem do problema terá variáveis binárias do tipo Xij, indicando o sentido da cidade i para a cidade j. Se o valor da variável for igual a 1 significa que aquele trecho deve ser percorrido. De forma inversa, se o valor da variável for igual a zero, significa que aquele trecho não deve ser percorrido.

Problemas de Menor Caminho

36


• X12 – trecho Lambari – Três Corações.• X13 – trecho Lambari – São Lourenço.• X15 – trecho Lambari – Caxambu.• X24 – trecho Três Corações – São Thomé das

Letras.• X35 – trecho São Lourenço – Caxambu.• X46 – trecho São Thomé das Letras – Baependi.• X56 – trecho Caxambu – Baependi.

1 6

4

5

3

2

50 Km

Lambari Baependi


Caxambu

São Lourenço

44 Km

27 Km

4 Km

45 Km

37 Km

41 Km

19

37

Segundo passo: função objetivoObjetivo: Minimizar a distância percorrida pelo caminhão

• Min Z = 41X12 + 44X13 + 50X15 + 37X24 + 27X35 + 45X46 + 4X56

1 6

4

5

3

2

50 Km

Lambari Baependi


Caxambu

São Lourenço

44 Km

27 Km

4 Km

45 Km

37 Km

41 Km

• X12 –Lambari – Três Corações.

• X13 –Lambari – São Lourenço.

• X15 –Lambari – Caxambu.• X24 –Três Corações – São

Thomé das Letras.• X35 –São Lourenço –

Caxambu.• X46 –São Thomé das Letras –

Baependi.• X56 –Caxambu – Baependi.

38


1 6

4

5

3

2

50 Km

Lambari Baependi


Caxambu

São Lourenço

44 Km

27 Km

4 Km

45 Km

37 Km

41 Km






Oferta = -1 Demanda = 1

20

39


• Restrição 01:• - X12 - X13 - X15 = - 1

1 6

4

5

3

2

50 Km

Lambari Baependi


Caxambu

São Lourenço

44 Km

27 Km

4 Km

45 Km

37 Km

41 Km






40


• Restrição 02:• X12 – X24 = 0

1 6

4

5

3

2

50 Km

Lambari Baependi


Caxambu

São Lourenço

44 Km

27 Km

4 Km

45 Km

37 Km

41 Km






21

41


• Restrição 03:• X13 – X35 = 0

1 6

4

5

3

2

50 Km

Lambari Baependi


Caxambu

São Lourenço

44 Km

27 Km

4 Km

45 Km

37 Km

41 Km

42


• Restrição 04:• X24 – X46 = 0

1 6

4

5

3

2

50 Km

Lambari Baependi


Caxambu

São Lourenço

44 Km

27 Km

4 Km

45 Km

37 Km

41 Km

22

43


• Restrição 05:• X15 + X35 – X56 = 0

1 6

4

5

3

2

50 Km

Lambari Baependi


Caxambu

São Lourenço

44 Km

27 Km

4 Km

45 Km

37 Km

41 Km

44


• Restrição 06:• X46 + X56 = 1

1 6

4

5

3

2

50 Km

Lambari Baependi


Caxambu

São Lourenço

44 Km

27 Km

4 Km

45 Km

37 Km

41 Km

23

45


Para completar a formulação do problema:• Xij = 0 ou 1

• i = 1; 2; ....

46Informações conhecidas



1 6

4

5

3

2

50 Km

Lambari Baependi


Caxambu

São Lourenço

44 Km

27 Km

4 Km

45 Km

37 Km

41 Km

24

47


Fórmula

1 6

4

5

3

2

50 Km

Lambari Baependi


Caxambu

São Lourenço

44 Km

27 Km

4 Km

45 Km

37 Km

41 Km

48


Fórmula

1 6

4

5

3

2

50 Km

Lambari Baependi


Caxambu

São Lourenço

44 Km

27 Km

4 Km

45 Km

37 Km

41 Km

*

25

49


• Restrição 01:• - X12 - X13 - X15 = - 1

50


Entradas Saídas






26

51







52

Solução pelo Solver(Solução)

1 6

4

5

3

2

50 Km

Lambari Baependi


Caxambu

São Lourenço

44 Km

27 Km

4 Km

45 Km

37 Km

41 Km

27

53

Problema do Fluxo Máximo

• Quando se quer maximizar a quantidade de um fluxo de um ponto de origem para um ponto de destino e estamos sujeitos a restrições de capacidade de fluxo nos arcos.

• Estes problemas geralmente envolvem fluxo de materiais como água, óleo, gás, energia através de uma rede de tubos ou canos. Podem representar fluxo de carros em malhas viárias, produtos em linha de produção, etc....

54

• Uma empresa distribuidora de gás deseja determinar a quantidade máxima de metros cúbicos por segundo de gás que pode bombear da estação de Campos para o centro consumidor do Rio de Janeiro, através da rede de gasodutos existentes. A figura a seguir ilustra o caso.

Problema do Fluxo Máximo - Exemplo

28

55


,

A B

3

42

1

Campos Rio de Janeiro

40 m3/s

20 m3/s

30 m3/s

30 m3/s

20 m3/s

30 m3/s

40 m3/s

56

Problema do Fluxo Máximo

• Para resolvermos este problema, utilizaremos um pequeno artifício: adicionaremos um arco virtual ligando o nó B ao nó A.

• A FO será portanto a maximização do fluxo de gás que passa de B para A.

• Como o fluxo do Rio de Janeiro para Campus não existe, o valor do fluxo no arco artificial representará o total de gás que pode chegar ao Rio de Janeiro vindo de Campus por mais de um caminho simultaneamente.

29

57

A B

3

42

1


40 m3/s

20 m3/s

30 m3/s

30 m3/s

20 m3/s

30 m3/s

40 m3/s


58


• XA1 – m3/s que saem de Campus e chegam a estação 01.• XA2 – m3/s que saem de Campus e chegam a estação 02. • X13 – m3/s que saem da estação 01 e chegam a estação 03.• X14 – m3/s que saem da estação 01 e chegam a estação 04.• X24 – m3/s que saem da estação 02 e chegam a estação 04.• X3B – m3/s que saem da estação 03 e chegam no Rio de Janeiro.• X4B – m3/s que saem da estação 04 e chegam no Rio de Janeiro.• XBA – m3/s que saem do Rio de Janeiro e chegam em Campus.

(artificial)

A B

3

42

1


40 m3/s

20 m3/s

30 m3/s

30 m3/s

20 m3/s

30 m3/s

40 m3/s

30

59

Segundo passo: função objetivoObjetivo: Maximizar o fluxo de gás

Max Z = XBA

A B

3

42

1


40 m3/s

20 m3/s

30 m3/s

30 m3/s

20 m3/s

30 m3/s

40 m3/s

60


• Restrições:• O fluxo de cada arco deverá ser maior ou igual a zero;• O fluxo de cada arco deverá ser menor ou igual a capacidade

do arco;• O fluxo que chega em cada nó deverá ser igual ao fluxo do

que sai do mesmo;• O fluxo do arco artificial (desconhecido) deve ser grande o

bastante para assumir qualquer valor possível, já que este será maximizado.

A B

3

42

1


40 m3/s

20 m3/s

30 m3/s

30 m3/s

20 m3/s

30 m3/s

40 m3/s

31

61


• Restrições de capacidade:• XA1 ≤ 40; XA2 ≤ 30;• X13 ≤ 30; X14 ≤ 20;• X24 ≤ 30; X3B ≤ 20;• X4B ≤ 40; XBA ≤ 9999;

A B

3

42

1


40 m3/s

20 m3/s

30 m3/s

30 m3/s

20 m3/s

30 m3/s

40 m3/s

62


• Restrições de fluxo:• XBA – (XA1 + XA2) = 0• XA1 – (X13 + X14) = 0• XA2 – X24 = 0• X13 – X3B = 0• X14 + X24 – X4B = 0• X3B + X4B – XBA = 0

A B

3

42

1


40 m3/s

20 m3/s

30 m3/s

30 m3/s

20 m3/s

30 m3/s

40 m3/s






32

63


Para completar a formulação do problema:• Xij >= 0

• i = A; B; 1; 2; ....

64

A B

3

42

1


40 m3/s

20 m3/s

30 m3/s

30 m3/s

20 m3/s

30 m3/s

40 m3/s



Informações conhecidas

33

65Fórmula


66


Entradas Saídas

34

67


68

Solução pelo Solver(Solução)

A B

3

42

1


40 m3/s

20 m3/s

30 m3/s

30 m3/s

20 m3/s

30 m3/s

40 m3/s

Documents

Universidade Federal de Itajubá - iepg.unifei.edu.br · Pesquisa Operacional ... unidade dummy que iguale a oferta a demanda. ... uma grande quantidade de peças na cidade de Baependi