基于二进制整数规划的办公室分配：基于问题的

打开实时脚本

此示例演示如何使用优化问题方法通过二进制整数规划解决分配问题。有关基于解算器的方法，请参阅基于二进制整数规划的办公室分配：基于解算器.

办公室分配问题

您希望将六个人，马塞洛、拉凯什、彼得、汤姆、马乔里和玛丽·安分配到七个办公室。每个办公室最多只能有一个人，每个人正好有一个办公室。因此将有一个空办公室。人们可以为办公室提供首选项，并根据他们的资历考虑他们的首选项。他们工作的时间越长我在MathWorks工作过，资历越高。有些办公室有窗户，有些没有，一扇窗户比另一扇小。此外，彼得和汤姆经常一起工作，所以应该在相邻的办公室。马塞洛和拉凯什经常一起工作，应该在相邻的办公室。

办公室布局

办公室1、2、3和4在办公室内部（没有窗户）。办公室5、6和7有窗户，但办公室5的窗户比其他两个小。以下是办公室的布置方式。

公职人员={“办公室1”,“办公室2”,“办公室3”,“办公室4”,“办公室5”,“办公室6”,“办公室7”}；PrintOfficeAsign（办公室列表）

问题表述

你需要用数学的方法来描述这个问题。创建二进制变量来指示一个人是否占用办公室。姓名列表如下所示

姓名列表={“玛丽·安”,“马乔里”,“汤姆”,“彼得”,“马塞洛”,“拉凯什”};

创建按办公室编号和名称索引的二进制变量。

占领=最优值(“占领”，姓名列表，公职人员，...“类型”,“整数”,“LowerBound”,0,“上限”,1);

年长

您希望根据资历对偏好进行加权，以便您在MathWorks工作的时间越长，您的偏好就越重要。资历如下：Mary Ann 9岁、Marjorie 10岁、Tom 5岁、Peter 3岁、Marcelo 1.5岁和Rakesh 2岁。创建基于资历的标准化权重向量。

资历=[9 10 5 3 1.5 2]；权重向量=资历/总和（资历）；

人民的办公室偏好

设置一个偏好矩阵，其中行对应于办公室，列对应于人。要求每个人为每个办公室提供值，以便他们所有选择（即他们的列）的总和为100。数字越大，表示该人越喜欢办公室。每个人的偏好列在列向量中。

玛丽安=[0,0,0,0,10,40,50]；马乔里=[0,0,0,0,20,40,40]；汤姆=[0,0,0,0,30,40,30]；彼得=[1,3,3,10,40,40]；马塞洛=[3,4,1,2,10,40,40]；拉凯什=[10,10,10,20,20]；

个人偏好向量的第i个元素是他们对第i个职位的重视程度。因此，组合偏好矩阵如下所示。

prefmatrix=[MaryAnn；Marjorie；Tom；Peter；Marcelo；Rakesh]；

按权重计算偏好矩阵的权重权重向量按资历缩放列。

PM=diag（权重向量）*矩阵；

目标函数

目标是最大限度地满足由资历加权的偏好。这是线性目标函数总和（总和（占*分））.

创建一个优化问题并包含目标函数。

