文档介绍：1运筹学教程版权所有,未经准许,不得翻制2第五章整数规划整数规划及其数学模型用分支定界法求解整数规划0-1型整数规划指派问题及其LINGO模型3一、整数规划数学模型的一般形式要求一部分或全部决策变量必须取整数值的规划问题称为整数规划(integer programming,简记IP)。不考虑整数条件,由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题(slack problem)。若松弛问题是一个线性规则,则称该整数规划为整数线性规划(integer linear programming)。整数线性规划数学模型的一般形式为:第一节整数规划及其数学模型4第一节整数规划及其数学模型Opt Z = c1x1 + c2 x2 + ... + cn xn (1-1)11 1 12 2 1 121 1 22 2 2 21 1 2 21, 2, , )( , )( , )...................................................................................( , )n nn nm m mn n mii na x a x a x ba x a x a x ba x a x a x bx?? ????????? ??????????? ??????????部分或全部取整( (1-2)5整数线性规划问题分为下列几种类型: :指全部决策变量部必须取整数值的整数线性规划。有时,也称为全整数规划。 :指决策变量中有一部分必须取整数值,另一部分可以不取整数值的整数线性规划。 -1型整数线性规划:指决策变量只能取值0或1的整数线性规划。第一节整数规划及其数学模型6本章仅讨论整数线性规划。后面提到的整数规划,一般都是指整数线性规划。整数规划的实例很多。例如,我们前面介绍的生产问题,如果产量的单位是件,则往往就要求变量取整数。另外,在表示工厂何时开工等问题时,往往需要利用0-1型整数变量。二、整数规划解的特点整数线性规划及其松弛问题,从解的特点上看,二者之间既有密切的联系,又有本质区别。第一节整数规划及其数学模型7松弛问题作为一个线性规划问题,其可行解的集合是一个凸集,任意两个可行解的凸组合仍为可行解。整数规划问题的可行解集合是它的松弛问题可行解集合的一个子集,任意两个可行解的凸组合不一定满足整数约束条件,因而不一定仍为可行解。由于整数规划问题的可行解一定也是它的松弛问题的可行解(反之则不一定),所以,整数规划问题最优解的目标函数值不会优于松弛问题最优解的目标函数值。第一节整数规划及其数学模型8在一般情况下,松弛问题的最优解不会刚好满足变量的整数约束条件,因而不是整数规划的可行解,自然就不是整数规划的最优解。此时,若对松弛问题的这个最优解中不符合整数要求的分量简单地取整数,所得到的解不一定是整数规划问题的最优解,甚至还不一定是整数规划问题的可行解。第一节整数规划及其数学模型9画出可行域见图4-1。在图4-1中,四边形OBPC及其内部的点为松弛问题的可行域,其中那些整数格点为整数规划问题的可行解。根据目标函数等值线的优化方向,P点(x1=18/7, x2=19/7)就是其松弛问题的最优解,z=94/7。?????????????且取整数0,823324max21212121xxxxxxxxZ例1考虑下面的整数规划问题:第一节整数规划及其数学模型10在P点附近对x1和x2简单取整,可得四点:A1,A2,A3和A4。其中,Al和A2为非可行解;A3和A4虽为可行解,但不是最优解。图4-1 例1的图解法第一节整数规划及其数学模型