系统工程---第四章 整数规划.pptVIP

从只有一个0元素的行（或列）开始，给这个0元素加圈，记作?，然后划去?所在列和行上的其它0元素，记作0； 重复进行1.中的过程，直到所有零元素都被圈出或划掉为止； 若仍有没有划掉的0元素，且同行（列）的0元素至少有两个，则从剩有0元素最少的行（或列）开始，比较这行（或列）各0元素所在列（行）中0元素的数目，选择0元素少的那列（行）的这个0元素加圈，然后划掉同行同列的其它0元素，如此反复进行，直到所有0元素都已圈出或划掉为止； 若?元素的数目m等于矩阵的阶数n，则指派问题（P）的最优解已得到，若mn，则转Step3； 最短工期指派问题举例 例某公司准备将5项工作分派给其下属的5家企业，已知各企业完成每项任务所需时间如下表，若要求每家企业只能接受一项生产任务，而每项生产任务也只能由一家企业来完成，那么该公司应如何安排生产任务，使工期最短？ B1 B2 B3 B4 B5 A1 A2 A3 A4 A5 12 8 6 15 3 6 9 17 14 10 9 6 12 6 7 7 6 14 7 10 9 6 9 10 9 企业 任务 解： (cij) = cij-3 bij-3 bij0 最短工期为max{6, 6, 6, 7, 7}=7个月，同时可知完成所有任务所需总时间为32个月。 最优解矩阵为： 如果以完成所有生产任务所需总时间最少为目标，利用前面的常规指派问题的算法可得到最优解矩阵为： 所需的总时间为30个月， 但其相应工期为 max{6, 6, 9, 6, 3}=9个月。 一、 整数规划简介 整数规划是数学规划的一个重要分支，它研究的是一类要求其部分或全部变量取整数的最优化问题。 要求所有的解xj 为整数，称为纯整数规划 要求部分的xj 为整数，称为混合整数规划 要求xj 的取值只能是0和1 ，称为0-1型整数规划 整数规划数学模型 第四章 整数规划 对应没有整数解要求的线性规划称之为松弛问题 整数规划的解是可数个的，最优解不一定发生在极点 整数规划的最优解不会优于其松弛问题的最优解 整数规划问题A 其松弛问题B 二、整数规划的解法 分枝定界法是一种计算与分析判断相结合的求解整数规划问题的重要方法。它既能解决纯整数规划问题，又能解决混合整数规划问题。这种方法有很强的适应能力，是目前较为成功的求解整数规划问题的一种方法。 1.分枝定界法 基本思想：分枝定界法是通过有系统的“分枝”和“定界”步骤来寻求最优解的。它是先求解松弛问题，如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的方法把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界距离，最后取得整数规划的最优解。 分枝定界法的解题步骤： Step1 求解松弛问题B， -若松弛问题B无解，则整数规划A也无解,则停止。 -若B有最优解，且符合问题A的整数条件，则B的最优解也是 A的最优解，则停止。 -若B有最优解，但不符合A的整数条件，记其目标函数值为f1。 Step2 确定A的最优目标函数值f*的上下界，其上界为f1，即 再用观察法找到A的一个整数可行解，求其目标函数值作为f*的下界，记为f，这时有 Step3 判断 是否等于 。如果 ，则A的最优解即为其目标函数值等于 的那个整数可行解。否则，进行Step4。 Step4 分枝，在B的最优解中任选一个不符合整数条件的变量xj=bj，以[bj]表示小于bj的最大整数。构造两个约束条件： xj≤ [bj] 和 xj ≥ [bj]+1 将这两个约束条件分别加入问题B，得到B的两个分枝B1和B2。 Step5 求解分枝B1, B2。修改A的最优目标函数值的上下界。 在各分枝问题的最优解中，找出最优目标函数值最大者作为新的上界。从已符合整数条件的各分枝中，找出目标函数值最大者作为新的下界，这就是定界过程。 Step6 比较与剪枝。各分枝的最优目标函数中若有小于 者，则剪掉这枝，即以后不再考虑了。若大于 ，且不符合整数条件，则重复Step4至Step6,直至 ，求出整数最优解为止。 各分枝问题的解可能出现的情况 情况 2, 4, 5 找到最优解 情况 3 在缩减的域上继续分枝定界法 情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后续分枝所得到的解进行比较，结论如情况 4或5 例1 解：松弛问题B的最优解为 x1=2.5 , x2=2 , f =23 分枝定界法举例 问题A 松弛问题B 由 x1=2.5 得到两个分枝如下： 显然x1=1 , x2=1是问题A的