Задача группового присвоения с методами оптимизации - PullRequest
Новая
       23

Задача группового присвоения с методами оптимизации

0 голосов
/ 29 октября 2018

Компания организует семинар, в котором примут участие 60 слушателей. Компания планирует разделить участников на 10 групп по 6 стажеров. Каждого из стажеров заранее попросили выбрать 5 других стажеров, с которыми они хотели бы работать. И каждый из пяти взвешен одинаково. Проблема в том, как мы можем распределить участников по группам так, чтобы общее удовлетворение могло быть оптимизировано.

1 Ответ

0 голосов
/ 31 октября 2018

позвольте мне привести небольшой пример с CPO в CPLEX в OPL: 

//There’s a company organising a seminar, where 60 trainees will attend. 
//The company plans to divide the participants into 10 groups, each of 6 trainees. 
//Each of the trainees was asked beforehand to choose 5 other trainees they would like to work with. 
//And each of the five is weighted equally. 
//The problem is how we can assign the participants into groups so that the total satisfaction could to optimised. 

using CP;

execute
{
cp.param.timelimit=20;
}

int nbTrainees=60;
int nbGroups=10;
int nbWishes=5;
int sizeGroup=nbTrainees div nbGroups;



range trainees=1..nbTrainees;
range groups=1..nbGroups;
range likes=1..nbWishes;

// let us start with the nbWishes next trainees
int wishes[t in trainees][w in likes]=(t+w-1) mod nbTrainees+1;

assert forall(t in trainees,w in likes) wishes[t][w] in trainees;
assert forall(t in trainees,w in likes) wishes[t][w] != t;

// a gievn trainee belongs to a given group ?
dvar boolean x[trainees][groups];

dvar int satisfaction;

maximize satisfaction;
subject to
{

// trainees belong to one and only one group
forall(t in trainees) sum(g in groups) x[t][g]==1;

// group size
forall(g in groups) sum(t in trainees) x[t][g]==sizeGroup;

// satisfaction formula
satisfaction==sum(t in trainees,w in likes,g in groups) ((x[t][g]*x[wishes[t][w]][g]));

}

{int} team[g in groups]={ i | i in trainees : x[i][g]==1};

execute
{
writeln(team);
}
...