资源描述：
《第五章 整数规划》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第五章整数规划第一节数学模型及解的特点要求一部分或全部决策变量必须取整数值的规划问题称为整数规划在整数规划中去掉取整数的约束，剩下的目标函数和约束条件构成的规划问题称为该整数规划的松弛问题若整数规划的松弛问题是线性规划，则称该整数规划为整数线性规划整数线性规划的数学模型松弛问题整数线性规划的几种类型纯整数线性规划混合整数线性规划0-1型整数线性规划整数规划的例子例1（p130）时段12345678服务员最少数目10x18x29x311x413x5853例2（p130）项目j投资额利润xjajxjcjxj整数线性规划问题解的特点整数规划的可行解集合是它的松弛问题可
2、行解集合的一个子集，即整数规划的可行解一定是其松弛问题的可行解（反之不然）整数规划问题的最优目标函数值不会优于其松弛问题最优解的目标函数值若松弛问题的可行解满足整数约束，则它也是整数规划的可行解整数规划问题的最优解不能由其松弛问题最优解经过简单取整得到松弛问题最优解整数规划最优解例4分支定界法分支：若松弛问题最优解中存在变量xi=bi’不满足整数约束，记[bi’]为不超过bi’的最大整数，则构造两个新的约束xi≤[bi’]，和xi≥[bi’]+1。将它们分别并入到原松弛问题中，形成原松弛问题的两个分支（后继问题）。当分支的最优解也不满足整数约束时，可以继续构造它
3、们的分支。定界：在分支的过程中，若某个后继问题恰好获得了整数规划的一个可行解，则这一可行解的目标函数值可看成一个“界限”，作为处理其他分支的依据分支定界法举例考虑如下的整数规划问题（IP）其相应的松弛问题为（LP）松弛问题（LP）的解为x1=3/2，x2=10/3；maxz=29/6LP的最优解不满足整数条件，可任选其中一个变量进行分支，这里选x1=3/2进行分支。利用最接近3/2的两个整数1，2构造两个新的约束x1≤1,x1≥2将它们分别并入到LP中得到两个后继问题LP1和LP2。后继问题的可行域如图ABCDEF依此类推，继续构造后继问题直至获得整数规划的最优
4、解整数规划的最优解为x1=3，x2=1（图中E点）或x1=2，x2=2（图中F点），maxz=4LPAx1=3/2,x2=10/3z=29/6LP2Cx1=1,x2=7/3z=10/3LP1Bx1=2,x2=23/9z=41/9LP11无可行解LP12Dx1=33/14,x2=2z=61/14LP122Cx1=2,x2=2z=4LP121Ex1=3,x2=1z=4x1≤1x1≥2x2≤2x2≥3x1≤2x1≥3第四节0-1型整数规划0-1变量：只能取值0或1的变量。0-1变量也称为逻辑变量。它常用来表示两个选项中非此即彼的选择。如P是一个方案，则类似，设A1，A
5、2，A3是三个方案，则可以用(x1,x2,x3)=(0,1,1)表示采用方案A2,A3但不用方案A1，(x1,x2,x3)=(1,0,1)表示采用方案A1,A3但不用方案A2再比如x1+x2+x3=1表示方案A1,A2,A3中恰好采用一个x1+x2+x3≤2表示方案A1,A2,A3中最多采用两个x1+x2+x3≥2表示方案A1,A2,A3中至少采用两个x1≥x3表示如果采用方案A3,则必采用方案A1••••••例如p130例20-1型变量还常常用来表示在多个不相容的条件（目标）之间的选择。例如p131例3y=1若建工厂A30若建工厂A4xij为工厂Ai运往需求地
6、Bj的物质数量目标函数约束条件0-1型整数规划问题的解法枚举法：列出变量取值为0或1的可能的组合（若有n个变量则有2n个组合），再逐一验证它们是否满足约束条件，然后对满足约束条件的可行解计算目标函数值，其中目标函数值最优的就是最优解方法的改进：通过设置过滤条件有效地减少验证组合为可行解的次数。(x1,x2,x3)zABCD过滤条件(0,0,0)(0,0,1)05YYYYYYYY(0,1,0)-2YYYY(0,1,1)3YNYY(1,0,0)3YYYY(1,0,1)8YYYY(1,1,0)1YNYY(1,1,1)6YNYYz≥0z≥5z≥8(x1,x2,x3)zA
7、BCD过滤条件(0,0,0)(0,0,1)(0,1,0)(0,1,1)(1,0,0)(1,0,1)(1,1,0)(1,1,1)05-233816YYYYYYYYYYYYz≥0z≥5z≥8指派问题指派问题的标准形式有n个人和n件事，已知第i个人做第j件事的费用为cij(i,j=1,2,…,n),要求确定人和事之间的一一指派方案，使完成这n件事的总费用最小。标准形式的特点：每个人必须承担也仅承担一项任务，每项任务必须有人承担承担任务的人数与任务数相同目标函数最小化对何人做何事没有限制指派问题数学模型若引入如下的0-1型变量则数学模型为指派问题的解可以用矩阵表示：若矩
8、阵X是指派问题的一个可行
