整数规划(2012使用版).ppt

第五章 整数规划 （Integer Programming, IP）,5.1 整数线性规划问题的提出 5.2 分支定界法 5.3 指派问题(Assignment problem),2/21,5.1 整数线性规划问题的提出,一、基本概念 要求所有 xj 的解为整数，称为纯(全)整数规划 要求部分 xj 的解为整数，称为混合整数规划 对应没有整数解要求的线性规划称之为松弛问题 整数规划的最优解不会优于其松弛问题的最优解,3/21,二、几个常见整数规划问题的例子 合理下料问题,现要做100套钢架。如何下料，使用的原材料最省。,设 xj 分别代表按方案15下料的原材料根数。,4/21,二、几个常见整数规划的例子 选址问题 有n个城市，需要某种物资的数量为dj , j=1,n ,现计划要建造m座工厂。在各个城市建厂的规模、建设费用以及两城市之间的单位运价见表，问m座工厂应设在何处，使得既能满足需求，又使总投资最省？,单位运价,销地,5/21,二、几个常见整数规划的例子 选址问题 分析：引入逻辑变量表示在某个城市是否建厂。 01变量发挥的作用。（运筹学01规划）,6/21,二、几个常见整数规划的例子 背包问题 一个背包的容积为v，现有n种物品可装，物品j的重量为wj，体积为vj ,（j1,n）。问如何配装，使得既不超过背包的容积，又使装的总重量最大？,注：目标可以是物品所起作用（或价值）最大。应用例子有人造卫星内的物品装载问题、运输中货物装载问题。运筹学动态规划部分介绍求解方法。,7/21,5.2 分支（枝）定界法,5.2.1 思路与解题步骤 只解松弛问题 1、在全部可行性域上解松弛问题 若松弛问题最优解为整数解，则其也是整数规划的最优解 2、分支过程 若松弛问题最优解中某个 xk= bk不是整数，令 bk 为 bk 的整数部分(小于bk 的最大整数) 构造两个新的约束条件 xk bk 和 xk bk +1，分别加于原松弛问题，形成两个新的整数规划 3、求解分支的松弛问题 定界过程 设两个分支的松弛问题分别为问题 1 和问题 2 ，它们的最优解有如下情况,整数线性规划问题的常见解法：分支定界法、 割平面法。,8/21,表5.2.1 分支问题解可能出现的情况,情况 2, 4, 5 找到最优解 情况 3 在缩减的域上继续分支定界法 情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后续分支所得到的解进行比较，结论如情况 4 或 5,9/21,5.2.2 分枝定界法举例,例5.2.1,解：松弛问题的最优解为 x1=2.5, x2=2, z 0 =23 由 x1=2.5 得到两个分支如下：,10/21,表5.2.2 分支问题的松弛解,问题II的解即原整数问题的最优解,可能存在两个分支都是非整数解的情况，可先分支目标函数值较大的（目标实现最大化）那个（也可同时分支），直到有整数解出现，就可以进行定界过程。 当存在很多变量有整数约束时，分支即广又深，在最坏情况下相当于组合所有可能的整数解。 一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如任务分配问题（指派问题）。,11/21,5.3 指派问题（分派、分配问题）,例5.3.1 有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表所示，问如何分配任务使完成四项任务的总工时耗费最少？,12/21,一、 指派问题的数学模型,模型中：xij 为第 i 个工人分配去做第 j 项任务； aij 为第 i 个工人为完成第 j 项任务时的工时消耗； aijmm 称为效率矩阵,指派问题是整数规划问题，是01规划的特例，也是运输问题的特例。 指派问题有2m个约束条件，但有且只有m个非零解，是自然高度退化的。 指派问题的解矩阵中的元素非0即1，且是位于不同行、不同列的m个1。 指派问题的求解方法：著名的匈牙利法。,13/21,二、 指派问题的求解方法匈牙利法,定理 1 如果从效率矩阵aijmm中每行元素分别减去一个常数 ui，从每列元素分别减去一个常数 vj ，所得新的效率矩阵bijmm的任务分配问题的最优解等价于原问题的最优解。 定理 2 若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。,14/21,5.3.1 指派问题的求解方法匈牙利法,匈牙利法的基本思路： 根据定理 1 变换效率矩阵，使矩阵中有足够多的零。 根据定理2判断变换后的效率矩阵中位于不同行、不同列的零元素的最多个数。 若矩阵中存在 m 个不同行不同列的零，就找到了最优解 若覆盖变换后的效率矩阵零元素的直线少于m 条，就尚未找到最优解，设法进一步变换矩阵，增加新的零。,15/21,匈牙利法的具体步骤：例5.3.1,第一步：变换效率矩阵，使每行每列至少有一个零 行变换：找出每行最小元素，从该行各元素中减去之 列变换：找出每列最小元素，从该列各元素中减去之,第二步：检查覆盖所有零元素的直线是否为m条 划线规则 1、逐行检查，若该行只有一个未标记的零，对其加( )标记，将 ( )标记元素同行同列上其它的零打上*标记。若该行有二个以上未标记的零，暂不标记，转下一行检查，直到所有行检查完；,16/21,2、逐列检查，若该列只有一个未标记的零，对其加( )标记，将( )标记元素同行同列上其它的零打上*标记。若该列有二个以上未标记的零，暂不标记，转下一列检查，直到所有列检查完；,3、重复1、2后，可能出现三种情况： a. 每行都有一个 (0)，显然已找到最优解，令对应(0)位置的 xij=1； b. 仍有零元素未标记，此时，一定存在某些行和列同时有多个零，称为僵局状态，因为无法采用 1、 2 中的方法继续标记。 4、打破僵局。令未标记零对应的同行同列上其它未标记零的个数为该零的指数，选指数最小的先标记 ( )；采用这种方法直至所有零都被标记，或出现 情况 a，或 情况 c 。,匈牙利法的具体步骤：例5.3.1,17/21,c. 所有零都已标记，但标有( )的零的个数少于m； 开始划线过程： 对没有标记 ( ) 的行打 对打 行上所有其它零元素对应的列打 再对打 列上有 ( ) 标记的零元素对应的行打 重复 ，直至无法继续 对没有打 的行划横线，对所有打 的列划垂线,划线后会出现两种情况： (1) 标记( )的零少于m个，但划有 m条直线，说明矩阵中已存在 m 个不同行不同列的零，但打破僵局时选择不合理，没能找到。回到 b 重新标记； (2) 少于m条直线，到第三步；,匈牙利法的具体步骤：例5.3.1,18/21,第三步：进一步变换； 在未划线的元素中找最小者，设为 对未被直线覆盖的各元素减去 对两条直线交叉点覆盖的元素加上 只有一条直线覆盖的元素保持不变 以上步骤实际上仍是利用 定理 1,第四步：抹除所有标记，回到第二步，重新标记；,匈牙利法的具体步骤：例5.3.1,19/21,答：最优分配方案为 x13= x21= x34 = x42 =1，其余为0， 即甲C，乙A，丙D，丁B，z20,匈牙利法的具体步骤：例5.3.1,20/21,5.3.2 关于算法的几点说明,要求所有aij 0 若某些 aij 0 ，则利用定理 1 进行变换，使所有 bij 0 目标函数为min型 对于max型目标函数，将效率矩阵中所有 aij 反号，则等效于求min型问题；再利用定理 1 进行变换，使所有 bij 0,不平