整数规划问题最优解的目标函数值不会优于松弛问题最优解的目标.ppt

运筹学教程 第五章 整 数 规 划 第一节 整数规划及其数学模型 一、?? 整数规划数学模型的一般形式 要求一部分或全部决策变量必须取整数值的规划问题称为整数规划(integer programming，简记IP)。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题(slack problem)。若松弛问题是一个线性规则，则称该整数规划为整数线性规划(integer linear programming)。整数线性规划数学模型的一般形式为： 第一节 整数规划及其数学模型 Opt Z = c1 x1 + c2 x2 + ... + cn xn (1-1) 第一节 整数规划及其数学模型 整数线性规划问题分为下列几种类型： 1．纯整数线性规划：指全部决策变量部必须取整数值的整数线性规划。有时，也称为全整数规划。 2．混合整数线性规划：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。 3．0-1型整数线性规划：指决策变量只能取值0或1的整数线性规划。 第一节 整数规划及其数学模型 本章仅讨论整数线性规划。后面提到的整数规划，一般都是指整数线性规划。 整数规划的实例很多。例如，我们前面介绍的生产问题，如果产量的单位是件，则往往就要求变量取整数。另外，在表示工厂何时开工等问题时，往往需要利用0-1型整数变量。 二、?? 整数规划解的特点 整数线性规划及其松弛问题，从解的特点上看，二者之间既有密切的联系，又有本质区别。 第一节 整数规划及其数学模型 松弛问题作为一个线性规划问题，其可行解的集合是一个凸集，任意两个可行解的凸组合仍为可行解。整数规划问题的可行解集合是它的松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。由于整数规划问题的可行解一定也是它的松弛问题的可行解（反之则不一定），所以，整数规划问题最优解的目标函数值不会优于松弛问题最优解的目标函数值。 第一节 整数规划及其数学模型 在一般情况下，松弛问题的最优解不会刚好满足变量的整数约束条件，因而不是整数规划的可行解，自然就不是整数规划的最优解。此时，若对松弛问题的这个最优解中不符合整数要求的分量简单地取整数，所得到的解不一定是整数规划问题的最优解，甚至还不一定是整数规划问题的可行解。 第一节 整数规划及其数学模型 画出可行域见图4-1 。在图4-1中，四边形OBPC及其内部的点为松弛问题的可行域，其中那些整数格点为整数规划问题的可行解。根据目标函数等值线的优化方向，P点（x1=18/7, x2=19/7）就是其松弛问题的最优解，z＝94/7。 第一节 整数规划及其数学模型 在P点附近对x1和x2简单取整，可得四点：A1，A2，A3和A4。其中，Al和A2为非可行解；A3和A4虽为可行解，但不是最优解。 第一节 整数规划及其数学模型 本例整数规划的最优解为A*点(x1＝4，x2=2)，其目标函数值Z =12。 由于整数规划及其松弛问题之间的上述特殊关系，像例4先求松弛问题最优解，再用简单取整的方法虽然直观简单，却并不是求解整数规划的有效方法。 第二节 用分支定界法求解整数规划 通常，混合整数规划问题一般有无限多个可行解。即使是纯整数规划问题，随着问题规模的扩大，其可行解的数目也将急剧增加。因此通过枚举全部可行解，并从中筛选出最优解的算法无实际应用价值。分支定界法(branch and bound method)是一种隐枚举法(implicit enumeration)或部分枚举法，它是在枚举法基础上的改进。分支定界法的关键是分支和定界。 第二节 用分支定界法求解整数规划 若整数规划的松弛问题的最优解不符合整数要求，假设Xi=b*不符合整数要求；[b*]是不超过b*的最大整数，则构造两个约束条件：Xi ≤ [b*]和Xi ≥[b*]+1。分别将其并入上述松弛问题中，从而形成两个分支，即两个后继问题。这两个后继问题的可行域中包含原整数规划问题的所有可行解。而在原松弛问题可行域中，满足的一部分区域在以后的求解过程中被遗弃了，然而它不包含整数规划的任何可行解。 第二节 用分支定界法求解整数规划 根