整数规划可认为是在相应的线性规划的基础上增加变量为整数的约束条件。如果不考虑整数约束,整数规划就变成了一个线性规划,这个线性规划称为整数规划的松弛问题(Slack Problem)。
首先求出整数规划相应的松弛问题(即不考虑整数限制)的最优解,若求得的最优解符合整数要求,则这个解就是原整数规划的最优解;若不满足整数条件,则任选一个不满足整数条件的变量来构造两个新的约束,使原问题分成两个问题,在原可行域中剔除部分非整数解,如此不断重复,直到获得一个整数解。
其次,整数规划的最优解不会优于相应线性规划的最优解。这样,对极大化问题来说,相应线性规划的目标函数最优值是原整数规划函数值的上界;对极小化问题来说,相应线性规划的目标函数的最优值是原整数规划目标函数值的下界。
对于最大化问题,在分支的过程中,如果求得一个整数解,则其他分支的松弛问题的最优解也必须大于这个整数解。只有大于这个整数解,才有必要再接着分支;如果不大于这个整数解,就可以剔除掉,不再考虑其分支,即“剪枝”。这样一来就可以简化计算步骤,提高解题效率。
分支为整数规划最优解的出现创造了条件,缩小了求解范围,而定界则可以提高求解的效率。分支定界法(Branch Bound Method)就是依据这种思路进行求解的。分支定界法的处理思路类似于解决复杂管理系统的分解和协调原理。对于一个大系统,人们认识不清,不便于数量化,则考虑将之分解为不同的子系统,以便理解系统和进行数量化处理。例如,可以将企业经营系统细分为生产系统、销售系统、采购系统、库存系统、物流系统、财务系统、信息系统等。
分支定界法可用于解纯整数或混合的整数规划问题。该法于20世纪60年代初由兰德·多伊格(Iand Doig)和戴金(Dakin)等人提出。
分支定界法具有以下优点:
①任何整数模型均可用(混合整数规划、全整数规划);
②思路简单灵活;
③适合计算机求解。因此现在它已是解整数规划的重要方法。
目前已普遍应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。