运筹学 第5章 整数规划

第五章整数规划第一节数学模型及解的特点要求一部分或全部决策变量必须取整数值的规划问题称为整数规划在整数规划中去掉取整数的约束，剩下的目标函数和约束条件构成的规划问题称为该整数规划的松弛问题若整数规划的松弛问题是线性规划，则称该整数规划为整数线性规划整数线性规划的数学模型数中的一部分或全部取整njnjijijnjjjxxxnjxmibxaxcz,,,,,2,1,0,,2,1,),(max2111njxmibxaxczjnjijijnjjj,,2,1,0,,2,1,),(max11松弛问题整数线性规划的几种类型•纯整数线性规划•混合整数线性规划•0-1型整数线性规划整数规划的例子例1（p130）时段12345678服务员最少数目10x18x29x311x413x5853且为整数0,,,35813119810min5215545435432432132121154321xxxxxxxxxxxxxxxxxxxxxxxxxxxxz例2（p124）不投资对项目投资对项目jjxj,0,1项目j投资额利润xjajxjcjxj),,2,1(1021max765431211njxxxxxxxxBxaxczjnjjjnjjj或0-1型变量还常常用来表示在多个不相容的条件（目标）之间的选择。例如p125例3B1B2B3B4A12934400A28357600A37612200A44525200350400300150y=1若建工厂A30若建工厂A4xij为工厂Ai运往需求地Bj的物质数量目标函数)]1(15001200[min4141yyxczijijij约束条件1or0)4,3,2,1,(0)1(200200600400150300400350s.t.4443424134333231242322211413121144342414433323134232221241312111yjixyxxxxyxxxxxxxxxxxxxxxxxxxxxxxxxxxxij整数线性规划问题解的特点•整数规划的可行解集合是它的松弛问题可行解集合的一个子集，即整数规划的可行解一定是其松弛问题的可行解（反之不然）•整数规划问题的最优目标函数值不会优于其松弛问题最优解的目标函数值•若松弛问题的可行解满足整数约束，则它也是整数规划的可行解•整数规划问题的最优解不能由其松弛问题最优解经过简单取整得到且取整数0,823324max21212121xxxxxxxxz松弛问题最优解整数规划最优解例4不能通过舍入取整地方法，由松弛问题的解得到整数规划的最优解分支定界法•分支：若松弛问题最优解中存在变量xi=bi’不满足整数约束，记[bi’]为不超过bi’的最大整数，则构造两个新的约束xi≤[bi’]，和xi≥[bi’]+1。将它们分别并入到原松弛问题中，形成原松弛问题的两个分支（后继问题）。当分支的最优解也不满足整数约束时，可以继续构造它们的分支。•定界：在分支的过程中，若某个后继问题恰好获得了整数规划的一个可行解，则这一可行解的目标函数值可看成一个“界限”，作为处理其他分支的依据分支定界法举例取整数2121212121,0,3121451149maxxxxxxxxxxxz考虑如下的整数规划问题（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依此类推，继续构造后继问题（取目标函数值大的先分支）直至获得整数规划的最优解整数规划的最优解为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问题LP2是否应继续分支。第四节0-1型整数规划0-1变量：只能取值0或1的变量。0-1变量也称为逻辑变量。它常用来表示两个选项中非此即彼的选择。如P是一个方案，则PPx当决策不用方案当决策采用方案,1,0类似，设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,则必采用方案A1••••••例如p130例20-1型变量还常常用来表示在多个不相容的条件（目标）之间的选择。例如p125例3B1B2B3B4A12934400A28357600A37612200A44525200350400300150y=1若建工厂A30若建工厂A4xij为工厂Ai运往需求地Bj的物质数量目标函数)]1(15001200[min4141yyxczijijij约束条件1or0)4,3,2,1,(0)1(200200600400150300400350s.t.4443424134333231242322211413121144342414433323134232221241312111yjixyxxxxyxxxxxxxxxxxxxxxxxxxxxxxxxxxxij含有相互排斥的约束条件的问题设工序B的每周工时约束为1505.03.021xx假设工序B还有一种新的加工方式，相应的每周工时约束为1204.02.021xx如果工序B只能从两种加工方式中选择其中一种，那么上面两式就是互为排斥的两个约束条件。为了表示在这两个约束条件之间进行的选择，可以引入如下的0-1变量：y1=0，若工序B采用了原加工方式1，若工序B不采用了原加工方式y2=0，若工序B采用了新加工方式1，若工序B不采用了新加工方式和于是两个互斥的约束条件可以下述三个约束条件统一起来：11204.02.01505.03.02122211121yyyMxxyMxx其中M1与M2都是形式上的大正数。注：关于变量的约简一般地，要从p个约束条件中恰好选择q个条件，则可以引入0-1变量：yi=0，若选择了第i个约束条件1，若不选择了第i个约束条件(i=1,…,p)qpypiyMbxapiiiiinjjij11,...,2,1,于是采用下列约束条件组就可以达到目的：指派问题指派问题的标准形式有n个人和n件事，已知第i个人做第j件事的费用为cij(i,j=1,2,…,n),要求确定人和事之间的一一指派方案，使完成这n件事的总费用最小。标准形式的特点：•每个人必须承担也仅承担一项任务，每项任务必须有人承担•承担任务的人数与任务数相同•目标函数最小化•对何人做何事没有限制指派问题数学模型事人做第若不指派第事人做第若指派第jijixij,0,1),2,1,(1,0),,2,1(1),,2,1(1min1111njixnjxnixxczijniijnjijninjijij或若引入如下的0-1型变量则数学模型为每个人必须承担也只能承担一项工作每项工作必须指派给一人也只能指派给一人明显地不同的n阶指派问题，有相同的可行解。但最优解可能不同。区别在于它们目标函数的系数不同。称指派问题的目标函数系数构成的矩阵为系数矩阵。指派问题的解可以用矩阵表示：nnijxX)(若矩阵X是指派问题的一个可行解，则它的每一行恰好有一个元素等于1其余元素为零，每一列也恰好有一个元素等于1其余元素为零。因此指派问题有n!个可行解。nnijcC)(例（p143）B1B2B3B4B5A14871512A279171410A3691287A46714610A5691210661012961061476781296101417971215784系数矩阵：