Документация

Проблема присвоения 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

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

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

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

Просмотрите решение - кто получил каждый 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');

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

Для этой проблемы удовлетворенность настроек старшинством максимизируется к значению -fval. exitflag = 1 говорит вам, что intlinprog сходился к оптимальному решению. Выходная структура дает информацию о процессе решения, такой как, сколько узлов исследовалось, и разрыв между нижними и верхними границами в переходящем вычислении. В этом случае никакие узлы метода ветвей и границ не были сгенерированы, означая, что проблема была решена без шага метода ветвей и границ. Разрыв 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).'