Проблема присвоения Office

Вы хотите присвоить шесть человек, Марсело, Рэкеша, Питера, Тома, Марджори и Мэри Энн, в семь офисов. Каждый офис может иметь не больше, чем одного человека, и каждый человек получает точно один офис. Таким образом, будет один пустой офис. Люди могут дать настройки для офисов, и их настройки рассматриваются на основе их старшинства. Чем дольше они были в MathWorks, тем выше старшинство. Некоторые офисы имеют окна, некоторые не делают, и одно окно меньше, чем другие. Кроме того, Питер и Том часто работают совместно, так должен быть в смежных офисах. Марсело и Рэкеш часто работают совместно и должны быть в смежных офисах.

Размещение Office

Офисы 1, 2, 3, и 4 являются внутренними офисами (никакие окна). Офисы 5, 6, и 7 имеют окна, но окно в офисе 5 меньше, чем другие два. Вот то, как офисы располагаются.

name = {'Office 1','Office 2','Office 3','Office 4','Office 5','Office 6','Office 7'};
printofficeassign(name)

Формулировка задачи

Необходимо сформулировать проблему математически. Во-первых, выберите что каждый элемент вашей переменной x решения представляет в задаче. Поскольку это - бинарная целочисленная задача, хороший выбор состоит в том, что каждый элемент представляет человека, присвоенного офису. Если человек присвоен офису, переменная имеет значение 1. Если человек не присвоен офису, переменная имеет значение 0. Люди номера можно следующим образом:

x вектор. Элементы x(1) к x(7) соответствуйте Мэри Энн, присваиваемой офису 1, офису 2, и т.д., офису 7. Следующие семь элементов соответствуют Марджори, присваиваемой этим семи офисам и т.д. В целом, x вектор имеет 42 элемента, поскольку шесть человек присвоены семи офисам.

Старшинство

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

PM = prefmatrix * diag(weightvector);
c = PM(:);

Целевая функция

Цель состоит в том, чтобы максимизировать удовлетворенность настроек, взвешенных старшинством. Это - линейная целевая функция

max c'*x

или эквивалентно

min -c'*x.

Ограничения

Первый набор ограничений требует, чтобы каждый человек получил точно один офис, который является для каждого человека, суммы x значения, соответствующие тому человеку, точно один. Например, поскольку Марджори является вторым человеком, это означает тот sum(x(8:14))=1. Представляйте эти линейные ограничения в матрице равенства Aeq и векторный beq, где Aeq*x = beq, путем создания соответствующих матриц. Матричный Aeq состоит из единиц и нулей. Например, вторая строка Aeq будет соответствовать Марджори, получающей один офис, таким образом, строка выглядит так:

0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 ... 0 0 0

Существуют семь 1 с в столбцах 8 - 14 и 0s в другом месте. Затем Aeq(2,:)*x = 1 эквивалентно sum(x(8:14)) = 1.

numOffices = 7;
numPeople = 6;
numDim = numOffices * numPeople;
onesvector = ones(1,numOffices);

Каждая строка Aeq соответствует одному человеку.

Aeq = blkdiag(onesvector,onesvector,onesvector,onesvector, ...
    onesvector,onesvector);
beq = ones(numPeople,1);

Второй набор ограничений является неравенствами. Эти ограничения указывают, что каждый офис имеет не больше, чем одного человека в нем, т.е. каждый офис имеет одного человека в нем или пуст. Создайте матричный A и векторный b таким образом, что A*x <= b получать эти ограничения. Каждая строка A и b соответствует офису и таким образом, строка 1 соответствует людям, присвоенным офису 1. На этот раз строки имеют этот тип шаблона для строки 1:

1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 ... 1 0 0 0 0 0 0

Каждая строка после того, как это подобно, но переключено (циркулярный) направо одним местом. Например, строка 3 соответствует офису 3 и говорит тот A(3,:)*x <= 1т.е. . офис 3 не может иметь больше чем одного человека в нем.

A = repmat(eye(numOffices),1,numPeople);
b = ones(numOffices,1);

Следующий набор ограничений является также неравенствами, поэтому добавьте их в матричный A и векторный b, которые уже содержат неравенства сверху. Вы хотите Тома и Питера не больше, чем один офис далеко друг от друга и того же самого с Марсело и Рэкешем. Во-первых, создайте матрицу расстояния офисов на основе их физических местоположений и использующий аппроксимированные манхэттенские расстояния. Это - симметрическая матрица.

