A Programação Linear

[pic 1]

UNIVERSIDADE FEDERAL DE PERNAMBUCO

CENTRO ACADEˆMICO DO AGRESTE NU´CLEO DE TECNOLOGIA

PROGRAMA DE PO´S-GRADUAC¸ A˜O EM ENGENHARIA DE PRODUC¸ A˜O

Winicius Antonio Souza Silva Atividade 7 Pesquisa Operacional

Caruaru 2024

Problema  1  de  Programa¸c˜ao  Linear

Objetivo:  Minimizar o custo total de instala¸c˜ao dos postos de atendimento.

Vari´aveis  de  Decis˜ao:

• x1: Posto no Bairro 1
• x2: Posto no Bairro 2
• x3: Posto no Bairro 3
• x4: Posto no Bairro 4
• x5: Posto no Bairro 5
• x6: Posto no Bairro 6
• x7: Posto no Bairro 7
• x8: Posto no Bairro 8

Restri¸co˜es:

Bairro 1:

Conectado ao bairro 2 (3 km), ao bairro 4 (4 km), ao bairro 3 (3 + 2 = 5 km) e ao bairro 5 (8 km).

Entao, podemos atender o bairro 1 se houver um posto em 1, 2, 3, 4 ou 5.

x1 + x2 + x3 + x4 + x5 ≥ 1;        (1)

Bairro 2:

Conectado ao bairro 1 (3 km), ao bairro 3 (2 km), ao bairro 4 (3 + 4 = 7 km) e ao bairro 6 (2 + 5

= 7 km).  Ent˜ao, podemos atender o bairro 2 se houver um posto em 1, 3, 4 ou 6.

Bairro 3:

---

x1 + x3 + x4 + x6 ≥ 1;        (2)

Conectado  ao  bairro  2  (2  km),  ao  bairro  1  (2  +  3  =  5  km)  e  ao  bairro  6  (5  km).  Ent˜ao,  podemos

atender o bairro 3 se houver um posto em 1, 2, 3 ou 6.

Bairro 4:

---

x1 + x2 + x3 + x6 ≥ 1;        (3)

Conectado  ao  bairro  1  (4  km),  ao  bairro  2  (4  +  3  =  7  km),  ao  bairro  5  (8  km).   Ent˜ao,  podemos

atender o bairro 4 se houver um posto em 1, 2, 4 ou 5.

x1 + x2 + x4 + x5 ≥ 1;        (4)

Bairro 5:

Conectado  ao  bairro  1  (6  km),  ao  bairro  4  (8  km)  e  ao  bairro  7  (8  km).  Ent˜ao,  podemos  atender  o bairro 5 se houver um posto em 1, 4, 5 ou 7.

Bairro 6:

---

x1 + x4 + x5 + x7 ≥ 1;        (5)

Conectado  ao  bairro  2  (5  +  2  =  7  km),  ao  bairro  3  (5  km)  e  ao  bairro  8  (7  km).  Ent˜ao,  podemos

atender o bairro 6 se houver um posto em 2, 3, 6 ou 8.

Bairro 7:

---

x2 + x3 + x6 + x8 ≥ 1;        (6)

Conectado  ao  bairro  5  (8  km)  e  ao  bairro  8  (3  km).  Ent˜ao,  podemos  atender  o  bairro  7  se  houver um posto em 5, 7 ou 8.

Bairro 8:

---

x5 + x7 + x8 ≥ 1;        (7)

Conectado  ao  bairro  6  (7  km)  e  ao  bairro  7  (3  km).  Ent˜ao,  podemos  atender  o  bairro  8  se  houver um posto em 6, 7 ou 8.

Fun¸c˜ao  Objetivo:

---

x6 + x7 + x8 ≥ 1;        (8)

Minimizar Z = 15x1 + 6x2 + 3x3 + 10x4 + 14x5 + 4x6 + 2x7 + 2x8

Restri¸c˜ao  de  Integridade:

Todas as vari´aveis de decis˜ao devem bin´arias.

Xi ∈ {0, 1};

Resolu¸c˜ao  do  Problema  1

[pic 2]

Figura 1: Problema 1 no R

[pic 3]

Figura 2:  Solu¸c˜ao Problema 1 no R

[pic 4]

Figura 3:  Solu¸c˜ao Problema 1 no Solver

Solu¸ca˜o

---

O´tima

Postos de atendimento

Foram escolhidos para serem constru´ıdos nos bairros representados por x2 e x7. Isso indica que esses  bairros  s˜ao  os  locais  mais  estrat´egicos,  considerando  o  custo  dos  terrenos  e  a  necessidade  de acessibilidade para os aposentados.