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
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
Seja i=1…5 índices das sondas e j=1…4 índices das equipes.
Definimos
A distância d_{ij} entre a sonda i (x_i,y_i) e a equipe j (X_j,Y_j) é
Objetivo e restrição:
Passo 3
Vamos calcular d_{ij} rápido (apenas os mínimos de cada linha):
- Sonda 1 (0,0):
- Equipe1 (1,1):
→ menor
- Sonda 2 (0,4):
- Equipe1 (1,1):
- Equipe3 (1,7): idem
Aqui empata, vou escolher Equipe 3 para balancear.
- Sonda 3 (5,5):
- Equipe4 (4,4):
→ menor
- Sonda 4 (1,2):
- Equipe1 (1,1):
→ menor
- 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.
• 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.