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