Назначения офиса двоичным целым числом: основанные на проблеме
Этот пример показывает, как решить задачу назначения путем двоичного целочисленного программирования с помощью подхода задачи оптимизации. Для основанного на решателе подхода смотрите Назначения офиса Двоичным Целым Программированием: Основанные на решателе.
Проблема назначения офиса
Вы хотите назначить шесть человек, Марсело, Ракеш, Питер, Том, Марджори и Мэри Энн, в семь офисов. Каждый офис может иметь не более одного человека, и каждый человек получает только один офис. Так что будет один пустой офис. Люди могут отдавать настройки офисам, а их настройки рассматриваются исходя из их стажа работы. Чем дольше они были в 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 сходился к оптимальному решению. Структура 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'