办公室由二进制整数规划作业:具体问题具体分析
这个例子展示了如何解决分配问题的二进制整数规划优化问题的方法。solver-based方法,请参阅办公室由二进制整数规划作业:Solver-Based。
办公室分配问题
你想安排6人,马塞洛,拉克什,彼得,汤姆,马约莉,和玛丽安,七个办事处。每个办公室可以有不超过一个人,每一人一个办公室。所以将会有一个空的办公室。人们可以给偏好的办公室,他们的偏好被认为是基于他们的资历。他们一直在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的时间越长,越多你的喜好。资历如下:玛丽安9年,马约莉10年,汤姆5年,3年,彼得马塞洛1.5年,Rakesh 2年。创建一个基于资历的归一化权重向量。
资历= (9 10 5 3 1.5 - 2);weightvector =资历/笔(工龄);
人们的办公室偏好
建立一个偏好矩阵的行对应于办公室和列对应于人。每个办公室问每个人给值,这样他们的选择的总和,即。,他们的列,金额为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,3,10日,40岁,40);马塞洛=[3、4、1、2、10,40岁,40);Rakesh = [10、10、10、10、20、20、20);
第i个元素的一个人的偏好向量是他们高度重视的第i个办公室。因此,合并后的偏好矩阵如下。
prefmatrix =[玛丽安,马约莉,汤姆,彼得,马塞洛;Rakesh);
体重的偏好矩阵weightvector规模列资历。
点=诊断接头(weightvector) * prefmatrix;
目标函数
目标是最大限度地满足偏好权重的资历。这是线性目标函数sum (sum(占领。*点))。
创建一个优化问题,包括目标函数。
peopleprob = optimproblem (“ObjectiveSense”,“最大化”,“目标”总和(sum(占领。*点)));
约束
第一组约束要求每一个人一个办公室,这是对于每一个人,的总和占领值对应于那个人就是一个。
peopleprob.Constraints。constr1 =总和(占领,2)= = 1;
第二组的约束是不平等。这些约束指定每个办公室都有不超过一个人。
peopleprob.Constraints。constr2 =总和(占领,1)< = 1;
你想要汤姆和彼得不超过一个办公室远离彼此,和相同的马塞洛和拉克什。
设置约束汤姆和彼得不超过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;
现在创建约束,马塞洛和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;
解决分配问题
调用解决来解决这个问题。
(溶液、fval exitflag、输出]=解决(peopleprob);
LP:最优的客观价值是-33.836066。找到最优解。Intlinprog停在根节点,因为客观价值差距公差内的最优值,选择。AbsoluteGapTolerance = 0(默认值)。在宽容intcon变量是整数,选项。IntegerTolerance = 1 e-05(默认值)。
查看解决方案——每个办公室了?
numOffices =长度(officelist);办公室=细胞(numOffices, 1);为i = 1: numOffices办公室{我}=找到(soln.occupy(:,我));%的人指数结束whoinoffice = officelist;%分配为我= 1:numOffices如果办公室isempty ({}) whoinoffice{我}=“空”;其他的办公室whoinoffice{我}=学生名单({});结束结束printofficeassign (whoinoffice);标题(办公室分配问题的解决方案);
解决方案质量
对于这个问题,满足偏好的资历是最大化的价值fval。的价值exitflag表明解决聚集到一个最优的解决方案。输出结构使信息解决方案过程,如探索有多少节点和之间的差距的上下边界计算分支。在这种情况下,没有生成和节点,这意味着没有和步骤,问题就迎刃而解了。绝对差距为0,这意味着解决方案是最优的,在没有内部差异计算低,目标函数上界。
fval exitflag,输出
fval = 33.8361
exitflag = 1
输出=结构体字段:relativegap: 0 absolutegap: 0 numfeaspoints: 1 numnodes: 0 constrviolation: 0消息:“找到最优解。↵↵Intlinprog停在根节点,因为客观价值差距公差内的最优值,选择。AbsoluteGapTolerance = 0(默认值)。在宽容intcon变量是整数,选项。IntegerTolerance = 1 e-05(默认值)。“解决者:“intlinprog”
