PESQUISA OPERACIONAL II 2018

LOCALIZAÇÃO

Capítulo 1

1-1

Capítulo 1

1-2

Regra do Jogo

Provas

1a Prova: 9 de outubro

2a Prova: 13 de novembro

Substitutiva: 20 de novembro

Média

P = Média das Provas

T = Média dos Trabalhos

Média = 0.8*P + 0.2*T

Bibliografia

Hillier, F. S., Lieberman, G.

J. Introdução à Pesquisa

Operacional, McGraw-

Hill, 2006

Lachtermacher, G.

Pesquisa Operacional na

Tomada de Decisões,

Campus, 2004

Wagner, H. M. Pesquisa

Operacional, Prentice-

Hall, 1986

Netto, P. O. B., Jurkiewicz,

S. Grafos: Introdução e

Prática, Blucher, 2017

LOCALIZAÇÃO

O que localizar?

Pontos Origem

Plantas, Vendedores, Portos

Pontos Intermediários

Armazéns, Terminais, Serviços públicos

(bombeiros, polícia, ambulâncias)

Pontos Destino

Varejistas, Clientes, Usuários

Capítulo 1

Fábricas

Estoques

Bancos

Creches

Antenas

1-3

LOCALIZAÇÃO

Por que é importante?

Estruturação da rede

Impacta significativamente

sobre os custos de estoque e

transporte

Fundamental para o nível de

serviço

Capítulo 1

Métodos de Resolução

Centro de Gravidade

Programação Inteira Mista

Modelo da P-mediana

1-4

Modelo

Matemático

1. Localização de Armazéns RS

A CEARS quer construir três novos armazéns agrícolas. Dados

os custos abaixo, localizar os armazéns.

Opções Custo

Construção

Capacidade Uruguaiana Pelotas Caxias do

Sul

Passo

Fundo

Porto

Alegre

Alegrete 7 milhões 600 kton 2,10 6,30 7,80 6,30 7,50

Caçapava

do Sul

5 milhões 750 kton 5,70 2,70 4,50 4,50 3,78

Tupanciretá 9 milhões 350 kton 5,40 5,58 4,38 2,88 4,80

Vacaria 6 milhões 450 kton 10,20 6,54 1,14 2,40 3,00

Santa Rosa 4 milhões 400 kton 5,58 7,86 6,00 3,48 6,84

Demanda 150 kton 450 kton 300 kton 250 kton 500 kton

Capítulo 1

1-5

Custo de transporte

Modelo Matemático

Minimizar = 7000y1 + 5000y2 + 9000y3 + 6000y4 + 4000y5 + 2,1 x11 + 6,3 x12 + 7,8 x13 +

... + 6,84x55

Sujeito a x11 + x12 + x13 + x14 + x15 ≤ 600 y1 yi = 0/1

x21 + x22 + x23 + x24 + x25 ≤ 750 y2 xij ≥ 0

x31 + x32 + x33 + x34 + x35 ≤ 350 y3

x41 + x42 + x43 + x44 + x45 ≤ 450 y4

x51 + x52 + x53 + x54 + x55 ≤ 400 y5

x11 + x21 + x31 + x41 + x51 = 150

x12 + x22 + x32 + x42 + x52 = 450

x13 + x23 + x33 + x43 + x53 = 300

x14 + x24 + x34 + x44 + x54 = 250

x15 + x25 + x35 + x45 + x55 = 500

y1 + y2 + y3 + y4 + y5 = 3

yi = 1 se localizar na cidade i

0 caso contrário

xij = quantidade enviada de i para j

Capítulo 1

1. Localização de Armazéns RS

1-6

Capítulo 1

1. Localização de Armazéns RS EXCEL

1-7

150 200 150 600

250 500 750

350

450

150 250 400

150 450 300 250 500

Capítulo 1

1. Localização de Armazéns RS LINGO

1-8

150 200 150 600

250 500 750

350

450

150 250 400

150 450 300 250 500

2. Problema do Hospital

O MHH pretende instalar serviços médicos de emergência na

região em que opera.

A meta principal é garantir que nenhum paciente gaste mais

do que 10 minutos para chegar a um centro de emergência.

Qual o número mínimo de salas de emergência e em que

pontos localizá-las?

Capítulo 1

1-9

2. Problema do Hospital

Tempo em trânsito de cada região para os locais potenciais

de sala de emergência:

1 2 3 4 5 6

A 0 5 15 25 25 15

B 5 0 20 30 15 5

C 15 20 0 10 25 15

D 25 30 10 0 10 20

E 25 15 25 10 0 9

F 15 5 15 20 9 0

Capítulo 1

Pontos de localização

Áreas

1-10

Locais de atendimento de emergência com tempo de

deslocamento de até 10 minutos:

Ponto Entorno

1 A, B

2 A, B, F

3 C, D

