Please enable JavaScript.
Coggle requires JavaScript to display documents.
Modelagem de Otimização (5/6) - Coggle Diagram
Modelagem de Otimização (5/6)
Problema de Agrupamento Equilibrado
Problema Gerencial:
Agrupar funcionários de forma equilibrada por afinidade.
Agrupamento não equilibrado
|C| != |V\C|
Agrupamento equilibrado
|C| ~ |V\C|
Dados do problema
V
Conjunto de funcionários
(i,j)
par de funcionarios E V
wijj
afinidade E [-1, 1]
yi
1 se está em C e 0 caso contrário (varíavel binária)
Problema de Otimização
Função objetivo
Irá maximizar a harmonia dos conjuntos de funcionários
Sigma (i E V) Sigma (j>i) wij(yi*yj + (1-yi)(1-yj))
Restrições
Equilíbrio entre conjuntos
|C| = floor(V/2)
Restrição binária
yi E {0,1}
Alternativa: yi(1-yi) = 0
É um problema binário quadrático (não-linear)
O problema poderá ser atacado como um problema de programação não-linear inteira, caso a restrição binária seja explicita ou programação não-linear caso seja implicita na equação
yi(1-yi) =0
Linearização do Problema
Representar relação quadrática por variável auxiliar uij
Adicionar restrições para garantir que uij =0 caso yi ou yj =0 .
uij < yi, i, j E V, j > i
uij < yj, i, j E V, j > i
Adicionar restrições para garantir que uij =1 caso yi = yj =1
uij >= yi + yj -1, i,j E V, j>i
'
https://www.youtube.com/watch?v=WGn0fz-wx4U&t=1504s