В этом примере показано, как решить задачу назначения с помощью двоичного целочисленного программирования с использованием подхода к задаче оптимизации. Для получения информации о подходе на основе решателей см. раздел Назначения Office по двоичному целочисленному программированию: на основе решателей.
Вы хотите назначить шесть человек, Марсело, Ракеш, Питер, Том, Марджори и Мэри Энн, в семь офисов. В каждом офисе может быть не более одного человека, а каждый человек получает ровно один кабинет. Так что будет один пустой офис. Люди могут давать преференции офисам, а их предпочтения рассматриваются исходя из их стажа. Чем дольше они работали в MathWorks, тем выше их стаж. Некоторые офисы имеют окна, некоторые - нет, а одно окно меньше других. Кроме того, Питер и Том часто работают вместе, поэтому должны быть в соседних офисах. Марсело и Ракеш часто работают вместе, и должны находиться в соседних офисах.
Офисы 1, 2, 3 и 4 находятся внутри офисов (без окон). Офисы 5, 6 и 7 имеют окна, но окно в офисе 5 меньше, чем два других. Вот как устроены офисы.
officelist = {'Office 1','Office 2','Office 3','Office 4','Office 5','Office 6','Office 7'};
printofficeassign(officelist)
Вам нужно сформулировать проблему математически. Создайте двоичные переменные, указывающие, занимает ли человек офис. Список имен людей:
namelist = {'Mary Ann','Marjorie','Tom','Peter','Marcelo','Rakesh'};Создание двоичных переменных, индексированных по номеру и имени офиса.
occupy = optimvar('occupy',namelist,officelist,... 'Type','integer','LowerBound',0,'Upperbound',1);
Вы хотите взвесить предпочтения в зависимости от стажа, чтобы чем дольше вы работаете в MathWorks, тем больше ваших предпочтений. Старшинство выглядит следующим образом: Мэри Энн 9 лет, Марджори 10 лет, Том 5 лет, Питер 3 года, Марсело 1,5 года, и Ракеш 2 года. Создайте нормированный весовой вектор на основе стажа.
seniority = [9 10 5 3 1.5 2]; weightvector = seniority/sum(seniority);
Настройте матрицу предпочтений, в которой строки соответствуют офисам, а столбцы - людям. Попросите каждого человека дать значения для каждого офиса, чтобы сумма всех их вариантов, т.е. их колонка, составила 100. Большее число означает, что человек предпочитает офис. Предпочтения каждого пользователя перечислены в векторе столбца.
MaryAnn = [0, 0, 0, 0, 10, 40, 50]; Marjorie = [0, 0, 0, 0, 20, 40, 40]; Tom = [0, 0, 0, 0, 30, 40, 30]; Peter = [1, 3, 3, 3, 10, 40, 40]; Marcelo = [3, 4, 1, 2, 10, 40, 40]; Rakesh = [10, 10, 10, 10, 20, 20, 20];
I-й элемент вектора предпочтений человека - насколько высоко они ценят i-й офис. Таким образом, комбинированная матрица предпочтений выглядит следующим образом.
prefmatrix = [MaryAnn;Marjorie;Tom;Peter;Marcelo;Rakesh];
Весить матрицу предпочтений на weightvector для масштабирования столбцов по старшинству.
PM = diag(weightvector) * prefmatrix;
Цель заключается в максимальном удовлетворении преференций, взвешенных по стажу. Это линейная целевая функция sum(sum(occupy.*PM)).
Создайте задачу оптимизации и включите целевую функцию.
peopleprob = optimproblem('ObjectiveSense','maximize','Objective',sum(sum(occupy.*PM)));
Первый набор ограничений требует, чтобы каждый человек получил ровно один офис, то есть для каждого человека, сумму occupy значения, соответствующие этому человеку, равны единице.
peopleprob.Constraints.constr1 = sum(occupy,2) == 1;
Второй набор ограничений - это неравенство. Эти ограничения указывают на то, что в каждом офисе находится не более одного человека.
peopleprob.Constraints.constr2 = sum(occupy,1) <= 1;
Вы хотите, чтобы Том и Питер не больше одного офиса друг от друга, и то же самое с Марсело и Ракешем.
Установите ограничения, что Том и Питер не более чем на 1 расстояние друг от друга.
peopleprob.Constraints.constrpt1 = occupy('Tom','Office 1') + sum(occupy('Peter',:)) - occupy('Peter','Office 2') <= 1; peopleprob.Constraints.constrpt2 = occupy('Tom','Office 2') + sum(occupy('Peter',:)) - occupy('Peter','Office 1') ... - occupy('Peter','Office 3') - occupy('Peter','Office 5') <= 1; peopleprob.Constraints.constrpt3 = occupy('Tom','Office 3') + sum(occupy('Peter',:)) - occupy('Peter','Office 2') ... - occupy('Peter','Office 4') - occupy('Peter','Office 6') <= 1; peopleprob.Constraints.constrpt4 = occupy('Tom','Office 4') + sum(occupy('Peter',:)) - occupy('Peter','Office 3') ... - occupy('Peter','Office 7') <= 1; peopleprob.Constraints.constrpt5 = occupy('Tom','Office 5') + sum(occupy('Peter',:)) - occupy('Peter','Office 2') ... - occupy('Peter','Office 6') <= 1; peopleprob.Constraints.constrpt6 = occupy('Tom','Office 6') + sum(occupy('Peter',:)) - occupy('Peter','Office 3') ... - occupy('Peter','Office 5') - occupy('Peter','Office 7') <= 1; peopleprob.Constraints.constrpt7 = occupy('Tom','Office 7') + sum(occupy('Peter',:)) - occupy('Peter','Office 4') ... - occupy('Peter','Office 6') <= 1;
Теперь создайте ограничения, которые Марсело и Ракеш не более чем на 1 расстояние друг от друга.
peopleprob.Constraints.constmr1 = occupy('Marcelo','Office 1') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 2') <= 1; peopleprob.Constraints.constmr2 = occupy('Marcelo','Office 2') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 1') ... - occupy('Rakesh','Office 3') - occupy('Rakesh','Office 5') <= 1; peopleprob.Constraints.constmr3 = occupy('Marcelo','Office 3') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 2') ... - occupy('Rakesh','Office 4') - occupy('Rakesh','Office 6') <= 1; peopleprob.Constraints.constmr4 = occupy('Marcelo','Office 4') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 3') ... - occupy('Rakesh','Office 7') <= 1; peopleprob.Constraints.constmr5 = occupy('Marcelo','Office 5') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 2') ... - occupy('Rakesh','Office 6') <= 1; peopleprob.Constraints.constmr6 = occupy('Marcelo','Office 6') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 3') ... - occupy('Rakesh','Office 5') - occupy('Rakesh','Office 7') <= 1; peopleprob.Constraints.constmr7 = occupy('Marcelo','Office 7') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 4') ... - occupy('Rakesh','Office 6') <= 1;
Звонить solve для решения проблемы.
[soln,fval,exitflag,output] = solve(peopleprob);
LP: Optimal objective value is -33.836066. Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).
numOffices = length(officelist); office = cell(numOffices,1); for i=1:numOffices office{i} = find(soln.occupy(:,i)); % people index in office end whoinoffice = officelist; % allocate for i=1:numOffices if isempty(office{i}) whoinoffice{i} = ' empty '; else whoinoffice{i} = namelist(office{i}); end end printofficeassign(whoinoffice); title('Solution of the Office Assignment Problem');
Для этой проблемы удовлетворение преференций по стажу максимизируется до значения fval. Значение exitflag указывает, что solve сходится к оптимальному решению. Структура вывода предоставляет информацию о процессе решения, например, сколько узлов было исследовано, и зазор между нижней и верхней границами в расчете ветвления. В этом случае не было создано узлов, связанных ветвями, что означает, что проблема была решена без шага, связанного ветвями. Абсолютный промежуток равен 0, что означает, что решение является оптимальным, без разницы между внутренними вычисленными нижней и верхней границами целевой функции.
fval,exitflag,output
fval = 33.8361
exitflag = 1
output = struct with fields:
relativegap: 0
absolutegap: 0
numfeaspoints: 1
numnodes: 0
constrviolation: 0
message: 'Optimal solution found.↵↵Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).'
solver: 'intlinprog'