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

打开实时脚本

这个例子展示了如何用优化问题的方法通过二进制整数规划来解决分配问题。有关基于求解器的方法，请参见二进制整数编程的办公室分配:基于求解器．

办公室分配问题

你想给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)

问题公式化

你需要用数学公式来表述这个问题。创建二进制变量，表明某人是否占用办公室。名单上的人是

名单= {“玛丽安”，“马约莉”，“汤姆”，“彼得”，“马塞洛”，拉克什的};

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

占用= 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];权重向量=资历/和(资历);

人们的办公室偏好

建立一个偏好矩阵，其中行对应办公室，列对应人员。让每个人给出每个办公室的值，使他们所有选择的总和，即他们的列，总和为100。数字越高，说明这个人更喜欢办公室。每个人的喜好都列在一个列向量中。

MaryAnn = [0,0,0,0,10,40,50];玛乔丽= [0,0,0,0,20,40,40];Tom = [0,0,0,0,30,40,30];彼得= [1,3,3,3,10,40,40];马塞洛= [3,4,1,2,10,40,40];Rakesh = [10,10,10,20,20,20];

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

prematrix =[玛丽安;玛乔丽;汤姆;彼得;马塞洛;拉凯什];

对偏好矩阵进行加权weightvector按资历排列列。

PM = diag(权重向量)*前置矩阵;

目标函数

目标是最大限度地满足以资历为权重的偏好。这是线性目标函数sum (sum(占领。*点))．

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

最优问题(“ObjectiveSense”，“最大化”，“目标”总和(sum(占领。*点)));

约束

第一套约束条件要求每个人得到恰好一间办公室，也就是每个人的和占领这个人对应的值恰好是1。

peopleprob.Constraints。Constr1 = sum(occupy,2) == 1;

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

peopleprob.Constraints。= sum(occupy,1) <= 1;

你想让汤姆和彼得只隔一间办公室，马塞洛和拉凯什也一样。

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

peopleprob.Constraints。Constrpt1 =占用(“汤姆”，办公室1 ') + sum(occupy(“彼得”，:)) -占用(“彼得”，《办公室2》) <= 1;peopleprob.Constraints。占用(占用)“汤姆”，《办公室2》) + sum(occupy(“彼得”，:)) -占用(“彼得”，办公室1 '）.．.占据(“彼得”，办公室3 ') -占用(“彼得”，办公室5 ') <= 1;peopleprob.Constraints。占用(占用)“汤姆”，办公室3 ') + sum(occupy(“彼得”，:)) -占用(“彼得”，《办公室2》）.．.占据(“彼得”，“办公室4”) -占用(“彼得”，“办公室6”) <= 1;peopleprob.Constraints。占用(占用)“汤姆”，“办公室4”) + sum(occupy(“彼得”，:)) -占用(“彼得”，办公室3 '）.．.占据(“彼得”，“办公室7”) <= 1;peopleprob.Constraints。占用(占用)“汤姆”，办公室5 ') + sum(occupy(“彼得”，:)) -占用(“彼得”，《办公室2》）.．.占据(“彼得”，“办公室6”) <= 1;peopleprob.Constraints。占用(占用)“汤姆”，“办公室6”) + sum(occupy(“彼得”，:)) -占用(“彼得”，办公室3 '）.．.占据(“彼得”，办公室5 ') -占用(“彼得”，“办公室7”) <= 1;peopleprob.Constraints。占用(占用)“汤姆”，“办公室7”) + sum(occupy(“彼得”，:)) -占用(“彼得”，“办公室4”）.．.占据(“彼得”，“办公室6”) <= 1;

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

peopleprob.Constraints。Constmr1 =占据(“马塞洛”，办公室1 ') + sum(occupy(拉克什的，:)) -占用(拉克什的，《办公室2》) <= 1;peopleprob.Constraints。Constmr2 =占据(“马塞洛”，《办公室2》) + sum(occupy(拉克什的，:)) -占用(拉克什的，办公室1 '）.．.占据(拉克什的，办公室3 ') -占用(拉克什的，办公室5 ') <= 1;peopleprob.Constraints。占据(“马塞洛”，办公室3 ') + sum(occupy(拉克什的，:)) -占用(拉克什的，《办公室2》）.．.占据(拉克什的，“办公室4”) -占用(拉克什的，“办公室6”) <= 1;peopleprob.Constraints。Constmr4 =占据(“马塞洛”，“办公室4”) + sum(occupy(拉克什的，:)) -占用(拉克什的，办公室3 '）.．.占据(拉克什的，“办公室7”) <= 1;peopleprob.Constraints。占据(“马塞洛”，办公室5 ') + sum(occupy(拉克什的，:)) -占用(拉克什的，《办公室2》）.．.占据(拉克什的，“办公室6”) <= 1;peopleprob.Constraints。占据(“马塞洛”，“办公室6”) + sum(occupy(拉克什的，:)) -占用(拉克什的，办公室3 '）.．.占据(拉克什的，办公室5 ') -占用(拉克什的，“办公室7”) <= 1;peopleprob.Constraints。占据(“马塞洛”，“办公室7”) + sum(occupy(拉克什的，:)) -占用(拉克什的，“办公室4”）.．.占据(拉克什的，“办公室6”) <= 1;

解决分配问题

调用解决解决问题。

[soln,fval,exitflag,output] = solve(peopleproblem);

LP:最佳目标值为-33.836066。找到最优解。Intlinprog停止在根节点，因为目标值在最佳值的间隙公差范围内，选项。AbsoluteGapTolerance = 0(默认值)。intcon变量是公差范围内的整数，选项。IntegerTolerance = 1e-05(默认值)。

查看解决方案——谁拥有每个办公室?

numOffices = length(officelist);office = cell(nummoffices,1);为i=1:numOffices office{i} = find(soln.occupy(:，i));%办公室人员指数结束Whoinoffice =办公室名单;%分配为我= 1:numOffices如果Isempty (office{i}) whoinoffice{i} =“空的”；其他的Whoinoffice {i} = namelist(office{i});结束结束printofficeassign (whoinoffice);标题(“办公室分配问题的解决方案”）;

解决方案质量

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

fval exitflag,输出

Fval = 33.8361

Exitflag = 1

输出=带字段的结构:relativegap: 0 absolutegap: 0 numfeaspoints: 1 numnodes: 0 constrviolation: 0 message: '找到最佳解决方案。(() Intlinprog停止在根节点，因为目标值在最优值，选项的间隙公差范围内。AbsoluteGapTolerance = 0(默认值)。intcon变量是公差范围内的整数，选项。IntegerTolerance = 1e-05(默认值)。'intlinprog'