1.分枝定界算法

1.1分枝定界算法概述

分枝定界算法(Branch-and-Bound  Algorithm,简称B&B)已被Land  Doig等人提出几十年之久.人们不单能够用其解决整数线性规划问题,而且还能用其解决近乎任意的最优化问题.

1.2分枝定界算法的基本思想

因有界 问题的整数解数目有有限多个,故可以通过“巧妙”的枚举 问题的可行 得到求解 问题的一种算法: 分枝定界法.先把给定的一个  的某些整数约束条件去掉,得到 的  并对其求解.若 无解,则 无解; 若 的最优解 各个分量都是整数,则 是 的最优解; 若 的某个分量不是整数,则有以下两种方法: 第一是对LP问题不停的改变以得到 的最优解; 第二是应用分枝术,将给定的原 问题 分解为若干个子问题,假如每个可行域内的最优解能在对应的子问题的可行域内找到,或者明确这个可行域内没有原  的最优解,这样原  就得到了简化.分解的过程称为分枝,步骤如 :

对整数线性规划问题                                                  

其中,A为整数矩阵,b, c为整数向量.如果  的  ,则 是 .如果 存在某个分量 不是整数,在可行域 或 中必然存在(P)的整数最优解的第i个分量,( 为不超过数 的最大整数),因而原问题 将被分解为以下两个子问题: 的可行域被这两个子问题分成了两个部分,若 的某个分量不是整数,排除.继续求 和 对应的LP问题,若 的LP问题的解 的分量全为整数,就不必再继续分枝; 若 的LP问题的最优解 的某个分量 不为整数,就把 按 或 分解成 .类似的,用上述方法继续分解下去,