运筹学-整数规划与分配问题PPT.ppt

第四章 整数规划与分配问题,整数规划的特点及作用,分配问题与匈牙利法,分枝定界法,割平面法,应用举例,1 整数规划的特点及应用,在实际问题中，全部或部分变量取值必须是整数。比如人或机器是不可分割的，选择地点可以设置逻辑变量等。,在一个线性规划问题中要求全部变量取整数值的，称纯整数线性规划或简称纯整数规划；只要求一部分变量取整数值的，称为混合整数规划。,对整数规划问题求解，有人认为可以不考虑对变量的整数约束，作为一般线性规划问题求解，当解为非整数时，用四舍五入或凑整方法寻找最优解。,当变量取值较小时，得到的解可能与实际整数最优解差别很大。,若问题中整数变量的数目很大，则凑整方法的组合数目很多。,例1.求下述整数规划问题的最优解,解：如果不考虑整数约束（松弛问题）用图解法得,考虑到整数约束，用凑整法求解时，比较四个点(4,3),(4,2),(3,3),(3,2)，前三个都不是可行解，第四个虽然是可行解，但 z=13 不是最优。实际问题的最优解为（4,1）这时 z*=14。,最优解为(3.25,2.5)。,逻辑（0-1）变量在建立数学模型中的作用,定义逻辑变量,又设 M 为任意大的正数，则约束条件可以改写为：,定义逻辑变量：,此时约束条件可以改写为：,定义逻辑变量：,又设 M 为任意大正数，则问题可表达为：,需注意，当约束为大于时，右端项中用减号。,4.用以表示含固定费用的函数,用 xj 代表产品 j 的生产数量，其生产费用函数表示为,其中 Kj 是同产量无关的生产准备费用，问题的目标是使所有产品的总生产费用为最小，即,定义逻辑变量（表示是否生产产品 j）,又设 M 为任意大正数，为了表示上述定义，引入约束：,显然，当 xj 0 时，yj=1。,将目标函数与约束条件合起来考虑有：,由此看出，当 xj=0 时，为使 z 极小化，应有 yj=0,2 分配问题与匈牙利法,一、问题的提出与数学模型,分配问题也称指派问题（assignment problem），是一种特殊的整数规划问题。假定有 m 项任务分配给 m 个人去完成，并指定每人完成其中一项，每项只交给其中一个人去完成，应如何分配使总的效率为最高。,如果完成任务的效率表现为资源消耗，考虑的是如何分配任务使得目标极小化；如果完成任务的效率表现为生产效率的高低，则考虑的是如何分配使得目标函数极大化。,在分配问题中，利用不同资源完成不同计划活动的效率常用表格形式表示为效率表，表格中数字组成效率矩阵。,例2.有一份说明书，要分别翻译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，使这四个人分别完成四项任务总的时间为最小。效率表如下：,效率矩阵用aij 表示，为,定义逻辑变量,则分配问题的数学模型写为：,二、匈牙利法,用表上作业法来求解分配问题时，单位运价表即效率表，产销平衡表中产量和销量都设为 1 即可。,匈牙利数学家克尼格（Konig）求解分配问题的计算方法被称为匈牙利法，原理是如果效率矩阵所有元素aij=0，而其中存在一组位于不同行不同列的零元素，则只要令对应于这些零元素位置的xij=1即为最优解。,定理1 如果从分配问题效率矩阵 aij 的每一行元素中分别减去（或加上）一个常数 ui(被称为该行的位势)，从每一列分别减去（或加上）一个常数 vj（被称为该列的位势），得到一个新的效率矩阵 bij，若其中 bij=aij-ui-vj，则 bij 的最优解等价于 aij 的最优解。,定理2 若矩阵 A 的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素的最大个数。,结合例2 说明匈牙利法的计算步骤,第一步：找出效率矩阵每行的最小元素，并分别从每行中减去。,第二步：找出矩阵每列的最小元素，分别从各列中减去。,第三步：经过上述两步变换后，矩阵的每行每列至少都有了一个零元素。下面确定能否找出 m 个位于不同行不同列的零元素的集合（该例中 m=4），也就是看要覆盖上面矩阵中的所有零元素，至少需要多少条直线。,1.从第一行开始，若该行只有一个零元素，就对这个零元素打上（），对打括号的零元素所在的列画一条线，若该行没有零元素或者有两个以上零元素（已划去的不算在内），则转下一行，依次进行到最后一行。,2.从第一列开始，若该列只有一个零元素，就对这个零元素打上（）（同样不考虑已划去的零元素），再对打括号的零元素所在行画一条直线。若该列没有零元素或有两个以上零元素，则转下一列，依次进行到最后一列为止。,3.重复上述步骤 1、2，可能出现三种情况：,效率矩阵每行都有打括号的零元素，只要对应这些元素令 xij=1 就找到了最优解。,打括号的零元素个数少于 m，但未被划去的零元素之间存在闭回路，这时顺着闭回路的走向，对每个间隔的零元素打一个括号，然后对所有打括号的零元素所在行（或列）画一条直线，同样得到最优解。,矩阵中所有零元素或被划去，或打上括号，但打括号的零元素少于 m，这时转入第四步。,第四步：按定理 1 进行如下变换,1.从矩阵未被直线覆盖的数字中找出一个最小的 k；,2.对矩阵中的每行，当该行有直线覆盖时，令 ui=0，无直线覆盖的，令 ui=k；,3.对矩阵中有直线覆盖的列，令 vj=-k，对无直线覆盖的列，令 vj=0；,4.从原矩阵的每个元素 aij中分别减去 ui 和 vj。,第五步：回到第三步，反复进行，直到矩阵的每一行都有一个打括号的零元素为止，即找到最优分配方案。,由于调整后的矩阵中新出现了一个零，因此对打括号的元素重新进行调整，得到如下矩阵，这时只要把打括号元素所对应的决策变量取值为1，就得到最优解。,该问题中，最优值为：4+4+9+11=28h,求下面所示效率矩阵的指派问题的最小解,课堂练习,三、两点说明,1.分配问题中人数和工作任务不相等时,当人数多于工作任务数时，可以添加假想任务使得人数与工作任务数相同，因为工作任务是假想的，因此完成这些任务的时间是零。当任务数多于人数时，可添加假想的人。这样的方法和运输问题中处理的方法类似。,2.当问题目标变为求极大时,可改写为,此时效率矩阵中元素都变为了负值，可利用定理1，使效率矩阵中全部元素都变为非负的，就可以利用匈牙利法进行求解。,3 分枝定界法,分枝定界法(branch and bound method)是为了求解同整数规划具有类似性质的一大类问题而设计的一种较好的方法。,结合例一来说明分枝定界法的思路和解题步骤：,例1.求下述整数规划问题的最优解,第一步：寻找替代问题并求解。放宽或取消原问题的某些约束，找出一个替代问题。若替代问题的最优解是原问题的可行解，这个解就是原问题的最优解，否则是源问题最优解的上界(求极大值)或下界(求极小值)。,例1对应的松弛问题 L0,其最优解为：,最优值为：,第二步：分枝与定界。将替代问题分成若干子问题，对子问题也要容易求解，且各子问题的解的集合要包含原问题的解集。然后对每个子问题求最优解，若满足原问题的约束，则找到原问题的可行解，否则该解为所属分枝的边界值；如果所有子问题的最优解均非原问题可行解，则选取边界值最大(求极大值)或最小(求极小值)的子问题再进一步细分子问题求解。分枝过程一直进行下去，直到找到一个原问题的可行解为止。如果计算中同时出现两个以上可行解，则选取其中最大(求极大值)或最小(求极小值)的一个保留。,将线性规划问题 L0 分为两枝。,在 L0 的最优解中，任选一个非整数变量，如 x2=2.5；因 x2 的最优整数解只可能是 x22 或 x23，故在 L0中分别增加约束条件：加上约束条件 x22，记为 L1；加上约束条件 x23，记为 L2。,由于两个子问题的最优解仍非原问题的可行解，故选取最优值较大的子问题L1进行分枝，将分解为 L11和 L12 两个子问题。,L11和 L12 两个子问题的可行域为：,这时两个问题获得的均为可行解，保留可行解中较大的一个,第三步：剪枝，将各子问题边界值与保留的可行解的值进行比较，把边界值劣于可行解的分枝剪去，如果除保留下来的可行解外，其余分枝均被剪去，则该可行解就是原问题的最优解，否则回到第二步，选取边界值最优的一个继续分枝。如果计算又出现新的可行解，则与原可行解比较，保留最优的，并重复上述步骤。,通过剪枝，求解得最优解为（4,1），最优解为14。,用分枝定界法可求解纯整数规划问题和混合整数规划问题，比穷举法优越，但若变量数目很大，其计算量也相当客观。,4 割平面法,割平面法是求解整数规划问题最早提出的一种方法，1958年由Gomory提出，其基本思想是在整数规划问题的松弛问题中依次引进线性约束条件，称为(Gomory约束)，使问题的可行域逐步缩小，但每次切割只割去问题的部分非整数解，直到使问题的最优目标函数点成为缩小后可行域的一个顶点。,例1.求下述整数规划问题的最优解,第一步：把约束条件的系数化成整数，不考虑变量的整数约束,加松弛变量，用单纯形法求解得最终单纯形表：,第二步：找出非整数解变量中分数部分最大的一个基变量，并写下该行约束：,将常数写成整数与一个正的分数值的和；,将整数项移到等式左端：,新约束条件只割去可行域部分非整数解，原有的整数解全部保留,将Gomory约束加到G0得到新的线性规划问题G1，如下：,第四步：重复第一至第三步一直到找出问题的整数最优解为止,由于得到的解仍为非整数解，重复第二步,最终的整数规划解(4,1)已经成为经过两次切割后可行域上的一个顶点，因此可以用单纯型法找出最优解,5 应用举例,清远市下设八个区，下表给出救护车从一个区至另一个区的车程时间(min)，该市拟建救护中心，要求各区离救护中心的车程时间必须在8min以内，问该市至少应建多少个救护中心，建于何处？,根据上表则对于每个区，距离其8min的区至少应该建一个救护站，因此有：,某钻井队要从10个可供选择的井位中确定5个钻井探油，使总的钻探费用最小。若10个井位的代号为S1S10，相应的钻探费用为C1C10，并且井位选择要满足以下条件：或选择S1和S7，或选择S8；选择了S3或S4，就不能选择S5，反之亦然；在S5，S6，S7，S8中最多只能选两个；试建立该问题的整数规划模型。,