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