peopleprob=优化问题(“客观感觉”,“最大化”,“目标”，sum（sum（占据.*PM））；

约束条件

第一组约束要求每个人只得到一个办公室，也就是说，对于每个人，每个办公室的占据与此人对应的值正好是一。

peopleprob.Constraints.Constraint1=总和（占用，2）==1；

第二组约束是不等式。这些约束规定每个办公室不超过一个人。

peopleprob.Constraints.Construct2=总和（占用，1）<=1；

你希望汤姆和彼得彼此之间的距离不超过一个办公室，马塞洛和拉凯什也一样。

设置Tom和Peter之间的距离不超过1的约束。

peopleprob.Constraints.constrpt1=占用(“汤姆”,“办公室1”)+和（占）(“彼得”，：）-占领(“彼得”,“办公室2”)<=1；peopleprob.Constraints.constrpt2=占用(“汤姆”,“办公室2”)+和（占）(“彼得”，：）-占领(“彼得”,“办公室1”)...-占据(“彼得”,“办公室3”)-占领(“彼得”,“办公室5”)<=1；peopleprob.Constraints.constrpt3=占用(“汤姆”,“办公室3”)+和（占）(“彼得”，：）-占领(“彼得”,“办公室2”)...-占据(“彼得”,“办公室4”)-占领(“彼得”,“办公室6”) <= 1; peopleprob.Constraints.constrpt4=占用(“汤姆”,“办公室4”)+和（占）(“彼得”，：）-占领(“彼得”,“办公室3”)...-占据(“彼得”,“办公室7”) <= 1; peopleprob.Constraints.constrpt5=占用(“汤姆”,“办公室5”)+和（占）(“彼得”，：）-占领(“彼得”,“办公室2”)...-占据(“彼得”,“办公室6”) <= 1; peopleprob.Constraints.constrpt6=占用(“汤姆”,“办公室6”)+和（占）(“彼得”，：）-占领(“彼得”,“办公室3”)...-占据(“彼得”,“办公室5”)-占领(“彼得”,“办公室7”) <= 1; peopleprob.Constraints.constrpt7=占用(“汤姆”,“办公室7”)+和（占）(“彼得”，：）-占领(“彼得”,“办公室4”)...-占据(“彼得”,“办公室6”) <= 1;

现在创建约束，使Marcelo和Rakesh彼此之间的距离不超过1。

peopleprob.Constraints.constmr1=占用(“马塞洛”,“办公室1”)+和（占）(“拉凯什”，：）-占领(“拉凯什”,“办公室2”) <= 1; peopleprob.Constraints.constmr2=占用(“马塞洛”,“办公室2”)+和（占）(“拉凯什”，：）-占领(“拉凯什”,“办公室1”)...-占据(“拉凯什”,“办公室3”)-占领(“拉凯什”,“办公室5”) <= 1; peopleprob.Constraints.constmr3=占用(“马塞洛”,“办公室3”)+和（占）(“拉凯什”，：）-占领(“拉凯什”,“办公室2”)...-占据(“拉凯什”,“办公室4”)-占领(“拉凯什”,“办公室6”) <= 1; peopleprob.Constraints.constmr4=占用(“马塞洛”,“办公室4”)+和（占）(“拉凯什”，：）-占领(“拉凯什”,“办公室3”)...-占据(“拉凯什”,“办公室7”)<=1；peopleprob.Constraints.constmr5=占用(“马塞洛”,“办公室5”)+和（占）(“拉凯什”，：）-占领(“拉凯什”,“办公室2”)...-占据(“拉凯什”,“办公室6”) <= 1; peopleprob.Constraints.constmr6=占用(“马塞洛”,“办公室6”)+和（占）(“拉凯什”，：）-占领(“拉凯什”,“办公室3”)...-占据(“拉凯什”,“办公室5”)-占领(“拉凯什”,“办公室7”)<=1；peopleprob.Constraints.constmr7=占用(“马塞洛”,“办公室7”)+和（占）(“拉凯什”，：）-占领(“拉凯什”,“办公室4”)...-占据(“拉凯什”,“办公室6”) <= 1;

解决指派问题

呼叫解决解决这个问题。

[soln，fval，exitflag，output]=solve（peopleprob）；

LP：最佳目标值为-33.836066。找到最佳解决方案。Intlinprog在根节点停止，因为目标值在最佳值的间隙公差范围内，options.AbsoluteGapTolerance=0（默认值）。intcon变量是公差范围内的整数，options.IntegerTolerance=1e-05（默认值）。

查看解决方案--谁拥有每个办公室？

数量=长度（officelist）；办公室=单元格（数量，1）；对于i=1:numofices office{i}=find（soln.occupation（：，i））；%办公室人员索引终止whoinoffice=公职人员；%分配对于i=1：数量如果isempty（office{i}）whoioffice{i}=“空的”;其他的whoioffice{i}=姓名列表（office{i}）；终止终止打印签名（whoinfice）；标题(“办公室分配问题的解决方案”);

溶液质量

对于这个问题，根据资历对偏好的满意度最大化为未来值.价值出口滞后表明解决收敛到最优解。输出结构提供了有关解过程的信息，例如探索了多少个节点，以及分支计算中上下限之间的差距。在这种情况下，没有生成分支和绑定节点，这意味着问题的解决没有分支和绑定步骤。绝对差距为0，表示该解决方案是最优的，目标函数内部计算的上下限之间没有差异。

fval，exitflag，输出

fval=33.8361

exitflag=1

输出=带字段的结构：relativegap:0 absolutegap:0 NumFasPoints:1 numnodes:0:0消息：“找到最佳解决方案。”。↵↵Intlinprog在根节点停止，因为目标值在最佳值options.AbsoluteGaptoreance=0（默认值）的间隙公差范围内。intcon变量是公差范围内的整数，options.IntegerTolerance=1e-05（默认值）。“解算器：'Intlinprog'