Trabalho Pratico de Investigação Operacional

[pic 1][pic 2][pic 3][pic 4][pic 5][pic 6]

[pic 7]

---

Enunciado

Considere o problema de decidir onde colocar sensores de fogo numa área geográfica com o objetivo de detetar eventuais ignições. A região em questão foi discretizada, e selecionado um conjunto de m pontos com coordenadas (𝑎𝑖 , 𝑏𝑖) normalizadas, i.e. com valores entre valores entre 0 e 1. Os dados não indicados no enunciado (e.g. coordenadas dos pontos) são definidos na função getData() onde num_aluno deve ser substituído pelo número de aluno mais elevado do grupo. As distâncias consideradas são as euclidianas.

1. Pretende-se minimizar a distância total dos pontos ao sensor que lhe está mais próximo considerando que existem p sensores (que podem ser localizados em qualquer um dos m pontos).

1. Apresente um modelo de programação inteira.
2. Implemente o modelo em Python/Gurobi.
3. Para m=10 e p=3, obtenha uma solução ótima e discuta a sua razoabilidade.
4. Para m=300 e p=30, obtenha uma solução ótima e discuta a sua razoabilidade.

1. Pretende-se minimizar a maior distância de entre todas as distâncias dos pontos ao sensor que lhe está mais próximo considerando que existem p sensores (que podem ser localizados em qualquer ponto um dos m pontos).

1. Apresente um modelo de programação inteira mista.
2. Implemente o modelo em Python/Gurobi.
3. Para m=10 e p=3, obtenha uma solução ótima e discuta a sua razoabilidade.
4. Para m=300 e p=30, obtenha uma solução ótima e discuta a sua razoabilidade.

1. Considere que há um índice de risco de incêndio entre 1 e 5 representado por 𝑟𝑖 , para cada ponto, 𝑖 = 1, … 𝑚, em que 5 corresponde ao maior risco. Considere também que o alcance de um sensor é limitado a um determinado raio: o sensor deteta uma ignição em todos os pontos a uma distância menor ou igual a 𝑎. Pretende-se que a soma dos índices de risco dos pontos cobertos com, no máximo, 𝑝 sensores seja o maior possível. Note que, se um ponto for coberto por mais de um sensor, apenas o risco tem de ser considerado apenas uma vez.

1. Apresente um modelo de programação inteira.
2. Para m=10 e p=3, a=0.3, obtenha uma solução ótima e discuta a sua razoabilidade.
3. Para m=300 e p=30, a=0.2, obtenha uma solução ótima e discuta a sua razoabilidade.
4. Para m=300 e p=30, a=0.2, obtenha uma solução ótima e discuta a sua razoabilidade
   

1. Considere agora que existem cinco tipos de sensores com diferentes custos e alcances (sensores com maiores custos têm maiores alcances). Pretende-se maximizar o número de pontos cobertos, respeitando o orçamento disponível.

1. Apresente um modelo de programação inteira.
2. Implemente o modelo em Python/Gurobi.
3. Para um exemplo em que m=10 e os restantes valores são dados por getData() e/ou arbitrados por si, obtenha uma solução ótima e discuta a sua razoabilidade.
4. Para um exemplo em que m=100 e os restantes valores são obtidos aleatoriamente no código, obtenha uma solução ótima e discuta a sua razoabilidade.

---

RESOLUÇÃO PERGUNTA 1

a)

Função objetivo:

• [pic 8]

Sujeito a:

• Todas os localizações abrangidas

[pic 9]

• Máximo 3 sensores

[pic 10]

• Sensor tem que existir para abranger a localização respetiva

[pic 11]

b)

# Criar modelo

mod = gp.Model('Exercício1')

# Variáveis de decisão

y = mod.addVars(m, vtype=GRB.BINARY, name='y')

x = mod.addVars(m, m, vtype=GRB.BINARY, name='x')

# Função Objectivo

mod.setObjective(sum(d[i,j]*x[i,j] for i in range(m) for j in range(m)), GRB.MINIMIZE)

# Restrição para abranger todas as localizações

r1=mod.addConstrs((sum(x[i,j] for j in range(m)) == 1) for i in range(m))

# Restrição: Máximo p sensores

r2=mod.addConstr(sum(y[i] for i in range (m)) <= p)

# Restrição: Existência do sensor implica que localização é abrangida

r3=mod.addConstrs((x[i,j]<=y[j]) for i in range(m) for j in range(m))

# Actualizar modelo (boa prática)

mod.update()

# Debug (escrever para ficheiro)

mod.write('Exercício1.lp')

# Otimizar modelo

mod.optimize()

c) Max z = 1.702532755772  m=10 e p=3

Nós sabemos que existem 3 sensores em três locais diferentes (Xij). Visto que as distâncias estão compreendidas entre 0 e 1, faz sentido que com 10 locais a distância mínima seja o Max z obtido.

d) Max z = 16.65717102486 m=300 e p=30

O resultado obtido faz sentido.
Uma vez que o m foi aumentado 30x e o p foi aumentado 10x, faz sentido que a distância ao sensor tenha aumentado, visto que proporcionalmente existem mais pontos do que sensores comparativamente à alinea c).

---

RESOLUÇÃO PERGUNTA 2

a) 

Variáveis de decisão

• [pic 12]
• [pic 13]
• [pic 14]

Objetivo

• [pic 15]

Sujeito a:

• Máximo p sensores

[pic 16]

• Sensor tem que existir para abranger a localização respetiva

[pic 17]

• Todas as localizações abrangidas

[pic 18]

…

[pic 19]

• Condição do w

[pic 20]

[pic 21]

[pic 22]

b) 

P poderá ser 3 ou 30 (para as questões enunciadas), bem como M: 10 ou 300.
E assumindo um alcance total dos sensores.

m=M

 p=P

---

    coord_x = []

    coord_y = []

    coord={}

   

    for i in range(m):

        coord_x.append(random.random())

        coord_y.append(random.random())

        coord[i]=(coord_x[i],coord_y[i])

    ####################################

    # distâncias entre todos os pares de pontos

...