Проблема назначения офиса

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

Размещение офиса

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

В столбцах с 8 по 14 имеется семь 1с, а в других - 0. Затем 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, а Ракеш - человек 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

все переменные двоичные

Вы уже сделали A, b, 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).

Просмотр решения -- Кто получил каждый офис?

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');

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

Для этой проблемы удовлетворение настроек по стажу максимизируется до значения -fval. exitflag = 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).'