运筹学 第5章 整数规划.ppt

《运筹学 第5章 整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第五章整数规划第一节数学模型及解的特点要求一部分或全部决策变量必须取整数值的规划问题称为整数规划在整数规划中去掉取整数的约束，剩下的目标函数和约束条件构成的规划问题称为该整数规划的松弛问题若整数规划的松弛问题是线性规划，则称该整数规划为整数线性规划整数线性规划的数学模型松弛问题整数线性规划的几种类型纯整数线性规划混合整数线性规划0-1型整数线性规划整数规划的例子例1（p130）时段12345678服务员最少数目10x18x29x311x413x5853例2（p124）项目j投资额利润xjajxjcjxj0-1型变量还常常用来表示在多个不相容的条件（目标）之间的选择。例如p125例3y

2、=1若建工厂A30若建工厂A4xij为工厂Ai运往需求地Bj的物质数量目标函数约束条件整数线性规划问题解的特点整数规划的可行解集合是它的松弛问题可行解集合的一个子集，即整数规划的可行解一定是其松弛问题的可行解（反之不然）整数规划问题的最优目标函数值不会优于其松弛问题最优解的目标函数值若松弛问题的可行解满足整数约束，则它也是整数规划的可行解整数规划问题的最优解不能由其松弛问题最优解经过简单取整得到松弛问题最优解整数规划最优解例4不能通过舍入取整地方法，由松弛问题的解得到整数规划的最优解分支定界法分支：若松弛问题最优解中存在变量xi=bi’不满足整数约束，记[bi’]为不超过bi’的最大

3、整数，则构造两个新的约束xi≤[bi’]，和xi≥[bi’]+1。将它们分别并入到原松弛问题中，形成原松弛问题的两个分支（后继问题）。当分支的最优解也不满足整数约束时，可以继续构造它们的分支。定界：在分支的过程中，若某个后继问题恰好获得了整数规划的一个可行解，则这一可行解的目标函数值可看成一个“界限”，作为处理其他分支的依据分支定界法举例考虑如下的整数规划问题（IP）其相应的松弛问题为（LP）松弛问题（LP）的解为x1=3/2，x2=10/3；maxz=29/6LP的最优解不满足整数条件，可任选其中一个变量进行分支，这里选x1=3/2进行分支。利用最接近3/2的两个整数1，2构造两个

4、新的约束x1≤1,x1≥2将它们分别并入到LP中得到两个后继问题LP1和LP2。后继问题的可行域如图ABCDEF依此类推，继续构造后继问题（取目标函数值大的先分支）直至获得整数规划的最优解整数规划的最优解为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≤

5、2x1≥3问题LP2是否应继续分支。第四节0-1型整数规划0-1变量：只能取值0或1的变量。0-1变量也称为逻辑变量。它常用来表示两个选项中非此即彼的选择。如P是一个方案，则类似，设A1，A2，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,则必采用方案A

6、1••••••例如p130例20-1型变量还常常用来表示在多个不相容的条件（目标）之间的选择。例如p125例3y=1若建工厂A30若建工厂A4xij为工厂Ai运往需求地Bj的物质数量目标函数约束条件含有相互排斥的约束条件的问题设工序B的每周工时约束为假设工序B还有一种新的加工方式，相应的每周工时约束为如果工序B只能从两种加工方式中选择其中一种，那么上面两式就是互为排斥的两个约束条件。为了表示在这两个约束条件之间进行的选择，可以引入如下的0-1变量：y1=0，若工序B采用了原加工方式1，若工序B不采用了原加工方式y2=0，若工序B采用了新加工方式1，若工序B不采用了新加工方式和于是两个

7、互斥的约束条件可以下述三个约束条件统一起来：其中M1与M2都是形式上的大正数。注：关于变量的约简一般地，要从p个约束条件中恰好选择q个条件，则可以引入0-1变量：yi=0，若选择了第i个约束条件1，若不选择了第i个约束条件(i=1,…,p)于是采用下列约束条件组就可以达到目的：指派问题指派问题的标准形式有n个人和n件事，已知第i个人做第j件事的费用为cij(i,j=1,2,…,n),要求确定人和事之间的一一指派方案，使完成这n件事的总费用最小。标准形式的特