整数规划问题及分配问题.ppt

整数规划（IP） 及分配问题,要求一部分或全部决策变量必须取整数值的规划问题称为整数规划（integer programming，简记IP）。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松驰问题（slack problem）。若松驰问题是一个线性规划，则称该整数规划为整数线性规划（integer linear programming）。,一、整数规划问题的数学模型,7-1 整数规划问题的数学模型及解的特点,整数线性规划数学模型的一般形式为:,3. 0-1型整数线性规划(Zero-one integer linear programming)：指决策变量只能了取值0或1的整数线性规划。,1. 纯整数线性规划(Pure integer linear programming)：指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。,2. 混合整数线性规划(Mixed integer linear programming）：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。,整数线性规划问题可以分为下列几种类型：,例7-1某厂生产 和 两种产品，需要经过 三道工序。单件工时和利润以及各工序每周工时限额见表7-1。问工厂应如何安排生产，才能使总利润最大？,二、整数规划的例子,解 设工厂每周生产 产品 件， 产品 件。 则该问题的数学模型为,这是一个纯整数线性规划问题。,例7-2某服务部门各时段（每2小时为一时段）需要的服务人数见表7-2。按规定，服务员连续工作8小时（即四个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。,解 设在第 时段开始时上班的服务员人数为 。由于第 时段开始时上班的服务员人数将在第 时段结束时下班，故决策变量只需要考虑 。数学模型为:,这也是一个纯整数线性规划问题。,三、解的特点,松驰问题作为一个线性规划问题，其可行解的集合是一个凸集，任意两个可行解的凸组合仍为可行解。 整数规划问题的可行解是它松驰问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。由于整数规划问题的可行解一定也是它的松驰问题的可行解（反之则不一定），所以，前者最优解的目标函数值不会优于后者最优解的目标函数值，即松弛问题的最优解是整数规划问题最优解的上限。,在一般情况下，松驰问题的最优解不会刚好满足变量的整数约束条件，因而不是整数规划的可行解，自然就不是整数规划的最优解。此时，若对松驰问题的这个最优解中不符合整数要求的分量简单地取整，所得到的解不一定是整数规划问题的最优解，甚至也不一定是整数规划问题的可行解。,7-2 分支定界法,7.2.1 思路与解题步骤（只解松弛问题） 1、在全部可行性域上解松弛问题 若松弛问题最优解为整数解，则其也是整数规划的最优解 2、分枝过程 若松弛问题最优解中某个xk=bk不是整数，令bk为 bk的整数部分 构造两个新的约束条件 xk bk 和 xk bk +1，分别加于原松弛问题，形成两个新的整数规划 3、求解分枝的松弛问题 定界过程 设两个分枝的松弛问题分别为问题1和问题2，它们的最优解有如下情况,表7.2.1 分枝问题解可能出现的情况,情况 2, 4, 5 找到最优解 情况 3 在缩减的域上继续分枝定界法 情况 6 问题1的整数解作为界被保留，用于以后与问题2的后续分枝所得到的解进行比较，结论如情况 4 或 5,计算过程可利用灵敏度分析（增加约束条件），简化问题的计算量,例1：求解下述问题： min z = -40x1-90x2 s.t. 9x1+7x256 7x1 +20x270 xj0,整数，j=1，2,算例,松弛问题的可行域和最优解,例2：求解下述（AIP）： max z = 3x1+2x2 s.t. 2x1+3 x2 14 x1 +0.5x2 4.5 xj0,整数，j=1,2,松弛问题的最优解为：x*=(3.25,2.5) z*=14.75,作业：（试用分枝定界法求解下面整数规划问题的解）,作业点评：,解：松弛问题的最优解为 x1=2.5, x2=2, OBJ=23 由 x1=2.5 得到两个分枝如下：,分枝问题的松弛解,问题II的解即原整数问题的最优解,可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程,7-3 0-1型整数规划,0-1型整数规划是整数规划中的特殊情形,变量xi仅取值为0或1,xi称为0-1变量或称二进制变量,具体实际问题常见关系:,1、投资场所的选定-相互排斥的计划,例1：某公司拟在市东、西和南三区建立门市部，拟议有7个位置Ai（i=1、27）可供选择，规定： 在东区A1、A2、A3中至多选择两个； 在西区A4、A5中至少选择一个； 在东区A6、A7中至少选择一个 如选择在Ai，设备投资估计为bi，每年可获利润为ci，投资总额不能超过B，应选择哪几个点可使得利润最大（建模）,例7-3现有资金总额为B，可供选择的投资项目有 个，项目 所需投资额和预期收益分别为 和 此外，由于种种原因，有三个附加条件：若选择项目1，就必须同时选择项目2，反之，则不一定；项目3和4中至少选择一个；项目5，6和7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？,解 每一个投资项目都有选择和不被选择两种可能，为此令,这样，问题可表示为,这是一个0-1型整数线性规划问题。其中，中间三个约束条件分别对应三个附加条件。,2、相互排斥的约束条件,问题满足两个约束条件中的一个,如果上述问题中一个或两个约束条件方程是“”型，应两边同乘“-1”变为“”型，再用上述方法进行调整。,在p个约束条件中至少要满足k个约束条件,令yi为0-1变量，如果第i个约束条件是k个约束条件中的一个，就令yi=1，否则取0；对p个约束条件中的每一个约束条件都增加yi，变为：,3、关于固定费用的问题,引例1：今有4辆装载不同货物的待卸车，派班员要分派给4个装卸班组，每个班组卸1辆。由于各个班组的技术特长不同，各个班组卸不同车辆所需时间如下表。问：派班员应如何分配卸车任务，可以使卸车所花费的总车辆小时最小？,一、指派问题及其模型特征,7-4 指派问题,引例2：一份中文说明书需要译成英、日、德、俄四种文字（E，J，G，R），现有甲、乙、丙、丁四人可以完成上述任务，他们将说明书翻译成不同语种的文字所需时间如下表，且一项任务只能由一人去完成，每人只能完成一项任务。问：指派何人完成何工作，可使总花费时间最少？,（1）n项工作怎样分配给n个工作人员去完成， 可以使总花费时间最省； （2）n项加工任务怎样分配给n台机床去完成， 可以使总费用最低； （3）n条航线，怎样指定n艘班轮去完成航行任 务，可以使总运输费用最低； 。 该类问题是运输问题的特殊形式，称为 指派问题。,（一）指派问题,（二）指派问题的基本特征,性质：特殊的运输问题、特殊0-1规划问题。 特征：（1）决策变量为0-1变量； (2) 发点数m = 收点数 n； （3）ai=bj=1 i,j=1,2,n ;,（三）指派问题的基本模型,运输问题是任务分配问题的松弛问题 任务分配问题不但是整数规划，而且是01规划 任务分配问题有2m个约束条件，但有且只有m个非零解，是自然高度退化的 任务分配是匹配问题，有著名的匈牙利算法,任务分配问题模型特征：,二、匈牙利法,、基本思想： （1）匈牙利法基于任务分配问题的标准型，应满足三个条件： 目标函数要求min； 效率矩阵aij为方阵; 效率阵中所有元素aij且为常数,定理 1（构造等效矩阵） 如果从效率矩阵aijmm中每行元素分别减去一个常数 ui，从每列元素分别减去一个常数 vj ，所得新的效率矩阵bijmm的任务分配问题的最优解等价于原问题的最优解。证明： 定理 2 若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。 证明：略 （）基本思路： 根据定理 1 变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在 m 个不同行不同列的零，就找到了最优解 若覆盖变换后的效率矩阵零元素的直线少于m 条，就尚未找到最优解，设法进一步变换矩阵，增加新的零,（）匈牙利定理,引例：有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如下表，问如何分配任务使完成四项任务的总工时耗费最少？,、计算步骤,第一步 建立等效矩阵(行变换和列变换) 使等效矩阵每一行和每一列都至少有1个0,第二步（最优解检验）检查覆盖所有零元素的直线是否为m条 划线规则 （1）逐行检查，若该行只有一个未标记的零，对其加( )标记，将 ( )标记元素同列上其它的零打上*标记。若该行没有或有二个以上未标记的零，暂不标记，转下一行检查，直到所有行检查完； （2）逐列检查，若该列只有一个未标记的零，对其加( )标记，将 ( )标记元素同行上其它的零打上*标记。若该列没有或有二个以上未标记的零，暂不标记，转下一列检查，直到所有列检查完；,（3）重复1、2后，可能出现三种情况： a、每行都有一个 (0)，显然已找到最优解，令对应(0)位置的 xij=1； b、仍有零元素未标记，此时，一定存在某些行和列同时有多个零，称为僵局状态（m较大时可能出现），因为无法采用 1、 2 中的方法继续标记。 c、所有零都已标记，但标有( )的零的个数少于m； （4）打破僵局。令未标记零对应的同行同列上其它未标记零的个数为该零的指数，选指数最小的先标记 ( )，划去同行同列其他0元素（标注*）；采用这种方法直至所有零都被标记，或出现 情况 a，或 情况 c 。,（5）出现c情况的处理方法（划线过程）行表示人，列表示任务 对没有标记 ( ) 的行打(没有安排任务) 对打 行上所有其它零元素0*对应的列打 (任务被安排) 再对打 列上有 ( ) 标记的零元素对应的行打 重复上面2、3步骤，直至无法继续 对没有打 的行划横线(已经安排任务)，对所有打 的列划垂线(任务已经被安排),划线后会出现两种情况： (1) 标记( )的零少于m个，但划有 m条直线，说明矩阵中已存在 m 个不同行不同列的零，但打破僵局时选择不合理，没能找到。回到 b 重新标记； (2) 少于m条直线，到第三步；,打破僵局时选择不当的结果：,结果仅出现 3 个标记 ( )，但却划出 4 条线， 说明什么？！,第三步：进一步变换（继续构造0元素） 在未划线的元素中找最小者，设为 对未被直线覆盖的各元素减去 对两条直线交叉点覆盖的元素加上 只有一条直线覆盖的元素保持不变 以上步骤实际上仍是利用 定理 1,第四步：抹除所有标记，回到第二步，重新标记；,所有未画横线的行都减去这个最小元素 所有画竖线的列都加上这个最小元素,基本步骤：,答：最优分配方案为 x13= x21= x34 = x42 =1，其余为0， 即甲C，乙A，丙D，丁B，OBJ=20,课堂练习： 某商业公司设计开办五家新闻商店 。为了尽早建成营业，商业公司通知了 五个建筑公司，以便让每家新商店由一个建筑公司承建。 建筑公司对新商店 的建造费用的投标为 均见表7-9。商业公司应当对五家建筑公司怎样分配建造任务，才能使总建造费用最少？,对各行元素分别减去本行的最小元素，对各列也如此，得,利用匈牙利法求得最优解为：,总的建设费用最少为34万元,3、不规范形式的转化,要求所有aij 0 若某些 aij 0 ，则利用定理 1 进行变换，使所有 bij 0 目标函数为min型 对于max型目标函数，将效率矩阵中所有 aij 反号，则等效于求min型问题；再利用定理 1 进行变换，使所有 bij 0，则可采用上述算法,三、 一般的指派问题,1、最大化指派问题,设最大化指派问题系数矩阵 ，其中最大元素 为 。令矩阵 ，则以B为系数矩阵的最小指派问题和以A为系数矩阵的原最大化指派问题有相同最优解。,例7-11 矩阵,的最大元素为 ，取 ，求出B矩阵,则以B为系数矩阵的最小化指派问题和以A为系数矩阵的最大化指派问题有相同最优解。 当系数矩阵为利润矩阵、产量矩阵等时，就产生最大化指派问题。,2、人数和事数不等的指派问题,若人少事多，则添上一些虚拟的“人”。这些虚拟的“人”做各事的费用系数可取0（理解为这些费用实际上不会发生），也可取足够的数M（理解为指派这些虚拟的“人”去做那些事，则那些事实际上没人去做）。 若人多事少，则添上一些虚拟的“事”，这些“事”被各人做的费用系数同样可取0，也可取足够大的数M。,3、一个人可做几件事的指派问题,m若某事一定不能由某人做，则可将相应的费用系数取作足够大的数M。,若某人可做几件事，则可将该人化作相同的几个“人”来接受指派，这几个“人”做同一件事的费用系数当然都一样。,4、某事一定不能