Atividade 8 - Bruno Sousa dos Santos

Prévia do material em texto

Disciplina: Otimização (ENG574) 
Professor: Karcius Assis 
Aluno: Bruno Sousa dos Santos 
Data: 13/05/2021 
 
Atividade VIII – Relatório 
 
Diferentemente dos problemas de localização, nos problemas de cobertura várias instalações 
oferecem serviços sobrepostos a várias localidades. O objetivo é determinar o número mínimo de 
instalações que cobrirão (isto é, satisfarão as necessidades) cada localidade. 
 
Problema 1. Para promover a segurança no campus o departamento de segurança da UFBA iniciou 
um processo de instalação de telefones de emergência em locais selecionados. O departamento quer 
instalar o número mínimo de telefones, contanto que cada uma das ruas principais do campus seja 
atendida por no mínimo um telefone. A Figura abaixo mapeia as ruas principais (A a K) do campus. 
Defina-se xj =1 se um telefone for instalado no local j e xj =0 caso contrário. As restrições do problema 
requerem a instalação de no mínimo um telefone em cada uma das 11 ruas (A a K). Baseado nessas 
informações construa o modelo matemático do problema. Após isso construa o modelo na linguagem 
AMPL e ache a solução ótima (quantos telefones instalados e em que localidades). Note que é lógico 
colocar telefones em cruzamentos de ruas (ver figura) de modo que cada telefone atenda no mínimo 
duas ruas. 
 
Formulação conforme PDF_anexo_At08. 
 
 
 
Código AMPL: 
#Atividade 08 Q1 
 
param t > 0 integer; 
param r > 0 integer; 
 
set C := 1..t; 
set Q := 1..r; 
 
var x{j in C} binary; 
var y{i in Q} binary; 
var f{j in C, i in Q} integer; 
 
minimize Telefone: sum{j in C} x[j]; 
 
 
 
subj to res1:x[1]+x[2]>=1; 
subj to res2:x[2]+x[3]>=1; 
subj to res3:x[4]+x[5]>=1; 
subj to res4:x[7]+x[8]>=1; 
subj to res5:x[6]+x[7]>=1; 
subj to res6:x[6]+x[2]>=1; 
subj to res7:x[1]+x[6]>=1; 
subj to res8:x[7]+x[4]>=1; 
subj to res9:x[2]+x[4]>=1; 
subj to res10:x[5]+x[8]>=1; 
subj to res11:x[5]+x[3]>=1; 
data; 
 
param t:=8; 
 
end 
 
Resultados Obtidos: 
O número mínimo de telefones que atenderá todas as restrições é 4. 
 
 
 
Os tesouros do rei Tut estão em exposição em um museu em Nova Orleans. O layout do museu é 
mostrado na figura abaixo, com as diferentes salas ligadas por portas abertas. Um guarda postado 
em uma porta pode vigiar duas salas adjacentes. O museu quer garantir a presença de guarda em 
todas as salas usando menor número de pessoas. Formule o problema, faça o código no AMPL e 
encontre a solução ótima. Formulação conforme PDF_anexo_At08. 
 
 
 
Código AMPL: 
#Atividade 08 Q2 
 
param t > 0 integer; 
param r > 0 integer; 
 
set C := 1..t; 
set Q := 1..r; 
 
var x{j in C, i in Q} binary; 
 
 
minimize Guardas: sum{j in C, i in Q} x[i,j]; 
 
 
subj to res1:x[1,3]+x[1,2]>=1; 
subj to res2:x[1,2]+x[2,5]>=1; 
subj to res3:x[1,3]+x[3,4]>=1; 
subj to res4:x[3,4]+x[4,5]>=1; 
subj to res5:x[4,5]+x[2,5]+x[5,8]+x[5,9]>=1; 
subj to res6:x[6,7]>=1; 
subj to res7:x[6,7]+x[7,8]>=1; 
subj to res8:x[7,8]+x[5,8]>=1; 
 
 
data; 
 
param t:=9; 
param r:=9; 
end 
 
Resultados Obtidos: 
 
 
O número mínimo de guardas a cuidar do Museu é 4, considerando a entrada do mesmo.