Присвоения Office бинарным целочисленным программированием: основанный на проблеме
В этом примере показано, как решить задачу присвоения бинарным целочисленным программированием с помощью подхода задачи оптимизации. Для основанного на решателе подхода смотрите Присвоения Office Бинарным Целочисленным программированием: основанный на решателе.
Проблема присвоения Office
Вы хотите присвоить шесть человек, Марсело, Рэкеша, Питера, Тома, Марджори и Мэри Энн, в семь офисов. Каждый офис может иметь не больше, чем одного человека, и каждый человек получает точно один офис. Таким образом, будет один пустой офис. Люди могут дать настройки для офисов, и их настройки рассматриваются на основе их старшинства. Чем дольше они были в MathWorks, тем выше старшинство. Некоторые офисы имеют окна, некоторые не делают, и одно окно меньше, чем другие. Кроме того, Питер и Том часто работают совместно, так должен быть в смежных офисах. Марсело и Рэкеш часто работают совместно и должны быть в смежных офисах.
Размещение Office
Офисы 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 года и Rakesh 2 года. Создайте нормированный вектор веса на основе старшинства.
seniority = [9 10 5 3 1.5 2]; weightvector = seniority/sum(seniority);
Народные настройки Office
Настройте матрицу настройки, где строки соответствуют офисам, и столбцы соответствуют людям. Попросите, чтобы каждый человек дал значения для каждого офиса так, чтобы сумма всего их выбора, i.e., их столбец, суммы к 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];
ith элемент вектора настройки человека - то, как высоко они оценивают ith офис. Таким образом объединенная матрица настройки следующие.
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).
Просмотрите решение - кто получил каждый Office?
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 сходившийся к оптимальному решению. Структура output дает информацию о процессе решения, такой как, сколько узлов исследовалось, и разрыв между нижними и верхними границами в переходящем вычислении. В этом случае никакие узлы метода ветвей и границ не были сгенерированы, означая, что задача была решена без шага метода ветвей и границ. Абсолютный разрыв 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'