运筹学05整数规划

《运筹学05整数规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、整数规划IntegerProgramming整数规划的数学模型MathematicalModelofIP整数规划的分支定界法BranchandBoundMethodforIP整数规划的割平面法CuttingPlaneMethodforIP0-1整数规划BinaryIntegerProgramming指派问题AssignmentProblem1整数规划的数学模型相关定义一部分或全部决策变量取整数值的规划问题称为整数规划(IntegerProgramming)整数规划中不考虑整数条件所对应的规划问题，称为该整数规划的松弛问题(SlackPro

2、blem)松弛问题为线性规划的整数规划问题称为整数线性规划(IntegerLinearProgramming)整数线性规划一般形式min(max)z=c1x1+c2x2+…+cnxnai1x1+ai2x2+…+ainxn=bi(i=1,2,…,m)xi≥0(i=1,2,…,n)且部分或全部取整数整数规划的几种类型纯整数线性规划(PureIntegerLinearProgramming)：决策变量全为整数的线性规划混合整数线性规划(MixedIntegerLinearProgramming)：至少一个变量为整数和非整数的线性规划0-1型整数

3、线性规划(0-1IntegerLinearProgramming)：全部变量为0或1的线性规划例1：某服务部门各时段(每2小时为一时段)需要的服务员最少人数见下表。按规定服务员连续工作8小时为一班。现要求安排服务员的工作班次，使服务部门服务员总数最少。时段12345678服务员最少人数10891113853解答：设在第j时段开始上班的服务人数为xj。数学模型为：minz=x1+x2+x3+x4+x5x1≥10x1+x2≥8x1+x2+x3≥9x1+x2+x3+x4≥11x2+x3+x4+x5≥13x3+x4+x5≥8x4+x5≥5x5≥3

4、xi取非负整数(i=1,2,3,4,5)用Excel求得结果ABCDEFGH1变量x1x2x3x4x52取值1008053目标函数系数11111234约束条件01110105约束条件02118106约束条件031119187约束条件04111111188约束条件05111113139约束条件0611181310约束条件07115511约束条件08135整数规划解的特点松弛问题可行解的集合是一个凸集，任意两点凸组合依然是可行解；而整数线性规划可行解的集合是松弛问题可行解的集合的一个子集，任意两点凸组合不一定是可行解。整数线性规划的最优解的目

5、标函数值不会优于其松弛问题。考虑下面的整数规划问题maxz=x1+4x2-2x1+3x2≤3x1+2x2≤8x1,x2取非负整数012345678P整数规划最优解松弛问题最优解A*z=x1+4x2=12z=x1+4x2=94/7z=x1+4x2x1x2x1+2x2=8-2x1+3x2=32整数规划的分支定界法分支定界法(BranchandBoundMethod)是在枚举法基础上的改进，是一种隐枚举法(ImplicitEnumerationMethod)或者部分枚举法(PartialEnumerationMethod)，不是一种有效算法。思

6、路：利用其松弛问题的最优解(值)来分支定界。关键：分支定界法的关键是分支和定界。分支：若得到松弛问题的一个最优解，分量x1=x1*不是一个整数。则将原松弛问题分别加上x1≤[x1*]和x1≥[x1*]+1这两个约束条件，构成两个松弛问题继续求解，这个过程体现了分支。定界：在以后的计算中遇到整数规划问题的最优解，其目标函数就可以设定为一个界限。不考虑比这个值小的可行解和最优解。例2：求解整数规划问题A整数规划问题A1松弛问题Bmaxz=40x1+90x2maxz=40x1+90x29x1+7x2≤569x1+7x2≤567x1+20x2≤7

7、07x1+20x2≤70x1,x2为非负整数x1,x2≥0序问题来源x1x2zz1z2处理(1)B松弛问题4.811.82355.880356x1分支(2)B1B+x1≤442.13490349x2分支(3)B2B+x1≥551.57341.430341x2分支(4)B11B1+x2≤242340340341可行(5)B12B1+x2≥31.433327.14界外停止(6)B21B2+x2≤15.441307.78界外停止(7)B22B1+x2≥2无解停止3整数规划的割平面法割平面法的基本思想求该整数规划松弛问题的最优解如最优解恰是一个整

8、数解，则停止如果线性规划的最优解不是整数解：则要求构造一个新的约束，对线性规划问题的可行域进行切割，切除已经得到的线性规划的最优解，但保留原可行域中所有的整数解求解新的线性规划问题如此一直进行