资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 整数规划与分配问题,1,整数规划的特点及作用,2,分配问题与匈牙利法,3,分枝定界法,4,割平面法,5,解,0-1,规划问题的隐枚举法,1,整数规划的特点及应用,在实际问题中，全部或部分变量的取值必须是整数。比如人或机器是不可分割的，选择建厂地点可以设置逻辑变量等。,在一个线性规划问题中要求全部变量取整数值的，称纯整数线性规划或简称,纯整数规划,；只要求一部分变量取整数值的，称为,混合整数规划,。,对整数规划问题求解，有人认为可以不考虑对变量的整数约束，作为一般线性规划问题求解，当解为非整数时，用四舍五入或凑整方法寻找最优解，我们从下面的例子说明这样的方法是不合适的。,例,1.,求下述整数规划问题的最优解,解,：如果不考虑整数约束（称为整数规划问题的,松弛问题,）用图解法得最优解为（,3.25 , 2.5,）,考虑到整数约束，用凑整法求解时，比较四个点（,4 , 3,）,（,4 , 2,）,（,3 , 3,）（,3 , 2,），前三个都不是可行解，第四个虽然是可行解，但,z=13,不是最优。实际问题的最优解为（,4 , 1,）这时,z,*,= 14,。,逻辑,（,0-1,）,变量在建立数学模型中的作用,1.,m,个约束条件中只有,k,个起作用,设,m,个约束条件可以表示为：,定义逻辑变量,又设,M,为任意大的正数，则约束条件可以改写为：,定义逻辑变量：,此时约束条件可以改写为：,2.,约束条件的右端项可能是,r,个值中的某一个,即,3.,两组条件满足其中一组,若,x,1,4,，则,x,2,1,（,第一组条件,）；否则当,x,1, 4,时，,x,2,3,（,第二组条件,）,.,定义逻辑变量：,又设,M,为任意大正数，则问题可表达为：,需注意，当约束为大于时，右端项中用减号。,4.,用以表示含固定费用的函数,用,x,j,代表产品,j,的生产数量，其生产费用函数表示为,其中,K,j,是同产量无关的生产准备费用，问题的目标是使所有产品的总生产费用为最小，即,定义逻辑变量（表示是否生产产品,j,）,又设,M,为任意大正数，为了表示上述定义，引入约束：,显然，当,x,j, 0,时，,y,j,=,1,。,将目标函数与约束条件合起来考虑有：,由此看出，当,x,j,=,0,时，为使,z,极小化，应有,y,j,= 0,2,分配问题与匈牙利法,一、问题的提出与数学模型,分配问题,也称,指派问题,（,assignment problem,），是一种特殊的整数规划问题。假定有,m,项任务分配给,m,个人去完成，并指定每人完成其中一项，每项只交给其中一个人去完成，应如何分配使总的效率为最高。,如果完成任务的效率表现为资源消耗，考虑的是如何分配任务使得目标极小化；如果完成任务的效率表现为生产效率的高低，则考虑的是如何分配使得目标函数极大化。,在分配问题中，利用不同资源完成不同计划活动的效率通常用表格形式表示为效率表，表格中数字组成,效率矩阵,。,例,2,.,有一份说明书，要分别翻译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，使这四个人分别完成四项任务总的时间为最小。效率表如下：,效率矩阵用,a,ij,表示，为,定义逻辑变量,则分配问题的数学模型写为：,二、匈牙利法,用表上作业法来求解分配问题时，单位运价表即效率表，产销平衡表中产量和销量都设为,1,即可。,匈牙利数学家克尼格（,Konig,）求解分配问题的计算方法被成为,匈牙利法,，他证明了如下两个定理：,定理,1,如果从分配问题效率矩阵,a,ij,的每一行元素中分别减去（或加上）一个常数,u,i,(,被称为该行的位势,),，从每一列分别减去（或加上）一个常数,v,j,（被称为该列的位势），得到一个新的效率矩阵,b,ij,，若其中,b,ij,=,a,ij,-,u,i,-,v,j,，则,b,ij,的最优解等价于,a,ij,的最优解。,定理,2,若矩阵,A,的元素可分成“,0 ”,与非“,0 ”,两部分，则覆盖“,0 ”,元素的最少直线数等于位于不同行不同列的“,0 ”,元素的最大个数。,结合例,2,说明,匈牙利法的计算步骤,第一步：找出效率矩阵每行的最小元素，并分别从每行中减去。,第二步：找出矩阵每列的最小元素，分别从各列中减去。,第三步：经过上述两步变换后，矩阵的每行每列至少都有了一个零元素。下面确定能否找出,m,个位于不同行不同列的零元素的集合（该例中,m,=4,），也就是看要覆盖上面矩阵中的所有零元素，至少需要多少条直线。,1.,从第一行开始，若该行只有一个零元素，就对这个零元素打上（ ），对打括号的零元素所在的列画一条线，若该行没有零元素或者有两个以上零元素（已划去的不算在内），则转下一行，依次进行到最后一行。,2.,从第一列开始，若该列只有一个零元素，就对这个零元素打上（ ）（同样不考虑已划去的零元素），再对打括号的零元素所在行画一条直线。若该列没有零元素或有两个以上零元素，则转下一列，依次进行到最后一列为止。,3.,重复上述步骤,1,、,2,，可能出现三种情况：,效率矩阵每行都有打括号的零元素，只要对应这些元素令,x,ij,= 1,就找到了最优解。,打括号的零元素个数少于,m,，但未被划去的零元素之间存在闭回路，这时顺着闭回路的走向，对每个间隔的零元素打一个括号，然后对所有打括号的零元素所在行（或列）画一条直线，同样得到最优解。,矩阵中所有零元素或被划去，或打上括号，但打括号的零元素少于,m,，这时转入第四步。,第四步：按定理,1,进行如下变换,1.,从矩阵未被直线覆盖的数字中找出一个最小的,k,；,2.,对矩阵中的每行，当该行有直线覆盖时，令,u,i,= 0,，无直线覆盖的，令,u,i,=,k,；,3.,对矩阵中有直线覆盖的列，令,v,j,= -,k,，对无直线覆盖的列，令,v,j,= 0,；,4.,从原矩阵的每个元素,a,ij,中分别减去,u,i,和,v,j,。,第五步：回到第三步，反复进行，直到矩阵的每一行都有一个打括号的零元素为止，即找到最优分配方案。,由于调整后的矩阵中新出现了一个零，因此对打括号的元素重新进行调整，得到如下矩阵，这时只要把打括号元素所对应的决策变量取值为,1,，就得到最优解。,该问题中，最优值为：,4+4+9+11=28h,三、两点说明,1.,分配问题中人数和工作任务不相等时,当人数多于工作任务数时，可以添加假想任务使得人数与工作任务数相同，因为工作任务是假想的，因此完成这些任务的时间是零。当任务数多于人数时，可添加假想的人。这样的方法和运输问题中处理的方法类似。,2.,当问题目标变为求极大时,可改写为,此时效率矩阵中元素都变为了负值，可利用定理,1,，使效率矩阵中全部元素都变为非负的，就可以利用匈牙利法进行求解。,3,分枝定界法,记待解的整数规划问题为,L,，相应的线性规划问题,(,去掉了整数约束，即松弛问题,),为,L,0,，整数规划的最优值为,z,*,。,分枝定界法的基本思想：,（,1,）先不考虑整数条件，即先求解相应线性规划,L,0,的最优解。若得到的是整数解，则问题得到解决,;,否则，这个非整数解必是原整数规划问题,L,的最优解,z,*,的上界，记为 ；而,L,的任一整数解，可以看作一个下界，记为,。,（,2,）从得到的,L,0,的最优解中，任选一个非整数的变量,x,k,，在,L,0,中增加约束条件,x,k,x,k,构成一个新的线性规划问题,L,1,，它实际上是,L,0,的一个分枝；在,L,0,中增加另一约束条件,x,k,x,k,+1,，又得到一个,L,0,的分支，记为,L,2,；分别求出,L,1,和,L,2,的最优解，判断这两个解是否是最优解，若是，问题得到解决；若不是，调整 和 ，将它们再分枝，直到求出最优整数解为止。,分枝定界法实质是将,L,0,的可行域分成若干子区域,(,称为分枝,),，逐渐减小 和增大 ，最终求出,z,*,。,例,.,用分枝定界法求解整数规划问题：,解,：,（,1,）求解对应的松弛问题,L,0,其最优解为：,最优值为：,目前最优值为,z=14.75,，令,=14.75,；,现在还没有任何整数解，可以令（,0,，,0,）作为初始整数解，因此有,=0,。,（,2,）定界,（,3,）分枝,将线性规划问题,L,0,分为两枝。,在,L,0,的最优解中，任选一个非整数变量，如,x,2,=2.5,；因,x,2,的最优整数解只可能是,x,2,2,或,x,2,3,，故在,L,0,中分别增加约束条件：,L,0,加上约束条件,x,2,2,，记为,L,1,；,L,0,加上约束条件,x,2,3,，记为,L,2,。这样，将分解成两个子问题,L,1,和,L,2,（即两枝）。,这样松弛问题,L,0,变为了求解下述两个问题：,L,0,分解为,L,1,和,L,2,：,L,1,的最优解为：,x,1,=3.5 ,x,2,=2 , z=14.5,L,2,的最优解为：,x,1,=2.5 ,x,2,=3 , z=13.5,定界：,这时两个问题的最优值中较大的一个是,14.5,，比原来的上界要小，因此修改上界，令 。,又由于目前没有出现更好的整数界，所以下界仍然是,0,。,分枝：,选取最优值较大的子问题优先进行分枝，将,L,1,分解为,L,11,和,L,12,两个子问题。,L,11,和,L,12,两个子问题的可行域为：,继续分枝定界，最后剪枝求解得最优解（,4 , 1,），最优解为,14,。,(,见,P93,，图,4.5),4,割平面法,割平面法是求解整数规划问题最早提出的一种方法，,1958,年由高莫雷（,Gomory,）提出。,基本思路是不断引进适当的线性约束条件，使得可行域逐步缩小，但每次切割只是割去问题的部分非整数解，直到使问题的目标值达到最优的整数点成为缩小后可行域的一个顶点，这样就可以用求解线性规划的方法找出这个最优解。,例,.,用割平面法求解整数规划问题：,解,：,（,1,）约束条件系数化整，忽略整数约束，用单纯形法求解对应的松弛问题,C,j,x,1,x,2,x,3,x,4,X,B,b,C,B,0 1 1/2 -1/2 1 0 -1/4 3/4,3 2 0 0,5/2 13/4,x,2,x,1,23,c,j,- z,j,0,0,-1/4,-5/4,得最终单纯形表：,（,2,）找出非整数解变量中分数部分最大的基变量，并写下这行约束,（,4,）重复第一至第三步一直到找出问题的整数最优解为止。（具体求解过程,P95,）,在这个问题的求解过程中，依次加入了两个约束条件（割了两次平面），问题变为：,图示割平面,最优解为（,4 , 1,）这时,z,*,= 14,。,(1),(2),步骤：,化标准形,(,隐枚举法,),：,1),目标函数极小化,2),约束条件化成,3),使目标函数系数皆为非负,若,x,j,系数为负值,则令,x,j,=1-x,j,4),使目标函数按变量系数由小大顺序排列，约束条件变 量排列的顺序要与之对应。,令所有变量,x,j,=0,，计算边界目标函数值,z,，检查是否满足所有约 束条件，若满足，即为最优解；否则，分枝计算。,分枝：按变量次序依次令各变量取“,1”,和“,0”,值，计算边界值，然后 检查是否满足所有约束，若满足，转下步；否则继续分枝。,剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。,(a),对可行解，保留边界值最小的一枝,z,min,，其余全剪掉；,(b) z,min,分枝，剪掉；,(c),能判断出为无可行解的分枝，剪掉；,(d),非上述情况，继续分枝。,5,解,0-1,规划问题的隐枚举法,例：求解下述,0-1,规划问题：,Max z=8x,1,+2x,2,-4x,3,-7x,4,-5x,5,st. 3x,1,+3x,2,+x,3,+2x,4,+3x,5,4 5,x,1,+3x,2,- 2x,3,- x,4,+ x,5,4 x,j,=0,或,1 (j=1,2,3,4,5),1),目标函数极小化,:,min z,=-8x,1,-2x,2,+4x,3,+7x,4,+5x,5,化标准形：,2),约束条件,：,-3x,1,-3x,2,-x,3,-2x,4,-3x,5,-4,-5,x,1,-3x,2,+ 2x,3,+ x,4,- x,5,-4,x,j,=0,或,1 (j=1,2,3,4,5),3),使目标函数系数皆为正：,令,x,1,=1-x,1,，,x,2,=1-x,2,min z,=-8+8 x,1,-2+2 x,2,+4x,3,+7x,4,+5x,5,st. -3+3 x,1,-3+3 x,2,-x,3,-2x,4,-3x,5,-4,-5+5,x,1,-3+3 x,2,+ 2x,3,+ x,4,- x,5,-4,x,1, ,x,2, ,x,j,=0,或,1 (j=3,4,5),4),变量按顺序排列：,min z,= 2 x,2,+4x,3,+5x,5,+7x,4,+8 x,1,-10,st. 3 x,2,-x,3,-3x,5,-2x,4,+3 x,1,2,3 x,2,+ 2x,3,- x,5,+ x,4,+5,x,1, 4,x,1, ,x,2, ,x,j,=0,或,1 (j=3,4,5),求解图示：,1,2,3,4,5,6,7,8,9,10,11,z,=-10,z,=-,8,z,=-4,z,=-6,z,=-5,z,=-1,z,=1,z,=-5,z,=-3,z,=-6,x,2,=1,x,2,=0,x,3,=1,x,3,=0,x,3,=1,x,3,=0,x,5,=1,x,5,=0,x,5,=1,x,5,=0,z,=-3,min z,= 2 x,2,+4x,3,+5x,5,+7x,4,+8 x,1,-10,st. 3 x,2,-x,3,-3x,5,-2x,4,+3 x,1,2,3 x,2,+ 2x,3,- x,5,+ x,4,+5,x,1, 4,x,1, ,x,2, ,x,j,=0,或,1 (j=3,4,5),
展开阅读全文