《运筹学》整数规划(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,Page,*,Chapter5,整数规划,(Integer Programming),整数规划的特点及应用,分支定界法,分配问题与匈牙利法,本章主要内容：,整数规划的特点及应用,整数规划（简称：,IP,）,要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。,整数线性规划数学模型的一般形式：,整数规划的特点及应用,整数线性规划问题的种类：,纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。,混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。,0-1,型整数线性规划：决策变量只能取值,0,或,1,的整数线性规划。,整数规划的特点及应用,整数规划的典型例子,例,5.1,工厂,A,1,和,A,2,生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有,A,3,和,A,4,两个。这种物资的需求地有,B,1,B,2,B,3,B,4,四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费,c,ij,，见下表：,B1,B2,B3,B4,年生产能力,A1,2,9,3,4,400,A2,8,3,5,7,600,A3,7,6,1,2,200,A4,4,5,2,5,200,年需求量,350,400,300,150,工厂,A3,或,A4,开工后，每年的生产费用估计分别为,1200,万或,1500,万元。现要决定应该建设工厂,A3,还是,A4,，才能使今后每年的总费用最少。,整数规划的特点及应用,解：这是一个物资运输问题，特点是事先不能确定应该建,A3,还是,A4,中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入,0-1,变量：,再设,x,ij,为由,A,i,运往,B,j,的物资数量，单位为千吨；,z,表示总费用，单位万元。,则该规划问题的数学模型可以表示为：,整数规划的特点及应用,混合整数规划问题,整数规划的特点及应用,例,5.2,现有资金总额为,B,。可供选择的投资项目有,n,个，项目,j,所需投资额和预期收益分别为,a,j,和,c,j,（,j,1,2,.,n,），此外由于种种原因，有三个附加条件：,若选择项目,1,，就必须同时选择项目,2,。反之不一定,项目,3,和,4,中至少选择一个；,项目,5,6,7,中恰好选择,2,个。,应该怎样选择投资项目，才能使总预期收益最大。,整数规划的特点及应用,解：对每个投资项目都有被选择和不被选择两种可能，因此分别用,0,和,1,表示，令,x,j,表示第,j,个项目的决策选择，记为：,投资问题可以表示为：,整数规划的特点及应用,例,5.3,指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。,工作人员,A,B,C,D,甲,85,92,73,90,乙,95,87,78,95,丙,82,83,79,90,丁,86,90,80,88,整数规划的特点及应用,设,数学模型如下：,要求每人做一项工作，约束条件为：,整数规划的特点及应用,每项工作只能安排一人，约束条件为：,变量约束：,整数规划的特点及应用,整数规划问题解的特征：,整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。,整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的目标函数值不会优于后者最优解的目标函数值。,整数规划的特点及应用,例,5.3,设整数规划问题如下,首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。,整数规划的特点及应用,用图解法求出最优解为：,x,1,3/2,x,2,=10/3,，且有,Z=29/6,现求整数解,(,最优解,):,如用舍入取整法可得到,4,个点即,(1,，,3),(2,，,3),(1,，,4),(2,，,4),。显然，它们都不可能是整数规划的最优解。,x,1,x,2,3,3,(3/2,10/3),按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如右图所示。,其中,(2,2),(3,1),点的目标函数值最大，即为,Z=4,。,整数规划的特点及应用,整数规划问题的求解方法：,分支定界法和割平面法,匈牙利法（指派问题）,分支定界法,1,）求整数规划的松弛问题最优解；,若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则转下一步；,2,）分支与定界：,任意选一个非整数解的变量,x,i,，在松弛问题中加上约束：,x,i,x,i,和,x,i,x,i,+1,组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。,检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（,max,）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于,(max),整数解的目标值，需要继续分枝，再检查，直到得到最优解。,分支定界法的解题步骤：,分支定界法,例,5.4,用分枝定界法求解整数规划问题,解：首先去掉整数约束，变成一般线性规划问题,(,原整数规划问题的松驰问题,),LP,IP,分支定界法,用图解法求松弛问题的最优解，如图所示。,x,1,x,2,3,(18/11,40/11),2,1,1,2,3,x,1,18/11,x,2,=40/11,Z=,218/11(,19.8),即,Z,也是,IP,最小值的下限。,对于,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,）,取,x1 1,x1 2,分支定界法,分支：,分别求出（,LP1,）和（,LP2,）的最优解。,分支定界法,先求,LP1,如图所示。此时在,B,点取得最优解。,x,1,1,x,2,=3,Z,(1),16,找到整数解，问题已探明，此枝停止计算。,x,1,x,2,3,3,(18/11,40/11),1,1,B,A,C,同理求,LP2,如图所示。在,C,点取得最优解。即,:,x,1,2,x,2,=10/3,Z,(2),56/3,18.7,Z,(2),Z,(1),16,原问题有比,16,更小的最优解，但,x2,不是整数，故继续分支。,分支定界法,在,IP2,中分别再加入条件：,x,2,3,x,2,4,得下式两支：,分别求出,LP21,和,LP22,的最优解,分支定界法,x,1,x,2,3,3,(18/11,40/11),1,1,B,A,C,D,先求,LP21,如图所示。此时,D,在点取得最优解。,即,x,1,12/52.4,x,2,=3,Z,(21),-87/5-17.4 Z,(211),如对,LP212,继续分解，其最小值也不会低于,15.5,，问题探明,剪枝。,分支定界法,原整数规划问题的最优解为,:,x,1,=2,x,2,=3,Z*,=,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,LP21,x,1,=12/5,x,2,=3,Z,(21),17.4,LP22,无可,行解,LP211,x,1,=2,x,2,=3,Z,(211),17,LP212,x,1,=3,x,2,=5/2,Z,(212),15.5,x,1,1,x,1,2,x,2,3,x,2,4,x,1,2,x,1,3,分支定界法,例,5.5,用分枝定界法求解,解,:,先求对应的松弛问题（记为,LP,0,）,用图解法得到最优解,X,(3.57,7.14),Z,0,=35.7,如下图所示。,分支定界法,10,10,松弛问题,LP,0,的最优解,X,=(3.57,7.14),Z,0,=35.7,x,1,x,2,o,A,B,C,分支定界法,10,x,2,o,A,B,C,LP,1,LP,2,3,4,LP,1:,X,=(3,7.6),Z,1,=34.8,LP,2:,X,=(4,6.5),Z,2,=35.5,分支定界法,10,x,1,x,2,o,A,B,C,LP,1,LP,21,3,4,LP,21:,X,=(4.33,6),Z,21,=35.33,6,分支定界法,10,x,1,x,2,o,A,C,LP,1,3,4,6,LP,211:,X,=(4,6),Z,211,=34,LP,212:,X,=(5,5),Z,212,=35,5,LP,212,分支定界法,上述分枝过程可用下图表示：,LP,0:,X,=(3.57,7.14),Z,0,=35.7,LP,1:,X,=(3,7.6),Z,1,=34.8,LP,2:,X,=(4,6.5),Z,2,=35.5,x,1,3,x,1,4,LP,21:,X,=(4.33,6),Z,21,=35.33,x,2,6,LP,211:,X,=(4,6),Z,211,=34,LP,212:,X,=(5,5),Z,212,=35,x,1,4,x,1,5,LP,22,无可行解,x,2,7,小结,学习要点：,掌握一般整数规划问题概念及模型结构,掌握分支定界法原理,能够用分支定界法求解一般整数规划问题,分配问题与匈牙利法,指派问题的数学模型的标准形式：,设,n,个人被分配去做,n,件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第,i,个人去做第,j,件工作的效率（时间或费用）为,C,ij,(i=1.2,n;j=1.2,n),并假设,C,ij,0,。问应如何分配才能使总效率（时间或费用）最高？,设决策变量,分配问题与匈牙利法,指派问题的数学模型为：,分配问题与匈牙利法,克尼格定理,:,如果从分配问题效率矩阵,a,ij,的每一行元素中分别减去,(,或加上,),一个常数,u,i,，从每一列中分别减去,(,或加上,),一个常数,v,j,，得到一个新的效率矩阵,b,ij,，则以,b,ij,为效率矩阵的分配问题与以,a,ij,为效率矩阵的分配问题具有相同的最优解。,分配问题与匈牙利法,指派问题的求解步骤：,1),变换指派问题的系数矩阵,(c,ij,),为,(b,ij,),，使在,(b,ij,),的各行各列中都出现,0,元素，即,从,(c,ij,),的每行元素都减去该行的最小元素；,再从所得新系数矩阵的每列元素中减去该列的最小元素。,2),进行试指派，以寻求最优解。,在,(b,ij,),中找尽可能多的独立,0,元素，若能找出,n,个独立,0,元素，就以这,n,个独立,0,元素对应解矩阵,(x,ij,),中的元素为,1,，其余为,0,，这就得到最优解。,分配问题与匈牙利法,找独立,0,元素，常用的步骤为：,从只有一个,0,元素的行开始，给该行中的,0,元素加圈，记作。然后划去 所在列的其它,0,元素，记作,；这表示该列所代表的任务已指派完，不必再考虑别人了。依次进行到最后一行。,从只有一个,0,元素的列开始（画,的不计在内），给该列中的,0,元素加圈，记作；然后划去 所在行的,0,元素，记作,，表示此人已有任务，不再为其指派其他任务了。依次进行到最后一列。,若仍有没有划圈的,0,元素，且同行,(,列,),的,0,元素至少有两个，比较这行各,0,元素所在列中,0,元素的数目，选择,0,元素少这个,0,元素加圈,(,表示选择性多的要,“,礼让,”,选择性少的,),。然后划掉同行同列的其它,0,元素。可反复进行，直到所有,0,元素都已圈出和划掉为止。,分配问题与匈牙利法,若 元素的数目,m,等于矩阵的阶数,n,（即：,m,n,）,，那么这指派问题的最优解已得到。若,m,n,则转入下一步。,3),用最少的直线通过所有,0,元素。其方法：,对没有的行打,“,”,；,对已打,“,”,的行中所有含,元素的列打,“,”,；,再对打有,“,”,的列中含 元素的行打,“,”,；,重复、直到得不出新的打号的行、列为止；,对没有打号的行画横线，有打号的列画纵线，这就得到覆盖所有,0,元素的最少直线数,l,。,注：,l,应等于,m,，若不相等，说明试指派过程有误，回到第,2,步，另行试指派；若,l,m n,，表示还不能确定最优指派方案，须再变换当前的系数矩阵，以找到,n,个独立的,0,元素，为此转第,4,步。,分配问题与匈牙利法,4),变换矩阵,(b,ij,),以增加,0,元素,在没有被直线通过的所有元素中找出最小值，没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍相同。转回第,2,步。,分配问题与匈牙利法,例,5.6,有一份中文说明书，需译成英、日、德、俄四种文字，分别记作,A,、,B,、,C,、,D,。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？,任务,人员,A,B,C,D,甲,6,7,11,2,乙,4,5,9,8,丙,3,1,10,4,丁,5,9,8,2,分配问题与匈牙利法,解：,1,）,变换系数矩阵，增加,0,元素。,5,2,）试指派（找独立,0,元素）,找到,3,个独立零元素,但,m=3 n=4,分配问题与匈牙利法,3,）,作最少的直线覆盖所有,0,元素,独立零元素的个数,m,等于最少直线数,l,，即,l,m,=3,n,=4,；,4,）没有被直线通过的元素中选择最小值为,1,，变换系数矩阵，将没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。得到新的矩阵，重复,2,）步进行试指派,分配问题与匈牙利法,0,0,0,0,0,0,试指派,得到,4,个独立零元素，所以最优解矩阵为：,即完成,4,个任务的总时间最少为：,2,4,1+8=15,分配问题与匈牙利法,例,5.7,已知四人分别完成四项工作所需时间如下表，求最优分配方案。,任务,人员,A,B,C,D,甲,2,15,13,4,乙,10,4,14,15,丙,9,14,16,13,丁,7,8,11,9,分配问题与匈牙利法,解：,1,）,变换系数矩阵，增加,0,元素。,2,）试指派（找独立,0,元素）,独立,0,元素的个数为,4,指派问题的最优指派方案即为甲负责,D,工作，乙负责,B,工作，丙负责,A,工作，丁负责,C,工作。这样安排能使总的工作时间最少，为,4,4,9,11,28,。,分配问题与匈牙利法,例,5.8,已知五人分别完成五项工作耗费如下表，求最优分配方案。,任务,人员,A,B,C,D,E,甲,7,5,9,8,11,乙,9,12,7,11,9,丙,8,5,4,6,8,丁,7,3,6,9,6,戊,4,6,7,5,11,分配问题与匈牙利法,-1,-2,解：,1,）变换系数矩阵，增加,0,元素。,分配问题与匈牙利法,2,）试指派（找独立,0,元素）,独立,0,元素的个数,l,45,，故画直线调整矩阵。,分配问题与匈牙利法,选择直线外的最小元素为,1,；直线外元素减,1,，直线交点元素加,1,，其他保持不变。,分配问题与匈牙利法,l,=,m,=4,n,=5,选择直线外最小元素为,1,，直线外元素减,1,，直线交点元素加,1,，其他保持不变，得到新的系数矩阵。,分配问题与匈牙利法,总费用为,=5+7+6+6+4=28,注：此问题有多个最优解,分配问题与匈牙利法,总费用为,=7+9+4+3+5=28,分配问题与匈牙利法,总费用为,=8+9+4+3+4=28,分配问题与匈牙利法,课堂练习：用匈牙利法求解下列指派问题。,练习,1,：,练习,2,：,分配问题与匈牙利法,48,21,答案：,分配问题与匈牙利法,非标准型的指派问题：,匈牙利法的条件是：模型求最小值、效率,c,ij,0,。,当遇到各种非标准形式的指派问题时，处理方法是先将其转化为标准形式，然后用匈牙利法来求解。,分配问题与匈牙利法,1.,最大化指派问题,处理方法：设,m,为最大化指派问题系数矩阵,C,中最大元素。令矩阵,B,（,m-c,ij,）,nn,则以,B,为系数矩阵的最小化指派问题和原问题有相同的最优解。,例,5.9,某人事部门拟招聘,4,人任职,4,项工作，对他们综合考评的 得分如下表（满分,100,分），如何安排工作使总分最多。,分配问题与匈牙利法,解,:M,95,，令,用匈牙利法求解,C,，最优解为：,即甲安排做第二项工作、乙做第三项、丙做第四项、丁做第三项,最高总分,Z,92,95,90,80,357,分配问题与匈牙利法,2.,不平衡的指派问题,当人数,m,大于工作数,n,时，加上,m,n,项虚拟工作，例如：,当人数,m,小于工作数,n,时，加上,n,m,个人，例如,分配问题与匈牙利法,3.,一个人可做几件事的指派问题,若某人可做几件事，则将该人化作相同的几个,“,人,”,来接受指派，且费用系数取值相同。,例如：丙可以同时任职,A,和,C,工作，求最优指派方案。,分配问题与匈牙利法,4.,某事一定不能由某人做的指派问题,将该人做此事的效率系数取做足够大的数，可用,M,表示。,例,5.10,分配甲、乙、丙、丁四个人去完成,A,、,B,、,C,、,D,、,E,五项任务。每个人完成各项任务的时间如表所示。由于任务数多于人数，考虑任务,E,必须完成，其他,4,项中可任选,3,项完成。试确定最优分配方案，使完成任务的总时间最少。,任务,人员,A,B,C,D,E,甲,25,29,31,42,37,乙,39,38,26,20,33,丙,34,27,28,40,32,丁,24,42,36,23,45,分配问题与匈牙利法,解,:1),这是不平衡的指派问题，首先转换为标准型，再用匈牙利法求解。,2),由于任务数多于人数，所以假定一名虚拟人，设为戊。因为工作,E,必须完成，故设戊完成,E,的时间为,M,（,M,为非常大的数），其余效率系数为,0,，则标准型的效率矩阵表示为：,任务,人员,A,B,C,D,E,甲,25,29,31,42,37,乙,39,38,26,20,33,丙,34,27,28,40,32,丁,24,42,36,23,45,戊,0,0,0,0,M,分配问题与匈牙利法,用匈牙利法求出最优指派方案为：,即甲,B,，乙,D,，丙,E,，丁,A,任务,C,放弃。,最少时间为,105,。,