通过二元整数规划进行办公室分配：基于问题
此示例说明如何使用优化问题方法通过二元整数规划解决分配问题。有关基于求解器的方法，请参阅通过二元整数规划进行办公室分配：基于求解器。
办公室分配问题
您想要将 Marcelo、Rakesh、Peter、Tom、Marjorie 和 Mary Ann 六个人分配到七间办公室。每间办公室最多只能有一个人，并且每个人只能有一间办公室。因此将会有一间空办公室。人们可以提出自己对办公室的偏好，分配时会结合每个人的资历来考虑他们的偏好。他们在 MathWorks 工作的时间越长，资历就越高。有些办公室有窗户，有些没有，而且有一扇窗户比其他的窗户小。此外，Peter 和 Tom 经常一起工作，因此应该在相邻的办公室。Marcelo 和 Rakesh 经常一起工作，应该在相邻的办公室。
办公室布局
办公室 1、2、3 和 4 属于内区办公室（没有窗户）。5、6 和 7 号办公室都有窗户，但 5 号办公室的窗户比其他两个办公室的窗户小。办公室的布置如下。
officelist = ["Office 1","Office 2","Office 3","Office 4","Office 5","Office 6","Office 7"]; printofficeassign(officelist)
问题表示
您需要用数学方法表示这个问题。创建二元变量来指示一个人是否占用办公室。人员名单如下
people = ["Mary Ann","Marjorie","Tom","Peter","Marcelo","Rakesh"];
创建按办公室编号和名称索引的二元变量。
occupy = optimvar("occupy",people,officelist,... Type="integer",LowerBound=0,Upperbound=1);
资历
您希望根据资历对偏好进行加权。这样，在 MathWorks 工作的时间越长，偏好的权重就越高。资历如下：Mary Ann 9 年、Marjorie 10 年、Tom 5 年、Peter 3 年、Marcelo 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];
一个人的偏好向量的第 i 个元素表示他们对第 i 个办公室的偏好程度。因此，合并后的偏好矩阵如下：
prefmatrix = [MaryAnn;Marjorie;Tom;Peter;Marcelo;Rakesh];
通过 weightvector 对偏好矩阵进行加权，以按资历缩放列。
PM = diag(weightvector) * prefmatrix;
目标函数
目标是最大限度地满足按资历加权的偏好。这是线性目标函数 sum(sum(occupy.*PM))。
创建一个优化问题并加入目标函数。
peopleprob = optimproblem(ObjectiveSense="maximize",Objective=sum(sum(occupy.*PM)));约束
第一组约束要求每个人恰好分得一间办公室，也就是说，对于每个人来说，与其对应的 occupy 值的总和恰好为 1。
peopleprob.Constraints.constr1 = sum(occupy,2) == 1;
第二组约束是不等式。这些约束规定每个办公室最多只能有一个人。
peopleprob.Constraints.constr2 = sum(occupy,1) <= 1;
您希望 Tom 和 Peter 之间的办公室距离不超过一个办公室，Marcelo 和 Rakesh 之间的办公室距离也同样如此。
设定约束：Tom 和 Peter 之间的距离不超过 1。
peopleprob.Constraints.constrpt1 = occupy("Tom","Office 1") + sum(occupy("Peter",:)) - occupy("Peter","Office 2") <= 1; peopleprob.Constraints.constrpt2 = occupy("Tom","Office 2") + sum(occupy("Peter",:)) - occupy("Peter","Office 1") ... - occupy("Peter","Office 3") - occupy("Peter","Office 5") <= 1; peopleprob.Constraints.constrpt3 = occupy("Tom","Office 3") + sum(occupy("Peter",:)) - occupy("Peter","Office 2") ... - occupy("Peter","Office 4") - occupy("Peter","Office 6") <= 1; peopleprob.Constraints.constrpt4 = occupy("Tom","Office 4") + sum(occupy("Peter",:)) - occupy("Peter","Office 3") ... - occupy("Peter","Office 7") <= 1; peopleprob.Constraints.constrpt5 = occupy("Tom","Office 5") + sum(occupy("Peter",:)) - occupy("Peter","Office 2") ... - occupy("Peter","Office 6") <= 1; peopleprob.Constraints.constrpt6 = occupy("Tom","Office 6") + sum(occupy("Peter",:)) - occupy("Peter","Office 3") ... - occupy("Peter","Office 5") - occupy("Peter","Office 7") <= 1; peopleprob.Constraints.constrpt7 = occupy("Tom","Office 7") + sum(occupy("Peter",:)) - occupy("Peter","Office 4") ... - occupy("Peter","Office 6") <= 1;
现在创建约束，使得 Marcelo 和 Rakesh 之间的距离不超过 1。
peopleprob.Constraints.constmr1 = occupy("Marcelo","Office 1") + sum(occupy("Rakesh",:)) - occupy("Rakesh","Office 2") <= 1; peopleprob.Constraints.constmr2 = occupy("Marcelo","Office 2") + sum(occupy("Rakesh",:)) - occupy("Rakesh","Office 1") ... - occupy("Rakesh","Office 3") - occupy("Rakesh","Office 5") <= 1; peopleprob.Constraints.constmr3 = occupy("Marcelo","Office 3") + sum(occupy("Rakesh",:)) - occupy("Rakesh","Office 2") ... - occupy("Rakesh","Office 4") - occupy("Rakesh","Office 6") <= 1; peopleprob.Constraints.constmr4 = occupy("Marcelo","Office 4") + sum(occupy("Rakesh",:)) - occupy("Rakesh","Office 3") ... - occupy("Rakesh","Office 7") <= 1; peopleprob.Constraints.constmr5 = occupy("Marcelo","Office 5") + sum(occupy("Rakesh",:)) - occupy("Rakesh","Office 2") ... - occupy("Rakesh","Office 6") <= 1; peopleprob.Constraints.constmr6 = occupy("Marcelo","Office 6") + sum(occupy("Rakesh",:)) - occupy("Rakesh","Office 3") ... - occupy("Rakesh","Office 5") - occupy("Rakesh","Office 7") <= 1; peopleprob.Constraints.constmr7 = occupy("Marcelo","Office 7") + sum(occupy("Rakesh",:)) - occupy("Rakesh","Office 4") ... - occupy("Rakesh","Office 6") <= 1;
求解分配问题
调用 solve 以求解问题。
[soln,fval,exitflag,output] = solve(peopleprob);
Solving problem using intlinprog.
Running HiGHS 1.11.0: Copyright (c) 2025 HiGHS under MIT licence terms
MIP has 27 rows; 42 cols; 164 nonzeros; 42 integer variables (42 binary)
Coefficient ranges:
Matrix [1e+00, 1e+00]
Cost [5e-02, 1e+01]
Bound [1e+00, 1e+00]
RHS [1e+00, 1e+00]
Presolving model
27 rows, 42 cols, 164 nonzeros 0s
27 rows, 42 cols, 174 nonzeros 0s
Objective function is integral with scale 61
Solving MIP model with:
27 rows
42 cols (42 binary, 0 integer, 0 implied int., 0 continuous, 0 domain fixed)
174 nonzeros
Src: B => Branching; C => Central rounding; F => Feasibility pump; J => Feasibility jump;
H => Heuristic; L => Sub-MIP; P => Empty MIP; R => Randomized rounding; Z => ZI Round;
I => Shifting; S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution;
z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
J 0 0 0 0.00% inf 22.96721311 Large 0 0 0 0 0.0s
T 0 0 0 0.00% 48.19672131 33.83606557 42.44% 0 0 0 17 0.0s
1 0 1 100.00% 33.83606557 33.83606557 0.00% 0 0 0 17 0.0s
Solving report
Status Optimal
Primal bound 33.8360655738
Dual bound 33.8360655738
Gap 0% (tolerance: 0.01%)
P-D integral 0.00293781929689
Solution status feasible
33.8360655738 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.02 (total)
0.00 (presolve)
0.00 (solve)
0.00 (postsolve)
Max sub-MIP depth 0
Nodes 1
Repair LPs 0 (0 feasible; 0 iterations)
LP iterations 17 (total)
0 (strong br.)
0 (separation)
0 (heuristics)
Optimal solution found.
Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06.
查看解 - 哪个人分得了哪间办公室？
numOffices = length(officelist); office = cell(numOffices,1); for i=1:numOffices office{i} = find(soln.occupy(:,i)); % people index in office end whoinoffice = officelist; % allocate for i=1:numOffices if isempty(office{i}) whoinoffice(i) = " empty "; else whoinoffice(i) = people(office{i}); end end printofficeassign(whoinoffice); title("Solution of the Office Assignment Problem");
解质量
对于这个问题，通过最大化 fval 的值来满足按资历排序的偏好。exitflag 的值指示 solve 收敛到一个最优解。输出结构给出了求解过程的信息，例如探索了多少个节点，以及分支计算中下界和上界之间的差距。在这种情况下，没有生成分支定界节点，这意味着问题无需分支定界步骤即可解决。绝对差距为 0，表示解是最优的，内部计算的目标函数的下界和上界之间没有差异。
fval,exitflag,output
fval = 33.8361
exitflag =
OptimalSolution
output = struct with fields:
relativegap: 0
absolutegap: 0
numfeaspoints: 2
numnodes: 1
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 = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06.'
solver: 'intlinprog'
