整数规划及分支定界法.ppt

第三章整数规划 3 1整数规划问题整数规划是一类要求变量取整数值的数学规划 可分成线性和非线性两类 根据变量的取值性质 又可以分为全整数规划 混合整数规划 0 1整数规划等 整数规划是数学规划中一个较弱的分支 目前只能解中等规模的线性整数规划问题 而非线性整数规划问题 还没有好的办法 例3 1 一登山队员做登山准备 他需要携带的物品有 食品 氧气 冰镐 绳索 帐篷 照相机和通讯设备 每种物品的重要性系数和重量如下 假定登山队员可携带最大重量为25公斤 解 如果令xi 1表示登山队员携带物品i xi 0表示登山队员不携带物品i 则问题表示成0 1规划 MaxZ 20 x1 15x2 18x3 14x4 8x5 4x6 10 x7s t 5x1 5x2 2x3 6x4 12x5 2x6 4x7 25xi 1或xi 0i 1 2 7 例3 2背包问题 KnapsackProblem 一个旅行者 为了准备旅行的必须用品 要在背包内装一些最有用的东西 但有个数限制 最多只能装b公斤的物品 而每件物品只能整个携带 这样旅行者给每件物品规定了一个 价值 以表示其有用的程度 如果共有n件物品 第j件物品aj公斤 其价值为cj 问题变成 在携带的物品总重量不超过b公斤条件下 携带哪些物品 可使总价值最大 解 如果令xj 1表示携带物品j xj 0表示不携带物品j 则问题表示成0 1规划 MaxZ cjxjs t ajxj bxj 0或1 数学模型整数规划 IP 的一般数学模型 Max min Z cjxjs t aijxj bi i 1 2 m xj 0且部分或全部是整数 解法概述当人们开始接触整数规划问题时 常会有如下两种初始想法 因为可行方案数目有限 因此经过一一比较后 总能求出最好方案 例如 背包问题充其量有2n 1种方式 连线问题充其量有n 种方式 实际上这种方法是不可行 设想计算机每秒能比较1000000个方式 那么要比较完20 大于2 1018 种方式 大约需要800年 比较完260种方式 大约需要360世纪 先放弃变量的整数性要求 解一个线性规划问题 然后用 四舍五入 法取整数解 这种方法 只有在变量的取值很大时 才有成功的可能性 而当变量的取值较小时 特别是0 1规划时 往往不能成功 例3 3求下列问题 MaxZ 3x1 13x2s t 2x1 9x2 4011x1 8x2 82x1 x2 0 且取整数值 O12345678910 54321 x1 x2 I 2 4 B 9 2 2 4 A D 可行域OABD内整数点 放弃整数要求后 最优解B 9 2 2 4 Z0 58 8 而原整数规划最优解I 2 4 Z0 58 实际上B附近四个整点 9 2 10 2 9 3 10 3 都不是原规划最优解 O12345678910 54321 x1 x2 I 2 4 B 9 2 2 4 A D 假如能求出可行域的 整点凸包 包含所有整点的最小多边形OEFGHIJ 则可在此凸包上求线性规划的解 即为原问题的解 但求 整点凸包 十分困难 E F G H I J O12345678910 54321 x1 x2 I 2 4 B 9 2 2 4 A D 假如把可行域分解成五个互不相交的子问题P1P2P3P4P5之和 P3P5的定义域都是空集 而放弃整数要求后P1最优解I 2 4 Z1 58P2最优解 6 3 Z2 57P4最优解 98 11 2 Z4 52 8 11 P1 P2 P4 X1 2 X1 6 X2 3 X2 2 X1 3 X1 7 X2 4 X2 3 P1 P5 P4 P2 P3 P 假如放弃整数要求后 用单纯形法求得最优解 恰好满足整数性要求 则此解也是原整数规划的最优解 以上描述了目前解整数规划问题的两种基本途径 分枝定界解法 BranchandBoundMethod 原问题的松驰问题 任何整数规划 IP 凡放弃某些约束条件 如整数要求 后 所得到的问题 P 都称为 IP 的松驰问题 最通常的松驰问题是放弃变量的整数性要求后 P 为线性规划问题 分枝定界法步骤一般求解对应的松驰问题 可能会出现下面几种情况 若所得的最优解的各分量恰好是整数 则这个解也是原整数规划的最优解 计算结束 若松驰问题无可行解 则原整数规划问题也无可行解 计算结束 若松驰问题有最优解 但其各分量不全是整数 则这个解不是原整数规划的最优解 转下一步 从不满足整数条件的基变量中任选一个xl进行分枝 它必须满足xl xl 或xl xl 1中的一个 把这两个约束条件加进原问题中 形成两个互不相容的子问题 两分法 定界 把满足整数条件各分枝的最优目标函数值作为上 max 下 min 界 用它来判断分枝是保留还是剪枝 剪枝 把那些子问题的最优值与界值比较 凡不优或不能更优的分枝全剪掉 直到每个分枝都查清为止 例5 6用分枝定界法求解 MaxZ 4x1 3x2s t 3x1 4x2 124x1 2x2 9x1 x2 0且为整数用单纯形法可解得相应的松驰问题的最优解 6 5 21 10 Z 111 10为各分枝的上界 01234 4321 x1 x2 分枝 X1 1 x1 2 P1 P2 两个子问题 P1 MaxZ 4x1 3x2s t 3x1 4x2 124x1 2x2 9x1 x2 0 x1 1 整数用单纯形法可解得相应的 P1 的最优解 1 9 4 Z 10 3 4 P2 MaxZ 4x1 3x2s t 3x1 4x2 124x1 2x2 9x1 x2 0 x1 2 整数用单纯形法可解得相应的 P2 的最优解 2 1 2 Z 9 1 2 01234 4321 x1 x2 再对 P1 分枝 X1 1 P3 x2 2 P4 x2 3 P1 P2 P3 P4 P1 两个子问题 P3 MaxZ 4x1 3x2s t 3x1 4x2 124x1 2x2 9x1 x2 0 x1 1 x2 2整数用单纯形法可解得相应的 P3 的最优解 1 2 Z 10 P1 两个子问题 P4 MaxZ 4x1 3x2s t 3x1 4x2 124x1 2x2 9x1 x2 0 x1 1 x2 3整数用单纯形法可解得相应的 P4 的最优解 0 3 Z 9 X1 2 X2 2 X1 1 X2 3 P1 1 9 4 Z 10 3 4 P4 0 3 Z 9 P2 2 1 2 Z 9 1 2 P3 1 2 Z 10 P 6 5 21 10 Z 111 10 原问题的最优解 1 2 Z 10 例5 7用分枝定界法求解 MinZ x1 4x2s t 2x1 x2 8x1 2x2 6x1 x2 0且取整数用单纯形法可解得相应的松驰问题的最优解 10 3 4 3 Z 26 3为各分枝的下界 0123456 87654321 x1 x2 p 0123456 87654321 x1 x2 p 选x1进行分枝 P1 x1 3 P2 x1 4为空集 P1 P1 MinZ x1 4x2s t 2x1 x2 8x1 2x2 6x1 x2 0 x1 3整数用单纯形法可解得 P1 的最优解 3 3 2 Z 9 P2 MinZ x1 4x2s t 2x1 x2 8x1 2x2 6x1 x2 0 x1 4整数无可行解 0123456 87654321 x1 x2 p 对 P1 x1 3选x2进行分枝 P3 x2 1无可行解 P4 x2 2 P4 P3 MinZ x1 4x2s t 2x1 x2 8x1 2x2 6x1 x2 0 x1 3 x2 1整数无可行解 P4 MinZ x1 4x2s t 2x1 x2 8x1 2x2 6x1 x2 0 x1 3 x2