整数规划与matlab.ppt

,单击此处编辑母版标题样式,单击此处编辑母版标题样式,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,整数规划与matlab,整数规划与matlab整数规划与matlab 设：xj 表示用Bj(j=1.2n)种方式下料根数,模型：整数规划的模型,设：,x,j,表示用,B,j,(,j,=1.2n),种方式下料根数,模型：,整数规划的模型,例三、机床分配问题,设有,m,台同类机床，要加工,n,种零件。已知各种零件的加工时间分别为,a,1,a,2,a,n,，问如何分配，使各机床的总加工任务相等，或者说尽可能平衡。,整数规划的模型,设：,1,分配第,i,台机床加工第,j,种零件；,x,ij,（,i,=1,2,m,;,j,=1,2,n,）,0,相反。,于是，第,i,台机床加工各种零件的总时间为：,因此，求,x,ij,，使得,又由于一个零件只能在一台机床上加工，所以有,整数规划的模型,整数规划一般形式,依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、,0,1,整数规划。,整数规划的数学模型,部分或者全部为整数,纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。,全整数规划：除所有决策变量要求取非负整数外，系数,a,ij,和常数,b,i,也要求取整数（这时引进的松弛变量和剩余变量也必须是整数）。,混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。,0,1,整数规划：所有决策变量只能取,0,或,1,两个整数。,整数规划的数学模型,从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。,整数规划与线性规划的关系,例：设整数规划问题如下,首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。,整数规划与线性规划的关系,且为整数,用图解法求出最优解,x,1,3/2,x,2,=10/3,且有,Z=29/6,x,1,x,2,3,3,(3/2,10/3),现求整数解（最优解）：如用“舍入取整法”可得到,4,个点即,(1,，,3),(2,，,3),(1,，,4),(2,，,4),。显然，它们都不可能是整数规划的最优解。,按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。,整数规划与线性规划的关系,因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。,如上例：其中（,2,，,2,）（,3,，,1,）点为最大值，,Z=4,。,目前，常用的求解整数规划的方法有：,分支定界法和割平面法；,对于特别的,0,1,规划问题采用隐枚举法和匈牙利法。,整数规划与线性规划的关系,考虑纯整数问题：,整数问题的松弛问题：,分枝定界法,1,、先不考虑整数约束，解,(,IP,),的松弛问题,(,LP,),，可能得到以下情况之一：,.,若,(,LP,),没有可行解，则,(,IP,),也没有可行解，停止计算。,.,若,(,LP,),有最优解，并符合,(,IP,),的整数条件，则,(,LP,),的最优解即为,(,IP,),的最优解，停止计算。,.,若,(,LP,),有最优解，但不符合,(,IP,),的整数条件，转入下一步。为讨论方便，设,(,LP,),的最优解为：,分枝定界法,2,、定界：,记,(,IP,),的目标函数最优值为,Z,*,以,Z,(0),作为,Z,*,的上界，记为 ,Z,(0),。再用观察法找的一个整数可行解,X,，并以其相应的目标函数值,Z,作为,Z,*,的下界，记为,Z,Z,，也可以令,Z,，则有,:,Z,Z,*,3,、分枝：,在,(,LP,),的最优解,X,(,0),中，任选一个不符合整数条件的变量，例如,x,r,=,b,r,（不为整数），以,b,r,表示不超过,b,r,的最大整数。构造两个约束条件,x,r,b,r,和,x,r,b,r,1,分枝定界法,将这两个约束条件分别加入问题,(,IP,),，形成两个子问题,(,IP1,),和,(,IP2,),，再解这两个问题的松弛问题,(,LP1,),和,(,LP2,),。,4,、修改上、下界：按照以下两点规则进行。,.,在各分枝问题中，找出目标函数值最大者作为新的上界；,.,从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。,5,、比较与剪枝：,各分枝的目标函数值中，若有小于,Z,者，则剪掉此枝，表明此子问题已经探清，不必再分枝了,;,否则继续分枝。,如此反复进行，直到得到,Z,Z,*,为止，即得最优解,X,*,。,分枝定界法,为了更好地说明用分枝定界法求整数规划最优解的过程，我们选择只有两个变量的引例,3.2.1,进行求解。,例,3.3.1,用分枝定界法求解整数规划问题,(P),：,max,Z,=15,x,1,20,x,2,s.t.6,x,1,4,x,2,25,x,1,3,x,2,10,x,i,0,1,2,解,：,1.,求解如下的松弛问题,(P,0,),：,(P,0,),：,max,Z,=15,x,1,20,x,2,s.t.,6,x,1,4,x,2,25,x,1,3,x,2,10,x,i,0,，,i,=1,2,得最优解,x,1,=2.5,，,x,2,=2.5,，最优值,z,=87.5,。由于原问题,(P),目标函数的系数为整数，,x,i,0,1,2,，故,z,*,87,，即最优值的上界,=87,。令最优值的下界,z,=0,，则有,z,=0,z,*,87=,。我们将这些结果记录在树形图图,3.3.3,中。,2.,因为此时两个变量都不是整数，我们从中选择一个变量进行分枝。假定选择,x,1,，在,(P,0,),的约束之外，增加两个互相排斥的约束条件：,x,1,2,与,x,1,3,，形成两个子模型,(P,1,),和,(P,2,),：,(P,1,),：,max,Z,=15,x,1,20,x,2,(P,2,),：,max,Z,=15,x,1,20,x,2,s.t.,6,x,1,4,x,2,25 s.t.,6,x,1,4,x,2,25,x,1,3,x,2,10,x,1,3,x,2,10,x,1,2,x,1,3,x,i,0,，,i,=1,2,x,i,0,，,i,=1,2,此时，模型,(P,0,),的可行域被分成两个相应的子域,R,1,和,R,2,，如图,3.3.2,所示。,显然，被抛去的非阴影区域内（,2,x,1,z,=75,，,所以，在,(P,2,),的约束之外，增加两个互相排斥的约束条件：,x,2,1,与,x,2,2,，形成两个子模型,(P,5,),和,(P,6,),：,(P,5,),：,max,Z,=15,x,1,20,x,2,(P,6,),：,max,Z,=15,x,1,20,x,2,s.t.,6,x,1,4,x,2,25 s.t.,6,x,1,4,x,2,25,x,1,3,x,2,10,x,1,3,x,2,10,x,1,3,x,1,3,x,2,1,x,2,2,x,i,0,，,i,=1,2,x,i,0,，,i,=1,2,7.,对子模型,(P,5,),进行求解，得最优解为,x,1,=3.5,，,x,2,=1,，最优值,z,=72.5,。由于最优值,z,=72.5 75=,z,，故不再分枝。因为分枝后，新模型的最优值不可能超过当前新的下界。,8.,对子模型,(P,6,),进行求解，因为无可行解，故不再分枝。,至此，已将所有分枝的子模型求解完毕，当前新的下界值相应的解，是现行最好的整数可行解，也就是原整数规划问题的最优解：,x,1,*=1,，,x,2,*=3,。最优目标函数值,z,=75,。,注：图,3.3.3,中的子模型,(P,3,),、,(P,4,),、,(P,5,),不再分枝，并不是说它们分枝后不可以找到新的整数可行解，而是表明：即使找出新的整数可行解也不会优于目前最好的整数可行解，其目标函数值不会大于目前的下界值，这些可行解已被全部隐含枚举了。,实质上,，,分枝定界法是一种隐枚举法,（,Implicit Enumeration,）。,提示,：用分枝定界法求解整数规划问题，其计算量一般比较大，所以此法只能求解规模不太大的整数规划问题。对于规模较大的整数规划问题，可以采取启发式算法，例如遗传算法来求解。,例二：用分枝定界法求解整数规划问题,记为（,IP,）,解：首先去掉整数约束，变成一般线性规划问题,记为（,LP,）,分枝定界法,用图解法求（,LP,）的最优解，如图所示。,x,1,x,2,3,3,(18/11,40/11),对于,x,1,18/111.64,，,取值,x,1,1,，,x,1,2,对于,x,2,=40/11 3.64,，,取值,x,2,3,，,x,2,4,先将（,LP,）划分为（,LP1,）和（,LP2,）,取,x,1,1,x,1,2,x,1,18/11,x,2,=40/11,Z,(0),=,218/11(,19.8),即,Z,是（,IP,）最小值的下限。,分枝定界法,有下式：,现在只要求出（,LP1,）和（,LP2,）的最优解即可。,分枝定界法,x,1,x,2,3,3,(18/11,40/11),先求（,LP1,）,如图所示。此时,B,在点取得最优解。,x,1,1,x,2,=3,Z,(1),16,找到整数解，问题已探明，此枝停止计算。,1,1,同理求（,LP2,）,如图所示。,在,C,点取得最优解。,即,x,1,2,x,2,=10/3,Z,(2),56/3,18.7,Z,2,Z,1,16,原问题有比（,16,）更小的最优解，但,x,2,不是整数，利用,3 10/34,加入条件。,B,A,C,分枝定界法,加入条件：,x23,x24,有下式：,只要求出（,LP3,）和（,LP4,）的最优解即可。,分枝定界法,x,1,x,2,3,3,(18/11,40/11),1,1,B,A,C,先求（,LP3,）,如图所示。此时,D,在点取得最优解。,即,x,1,12/52.4,x,2,=3,Z,(3),-87/5-17.4 Z(5),F,如对,Z(6),继续分解，其最小值也不会低于,15.5,，问题探明,剪枝。,分枝定界法,至此，原问题（,IP,）的最优解为：,x,1,=2,，,x,2,=3,Z,*,=Z,(5),17,以上的求解过程可以用一个树形图表示如右：,LP1,x,1,=1,x,2,=3,Z,(1),16,LP,x,1,=18/11,x,2,=40/11,Z,(0),19.8,LP2,x,1,=2,x,2,=10/3,Z,(2),18.5,LP3,x,1,=12/5,x,2,=3,Z,(3),17.4,LP4,无可,行解,LP5,x,1,=2,x,2,=3,Z,(5),17,LP6,x,1,=3,x,2,=5/2,Z,(6),15.5,x,1,1,x,1,2,x,2,3,x,2,4,x,1,2,x,1,3,分枝定界法,（一）、计算步骤：,1,、用单纯形法求解,(,IP,),对应的松弛问题,(,LP,),：,.,若,(,LP,),没有可行解，则,(,IP,),也没有可行解，停止计算。,.,若,(,LP,),有最优解，并符合,(,IP,),的整数条件，则,(,LP,),的最优解即为,(,IP,),的最优解，停止计算。,.,若,(,LP,),有最优解，但不符合,(,IP,),的整数条件，转入下一步。,割平面法,2,、从,(LP),的最优解中，任选一个不为整数的分量,x,r,将最优单纯形表中该行的系数 和 分解为整数部分和小数部分之和，并以该行为源行，按下式作割平面方程：,3,、将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列向量），用对偶单纯形法求出新的最优解，返回,1,。,的小数部分,的小数部分,割平面法,例一：用割平面法求解整数规划问题,解：增加松弛变量,x,3,和,x,4,，得到,(,LP),的初始单纯形表和最优单纯形表：,C,j,0,1,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,0,x,3,6,3,2,1,0,0,x,4,0,-3,2,0,1,Z,0,0,1,0,0,C,j,0,1,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,0,x,1,1,1,0,1/6,-1/6,1,x,2,3/2,0,1,1/4,1/4,Z,-3/2,0,0,-1/4,-1/4,割平面法,此题的最优解为：,X,*,=,(1,3/2)Z=3/2,但不是整数最优解，引入割平面。以,x2,为源行生成割平面，由于,1/4=0+1/4,3/2=1+1/2,我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为,:,也即：,割平面法,将,x,3,=,6-3,x,1,-2,x,2,x,4,=3,x,1,-2,x,2,带入,x,1,x,2,3,3,第一个割平面,得到等价的割平面条件：,x2 1,见下图。,割平面法,C,j,0,1,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,s,1,0,x,1,1,1,0,1/6,-1/6,0,1,x,2,3/2,0,1,1/4,1/4,0,0,s,1,-1/2,0,0,-1/4,-1/4,1,Z,-3/2,0,0,-1/4,-1/4,0,现将生成的割平面条件加入松弛变量，然后加到表中：,C,B,X,B,b,x,1,x,2,x,3,x,4,s,1,0,x,1,2/3,1,0,0,-1/3,2/3,1,x,2,1,0,1,0,0,1,0,x,3,2,0,0,1,1,-4,Z,-1,0,0,0,0,-1,割平面法,此时，,X,1,(2/3,1),Z,=1,仍不是整数解。继续以,x,1,为源行生成割平面，其条件为：,用上表的约束解出,x4,和,s1,，将它们带入上式得到等价的割平面条件：,x1 x2,，见图：,x,1,x,2,3,3,第一个割平面,第二个割平面,割平面法,将生成的割平面条件加入松弛变量，然后加到表中：,C,B,X,B,b,x,1,x,2,x,3,x,4,s,1,s,2,0,x,1,2/3,1,0,0,-1/3,2/3,0,1,x,2,1,0,1,0,0,1,0,0,x,3,2,0,0,1,1,-4,0,0,s,2,-2/3,0,0,0,-2/3,-2/3,1,Z,-1,0,0,0,0,-1,0,C,B,X,B,b,x,1,x,2,x,3,x,4,s,1,s,2,0,x,1,0,1,0,0,-1,0,1,1,x,2,0,0,1,0,-1,0,3/2,0,x,3,6,0,0,1,5,0,-6,0,s,1,1,0,0,0,1,1,-3/2,Z,0,0,0,0,1,0,-3/2,割平面法,C,B,X,B,b,x,1,x,2,x,3,x,4,s,1,s,2,0,x,1,1,1,0,0,0,1,-1/2,1,x,2,1,0,1,0,0,1,0,0,x,3,1,0,0,1,0,-5,3/2,0,x,4,1,0,0,0,1,1,-3/2,Z,-1,0,0,0,0,-1,0,至此得到最优表，其最优解为,X,=(1,1),Z=1,这也是原问题的最优解。,有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。,割平面法,0-1,型整数规划,0-1,变量及其应用：,0-1,变量可表示逻辑关系：,x=1:,采取方案。,x=0:,不采取方案。,若需要从,p,个约束条件中，,恰好选择,q,个，则可引入,p,个,0-1,变量：,y,i,=0:,选择,i,个约束条件。,y,i,=1:,不选择,i,个约束条件,那么，约束条件组为：,M,i,是充分大的数,2.,0-1,型整数规划的解法,n,个变量有,2,n,种组合，采用隐枚举法。,列出,2,n,种组合，先求出一个可行解，计算目标函数值，作为当前的最优解。对于其它组合，先计算目标函数值，若不如当前的最优解，就不必检验它的可行性。,否则，如果是可行解，则把更新为当前的最优解。,采用分支定界法，搜索更快。,0,1,整数规划是一种特殊形式的整数规划，这时的决策变量,x,i,只取两个值,0,或,1,，一般的解法为隐枚举法。,例一、求解下列,0,1,规划问题,0,1,整数规划,解：对于,0,1,规划问题，由于每个变量只取,0,，,1,两个值，一般会用穷举法来解，即将所有的,0,，,1,组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。,x,1,.x,2,.x,3,约束条件,满足条件,Z,值,(1)(2)(3)(4),是 否,(0.0.0 ),0 0 0 0,0,(0.0.1),1 1 0 1,5,(0.1.0),2 4 1 4,2,(1.0.0),1 1 1 0,3,(0.1.1),1 5,(1.0.1),0 2 1 1,8,(1.1.0),3,(1.1.1),2 6,0,1,整数规划,由上表可知，问题的最优解为,X,*=(,x,1,=,1,x,2,=,0,x,3,=,1,),由上表可知：,x,1,=,0,x,2,=,0,x,3,=,1,是一个可行解，为尽快找到最优解，可将,3,x,1,2,x,2,5,x,3,5,作为一个约束，凡是目标函数值小于,5,的组合不必讨论，如下表。,x,1,.x,2,.x,3,约束条件,满足条件,Z,值,(0)(1)(2)(3)(4),是 否,(0.0.0 ),0 0 0 0 0,0,(0.0.1),5,1 1 0 1,5,(0.1.0),-2,(0.1.1),3,(1.0.0),3,(1.0.1),8 0 2 1 1,8,(1.1.0),1,(1.1.1),4,0,1,整数规划,指派问题的数学模型,设,n,个人被分配去做,n,件工作，已知第,i,个人去做第,j,件工作的的效率为,C,ij,(,i,=1.2,n,;,j,=1.2,n,),并假设,C,ij,0,。问应如何分配才能使总效率（时间或费用）最高？,指派问题,设决策变量,1,分配第,i,个人去做第,j,件工作,x,ij,=,0,相反,(,I,j,=1.2.,n,),解题步骤：,第一步：变换指派问题的系数矩阵（,c,ij,）为,(,b,ij,),，使在,(,b,ij,),的各行各列中都出现,0,元素，即,(1),从（,c,ij,）的每行元素都减去该行的最小元素；,(2),再从所得新系数矩阵的每列元素中减去该列的最小元素。,第二步：进行试指派，以寻求最优解。,在,(,b,ij,),中找尽可能多的独立,0,元素，若能找出,n,个独立,0,元素，就以这,n,个独立,0,元素对应解矩阵,(,x,ij,),中的元素为,1,，其余为,0,，这就得到最优解。找独立,0,元素，常用的步骤为：,指派问题,(1),从只有一个,0,元素的行,(,列,),开始，给这个,0,元素加圈，记作。然后划去 所在列,(,行,),的其它,0,元素，记作,；这表示这列所代表的任务已指派完，不必再考虑别人了。,(2),给只有一个,0,元素的列,(,行,),中的,0,元素加圈，记作；然后划去 所在行的,0,元素，记作,(3),反复进行,(1),，,(2),两步，直到尽可能多的,0,元素都被圈出和划掉为止。,(4),若仍有没有划圈的,0,元素，且同行,(,列,),的,0,元素至少有两个，则从剩有,0,元素最少的行,(,列,),开始，比较这行各,0,元素所在列中,0,元素的数目，选择,0,元素少的那列的这个,0,元素加圈,(,表示选择性多的要“礼让”选择性少的,),。然后划掉同行同列的其它,0,元素。可反复进行，直到所有,0,元素都已圈出和划掉为止。,（,5,）若 元素的数目,m,等于矩阵的阶数,n,，那么这指派问题的最优解已得到。若,m,n,则转入下一步。,指派问题,第三步：作最少的直线覆盖所有,0,元素。,(1),对没有的行打号；,(2),对已打号的行中所有含,元素的列打号；,(3),再对打有号的列中含 元素的行打号；,(4),重复,(2),，,(3),直到得不出新的打号的行、列为止；,(5),对没有打号的行画横线，有打号的列画纵线，这就得到覆盖所有,0,元素的最少直线数,l,。,l,应等于,m,，若不相等，说明试指派过程有误，回到第二步,(4),，另行试指派；若,l,m,n,，须再变换当前的系数矩阵，以找到,n,个独立的,0,元素，为此转第四步。,指派问题,第四步：变换矩阵,(,b,ij,),以增加,0,元素。,在没有被直线覆盖的所有元素中找出最小元素，然后打各行都减去这最小元素；打各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。,任务,人员,A,B,C,D,甲,2,15,13,4,乙,10,4,14,15,丙,9,14,16,13,丁,7,8,11,9,指派问题,2,4,9,7,指派问题,4,2,指派问题,指派问题,有一份中文说明书，需译成英、日、德、俄四种文字，分别记作,A,、,B,、,C,、,D,。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？,任务,人员,A,B,C,D,甲,6,7,11,2,乙,4,5,9,8,丙,3,1,10,4,丁,5,9,8,2,指派问题,求解过程如下：,第一步，变换系数矩阵：,5,第二步，试指派：,找到,3,个独立零元素,但,m=3 n=4,指派问题,第三步，作最少的直线覆盖所有,0,元素：,独立零元素的个数,m,等于最少直线数,l,，即,l,m=3=12;,x3+x4+x5+x6+x7=15;,x1+x4+x5+x6+x7=12;,x1+x2+x5+x6+x7=14;,x1+x2+x3+x6+x7=16;,x1+x2+x3+x4+x7=18;,x1+x2+x3+x4+x5=19;,gin,(x1);,gin,(x2);,gin,(x3);,gin,(x4);,gin,(x5);,gin,(x6);,gin,(x7);,End,返回,Global optimal solution found at iteration:9,Objective value:4400.000,Variable Value Reduced Cost,X1 5.000000 0.000000,X2 2.000000 0.000000,X3 8.000000 0.000000,X4 0.000000 0.000000,X5 4.000000 0.000000,X6 0.000000 66.66667,X7 3.000000 0.000000,注解,该问题本质上是个整数规划问题，放松的线性规划的最优解是个整数解，所以两规划等价。,定义整数变量用函数,gin,(x1),gin,(x7);,0-1,整数变量为,bin(x1,),应急选址问题,某城市要在市区设置,k,个应急服务中心,经过初步筛选确定了,m,个备选地，现已知共有,n,个居民小区，各小区到个备选地的距离为 为了使得各小区能及时得到应急服务，要求各小区到最近的服务中心的距离尽可能的短，试给出中心选址方案。,问题分析,该问题与传统的选址问题的主要区别在于其目标不再是要求费用最小，而是要求最长距离最短。也就是离服务中心距离最远的小区离最近的服务中心距离最小。,变量,：当中心的位置确定下来后，各小区对应的最近中心也就确定，所以真正的变量也就是小区的位置。设,问题分析,为了便于说明问题引入间接变量，第,i,小区是否由第,j,个中心服务,以及最远的距离,约束条件,小区服务约束,问题分析,最远距离约束,中心个数约束,目标函数：最远距离 最小,模 型,3.4,求解整数规划的蒙特卡洛方法,在,3.4,中介绍的分枝定界方法，算法的每一个计算步骤都是固定的，而且可以保证求得最优解。但是，当整数线性规划的决策变量数目很大时，分枝定界法的代价可能是巨大的；特别是当整数规划本身是非线性的时候，尚未有一种成熟而有效的求解方法，因为非线性规划本身的通用有效解法尚未找到。,然而，由于整数规划解的数目是有限的，于是为枚举法提供了方便。当然，当决策变量数目很大、取值范围很宽情况下，企图用完全搜索（即穷举法）计算出最优值是不现实的，但是应用蒙特卡洛算法，在一定的计算量下，完全可以得出一个满意解。,例,3.4.1,已知非线性整数规划为：,max,s.t.,Z,=,x,1,2,x,2,2,3,x,3,2,4,x,4,2,2,x,5,2,8,x,1,2,x,2,3,x,3,x,4,2,x,5,x,1,x,2,x,3,x,4,x,5,400,x,1,2,x,2,2,x,3,x,4,6,x,5,800,2,x,1,x,2,6,x,3,200,x,3,x,4,5,x,5,200,5,x,1,9,x,2,45,0,x,i,99,，,i,=1,2,3,4,5,对该问题，目前尚无有效方法求出准确的最优解。如果用穷举法（完全搜索）试探，共需计算,100,5,=10,10,个点，计算量非常大。然而概率理论能够保证，应用蒙特卡洛方法随机计算,10,6,个点，便可找到问题的满意解。,解：用蒙特卡洛方法求解这个问题必须借助计算机来实现。,运行程序,5,次，可得如下表 所示的结果：,运行程序,最优解,最优值,第一次运行,x,=(2,93,13,99,10),T,48024,第二次运行,x,=(9,98,4,99,17),T,48558,第三次运行,x,=(34,95,5,98,9),T,48097,第四次运行,x,=(50,91,1,98,15),T,48517,第五次运行,x,=(38,99,3,99,3),T,49866,注,：蒙特卡洛（,Monte Carlo,）算法是一种随机搜索算法，它允许算法在执行的过程中随机选择下一个计算步骤。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时，因此蒙特卡洛算法可在很大程度上降低算法的复杂度。但另一方面，同一实例用蒙特卡洛算法求解两次可能得到完全不同的结果，也就是说，用蒙特卡洛算法能够求得问题的一个解，但无法判断这个解是否正确，求得正确解的概率依赖于算法所用的时间，算法所用的时间越多，得到正确解的概率就越高。,3.5,范例,招聘计划,招聘计划,：一家保姆服务公司专门向顾主提供保姆服务。根据估计，下一年的需求是：春季,6000,人日，夏季,7500,人日，秋季,5500,人日，冬季,9000,人日。公司新招聘的保姆必须经过,5,天的培训才能上岗，每个保姆每季度工作（新保姆包括培训）,65,天。保姆从该公司而不是从顾主那里得到报酬，每人每月工资,800,元。春季开始时公司拥有,120,名保姆，在每个季度结束后，将有,15%,的保姆自动离职。,(1),如果公司不允许解雇保姆，请你为公司制定下一年的招聘计划；哪些季度需求的增加不影响招聘计划？可以增加多少？,(2),如果公司在每个季度结束后允许解雇保姆，请为公司制定下一年的招聘计划。,解,：,(1),设,4,个季度开始时公司新招聘的保姆数分别为,x,1,，,x,2,，,x,3,，,x,4,人，,4,个季度开始时保姆总数量分别为,S,1,，,S,2,，,S,3,，,S,4,人。以本年度付出的总报酬最少（即,4,个季度开始时保姆总数量之和最小）为目标，则模型为,min,Z,=,S,1,+,S,2,+,S,3,+,S,4,s.t.65,S,1,6000+5,x,1,65,S,2,7500+5,x,2,65,S,3,5500+5,x,3,65,S,4,9000+5,x,4,S,1,=120+,x,1,S,2,=0.85,S,1,+,x,2,S,3,=0.85,S,2,+,x,3,S,4,=0.85,S,3,+,x,4,x,1,x,2,x,3,x,4,S,1,S,2,S,3,S,4,Z,+,虽然模型要求,x,1,，,x,2,，,x,3,，,x,4,，,S,1,，,S,2,，,S,3,，,S,4,为正整数，但因为保姆数量较大，因此可以近似看作实数来处理。此外，由于非整数因子,0.85,的影响，如果要求,x,1,，,x,2,，,x,3,，,x,4,，,S,1,，,S,2,，,S,3,，,S,4,为整数，则可能使得新招聘的保姆数量远远超出实际需要的数量，从而难以找到合理的整数解。,将上述整数规划模型松弛成线性规划模型，用,Matlab,求解得：,对上述结果取整，,4,个季度开始时公司新招聘的保姆数量分别为,0,，,15,，,0,，,59,人。,x,1,=0.0000,S,1,=120.0000,x,2,=14.5000,S,2,=116.5000,x,3,=0.0000,S,3,=99.0250,x,4,=58.8145,S,4,=142.9857,由于春季开始时公司拥有,S,1,=120,名保姆，且春季开始时公司招聘的保姆数量为,x,1,=0,，因此，根据约束条件,65,S,1,6000+5,x,1,知，春季需求的增加不影响招聘计划，且可以增加,65,S,1,6000=1800,人日。,类似地，秋季需求的增加也不影响招聘计划，且可以增加,65,S,3,5500=936,人日。,(2),设,4,个季度开始时公司新招聘的保姆数分别为,x,1,，,x,2,，,x,3,，,x,4,人，,4,个季度结束时公司解雇的保姆数分别为,y,1,，,y,2,，,y,3,，,y,4,人，,4,个季度开始时保姆总数量分别为,S,1,，,S,2,，,S,3,，,S,4,人。以本年度付出的总报酬最少（即,4,个季度开始时保姆总数量之和最小）为目标，则模型为,min,Z,=,S,1,+,S,2,+,S,3,+,S,4,s.t.65,S,1,6000+5,x,1,65,S,2,7500+5,x,2,65,S,3,5500+5,x,3,65,S,4,9000+5,x,4,S,1,=120+,x,1,S,2,=0.85,S,1,+,x,2,y,1,S,3,=0.85,S,2,+,x,3,y,2,S,4,=0.85,S,3,+,x,4,y,3,x,i,y,i,S,i,Z,+,i,=1,2,3,4,谢谢,