第5讲整数规划课件.pptVIP

第三节 整数规划模型的解 例 整数规划模型 且为整数 1 2 3 4 5 1 由 — 解得: 4 （1）若取整： 是可行解，但非最优解， （2）按四舍五入得： 不是可行解 2 因 左边为：59 56 用穷举法也是不可取的。 因有可行解： 一、分枝定界法 设整数规划模型： （P） 且为整数， 记最优解为 ，最优目标值为 。 松弛问题： （P0） 记可行域为S0 , 最优解为X0 ,最优目标值为z0 。 1 2 3 1 3 — ? 若 整，则 ? 若 非整， 则分枝 自然上界 1 3 — 1 3 — 若 整，则剪枝 并换上界： 若 非整，则 ? 若 ，则剪枝 ? 若 ，则分枝 当前上界 1 3 — 1 3 — 若 整，则剪枝 ? 若 ，则换界 ? 若 ，则不换界 若 非整，则 ? 若 当前上界，则剪枝 ? 若 当前上界，则分枝 剪完所有枝得： 则 最小上界对应的最优解为所求。 对每个子问题 ，不外乎有以下三种可能情况: （1） 不可行，则剪枝； （2）其最优解 为整数解，则剪枝，且 ? 当目标值 当前上界时，则换界； ? 当目标值 当前上界时，则不换界。 （3）其最优解 为非整数解，则 ? 当目标值 当前上界时，则剪枝； ? 当目标值 当前上界时，则分枝。 注：对于极大化问题，则是定下界，最大下界对应的整数解为所求。 则 归纳起来: 例 求解 且为整数 1 2 3 4 5 解松弛问题P0 可用 图解法 目标函数等值线 1 4 1 4 1 4 换界: 分枝 换界： 最优目标值： 最优解： ＃ 二、0－1规划的解 若对每一个变量取0、1进行分枝，计算量很大。如 的情形： 共有 个子问题 n个变量的情形共有子问题个数： 下面的方法可减少计算量。 1. 隐数法 设模型为： ? 若 ， 则令 ? 若约束是“ ”，可乘（－1） ? 若约束是“＝”，则可换为： 上述假设之用处： ? 当 从取0变为取1时，目标值增加 ? 验证当前解是否为可行解时，只需验证 的符号 约定： 表示原问题 表示 的子问题 这时 称为固定变量， 其余变量称为自由变量。 ＃ 隐数法的基本思想： 从目标函数的最小值 z=0 （解点 ）开始： ? 若该点可行，则为最优解； ? 若不可行，则选分枝变量分枝（原则：其值升为“1”，其余仍取0，得一新解点“最接近可行”） ? 若新解点可行，则剪枝，定界； ?若新解点不可行，则与当前上界比较，确定剪枝或分枝。 直到剪完所有的枝，最小上界对应的可行解为所求。 用此思想初步计算 P.25 例1.21 例 解 对于 不可行， 因此它不是最优解。 确定分枝变量： 若用 分枝，两个子问题为： 解点： 均“很不可行” 若用 分枝，两个子问题为： — 解点： 是可行解 因此， 为分枝变量。 见图 对于P2 : 所以该分枝。 若用 分枝，则两个解点均很不可行， 所以取 为分枝变量。 若用 分枝，则解 可行， 见图 无可行解 最优解 最优目标值 自然上界 一般编程步骤见P.25 部分枚举法 思路：让 最小的 取1，其余取0，若是可行解，则为最优解；否则再让次小的 对应的变量升为1，直到可行为止。 例 解 （1）解点 不可行，则转入（2） （若可行得 ） （2） 最小，让 取1，其余取0得解点 因不可行，转入（3），若可行则为最优解。 （3） 为次小的，则让 取1，其余取0得解点 仍不可行，转入（4） （4） ， 为剩下系数中的最小者 让 取1，其余取0得解点 是一可行解，故得： 最优解 最优目标值 # 2. 隐枚举法 先找一可行解 、目标值 ，得过滤条件： 因最优目标值 ， 所以只需在满足过滤条件的解点中找最优者。 例 1 2 3 解 找到可行解点(1,0,0)，对应的 z =4, 得过滤条件：