Присвоения 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

Настройте матрицу настройки, где строки соответствуют офисам, и столбцы соответствуют людям. Попросите, чтобы каждый человек дал значения для каждого офиса так, чтобы сумма всего их выбора, т.е. их столбца, суммировала к 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 сходился к оптимальному решению. Выходная структура дает информацию о процессе решения, такой как, сколько узлов исследовалось, и разрыв между нижними и верхними границами в переходящем вычислении. В этом случае никакие узлы метода ветвей и границ не были сгенерированы, означая, что проблема была решена без шага метода ветвей и границ. Абсолютный разрыв 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'

Для просмотра документации необходимо авторизоваться на сайте