D = zeros(numOffices);

Настройте правую верхнюю половину матрицы.

D(1,2:end) = [1 2 3 2 3 4];
D(2,3:end) = [1 2 1 2 3];
D(3,4:end) = [1 2 1 2];
D(4,5:end) = [3 2 1];
D(5,6:end) = [1 2];
D(6,end)   = 1;

Нижняя левая половина совпадает с верхним правым углом.

D = triu(D)' + D;

Найдите офисы, которые являются больше чем одной единицей расстояния далеко.

[officeA,officeB] = find(D > 1);
numPairs = length(officeA)

numPairs = 26

Это находит numPairs пары офисов, которые не смежны. Для этих пар, если Том занимает один офис в паре, то Питер не может занять другой офис в паре. Если бы он сделал, они не были бы смежны. То же самое верно для Марсело и Рэкеша. Это дает 2*numPairs больше ограничений неравенства, которые вы добавляете в A и b.

Добавьте достаточно строк в A вмещать эти ограничения.

numrows = 2*numPairs + numOffices; 
A((numOffices+1):numrows, 1:numDim) = zeros(2*numPairs,numDim);

Для каждой пары офисов в numPairs, для x(i) это соответствует Тому в officeA и для x(j) это соответствует Питеру в OfficeB,

x(i) + x(j) <= 1.

Это означает, что или Том или Питер могут занять один из этих офисов, но они оба не могут.

Том является человеком 3, и Питер является человеком 4.

tom = 3;
peter = 4;

Марсело является человеком 5, и Rakesh является человеком 6.

marcelo = 5;
rakesh = 6;

Следующие анонимные функции возвращают индекс в соответствии x Тому, Питеру, Марсело и Рэкешу соответственно в офисе i.

tom_index=@(officenum) (tom-1)*numOffices+officenum;
peter_index=@(officenum) (peter-1)*numOffices+officenum;
marcelo_index=@(officenum) (marcelo-1)*numOffices+officenum;
rakesh_index=@(officenum) (rakesh-1)*numOffices+officenum;

for i = 1:numPairs    
    tomInOfficeA = tom_index(officeA(i));
    peterInOfficeB = peter_index(officeB(i));
    A(i+numOffices, [tomInOfficeA, peterInOfficeB]) = 1;
   
    % Repeat for Marcelo and Rakesh, adding more rows to A and b.
    marceloInOfficeA = marcelo_index(officeA(i));
    rakeshInOfficeB = rakesh_index(officeB(i));
    A(i+numPairs+numOffices, [marceloInOfficeA, rakeshInOfficeB]) = 1;
end
b(numOffices+1:numOffices+2*numPairs) = ones(2*numPairs,1);

Решите Используя intlinprog

Формулировка задачи состоит из линейной целевой функции

min -c'*x

подвергните линейным ограничениям

Aeq*x = beq

A*x <= b

весь двоичный файл переменных

Вы уже сделали AB, Aeq, и beq записи. Теперь установите целевую функцию.

f = -c;

Гарантировать, что переменные являются бинарными, помещенными нижними границами 0, верхними границами 1, и устанавливают intvars представлять все переменные.

lb = zeros(size(f));
ub = lb + 1;
intvars = 1:length(f);

Вызовите intlinprog решать задачу.

[x,fval,exitflag,output] = intlinprog(f,intvars,A,b,Aeq,beq,lb,ub);

LP:                Optimal objective value is -33.868852.                                           

Cut Generation:    Applied 1 Gomory cut.                                                            
                   Lower bound is -33.836066.                                                       
                   Relative gap is 0.00%.                                                          


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?

numPeople = 7; office = cell(numPeople,1);
for i=1:numPeople
    office{i} = find(x(i:numPeople:end)); % people index in office
end

people = {'Mary Ann', 'Marjorie','  Tom   ',' Peter  ','Marcelo ',' Rakesh '};
for i=1:numPeople
    if isempty(office{i})
        name{i} = ' empty  ';
    else
        name{i} = people(office{i});
    end
end

printofficeassign(name);
title('Solution of the Office Assignment Problem');

Качество решения

Для этой проблемы удовлетворенность настроек старшинством максимизируется к значению -fvalexitflag = 1 говорит вам тот intlinprog сходившийся к оптимальному решению. Структура 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).'