4 C, D, E

5 D, E, F

6 B, E, F

2. Problema do Hospital

Capítulo 1

1-11

Modelo Matemático Minimizar = xA + xB + xC + xD + xE + xF

Sujeito a xA + xB ≥ 1 Local 1

xA + xB + xF ≥ 1 Local 2

xC + xD ≥ 1 Local 3

xC + xD + xE ≥ 1 Local 4

xD + xE + xF ≥ 1 Local 5

xB + xE + xF ≥ 1 Local 6

xi = 1 se localizar na área i

0 caso contrário

2. Problema do Hospital

Capítulo 1

1-12

2. Problema do Hospital EXCEL

Capítulo 1

1-13

2. Problema do Hospital LINGO

Capítulo 1

1-14

3. Problema do Banco

A OTC pretende estabelecer-se em 20 municípios principais (PPB).

De acordo com a lei de Ohio, se estabelecer-se em 1 município principal (PPB), pode abrir agências ali e nos municípios adjacentes.

Determinar quais são os municípios mais indicados para instalação de um número mínimo de PPBs.

Capítulo 1

1-15

Município Vizinhos Município Vizinhos

1) Ashtabula 2, 12, 16 11) Stark 8, 10, 13, 14, 15, 18,

19, 20

2) Lake 1, 3, 12 12) Geauga 1, 2, 3, 10, 13, 16

3) Cuyahoga 2, 4, 9, 10, 12, 13 13) Portage 3, 10, 11, 12, 15, 16

4) Lorain 3, 5, 7, 9 14) Columbiana 11, 15, 20

5) Huron 4, 6, 7 15) Mahoning 11, 13, 14, 16

6) Richland 5, 7, 17 16) Trumbell 1, 12, 13, 15

7) Ashland 4, 5, 6, 8, 9, 17, 18 17) Knox 6, 7, 18

8) Wayne 7, 9, 10, 11, 18 18) Holmes 7, 8, 11, 17, 19

9) Medina 3, 4, 7, 8, 10 19) Tuscarawas 11, 18, 20

10) Summit 3, 8, 9, 11, 12, 13 20) Carroll 11, 14, 19

3. Problema do Banco

Capítulo 1

1-16

Modelo Matemático

Minimizar = x1 + x2 + x3 + x4 + x5+ x6 + x7 + x8 + x9 + x10 + x11 + x12 + x13 + x14 + x15 + x16 + x17 +

x18 + x19 + x20

Sujeito a:

x1 + x2 + x12 + x16 >= 1; x1 + x2 + x3 + x12 >= 1;

x2 + x3 + x4 + x10 + x12 + x13 >= 1; x3 + x4 + x5 + x7 + x9 >= 1;

x4 + x5 + x6 + x7 >= 1; x5 + x6 + x7 + x17 >= 1;

x4 + x5 + x6 + x7 + x8 + x9 + x17 + x18 >= 1; x7 + x8 + x9 + x10 + x11 + x18 >= 1;

x3 + x4 + x7 + x8 + x9 + x10 >= 1; x3 + x8 + x9 + x10 + x11 + x12 + x13 >= 1;

x8 + x10 + x11 + x13 + x14 + x15 + x18 + x19 + x20 >= 1;

x1 + x2 + x3 + x10 + x12 + x13 + x16 >= 1;

x3 + x10 + x11 + x12 + x13 + x15 + x16 >= 1; x11 + x14 + x15 + x20 >= 1;

x11 + x13 + x14 + x15 + x16 >=1; x1 + x12 + x13 + x14 + x15 + x16 >= 1;

x6 + x7 + x17 + x18 >= 1; x7 + x8 + x11 + x17 + x8 + x19 >= 1;

x11 + x18 + x19 + x20 >= 1; x11 + x14 + x19 + x20 >= 1;

3. Problema do Banco xi = 1 se localizar PPB em i

0 caso contrário

Capítulo 1

1-17

3. Problema do Banco LINGO

Capítulo 1

1-18

Capítulo 1

Modelo da P-Mediana

Modelo Matemático

x11 x12 x13

x21 x22 x23

x31 x32 x33

L1 L2 L3

L1 1 0 0

L2 0 0 1

L3 0 0 1

1-19

Uma empresa com filiais em 4 cidades da região sudeste (Ribeirão

Preto, São José do Rio Preto, Uberlândia, Londrina e Presidente

Prudente) quer marcar 1 ou 2 reuniões entre seus colaboradores

em uma destas cidades, a que for mais conveniente para

seus colaboradores.

Resolver o problema da

p-mediana e localizar:

a) Uma cidade

b) Duas cidades

4. Problema das Reuniões

P-MEDIANA

Capítulo 1

1-20

RP SJRP U L PP

RP 0 186 281 471 446

SJRP 186 0 289 390 275

U 281 289 0 743 562

