[管理学]第五章_整数规划ppt课件.ppt

《[管理学]第五章_整数规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章整数规划第一节数学模型及解的特点在数学规划问题中要求一部分或全部决策变量必须取整数值的规划问题称为整数规划在整数规划中去掉取整数的约束，剩下的目标函数和约束条件构成的规划问题称为该整数规划的松弛问题若整数规划的松弛问题是线性规划，则称该整数规划为整数线性规划（只讨论整数线性规划）整数线性规划的数学模型松弛问题整数线性规划的几种类型纯整数线性规划混合整数线性规划0-1型整数线性规划整数规划的例子例1（p124）时段12345678服务员最少数目10x18x29x311x413x5853例2（p124）项目j投资额利润xjajxjcjxj整

2、数线性规划问题解的特点整数规划的可行解集合是它的松弛问题可行解集合的一个子集，即整数规划的可行解一定是其松弛问题的可行解（反之不然）整数规划问题的最优目标函数值不会优于其松弛问题最优解的目标函数值若松弛问题的可行解满足整数约束，则它也是整数规划的可行解整数规划问题的最优解不能由其松弛问题最优解经过简单取整得到如用“舍入取整法”可得到4个点即(2，2),(2，3),(3，2),(3，3)。显然，它们都不可能是整数规划的最优解。松弛问题最优解整数规划最优解例4不能通过舍入取整地方法，由松弛问题的解得到整数规划的最优解分支定界法分支：若松弛问题最优

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

4、解不满足整数条件，可任选其中一个变量进行分支，这里选x1=3/2进行分支。利用最接近3/2的两个整数1，2构造两个新的约束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无可行解LP

5、12Dx1=33/14,x2=2z=61/14LP122Cx1=2,x2=2z=4LP121Ex1=3,x2=1z=4x1≤1x1≥2x2≤2x2≥3x1≤2x1≥3问题LP2是否应继续分支。上界41/9下界0上界61/14下界0上界4下界4（1）先求解整数规划的松弛问题，若其无最优解，这时IP也无最优解，停止求解；若其有最优解，且符合整数条件，则此整数最优解即为相应IP的最优解，停止求解；若其是非整数最优解，记其目标函数值为z'，转下一步。（2）定界，用观察法找IP的一个整数可行解，求得其目标函数值，并记作z,以z*表示IP的最优值,这时有

6、:z≤z*≤z'(3)对z'问题分支，在z'问题的最优解中任选一个不符合整数条件的变量xj，其值为bj，以[bj]表示不大于bj的最大整数，构造两个约束条件xj≤[bj]，和xj≥[bj]+1将这两个约束条件分别加到z‘所代表的问题，构成两个新的线性规划分支，求解它们。分支定界法步骤：（4）比较、定界与剪枝，新分支中（包括未剪掉且未分的分支）的最大最优值作为IP新的上界z'，可得到的最大整数最优解的目标函数值作为IP新的下界z，若IP新的上下界相等，则此新上（下）界即为IP的最优值，对应的解为最优解，停止计算；否则对无最优解的分支、最优目标函

7、数小于z的分枝予以剪枝，以后不再考虑，转（3）。第四节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中至少

8、采用两个x1≥x3表示如果采用方案A3,则必采用方案A1••••••例如p124例20-1型变量还常常用来表示在多个不相容的条件（目标）之间的选择。例如p125例3