二进制整数规划的办公室作业:基于问题
这个例子展示了如何用最优化问题的方法通过二进制整数规划来解决一个赋值问题。关于基于求解器的方法，请参见二进制整数规划的办公室分配:基于解算器。
办公室分配问题
您想要分配6个人到7个办公室，分别是Marcelo、Rakesh、Peter、Tom、Marjorie和Mary Ann。每个办公室只能有一个人，每个人只能有一个办公室。所以会有一间空办公室。人们可以给出对办公室的偏好，他们的偏好是根据他们的资历来考虑的。他们在MathWorks工作的时间越长，资历越高。有些办公室有窗户，有些没有，而且有一扇窗户比其他的小。另外，彼得和汤姆经常在一起工作，所以他们应该在相邻的办公室。马塞洛和拉凯什经常一起工作，而且应该在相邻的办公室。
办公室布局
办公室1、2、3和4是内部办公室(没有窗户)。5号、6号和7号办公室有窗户，但5号办公室的窗户比其他两个小。办公室是这样安排的。
Officelist = {办公室1 '，《办公室2》，办公室3 '，“办公室4”，办公室5 '，“办公室6”，“办公室7”};printofficeassign (officelist)
问题公式化
你需要用数学公式来表述这个问题。创建二进制变量，指示某人是否占用办公室。名单上的人是
Namelist = {“玛丽安”，“马约莉”，“汤姆”，“彼得”，“马塞洛”，拉克什的};
创建按办公室号码和名称索引的二进制变量。
占用= optimvar()“占领”, officelist名称列表…“类型”，“整数”，下界的0,“Upperbound”1);
资历
您希望根据资历对偏好进行加权，以便您在MathWorks工作的时间越长，您的偏好就越重要。年龄:Mary Ann 9岁，Marjorie 10岁，Tom 5岁，Peter 3岁，Marcelo 1.5岁，Rakesh 2岁。创建一个基于资历的标准化权重向量。
年资= [9 10 5 3 1.5 2];权重向量=工龄/sum(工龄);
人们的办公室偏好
设置一个偏好矩阵，其中行对应办公室，列对应人员。让每个人给出每个办公室的值，这样他们所有选择的总和，即他们的列，等于100。更高的数字意味着这个人更喜欢办公室。每个人的偏好都列在一个列向量中。
MaryAnn = [0,0,0,0,10,40,50];Marjorie = [0,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,10,10,20,20,20];
一个人偏好向量的第i个元素是他们对第i个办公室的重视程度。因此，组合偏好矩阵为:
prematrix = [MaryAnn;Marjorie;Tom;Peter;Marcelo;Rakesh];
对偏好矩阵进行加权weightvector按资历对列进行缩放。
PM = diag(weightvector) * prematrix;
目标函数
目标是最大限度地满足按资历加权的偏好。这是线性目标函数sum (sum(占领。*点))。
创建一个优化问题并包含目标函数。
people =最优问题“ObjectiveSense”，“最大化”，“目标”总和(sum(占领。*点)));
约束
第一组约束要求每个人只分到一个办公室，对每个人来说，是占领这个人对应的值正好是1。
peopleprob.Constraints。1 = sum(occupy,2) == 1;
第二组约束是不等式。这些约束规定每个办公室中不能有超过一个人。
peopleprob.Constraints。Constr2 = sum(占位，1)<= 1;
你希望汤姆和彼得之间的距离不超过一间办公室，马塞洛和拉凯什也是如此。
设置约束，Tom和Peter彼此之间的距离不超过1。
peopleprob.Constraints。Constrpt1 =占用(“汤姆”，办公室1 ') + sum(占)“彼得”，:)) -占用(“彼得”，《办公室2》) <= 1;peopleprob.Constraints。Constrpt2 =占用(“汤姆”，《办公室2》) + sum(占)“彼得”，:)) -占用(“彼得”，办公室1 '）…占据(“彼得”，办公室3 ') -占用(“彼得”，办公室5 ') <= 1;peopleprob.Constraints。Constrpt3 =占用(“汤姆”，办公室3 ') + sum(占)“彼得”，:)) -占用(“彼得”，《办公室2》）…占据(“彼得”，“办公室4”) -占用(“彼得”，“办公室6”) <= 1;peopleprob.Constraints。Constrpt4 =占用(“汤姆”，“办公室4”) + sum(占)“彼得”，:)) -占用(“彼得”，办公室3 '）…占据(“彼得”，“办公室7”) <= 1;peopleprob.Constraints。Constrpt5 =占用(“汤姆”，办公室5 ') + sum(占)“彼得”，:)) -占用(“彼得”，《办公室2》）…占据(“彼得”，“办公室6”) <= 1;peopleprob.Constraints。Constrpt6 =占用(“汤姆”，“办公室6”) + sum(占)“彼得”，:)) -占用(“彼得”，办公室3 '）…占据(“彼得”，办公室5 ') -占用(“彼得”，“办公室7”) <= 1;peopleprob.Constraints。Constrpt7 =占用(“汤姆”，“办公室7”) + sum(占)“彼得”，:)) -占用(“彼得”，“办公室4”）…占据(“彼得”，“办公室6”) <= 1;
现在创建约束，Marcelo和Rakesh彼此之间的距离不超过1。
peopleprob.Constraints。Constmr1 =占用(“马塞洛”，办公室1 ') + sum(占)拉克什的，:)) -占用(拉克什的，《办公室2》) <= 1;peopleprob.Constraints。Constmr2 =占用(“马塞洛”，《办公室2》) + sum(占)拉克什的，:)) -占用(拉克什的，办公室1 '）…占据(拉克什的，办公室3 ') -占用(拉克什的，办公室5 ') <= 1;peopleprob.Constraints。Constmr3 =占用(“马塞洛”，办公室3 ') + sum(占)拉克什的，:)) -占用(拉克什的，《办公室2》）…占据(拉克什的，“办公室4”) -占用(拉克什的，“办公室6”) <= 1;peopleprob.Constraints。Constmr4 =占用(“马塞洛”，“办公室4”) + sum(占)拉克什的，:)) -占用(拉克什的，办公室3 '）…占据(拉克什的，“办公室7”) <= 1;peopleprob.Constraints。Constmr5 =占用(“马塞洛”，办公室5 ') + sum(占)拉克什的，:)) -占用(拉克什的，《办公室2》）…占据(拉克什的，“办公室6”) <= 1;peopleprob.Constraints。Constmr6 =占用(“马塞洛”，“办公室6”) + sum(占)拉克什的，:)) -占用(拉克什的，办公室3 '）…占据(拉克什的，办公室5 ') -占用(拉克什的，“办公室7”) <= 1;peopleprob.Constraints。Constmr7 =占用(“马塞洛”，“办公室7”) + sum(占)拉克什的，:)) -占用(拉克什的，“办公室4”）…占据(拉克什的，“办公室6”) <= 1;
解决分配问题
调用解决解决问题。
[soln,fval,exitflag,output] = solve(peopleprob);
LP:最优目标值为-33.836066。找到最优解。Intlinprog停止在根节点，因为目标值在最优值的容差范围内，选项。AbsoluteGapTolerance = 0(默认值)。intcon变量是公差范围内的整数，选项。IntegerTolerance = 1e-05(默认值)。
查看解决方案——谁得到了每个办公室?
numooffices = length(officelist);office = cell(numoffice,1);为i=1: nuoffice office{i} = find(soln.occupy(:，i));%的人在办公室索引结束Whoinoffice = officelist;%分配为我= 1:numOffices如果Isempty (office{i}) whoinoffice{i} =“空的”；其他的Whoinoffice {i} = namelist(office{i});结束结束printofficeassign (whoinoffice);标题(“办公室分配问题的解决方案”）；
解决方案质量
对于这个问题，资历对偏好的满足最大化到的值fval。的价值exitflag表明解决收敛到最优解。输出结构提供有关解决过程的信息，例如探索了多少个节点，以及分支计算中下界和上界之间的差距。在本例中，没有生成分支绑定节点，这意味着没有分支绑定步骤就解决了问题。绝对差距为0，意味着解决方案是最优的，内部计算的目标函数的下界和上界之间没有差异。
fval exitflag,输出
Fval = 33.8361
退出标志= 1
输出=带有字段的结构体:relativegap: 0 absolutegap: 0 numfeaspoints: 1 numnodes: 0 constrviolation: 0 message: '找到最优解。由于目标值在最优值的容差范围内，Intlinprog停止在根节点。AbsoluteGapTolerance = 0(默认值)。intcon变量是公差范围内的整数，选项。IntegerTolerance = 1e-05(默认值)。求解器:intlinprog