L 471 390 743 0 162

PP 446 275 562 162 0

Distâncias

Modelo Matemático

Minimizar = 186*x12 + 281*x13 + 471*x14 + 446*x15 + 186*x21 + 289*x23 + 390*x24 + 275*x25 + 281*x31 + 289*x32 +

743*x34 + 562*x35 + 471*x41 + 390*x42 + 743*x43 + 162*x45 + 446*x51 + 275*x52 + 562*x53 + 162*x54;

Sujeito a

x11 + x12 + x13 + x14 + x15 = 1; x21 + x22 + x23 + x24 + x25 = 1; x31 + x32 + x33 + x34 + x35 = 1;

x41 + x42 + x43 + x44 + x45 = 1; x51 + x52 + x53 + x54 + x55 = 1; x11 + x22 + x33 + x44 + x55 = 2;

x11 + x21 + x31 + x41 + x51 <= 3; x12 + x22 + x32 + x42 + x52 <= 3; x13 + x23 + x33 + x43 + x53 <= 3;

x14 + x24 + x34 + x44 + x54 <= 3; x15 + x25 + x35 + x45 + x55 <= 3;

x11 + x21 + x31 + x41 + x51 >= x11; x12 + x22 + x32 + x42 + x52 >= x22; x13 + x23 + x33 + x43 + x53 >= x33;

x14 + x24 + x34 + x44 + x54 >= x44; x15 + x25 + x35 + x45 + x55 >= x55;

x21 <= x11; x31 <= x11; x41 <= x11; x51 <= x11;

x12 <= x22; x32 <= x22; x42 <= x22; x52 <= x22;

x13 <= x33; x23 <= x33; x43 <= x33; x53 <= x33;

x14 <= x44; x24 <= x44; x34 <= x44; x54 <= x44;

x15 <= x55; x25 <= x55; x35 <= x55; x45 <= x55;

Capítulo 1

4. Problema das Reuniões

P-MEDIANA

x11 x12 x13 x14 x15

x21 x22 x23 x24 x25

x31 x32 x33 x34 x35

x41 x42 x43 x44 x45

x51 x52 x53 x54 x55

1-21

xij = 1 se o agente da cidade i

é designado para

reunião na cidade j

0 caso contrário

4. Localidade para Reuniões

P-MEDIANA

Capítulo 1

1-22

A Plus quer construir 1 ou 2 incineradores para destruir produtos tóxicos transportados de 5 cidades (A, B, C, D, E) para incineração em qualquer uma destas cidades. A capacidade de cada incinerador instalado será de 1000 toneladas.

Resolver o problema da

p-mediana e localizar:

a) Um incinerador

b) Dois incineradores

5. Problema dos Incineradores

P-MEDIANA

Capítulo 1

1-23

A B C D E Tonela

das

A 0 9 6 4 2 100

B 9 0 7 1 5 200

C 6 7 0 3 8 150

D 4 1 3 0 3 150

E 2 5 8 3 0 300

Distâncias

Modelo Matemático

Minimizar = 9*x12 + 6*x13 + 4*x14 + 2*x15 + 9*x21 + 7*x23 + 1*x24 + 5*x25 + 6*x31 + 7*x32 + 3*x34 + 8*x35 + 4*x41 +

1*x42 + 3*x43 + 3*x45 + 2*x51 + 5*x52 + 8*x53 + 3*x54;

s/a x11 + x12 + x13 + x14 + x15 = 1; x21 + x22 + x23 + x24 + x25 = 1; x31 + x32 + x33 + x34 + x35 = 1;

x41 + x42 + x43 + x44 + x45 = 1; x11 + x12 + x13 + x14 + x15 = 1 x11 + x22 + x33 + x44 + x55 = 1;

x11 + x21 + x31 + x41 + x51 <= 5; x12 + x22 + x32 + x42 + x52 <= 5; x13 + x23 + x33 + x43 + x53 <= 5;

x14 + x24 + x34 + x44 + x54 <= 5; x15 + x25 + x35 + x45 + x55 <= 5; x11 + x21 + x31 + x41 + x51 >= 2*x11;

x12 + x22 + x32 + x42 + x52 >= 2*x22; x13 + x23 + x33 + x43 + x53 >= 2*x33; x14 + x24 + x34 + x44 + x54 >= 2*x44;

x15 + x25 + x35 + x45 + x55 >= 2*x55;

100*x11 + 200*x21 + 150*x31 +150*x41 +300*x51 <= 1000*x11;

100*x12 + 200*x22 +150*x32 +150*x42 + 300*x52 <= 1000*x22;

100*x13 + 200*x23 +150*x33 +150*x43 + 300*x53 <= 1000*x33;

100*x14 + 200*x24 +150*x34 +150*x44 + 300*x54 <= 1000*x44;

