基于二进制整数规划的办公室分配:基于问题
这个例子展示了如何使用优化问题的方法，通过二进制整数规划来解决分配问题。有关基于求解器的方法，请参见二进制整数规划的办公室分配:基于求解器．
办公室分配问题
你要安排六个人，马塞洛，拉凯什，彼得，汤姆，玛乔丽和玛丽·安，到七个办公室工作。每个办公室最多只能有一个人，每个人只能有一个办公室。所以会有一间空办公室。人们可以对办公室有偏好，他们的偏好是根据他们的资历来考虑的。他们在数学工场工作的时间越长，资历越高。有些办公室有窗户，有些没有，有一扇窗户比其他的小。另外，彼得和汤姆经常在一起工作，所以应该在相邻的办公室。马塞洛和拉凯什经常一起工作，应该在相邻的办公室。
办公室布局
办公室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];weightvector =资历/笔(工龄);
人们的办公室偏好
建立一个偏好矩阵，其中行对应办公室，列对应人。让每个人给出每个办公室的值，这样他们所有的选择的总和，也就是他们的栏，就等于100。数字越大，表示这个人更喜欢这个办公室。每个人的偏好在列向量中列出。
MaryAnn = [0, 0, 0, 10, 40, 50];Marjorie = [0, 0, 0, 20, 40, 40];Tom = [0, 0, 0, 0, 30, 40, 30];Peter = [1,3,3,10,40, 40];Marcelo = [3, 4, 1, 2, 10, 40, 40];Rakesh = [10,10,10,20, 20, 20];
个人偏好向量的第i个元素是他们对第i个办公室的评价。因此，组合偏好矩阵如下。
prefmatrix =[玛丽安,马约莉,汤姆,彼得,马塞洛;Rakesh);
偏好矩阵的权重weightvector按年资排列。
PM = diag(权重向量)*前缀矩阵;
目标函数
目标是最大限度地满足按资历加权的偏好。这是线性目标函数sum (sum(占领。*点))．
创建一个优化问题并包含目标函数。
peopleprob = optimproblem (“ObjectiveSense”，“最大化”，“目标”总和(sum(占领。*点)));
约束
第一组约束要求每个人只能得到一个办公室，也就是说，每个人的办公室和占领对应于那个人的值正好是1。
peopleprob.Constraints。Constr1 = sum(occupy,2) == 1;
第二组约束是不等式。这些约束规定每个办公室中不超过一个人。
peopleprob.Constraints。Constr2 = sum(occupy,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;
现在创建约束条件，使马塞洛和拉凯什之间的距离不超过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;
解决分配问题
调用解决来解决问题。
(溶液、fval exitflag、输出]=解决(peopleprob);
LP:最优物值为-33.836066。找到最优解。Intlinprog在根节点停止，因为客观值在最优值选项的间隙公差内。AbsoluteGapTolerance = 0(默认值)intcon变量在tolerance, options中是整数。IntegerTolerance = 1e-05(默认值)。
查看解决方案——谁得到了每个办公室?
numOffices =长度(officelist);办公室=细胞(numOffices, 1);为i=1:numOffices office{i} = find(soln.occupy(:，i));在办公室的人指数结束whoinoffice = officelist;%分配为我= 1:numOffices如果办公室isempty ({}) whoinoffice{我}=“空”；其他的办公室whoinoffice{我}=学生名单({});结束结束printofficeassign (whoinoffice);标题(“解决办公室分配问题”)；
解决方案质量
对于这个问题，排资优先的满意度最大化到值fval．的价值exitflag表明解决收敛到最优解。输出结构提供了关于解决过程的信息，例如已经探索了多少节点，以及分支计算中下界和上界之间的差距。在本例中，没有生成分支绑定节点，这意味着无需分支绑定步骤就可以解决问题。绝对差距为0，意味着解决方案是最优的，内部计算的目标函数上下限和上限之间没有差异。
fval exitflag,输出
fval = 33.8361
exitflag = 1
输出=结构体字段:numfeaspoints: 1 numnodes: 0 constr违例:0 message: 'Optimal solution found. '↵↵Intlinprog在根节点停止，因为客观值在最优值，选项的间隙公差内。AbsoluteGapTolerance = 0(默认值)intcon变量在tolerance, options中是整数。IntegerTolerance = 1e-05(默认值)。“解决者:“intlinprog”
相关的话题
你也可以从以下列表中选择一个网站:
