Otimização de softwares antivírus

Segue um pequeno exercício de otimização.

Você está numa empresa brasileira de alcance nacional, responsável pela aquisição de softwares antivírus para a empresa toda.

Há 30 softwares possíveis (numerados de 1 a 30) e 15 ameaças mapeadas (denominadas de A a O).

Cada software é homologado a prestar somente alguns serviços, e isso é assinalado com o valor 1 na tabela acima.

Cada software tem um custo para executar o pacote de serviços a que ele está homologado, dado pela tabela a seguir.

Quando você contrata o software, ele fornece toda a proteção do pacote. Não é possível contratar apenas um pedaço do software.

Além disso, há algumas restrições adicionais:

• Software 4 é incompatível com Software 25, somente um dos dois deve ser contratado
• Software 12 é incompatível com Software 16
• Software 20 é incompatível com Software 30
• Software 11 é incompatível com Software 12
• O Software 21 deve ser contratado, por motivos políticos

Pergunta: Quais os softwares a serem contratados, de modo que todas as ameaças estejam cobertas, todas as restrições sejam atendidas e que o custo total de contratação seja o mínimo possível?

— — -

Resolução

Vamos separar o range (G39:G68) para a variável de decisão. É uma variável binária: 1 para indicar que vamos comprar o software, 0 para indicar que não.

A função objetivo (na célula M38) será dada pelo somarproduto da variável de decisão e o custo de cada alternativa.

Nas linhas de C35:Q35, vamos fazer a conta de quantos softwares estão cobrindo a ameaça.

Para modelar a restrição de incompatibilidade:

Software 4 é incompatível com software 25, equivale a dizer que não podemos comprar ambos os softwares. Pela variável de decisão ser binária, isso quer dizer que a soma deve ser menor ou igual a 1.

O mesmo vale para as demais restrições do tipo.

O software 21 ser obrigatório é indicado pela restrição de que ele deve ser igual a 1.

Vamos utilizar o solver do Excel para resolução.

$C$35:$Q$35 >= 1 (Todas as ameaças devem ser cobertas por algum software) $G$39:$G$68 = binário (Variáveis de decisão binárias) $L$44:$L$47 <= 1 (Softwares incompatíveis) $L$48 = 1 (Software obrigatório)

Resolvendo, temos a função objetivo de 138.000.

— — — —

Para formulação em Pyomo

# Definição dos dados num_softwares = 30 num_ameacas = 15 # Matrizes de cobertura e custos

[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],

[1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],

[0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0],

[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],

[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],

[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],

[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],

[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],

[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],

[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],

[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],

[0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],

[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],

]

custos = [

18000, 4000, 6000, 22000, 38000, 14000, 4000, 16000, 28000, 10000,

20000, 12000, 4000, 20000, 20000, 6000, 18000, 20000, 8000, 14000,

20000, 18000, 8000, 18000, 36000, 4000, 12000, 30000, 30000, 34000

]

# Conflitos

conflitos = [ (4, 25), (12, 16), (20, 30), (11, 12)]

import pyomo.environ as pyo

model = pyo.ConcreteModel()

#Cria ranges para usar no modelo

model.softwares = range(num_softwares)

model.ameacas= range(num_ameacas)

model.var_decisao = pyo.Var(model.softwares, within = pyo.Binary)

#Definição da Função Objetivo

def funcao_obj(model):

return sum(model.var_decisao[i]*custos[i] for i in model.softwares)

model.objetivo = pyo.Objective(expr = funcao_obj, sense = pyo.minimize)

model.constraints = pyo.ConstraintList()

#Restrição de cobertura das ameaças

for ameaca in model.ameacas:

model.constraints.add(sum(model.var_decisao[i]*cobertura[i][ameaca] for i in model.softwares) >=1)

#Restrição conflito de softwares

for conflito in conflitos:

model.constraints.add(model.var_decisao[conflito[0]-1] + model.var_decisao[conflito[1]-1] <=1)

#Restrição Software_21_Obrigatorio

model.constraints.add(model.var_decisao[21–1]==1)

#Roda o solver

#Trocar pelo solver que estiver disponível

solver = pyo.SolverFactory(‘cbc’, executable = “C:\\CBC\\cbc.exe”)

result = solver.solve(model)

#Print de resultados

print(result)

#Print do modelo (opcional)

#model.pprint()

#Print dos softwares escolhidos

for i in list(model.var_decisao):

print (i+1, “: “, model.var_decisao[i].value)

Este é um caso conhecido na literaturacomo “Problema da Cobertura”.

Originally published at https://ideiasesquecidas.com on June 14, 2024.