100*x15 + 200*x25 +150*x35 +150*x45 + 300*x55 <= 1000*x55;

x21 <= x11; x31 <= x11; x41 <= x11; x51 <= x11; x12 <= x22; x32 <= x22; x42 <= x22; x52 <= x22;

x13 <= x33; x23 <= x33; x43 <= x33; x53 <= x33; x14 <= x44; x24 <= x44; x34 <= x44; x54 <= x44;

x15 <= x55; x25 <= x55; x35 <= x55; x45 <= x55;

Capítulo 1

5. Problema dos Incineradores

P-MEDIANA

x11 x12 x13 x14 x15

x21 x22 x23 x24 x25

x31 x32 x33 x34 x35

x41 x42 x43 x44 x45

x51 x52 x53 x54 x55

1-24

xij = 1 se o produto tóxico da

cidade i é designado

para o incinerador

da cidade j

0 caso contrário

5. Incineradores de Lixo

P-MEDIANA

Capítulo 1

1-25

Fábrica 5 peças e 4 máquinas

Capítulo 1

6. Projeto de Células de Manufatura

P-MEDIANA

M1 M2 M3 M4

P1 1 0 1 0

P2 0 1 0 1

P3 1 0 1 0

P4 1 0 0 0

P5 0 0 0 1

Projetar

2

Células de

Manufatura

M1 M3 M2 M4

P1 1 1

P3 1 1

P4 1

P2 1 1

P5 1

1-26

Dissimilaridades (ou distâncias) entre peças

Capítulo 1

6. Projeto de Células de Manufatura

P-MEDIANA

P1 P2 P3 P4 P5

P1 0 4 0 1 3

P2 0 4 3 1

P3 0 1 3

P4 0 2

P5 0

M1 M2 M3 M4

P1 1 0 1 0

P2 0 1 0 1

P3 1 0 1 0

P4 1 0 0 0

P5 0 0 0 1

1-27

Modelo Matemático

Minimizar = 4*x12 + 4*x21 + x14 + x41 + 3*x15 + 3*x51 + 4*x23 + 4*x32 + 3*x24 +3*x42 +

x25 + x52 + x34 + x43 + 3*x35 + 3*x53 + 2*x45 + 2*x54;

Sujeito a x11 + x12 + x13 + x14 + x15 = 1; x21 + x22 + x23 + x24 + x25 = 1;

x31 + x32 + x33 + x34 + x35 = 1; x41 + x42 + x43 + x44 + x45 = 1;

x51 + x52 + x53 + x54 + x55 = 1;

x11 + x22 + x33 + x44 + x55 = 2;

x21 <= x11; x31 <= x11; x41 <= x11; x51 <= x11;

x12 <= x22; x32 <= x22; x42 <= x22; x52 <= x22;

x13 <= x33; x23 <= x33; x43 <= x33; x53 <= x33;

x14 <= x44; x24 <= x44; x34 <= x44; x54 <= x44;

x15 <= x55; x25 <= x55; x35 <= x55; x45 <= x55;

Capítulo 1

6. Projeto de Células de Manufatura

P-MEDIANA

x11 x12 x13 x14 x15

x21 x22 x23 x24 x25

x31 x32 x33 x34 x35

x41 x42 x43 x44 x45

x51 x52 x53 x54 x55

xij = 1 se i pertence

ao grupo

formado em

torno de j

0 caso contrário

P1 P2 P3 P4 P5

P1 - 4 0 1 3

P2 - 4 3 1

P3 - 1 3

P4 - 2

P5 -

1-28

Capítulo 1

6. Projeto de Células de Manufatura

P-MEDIANA

x11 x12 x13 x14 x15

x21 x22 x23 x24 x25

x31 x32 x33 x34 x35

x41 x42 x43 x44 x45

x51 x52 x53 x54 x55

1 0 0 0 0

0 1 0 0 0

1 0 0 0 0

1 0 0 0 0

0 1 0 0 0

0 0 1 0 0

0 0 0 0 1

0 0 1 0 0

0 0 1 0 0

0 0 0 0 1

M1 M3 M2 M4

P1 1 1

P3 1 1

P4 1

P2 1 1

P5 1

M1 M2 M3 M4

P1 1 0 1 0

P2 0 1 0 1

P3 1 0 1 0

P4 1 0 0 0

P5 0 0 0 1

1-29

Capítulo 1

6. Projeto de Células de Manufatura

P-MEDIANA

x11 x12 1

x14 x15

x21 x22 x23 x24 1

x31 x32 1

x34 x35

x41 x42 1

x44 x45

x51 x52 x53 x54 1

M1 M3 M2 M4

P1 1 1

P3 1 1

P4 1

P2 1 1

P5 1

Função-Objetivo = 2

1-30

Capítulo 1

P-MEDIANA

7. Problema dos Laboratórios

P-MEDIANA

1-31