这个例子展示了如何用优化问题的方法用二进制整数规划来解决分配问题。关于基于求解器的方法,请参见二进制整数规划的办公室分配:基于求解器。
你想把马塞洛、拉凯什、彼得、汤姆、玛乔丽和玛丽·安这六个人分配到七个办公室。每个办公室不能有超过一个人,每个人正好有一个办公室。所以会有一间空办公室。人们可以对办公室有偏好,他们的偏好是根据他们的资历来考虑的。他们在MathWorks工作的时间越长,资历就越高。有些办公室有窗户,有些没有,一个窗户比另一个小。另外,Peter和Tom经常一起工作,所以应该在相邻的办公室。马塞洛和拉凯什经常一起工作,应该在相邻的办公室。
办公室1,2,3和4位于办公室内(无窗口)。办公室5,6和7具有窗户,但办公室5中的窗口小于其他两个。以下是办公室的排列方式。
officelist = {'办公室1'那《办公室2》那办公室3 '那“办公室4”那'办公室5'那'办公室6'那'办公室7'};printofficeassign (officelist)
你需要用数学来阐述这个问题。创建二进制变量来指示一个人是否占据了办公室。人们的名单是
名称列表= {'玛丽安'那“马约莉”那“汤姆”那“彼得”那'marcelo'那拉克什的};
创建由Office号和名称索引的二进制变量。
占用= Optimvar(“占领”,namelist,官方者,......“类型”那“整数”那'indowbound'0,'上行'1);
您希望根据资历重视偏好,以便您在MathWorks的时间越长,您的偏好数量越多。资历如下:玛丽安9年,玛雅丽10年,汤姆5年,彼得3年,马塞洛1.5年,并rakesh 2年。根据资历创建一个规范化的权重向量。
资历= [9 10 5 3 1.5 2];重量矢量=资历/总和(资历);
设置优先矩阵,其中行对应于办公室,列对应于人员。要求每个人为每个办公室提供价值,以便所有选择的总和,即他们的专栏,总和100.更高的数字意味着该人更喜欢该办公室。每个人的偏好都列在列向量中。
MaryAnn = [0,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,20,20, 20];
一个人的偏好向量的第i个元素是他们对第i个办公室的重视程度。因此,组合偏好矩阵为:
prefmatrix =[玛丽安,马约莉,汤姆,彼得,马塞洛;Rakesh);
重量偏好矩阵weightvector
按资历扩展列。
PM = diag(权重向量)*前缀矩阵;
其目标是最大限度地满足按资历加权的偏好。这是线性目标函数总和(总和(占用。* PM))
。
创建优化问题并包括目标函数。
peopleprob = optimproblem ('ObjectiveSense'那“最大化”那'客观的',总和(总和(占用。* PM)));
第一组约束要求每个人都恰好一个办公室,这是每个人,这是一个办公室,这是每个人的总和占据
这个人对应的值正好是1。
peopleprob.Constraints。Constr1 = sum(occupy,2) == 1;
第二组约束是不等式。这些约束规定每个办公室中不超过一个人。
peopleprob.constraints.constr2 = sum(占用,1)<= 1;
你想要汤姆和彼得不超过一个办公室远离彼此,也是马塞洛和rakesh的办公室。
设置汤姆和彼得的约束彼此不超过1个。
peopleprob.constraints.constrtt1 =占据(“汤姆”那'办公室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.constratt7 =占用(“汤姆”那'办公室7')+总和(占用(“彼得”,:))——占领(“彼得”那“办公室4”)......占据(“彼得”那'办公室6') < = 1;
现在创建约束条件,使马塞洛和拉凯什之间的距离不大于1。
peopleprob.constraints.constmr1 =占用('marcelo'那'办公室1')+总和(占用(拉克什的,:))——占领(拉克什的那《办公室2》) < = 1;peopleprob.constraints.constmr2 =占用('marcelo'那《办公室2》)+总和(占用(拉克什的,:))——占领(拉克什的那'办公室1')......占据(拉克什的那办公室3 ') - 占据(拉克什的那'办公室5') < = 1;peopleprob.constraints.constmr3 =占据('marcelo'那办公室3 ')+总和(占用(拉克什的,:))——占领(拉克什的那《办公室2》)......占据(拉克什的那“办公室4”) - 占据(拉克什的那'办公室6') < = 1;peopleprob.constraints.constmr4 =占用('marcelo'那“办公室4”)+总和(占用(拉克什的,:))——占领(拉克什的那办公室3 ')......占据(拉克什的那'办公室7') < = 1;peopleprob.constraints.constmr5 =占据('marcelo'那'办公室5')+总和(占用(拉克什的,:))——占领(拉克什的那《办公室2》)......占据(拉克什的那'办公室6') < = 1;peopleprob.constraints.constmr6 =占据('marcelo'那'办公室6')+总和(占用(拉克什的,:))——占领(拉克什的那办公室3 ')......占据(拉克什的那'办公室5') - 占据(拉克什的那'办公室7') < = 1;peopleprob.Constraints。constmr7 =占领('marcelo'那'办公室7')+总和(占用(拉克什的,:))——占领(拉克什的那“办公室4”)......占据(拉克什的那'办公室6') < = 1;
称呼解决
来解决这个问题。
(溶液、fval exitflag、输出]=解决(peopleprob);
LP:最佳目标值为-33.836066。找到最佳解决方案。intlinprog在根节点停止,因为客观值在最佳值的间隙容忍度范围内,Options.absolutegAppolerance = 0(默认值)。INTCON变量在容差,选项中是整数.inteGertolerance = 1E-05(默认值)。
numOffices =长度(officelist);办公室=细胞(numOffices, 1);为了i=1: numooffices office{i} = find(soln.occupy(:,i));%人员在办公室指数结尾Whoinoffice =官方者;%分配为了我= 1:numoftices如果办公室isempty ({}) whoinoffice{我}=' 空的 ';别的whoinoffice {i} = namelist(办公室{i});结尾结尾PrintofficeAssign(Whoinoffice);标题('办公室分配问题的解决方案');
对于这个问题,资历偏好的满足感最大化到了价值fval.
。的价值ExitFlag.
表明解决
融合到最佳解决方案。输出结构提供有关解决方案过程的信息,例如探索了多少个节点,以及分支计算中的下限和上限之间的间隙。在这种情况下,没有生成分支和绑定节点,这意味着问题在没有分支和绑定步骤的情况下解决了问题。绝对间隙为0,这意味着解决方案是最佳的,内部计算的下限和上限之间没有差异。
FVAL,EXITFLAG,输出
fval = 33.8361
EXITFLAG = 1
输出=结构体字段:relativegap: 0 absoltegap: 0 numfeaspoints: 1 numnodes: 0 construc违例:0消息:'最佳解决方案找到了。↵↵Intlinprog在根节点停止,因为客观值在最优值options的间隙公差范围内。AbsoluteGapTolerance = 0(默认值)。INTCON变量在容差,选项中是整数.inteGertolerance = 1E-05(默认值)。“解决者:“intlinprog”