[整数规划解法.ppt

4.5 整数规划的解法 分支定界法 割平面法 匈牙利法 4.5.1 整数规划解法 ——分枝定界法 步骤： 1、寻找替代问题并求解 2、分枝与定界 3、剪枝 （2）替代问题的求解 4.5.2 整数规划解法2——割平面法 割平面法的基本思想： 在整数规划问题的松弛问题中依次引进线性约束条件(称Gomory约束，高莫雷约束或割平面)，使问题的可行域逐步缩小。但每次切割时，只割去问题的部分非整数解，而不切割任何整数的可行解，直到使问题的目标函数值达到最优的整数点成为缩小后可行域的一个顶点，这样就可以用求解线性规划问题的方法找出这个最优解。 4.5.3 整数规划的解法——匈牙利法应用于分配问题或指派问题 分配问题也称指派问题，是一种特殊的整数规划问题。 假定有m项任务分配给m个人去完成，并指定每人完成其中一项，每项只交给其中一个人去完成，应如何分配使总的效率为最高。 1、指派问题一般模型的引出 例：有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间(h)如表所示。问：如何分配任务使效率最高（所需总时间最短）？ 指派问题的一般模型 假设： [aij]表示指派问题的效率矩阵 xij表示决策变量，决策变量的取值： 指派问题的一般模型 指派问题的一般数学模型 2、指派问题的求解方法 单纯形法 表上作业法 匈牙利法 （1）指派问题的求解—匈牙利法 核心思路：基于这样一个事实：如果效率矩阵的所有元素aij≥0，而其中存在一组位于不同行、不同列的零元素，则只要令对应于这些零元素的xij=1（分配任务），其余的xij =0，则目标函数z必然会取得最小（0）。 问 题 要求：效率矩阵中存在零元素，同时存在不在同一行、同一列的零元素。 实际的效率矩阵中，是不可能存在0元素的，那么如何获得这种特殊的效率矩阵？ 如何让效率矩阵中产生零元素； 如何让产生的零元素位于不同行和不同列。 （2）零元素的产生方法：匈牙利法的基本定理1 如果从分配问题效率矩阵[aij]的每一行元素中分别减去(或加上)一个常数ui (被称为该行的位势)，从每一列分别减去(或加上)一个常数vj (称为该列的位势)，得到一个新的效率矩阵[bij]，若其中 则[bij]的最优解等价于[aij]的最优解（说明，经过变换后，有零的新效率矩阵取得最优解时，原效率矩阵也同时取得最优解） （3）独立零元素的判断方法：匈牙利法的基本定理2 若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行、不同列的“0”元素的最大个数。 匈牙利法的计算步骤 基本步骤：在效率矩阵中产生零元素→判断独立的零元素个数是否等于任务数或人数？→如是，则对效率矩阵中独立零元素所处的位置进行指派（对应的决策变量为1），完成→如否，则要继续产生足够的独立零元素。 通过实例来说明匈牙利法求解指派问题的过程。 例： 有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间(h)如表所示。问：如何分配任务使效率最高？ 效率矩阵 步骤一：零元素的产生。方法：找出效率矩阵每行的最小元素，并分别从每行中减去它。 步骤二：继续产生零元素方法：再找出矩阵每列的最小元素，再分别从各列中减去它。 步骤三：判断零元素是否位于不同行、不同列？ 经过上述两步变换后，矩阵的每行每列至少都有了一个零元素。 确定能否找出m个位于不同行不同列的零元素的集合(本例中m=4)， 直观法：m很小时，直接判断得到； 非直观法：m很大时，根据一定规则寻找。 非直观法-步骤1（试指派过程） (1) 从任务的角度来挑选从第一行开始，若该行只有一个零元素，就对这个零元素打上( )号。表示该0元素处在单独的一行 同时，对打( )号零元素所在列画一条直线，表示此列已经确定（人员确定），不能再从事其他行的工作（任务） 。 若该行没有零元素或有两个以上零元素(已划去的零元素不计在内)，则转下一行，按照上述方法依次进行到最后一行； 非直观法-步骤2 (2) 从人的角度在行寻找的基础上，从第一列开始，若该列只有一个零元素就对这个零元素打上( )号(同样不考虑已划去的零元素)， 对打( )号零元素所在行画一条直线（任务分配完毕，不能再分配给其他人）。 若该列没有零元素或有两个以上零元素，则转下一列，依次进行到最后一列； 非直观法-步骤3（第一种情形） (3) 重复(1)、(2)两个步骤，可能出现三种情况： ① 效率矩阵每行都有一个打( )号的零元素，很显然，按上述步骤得到的打( )号的零元素都位于不同行不同列，只要令对应打( )号零