Suponha que o departamento de serviços especiais de sondagem (SES) recebe em uma semana uma demanda para a realização de 5 atividades em locais dados pelas coordenadas na tabela abaixo. Cada atividade é realizada por uma equipe que está atualmente sediada num determinado local (cujas coordenadas também são dadas na tabela abaixo). Formule o problema e o resolva:
Coordenada x Coordenada y
Sonda 1 0 0
Sonda 2 0 4
Sonda 3 5 5
Sonda 4 1 2
Sonda 5 3 3
Equipe 1 1 1
Equipe 2 3 2
Equipe 3 1 7
Equipe 4 4 4

Passo 1

Beleza, o enunciado diz que temos 5 sondas (atividades) espalhadas num plano pelas coordenadas dadas, e 4 equipes também com coordenadas fixas. A ideia é “atualocar” cada atividade a uma equipe de modo a minimizar a distância total que elas vão percorrer.
Conteúdo: modelo de atribuição (assignment problem) usando programação inteira e distância euclidiana. Vamos precisar
  • Definir variáveis binárias de alocação x_{ij},
  • Usar a fórmula da distância euclidiana
  • Montar o modelo matemático e resolver (aqui, como não há limite de quantas tarefas uma equipe faz, basta atribuir cada sonda à equipe mais próxima).

Passo 2

Modelagem matemática:
Seja i=1…5 índices das sondas e j=1…4 índices das equipes.
Definimos
xij = 1, &se a sonda i for atribuída à equipe j, 0, &caso contrário íàá
A distância d_{ij} entre a sonda i (x_i,y_i) e a equipe j (X_j,Y_j) é
dij = raiz(xi - Xj)^2 + (yi - Yj)^2
Objetivo e restrição:
min sumi=1^5sumj=1^4 dij,xij sa sumj=1^4 xij = 1forall i, xijin0,1

Passo 3

Vamos calcular d_{ij} rápido (apenas os mínimos de cada linha):
  1. Sonda 1 (0,0):
  • Equipe1 (1,1): → menor
  1. Sonda 2 (0,4):
  • Equipe1 (1,1):
  • Equipe3 (1,7): idem
    Aqui empata, vou escolher Equipe 3 para balancear.
  1. Sonda 3 (5,5):
  • Equipe4 (4,4): → menor
  1. Sonda 4 (1,2):
  • Equipe1 (1,1): → menor
  1. Sonda 5 (3,3):
  • Equipe2 (3,2): → menor

Passo 4

Atribuindo cada sonda à sua equipe mais próxima:
  • Sonda 1 → Equipe 1 (distância ≈1,414)
  • Sonda 2 → Equipe 3 (distância ≈3,162)
  • Sonda 3 → Equipe 4 (distância ≈1,414)
  • Sonda 4 → Equipe 1 (distância =1)
  • Sonda 5 → Equipe 2 (distância =1)
Somando tudo:
(aprox).

Resposta

Atribuições:
• Sonda 1 → Equipe 1
• Sonda 2 → Equipe 3
• Sonda 3 → Equipe 4
• Sonda 4 → Equipe 1
• Sonda 5 → Equipe 2
Distância total mínima ≈ 7,99.

Exercícios relacionados