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

整数规划（ IP） 及分配问题 要求一部分或全部决策变量必须取整数值的规 划问题称为整数规划 （ integer programming， 简记 IP ） 。 不考虑整数条件 ， 由余下的目标函数和约束条 件构成的规划问题称为该整数规划问题的松驰问题 （ slack problem） 。 若松驰问题是一个线性规划 ， 则称该整数规划为整数线性规划 （ integer linear programming） 。 一、整数规划问题的数学模型 7-1 整数规划问题的数学模型及解的特点 1 1 12 m a x ( m in ) ( 7 1 ) ( , ) 1 , 2 , , ( 7 2 ) . . 0 1 , 2 , , ( 7 3 ) , , , n jj j n ij j i j j n z c x a x b i m s t x j n x x x 或 中 部 分 或 全 部 取 整 数 (7-4) 整数线性规划数学模型的一般形式为 : 3. 0-1型整数线性规划 (Zero-one integer linear programming)： 指决策变量只能了取值 0或 1的整数线 性规划 。 1. 纯整数线性规划 (Pure integer linear programming)： 指全部决策变量都必须取整数值的整 数线性规划。有时，也称为全整数规划 。 2. 混合整数线性规划 (Mixed integer linear programming）： 指决策变量中有一部分必须取整数 值，另一部分可以不取整数值的整数线性规划。 整数线性规划问题可以分为下列几种类型： 例 7-1某厂生产 和 两种产品 ， 需要经过 三道工 序 。 单件工时和利润以及各工序每周工时限额见表 7-1。 问 工厂应如何安排生产 ， 才能使总利润最大 ？ 321 , BBB 1A 2A 表 7-1 1A 2A 1B 2B 3B 工序 工时 /件 产品 利润（元 / 件） 0.3 0.2 0.3 25 0.7 0.1 0.5 40 工时限制 （ h/周） 250 100 150 二、整数规划的例子 解 设工厂每周生产 产品 件 ， 产品 件 。 则该问题的数学模型为 1A 1x 2 A 2x 21 4025m a x xxz 且为整数,0,0 1505.03.0 1001.02.0 2507.03.0 . 21 21 21 21 xx xx xx xx ts 这是一个纯整数线性规划问题。 例 7-2某服务部门各时段 （ 每 2小时为一时段 ） 需要的服务 人数见表 7-2。 按规定 ， 服务员连续工作 8小时 （ 即四个时段 ） 为一班 。 现要求安排服务员的工作时间 ， 使服务部门服务员 总数最少 。 表 7-2 时 段 1 2 3 4 5 6 7 8 服务员最少 数目 10 8 9 11 13 8 5 3 解 设在第 时段开始时上班的服务员人数为 。 由于 第 时段开始时上班的服务员人数将在第 时段结束时 下班 ， 故决策变量只需要考虑 。 数学模型为 : j jx j )3( j 54321 , xxxxx 1 12 1 2 3 1 2 3 4 2345 345 45 5 1 2 3 4 5 1 2 3 4 5 10 8 9 11 13 . 8 5 3 , , , , 0 , , , , , x xx x x x x x x x x x x x st x x x xx x x x x x x x x x x x 皆 为 整 数 54321m i n xxxxxz 这也是一个纯整数线性规划问题。 三、解的特点 松驰问题 作为一个线性规划问题 ， 其可行解的集合 是一个凸集 ， 任意两个可行解的凸组合仍为可行解 。 整数规划问题 的可行解是它松驰问题可行解集合的一 个子集 ， 任意两个可行解的凸组合不一定满足整数约束 条件 ， 因而不一定仍为可行解 。 由于整数规划问题的可 行解一定也是它的松驰问题的可行解 （ 反之则不一定 ） ， 所以 ， 前者最优解的目标函数值不会优于后者最优解的 目标函数值 ， 即 松弛问题的最优解是整数规划问题最优 解的 上限 。 在一般情况下 ， 松驰问题的最优解不会刚好满 足变量的整数约束条件 ， 因而不是整数规划的可行解 ， 自然就不是整数规划的最优解 。 此时 ， 若对松驰问题 的这个最优解中不符合整数要求的分量简单地取整 ， 所得到的解不一定是整数规划问题的最优解 ， 甚至也 不一定是整数规划问题的可行解 。 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 = -40 x1-90 x2 s.t. 9x1+7x256 7x1 +20 x270 xj0,整数， j=1， 2 算例 2 0 x1 x2 1 （ 4.81， 1.82） 2 3 4 5 6 1 3 4 7 K0 (K0): X*=(4.81,1.82)T Z* =-356 松弛问题的可行域和最优解 2 0 x1 x2 1 （ 4.81， 1.82） 2 3 4 5 6 1 3 4 7 (K1) (K1) : X1*=(4.00,2.10)T Z1 * =-349 (K2) (K2) : X2*=(5.00,1.57)T Z2 * =-341 2 0 x1 x2 1 （ 4.81， 1.82） 2 3 4 5 6 1 3 4 7 (K3) (K3) : X3*=(4.00,2.00)T Z3 * =-340 (K2) (K4) : X4*=(1.42,3.00)T Z4 * =-327 (K4) 2 0 x1 x2 1 2 3 4 5 6 1 3 4 7 (K3) (K5) : X5*=(5.44,1.00)T Z5 * =-308 (K5) (K6) : K6= (K4) （ 4.81， 1.82） (K6) = 例 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 75.14 5.2,25.3 21 z xx 5.14 2,5.3 21 z xx 5.13 3,5.2 21 z xx 22 x 32 x 13 2,3 21 z xx 14 1,4 21 z xx 31x41x 作业： （ 试用分枝定界法求解下面整数规划问题的解 ） 且为整数 0, 7 2 1342 46)(m a x 21 21 21 21 xx xx xx xxxf 作业点评： 且为整数 0, 7 2 1342 46)(m a x 21 21 21 21 xx xx xx xxxf 解 ：松弛问题的最优解为 x1=2.5, x2=2, OBJ=23 由 x1=2.5 得到两个分枝如下： 且为整数 问题 0, 2 7 2 1342 I 46)(m a x 21 1 21 21 21 xx x xx xx xxxf 且为整数 问题 0, 3 7 2 1342 II 46)(m a x 21 1 21 21 21 xx x xx xx xxxf 分枝问题的松弛解 问题 I 问题 II x 1 2 3 x 2 9 / 4 1 f ( x ) 21 22 问题 II的解即原整数问题的最优解 可能存在两个分枝都是非整数解的情况，则需要两边同 时继续分枝，直到有整数解出现，就可以进行定界过程 11 1 1 ( nn jj jj xx 至 多 选 一 ） 7-3 0-1型整数规划 0-1型整数规划是整数规划中的特殊情形 ,变量 xi仅 取值为 0或 1,xi称为 0-1变量或称二进制变量 ,具体实际问 题常见关系 : ijxx ijxx 1、投资场所的选定 -相互排斥的计划 例 1：某公司拟在市东、西和南三区建立门市部，拟议有 7 个位置 Ai（ i=1、 2.7）可供选择，规定： 在东区 A1、 A2、 A3中至多选择两个； 在西区 A4、 A5中至少选择一个； 在东区 A6、 A7中至少选择一个 如选择在 Ai，设备投资估计为 bi，每年可获利润为 ci， 投资 总额不能超过 B，应选择哪几个点可使得利润最大（建模） 例 7-3现有资金总额为 B， 可供选择的投资项目有 个 ， 项目 所需投资额和预期收益分别为 和 此外 ， 由于种种原因 ， 有三个附加条件： 若选择项目 1， 就必须同时选择项目 2， 反之 ， 则不一定； 项目 3和 4中至 少选择一个； 项目 5， 6和 7中恰好选择两个 。 应当怎样选 择投资项目 ， 才能使总预期收益最大 ？ n j ja ),2,1( njc j 解 每一个投资项目都有选择和不被选择两种可能 ， 为此令 ),2,1(01 njjjx j 不投资对项目 投资对项目 这样，问题可表示为 ),2,1(10 2 1 . m a x 765 43 21 1 1 njx xxx xx xx Bxa ts xcz j n j jj n j jj 或 这是一个 0-1型整数线性规划问题 。 其中 ， 中间三 个约束条件分别对应三个附加条件 。 2、相互排斥的约束条件 问题满足两个约束条件中的一个 1 1 1 1 2 2 2 1 n jj j n jj j a x b a x b 1 1 1 1 2 2 2 1 1 01 n jj j n jj j a x b M a x b M （ ） （ 且 取 整 ） 如果上述问题中一个或两个约束条件方程是“ ” 型， 应两边同乘“ -1” 变为“ ” 型，再用上述方法进行 调整。 在 p个约束条件中至少要满足 k个约束条件 1 ( 1 , 2 . . . . ) n ij ij i j a x b i p 令 yi为 0-1变量，如果第 i个约束条件是 k个约束条件中的一 个，就令 yi=1，否则取 0；对 p个约束条件中的每一个约束 条件都增加 yi，变为： 1 1 ( 1 ) ( 1 , 2. . ) 01 n ij ij i i j p ii i a x b y M i p y k y 且 取 值 或 3、关于固定费用的问题 引例 1： 今有 4辆装载不同货物的待卸车，派班员要分派给 4个 装卸班组，每个班组卸 1辆。由于各个班组的技术特长不同， 各个班组卸不同车辆所需时间如下表。问：派班员应如何分 配卸车任务，可以使卸车所花费的总车辆小时最小？ i j P1 P2 P3 P4 甲 4 3 4 1 乙 2 3 6 5 丙 4 3 5 4 丁 3 2 6 6 一、指派问题及其模型特征 7-4 指派问题 引例 2：一份中文说明书需要译成英、日、德、俄四种文字（ E， J， G， R），现有甲、乙、丙、丁四人可以完成上述任务 ，他们将说明书翻译成不同语种的文字所需时间如下表，且 一项任务只能由一人去完成，每人只能完成一项任务。问： 指派何人完成何工作，可使总花费时间最少？ i j E J G R 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9 （ 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 ; mji ji ji x ij ,2,1, 0 1 项任务个工人未分配去做第当第 项任务个工人分配去做第当第 1,0 ,2,1 1 ,2,1 1 )(m in 1 1 1 1 ij m i ij m j ij m i m j ijij x mjx mix xaxf （三）指派问题的基本模型 运输问题是任务分配问题的松弛问题 任务分配问题不但是整数规划，而且是 01规划 任务分配问题有 2m个约束条件，但有且只有 m个非零解 ，是自然 高度退化 的 任务分配是 匹配问题 ，有著名的 匈牙利算法 任务分配问题模型特征： 二、匈牙利法 、基本思想 ： （ 1） 匈牙利法基于任务分配问题的标准型，应满足三个条 件 ： 目标函数要求 min； 效率矩阵 aij为方阵 ; 效率阵中所有元素 aij 且为常数 定理 1（构造等效矩阵） 如果从效率矩阵 aijmm中每行元素分 别减去一个常数 ui，从每列元素分别减去一个常数 vj ， 所得 新的效率矩阵 bijmm的任务分配问题的最优解等价于原问题 的最优解。 证明： 定理 2 若方阵中一部分元素为零，一部分元素非零，则覆盖方 阵内所有零元素的最少直线数等于位于不同行、不同列的零 元素的最多个数。 证明：略 （） 基本思路： 根据 定理 1 变换效率矩阵，使矩阵中有足够多的零。若 矩阵中存在 m 个不同行不同列的零，就找到了最优解 若覆盖变换后的效率矩阵零元素的直线少于 m 条，就尚 未找到最优解，设法进一步变换矩阵，增加新的零 （）匈牙利定理 最优解不变 KZZx xKxaZ m j ij m ji ij m i m j ijij 1 1 1)(1 1 引例： 有四个熟练工人，他们都是多面手，有四项任务要他 们完成。若规定每人必须完成且只完成一项任务，而每 人完成每项任务的工时耗费如下表，问如何分配任务使 完成四项任务的总工时耗费最少？ 任务 工时 A B C D 人员 人员 甲 10 9 7 8 1 乙 5 8 7 7 1 丙 5 4 6 5 1 丁 2 3 4 5 1 任务 1 1 1 1 、计算步骤 2210 0201 1230 0023 3210 1201 2230 )1(023 543)2( 56)4(5 778)5( 8)7(910 换 变 列 换 变 行 第一步 建立等效矩阵 (行变换和列变换 ) 使等效矩阵每一行和每一列都至少有 1个 0 221*0 *02)0(1 123)0( *0)0(23 221*0 0201 123)0( 0023 查 检 列 逐 查 检 行 逐 第二步 （ 最优解检验）检查覆盖所有零元素的直线是否为 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步骤，直至无法继续 对没有打 的行划横线 (已经安排任务 )，对所有 打 的列 划垂线 (任务已经被安排 ) 221*0 *02)0(1 123)0( *0)0(23 划线后会出现两种情况： (1) 标记 ( )的零少于 m个，但划有 m条 直线，说明矩阵中已存在 m 个不同行 不同列的零，但打破僵局时选择不合 理，没能找到。回到 b 重新标记； (2) 少于 m条直线，到 第三步 ； 6 0 2 0 5 0 4 0 0 3 0 1 0 2 0 0 局 僵 破 打 打破僵局时选择不当的结果： 结果仅出现 3 个标记 ( )，但却划出 4 条线， 说明什么？！ 6 0 2 *0 5 0 4 *0 0 3 0 1 *0 2 *0 )0( 局 僵 破 打 6 *0 2 *0 5 )0( 4 *0 0 3 0 1 *0 2 *0 )0( 局 僵 破 打 6 *0 2 *0 5 )0( 4 *0 *0 3 )0( 1 *0 2 *0 )0( 局 僵 破 打 221*0 *02)0(1 123)0( *0)0(23 第三步：进一步变换（继续构造 0元素） 在未划线的元素中找 最小者 ，设为 对未被直线覆盖的各元素减去 对两条直线交叉点覆盖的元素加上 只有一条直线覆盖的元素保持不变 以上步骤实际上仍是利用 定理 1 1100 0202 0120 0024 1 第四步：抹除所有标记，回到第二步，重新标记 ； 所有未画横线的行都减去这 个最小元素 所有画竖线的列都加上这个 最小元素 解 优 最 列 逐 行 逐 记 标 11)0(*0 )0(2*02 *012)0( *0)0(24 基本步骤： 1100 0202 0120 0024 1 答：最优分配方案为 x13= x21= x34 = x42 =1，其余为 0， 即甲 C，乙 A，丙 D，丁 B， OBJ=20 1100 0202 0120 *0)0(24 记 标 列 110*0 0202 *012)0( *0)0(24 局 僵 破 打 221*0 *02)0(1 123)0( *0)0(23 课堂练习： 某商业公司设计开办五家新闻商店 。 为了尽早 建成营业 ， 商业公司通知了 五个建筑公司 ， 以 便让每家新商店由一个建筑公司承建 。 建筑公司对新商 店 的建造费用的投标为 均见表 7-9。 商业公司应当对 五家建筑公司怎样分配建造任务 ， 才能使总建造费用最少 ？ 54321 , BBBBB 54321 , AAAAA iA jB ijc 2A 3A 4A 5A 4 8 7 15 12 7 9 17 14 10 6 9 12 8 7 6 7 14 6 10 6 9 12 10 6 1B 2B 3B 4B 5B 1A ijc jB iA )0(4320 405)0( 1232 3771 811)0(3 0 0 )0( 0 * * * * 对各行元素分别减去本行的最小元素 ， 对各列也如此 ， 得 04320 4050 1232 3771 81103 0 0 0 0 04630 4081 1263 37102 81134 0 0 0 0 6101296 106147 78129 1014179 121578 6 6 7 4 利用匈牙利法求得最优解为： 5 4 3 2 1 * 10000 0100 0000 0001 0010 0 1 0 0 A A A A A X 54321 , BBBBB 总的建设费用最少为 34万元 3、不规范形式的转化 要求所有 aij 0 若某些 aij 0 ，则利用定理 1 进行变换，使所 有 bij 0 目标函数为 min型 对于 max型目标函数，将效率矩阵中所有 aij 反 号，则等效于求 min型问题；再利用定理 1 进行 变换，使所有 bij 0，则可采用上述算法 三、 一般的指派问题 1、 最大化指派问题 设最大化指派问题系数矩阵 ， 其中最大元素 为 。 令矩阵 ， 则以 B为系数矩 阵的最小指派问题和以 A为系数矩阵的原最大化指派问题 有相同最优解 。 nnijaA )( m nnijnnij ambB )()( 例 7-11 矩阵 91187 1316149 1514410 413152 A 的最大元素为 ， 取 ， 求出 B矩阵 16 33 a 16m 7589 3027 12126 123114 9161116816716 131616161416916 151614164161016 4161316516216 B 则以 B为系数矩阵的最小化指派问题和以 A为系数矩 阵的最大化指派问题有相同最优解 。 当系数矩阵为利润矩阵 、 产量矩阵等时 ， 就产生最 大化指派问题 。 2、人数和事数不等的指派问题 若人少事多 ， 则添上一些虚拟的 “ 人 ” 。 这些虚拟的 “ 人 ” 做各事的费用系数可取 0（ 理解为这些费用实际上不 会发生 ） ， 也可取足够的数 M（ 理解为指派这些虚拟的 “ 人 ” 去做那些事 ， 则那些事实际上没人去做 ） 。 若人多事少 ， 则添上一些虚拟的 “ 事 ” ， 这些 “ 事 ” 被各人做的费用系数同样可取 0， 也可取足够大的数 M。 3、一个人可做几件事的指派问题 m若某事一定不能由某人做，则可将相应的费用系数取作 足够大的数 M。 若某人可做几件事，则可将该人化作相同的几个“人” 来接受指派，这几个“人”做同一件事的费用系数当然都 一样。 4、某事一定不能由某人做的指派问题 例 7-12 对于课堂练习的指派问题 ， 为了加快建造速度 ， 经 研究决定 ， 舍弃建筑公司 和 ， 而让技术力量较强的建 筑公司 和 来承建 。 根据实际情况 ， 可以允许每家 建筑公司承建一个或两个商店 。 求使总费用最少的指派方案 。 反映投标费用的系数矩阵为 4A 5A 21, AA 3A 7 10 12 8 14 15 1296 1797 784 3 2 1 54321 A A A BBBBB 由于每家建筑公司最多可承建两个新商店 ， 因此 ， 把每 家建筑公司化作相同的两家 （ 和 ） 。 这样 系数矩阵为： iA 3,2,1, iAi 现在 ， 用匈牙利解法求最优指派方案如下： 000512 000512 0361013 0361013 057000 057000 C * * * * * 3 3 2 2 1 1 654321 0)0(0512 00)0(512 0361013 )0(361013 0570)0(0 05700)0( 000512 000512 0361013 0361013 057000 057000 0 0 0 0 0 0 7 7 10 10 12 12 8 8 14 14 15 15 12 12 17 17 7 7 9 9 9 9 8 8 6 6 7 7 4 4 A A A A A A C BBBBBB 1 1 )0( 0 0 )0( 5 5 12 12 0 )0( 1 1 2 2 5 5 59)0(2 5902 7)0(00 700)0( * * * * * * 1 1 0 0 0 0 5 5 1 1 2 2 0 0 1 1 2 2 5 5 5902 5902 7000 7000 从最后的矩阵已能确定最优解 。 从表面看 ， 似乎有 6个最优 解 ， 但根据问题的特殊性 ， 它们都是相同的 ， 即 1 0 0 1 0 0 000 010 101 3 2 1 54321 A A A BBBBB 所以 ， 最优指派方案是 总的建造费用最省 ， 是 4+7+9+8+7=35万元 。 1 1 3 22 3 4 5 , , A B B AB A B B